Open Access Open Access  Restricted Access Subscription or Fee Access

A Hole-Filling Model with Triangular Meshing based on Reverse Engineering

Yousef Sabbah, Kifaya Sabbah


This paper presents a hole-filling model that implements triangular meshing based on reverse engineering using grey system prediction. The main objective is to improve the performance of this process in terms of execution time and average error. We made some modifications on this system based on parallel processing. In order to do so, we classified the hole-filling methods into geometric and volumetric methods. We also compared all methods of both classes in terms of pros and cons in order to select the best methods that fit the data models. Finally, we implemented our proposed model, and provided our results compared with previous results. Our proposed model proved better performance with lees execution time and average error.


Boundary, Detection, Edge, Geometric, Gap, Grey System, Hole-Filling, Meshing, Vertices, Volumetric.

Full Text:



T. Ju, 2009. “Fixing geometric errors on polygonal models: a survey”, JCST, 24 - 1, January 2009, 19-29.

J. H. Bohn, “Removing zero-volume parts from cad models for layered manufacturing,” IEEE Comput. Graph. Appl., 15, 6, 27–34. 1995.

A. Gueziec, G. Taubin, F. Lazarus, and B. Horn, “Cutting and stitching: Converting sets of polygons to manifold surfaces,” IEEE Transactions on Visualization and Computer Graphics, 7, 2, 136–151.2001

G. Turk, and M. Levoy." Zippered polygon meshes from range images," In SIGGRAPH ’94: Proc. of the 21st annual conference on CGIT, 1994, 311–318, New York, NY, USA.

L. C. Wang, and Y. C. Hung, “Hole filling of triangular mesh segments using systematic grey prediction,” Computer-Aided Design, vol. 44, pp. 1182-1189, Jul. 2012.

M. Varnuska, J. Parus, and I. Kolingerova, "Simple holes triangulation in surface reconstruction," In Proceedings of Algoritmy, 2005, 280–289.

M. Wagner, U. Labsik, and G. Greiner. “Repairing non-manifold triangle meshes using simulated annealing,” In Proc. of 4th Israel-Korea Bi-National Conference on Geometric Modeling and Computer Graph.2003, 21, 2, 137–153.

P. Liepa, "Filling holes in meshes," In Euro-graphics Symposium on Geometry Processing, 2003, 200–205.

P. S. Patel, L.D. Marcum, and G. M. Remotigue, “Stitching and filling: Creating conformal faceted geometry,” In Proc. 14th International Meshing Roundtable, 2005, 239–256.

J. P. Pernot, G. Moraru, and P. Veron, 2006, “Filling holes in meshes using a mechanical model to simulate the curvature variation minimization”. Computer Graphics, 30, 6, 892–902.

L. S. Tekumalla, and E. Cohen, 2004, “Hole-filling algorithm for triangular meshes”. Technical Report UUCS-04-019, School of Computing, University of Utah.

J. Wang, and M. Oliveira, “Filling holes on locally smooth surfaces reconstructed from point clouds, Image Vision Comput. 25, 1, 103–113.2007.

W. Zhao, S. Gao and H. Lin, “A robust hole-filling algorithm for triangular mesh”. The Visual Computer, 23, 12, 987–997.2007.

I. Makela, and A. Dolenc, “Some efficient procedures for correcting triangulated models,” In Proc. Solid Free form Fabrication Symposium, 126–134, Austin, Texas, USA.

B. Levy, “Dual domain extrapolation,” In ACM Transactions on Graphics (SIGGRAPH’03), 364–369.2003.

X. J. Wu, M. Y. Wang, and B. Hanm, “An Automatic Hole-Filling Algorithm for Polygon Meshes,” CADA, 5, 6, 889-899.2008.

S. Park, X. Guo, H. Shin, and H. Qin, “Shape and Appearance Repair for Incomplete Point Surfaces,” Proceedings of the Tenth IEEE International Conference on Computer Vision, 2005, 2, 1260-1267.

S. Park, X. Guo, H. Shin, and H. Qin, “Surface completion for shape and appearance,” Visual Comput. 22, 168–180.2006.

A. Brunton, S. Wuhrer, C. Shu, P. Bose, and E. Demaine, “Filling holes in triangular meshes by curve unfolding,” Shape Modeling and Applications, SMI. IEEE International Conference, 2009, 66-72.

