DOC PREVIEW
TAMU CSCE 689 - p888-ju

This preview shows page 1-2-3 out of 8 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 8 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 8 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 8 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 8 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

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

TAMU CSCE 689 - p888-ju

Documents in this Course
slides

slides

10 pages

riccardo2

riccardo2

33 pages

ffd

ffd

33 pages

intro

intro

23 pages

slides

slides

19 pages

w1

w1

23 pages

vfsd

vfsd

8 pages

subspace

subspace

48 pages

chapter2

chapter2

20 pages

MC

MC

41 pages

w3

w3

8 pages

Tandem

Tandem

11 pages

meanvalue

meanvalue

46 pages

w2

w2

10 pages

CS689-MD

CS689-MD

17 pages

VGL

VGL

8 pages

ssq

ssq

10 pages

Load more
Download p888-ju
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view p888-ju and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view p888-ju 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?