A comparison of hole-filling methods in 3D

Emiliano Pérez ; Santiago Salamanca ; Pilar Merchán ; Antonio Adán

International Journal of Applied Mathematics and Computer Science, Tome 26 (2016), p. 885-903 / Harvested from The Polish Digital Mathematics Library

Résumé

This paper presents a review of the most relevant current techniques that deal with hole-filling in 3D models. Contrary to earlier reports, which approach mesh repairing in a sparse and global manner, the objective of this review is twofold. First, a specific and comprehensive review of hole-filling techniques (as a relevant part in the field of mesh repairing) is carried out. We present a brief summary of each technique with attention paid to its algorithmic essence, main contributions and limitations. Second, a solid comparison between 34 methods is established. To do this, we define 19 possible meaningful features and properties that can be found in a generic hole-filling process. Then, we use these features to assess the virtues and deficiencies of the method and to build comparative tables. The purpose of this review is to make a comparative hole-filling state-of-the-art available to researchers, showing pros and cons in a common framework.

Détail

Publié le : 2016-01-01
EUDML-ID : urn:eudml:doc:287170

Bibliographie

[000] Amenta, N., Bern, M. and Kamvysselis, M. (1998). A new Voronoi-based surface reconstruction algorithm, Proceedings of the 25th Annual Conference on Computer Graphics and Interactive Techniques (SIGGRAPH'98), Orlando, FL, USA, pp. 415-421.

[001] Attene, M., Campen, M. and Kobbelt, L. (2013). Polygon mesh repairing: An application perspective, ACM Computing Surveys 45(2): 15:1-15:33. | Zbl 1293.68279

[002] Bajaj, C., Bernardini, F. and Xu, G. (1995). Automatic reconstruction of surfaces and scalar fields from 3D scans, Proceedings of the 22nd Annual Conference on Computer Graphics and Interactive Techniques (SIGGRAPH'95), Los Angeles, CA, USA, pp. 109-118.

[003] Barequet, G. and Sharir, M. (1995). Filling gaps in the boundary of a polyhedron, Computer-Aided Geometric Design 12(2): 207-229. | Zbl 0875.68921

[004] Bernardini, F., Mittleman, J., Rushmeier, H., Silva, C. and Taubin, G. (1999). The ball-pivoting algorithm for surface reconstruction, IEEE Transactions on Visualization and Computer Graphics 5(4): 349-359.

[005] Bischoff, S., Pavic, D. and Kobbelt, L. (2005). Automatic restoration of polygon models, ACM Transactions on Graphics 24(4): 1332-1352.

[006] Bloomenthal, J. (1994). Graphics gEMS IV, Academic Press Professional, Inc., San Diego, CA, pp. 324-349.

[007] Botsch, M. and Kobbelt, L. (2004). A remeshing approach to multiresolution modeling, Proceedings of the 2004 Eurographics/ACM SIGGRAPH Symposium on Geometry Processing, SGP'04, Orlando, FL, USA, pp. 185-192.

[008] Branch, J., Prieto, F. and Boulanger, P. (2006). A hole-filling algorithm for triangular meshes using local radial basis function, Proceedings of the 15th International Meshing Roundtable, Birmingham, AL, USA, pp. 411-431.

[009] Breckon, T. and Fisher, R. (2005). Non-parametric 3D surface completion, Proceedings of the 5th International Conference on 3-D Digital Imaging and Modeling (3DIM'05), Ottawa, Ontario, Canada, pp. 573-580. | Zbl 1141.68627

[010] Brunton, A., Wuhrer, S. and Shu, C. (2007). Image-based model completion, Proceedings of the 6th International Conference on 3-D Digital Imaging and Modeling (3DIM'07), Montreal, Quebec, Canada, pp. 305-311.

[011] Brunton, A., Wuhrer, S., Shu, C., Bose, P. and Demaine, E. (2009). Filling holes in triangular meshes by curve unfolding, Proceedings of the 2009 IEEE International Conference on Shape Modeling and Applications (SMI'09), Beijing, China, pp. 66-72.

[012] Carr, J., Beatson, R., Cherrie, J., Mitchell, T., Fright, W., McCallum, B. and Evans, T. (2001). Reconstruction and representation of 3D objects with radial basis functions, Proceedings of the 18th Annual Conference on Computer Graphics and Interactive Techniques (SIGGRAPH'01), Los Angeles, CA, USA, pp. 67-76.

[013] Caselles, V., Haro, G., Sapiro, G. and Verdera, J. (2008). On geometric variational models for inpainting surface holes, Computer Vision and Image Understanding 111(3): 351-373.

[014] Castellani, U., Livatino, S. and Fisher, R. (2002). Improving environment modelling by edge occlusion surface completion, 1st International Symposium on 3D Data Processing Visualization and Transmission (3DPVT 2002), Padova, Italy, pp. 672-675.

[015] Curless, B. and Levoy, M. (1996). A volumetric method for building complex models from range images, Proceedings of the 23rd Annual Conference on Computer Graphics and Interactive Techniques (SIGGRAPH'96), New Orleans, LA, USA, pp. 303-312.

[016] Davis, J., Marschner, S., Garr, M. and Levoy, M. (2001). Filling holes in complex surfaces using volumetric diffusion, Proceedings of the 1st International Symposium on 3D Data Processing, Visualization and Transmission, Padova, Italy, pp. 428-438.

[017] Dell'acqua, F. and Fisher, R. (2002). Reconstruction of planar surfaces behind occlusions in range images, IEEE Transactions on Pattern Analysis and Machine Intelligence 24(4): 569-575.

[018] Dey, T., Giesen, J. and Hudson, J. (2001). Delaunay based shape reconstruction from large data, Proceedings of the IEEE 2001 Symposium on Parallel and Large-Data Visualization and Graphics (PVG'01), San Diego, CA, USA, pp. 19-27.

[019] Dinh, H. and Turk, G. (2001). Reconstructing surfaces using anisotropic basis functions, Proceedings of the 2001 International Conference on Computer Vision (ICCV'01), Vancouver, British Columbia, Canada, pp. 606-613.

[020] Edelsbrunner, H. and Mücke, E. (1994). Three-dimensional alpha shapes, ACM Transactions on Graphics 13(1): 43-72. | Zbl 0806.68107

[021] Efros, A., Efros, A. and Leung, T. (1999). Texture synthesis by non-parametric sampling, Proceedings of the 2001 International Conference on Computer Vision (ICCV'01), Vancouver, British Columbia, Canada, pp. 1033-1038.

[022] Fang, T.-P. and Piegl, L. (1995). Delaunay triangulation in three dimensions, IEEE Computer Graphics and Applications 15(5): 62-69.

[023] Guo, T.-Q., Li, J.-J., Weng, J.-G. and Zhuang, Y.-T. (2006). Filling holes in complex surfaces using oriented voxel diffusion, Proceedings of the 5th International Conference on Machine Learning and Cybernetics, Dalian, China, pp. 4370-4375.

[024] Harary, G., Tal, A. and Grinspun, E. (2014). Context-based coherent surface completion, ACM Transactions on Graphics 33(1): 5:1-5:12. | Zbl 1288.68227

[025] Hu, P., Wang, C., Li, B. and Liu, M. (2012). Filling holes in triangular meshes in engineering, Journal of Software 7(1): 141-148.

[026] Jakobsen, B., Bærentzen, J. and Christensen, N. (2007). Variational volumetric surface reconstruction from unorganized points, Proceedings of the 6th Eurographics/IEEE VGTC Conference on Volume Graphics, VG'07, Prague, Czech Republic, pp. 65-72.

[027] Ju, T. (2004). Robust repair of polygonal models, Technical report, Rice University, Houston, TX.

[028] Ju, T. (2009). Fixing geometric errors on polygonal models: A survey, Journal of Computer Science Technology 24(1): 19-29.

[029] Ju, T., Losasso, F., Schaefer, S. and Warren (2002). Dual contouring of hermite data, SIGGRAPH02, San Antonio, TX, USA, pp. 339-346.

[030] Kazhdan, M., Bolitho, M. and Hoppe, H. (2006). Poisson surface reconstruction, Proceedings of the 4th Eurographics Symposium on Geometry Processing, SGP'06, Cagliari, Sardinia, Italy, pp. 61-70.

[031] Klincsek, G. (1980). Minimal triangulations of polygonal domains, Annals of Discrete Mathematics 9: 121-123. | Zbl 0452.05002

[032] Kobbelt, L., Campagna, S., Vorsatz, J. and Seidel, H.-P. (1998). Interactive multi-resolution modeling on arbitrary meshes, Proceedings of the 25th Annual Conference on Computer Graphics and Interactive Techniques (SIGGRAPH'98), Orlando, FL, USA, pp. 105-114. | Zbl 0959.65043

[033] Kumar, A. and Shih, A. (2012). Hybrid approach for repair of geometry with complex topology, in W. Quadros (Ed.), Proceedings of the 20th International Meshing Roundtable, Springer, Berlin/Heidelberg, pp. 387-403.

[034] Kumar, A., Shih, A., Ito, Y., Ross, D. and Soni, B. (2007). A hole-filling algorithm using non-uniform rational b-splines, Proceedings of the 16th International Meshing Roundtable, Seattle, WA, USA, pp. 169-182. | Zbl 1135.65312

[035] Lancaster, P. and Salkauskas, K. (1981). Surfaces generated by moving least squares methods, Mathematics of Computation 37(155): 141-158. | Zbl 0469.41005

[036] Li, G., Ye, X. and Zhang, S. (2008). An algorithm for filling complex holes in reverse engineering, Engineering with Computers 24(2): 119-125.

[037] Li, Z., Meek, D. and Walton, D. (2010). Polynomial blending in a mesh hole-filling application, Journal of Computer-Aided Design 42(4): pp. 340-349.

[038] Liepa, P. (2003). Filling holes in meshes, SGP'03: Proceedings of the 2003 Eurographics/ACM SIGGRAPH Symposium on Geometry Processing, San Diego, CA, USA, pp. 200-205.

[039] Lui, L. and Gu, X. (2013). A conformal approach for surface inpainting, Inverse Problems and Imaging 7(3): 863-884. | Zbl 1276.65014

[040] Murali, T. and Funkhouser, T.A. (1997). Consistent solid and boundary representations from arbitrary polygonal data, Proceedings of the 1997 Symposium on Interactive 3D Graphics, I3D'97, Providence, RI, USA, pp. 155-162.

[041] Ngo, H.-M. and Lee, W.-S. (2013). Feature-first hole filling strategy for 3D meshes, in G. Csurka et al. (Eds.), Computer Vision, Imaging and Computer Graphics. Theory and Applications, Communications in Computer and Information Science, Vol. 274, Springer, Berlin/Heidelberg, pp. 53-68.

[042] Nooruddin, F. and Turk, G. (2003). Simplification and repair of polygonal models using volumetric techniques, IEEE Transactions on Visualization and Computer Graphics 9(2): 191-205.

[043] Paulsen, R.R., Baerentzen, J.A. and Larsen, R. (2010). Markov random field surface reconstruction, IEEE Transactions on Visualization and Computer Graphics 16(4): 636-646.

[044] Pérez, E., Salamanca, S., Cerrada, C., Merchán, P. and Adán, A. (2012). Filling holes in manifold digitized 3D meshes using image restoration algorithms, Proceedings of the IEEE Intelligent Vehicles Symposium Workshops, Madrid, Spain.

[045] Pérez, E., Salamanca, S., Merchán, P., Adán, A., Cerrada, C. and Cambero, I. (2008). A robust method for filling holes in 3D meshes based on image restoration, in S. Bourennane et al. (Eds.), Proceedings of the 10th International Conference on Advanced Concepts for Intelligent Vision Systems, ACIVS'08, Springer-Verlag, Berlin/Heidelberg, pp. 742-751.

[046] Pernot, J.-P., Moraru, G. and Vron, P. (2006). Filling holes in meshes using a mechanical model to simulate the curvature variation minimization, Computers & Graphics 30(6): 892-902.

[047] Podolak, J. and Rusinkiewicz, S. (2005). Atomic volumes for mesh completion, Proceedings of the 3rd Eurographics Symposium on Geometry Processing (SGP'05), Vienna, Austria, p. 33.

[048] Roth, S. and Black, M.J. (2005). Fields of experts: A framework for learning image priors, IEEE Conference on Computer Vision and Pattern Recognition, San Diego, CA, USA, pp. 860-867.

[049] Sagawa, R. and Ikeuchi, K. (2008). Hole filling of a 3D model by flipping signs of a signed distance field in adaptive resolution, IEEE Transactions on Pattern Analysis and Machine Intelligence 30(4): 686-699.

[050] Sharf, A., Alexa, M. and Cohen-Or, D. (2004). Context-based surface completion, ACM Transactions on Graphics 23(3): 878-887.

[051] Sorkine, O. and Cohen-Or, D. (2004). Least-squares meshes, Proceedings of the 2004 International Conference on Shape Modeling Applications (SMI'04), Genova, Italy, pp. 191-199.

[052] Stulp, F. and Fisher, R. (2001). Reconstruction of surfaces behind occlusions in range images, Proceedings of the 3rd International Conference on 3-D Digital Imaging and Modeling (3DIM'01), Quebec City, Canada, pp. 232-239.

[053] Vichitvejpaisal, P. and Kanongchaiyos, P. (2014). Surface completion using Laplacian transform, Engineering Journal 18(1): 129-144.

[054] Wang, J. and Oliveira, M. (2007). Filling holes on locally smooth surfaces reconstructed from point clouds, Image and Vision Computing 25(1): 103-113.

[055] Wang, L.-C. and Hung, Y.-C. (2012). Hole filling of triangular mesh segments using systematic grey prediction, Computer-Aided Design 44(12): 1182-1189.

[056] Wang, X., Cao, J., Liu, X. and Li, B. (2011). Advancing front method in triangular meshes hole-filling application, Journal of Computer-Aided Design and Computer Graphics 23(6): 1048-1054.

[057] Wang, X., Liu, X., Lu, L., Li, B., Cao, J., Yin, B. and Shi, X. (2012). Automatic hole-filling of CAD models with feature-preserving, Computers & Graphics 36(2): 101-110.

[058] Wei, L.-Y., Lefebvre, S., Kwatra, V. and Turk, G. (2009). State of the art in example-based texture synthesis, Eurographics 2009, Munich, Germany, pp. 1-25.

[059] Wei, M., Wu, J. and Pang, M. (2010). An integrated approach to filling holes in meshes, Proceedings of the 2010 International Conference on Artificial Intelligence and Computational Intelligence, Las Vegas, NV, USA, pp. 306-310.

[060] Wilkowski, A., Kornuta, T., Stefańczyk, M. and Kasprzak, W. (2016). Efficient generation of 3D surfel maps using RGB-D sensors, International Journal of Applied Mathematics and Computer Science 26(1): 99-122, DOI: 10.1515/amcs-2016-0007. | Zbl 1336.94012

[061] Wu, X., Wang, M. and Han, B. (2008). An automatic hole-filling algorithm for polygon meshes, Journal of Computer-Aided Design and Applications 5(6): 889-899.

[062] Zhao, M., Ma, L., Mao, Z. and Li, Z. (2006). Feature sensitive hole filling with crest lines, in L. Jiao et al. (Eds.), Advances in Natural Computation, Lecture Notes in Computer Science, Vol. 4222, Springer, Berlin/Heidelberg, pp. 660-663.

[063] Zhao, W., Gao, S. and Lin, H. (2007). A robust hole-filling algorithm for triangular mesh, The Visual Computer 23(12): 987-997.