In computer science a level set data structure is designed to represent discretely sampled dynamic level sets functions.
Contents
- Chronological developments
- Narrow band
- Sparse field
- Sparse block grid
- Octree
- Run length encoded
- Hash Table Local Level Set
- Point based
- References
A common use of this form of data structure is in efficient image rendering. The underlying method constructs a signed distance field that extends from the boundary, and can be used to solve the motion of the boundary in this field.
Chronological developments
The powerful level set method is due to Osher and Sethian 1988. However, the straightforward implementation via a dense d-dimensional array of values, results in both time and storage complexity of
Narrow band
The narrow band level set method, introduced in 1995 by Adalsteinsson and Sethian, restricted most computations to a thin band of active voxels immediately surrounding the interface, thus reducing the time complexity in three dimensions to
Sparse field
This
Sparse block grid
The sparse block grid method, introduced by Bridson in 2003, divides the entire bounding volume of size
Octree
The octree level set method, introduced by Strain in 1999 and refined by Losasso, Gibou and Fedkiw, and more recently by Min and Gibou uses a tree of nested cubes of which the leaf nodes contain signed distance values. Octree level sets currently require uniform refinement along the interface (i.e. the narrow band) in order to obtain sufficient precision. This representation is efficient in terms of storage,
Run-length encoded
The run-length encoding (RLE) level set method, introduced in 2004, applies the RLE scheme to compress regions away from the narrow band to just their sign representation while storing with full precision the narrow band. The sequential traversal of the narrow band is optimal and storage efficiency is further improved over the octree level set. The addition of an acceleration lookup table allows for fast
Hash Table Local Level Set
The Hash Table Local Level Set method, introduced in 2012 by Brun, Guittet and Gibou, only computes the level set data in a band around the interface, as in the Narrow Band Level-Set Method, but also only stores the data in that same band. A hash table data structure is used, which provides an
as it is, [...] a quadtree data structure seems more adapted than the hash table data structure for level-set algorithms.
Three main reasons for worse efficiency are listed:
- to obtain accurate results, a rather large band is required close to the interface, which counterbalances the absence of grid nodes far from the interface;
- the performances are deteriorated by extrapolation procedures on the outer edges of the local grid and
- the width of the band restricts the time step and slows down the method.
Point-based
Corbett in 2005 introduced the point-based level set method. Instead of using a uniform sampling of the level set, the continuous level set function is reconstructed from a set of unorganized point samples via moving least squares.