In computer science, a level set is a data structure designed to represent discretely sampled dynamic level sets of functions.
A common use of this form of data structure is in efficient image rendering.
The powerful level-set method is due to Osher and Sethian 1988.
[1] However, the straightforward implementation via a dense d-dimensional array of values, results in both time and storage complexity of
is the cross sectional resolution of the spatial extents of the domain and
The narrow band level set method, introduced in 1995 by Adalsteinsson and Sethian,[2] restricted most computations to a thin band of active voxels immediately surrounding the interface, thus reducing the time complexity in three dimensions to
Periodic updates of the narrowband structure, to rebuild the list of active voxels, were required which entailed an
time complexity was eliminated in the approximate "sparse field" level set method introduced by Whitaker in 1998.
This allows incremental extension of the active region as needed without incurring any significant overhead.
storage space is still required by the sparse field level set method.
The sparse block grid method, introduced by Bridson in 2003,[6] divides the entire bounding volume of size
then stores pointers only to those blocks that intersect the narrow band of the level set.
Block allocation and deallocation occur as the surface propagates to accommodate to the deformations.
, but retains the constant time access inherent to dense grids.
The octree level set method, introduced by Strain in 1999[7] and refined by Losasso, Gibou and Fedkiw,[8] and more recently by Min and Gibou[9] 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.
An advantage of the level method on octree data structures is that one can solve the partial differential equations associated with typical free boundary problems that use the level set method.
The CASL research group[10] has developed this line of work in computational materials, computational fluid dynamics, electrokinetics, image guided surgery and controls.
The run-length encoding (RLE) level set method, introduced in 2004,[11] 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.
random access, where r is the number of runs per cross section.
Additional efficiency is gained by applying the RLE scheme in a dimensional recursive fashion, a technique introduced by Nielsen & Museth's similar DT-Grid.
The Hash Table Local Level Set method, introduced in 2011 by Eyiyurekli and Breen [13] and extended in 2012 by Brun, Guittet and Gibou,[14] 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.
Three main reasons for worse efficiency are listed: Corbett in 2005 [15] introduced the point-based level set method.