基于特征线的三维模型孔洞修复方法

刘　震，白丽丽，缪永伟

(1．浙江工业大学 理学院，浙江 杭州 310023；2．浙江工业大学 计算机科学与技术学院，浙江 杭州 310023)

基于特征线的三维模型孔洞修复方法

刘震1，白丽丽1，缪永伟2

(1．浙江工业大学 理学院，浙江 杭州 310023；2．浙江工业大学 计算机科学与技术学院，浙江 杭州 310023)

摘要：三维模型的孔洞修复是数字几何处理中的一个重要问题.首先利用耳切三角化技术，提出了针对三维模型孔洞的一种基曲面构建方法.然后利用孔洞周围探测得到的特征线的信息来恢复孔洞区域的细节.对于孔洞区域的三角形，根据特征线确定的细分顺序进行细分.细分方法是利用三角形的邻域点的信息和特征线的信息拟合二次曲面，再将三角形的重心投影到拟合的二次曲面上.实验表明：基于特征线的修复方法能够较好地捕获模型的全局特征，并能够有效恢复孔洞区域的显著几何特征，从而获得较自然的修复效果.

关键词：孔洞修复；基曲面；特征线；优先三角形；拟合二次曲面

The repair methods for hole of three-dimensional model based on feature lines

LIU Zhen1, BAI Lili1, MIAO Yongwei2

(1.College of Science, Zhejiang University of Technology, Hangzhou 310023, China；

2.College of Computer Science and Technology, Zhejiang University of Technology, Hangzhou 310023, China)

Abstract:The repair method for hole of three-dimensional model is an important quesiton in the area of 3D digital geometry processing. A surface-based construction method for 3D model is presented in this paper based on the technique of ear clipping triangulation. The characterisitic lines detected from the region around the hole are used to recover the details of the hole area. According to the order of the feature line, the triangular region of the hole will be subdivided. The subdivided method takes advantage of the information of adjacent points in the triangle region and the information of feature lines to fit conicoid. Then the center of gravity of the triangle is projected onto the fitted conicoid. The experiment results shows that this method based on feature lines can capture the global structure of the model and recover the salient geometric features in the hole patch in a natural way.

Keywords:model repair; base surface; feature lines; prior triangle; quadric surface fitting

随着三维扫描技术和建模技术的发展，三维数字化模型的应用变得越来越广泛.但由于扫描技术的限制和模型实体本身的缺陷，获取的大量的3D模型通常情况下都有孔洞存在.为了方便地对模型进一步进行各类几何处理操作[1]，如三维渲染[2]，重建[3]，检索[4-5]等，都需要对模型的孔洞进行修复.现有的修复方法主要分为两类，即基于体的算法和曲面定向算法[6-8].基于体的算法主要思想是将输入的待修补模型转换成体素，然后利用等值面的提取最终实现修复[9-12].这类方法以较低的时间复杂度自动完成修复工作，但是由于网格和体素之间的转换，会丢失一些原始模型上本有的细节特征.曲面定向的算法一般是直接探测孔洞并对孔洞区域进行修复[13-16].这些算法可以分为两种.一种是利用平滑的曲面片直接对孔洞区域进行修复.这些方法能快速有效的实现模型修复，但是并不能恢复孔洞的细节特征.另一类是通过寻找与孔洞相似的区域进行修复.对于那些有相似区域的模型，利用这类算法能够得到一个非常好的修补结果，但是搜索相似区域的过程往往都比较耗时.笔者提出了一种基于特征线的三维孔洞修复方法.该方法的优势是效率较高，而且能够恢复孔洞区域的显著几何特征.

1基于特征线的修复方法

首先给出三维的耳切三角化的方法构建基曲面.然后，为了尽可能的利用孔洞周围的特征信息并沿着特征线恢复孔洞区域的细节特征，给出孔洞区域三角形的细分顺序和细分方法.

1.1基于切割耳的基曲面构建方法

该小节推广二维耳切三角化算法[17]，给出一种三维孔洞的剖分方法.利用这种方法得到的基曲面为孔洞区域提供了网格数据结构，这种网格数据结构为孔洞区域进一步添加细节信息提供了方便.

对于三维模型上的某个多边形孔洞P=[p0,p1,…,pn-1]，如果三个连续的顶点pi-1,pi,pi+1构成的内角小于π，那么pi-1,pi,pi+1构成P的一个耳.切割耳就是把Δpi-1pipi+1从多边形P中移除，移除后的多边形变为[p0,p1,…,pi-1,pi+1,…,pn-1].利用切割耳的方法对孔洞进行剖分，首先按逆时针方向收集模型上某个孔洞的边界顶点p0,p1,…,pn-1，得到孔洞P=[p0,p1,…,pn-1].然后利用切割耳对P进行剖分，再给出对带有孔洞的兔子模型的剖分结果.

