research-article

Context-based coherent surface completion

Authors:

Eitan GrinspunAuthors Info & Claims

ACM Transactions on Graphics (TOG), Volume 33, Issue 1

Article No.: 5, Pages 1 - 12

https://doi.org/10.1145/2532548

Published: 07 February 2014 Publication History

Abstract

We introduce an algorithm to synthesize missing geometry for a given triangle mesh that has “holes.” Similarly to previous work, the algorithm is context based in that it fills the hole by synthesizing geometry that is similar to the remainder of the input mesh. Our algorithm goes further to impose a coherence objective. A synthesis is coherent if every local neighborhood of the filled hole is similar to some local neighborhood of the input mesh. This requirement avoids undesired features such as can occur in context-based completion. We demonstrate the algorithm's ability to fill holes that were difficult or impossible to fill in a compelling manner by earlier approaches.

Supplementary Material

harary (harary.zip)

Supplemental movie and image files for, Context-based coherent surface completion

Download
13.77 MB

MP4 File (a5-sidebyside.mp4)

Download
14.11 MB

References

[1]

G. H. Bendels, 2007. Methods for 3D geometry processing in the cultural heritage domain. Ph.D. Dissertation, University of Bonn.

[2]

G. H. Bendels, R. Schnabel, and R. Klein. 2005. Detail-preserving surface inpainting. In Proceedings of the 6^th International Conference on Virtual Reality, Archaeology and Intelligent Cultural Heritage (VAST'05). 41--48.

Digital Library

[3]

S. Bischoff, D. Pavic, and L. Kobbelt. 2005. Automatic restoration of polygon models. ACM Trans. Graph. 24, 4, 1332--1352.

Digital Library

[4]

J. Branch, F. Prieto, and P. Boulanger. 2006. A hole-filling algorithm for triangular meshes using local radial basis function. In Proceedings of the 3^rd International Symposium on 3D Data Processing, Visualization and Transmission (3DPVT'06). 727--734.

Digital Library

[5]

T. P. Breckon and R. B. Fisher. 2005. Non-parametric 3D surface completion. In Proceedings of the 5^th International Conference on 3-D Digital Imaging and Modeling (3DIM'05). 573--580.

Digital Library

[6]

C. Y. Chen and K. Y. Cheng. 2008. A sharpness-dependent filter for recovering sharp features in repaired 3D mesh models. IEEE Trans. Vis. Comput. Graph. 14, 1, 200--212.

Digital Library

[7]

U. Clarenz, U. Diewald, G. Dziuk, M. Rumpf, and R. Rusu. 2004. A finite element method for surface restoration with smooth boundary conditions. Comput. Aid. Geom. Des. 21, 5, 427--445.

Digital Library

[8]

J. Davis, S. R. Marschner, M. Garr, and M. Levoy. 2002. Filling holes in complex surfaces using volumetric diffusion. In Proceedings of the 1^st International Symposium on 3D Data Processing, Visualization, and Transmission (3DPVT'02). 428--441.

[9]

A. P. Dempster, N. M. Laird, and D. B. Rubin. 1977. Maximum likelihood from incomplete data via the em algorithm. J. Royal Statist. Soc. Series B 39, 1, 1--38.

[10]

A. A. Efros and T. K. Leung. 1999. Texture synthesis by non-parametric sampling. In Proceedings of the IEEE International Conference on Computer Vision (ICCV'99), vol. 2. 1033--1038.

Digital Library

[11]

M. Fisher, P. Schröder, M. Desbrun, and H. Hoppe. 2007. Design of tangent vector fields. ACM Trans. Graph. 26, 3, 1--9.

Digital Library

[12]

R. Gal, A. Shamir, T. Hassner, M. Pauly, and D. Cohen-Or. 2007. Surface reconstruction using local shape priors. In Proceedings of the 5^th Eurographics Symposium on Geometry Processing (SGP'07). 253--262.

Digital Library

[13]

M. Garland and P. S. Heckbert. 1997. Surface simplification using quadric error metrics. In Proceedings of the 24^th Annual Conference on Computer Graphics and Interactive Techniques (SIGGRAPH'97). 209--216.

Digital Library

[14]

T. Q. Guo, J. J. Li, J. G. Weng, and Y. T. Zhuang. 2006. Filling holes in complex surfaces using oriented voxel diffusion. In Proceedings of the International Conference on Machine Learning and Cybernetics. 4370--4375.

[15]

P. Heider, A. Pierre-Pierre, R. Li, and C. Grimm. 2011. Local shape descriptors, a survey and evaluation. In Proceedings of the 4^th Eurographics Conference on 3D Object Retrieval (3DOR'11). 49--56.

Digital Library

[16]

A. E. Johnson and M. Hebert. 1999. Using spin images for efficient object recognition in cluttered 3D scenes. IEEE Trans. Pattern Anal. Mach. Intell. 21, 5, 433--449.

Digital Library

[17]

T. Ju. 2004. Robust repair of polygonal models. ACM Trans. Graph. 23, 3, 888--895.

Digital Library

[18]

T. Ju. 2009. Fixing geometric errors on polygonal models: A survey. J. Comput. Sci. Technol. 24, 1, 19--29.

Digital Library

[19]

J. J. Koenderink and A. J. van Doorn. 1992. Surface shape and curvature scales. Image Vis. Comput. 10, 8, 557--564.

Digital Library

[20]

M. Kolomenkin, I. Shimshoni, and A. Tal. 2011. Prominent field for shape processing and analysis of archaeological artifacts. Int. J. Comput. Vis. 94, 1, 89--100.

Digital Library

[21]

J. Kopf, C. W. Fu, D. Cohen-Or, O. Deussen, D. Lischinski, and T. T. Wong. 2007. Solid texture synthesis from 2D exemplars. ACM Trans. Graph. 26, 3, 1--9.

Digital Library

[22]

V. Kraevoy and A. Sheffer. 2005. Template-based mesh completion. In Proceedings of the Symposium on Geometry Processing (SGP'05). 13--22.

Digital Library

[23]

V. Kwatra, D. Adalsteinsson, T. Kim, N. Kwatra, M. Carlson, and M. C. Lin. 2007. Texturing fluids. IEEE Trans. Vis. Comput. Graph. 13, 5, 939--952.

Digital Library

[24]

V. Kwatra, I. Essa, A. Bobick, and N. Kwatra. 2005. Texture optimization for example-based synthesis. ACM Trans. Graph. 24, 3, 795--802.

Digital Library

[25]

G. Leifman and A. Tal. 2012. Mesh colorization. Comput. Graph. Forum 31, 2.

Digital Library

[26]

P. Liepa. 2003. Filling holes in meshes. In Proceedings of the Eurographics/ACM SIGGRAPH Symposium on Geometry Processing (SGP'03). 200--205.

Digital Library

[27]

M. Müller, B. Heidelberger, M. Teschner, and M. Gross. 2005. Meshless deformations based on shape matching. ACM Trans. Graph. 24, 3, 471--478.

Digital Library

[28]

M. X. Nguyen, X. Yuan, and B. Chen. 2005. Geometry completion and detail generation by texture synthesis. Vis. Comput. 21, 8--10, 669--678.

[29]

Y. Ohtake, A. Belyaev, M. Alexa, G. Turk, and H. P. Seidel. 2003. Multilevel partition of unity implicits. ACM Trans. Graph. 22, 3, 463--470.

Digital Library

[30]

Y. Ohtake, A. Belyaev, and H. P. Seidel. 2004. Ridge-valley lines on meshes via implicit surface fitting. ACM Trans. Graph. 23, 3, 609--612.

Digital Library

[31]

S. Park, X. Guo, H. Shin, and H. Qin. 2006. Surface completion for shape and appearance. Vis. Comput. 22, 3, 168--180.

Digital Library

[32]

M. Pauly, N. J. Mitra, J. Giesen, M. Gross, and L. J. Guibas. 2005. Example based 3D scan completion. In Proceedings of the 3^rd Eurographics Symposium on Geometry Processing (SGP'05).

Digital Library

[33]

M. Pauly, N. J. Mitra, J. Wallner, H. Pottmann, and L. J. Guibas. 2008. Discovering structural regularity in 3D geometry. ACM Trans. Graph. 27, 3, 1--12.

Digital Library

[34]

J. P. Pernot, G. Moraru, and P. Véron. 2006. Filling holes in meshes using a mechanical model to simulate the curvature variation minimization. Comput. Graph. 30, 6, 892--902.

Digital Library

[35]

S. Rusinkiewicz and M. Levoy. 2001. Efficient variants of the icp algorithm. In Proceedings of the 3^rd International Conference on 3D Digital Imaging and Modeling (3DIM'01). 145--152.

[36]

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

Digital Library

[37]

D. Simakov, Y. Caspi, E. Shechtman, and M. Irani. 2008. Summarizing visual data using bidirectional similarity. In Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR'08). 1--8.

[38]

O. Sorkine and D. Cohen-Or. 2004. Least-squares meshes. In Proceedings of the International Conference on Shape Modeling and Applications (SMI'04). 191--199.

Digital Library

[39]

J. Sun, M. Ovsjanikov, and L. Guibas. 2009. A concise and provably informative multi-scale signature based on heat diffusion. Comput. Graph. Forum 28, 5, 1383--1392.

[40]

A. Vaxman, M. Ben-Chen, and C. Gotsman. 2010. A multi-resolution approach to heat kernels on discrete surfaces. ACM Trans. Graph. 29, 4, 1--10.

Digital Library

[41]

J. Verdera, V. Caselles, M. Bertalmio, and G. Sapiro. 2003. Inpainting surface holes. In Proceedings of the International Conference on Image Processing (ICIP'03), vol. 2. 903--906.

[42]

J. Wang and M. M. Oliveira. 2007. Filling holes on locally smooth surfaces reconstructed from point clouds. Image Vis. Comput. 25, 1, 103--113.

[43]

Y. Wexler, E. Shechtman, and M. Irani. 2007. Space-time completion of video. IEEE Trans. Pattern Anal. Mach. Intell. 29, 3, 463--476.

Digital Library

[44]

C. Xiao, W. Zheng, Y. Miao, Y. Zhao, and Q. Peng. 2007. A unified method for appearance and geometry completion of point set surfaces. Vis. Comput. 23, 6, 433--443.

Digital Library

[45]

K. Xu, D. Cohen-Or, T. Ju, L. Liu, H. Zhang, S. Zhou, and Y. Xiong. 2009a. Feature-aligned shape texturing. ACM Trans. Graph. 28, 5, 108: 1--8.

Digital Library

[46]

K. Xu, H. Zhang, A. Tagliasacchi, L. Liu, G. Li, M. Meng, and Y. Xiong. 2009b. Partial intrinsic reflectional symmetry of 3D shapes. ACM Trans. Graph. 28, 5, 138: 1--10.

Digital Library

[47]

S. Xu, A. Georghiades, H. Rushmeier, J. Dorsey, and L. McMillan. 2006. Image guided geometry inference. In Proceedings of the 3^rd International Symposium on 3D Data Processing, Visualization, and Transmission (3DPVT'06). 310--317.

Digital Library

[48]

S. Zelinka and M. Garland. 2004. Similarity-based surface modelling using geodesic fans. In Proceedings of the Eurographics/ACM SIGGRAPH Symposium on Geometry Processing (SGP'04). 204--213.

Digital Library

[49]

W. Zhao, S. Gao, and H. Lin. 2007. A robust hole-filling algorithm for triangular mesh. The Vis. Comput. 23, 12, 987--997.

Digital Library

[50]

K. Zhou, X. Huang, X. Wang, Y. Tong, M. Desbrun, B. Guo, and H. Y. Shum. 2006. Mesh quilting for geometric texture synthesis. ACM Trans. Graph. 25, 3, 690--697.

Digital Library

Cited By

Hattori SYatagawa TOhtake YSuzuki H(2025)Learning Self-Prior for Mesh Inpainting Using Self-Supervised Graph Convolutional NetworksIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2024.336436531:2(1448-1464)Online publication date: 1-Feb-2025
https://dl.acm.org/doi/10.1109/TVCG.2024.3364365
Du ZDou JLiu ZWei JWang GXie NYang YWooldridge MDy JNatarajan S(2024)CDPNetProceedings of the Thirty-Eighth AAAI Conference on Artificial Intelligence and Thirty-Sixth Conference on Innovative Applications of Artificial Intelligence and Fourteenth Symposium on Educational Advances in Artificial Intelligence10.1609/aaai.v38i2.27930(1635-1643)Online publication date: 20-Feb-2024
https://dl.acm.org/doi/10.1609/aaai.v38i2.27930
Sun JGuo RZhang J(2024)Global and Uniform Point Cloud Completion With Density-Sensitive Transformer for Small-Scale 3-D Object ReconstructionIEEE Transactions on Industrial Informatics10.1109/TII.2024.339356520:8(10499-10509)Online publication date: Aug-2024
https://doi.org/10.1109/TII.2024.3393565
Show More Cited By

Index Terms

Context-based coherent surface completion
1. Computing methodologies
  1. Computer graphics

Recommendations

Context-based surface completion
SIGGRAPH '04: ACM SIGGRAPH 2004 Papers

Sampling complex, real-world geometry with range scanning devices almost always yields imperfect surface samplings. These "holes" in the surface are commonly filled with a smooth patch that conforms with the boundary. We introduce a context-based method: ...
Complex hole-filling algorithm for 3D models
CGI '17: Proceedings of the Computer Graphics International Conference

In this paper, we propose a new and simple method for filling complex holes in surfaces. To fill a hole, locally uniform points are added to the hole by creating contour curves inside the boundary edges of the hole. A set of contour curves is created by ...
Filling holes on the surface of 3D point clouds based on tangent plane of hole boundary points
SoICT '16: Proceedings of the 7th Symposium on Information and Communication Technology

Filling the holes of a triangular mesh has been studied for many years in the field of geometric modeling. This research is one of the reconstructing steps of a triangular mesh (or called refinement of a mesh) in order to improve the quality of a 3D ...

Comments

Information & Contributors

Information

Published In

cover image ACM Transactions on Graphics

ACM Transactions on Graphics Volume 33, Issue 1

January 2014

179 pages

ISSN:0730-0301

EISSN:1557-7368

DOI:10.1145/2577382

Issue’s Table of Contents

Copyright © 2014 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 07 February 2014

Accepted: 01 May 2013

Revised: 01 April 2013

Received: 01 November 2012

Published in TOG Volume 33, Issue 1

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

Division of Information and Intelligent Systems
Israel Science Foundation
Microsoft
Jacobs-Qualcomm Foundation
United States - Israel Binational Science Foundation
Ollendorff Foundation
Viterbi Foundation

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

62
Total Citations
View Citations
1,074
Total Downloads

Downloads (Last 12 months)33
Downloads (Last 6 weeks)2

Reflects downloads up to 03 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Hattori SYatagawa TOhtake YSuzuki H(2025)Learning Self-Prior for Mesh Inpainting Using Self-Supervised Graph Convolutional NetworksIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2024.336436531:2(1448-1464)Online publication date: 1-Feb-2025
https://dl.acm.org/doi/10.1109/TVCG.2024.3364365
Du ZDou JLiu ZWei JWang GXie NYang YWooldridge MDy JNatarajan S(2024)CDPNetProceedings of the Thirty-Eighth AAAI Conference on Artificial Intelligence and Thirty-Sixth Conference on Innovative Applications of Artificial Intelligence and Fourteenth Symposium on Educational Advances in Artificial Intelligence10.1609/aaai.v38i2.27930(1635-1643)Online publication date: 20-Feb-2024
https://dl.acm.org/doi/10.1609/aaai.v38i2.27930
Sun JGuo RZhang J(2024)Global and Uniform Point Cloud Completion With Density-Sensitive Transformer for Small-Scale 3-D Object ReconstructionIEEE Transactions on Industrial Informatics10.1109/TII.2024.339356520:8(10499-10509)Online publication date: Aug-2024
https://doi.org/10.1109/TII.2024.3393565
Kim KChoi JPark Y(2024)A new spatial data structure for triangular mesh with toroidal patchesJournal of King Saud University - Computer and Information Sciences10.1016/j.jksuci.2023.10189136:1Online publication date: 17-Apr-2024
https://dl.acm.org/doi/10.1016/j.jksuci.2023.101891
Al shawabkeh RArar M(2024)Virtual reality as a tool to enhance the efficiency and reliability of the virtual reconstruction process for heritage/archaeological sites: The case of umm Al-Jimal in JordanDigital Applications in Archaeology and Cultural Heritage10.1016/j.daach.2024.e0032533(e00325)Online publication date: Jun-2024
https://doi.org/10.1016/j.daach.2024.e00325
Gisbert GChaine RCoeurjolly D(2024)Neural inpainting of folded fabrics with interactive editingComputers and Graphics10.1016/j.cag.2024.103997122:COnline publication date: 1-Aug-2024
https://dl.acm.org/doi/10.1016/j.cag.2024.103997
Wu XLu ZQu CZhou HMiao Y(2024)Scnet: shape-aware convolution with KFNN for point clouds completionInternational Journal of Machine Learning and Cybernetics10.1007/s13042-024-02359-116:3(1671-1690)Online publication date: 16-Sep-2024
https://doi.org/10.1007/s13042-024-02359-1
Lan Yiling 兰Kang Chuanli 康Wang Ning 王Yang Jiale 杨Chen Jinqi 陈(2023)附加增值条件的移动最小二乘法的点云孔洞修补Infrared and Laser Engineering10.3788/IRLA2022039052:2(20220390)Online publication date: 2023
https://doi.org/10.3788/IRLA20220390
Li WChen XWang JChen B(2023)Patch-Based 3D Natural Scene Generation from a Single Example2023 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)10.1109/CVPR52729.2023.01608(16762-16772)Online publication date: Jun-2023
https://doi.org/10.1109/CVPR52729.2023.01608
Basu APaul SGhosh SDas SChanda BBhagvati CSnasel V(2023)Digital Restoration of Cultural Heritage With Data-Driven Computing: A SurveyIEEE Access10.1109/ACCESS.2023.328063911(53939-53977)Online publication date: 2023
https://doi.org/10.1109/ACCESS.2023.3280639
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Issue’s Table of Contents