A triangulation-based hole patching method using differential evolution

• Published in: Computer aided design 2013-12, Vol.45 (12), p.1651-1664
• Main Authors: Xie, Wei-Cheng, Zou, Xiu-Fen
• Format: Article
• Language: English
• Subjects: Algorithms; Boundaries; Curvature; Damage; Data points; Differential evolution; Evolution; Hole patching; Mesh optimization; Patching; Point correspondence; Three dimensional; Triangulation model
• ISSN: 0010-4485; 1879-2685
• DOI: 10.1016/j.cad.2013.08.003

In this work, a new hole patching method (namely as, HPDE) is proposed to repair the damaged or ill-scanned three dimensional objects in real engineering applications. Our method differentiates from other related algorithms mainly on the following three aspects. Firstly, our algorithm sufficiently utilizes the point information around the considered hole for each prediction by constructing point correspondences on both sides of the boundary curve of the hole; secondly, the missing points in the hole region are predicted by the algorithm of differential evolution (DE), which is used to obtain the topological and geometrical structures of the mesh in the hole region; thirdly, operations of mesh optimization are adopted for improving the quality of the obtained triangulation mesh. Numerical results on kinds of holes with complex shape and large curvature, and a comparison with two recently proposed algorithms verify the effectiveness of the algorithm, further experiments on the noisy data points illustrate the robustness of the algorithm against noise. •A new hole patching method is proposed to repair the defective model.•The information on both sides of the boundary around the considered hole is used.•The points in the hole region are predicted by differential evolution.•The operations of mesh optimization are used to improve the quality of the mesh.