摘要：针对三维模型中带有各种原因造成的孔洞，为后续的模型分析操作带来困难，提出了一种基于曲率特征的三维模型孔洞修补方法。算法的基本思想是利用波前法对孔洞进行快速填充获得初始的修补网格，再运用网格优化的技术依据孔洞边界点的曲率特征对初始网格进行调整。首先根据邻接三角形中边界边的性质识别出孔洞的边界，然后使用波前法和三角形顶点的夹角关系完成孔洞的初始填充，接着结合曲率标准对孔洞网格进行细化，最后对修补孔洞的网格顶点进行几何形态的调整，使其与周围网格过渡自然。实验表明该算法简单、稳定，可以完成不同类型的孔洞修补。

关键字:三角网格；孔洞修补；波前法；三角剖分;网格细化；

Research on Hole-filling Algorithm for 3D Models

Abstract: Due  to existing  holes  in  the scanning  3D  models，this  paper  presents  a  novel hole-filling  algorithm based  on  the curvature character . The main idea of this approach is to fill the holes fast by advancing front method in order to obtain the initial patch mesh and the adjustment would  be  carried  out  by  the curvature feature  of  edge  point  of  holes. Firstly the  boundary  of  hole was  extracted based  on the nature  of adjacent triangles.  Then the  hole  was covered by the  initial  patch  mesh which obtained by using the advancing front method. Second the subdivision for the patch mesh was performed according to the standard of curvature. Finally the vertices of newly triangles were re-positioned by  Delaunay  principle  to  make  the  patch  better  fitting  the surrounding mesh.  The experiment  shows that  this algorithm is simple, efficient and stable, which can repair different kind’s holes.       

Keywords: triangle mesh; hole filling; advancing front method; triangulation; mesh refinement; 

0  引言 

三维网格模型因为其定义简单、描述能力强被广泛地用来表示三维模型。由于扫描和建模过程中的问题使得网格模型中总是存在孔洞或其他缺陷。这为很多后续操作如模型修复、有限元分析等带来困难，因此网格模型的孔洞修补是三维模型前期处理的重要组成部分。近年来，国内外的学者对三维模型孔洞修补的问题进行了大量的研究，取得了一定的成果[1-5]。 

常用的孔洞修补算法可以归纳为基于网格的方法和基于体表达两种[6]。基于网格的修补方法首先搜索孔洞的周边区域，再根据周边区域的特征进行网格的填充。如Liepa[ 4]首先识别出孔洞的边界后对其进行三角化,  然后根据周边网格的形状插入面片并进行平滑,获得了较好的填充效果,  但是算法的效率不高。Attene [7]使用了这种方法。Zhao[8]采用波前推进法完成对孔洞的粗略修补，再通过泊松方程调整顶点的位置，优化修补结果，可是结果的精确化程度不高。Pernot[9]通过插入面片的方法填补孔洞，始终使面片和孔洞周围保持最小曲率。但是在修补复杂孔洞时需要借助较多的人工干预。基于网格的方法只需要对网格缺损的部分进行填充，不会改变输入模型其它部分的网格特征，但是因为较少考虑孔洞本身的曲面特征，所以对于曲率较大的孔洞不能完成很好的填充。基于体表达的方法首先将输入模型转化为一种中间的体网格，在进行修补之后，再根据不同的等值面抽取方法，将其还原为三角网格模型。Davis[2]首先定义一个符号距离函数描述邻近的可见表面，然后用扩散的方法将其扩展到整个体数据场，直到包含所有的孔洞，然后重新输出模型。Bischoff [5]根据输入模型建立自适应八叉树，根据八叉树的形态操作完成模型拓扑，最后重构出模型。该方法可以很好地保留模型的尖锐特征。Fakir [10]将输入模型转化为一个均匀的自适应采样距离场，然后通过多边形化生成输入模型的简化版本，由于这一过程中需要进行整个模型的重采样，这样或导致孔洞的特征不能完全保留下来。基于体表达的方法需要借助中间体结构,输出模型会丢失原始模型的一些结构特征，不能保持与原始模型的一致性，并且会产生大量狭长的三角面片，影响新加入三角片的形状。 

