Ben Houston
Michael B. Nielsen
Christopher Batty
Ken Museth
Abstract
This article introduces the Hierarchical Run-Length Encoded (H-RLE) Level Set data structure. This novel data structure combines the best features of the DT-Grid (of Nielsen and Museth [2004]) and the RLE Sparse Level Set (of Houston et al. [2004]) to provide both optimal efficiency and extreme versatility. In brief, the H-RLE level set employs an RLE in a dimensionally recursive fashion. The RLE scheme allows the compact storage of sequential nonnarrowband regions while the dimensionally recursive encoding along each axis efficiently compacts nonnarrowband planes and volumes. Consequently, this new structure can store and process level sets with effective voxel resolutions exceeding 5000 × 3000 × 3000 (45 billion voxels) on commodity PCs with only 1 GB of memory. This article, besides introducing the H-RLE level set data structure and its efficient core algorithms, also describes numerous applications that have benefited from our use of this structure: our unified implicit object representation, efficient and robust mesh to level set conversion, rapid ray tracing, level set metamorphosis, collision detection, and fully sparse fluid simulation (including RLE vector and matrix representations.) Our comparisons of the popular octree level set and Peng level set structures to the H-RLE level set indicate that the latter is superior in both narrowband sequential access speed and overall memory usage.
- Adalsteinsson, D. and Sethian, J. A. 1995. A fast level set method for propagating interfaces. J. Computat. Phys. 118, 2, 269--277. Google Scholar
- Batty, C. and Houston, B. 2005. The visual simulation of wispy smoke. In Proceedings of the SIGGRAPH 2005 on Sketches & Applications. ACM Press, New York, NY. Google Scholar
- Breen, D., Fedkiw, R., Museth, K., Osher, S., Sapiro, G., and Whitaker, R. 2004. Level Sets and PDE Methods for Computer Graphics. ACM SIGGRAPH '04 COURSE #27. ACM SIGGRAPH, Los Angeles, CA. ISBN 1-58113-950-X. Google Scholar
- Breen, D. E. and Whitaker, R. T. 2001. A level-set approach for the metamorphosis of solid models. IEEE Trans. Visual. Comput. Graph. 7, 2, 173--192. Google Scholar
- Bridson, R. 2003. Computational aspects of dynamic surfaces. dissertation. Stanford University, Stanford, CA. Google Scholar
- Bridson, R., Marino, S., and Fedkiw, R. 2003. Simulation of clothing with folds and wrinkles. In SCA '03: Proceedings of the 2003 ACM SIGGRAPH/Eurographics Symposium on Computer animation. Eurographics Association, Aire-la-Ville, Switzerland, Switzerland, 28--36. Google Scholar
- Carlson, M. 2004. Rigid, melting and flowing fluid. Ph.D. dissertation, Georgia Institute of Technology, Atlanta, GA. Google Scholar
- Curless, B. and Levoy, M. 1996. A volumetric method for building complex models from range images. In Computer Graphics 30. Annual Conference Series. 303--312. Google Scholar
- de Araujo, B. R. and Jorge, J. A. P. 2004. Curvature dependent polygonization of implicit surfaces. In Proceedings of the XVII Brazilian Symposium on Computer Graphics and Image Processing (SIBGRAPI'04). IEEE, Computer Society Press, Los Alamitos, CA. 266--273. Google Scholar
- Enright, D., Losasso, F., and Fedkiw, R. 2004. A fast and accurate semi-Lagrangian particle level set method. Comput. Struct. 83, 479--490. Google Scholar
- Enright, D., Marschner, S., and Fedkiw, R. 2002. Animation and rendering of complex water surfaces. ACM Trans. Graph. 21, 3, 736--744. Google Scholar
- Foster, N. and Fedkiw, R. 2001. Practical animation of liquids. In SIGGRAPH '01: Proceedings of the 28th Annual Conference on Computer Graphics and Interactive Techniques. ACM Press, New York, NY, 23--30. Google Scholar
- Frisken, S. F., Perry, R. N., Rockwood, A. P., and Jones, T. R. 2000. Adaptively sampled distance fields: A general representation of shape for computer graphics. In Proceedings of SIGGRAPH 2000. Computer Graphics Proceedings, Annual Conference Series. ACM Press, New York, NY/Addison Wesley Longman, Reading, MA, 249--254. Google Scholar
- Goktekin, T. G., Bargteil, A. W., and O'Brien, J. F. 2004. A method for animating viscoelastic fluids. ACM Trans. Graph. 23, 3, 463--468. Google Scholar
- Guendelman, E., Bridson, R., and Fedkiw, R. 2003. Nonconvex rigid bodies with stacking. ACM Trans. Graph. 22, 3, 871-- 878. Google Scholar
- Houston, B., Bond, C., and Wiebe, M. 2003. A unified approach for modeling complex occlusions in fluid simulations. In Proceedings of the SIGGRAPH 2003 on Sketches & Applications. ACM Press, New York, NY. Google Scholar
- Houston, B., Nielsen, M. B., Batty, C., Nilsson, O., and Museth, K. 2005. Gigantic deformable surfaces. In Proceedings of the SIGGRAPH 2005 on Sketches & Applications. ACM Press, New York, NY. Google Scholar
- Houston, B., Wiebe, M., and Batty, C. 2004. RLE sparse level sets. In Proceedings of the SIGGRAPH 2004 on Sketches & Applications. ACM Press, New York, NY. Google Scholar
- Irving, G., Teran, J., and Fedkiw, R. 2004. Invertible finite elements for robust simulation of large deformation. In SCA '04: Proceedings of the 2004 ACM SIGGRAPH/Eurographics Symposium on Computer Animation. New York, NY, 131--140. Google Scholar
- Ju, T. 2004. Robust repair of polygonal models. ACM Trans. Graph. 23, 3, 888--895. Google Scholar
- LeVeque, R. 1996. High-resolution conservative algorithms for advection in incompressible flow. SIAM J. Numer. Anal. 33, 627--665. Google Scholar
- Liu, X., Osher, S., and Chan, T. 1994. Weighted essentially nonoscillatory schemes. J. Comput. Physat. 115, 200--212. Google Scholar
- Losasso, F., Fedkiw, R., and Osher, S. 2005. Spatially adaptive techniques for level set methods and incompressible flow. Comput. Fluids. In Press.Google Scholar
- Losasso, F., Gibou, F., and Fedkiw, R. 2004. Simulating water and smoke with an octree data structure. ACM Trans. Graph. 23, 3, 457--462. Google Scholar
- Mauch, S. 2000. A fast algorithm for computing the closest point and distance transform. Go online to http://www.acm.caltech.edu/seanm/software/cpt/cpt.pdf.Google Scholar
- Museth, K., Breen, D. E., Whitaker, R. T., and Barr, A. H. 2002. Level set surface editing operators. ACM Trans. Graph. 21, 3, 330--338. Google Scholar
- Nielsen, M. B. and Museth, K. 2006. Dynamic Tubular Grid: An efficient data structure and algorithms for high resolution level sets. J. Sci. Comput. 26, 1, 1--39. Google Scholar
- Osher, S. and Sethian, J. A. 1988. Fronts propagating with curvature-dependent speed: Algorithms based on Hamilton-Jacobi formulations. J. Computat. Phys. 79, 12--49. Google Scholar
- Osher, S. and Shu, C. 1991. High-order essentially nonoscillatory schemes for Hamilton-Jacobi equations. SIAM J. Num. Anal. 28, 907--922. Google Scholar
- Peng, D., Merriman, B., Osher, S., Zhao, H., and Kang, M. 1999. A PDE-based fast local level set method. J. Computat. Phys. 155, 2, 410--438. Google Scholar
- Rasmussen, N., Enright, D., Nguyen, D., Marino, S., Sumner, N., Geiger, W., Hoon, S., and Fedkiw, R. 2004. Directable photorealistic liquids. In SCA '04: Proceedings of the 2004 ACM SIGGRAPH/Eurographics Symposium on Computer Animation. ACM Press, New York, NY, 193--202. Google Scholar
- Sethian, J. A. 1996. A fast marching level set method for monotonically advancing fronts. In Proceedings of the National Academy of Sciences of the USA 93, 4 (Feb.), 1591--1595.Google Scholar
- Shah, M., Cohen, J. M., Patel, S., Lee, P., and Pighin, F. 2004. Extended Galilean invariance for adaptive fluid simulation. In SCA '04: Proceedings of the 2004 ACM SIGGRAPH/Eurographics Symposium on Computer Animation. ACM Press, New York, NY, 213--221. Google Scholar
- Shewchuk, J. R. 1994. An introduction to the conjugate gradient method without the agonizing pain. Go online to http://www.cs.cmu.edu/quake-papers/painless-conjugate-gradient.pdf.Google Scholar
- Shu, C. and Osher, S. 1988. Efficient implementation of essentially non-oscillatory shock capturing schemes. J. Computat. Phys. 77, 439--471. Google Scholar
- Stam, J. 1999. Stable fluids. In Proceedings of SIGGRAPH 99. Computer Graphics Proceedings, Annual Conference Series. 121--128. Google Scholar
- Strain, J. 1999. Tree methods for moving interfaces. J. Computat. Phys. 151, 2, 616--648. Google Scholar
- Whitaker, R. T. 1998. A level-set approach to 3d reconstruction from range data. Int. J. Comput. Vision 29, 3, 203--231. Google Scholar
- Wiebe, M. and Houston, B. 2004. The Tar Monster: Creating a character with fluid simulation. In Proceedings of the SIGGRAPH 2004 on Sketches & Applications. ACM Press, New York, NY. Google Scholar
- Yngve, G. and Turk, G. 2002. Robust creation of implicit surfaces from polygonal meshes. IEEE Trans. Visual. Comput. Graph. 8, 4, 346--359. Google Scholar
Index Terms
- Hierarchical RLE level set: A compact and versatile deformable surface representation
Recommendations
Out-of-core and compressed level set methods
This article presents a generic framework for the representation and deformation of level set surfaces at extreme resolutions. The framework is composed of two modules that each utilize optimized and application specific algorithms: 1) A fast out-of-...
Geometric Texturing Using Level Sets
We present techniques for warping and blending (or subtracting) geometric textures onto surfaces represented by high resolution level sets. The geometric texture itself can be represented either explicitly as a polygonal mesh or implicitly as a level ...
Level set surface editing operators
SIGGRAPH '02: Proceedings of the 29th annual conference on Computer graphics and interactive techniquesWe present a level set framework for implementing editing operators for surfaces. Level set models are deformable implicit surfaces where the deformation of the surface is controlled by a speed function in the level set partial differential equation. In ...
Comments