Content deleted Content added
m →Run-length encoded: typo |
No edit summary |
||
Line 17:
The sparse block grid method, introduced by Bridson in 2003 <ref name=Bridson>Bridson, R. 2003. "Computational aspects of dynamic surfaces (dissertation)." [[Stanford University]], Stanford, California.</ref>, divides the entire bounding volume of size <math>n^3</math> into small cubic blocks of <math>m^3</math> voxels each. A coarse grid of size <math>(n/m
)^3</math> 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. This method has a suboptimal storage complexity of <math>O\left((nm)3 + m^3n^2\right)</math>, but retains the constant time access inherent to dense grids.
===Sparse hash grid===
Bridson also suggests in his dissertation replacing the coarse grid with a hashtable, obtaining optimal storage complexity while retaining constant time access and the same cache friendliness of the small blocks. However, he does not report any experiments with this structure.
===Octree===
| |||