A comparison of hole-filling methods in 3D

• Autorzy: Pérez E. , Salamanca S. , Merchán P. , Adán A.

Identyfikatory

DOI

10.1515/amcs-2016-0063

• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

3D polygonal model; repairing meshes; hole filling; restoration algorithm

PL

model wielokątny 3D; renowacja siatki; algorytm renowacji

• Wydawca: Oficyna Wydawnicza Uniwersytetu Zielonogórskiego
• Czasopismo: International Journal of Applied Mathematics and Computer Science
• Rocznik: 2016
• Tom: Vol. 26, no. 4
• Strony: 885--903
• Opis fizyczny: Bibliogr. 64 poz., rys., tab., wykr.

Twórcy

autor

Pérez E.

• Industrial Engineering School, University of Extremadura, Avda. Elvas, 06006 Badajoz, Spain

autor

Salamanca S.

• Industrial Engineering School, University of Extremadura, Avda. Elvas, 06006 Badajoz, Spain

autor

Merchán P.

• Industrial Engineering School, University of Extremadura, Avda. Elvas, 06006 Badajoz, Spain

autor

Adán A.

• Computer Science School, University of Castilla–La Mancha, Paseo de la Universidad 4, 13071 Ciudad Real, Spain

Bibliografia

• [1] 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.
• [2] Attene, M., Campen, M. and Kobbelt, L. (2013). Polygon mesh repairing: An application perspective, ACM Computing Surveys 45(2): 15:1–15:33.
• [3] 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.
• [4] Barequet, G. and Sharir, M. (1995). Filling gaps in the boundary of a polyhedron, Computer-Aided Geometric Design 12(2): 207–229.
• [5] 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.
• [6] Bischoff, S., Pavic, D. and Kobbelt, L. (2005). Automatic restoration of polygon models, ACM Transactions on Graphics 24(4): 1332–1352.
• [7] Bloomenthal, J. (1994). Graphics gEMS IV, Academic Press Professional, Inc., San Diego, CA, pp. 324–349.
• [8] 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.
• [9] 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.
• [10] 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.
• [11] 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.
• [12] 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.
• [13] 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.
• [14] 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.
• [15] 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.
• [16] 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.
• [17] 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.
• [18] 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.
• [19] 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.
• [20] 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.
• [21] Edelsbrunner, H. and Mücke, E. (1994). Three-dimensional alpha shapes, ACM Transactions on Graphics 13(1): 43–72.
• [22] 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.
• [23] Fang, T.-P. and Piegl, L. (1995). Delaunay triangulation in three dimensions, IEEE Computer Graphics and Applications 15(5): 62–69.
• [24] 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.
• [25]Harary, G., Tal, A. and Grinspun, E. (2014). Context-based coherent surface completion, ACM Transactions on Graphics 33(1): 5:1–5:12.
• [26] Hu, P., Wang, C., Li, B. and Liu, M. (2012). Filling holes in triangular meshes in engineering, Journal of Software 7(1): 141–148.
• [27] 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.
• [28] Ju, T. (2004). Robust repair of polygonal models, Technical report, Rice niversity, Houston, TX.
• [29] Ju, T. (2009). Fixing geometric errors on polygonal models: A survey, Journal of Computer Science Technology 24(1): 19–29.
• [30] Ju, T., Losasso, F., Schaefer, S. and Warren (2002). Dual contouring of hermite data, SIGGRAPH02, San Antonio, TX, USA, pp. 339–346.
• [31] 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.
• [32] Klincsek, G. (1980). Minimal triangulations of polygonal domains, Annals of Discrete Mathematics 9: 121–123.
• [33] 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.
• [34] 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.
• [35] 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.
• [36] Lancaster, P. and Salkauskas, K. (1981). Surfaces generated by moving least squares methods, Mathematics of Computation 37(155): 141–158.
• [37] Li, G., Ye, X. and Zhang, S. (2008). An algorithm for filling complex holes in reverse engineering, Engineering with Computers 24(2): 119–125.
• [38] 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.
• [39] 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.
• [40] Lui, L. and Gu, X. (2013). A conformal approach for surface inpainting, Inverse Problems and Imaging 7(3): 863–884.
• [41] 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.
• [42] 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.
• [43] 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.
• [44] 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.
• [45] 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.
• [46] 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.
• [47] 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.
• [48] 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.
• [49] 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.
• [50] 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.
• [51] Sharf, A., Alexa, M. and Cohen-Or, D. (2004). Context-based surface completion, ACM Transactions on Graphics 23(3): 878–887.
• [52] 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.
• [53] 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.
• [54] Vichitvejpaisal, P. and Kanongchaiyos, P. (2014). Surface completion using Laplacian transform, Engineering Journal 18(1): 129–144.
• [55] Wang, J. and Oliveira, M. (2007). Filling holes on locally smooth surfaces reconstructed from point clouds, Image and Vision Computing 25(1): 103–113.
• [56] 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.
• [57] 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.
• [58] 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.
• [59] 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.
• [60] 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.
• [61] 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.
• [62] 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.
• [63] 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.
• [64] Zhao, W., Gao, S. and Lin, H. (2007). A robust hole-filling algorithm for triangular mesh, The Visual Computer 23(12): 987–997.

Uwagi

Opracowanie ze środków MNiSW w ramach umowy 812/P-DUN/2016 na działalność upowszechniającą naukę.