skip to main content
article

Automatic restoration of polygon models

Published: 01 October 2005 Publication History

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 40963 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]
Andujar, C., Brunet, P., and Ayala, D. 2002. Topology-reducing surface simplification using a discrete solid representation. ACM Trans. Graph. 21, 2, 88--105.
[2]
Barequet, G., Duncan, C., and Kumar, S. 1998. Rsvp: A geometric toolkit for controlled repair of solid models. IEEE Trans. Visualiz. Comput. Graph. 4, 2, 162--177.
[3]
Barequet, G. and Kumar, S. 1997. Repairing cad models. In Proceedings of the IEEE Visualization. 363--370.
[4]
Barequet, G. and Sharir, M. 1995. Filling gaps in the boundary of a polyhedron. Comput. Aided Geomet. Des. 12, 2, 207--229.
[5]
Bischoff, S. and Kobbelt, L. 2002. Isosurface reconstruction with topology control. In Proceedings of the Pacific Graphics. 246--255.
[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]
Brunet, P. and Navazo, I. 1990. Solid representation and operation using extended octrees. ACM Trans. Graph. 9, 2, 170--197.
[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]
Frisken, S. F., Perry, R. N., Rockwood, A. P., and Jones, T. R. 2000. Adaptively sampled distance fields: a general representation of shape for computer graphics. In Proceedings of SIGGRAPH. 249--254.
[12]
Garland, M. and Heckbert, P. S. 1997. Surface simplification using quadric error metrics. In Proceedings of SIGGRAPH. 209--216.
[13]
Gibson, S. F. F. 1998. Using distance maps for accurate surface representation in sampled volumes. In Proceedings of IEEE Symposium on Volume Visualization. 23--30.
[14]
Gonzalez, R. and Woods, R. 1992. Digital Image Processing. Addison-Wesley.
[15]
Gottschalk, S., Lin, M. C., and Manocha, D. 1996. Obbtree: A hierarchical structure for rapid interference detection. In Proceedings of SIGGRAPH. 171--180.
[16]
Greß, A. and Klein, R. 2003. Efficient representation and extraction of 2-manifold isosurfaces using kd-trees. In Proceedings of the 11th Pacific Conference on Computer Graphics and Applications (PG'03). 364--376.
[17]
Guéziec, A., Taubin, G., Lazarus, F., and Horn, B. 2001. Cutting and stitching: Converting sets of polygons to manifold surfaces. IEEE Trans. Visualiz. Comput. Graph. 7, 2, 136--151.
[18]
Guskov, I. and Wood, Z. J. 2001. Topological noise removal. In Proceedings of Graphics Interface. 19--26.
[19]
Ju, T. 2004. Robust repair of polygonal models. ACM Trans. Graph. 23, 3, 888--895.
[20]
Ju, T., Losasso, F., Schaefer, S., and Warren, J. 2002. Dual contouring of hermite data. In Proceedings of the SIGGRAPH. 339--346.
[21]
Kobbelt, L., Campagna, S., Vorsatz, J., and Seidel, H.-P. 1998. Interactive multi-resolution modeling on arbitrary meshes. In Proceedings of SIGGRAPH. 105--114.
[22]
Kobbelt, L. P., Botsch, M., Schwanecke, U., and Seidel, H.-P. 2001. Feature sensitive surface extraction from volume data. In Proceedings of SIGGRAPH. 57--66.
[23]
Kong, T. and Rosenfeld, A. 1989. Digital topology: Introduction and survey. Comput. Vision, Graph. Image Process. 48, 357--397.
[24]
Liepa, P. 2003. Filling holes in meshes. In Proceedings of the Symposium on Geometry Processing 03. 200--205.
[25]
Lorensen, W. E. and Cline, H. E. 1987. Marching cubes: A high resolution 3d surface construction algorithm. In Proceedings of SIGGRAPH. 163--169.
[26]
Nooruddin, F. and Turk, G. 2003. Simplification and repair of polygonal models using volumetric techniques. IEEE Trans. Visualiz. Comput. Graph. 9, 2, 191--205.
[27]
Samet, H. and Webber, R. E. 1988. Hierarchical data structures and algorithms for computer graphics. Part i. IEEE Comput. Graph. Appl. 8, 3, 48--68.
[28]
Taubin, G. 1995. A signal processing approach to fair surface design. In Proceedings of SIGGRAPH. 351--358.
[29]
Turk, G. and Levoy, M. 1994. Zippered polygon meshes from range images. In Proceedings of SIGGRAPH 94. 311--318.
[30]
Varadhan, G., Krishnan, S., Kim, Y., Diggavi, S., and Manocha, D. 2003. Efficient max-norm distance computation and reliable voxelization. In Proceedings of the Symposium on Geometry Processing. 116--126.
[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.

Cited By

View all
  • (2025)Learning Self-Prior for Mesh Inpainting Using Self-Supervised Graph Convolutional NetworksIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2024.336436531:2(1448-1464)Online publication date: 1-Feb-2025
  • (2024)Robust Containment Queries over Collections of Rational Parametric Curves via Generalized Winding NumbersACM Transactions on Graphics10.1145/365822843:4(1-14)Online publication date: 19-Jul-2024
  • (2024)Visual-Preserving Mesh RepairIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2023.334882930:9(6586-6597)Online publication date: 1-Jan-2024
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Transactions on Graphics
ACM Transactions on Graphics  Volume 24, Issue 4
October 2005
244 pages
ISSN:0730-0301
EISSN:1557-7368
DOI:10.1145/1095878
Issue’s Table of Contents

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 October 2005
Published in TOG Volume 24, Issue 4

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. Mesh repair
  2. polygon meshes
  3. surface extraction
  4. voxelization

Qualifiers

  • Article

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)27
  • Downloads (Last 6 weeks)3
Reflects downloads up to 13 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2025)Learning Self-Prior for Mesh Inpainting Using Self-Supervised Graph Convolutional NetworksIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2024.336436531:2(1448-1464)Online publication date: 1-Feb-2025
  • (2024)Robust Containment Queries over Collections of Rational Parametric Curves via Generalized Winding NumbersACM Transactions on Graphics10.1145/365822843:4(1-14)Online publication date: 19-Jul-2024
  • (2024)Visual-Preserving Mesh RepairIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2023.334882930:9(6586-6597)Online publication date: 1-Jan-2024
  • (2024)Robust digital-twin airspace discretization and trajectory optimization for autonomous unmanned aerial vehiclesScientific Reports10.1038/s41598-024-62421-414:1Online publication date: 31-May-2024
  • (2024)Feature-preserving shrink wrapping with adaptive alphaComputer Aided Geometric Design10.1016/j.cagd.2024.102321111(102321)Online publication date: Jun-2024
  • (2023)Design of 3D-Printable Compliant Robotic Grippers Using Solid Geometry Library in MATLAB2023 IEEE International Conference on Robotics and Biomimetics (ROBIO)10.1109/ROBIO58561.2023.10354887(1-6)Online publication date: 4-Dec-2023
  • (2022)Research on Automatic Error Correction Method in English Writing Based on Deep Neural NetworkComputational Intelligence and Neuroscience10.1155/2022/27092552022Online publication date: 1-Jan-2022
  • (2022)Restricted Delaunay Triangulation for Explicit Surface ReconstructionACM Transactions on Graphics10.1145/353376841:5(1-20)Online publication date: 29-Oct-2022
  • (2022)Alpha wrapping with an offsetACM Transactions on Graphics10.1145/3528223.353015241:4(1-22)Online publication date: 22-Jul-2022
  • (2022)A CAE-oriented mesh hole-filling algorithm focusing on geometry and qualityEngineering Computations10.1108/EC-07-2021-041139:7(2483-2504)Online publication date: 8-Apr-2022
  • Show More Cited By

View Options

Login options

Full Access

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media