Speeding Up Isosurface Extraction using Interval Trees
P. Cignoni, P. Marino, C. Montani, E. Puppo, R. Scopigno
Abstract
The interval tree is an optimally efficient search structure proposed by
Edelsbrunner to retrieve intervals of the real line that
contain a given query value.
We propose the application of such a data structure to the fast location
of cells intersected by an isosurface in a volume dataset. The resulting
search method can be applied to both structured and unstructured volume
datasets, and it can be applied incrementally to exploit coherence between
isosurfaces.
We also address issues about storage requirements, and operations
other than the location of cells, whose impact is relevant in the whole
isosurface extraction task.
In the case of unstructured grids, the overhead due to the search structure
is compatible with the storage cost of the dataset, and local coherence in
the computation of isosurface patches is exploited through a hash table.
In the case of a structured dataset, a new conceptual organization is
adopted, called the {\em chess-board approach}, wich exploits the regular
structure of the dataset to reduce memory usage and to exploit local coherence.
In both cases, efficiency in the computation of surface normals on the
isosurface is obtained by a pre-computation of the gradients at the
vertices
of the mesh.
Experiments on different kinds of input show that the practical
performance of the method reflects its theoretical optimality.
|