1.2基于特征线的细节修复

为了利用孔洞周围的几何特征恢复孔洞区域的特征信息，首先探测和匹配孔洞周围的特征线.再根据探测到的特征线的信息给出孔洞区域三角形的细分顺序.有了这种细分顺序，可以沿着特征线为基曲面添加细节特征.对于孔洞区域要细分的三角形，通过把它的重心投影到拟合的二次曲面上对其进行细分.基于特征线的细节恢复过程具体如下.

1.2.1特征线的探测与匹配

首先利用[18]的方法探测孔洞周围的特征线，然后为探测得到的每一条特征线寻找其最优匹配对.下面给出选择一条特征线的最优匹配对的衡量标准MP，即

式中：S={si}为孔洞周围的特征线集合；si为以边界顶点vi,0为起点有m个采样点vi,0,…,vi,m的边界周围的特征线；aj,t为sj的第t个采样点vj,t在由si延伸的曲线上的投影，如图1所示.对于特征线si，能够使MP(si,sj)最大的sj为它的最优匹配.如果sj的最优匹配对也是si，那么我们称(si,sj)是一个匹配对.对于特征线匹配对(si,sj)我们用球线性插值u(t)将他们连接起来，即

式中:u0=(vi,0-o)，u1=(vj,0-o)(o是三个点vi,0,vj,0,vi,1所确定圆的中心)；φ为向量u0和u1之间的夹角.

图1　特征线的匹配Fig.1　Matching of the feature lines

1.2.2孔洞区域三角形细分顺序的确定

首先将孔洞区域从边界到孔洞中心进行分层.以P=[p0,p1,…,pn-1]，为边界的孔洞区域的第k层的三角形集合Δk为

Δk={Δpipjps|Δpipjps∈Nk(pm)且Δpipjps∉

Δk-1,m=0,1,…,n-1}

式中：Δ0=∅；Nk(pm)为点pm的k邻域三角形.

然后在孔洞区域的每一层，根据特征线判断要先细分的三角形，即优先三角形，就是那些与特征线的起点相连或与匹配对(si,sj)上的点vi,0,vj,0,vi,1,vj,1所拟合的特征平面相交的三角形.这样确定的孔洞区域三角形的细分顺序是从孔洞的第一层到其最后一层，在每一层首先细分优先三角形.

1.2.3三角形的细分方法

一个三角形通过把它的重心向拟合的二次曲面上投影的方法细分为三个三角形.对于某个层的三角形Δpipjps，下面是具体的细分过程.

1) 拟合二次曲面.对于Δpipjpk，用来拟合它的二次曲面的点的选择方式:① 如果三角形Δpipjps是一个非优先三角形，从三个顶点pi,pj,pk中选择到其重心G距离较近的两个点的邻域顶点来拟合这个三角形相应的二次曲面.② 如果三角形Δpipjpk有一个顶点在特征线上，那么选择在特征线上的顶点和另外一个到其重心较近的顶点的邻域顶点拟合二次曲面.③ 如果三角形Δpipjpk是一个与特征平面相交的优先三角形，那么首先选择在特征平面同侧的三角形的两个顶点，再选择一个位于球线性插值曲线上到两个同侧顶点的中点的距离最近的点.然后利用两个同侧顶点的邻域顶点和位于球线性插值曲线上的那个点拟合二次曲面.

2) 重心投影细分三角形Δpipjpk.首先将三角形Δpipjpk的重心G沿着三角形的法线方向n投影到拟合的二次曲面G′上，然后把Δpipjpk细分成为三个三角形ΔpipjG′,ΔpjpkG′和ΔpkpiG′，如图2所示.

图2　重心投影细分三角形Fig.2　Refinement of a triangle by projection of centroid

在细分过程中，如果三角形Δpipjps的平均边长大于孔洞的边界边的平均边长，就对Δpipjps进行细分.如果细分之后的三角形为狭长三角形，就把它的边进行翻转以保证得到正规的网格.为了能够使孔洞区域的顶点密度与孔洞周围的顶点密度一样，从孔洞边界开始重复这一细分过程直到内部三角形的平均边长低于孔洞边界的平均边长.修复结果如图3～5所示.

图3　兔子模型的孔洞的修复Fig.3　The results of completion of the rabbit model

图4　骆驼的修复Fig.4　The results of completion of camel

图5　对零件模型的修复结果Fig.5　The results of completion of the machine part

2实验结果与讨论

提出的基于特征线的修复算法已经在2.3GHz，4GB内存i3处理器上利用VisualC++得到了实现,图3～5给出了几个模型的修复结果并与Davis[9]和Ju[11]的方法进行了比较.