J. Branch, F. Prieto, and P. Boulanger, “A Hole-filling algorithm for triangular meshes using local Radial Basis Function,” In Proceedings of the 15th International Meshing Roundtable,2006, 411-431. DOI 10.1007/978-3-540-34958-7_24.

J. C. Carr , R. K. Beatson, J. B. Cherrie, T. J. Mitchell, R. W. Fright, B. C. Mccallum, and T. R. Evans, “Reconstruction and representation of 3D objects with radial basis functions,” In ACM Transactions on Graphics (SIGGRAPH’01) 2001, 67-76.

C. Y.Chen , K. Y. Cheng, and H. Y. Liao, “Fairing of polygon meshes via Bayesian discriminant analysis,” In Proc. of the 12th ICCE on CGVCV,2004, 12, 175-182.

G. Barequet, and M. Sharir, “Filling gaps in the boundary of a polyhedron. Computer Aided Geometric Design,” 12, 2, 207–229. 1995.

Y. Jun, “A piecewise hole-filling algorithm in reverse engineering,” Comput. Aided Des. 22, 8, 263–270.2005.

G. Li, X. Z. Ye, and S. Y. Zhang, “An algorithm for filling complex holes in reverse engineering,” Engineering with Computers, 24, 2, 119–125.2008.

X. Liu, C. Li, X. Wang, “Hole-filling Algorithm for High-curvature Region in Triangular Mesh Models,” TELKOMNIKA (November 2012), 10, 7, 1598-1603.2012.

J. Hou, R. Wang, H. Zhang, X. Wen, M. Lei, and Y. Zhao, “Research on Hole Filling Method in Curved Surface of N-sided Region,” JCIS, 8, 6073– 6078.2012.

A. Brunton, S. Wuhrer, C. Shu, P. Bose, and E. Demaine, “Filling Holes in Triangular Meshes Using Digital Images by Curve Unfolding,” IJSM. 16, 1-2, 151-171.2010.

M. X. Nguyen, X. Yan, and B. Chen, “Geometry Completion and Detail Generation by Texture Synthesis,” In Proceeding of Pacific Graphics, 2005, 23-32.

A. Sharf, M. Alexa, and D. Cohen, “Context-based surface completion,” ACM Trans. Graph. 23, 878–887. 2004.

V. Kraevoy, and A. Sheffer, “Template based mesh completion,” Proceedings of the third EG SGP, 2005, ’05, 13-22.

K. Sabbah, H. Ebied, H. Shedeed, and A. Salem, "Hole-filling Techniques for 3D-Objects: A Comparative Study," in Proc. ICICS13, 2013, Paper 70, p. 118.

T. J. Chung, “Computational Fluid Dynamics,” Cambridge University Press. ISB 0521594162, 9780521594165, 1012 pages.2002.

J. Davis, S. R .Marschner, M. Garr, and M. Levoy, “Filling holes in complex surfaces using volumetric diffusion,” In First International Symposium on 3D Data Processing, Visualization and Transmission, 2002, 438–433.

J. E. Flaherty, and A. Eaton, 2000, Finite Element Analysis- Lecture Notes, Rensselaer Polytechnic Institute, Troy.

A. Gress, and R. Klein, “Efficient representation and extraction of 2-manifold iso-surfaces using kd-trees,” Graph. Models, 66, 6, 370–397.2004.

A. Kumar, A. Shih, Y. Ito, D. Ross, and B. Soni, “A Hole-filling Algorithm Using Non-uniform Rational B-splines,” In Proceedings of the 16th IMR, 2008,169-182.

T. Ju, 2004. “Robust repair of polygonal models”. In Processing of SIGGRAPH, Los Angeles, CA, USA, 8–12 August, 2004, 888–895.

J. Podolak, and S. Rusinkiewicz, “Atomic volume for mesh completion,” In Euro-graphics Symposium on Geometry Processing, Aire-la-Ville, Switzerland, July 2005, 33.

B. Curless, and M. Levoy, “A volumetric method for building complex model from range image,” In Proc. of SIGGRAPH, New Orleans, USA, (August, 4–9, 1996). ACM, New York, 303–312.

Q. G. Tian, B. Z. Ge and D. Y. Yu. “Hole-filling algorithm in mesh surface based on grey model GM (1, 1). Journal of Engineering Graphics 2007, 3, 78–83.


  • There are currently no refbacks.

Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.