Hierarchical RLE Level Set: A Compact and Versatile Deformable Surface Representation

A high resolution Stanford bunny is put through the "Enright" test: A rotational velocity fields warps it, and then the reverse velocity field returns to its original shape.

Paper: PDF

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 non-narrowband regions while the dimensionally recursive encoding along each axis efficiently compacts non-narrowband planes and volumes. Consequently, this new structure can store and process level sets with effective voxel resolutions exceeding 5000x3000x3000 (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.

Video: Quicktime

Authors:
Ben Houston, Exocortex Technologies and Frantic Films
Michael B. Nielsen, University of Arhus
Christopher Batty, University of British Columbia and Frantic Films
Ola Nilsson, Linkoping Institute of Technology
Ken Museth, Linkoping Institute of Technology and University of Arhus

Citation: Houston, B., Nielsen, M., Batty, C., Nilsson, O., and Museth, K. 2006. Hierarchical RLE Level Set: A Compact and Versatile Deformable Surface Representation. ACM Transactions on Graphics, 25(1).

Journal: ACM Transactions on Graphics

Bibtex:

@article{hrle06,
 author = {Ben Houston and Michael B. Nielsen and Christopher Batty and Ola Nilsson and Ken Museth},
 title = {Hierarchical RLE level set: A compact and versatile deformable surface representation},
 journal = {ACM Trans. Graph.},
 volume = {25},
 number = {1},
 year = {2006},
 issn = {0730-0301},
 pages = {151--175},
 doi = {http://doi.acm.org/10.1145/1122501.1122508},
 publisher = {ACM},
 address = {New York, NY, USA},
}

Funding:
National Research Council of Canada
Centre for Interactive Spaces
Swedish Research Council
Frantic Films