| Abstract |
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. |