Level sets have recently proven successful in many areas of computer graphics including water simulations and geometric modeling. However, current implementations of these level set methods are limited by factors such as computational efficiency, storage requirements and the restriction to a domain enforced by the convex boundaries of an underlying cartesian computational grid. Here we present a novel very memory efficient narrow band data structure, dubbed the Sparse Grid, that enables the representation of grid independent high resolution level sets. The key features our new data structure are: Both memory usage and computational efficiency scales linearly with the size of the interface The values in the narrow band can be compressed using quantization without compromising visual quality The level set propagation is independent of the boundaries of an underlying grid. Unlike previous method that use fixed computational grids with convex boundaries our Sparse Grid can expand and/or contract dynamically in any direction with non-convex boundaries. Our data structure generalizes to any number of dimensions. Our flexible data structure can transparently be integrated with the existing finite difference schemes typically used to numerically solve the level set equation on fixed uniform grids.
Sigrad'04: Svenska Föreningen För Grafisk Databehandling, 2004, p. 59-60
Main Research Area:
The Annual SIGRAD Conference, SIGRAD 2004. Special theme: Environmental Visualization