在对这两类方法分析的基础上，本文提出了一种基于曲率特征的网格模型孔洞修补方法。该方法首先利用网格模型中对边界边的定义，识别出所有边界点，将得到的边界边相连得到孔洞边界。然后采用波前法对孔洞区域进行三角剖分得到修补网格，然后采用周边区域的曲率特征完成修补网格的细化，最后再调整网格的几何形态，使修补网格在保持各向异性的同时，能较好与孔洞周边区域融合。 

1  孔洞的边界识别 

在进行孔洞的修补之前，首先需要识别孔洞的边界。三角网格模型是由一系列顶点和连接这些点的三角形构成，仅连接一个三角形的边称为边界边，边界边上的点称为边界点，边界三角形是指拥有一个或两个边界点的三角形。依据网格模型这样的性质，对网格面进行遍历后，如图1所示将这样边的首尾相连就构成了孔洞的边界。具体实现的方法如下： Step1：对于模型表面S任意顶点L，获取其邻接点和邻接三角形的信息 Step2：比较该点的邻接点和邻接三角形数目。若相等，读取邻接点返回step1；若不等，标记L为边界点，存入边界点集合  并读取邻接点' L，重复step2。 Step3：重复上述步骤，直到边界点集合不产生新的点。 Step4：连接边界边，形成闭合环，得到孔洞边界。  图1  边界点和边界边 

2  波前法三角剖分  

三角剖分是解决孔洞修补问题的关键，传统的三角剖分方法，为了一次性得到最优化的网格，在生成网格模型时，加入各种约束条件，如Liepa[4]采用的动态规划算法，其时间复杂度高达到O(n3)。这里采用Lohner[11]和Lo[12]提出的波前法（Advancing Front Method ,AFM)来进行初始网格的生成。波前法使用了递归的思想，可以有效降低问题的时间复杂度，具有实现简单、速度快和生成的网格可控性好的优点，它已经成为网格生成最重要的算法之一。其基本思想是首先初始化带剖分区域的边界成为首尾相连的有向边的集合，称为波前。以当前的边界为起点，不断向内产生三角形，更新波前，逐步收缩边界直到波前为空。 波前法通常是选择具有最小夹角的边界边上的顶点作为当前点，算法的实现步骤如下： Step1：使用孔洞的边界点初始化波前 Step2：计算波前每一个顶点in相邻边( )1,iill+的夹角0v Step3：从最小夹角对应的顶点开始，根据图2的规则在il与1 il+决定的平面上生成三角形 Step4：将新构造的三角形的波前单元边添加到波前单元集合中。 Step5：重复step2，直到波前单元集合为空  图2  新增三角形的规则         

波前法是以原有的孔洞边界为基础进行三角形划分的，因此利用它生成的网格可以形成对任何形状孔洞的完全覆盖，这样就保证了算法的鲁棒性。算法中，1 iivv+是根据最小角原则新生成的有向边，newv，1 newv和2 newv是新生成的顶点，并与原有的顶点组成新的有向边，加入到波前单元集合中，取代原有的波前；然后再对新的波前进行再一次的划分，直到孔洞多边形被全部划分成三角形为止。这个的递归算法的最大时间复杂度是O(n)，平均的时间复杂度是O(logn)。相较传统的优化三角剖分法O(n3)的时间复杂度，极大提高了孔洞三角化的速度。 

但在修补过程中，应用的最小夹角原则，会导致生成的网格分布不均匀，进而影响最终的修补结果。因此就需要对生成的初始网格进行优化。   

3  基于曲率网格优化 

