World Scientific
  • Search
Skip main navigation

Cookies Notification

We use cookies on this site to enhance your user experience. By continuing to browse the site, you consent to the use of our cookies. Learn More
Our website is made possible by displaying certain online content using javascript.
In order to view the full content, please disable your ad blocker or whitelist our website

System Upgrade on Tue, Oct 25th, 2022 at 2am (EDT)

Existing users will be able to log into the site and access content. However, E-commerce and registration of new users may not be available for up to 12 hours.
For online purchase, please visit us again. Contact us at [email protected] for any enquiries.


    We propose a novel approach to automatically fill holes in triangulated models. Each hole is filled using a minimum energy surface that is obtained in three steps. First, we unfold the hole boundary onto a plane using energy minimization. Second, we triangulate the unfolded hole using a constrained Delaunay triangulation. Third, we embed the triangular mesh as a minimum energy surface in ℝ3. When embedding the triangular mesh, any energy function can be used to estimate the missing data. We use a variational multi-view approach to estimate the missing data. The running time of the method depends primarily on the size of the hole boundary and not on the size of the model, thereby making the method applicable to large models. Our experiments demonstrate the applicability of the algorithm to the problem of filling holes bounded by highly curved boundaries in large models.

    Partial results of this work appeared in the 3-D Digital Imaging and Modeling Conference 2007 [A. Brunton, S. Wuhrer, C. Shu, Image-Based Model Completion, 3DIM 2007] and in the IEEE International Conference on Shape Modeling and Applications 2009 [A. Brunton, S. Wuhrer, C. Shu, P. Bose, E. D. Demaine, Filling Holes in Triangular Meshes by Curve Unfolding, SMI 2009].


    • Ahmed   Abdelhafiz , Björn   Riedel and Wolfgang   Niemeier , Towards a 3D true colored space by the fusion of laser scanner point cloud and digital photos , Proceedings of the ISPRS Working Group V/4 Workshop (3D-ARCH 2005) . Google Scholar
    • Marco Attene and Bianca Falcidieno, Remesh: An interactive environment to edit and repair triangle meshes, SMI '06: Proceedings of the IEEE International Conference on Shape Modeling and Applications 2006 (2006) p. 41. Google Scholar
    • Gill Barequet, Matthew Dickerson and David Eppstein, On triangulating three-dimensional polygons, Symposium on Computational Geometry (1996) pp. 38–47. Google Scholar
    • Gill Barequet and Micha Sharir, Computer Aided Geometric Design 12(2), 207 (1995), DOI: 10.1016/0167-8396(94)00011-G. CrossrefGoogle Scholar
    • Alexander Bobenko and Peter Schröder, Discrete willmore flow, Eurographics Symposium on Geometry Processing (2005) pp. 101–110. Google Scholar
    • John Branch, Flavio Prieto and Pierre Boulanger, Automatic hole-filling of triangular meshes using local radial basis function, Third International Symposium on 3D Data Processing, Visualization and Transmission (3DPVT'06) (2006) pp. 727–734. Google Scholar
    • Jonathan C.   Carr et al. , Reconstruction and representation of 3d objects with radial basis functions , ACM Transactions on Graphics (SIGGRAPH'01) . Google Scholar
    • Chun-Yen   Chen , Kuo-Young   Cheng and Hong-Yuan Mark   Liao , Fairing of polygon meshes via bayesian discriminant analysis , International Conference in Central Europe on Computer Graphics, Visualization and Computer Vision . Google Scholar
    • L. Paul Chew. Guaranteed-quality triangular meshes. Technical Report TR 89-983, Computer Science Department, Cornell University, 1989 . Google Scholar
    • James Daviset al., Filling holes in complex surfaces using volumetric diffusion, First International Symposium on 3D Data Processing, Visualization and Transmission (3DPVT'02) (2002) pp. 438–433. Google Scholar
    • Tamal K. Dey and Samrat Goswami, Tight cocone: A water-tight surface reconstructor, ACM Symposium on Solid Modeling and Applications 2003 (2003) pp. 127–134. Google Scholar
    • Paulo   Dias et al. , Registration and fusion of intensity and range data for 3D modelling of real world scenes , Fourth International Conference on 3-D Digital Imaging and Modeling (3DIM'03) . Google Scholar
    • Ye. Duanet al., Shape reconstruction from 3D and 2D data using PDE-based deformable surfaces, ECCV3 (2004) pp. 238–251. Google Scholar
    • Sabry F. El-Hakimet al., Effective 3D modeling of heritage sites, Fourth International Conference on 3-D Digital Imaging and Modeling (3DIM'03) (2003) pp. 302–309. Google Scholar
    • Carlos H. Esteban and Francis Schmitt, A snake approach for high quality image-based 3D object modeling, 2nd IEEE Workshop on Variational, Geometric and Level Set Methods in Computer Vision (Nice, France, 2003) pp. 241–248. Google Scholar
    • Olivier Faugeras and Renaud Keriven, IEEE Transactions on Image Processing 7(3), 336 (1998), DOI: 10.1109/83.661183. CrossrefGoogle Scholar
    • Richard   Hartley and Andrew   Zisserman , Multiple View Geometry in Computer Vision ( Cambridge University Press , 2000 ) . Google Scholar
    • Joel Hass, Jack Snoeyink and William P. Thurston, Discrete and Computational Geometry 29(1), 1 (2003), DOI: 10.1007/s00454-002-2707-6. CrossrefGoogle Scholar
    • Vu Hoang Hiepet al., Towards highresolution large-scale multi-view stereo, IEEE Conference on Pattern Recognition and Computer Vision (CVPR97) (2009) pp. 1430–1437. Google Scholar
    • Klaus Hildebrandt and Konrad Polthier, Computer Graphics Forum 23, 391 (2004), DOI: 10.1111/j.1467-8659.2004.00770.x. CrossrefGoogle Scholar
    • Tao Ju, Robust repair of polygonal models, ACM Transactions on Graphics (SIGGRAPH'04) (ACM, New York, NY, USA, 2004) pp. 888–895. Google Scholar
    • Yongtae Jun, Computer-Aided Design 37(2), 263 (2005). CrossrefGoogle Scholar
    • Scott Kirpatrick, Dan Gelatt and Mario Vecchi, Science 220(4598), 671 (1983). CrossrefGoogle Scholar
    • Leif Kobbeltet al., Interactive multi-resolution modeling on arbitrary meshes, Conference on Computer graphics and interactive techniques (SIGGRAPH98) (1998) pp. 105–114. Google Scholar
    • Andrew Ladd and Lydia Kavraki, The International Journal of Robotics Research 23(7–8), 797 (2004), DOI: 10.1177/0278364904045469. CrossrefGoogle Scholar
    • Bruno Lévy, Dual domain extrapolation, ACM Transactions on Graphics (SIGGRAPH'03) (2003) pp. 364–369. Google Scholar
    • Gen Li, Xiu-Zi Ye and San-Yuan Zhang, Engineering with Computers 24(2), 119 (2008), DOI: 10.1007/s00366-007-0075-9. CrossrefGoogle Scholar
    • Peter Liepa, Filling holes in meshes, Eurographics Symposium on Geometry Processing (2003) pp. 200–205. Google Scholar
    • Dong C. Liu and Jorge Nocedal, Mathematical Programming 45, 503 (1989), DOI: 10.1007/BF01589116. CrossrefGoogle Scholar
    • Minica Panchetti, Jean-Philippe Pernot, and Philippe Véron. Towards recovery of complex shapes in meshes using digital images for reverse engineering applications. Computer Aided Design, Accepted for publication . Google Scholar
    • Jean-Philippe Pernot, George-Florin Moraru and Philippe Véron, Journal of Engineering Design 18(5), 459 (2007), DOI: 10.1080/09544820701403797. CrossrefGoogle Scholar
    • Joshua   Podolak and Szymon   Rusinkiewicz , Atomic volumes for mesh completion , Eurographics Symposium on Geometry Processing . Google Scholar
    • Jean-Philippe Pons, Renaud Keriven, and Olivier Faugeras. Modelling Non-Rigid Dynamic Scenes from Multi-View Image Sequences, in Handbook of Mathematical Models in Computer Vision, N. Paragios, Y. Chen and O. Faugeras, Eds, 2006 . Google Scholar
    • William H.   Press et al. , Numerical recipes in C: the art of scientific computing , 2nd edn. ( Cambridge University Press , 1992 ) . Google Scholar
    • Steven   Seitz et al. , A comparison and evaluation of multi-view stereo reconstruction algorithms , Proc. Computer Vision and Pattern Recognition (CVPR 2006) . Google Scholar
    • Andrei Sharf, Marc Alexa and Daniel Cohen-Or, ACM Transactions on Graphics (SIGGRAPH'04) 23(3), 878 (2004), DOI: 10.1145/1015706.1015814. CrossrefGoogle Scholar
    • Jonathan R. Shewchuk, Triangle: Engineering a 2D quality mesh generator and Delaunay triangulator, First Workshop on Applied Computational Geometry (1996) pp. 124–133. Google Scholar
    • Philip   Shilane et al. , The princeton shape benchmark , Proceedings of Shape Modeling International . Google Scholar
    • Olga Sorkine and Daniel Cohen-Or, Least-squares meshes, International Conference on Shape Modeling and Applications (SMI) (2004) pp. 191–199. Google Scholar
    • Lavanya Sita Tekumalla and Elaine Cohen. Hole-filling algorithm for triangular meshes. Technical Report UUCS-04-019, School of Computing, University of Utah, 2004 . Google Scholar
    • Greg Turk and Marc Levoy, Zippered polygon meshes from range images, Proceedings of SIGGRAPH'94 (1994) pp. 311–318. Google Scholar
    • Songhua   Xu et al. , Image guided geometry inference , Third International Symposium on 3D Data Processing, Visualization and Transmission (3DPVT'06) . Google Scholar
    • Wei Zhao, Shuming Gao and Hongwei Lin, The Visual Computer 23(12), 987 (2007), DOI: 10.1007/s00371-007-0167-y. CrossrefGoogle Scholar
    • Ciyou Zhuet al., ACM Trans. Mathematical Software 23(4), 550 (1997), DOI: 10.1145/279232.279236. CrossrefGoogle Scholar