More Web Proxy on the site http://driver.im/

article

Hierarchical RLE level set: A compact and versatile deformable surface representation

Authors:

Michael B. Nielsen,

Christopher Batty,

Ken MusethAuthors Info & Claims

ACM Transactions on Graphics (TOG), Volume 25, Issue 1

Pages 151 - 175

https://doi.org/10.1145/1122501.1122508

Published: 01 January 2006 Publication History

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.

References

[1]

Adalsteinsson, D. and Sethian, J. A. 1995. A fast level set method for propagating interfaces. J. Computat. Phys. 118, 2, 269--277.

[2]

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.

[3]

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 &num;27. ACM SIGGRAPH, Los Angeles, CA. ISBN 1-58113-950-X.

[4]

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.

[5]

Bridson, R. 2003. Computational aspects of dynamic surfaces. dissertation. Stanford University, Stanford, CA.

[6]

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.

[7]

Carlson, M. 2004. Rigid, melting and flowing fluid. Ph.D. dissertation, Georgia Institute of Technology, Atlanta, GA.

[8]

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.

[9]

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.

[10]

Enright, D., Losasso, F., and Fedkiw, R. 2004. A fast and accurate semi-Lagrangian particle level set method. Comput. Struct. 83, 479--490.

[11]

Enright, D., Marschner, S., and Fedkiw, R. 2002. Animation and rendering of complex water surfaces. ACM Trans. Graph. 21, 3, 736--744.

[12]

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.

[13]

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.

[14]

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.

[15]

Guendelman, E., Bridson, R., and Fedkiw, R. 2003. Nonconvex rigid bodies with stacking. ACM Trans. Graph. 22, 3, 871-- 878.

[16]

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.

[17]

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.

[18]

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.

[19]

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.

[20]

Ju, T. 2004. Robust repair of polygonal models. ACM Trans. Graph. 23, 3, 888--895.

[21]

LeVeque, R. 1996. High-resolution conservative algorithms for advection in incompressible flow. SIAM J. Numer. Anal. 33, 627--665.

[22]

Liu, X., Osher, S., and Chan, T. 1994. Weighted essentially nonoscillatory schemes. J. Comput. Physat. 115, 200--212.

[23]

Losasso, F., Fedkiw, R., and Osher, S. 2005. Spatially adaptive techniques for level set methods and incompressible flow. Comput. Fluids. In Press.

[24]

Losasso, F., Gibou, F., and Fedkiw, R. 2004. Simulating water and smoke with an octree data structure. ACM Trans. Graph. 23, 3, 457--462.

[25]

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.

[26]

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.

[27]

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.

[28]

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.

[29]

Osher, S. and Shu, C. 1991. High-order essentially nonoscillatory schemes for Hamilton-Jacobi equations. SIAM J. Num. Anal. 28, 907--922.

[30]

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.

[31]

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.

[32]

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.

[33]

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.

[34]

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.

[35]

Shu, C. and Osher, S. 1988. Efficient implementation of essentially non-oscillatory shock capturing schemes. J. Computat. Phys. 77, 439--471.

[36]

Stam, J. 1999. Stable fluids. In Proceedings of SIGGRAPH 99. Computer Graphics Proceedings, Annual Conference Series. 121--128.

[37]

Strain, J. 1999. Tree methods for moving interfaces. J. Computat. Phys. 151, 2, 616--648.

[38]

Whitaker, R. T. 1998. A level-set approach to 3d reconstruction from range data. Int. J. Comput. Vision 29, 3, 203--231.

[39]

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.

[40]

Yngve, G. and Turk, G. 2002. Robust creation of implicit surfaces from polygonal meshes. IEEE Trans. Visual. Comput. Graph. 8, 4, 346--359.

Cited By

Niu LWang ZLin ZZhang YYan YHe Z(2024)Voxel-Based Navigation: A Systematic Review of Techniques, Applications, and ChallengesISPRS International Journal of Geo-Information10.3390/ijgi1312046113:12(461)Online publication date: 19-Dec-2024
https://doi.org/10.3390/ijgi13120461
Wang SDeng YDeng MYu HZhou JChen DKomura TWu JZhu B(2024)An Eulerian Vortex Method on Flow MapsACM Transactions on Graphics10.1145/368799643:6(1-14)Online publication date: 19-Dec-2024
https://dl.acm.org/doi/10.1145/3687996
Kim DLee MMuseth K(2024)NeuralVDB: High-resolution Sparse Volume Representation using Hierarchical Neural NetworksACM Transactions on Graphics10.1145/364181743:2(1-21)Online publication date: 23-Jan-2024
https://dl.acm.org/doi/10.1145/3641817
Show More Cited By

