Level set (data structures): Difference between revisions

Revision as of 02:27, 14 April 2025

Latest revision as of 12:06, 27 June 2025

(3 intermediate revisions by 2 users not shown)

Line 1:

{{Short description|Data structure used in image rendering}}

In [[computer science]], a '''[[level set]]''' is a data structure designed to represent discretely [[Sampling (statistics)|sampled]] dynamic level sets of functions.

{{Use British English|date=June 2025}}

In [[computer science]], a '''[[level set]]''' is a data structure designed to represent discretely [[Sampling (statistics)|sampled]] dynamic level sets of functions.

A common use of this form of data structure is in efficient image [[Rendering (computer graphics)|rendering]]. The underlying method constructs a [[distance transform|signed distance field]] that extends from the boundary, and can be used to solve the motion of the boundary in this field.

Line 24 ⟶ 26:

===Hash Table Local Level Set===

The Hash Table Local Level Set method, was introduced in 2011 by Eyiyurekli and Breen <ref name=Eyiyurekli>Eyiyurekli, M. & Breen, D. 2011. "Data structures for interactive high resolution level-set surface editing," Proc. Graphics Interface. pp. 95-102.</ref> and extended in 2012 by Brun, Guittet, and Gibou,<ref name=BrunGuittetGibou>Brun, E., Guittet, A. & Gibou, F. 2012. "A local level-set method using a hash table data structure." ''[[Journal of Computational Physics]]''. 231(6)2528-2536.</ref> 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 <math>O(1)</math> 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 {{blockquote|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