4.1网格细化 在一般的处理中都采用了分裂所有超过平均边长的边，生成新三角形的方法，通过消除狭长三角形来以改善网格的质量。若长边所在的区域比较平坦，这样的划分就没有必要了，反而会影响程序的实时性。由于曲率是反映曲面弯曲程度的重要指标，所以引入曲率作为三角形细化的判断指标。算法先计算原孔洞边界上每个顶点的高斯曲率，将其平均值作为阈值。然后分别计算每个新增三角形顶点的高斯曲率，对大于阈值的曲率要求的三角形的边进行分裂，直到满足一定的曲率要求为止。 高斯曲率是反映曲面弯曲程度的重要指标，估算的方法有很多。这里采用Meyer[13]的Voronoi方法来估算生成三角网格各顶点的高斯曲率。该方法是将曲面看作是一族网格的线性逼近，用空间网格在这个点的1-邻域的均值来近似度量该点处的几何性质。相关定义（如图3所示）： ip为三角网格上面的任意顶点，其jp  ，+1 jp，2 jp+是其邻接点。 jq为边ijpp与边1 ijpp+的夹角,A是ip在网格曲面上的一个无穷小领域 通常A是取ip的1-邻域，这里根据三角形的性质来分类讨论。如图4所示对于锐角三角形取其外心与其余两边的中点；对于钝角三角形取对应边的中心与其余两边的中点，MA为整个邻域的混合面积。  图3  曲率相关参数定义                        图4 ip点的1邻域 根据微分几何中的Gauss-Bonnet定理，高斯曲率的计算公 第9期  计  算  机  应  用  研  究  第30卷  式如下： ()1( ) (2 )G i ij N iMkpApqÎ=-å 

依据这一公式，分别计算孔洞原边界上各点的高斯曲率及其平均值averk，然后计算新增三角形iS各顶点的高斯曲率，并用邻接点曲率的均值代表边l的曲率lk。若lk大于averk，就对该边l进行分裂。分类方法是选取l的中点，作为新顶点插入，并与其余两顶点相连，形成新的三角形。 引入曲率作为三角形细分的标准，使得处于较弯曲曲面上的三角形能够细分为多个小三角形，而处于平坦曲面的三角形则不需要细化，这样较好体现了曲面三角化的各向异性，同时提高了补洞算法的速度。 

4.2 网格优化调整 Delaunay三角网所具有的空圆特性以及最大化最小角特性，使得所获取网格质量较高，这里采用的边置换的方法[14]来保证网格的Delaunay性质。对于两个邻接的三角形1 S和2 S，由1 S决定的外接圆，对进行判断，若其有一个顶点的投影点不包含在1 S所决定的圆内，则认为它具有Delaunay性质，就不需要进行调整，否则需进行如图5的边置换得到1' S与2' S。     图5  边置换 为使边置换后得到的网格与周边网格更好的进行过渡，还需要使用拉普拉斯算子对顶点位置进行调整。每个顶点一环邻域的加权重心，作为新的顶点位置，权重由一环邻域上的顶点密度所决定。 

4  试验结果与分析 

实验中针对不同类型的孔洞验证了本文提出的补洞算法。表1给出了不同复杂度模型修补孔洞所需要的时间，从执行时间可以看出，即使较为复杂的模型，利用本文的方法也能在较短时间内完成孔洞的修补。首先使用了stanford 的原始扫描bunny 模型进行试验，模型上有若干规则、大小不同的孔洞。图6(a)显示的是一个位于拐角的不规则小孔洞，修补图显示获得了较好的修补结果，图6(b)中的孔洞的面积较大，且具有较为明显的边界特征，修补结果基本体现了原来边界的几何特征。图7和图8中模型上的孔洞是人为造成的较大孔洞，应用本文方法也获得了较好的修补结果。图9所示为采用本文方法对颅骨三维模型上孔洞修补的结果。该孔洞面积较大，且所处位置的曲率较大，从修补结果可以看到，孔洞网格与周边网格形成了较好的拟合，过渡较为自然。 表一、四种不同模型的孔洞填充的时间 模型  顶点数  三角面片数  时间(ms) Cow  4896  8735  10 Bunny  35947  69451  42 人脸  236484  492543  121 颅骨  1380943  2790874  794  图6（a）Bunny模型的正面孔洞及修补结果  图6（b）Bunny模型的底面孔洞及修补结果  图7 cow模型孔洞及修补结果  图8  人脸模型孔洞及修补结果  图9  颅骨三维模型孔洞及修补结果 结束语      本文提出了一种高效并且鲁棒的三维模型孔洞填充算法。首先利用边界边的定义识别出孔洞边界，然后使用波前法完成孔洞的初始修补，下来根据曲率标准完成初始网格的细化，最后根据Delaunay性质优化网格，获得高质量的修补网格。实验结果表明，这种方法对于不同类型的孔洞均取得了理想的修补结果。在下一步工作中，我们将对修补网格特征的保持以及与周边网格实现连续过渡的问题进行深入研究，以获得更加理想的修补结果。 