Index Terms

Hierarchical RLE level set: A compact and versatile deformable surface representation
1. Computing methodologies
  1. Computer graphics
    1. Animation
      1. Physical simulation
    2. Shape modeling
      1. Parametric curve and surface models
      2. Volumetric models
  2. Modeling and simulation
    1. Simulation types and techniques
      1. Simulation by animation
2. Mathematics of computing
  1. Continuous mathematics
    1. Topology
      1. Geometric topology

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 techniques

We 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

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Graphics

ACM Transactions on Graphics Volume 25, Issue 1

January 2006

175 pages

ISSN:0730-0301

EISSN:1557-7368

DOI:10.1145/1122501

Issue’s Table of Contents

Copyright © 2006 ACM.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 January 2006

Published in TOG Volume 25, Issue 1

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

92
Total Citations
View Citations
1,351
Total Downloads

Downloads (Last 12 months)26
Downloads (Last 6 weeks)6

Reflects downloads up to 21 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Niu LWang ZLin ZZhang YYan YHe Z(2024)Voxel-Based Navigation: A Systematic Review of Techniques, Applications, and ChallengesISPRS International Journal of Geo-Information10.3390/ijgi1312046113:12(461)Online publication date: 19-Dec-2024
https://doi.org/10.3390/ijgi13120461
Wang SDeng YDeng MYu HZhou JChen DKomura TWu JZhu B(2024)An Eulerian Vortex Method on Flow MapsACM Transactions on Graphics10.1145/368799643:6(1-14)Online publication date: 19-Dec-2024
https://dl.acm.org/doi/10.1145/3687996
Kim DLee MMuseth K(2024)NeuralVDB: High-resolution Sparse Volume Representation using Hierarchical Neural NetworksACM Transactions on Graphics10.1145/364181743:2(1-21)Online publication date: 23-Jan-2024
https://dl.acm.org/doi/10.1145/3641817
Dendukuri ATunc MDemirel DKockara SHalic T(2023)Unified Framework for Real-Time Fluid Simulation in Virtual Rotator Cuff Arthroscopic Skill Trainer (ViRCAST)2023 IEEE 23rd International Conference on Bioinformatics and Bioengineering (BIBE)10.1109/BIBE60311.2023.00063(346-353)Online publication date: 4-Dec-2023
https://doi.org/10.1109/BIBE60311.2023.00063
Xiong SWang ZWang MZhu B(2022)A clebsch method for free-surface vortical flow simulationACM Transactions on Graphics10.1145/3528223.353015041:4(1-13)Online publication date: 22-Jul-2022
https://dl.acm.org/doi/10.1145/3528223.3530150
Goel PJames D(2022)Unified many-worlds browsing of arbitrary physics-based animationsACM Transactions on Graphics10.1145/3528223.353008241:4(1-15)Online publication date: 22-Jul-2022
https://dl.acm.org/doi/10.1145/3528223.3530082
Aleksandrov MZlatanova SHeslop D(2021)Voxelisation Algorithms and Data Structures: A ReviewSensors10.3390/s2124824121:24(8241)Online publication date: 9-Dec-2021
https://doi.org/10.3390/s21248241
段忠(2021)Research Progress of Solid Modeling TechnologyComputer Science and Application10.12677/CSA.2021.11411211:04(1089-1097)Online publication date: 2021
https://doi.org/10.12677/CSA.2021.114112
Hu YLiu JYang XXu MKuang YXu WDai QFreeman WDurand F(2021)QuanTaichiACM Transactions on Graphics10.1145/3450626.345967140:4(1-16)Online publication date: 19-Jul-2021
https://dl.acm.org/doi/10.1145/3450626.3459671
Chen CHu MChu WChen J(2021)A Real-Time Sculpting and Terrain Generation System for Interactive Content CreationIEEE Access10.1109/ACCESS.2021.31054179(114914-114928)Online publication date: 2021
https://doi.org/10.1109/ACCESS.2021.3105417
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents