Content deleted Content added
Two author publication was credited to only the first author. Thus, the second author was added. |
No edit summary |
||
Line 18:
===Octree===
The [[octree]] level set method, introduced by Strain in 1999 <ref name=Strain>Strain, J. 1999. "Tree methods for moving interfaces." ''[[Journal of Computational Physics]]''. 151(2)616–648.</ref> and refined by Losasso, Gibou and Fedkiw,<ref name=Losasso>Losasso, F., Gibou, F., & Fedkiw, R. 2004. Simulating water and smoke with an octree data structure. [[ACM Transactions on Graphics]]. 23(3)457–462.</ref> and more recently by Min and Gibou<ref name=MinGibou>Min, C. & Gibou, F. 2007. A second order accurate level set method on non-graded adaptive cartesian grids. [[Journal of Computational Physics]]. 225(1)300–321.</ref> 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, <math>O(n^2),</math> and relatively efficient in terms of access queries, <math>O(\log\, n).</math> 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<ref name=CASL>http://www1.engr.ucsb.edu/~fgibou/Home.html</ref> 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,<ref name=Houston2004>Houston, B., Nielsen, M., Batty, C., Nilsson, O. & K. Museth. 2006. "Hierarchical RLE Level Set: A Compact and Versatile Deformable Surface Representation." ''[[ACM Transactions on Graphics]]''. 25(1).</ref> 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 <math>O(\log r)</math> 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.<ref name=Nielsen>Nielsen, M. B. & Museth K. 2006. "Dynamic Tubular Grid: An efficient data structure and algorithms for high resolution level sets." ''[[Journal of Scientific Computing]]''. 26(1) 1–39.</ref>
===Hash Table Local Level Set===
The Hash Table Local Level Set method, introduced 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 O(1) access to the data.
===Point-based===
| |||