图3给出了具有33 600个顶点的模型兔子的修复结果.图3(b)为利用Ju[11]的方法得到的修复结果，运行时间为4s.图3(c)为利用Davis[9]等的方法修复的结果，运行时间为27s.笔者的方法因为恢复模型的细节特征，所用的时间比Davis[9]和Ju[11]的方法稍微长一些，运行时间为39s.在笔者的修复结果中，兔子的背部和腿部的特征得到了很好的保持，颈部的谷线也得到了很好地恢复.

图4给出了骆驼模型的修复结果.对于驼峰的修复，笔者的修复结果明显好于Ju[11]和Liepa[13]的修复结果.图5给出了零件的修复结果.对于该模型中不同尺度的孔洞，利用笔者的方法使得特征得到了很好地保持，获得了令人满意的修复结果.因为图5中模型的孔洞较大，Davis[9]和Ju[11]这两种方法都没有实现对孔洞的修复.

3结论

首先提出了一种构建基曲面的方法.这种方法的时间复杂度是线性的.在构建的基曲面的基础上，利用孔洞周围探测得到特征线的信息，给出孔洞区域三角形的细分顺序.这种细分顺序可以尽可能的利用孔洞周围的几何信息，沿着特征线修复孔洞区域的细节.基于特征线的修复方法不会破坏原始网格的数据结构，而且能够有效的恢复孔洞区域的几何特征，最终得到令人较满意的修复结果.

参考文献：

[1]BOTSCHM,PAULYM,KOBBELTL,etal.Geometricmodelingbasedonpolygonalmeshes[M].NewYork:ACMPress,2007.

[2]吕慧强，李益明，孔繁胜.基于互联网的3D复杂场景渲染算法研究[J].浙江工业大学学报，2003,31(1)：36-41.

[3]刘培君,陆国栋.基于面识别的三维重建[J].浙江工业大学学报，2000,28(7)：57-63.

[4]冯毅攀，刘志，潘翔，等.一种基于单一视图的三维模型检索方法[J].浙江工业大学学报，2012,40(4)：431-436.

[5]徐彩虹，刘志，潘翔，等.一种基于实例学习的三维模型检索匹配方法[J].浙江工业大学学报，2012,40(3)：326-330.

[6]JUT.Fixinggeometricerrorsonpolygonalmodels:asurvey[J].JournalofComputerScienceandTechnology,2009,24(1):19-29.

[7]ATTENEM,CAMPENM,KOBBELTL.Polygonmeshrepairing:anapplicationperspective[J].ACMComputingSurveys,2013,45(2):33-70.

[8]BOTSCHM,KOBBELTL,PAULYM,etal.Polygonmeshprocessing[M].Bombay:PetersAK,2010.

[9]DAVISJ,MARSCHNERSR,GARRM,etal.Fillingholesincomplexsurfacesusingvolumetricdiffusion[C]//ProceedingsofSymposiumon3DDataProcessingVisualizationandTransmission.Washington:IEEEComputerSociety,2002,428-438.

[10]NOORUDDINF.S,TURKG.Simplificationandrepairofpolygonalmodelsusingvolumetrictechniques[J].IEEETransactionsonVisualizationandComputerGraphics,2003,9(2):191-205.

[11]JUT.Robustrepairofpolygonalmodels[J].ACMTransactionsonGraphics,2004,23(3):888-895.

[12]BISCHOS,KOBBELTL.StructurepreservingCADmodelrepair[J].ComputerGraphForum,2005,24(3):527-536.

[13]LIEPAP.Fillingholesinmeshes[C]//ProceedingsoftheEurographicsSymposiumonGeometryProcessing．Aachen:EurographicsAssociation,2003:200-205.

[14]HARARYG,TALA,GRINSPUNE.Context-basedcoherentsurfacecompletion[J].ACMTransactionsonGraphics,2014,33(1):701-712.

[15]ZHAOW,GAOS,LIH.Arobusthole-fillingalgorithmfortriangularmesh[J].TheVisualComputer,2007,23(12):987-997.

[16]BRECKONTP,FISHERRB.Ahierarchicalextensionto3Dnon-parametricsurfacereliefcompletion[J].PatternRecognition,2012,45(1):172-185.

[17]周培德.计算几何——算法设计与分析[M].3版.北京：清华大学出版社,2008.

[18]HILDEBRANDTK,POLTHIERK,WARDETZKYM.Smoothfeaturelinesonsurfacemeshes[C]//ProceedingsoftheEurographicsSymposiumonGeometryProcessing．Vienna:EurographicsAssociation,2005:85-90.

(责任编辑：陈石平)

中图分类号：TP391

文献标志码：A

文章编号：1006-4303(2015)03-0346-04

作者简介：刘震(1976—)，男，河南商丘人，副教授，研究方向为数字几何处理，E-mail:zhenliu@zjut.edu.cn.

基金项目：国家自然科学基金资助项目(61272309)

收稿日期：2014-12-03