Optimal memory constrained isosurface extraction

Efficient isosurface extraction from large volume data sets requires special algorithms and data structures. Such algorithms typically either use a hierarchical spatial subdivision of the volume or they organize the scalar values attached to the cells of the volume, i.e., intervals, in some suitable data structures. Octrees, kd-trees, and interval trees are commonly applied. However, these data structures demand storage space that can be many times as large as the original volume data. In practice storage space is constrained and, therefore, new algorithms may be necessary that adapt the size of the data structures to the given limits. We present a hybrid algorithm which combines binary space partition (BSP) trees with fast search methods at some leaf nodes of the BSP-tree and memory-free linear search at the remaining leaf nodes. The method optimally trades off space for extraction speed