|
|
|
 |
TR-CIS-2003-02 (06/20/2003)
Yi-Jen Chiang and Xiang Lu
Abstract
Isosurface extraction is one of the most powerful techniques in the
investigation of volume datasets in scientific visualization. The
contour tree is a fundamental data structure for fast isosurface
extraction, and has also been used to build user interfaces to report
the complete topological characterization of the isosurfaces embedded
in the volume data, as well as to simplify the volume data to build a
multi-resolution hierarchy while preserving the isosurface topologies.
In this paper, we present a new output-sensitive algorithm for
computing the contour tree. Our algorithm is simple, and achieves the
optimal bound of \Theta(m + t \log t) in running time for both
structured- and unstructured-grid volume datasets, where m is the
number of cells of the input volume, and t is the number of critical
points in the input volume, which bounds the size of the contour
tree. Our algorithm improves the previous best running time of
O(m\alpha(n) + n\log n) given in [5] for unstructured grids (where n is
the number of vertices of the input volume), and as the algorithm of
[5], works in all dimensions as well. The experiments show that
typically t is less than 5% of the overall number n of the input
vertices, and that our algorithm is 2 to 3 times as fast as the
previous best algorithm [5].