Automatic restoration of polygon models

ABSTRACT

We present a fully automatic technique which converts an inconsistent input mesh into an output mesh that is guaranteed to be a clean and consistent mesh representing the closed manifold surface of a solid object. The algorithm removes all typical mesh artifacts such as degenerate triangles, incompatible face orientation, non-manifold vertices and edges, overlapping and penetrating polygons, internal redundant geometry, as well as gaps and holes up to a user-defined maximum size ρ. Moreover, the output mesh always stays within a prescribed tolerance ϵ to the input mesh. Due to the effective use of a hierarchical octree data structure, the algorithm achieves high voxel resolution (up to 4096³ on a 2GB PC) and processing times of just a few minutes for moderately complex objects. We demonstrate our technique on various architectural CAD models to show its robustness and reliability.

REFERENCES

• 1: Carlos Andújar , Pere Brunet , Dolors Ayala, Topology-reducing surface simplification using a discrete solid representation, ACM Transactions on Graphics (TOG), v.21 n.2, p.88-105, April 2002 [doi>10.1145/508357.508359]
• 2: Gill Barequet , Christian A. Duncan , Subodh Kumar, RSVP: A Geometric Toolkit for Controlled Repair of Solid Models, IEEE Transactions on Visualization and Computer Graphics, v.4 n.2, p.162-177, April 1998 [doi>10.1109/2945.694983]
• 3: Gill Barequet , Subodh Kumar, Repairing CAD models, Proceedings of the 8th conference on Visualization '97, p.363-ff., October 18-24, 1997, Phoenix, Arizona, United States
• 4: Gill Barequet , Micha Sharir, Filling gaps in the boundary of a polyhedron, Computer Aided Geometric Design, v.12 n.2, p.207-229, March 1995 [doi>10.1016/0167-8396(94)00011-G]
• 5: Stephan Bischoff , Leif P. Kobbelt, Isosurface Reconstruction with Topology Control, Proceedings of the 10th Pacific Conference on Computer Graphics and Applications, p.246, October 09-11, 2002
• 6: B&oslace;hn, J. and Wozny, M. 1992. Automatic cad-model repair: Shell-closure. In Proceedings of the Symposium on Solid Freeform Fabrication. 86--94.
• 7: Borodin, P., Novotni, M., and Klein, R. 2002. Progressive gap closing for mesh repairing. In Advances in Modelling, Animation and Rendering, J. Vince and R. Earnshaw, Eds. Springer Verlag, 201--213.
• 8: Pere Brunet , Isabel Navazo, Solid representation and operation using extended octrees, ACM Transactions on Graphics (TOG), v.9 n.2, p.170-197, April 1990 [doi>10.1145/78956.78959]
• 9: Davis, J., Marschner, S., Garr, M., and Levoy, M. 2002. Filling holes in complex surfaces using volumetric diffusion. In Proceedings of the International Symposium on 3D Data Processing, Visualization, Transmission. 428--438.
• 10: Dolenc, A. and Mäkelä, I. 1991. Optimized triangulation of parametric surfaces. Techn. rep. TKO-B74, Helsinki University of Technology.
• 11: Sarah F. Frisken , Ronald N. Perry , Alyn P. Rockwood , Thouis R. Jones, Adaptively sampled distance fields: a general representation of shape for computer graphics, Proceedings of the 27th annual conference on Computer graphics and interactive techniques, p.249-254, July 2000 [doi>10.1145/344779.344899]
• 12: Michael Garland , Paul S. Heckbert, Surface simplification using quadric error metrics, Proceedings of the 24th annual conference on Computer graphics and interactive techniques, p.209-216, August 1997 [doi>10.1145/258734.258849]
• 13: Sarah F. F. Gibson, Using distance maps for accurate surface representation in sampled volumes, Proceedings of the 1998 IEEE symposium on Volume visualization, p.23-30, October 19-20, 1998, Research Triangle Park, North Carolina, United States [doi>10.1145/288126.288142]
• 14: Rafael C. Gonzalez , Richard E. Woods, Digital Image Processing, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1992
• 15: S. Gottschalk , M. C. Lin , D. Manocha, OBBTree: a hierarchical structure for rapid interference detection, Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, p.171-180, August 1996 [doi>10.1145/237170.237244]
• 16: Alexander Greβ , Reinhard Klein, Efficient Representation and Extraction of 2-Manifold Isosurfaces Using kd-Trees, Proceedings of the 11th Pacific Conference on Computer Graphics and Applications, p.364, October 08-10, 2003
• 17: André Guéziec , Gabriel Taubin , Francis Lazarus , Bill Horn, Cutting and Stitching: Converting Sets of Polygons to Manifold Surfaces, IEEE Transactions on Visualization and Computer Graphics, v.7 n.2, p.136-151, April 2001 [doi>10.1109/2945.928166]
• 18: Igor Guskov , Zoë J. Wood, Topological noise removal, No description on Graphics interface 2001, p.19-26, June 07-09, 2001, Ottawa, Ontario, Canada
• 19: Tao Ju, Robust repair of polygonal models, ACM Transactions on Graphics (TOG), v.23 n.3, August 2004
• 20: Tao Ju , Frank Losasso , Scott Schaefer , Joe Warren, Dual contouring of hermite data, Proceedings of the 29th annual conference on Computer graphics and interactive techniques, July 23-26, 2002, San Antonio, Texas
• 21: Leif Kobbelt , Swen Campagna , Jens Vorsatz , Hans-Peter Seidel, Interactive multi-resolution modeling on arbitrary meshes, Proceedings of the 25th annual conference on Computer graphics and interactive techniques, p.105-114, July 1998 [doi>10.1145/280814.280831]
• 22: Leif P. Kobbelt , Mario Botsch , Ulrich Schwanecke , Hans-Peter Seidel, Feature sensitive surface extraction from volume data, Proceedings of the 28th annual conference on Computer graphics and interactive techniques, p.57-66, August 2001 [doi>10.1145/383259.383265]
• 23: T. Y. Kong , A. Rosenfeld, Digital topology: introduction and survey, Computer Vision, Graphics, and Image Processing, v.48 n.3, p.357-393, Dec. 1989 [doi>10.1016/0734-189X(89)90147-3]
• 24: Peter Liepa, Filling holes in meshes, Proceedings of the 2003 Eurographics/ACM SIGGRAPH symposium on Geometry processing, June 23-25, 2003, Aachen, Germany
• 25: William E. Lorensen , Harvey E. Cline, Marching cubes: A high resolution 3D surface construction algorithm, Proceedings of the 14th annual conference on Computer graphics and interactive techniques, p.163-169, August 1987
• 26: Fakir S. Nooruddin , Greg Turk, Simplification and Repair of Polygonal Models Using Volumetric Techniques, IEEE Transactions on Visualization and Computer Graphics, v.9 n.2, p.191-205, April 2003 [doi>10.1109/TVCG.2003.1196006]
• 27: Hanan Samet , Robert E. Webber, Hierarchical Data Structures and Algorithms for Computer Graphics. Part I., IEEE Computer Graphics and Applications, v.8 n.3, p.48-68, May 1988 [doi>10.1109/38.513]
• 28: Gabriel Taubin, A signal processing approach to fair surface design, Proceedings of the 22nd annual conference on Computer graphics and interactive techniques, p.351-358, September 1995 [doi>10.1145/218380.218473]
• 29: Greg Turk , Marc Levoy, Zippered polygon meshes from range images, Proceedings of the 21st annual conference on Computer graphics and interactive techniques, p.311-318, July 1994 [doi>10.1145/192161.192241]
• 30: Gokul Varadhan , Shankar Krishnan , Young J. Kim , Suhas Diggavi , Dinesh Manocha, Efficient max-norm distance computation and reliable voxelization, Proceedings of the 2003 Eurographics/ACM SIGGRAPH symposium on Geometry processing, June 23-25, 2003, Aachen, Germany
• 31: Weihe, K. and Willhalm, T. 1998. Why cad data repair requires discrete algorithmic techniques. In Proceedings of the 2nd Workshop on Algorithm Engineering. 1--12.
• 32: Wu, J. and Kobbelt, L. 2003. A stream algorithm for the decimation of massive meshes. In Proceedings of Graphics Interface. 185--192.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Geometric algorithms, languages, and systems

General Terms:
Algorithms

Keywords:
Mesh repair, polygon meshes, surface extraction, voxelization