Eurographics Symposium on Geometry Processing (2005)M. Desbrun, H. Pottmann (Editors)Extraction and Simplification of Iso-surfaces in Tandem†Dominique Attali1, David Cohen-Steiner2, and Herbert Edelsbrunner31LIS-CNRS, Grenoble, France2Geometrica-INRIA, Sophia-Antipolis, France3Duke University and Raindrop Geomagic, North Carolina, USAAbstractThe tandem algorithm combines the marching cube algorithm for surface extraction and the edge contractionalgorithm for surface simplification in lock-step to avoid the costly intermediate step of storing the entire extractedsurface triangulation. Beyond this basic strategy, we introduce refinements to prevent artifacts in the resultingtriangulation, first, by carefully monitoring the amount of simplification during the process and, second, by drivingthe simplification toward a compromise between shape approximation and mesh quality. We have implemented thealgorithm and used extensive computational experiments to document the effects of various design options and tofurther fine-tune the algorithm.Categories and Subject Descriptors (according to ACM CCS): I.3.5 [Computer Graphics]: Boundary representations,Hierarchy and geometric transformations F.2.2 [Analysis of Algorithms and Problem Complexity]: Geometricalproblems and computations I.4.10 [Image Processing and Computer Vision]: Volumetric1. IntroductionThe work of Hoppe [Hop96] and of Garland and Heckbert[GH97] opened a new chapter on surface simplification as acentral theme in geometric processing. In this paper, we con-tribute to the growing body of work on variants, extensions,and refinements of the original algorithm.Historical perspective. Motivated by the demands oflarge datasets, the generation of simplified representationshas long been a topic within computer graphics. As ap-plied to geometric shapes, the focus has been on tri-angulated surfaces embedded in three-dimensional space[HDD∗93, RB93, SZL92]. A breakthrough in simplifyingsuch surfaces has been achieved in the late 1990s when Gar-land and Heckbert combined the edge contraction opera-tion developed by Hoppe and co-workers [HDD∗93, Hop96]with anisotropic square norms representing the accumulatederror [GH97]. The confluence of these two ideas formed thestarting point of developments in several directions:†Research by the first two authors was partially supported bythe IST Program of the EU under Contract IST-2002-506766(Aim@Shape). Research by the third author was partially supportedby NSF grant CCR-00-86013 (BioGeometry).• variants of the algorithm, including the restriction totopology preserving edge contractions [DEGN99] and theformulation of memoryless error measures [LT98];• evaluation of the generated triangulations, including themathematical analysis of the original algorithm [HG99]and the development of a software tool for experimentalcomparison [CRS98];• extensions to higher dimensions, including surfaceswith attributes [GH98, Hop99] and tetrahedral meshes[SG98, THJW98];• memory-efficient processing orders that focus the algo-rithm to a moving window and this way simplify trian-gulations that may be too large to fit into main memory[ILGS03, Lin00, WK03].Because of the central importance of simplification as ameans to abstract essential information from large datasets,it is likely these themes will continue to be at the forefrontof geometry processing research.Our contributions. The work reported in this paper startedwith the realization that the limitation of edge contractionsto memory-efficient processing orders leads to artifacts inthe generated triangulations. Two questions arise: “how dowe capture or quantify the artifacts?” and “how do we avoidc The Eurographics Association 2005.D. Attali, D. Cohen-Steiner & H. Edelsbrunner / Extraction and Simplification of Iso-surfaces in Tandemthem?”. The answers to these questions are not independent.Specifically, we use the insights gained in quantifying ar-tifacts towards modifying the algorithm to counteract theircreation. Our approach is a mix of theoretical and experi-mental analysis and design. We base our experimental workon a particular memory-efficient processing order in whichthe marching cube algorithm for surface extraction is com-bined with the simultaneous simplification of the triangula-tion. Building a surface layer by layer, the marching cube al-gorithm has been intensively studied as a tool for extractingiso-surfaces from density data [LC87, JLSW02, KBSS01].We call our approach the tandem algorithm because it alter-nates the extraction of a layer with the simplification of theaccumulated partial surface. Our contributions are:1. the formulation and implementation of the tandem algo-rithm;2. the refinement of the processing order to counteract thecreation of artifacts;3. the refinement of the error quadric of Garland and Heck-bert to control the mesh quality;4. the quantification of mesh isotropy and directional biasas aspects of mesh quality.We note that the method to control mesh quality is similar tobut different from the one described in [NE04]. On the tech-nical side, our work uses anisotropic square norms, whosemathematical formulation is developed in Appendix A. Eventhough we have based our work on the tandem algorithm,our results apply to other memory-efficient surface simplifi-cation algorithms and to surface simplification in general.Outline. Section 2 describes the marching cube algorithmfor surface extraction and the edge contraction algorithm forsurface simplification. Section 3 explains the tandem algo-rithm, which combines the extraction and simplification ofthe surface into one step. Section 4 introduces measures thatassess the quality of the extracted and simplified surfacesand compares the classical and the tandem algorithms. Sec-tion 5 concludes the paper.2. Classical AlgorithmThe classical algorithm for constructing the iso-surface ofa density function on R3first extracts a fine resolution rep-resentation, which it then simplifies to a more appropriatecoarse resolution. We begin with a description on how thedensity function is given.Density data. The most common representation of a den-sity function F : R3→ R consists of a regular cube grid andspecifies the function value at every vertex. To be specific,let the grid consist of all vertices with integer coordinates0 ≤ i, j,k ≤ m and let F[i, j,k] store the function value atthe point (i, j,k) ∈ R3. We sometimes refer to the third co-ordinate as the rank.
View Full Document
Unlocking...