Abstract
When designing novel algorithms for geometric processing and analysis, researchers often assume that the input conforms to several requirements. On the other hand, polygon meshes obtained from acquisition of real-world objects typically exhibit several defects, and thus are not appropriate for a widespread exploitation.
In this paper, an algorithm is presented that strives to convert a low-quality digitized polygon mesh to a single manifold and watertight triangle mesh without degenerate or intersecting elements. Differently from most existing approaches that globally resample the model to produce a fixed version, the algorithm presented here attempts to modify the input mesh only locally within the neighborhood of undesired configurations.
After having converted the input to a single combinatorial manifold, the algorithm proceeds iteratively by removing growing neighborhoods of undesired elements and by patching the resulting surface gaps until all the “defects" are removed. Though this heuristic approach is not guaranteed to converge, it was tested on more than 400 low-quality models and always succeeded. Furthermore, with respect to similar existing algorithms, it proved to be computationally efficient and produced more accurate results while using fewer triangles.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
AIM@SHAPE shape repository (2004). http://shapes.aimatshape.net/
Albertoni, R., Papaleo, L., Robbiano, F., Spagnuolo, M.: Towards a conceptualization for shape acquisition and processing. In: Proc. of 1st International Workshop on Shapes and Semantics (2006)
Attene, M., Falcidieno, B.: Remesh: An interactive environment to edit and repair triangle meshes. In: Shape Modeling and Applications, pp. 271–276 (2006)
Attene, M., Mortara, M., Spagnuolo, M., Falcidieno, B.: Hierarchical convex approximation for fast region selection. Comput. Graph. Forum 27(5), 1323–1333 (2008)
Barequet, G., Sharir, M.: Filling gaps in the boundary of a polyhedron. Comput. Aided Geom. Des. 12(2), 207–229 (1995)
Biasotti, S., Attene, M.: Shrec08 entry: Report of the stability track on watertight models. In: Shape Modeling and Applications (2008)
Bischoff, S., Kobbelt, L.: Structure preserving cad model repair. Comput. Graph. Forum 24(3), 527–536 (2005)
Bischoff, S., Pavic, D., Kobbelt, L.: Automatic restoration of polygon models. ACM Trans. Graph. 24(4), 1332–1352 (2005)
Borodin, P., Novotni, M., Klein, R.: Progressive gap closing for mesh repairing. In: Advances in Modelling, Animation and Rendering, pp. 201–213 (2002)
Botsch, M., Kobbelt, L.: A robust procedure to eliminate degenerate faces from triangle meshes. In: Vision, Modeling and Visualization, pp. 283–290 (2001)
Botsch, M., Pauly, M., Kobbelt, L., Alliez, P., Levy, B., Bischoff, S., Roessl, C.: Geometric modeling based on polygonal meshes. In: SIGGRAPH Course Notes (2007)
Branch, J., Prieto, F., Boulanger, P.: Automatic hole-filling of triangular meshes using local radial basis function. In: Proceedings of 3DPVT’06, pp. 727–734 (2006)
Cignoni, P., Rocchini, C., Scopigno, R.: Metro: measuring error on simplified surfaces. Comput. Graph. Forum 17(2), 167–174 (1998)
Davis, J., Marschner, S., Garr, M., Levoy, M.: Filling holes in complex surfaces using volumetric diffusion. In: Int. Symposium on 3D Data Processing, Visualization, Transmission, pp. 428–438 (2002)
Dey, T.K., Edelsbrunner, H., Guha, S., Nekhayev, D.: Topology preserving edge contraction. Publ. Inst. Math. (Beograd) 20(80), 23–45 (1999)
Floriani, L.D., Morando, F., Puppo, E.: Representation of non-manifold objects through decomposition into nearly manifold parts. In: ACM Solid Modeling, pp. 304–309 (2003)
Geomagic, Inc. Geomagic Studio. http://www.geomagic.com/
Gottschalk, S., Lin, M.C., Manocha, D.: Obbtree: A hierarchical structure for rapid interference detection. In: ACM Siggraph Proceedings, pp. 171–180 (1996)
Guéziec, A., Taubin, G., Lazarus, F., Horn, B.: Cutting and stitching: Converting sets of polygons to manifold surfaces. IEEE Trans. Vis. Comput. Graph. 7(2), 136–151 (2001)
Guibas, L., Salesin, D., Stolfi, J.: Epsilon geometry: building robust algorithms from imprecise computations. In: ACM Symposium on Computational Geometry, pp. 208–217 (1989)
Guskov, I., Wood, Z.: Topological noise removal. In: Proceedings of Graphics Interface, pp. 19–26 (2001)
InnovMetric Software, Inc. Polyworks. http://www.innovmetric.com/
INUS Technology, Inc. Rapidform. http://www.rapidform.com/
Ju, T.: Robust repair of polygonal models. ACM Trans. Graph. 23(3), 888–895 (2004)
Liepa, P.: Filling holes in meshes. In: Eurographics Symposium on Geometry Processing, pp. 200–205 (2003)
Murali, T., Funkhouser, T.: Consistent solid and boundary representations from arbitrary polygonal data. In: Proceedings of Symposium on Interactive 3D Graphics, pp. 155–162 (1997)
Nooruddin, F., Turk, G.: Simplification and repair of polygonal models using volumetric techniques. ACM Trans. Vis. Comput. Graph. 9(2), 191–205 (2003)
Podolak, J., Rusinkiewicz, S.: Atomic volumes for mesh completion. In: Eurographics Symposium on Geometry Processing, pp. 33–42 (2005)
Rocchini, C., Cignoni, P., Ganovelli, F., Montani, C., Pingi, P., Scopigno, R.: The marching intersections algorithm for merging range images. Vis. Comput. 20(2–3), 149–164 (2004)
Rossignac, J., Cardoze, D.: Matchmaker: manifold breps for non-manifold r-sets. In: Proc. of 5th ACM Symposium on Solid Modeling and Applications, pp. 31–41 (1999)
Rourke, C.P., Sanderson, B.J.: Introduction to Piecewise Linear Topology. Springer, Berlin (1972)
Samet, H.: Spatial Data Structures: Quadtrees, Octrees and Other Hierarchical Methods. Addison Wesley, Reading (1989)
Shewchuk, J.R.: Delaunay refinement algorithms for triangular mesh generation. Comput. Geom. Theory Appl. 22(1–3), 21–74 (2002)
Si, H., Gaertner, K.: Meshing piecewise linear complexes by constrained Delaunay tetrahedralizations. In: Proceedings of the 14th International Meshing Roundtable, pp. 147–163 (2005)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Attene, M. A lightweight approach to repairing digitized polygon meshes. Vis Comput 26, 1393–1406 (2010). https://doi.org/10.1007/s00371-010-0416-3
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00371-010-0416-3