Efficient isosurface extraction from large volume data sets requires
special algorithms and data structures that allow to quickly
identify large parts of the data set that do not contain any part of the
surface and which therefore can be eliminated from the search. 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 auxiliary data structures demand
storage space that can be several times as large as the original volume data
itself. In practise memory capacity is constrained and, therefore, new
algorithms may be necessary that adapt the size of the additional 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. We develop the theory for the
optimization, provide implementation details and an example demonstrating the
efficiency of the approach.
