TECHNICAL REPORT ARCHIVE

Simple and Optimal Output-Sensitive Computation of Contour Trees

TR-CIS-2003-02 (06/20/2003)
Yi-Jen Chiang and Xiang Lu

pdf version of this paper

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

Back to previous page