参考文献   [1] BAREQUET G, SHARIR M. Filling gaps in the boundary of a polyhedron [J]. computer aided geometric design 1995; 12(2):207-229. [2]DAVIS J,  MARCHNER S,  CARR M, LEVOY M.  Filling  holes  in  complex surfaces using volumetric diffusion [C]. First international symposium on 3D data processing, visualization, and transmission; 2002: 428-438. [3]BORODIN  P,  NOVOTNI  M,  KLEIN R.  Progressive  gap  closing  for  mesh 1 S 1 S 2 S 1' S 2' S  第9期  计  算  机  应  用  研  究  第30卷  repairing  [M].Vince  J,  Earnshaw.  Advances  in Modeling,  Animation  and Rendering. Heidelberg: Springer, 2002:201- 213 [4]  LIEPA  P.  Filling  holes  in  meshes  [C].  Proceedings  of  the  Euro graphics/ACM  SIGGRAPH  Symposium  on  Geometry  Processing,  Aachen, 2003: 200- 205 [5]  BISCHOFF  S,  KOBBELT  L.  Structure  preserving  CAD  model repair [J].Computer Graph Forum 2005. 24(3): 527-536. [6] JU Tao. Fixing geometric errors on polygonal models[J]: a survey. Journal of Computer Science Technology 2009; 24(1):19-29. [7]ATTENE M.  A  lightweight  approach  to  repairing  digitized  polygon meshes [J]. Visual Computer 2010;    26(11): 1393-1406. [8]  ZHAO Wei, GAO Shuming,  LIN Hongwei. A  robust hole-filling  algorithm for triangular mesh [J]. Visual Computer 2007; 23(12):987–997. [9]PERNOT J.P,  MORARU  G,  VERON  P.  Filling  holes  in  meshes  using  a mechanical  model  to  simulate  the  curvature  variation  minimization  [J]. Computer Graph 2006; 30(6): 892–902. [10]F.  Nooruddin  and  G.  Turk.  Simplification  and  repair  of  polygonal  models using  volumetric techniques[J].  ACM  Transactions  on  Visualization  and Computer Graphics, 2003,9(2):191–205,. [11]LOHNER,  R,  PARIKH,  P,  and  GUMBERT  C,  Interactive  Generation  of Unstructured  Grid  for  Three  Dimensional  Problems[C].  Numerical  Grid Generation  in  Computational  Fluid  Mechanics  1988,  Pineridge  Press: 687-697 [12]LO S.H. Volume discretization into tetrahedral-I.Verification and orientation of boundary surfaces[C]. Computers and Structures, Vol 39, no. 5: 493-500 [13]  MEYER  M，DESBRUN  M，SCHRODER  P.  et  al.  Discrete differential-geometry  operators  for  triangulated  2-manifolds  [C]  In Visualization and Mathematics, Berlin, Germany, 2002, 52-58． [14]  张洁,岳玮宁,王楠,汪国平.三角网格模型的各向异性孔洞修补算法[J].计算机辅助设计与图形学学报.2007, 19(7):892-897