Permission to make digital or hard copies of part or all of this work for personal orclassroom use is granted without fee provided that copies are not made or distributed forprofit or direct commercial advantage and that copies show this notice on the first page orinitial screen of a display along with the full citation. Copyrights for components of thiswork owned by others than ACM must be honored. Abstracting with credit is permitted. Tocopy otherwise, to republish, to post on servers, to redistribute to lists, or to use anycomponent of this work in other works requires prior specific permission and/or a fee.Permissions may be requested from Publications Dept., ACM, Inc., 1515 Broadway, NewYork, NY 10036 USA, fax +1 (212) 869-0481, or [email protected] Repair of Polygonal ModelsTao Ju∗Rice UniversityFigure 1: A synthetically distorted Horse model (left) containing numerous self-intersecting polygons, gaps and holes, and the repaired model(right) with a closed surface.AbstractWe present a robust method for repairing arbitrary polygon mod-els. The method is guaranteed to produce a closed surface thatpartitions the space into disjoint internal and external volumes.Given any model represented as a polygon soup, we construct aninside/outside volume using an octree grid, and reconstruct the sur-face by contouring. Our novel algorithm can efficiently processlarge models containing millions of polygons and is capable of re-producing sharp features in the original geometry.CR Categories: I.3.5 [Computer Graphics]: Computational Ge-ometry and Object Modeling—Boundary representations; Curve,surface, solid, and object representations; Geometric algorithms,languages, and systemsKeywords: model repair, robustness, scan conversion, octree1 IntroductionPolygonal representations are widely used in computer systemsand applications for modeling 3-dimensional geometry. Polygo-nal models can be created from various sources, such as 3D rangescans and computer-aided design software. However, due to limita-tions of these creation methods, the resulting polygonal models of-ten cannot be directly utilized by applications that require a closedmodel as input. By saying closed, we mean that the surface of themodel partitions the entire space into disjoint internal and externalvolumes, so that each polygon lies between an internal volume andan external volume. A non-closed model often contains mesh de-fects such as gaps, holes, self-intersecting polygons, etc. Figure∗e-mail: [email protected] compares two groups of curve models in 2D, one group beingclosed (bottom) and the other not (top).We seek a robust method for repairing an arbitrary polygonalmodel, so that the repaired model is always closed. Due to thediversity and complexity of polygonal models, mesh repair facesdaunting challenges. Specifically, an ideal repair method shouldpossess the following properties:1. Robustness: The method should always produce a closed sur-face for any input model.2. Efficiency: The method should be able to process huge mod-els within reasonable time and space.3. Accuracy: The method should preserve the geometry of theinput model whenever possible.Unfortunately, no existing methods are known to the authors thatsatisfy all the desired properties. In particular, the robustness of therepair method is hard to guarantee, especially for huge input modelswith numerous mesh defects. In this paper, we present a satisfactorysolution using a volumetric approach. Our method takes a polygonsoup (e.g., the horse in figure 1 left) as input, constructs an interme-diate volume grid, and generates the output surface (e.g., the horsein figure 1 right) by contouring the grid. The method is guaran-teed to produce a closed and consistently oriented surface for anyarbitrary input polygonal model. By using memory-less operationsand divide-and-conquer techniques, input models with millions oftriangles can be repaired on a consumer level PC in minutes. As anoption, our method is also capable of reproducing sharp features onthe input surface, which is particularly suitable for repairing CADmodels.1.1 ContributionsAlthough other volumetric techniques have been proposed for re-pairing polygon models [Nooruddin and Turk 2003] or filling holeson the model surface [Curless and Levoy 1996; Davis et al. 2002],our method differs substantially in the following aspects:888© 2004 ACM 0730-0301/04/0800-0888 $5.00Figure 2: Three non-closed curves (top) and three closed curves(bottom). Vertices are represented by dots, internal volumes arecolored dark gray and external volumes are colored light gray.1. Unlike previous methods that rely on a uniform volume grid,we employ a space-efficient octree grid that allows the inputmodel to be repaired and reconstructed at a higher resolutionwith less space consumption. Correspondingly, we present afast, memory-less and numerically robust algorithm for scan-converting an arbitrary input model onto an octree grid.2. The core of our method is a simple and robust algorithmfor determining, at each point on the grid, a sign indicatingwhether the point lies inside or outside the input model. Thesigns are generated as a post-process on the scan-convertedgrid and requires no global iterations. Our algorithm can beefficiently implemented as recursive procedures on the octree.3. Unlike previous volumetric approaches that generate blobbysurfaces, by recording Hermite data, we are able to reproducesharp features in the original model using Dual Contouring[Ju et al. 2002].2 Related works2.1 Mesh-based model repairOne class of model repair methods, which we refer to as mesh-based methods, operate directly on the polygons in the model torepair various geometric and topological errors. Turk and Levoy[Turk and Levoy 1994] introduce mesh zippering for removingoverlapping regions on the mesh when merging multiple range scanimages. Barequet and Kumar [Barequet and Kumar 1997] describean interactive system that closes small cracks by stitching corre-sponding edges and fills big holes by triangulating the detectedhole boundary. A different approach is proposed by Borodin etal. [Borodin et al. 2002] who describe gap closing as progres-sive boundary decimation. Recently, Liepa [Liepa 2003] appliesmesh fairing after hole triangulation so that the patch interpolatesthe shape and density of the surrounding mesh. On the other hand,Gueziec et al. [Gueziec et al. 1998] generate manifold surfacesfrom non-manifold sets of polygons by
View Full Document