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 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 is the number of spatial dimensions of the domain.

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 Differential constructions over the narrow band domain edge require careful interpolation and domain alteration schemes to stabilise the solution.

Sparse field

time complexity was eliminated in the approximate "sparse field" level set method introduced by Whitaker in 1998. storage space is still required by the sparse field level set method. See for implementation details.

Sparse block grid

The sparse block grid method, introduced by Bridson in 2003, divides the entire bounding volume, but retains the constant time access inherent to dense grids.

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 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 has developed this line of work in computational materials, computational fluid dynamics, electrokinetics, image-guided surgery and controls.

Run-length encoded

The run-length encoding (RLE) level set method, introduced in 2004, 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.

Hash Table Local Level Set

The Hash Table Local Level Set method was introduced in 2011 by Eyiyurekli and Breen and extended in 2012 by Brun, Guittet, and Gibou, access to the data. However, Brun et al. conclude that their method, while being easier to implement, performs worse than a quadtree implementation. They find that Three main reasons for worse efficiency are listed:

1. 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;

2. the performances are deteriorated by extrapolation procedures on the outer edges of the local grid and

3. 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.

References