Progressive Simplification of Tetrahedral Meshes Preserving All Isosurface Topologies

Yi Jen Chiang, Xiang Lu

    Research output: Contribution to journalConference articlepeer-review


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

    Original languageEnglish (US)
    Pages (from-to)493-504
    Number of pages12
    JournalComputer Graphics Forum
    Issue number3
    StatePublished - 2003
    EventEuropean Association for Computer Graphics 24th Annual Conference EUROGRAPHICS 2003 - Granada, Spain
    Duration: Sep 1 2003Sep 6 2003

    ASJC Scopus subject areas

    • Computer Graphics and Computer-Aided Design


    Dive into the research topics of 'Progressive Simplification of Tetrahedral Meshes Preserving All Isosurface Topologies'. Together they form a unique fingerprint.

    Cite this