A technical sketch presented in the Fluids and Level Sets session at SIGGRAPH 2004

RLE Sparse Level Sets
A Fast & Scalable Implicit Surface Representation

Ben Houston
Exocortex Technologies, Inc
ben @ exocortex.org
Mark Wiebe
Frantic Films
mwiebe @ franticfilms.com
Christopher Batty
Frantic Films
cbatty @ franticfilms.com

General Website Navigation:
Ben Houston's Homepage    The Project Gallery

Other SIGGRAPH / ACM TOG sketches & publications:
Hierarchical RLE Level Set: A Compact and Versatile Deformable Surface Representation (ACM TOG January 2006)
Visual Simulation of Wispy Smoke - A particle-based and multi-resolution approach (SIGGRAPH 2005)
Gigantic Deformable Surfaces - a novel level set data structure combining DT-Grid and RLE features (SIGGRAPH 2005)
The Tar Monster - creating a character with fluid simulation (SIGGRAPH 2004)
Modeling Complex Occlusions in Fluid Simulations - a unified level set-based approach (SIGGRAPH 2003)
Clara.io: Online 3D editor (another of my projects)


Comparison of an animated character represented first as
a tri-mesh (red) and then as a RLE sparse level set (blue)  [9 MB Quicktime]

The RLE (run-length encoded) sparse level set is a novel scalable level set representation.  This compact level set representation, and it's ability to represent animated characters, was used in the creation of the "Tar Monster" CG character featured in the movie Scooby Doo 2.

(Please note: this web write-up contains more accurate O-notations than given in the sketch below.)

A. The RLE Sparse Level Set Structure

The novel RLE sparse level set representation has many beneficial characteristics:

(1) highly scalable: +100 million voxel volumes can be presented in less than 15 MB,
(2) fast to access randomly: O( log r ), where r is the number of runs in a single line cross section,
(3) sequential narrow band traversal is near optimal: O( (n2)/D + 1 ) / narrow band element
(4) approximate distance values are provided throughout the bounding volume, and
(5) easily adapted to work with all existing level set methods developed for regular grid structures.

 These advantages are not all shared by the octree [Strain 1999; Frisken 2000], the sparse field method [Whitaker 1998], or the sparse block grid [Bridson 2003] scalable level set representations.

The format of the RLE sparse level set structure is as follows: Essentially, each row of the level set is considered as a stream of data, and we use a run-length encoding of the row based on its value. We store 3 types of runs: +infinity (Φ(x) < -m), +infinity (Φ(x) > m), and defined ((x)| m), for some bandwidth value m . The defined values of the narrow interface band are associated with a secondary array storing the actual values, while the values of inside or outside runs are discarded.


Diagram: the run structure of

a 2D RLE sparse level set

Random Access.  Indexing into individual level set rows is performed using a simple table lookup based on the 2 coordinates perpendicular to the axis of compression. Locating the correct run within a row is done using a binary search after which finding an individual level set value of the run requires just an offset.  Random access thus results O( log r ) time where r is the number of runs in a single row.

Memory Usage. Assuming that in any O(n3) grid there are only O(n2) cells close to the surface, as is the case for smooth enough geometry, the RLE sparse level set structure scales with near optimal, O(n2+R+D), space and time costs, where R is the number of runes, D is the number of defined values and n is the side-length of the bounding volume.

Encoding. Constructing an RLE sparse field structure has both space and time complexity of O(n2+R+D), where n is the side-length of the bounding volume, R is the number of runs and D is the total number of defined voxels.

CSG Operations. Common level set constructive solid geometry (CSG) operations such as union, intersection and subtraction can be performed very efficiently, using only O(n2+R1+D1+R2+D2) operations when the encoding axes of the input RLE sparse level sets match.
 

B. Representing Traditionally Modeled and Animated Characters Using RLE Sparse Level Sets

Representing an animated polygon-based CG character via a series of RLE sparse level sets in a robust and efficient manner while maintaining fidelity involves solving multiple challenges:

(1) how to create from a polygon mesh an RLE sparse level set with a bounding volume of n3 voxels in less than O(n3) operations,
(2) robustness in the presence of imperfectly closed meshes, which are quite commonly produced by traditional polygon-character modeling and animation techniques, and
(3) how to avoid temporal anti-aliasing issues that could arise from the inability of regular level sets to represent features smaller than the voxel widths.

Buddha RLE sparse level set turntable [4.9 MB Quicktime]
The Stanford Buddha tri-mesh model, consisting of ~150K faces, is rotated relative to the fixed level set coordinate system.  For each frame of the animation the model is (1) converted to a 600x600x600 RLE sparse level set volume, (2) down-sampled 300x300x300 to reduce aliasing artifacts, and (3) then rendered.  Tri-mesh to RLE sparse level set conversion required approx. 4 minutes per frame.

C. Summary

The RLE sparse level set structure, or structures based on it's general design, will most likely have significant uses in the field of physical simulation-based computer graphics.  Obvious areas where the RLE sparse level set structure can be applied are (a) fluid simulation [Enright et al. 2002; Houston et al. 2003], (b) rigid-body dynamics [Guendelman et al. 2003], (c) soft-body dynamics [Irving et al. 2003] and (d) cloth simulation [Bridson et al. 2002].

 

Houston, B., Wiebe, M. & C. Batty.  (2004)  "RLE Sparse Level Sets."  Proceedings of the SIGGRAPH 2004 Conference on Sketches & Applications. ACM Press. [PDF]  (Supplemental Materials [PDF])

 

@inproceedings{
   author = {Ben Houston and Mark Wiebe and Christopher Batty},
   title = {RLE Sparse Level Sets},
   booktitle = {Proceedings of the SIGGRAPH 2004 Conference on
       Sketches \& Applications},
   year = {2004},
   location = {Los Angeles, California},
   publisher = {ACM Press},
   }

This research was supported in part by NRC IRAP Grant #482564.