In this paper, we propose a novel technique for constructing multiple levels of a tetrahedral volume dataset while preserving the topologies of all isosurfaces embedded in the data. Our simplification technique has two major phases. In the segmentation phase, we segment the volume data into topological-equivalence regions, that is, the sub-volumes within each of which all isosurfaces have the same topology. In the simplification phase, we simplify each topological-equivalence region independently, one by one, by collapsing edges from the smallest to the largest errors (within the user-specified error tolerance, for a given error metrics), and ensure that we do not collapse edges that may cause an isosurface-topology change. We also avoid creating a tetrahedral cell of negative volume (i.e., avoid the fold-over problem). In this way, we guarantee to preserve all isosurface topologies in the entire simplification process, with a controlled geometric error bound. Our method also involves several additional novel ideas, including using the Morse theory and the implicit fully augmented contour tree, identifying types of edges that are not allowed to be collapsed, and developing efficient techniques to avoid many unnecessary to expensive checkings, all in an integrated manner. The experiments show that all the resulting isosurfaces preserve the topologies, and have good accuracies in their geometric shapes. Moreover, we obtain nice data-reduction rates, with competitively fast running times.
展开▼
