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

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

The RLE (runlength 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 writeup contains more accurate Onotations than given in the sketch below.) A. The RLE Sparse Level Set Structure The novel RLE sparse level set representation has many beneficial characteristics:
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.
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(n^{3}) grid there are only O(n^{2}) cells close to the surface, as is the case for smooth enough geometry, the RLE sparse level set structure scales with near optimal, O(n^{2}+R+D), space and time costs, where R is the number of runes, D is the number of defined values and n is the sidelength of the bounding volume. Encoding. Constructing an RLE sparse field structure has both space and time complexity of O(n^{2}+R+D), where n is the sidelength 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(n^{2}+R_{1}+D_{1}+R_{2}+D_{2})
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 polygonbased CG character via a series of RLE sparse level sets in a robust and efficient manner while maintaining fidelity involves solving multiple challenges:
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 simulationbased
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) rigidbody dynamics [Guendelman et al. 2003],
(c) softbody 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. 