马 天，李娇娇，李 赟

(西安科技大学 计算机科学与技术学院，陕西 西安 710054)

0 引 言

虚拟牙齿矫正系统通过计算机逼真地模拟牙齿矫正过程，为患者量身定制治疗计划，进而将不整齐的牙齿排列整齐。牙齿(刚体)改变位置通常会引起牙龈(软组织)变形，因此精确、高效地模拟牙龈软组织的形变是该系统重要的一部分。在计算机图形学和计算机辅助设计中，通常用三角形网格来表示复杂的三维实体模型，在模拟牙龈软组织形变过程中通常会在牙龈表面产生褶皱，这种褶皱会影响形变仿真的真实性，因此对牙龈表面进行细分光滑处理显得十分必要。

细分算法的基本思想最早追溯到50年代中期到70年代末。CATMULL和CLARK第1次明确地提出了细分曲面的概念[1]。80年代初到90年代，形成了很多经典的细分算法。90年代中期，细分理论逐步完善并开始应用于工业邻域。近年来，三角网格细分技术不断被应用到计算机视觉、模式识别以及虚拟现实等邻域[2]。一般来说，三角网格模型的网格越密集，三角网格逼近程度越高，模型表面光滑度越好，模型精度越高[3]。均匀的小尺寸单元虽然可以保证满足网格的质量和计算精度，但会在过度平坦的区域产生过多的单元，从而极大地降低程序的时空效率[4]。因此，生成几何自适应光顺曲面网格就十分有必要。

用特殊的细分规则，在保证网格曲面光滑度要求的同时减少网格数量，这种方法就称为网格自适应细分[5]。自适应细分算法就是在均匀细分算法的基础上，采用特殊的判定准则，通常是设置阈值来判断某个三角网格是否进行下一次迭代细分[6]。通过控制细分深度，使那些满足精度的面片不再参与细分，而不满足的继续细分，从而大大减少冗余面片，提高模型的处理速度，减轻计算机的负担[7]。

自适应细分判定准则主要包括非几何准则和几何准则2类。非几何准则主要取决于外部环境，根据感兴趣区域或可见区域对模型进行自适应细分。几何准则通过计算一小块邻域的几何信息来决定细分深度，主要包括：基于网格控制顶点与其极限位置间距离的准则[8]；基于网格面片与其相应曲面片间距离的准则；基于控制顶点曲率的准则；基于三角面片面积的准则；基于碰撞检测的准则；基于运动时间的准则[9]；基于网格面夹角的准则。实际应用中经常选择几何准则作为自适应细分判定准则。

基于网格控制顶点与其极限位置间距离的准则，仅适用于逼近型细分，对于插值型细分，网格控制顶点与其极限位置间距离始终为零。基于网格面片与其相应曲面片间距离的准则，要求细分算法有对应的参数表示，但并非所有细分曲面都有参数表示。基于控制顶点曲率的准则中，离散点曲率的计算比较复杂[10]，该方法也具有一定的局限性。基于三角面片面积的准则，对于面积相同的规则三角形和狭长三角形难以很好的区分。基于碰撞检测的准则，是指当研究对象与其他物体发生碰撞时[11]，对碰撞区域进行细分从而避免发生穿透等来更加精确的模拟物体运动。鲍义东等将这种基于碰撞检测的自适应细分算法应用在虚拟手术训练系统中实现了较好的仿真效果[12]。但这里研究的是软组织的形变仿真，不适合使用该准则。基于运动时间的准则，是指根据物体在不同时刻的运动状态进行细分，因此也不适用于研究邻域。基于网格面夹角的准则，也叫做二面角准则，最早由AMRESH和FARIN等提出，是目前广泛采用的几何准则[13]。近年来，这种方法主要应用在其他仿真邻域，对于牙龈软组织形变仿真涉及到的不多。陈云翔等在对三维地形进行仿真时提出了平坦度的概念，其自适应判定准则以一个面片为基准，判断该面片1-邻域面片与该基准面片的夹角平均值与阈值的大小关系[14]。周怡等在对CAD零件模型进行自适应细分时采用基于平均法向量的自适应细分判定准则，以一个顶点为基准，判断该顶点1-邻域面片每个面片的平均法向量与其法向量夹角的平均值与阈值的大小关系。王艳艳等在进行自适应细分时采用顶点1-邻域内与该顶点相连较长3条边的端点构成的平面去代替其平均平面，并将顶点到其平均平面的距离作为判断顶点重要度的标准来对三角网格进行自适应细分[15]，但该方法不仅会造成较差的细分精度，细分后三角面片数仍较多。钟李涛等在对布料进行形变仿真时提出的顶点权重变形度也是一种基于二面角的方法[16]，但该方法在实际应用中需要键入命令来执行细分程序，因而灵活性不高。

总之，上述方法在进行自适应细分时或者细分效率较低，或者生成的三角网格质量较低、曲面光顺质量不高。主要研究虚拟牙齿矫正系统中牙龈软组织的形变仿真，为了更加真实、高效地模拟牙龈软组织的形变，需要对形变后牙龈三角网格进行自适应细分。因此，如何在保证细分效率的同时，使生成的三角网格更加规则，曲面光顺性更好，成为研究的主要问题。

1 Loop细分规则

Loop细分是一种基于三角网格、逼近型、1-4面分裂细分算法，由美国犹他大学的CHARLES LOOP于1987年在其硕士论文中提出[17]。该算法细分规则简单，光滑性好，生成的曲面质量较高，但对尖锐特征的保持能力较弱，处理后曲面会产生较大的收缩，在正则点处可以达到C2连续，在奇异点处达到C1连续，是目前应用最广泛的细分算法之一[18]。以Loop细分算法作为研究基础来对三角网格进行自适应细分。

图1 Loop细分过程

图2 Loop细分规则

2 三角网格质量评价方法

在虚拟牙龈软组织形变仿真过程中，牙龈表面通常会产生褶皱影响仿真效果。为了对比仿真效果，提高仿真精度，并进行后续的网格处理，研究三角网格质量评价方法具有重要意义。三角网格质量是指三角形几何形状的合理性，一般通过三角形单元的边长、面积、内角等来衡量[19]。三维模型中三角网格的数量、网格的大小、网格的形状以及网格单元拓扑结构是决定计算效率和精度的主要因素。因此网格质量度量方法主要包括：基于曲率的方法、基于三角形大小的方法、基于三角形规则度的方法、基于顶点度数的方法和基于二面角的方法。

基于曲率的方法。曲率可以度量曲面的凹凸程度，通常用平均曲率与原曲率的差值来确定顶点的调整量进而进行网格光顺。刘胜兰等提出主曲率均匀的光顺算法，以邻点的主曲率和主方向的加权平均值作为光顺后顶点的主曲率和主方向来确定顶点的调整量，从而较好的保持了模型的体积[20]。基于三角形大小的方法。三角形的大小是决定网格质量的一个重要标准，过大的三角形会影响模型的精度，过小的三角形会增加计算负担。潘炯波通过计算三角面片的面积与整个三角网格模型平均面积的比值，并比较该值与设定的阈值标准的大小来确定细分区域[21]。基于三角形规则度的方法。通常三角面片越接近正三角形，三维网格模型的质量越好。规则度度量最为常见的是顶点周围的最小角和最大角，另外还有网格外接圆半径等[22]。王忠飞等采用半径比的方法来评价三维模型的变形效果[23]，该方法不利于判断整个三维模型形变区域的光顺性。基于顶点度数的方法,良好的网格模型不仅需要每个三角形接近正三角形，而且要求三角形之间具有良好的拓扑关系[24]。顶点的度数是指共享该顶点的边的条数，是衡量三角网格模型质量又一个重要的标准。基于二面角的方法。基于二面角的方法通过计算三维网格相邻三角面片法向量夹角来度量粗糙程度[25]。史卓等通过对三角面片两两之间的夹角阈值做判断，并按一定的细分规则进行局部细分，从而使模型局部特征明显的部分更加精细[26]。

网格质量优化通过将节点不断的重定位到其邻域空间内的最优位置来提升曲面网格的质量。其目标是在精确地表示原始模型的基础上，尽可能地输出更为规则的网格，得到顶点分布比较均匀、三角形也尽可能接近正三角形的网格。但对网格形变操作后，衡量网格形变效果也是一个重要的方面。为了改善形变仿真后模型整体的仿真效果、提升网格质量，网格光顺质量度量是必不可少的环节。基于光滑度之和[27]，采用平均光滑度来度量网格光顺质量。

3 细分判定改进

3.1 顶点光滑度判定

文中基于二面角准则，提出顶点光滑度判定准则来对三角网格进行自适应细分，细分方式基于Loop细分模式。

三角网格中各个顶点vi的顶点光滑度是通过求该顶点1-邻域内相邻三角面片对的法向量夹角的平均值求得的，其公式为

(1)

式中k为顶点1-邻域内三角面片的个数；nj和n(j+1)%k分别为该顶点1-邻域内的相邻三角面片对Cj和C(j+1)%k的单位法向量；α为相邻三角面片对的法向量夹角。顶点1-邻域三角面片及其法向量如图3所示。

图3通过设定光滑阈值来选取自适应细分区域，光滑阈值为所有顶点的顶点光滑度的平均值，即

图3 顶点1-邻域三角面片及其法向量

(2)

式中θi为细分前每个顶点的顶点光滑度；N为细分前模型的顶点个数。

根据顶点光滑度及光滑阈值的定义可知：如果顶点1-邻域区域比较光滑，那么该顶点1-邻域内相邻三角面片对的法向量夹角就越小，这样顶点光滑度就越小；否则，顶点光滑度就越大。将顶点光滑度作为衡量顶点1-邻域区域光滑度大小的标准，然后再将该值与光滑阈值进行比较，从而来确定自适应细分区域。因此，可以说顶点的顶点光滑度和设定的光滑阈值决定着整个网格的自适应细分情况。采用这种细分策略，对在形变过程中遭受拉伸扭曲较为剧烈的区域中的三角面片进行自适应细分，可以显著地减少网格的扭曲程度，获得更好的变形效果。在三维网格质量评价背景下，通过这种自适应细分算法生成的网格质量相对更优。

3.2 改进细分算法

在对三角网格进行自适应细分时，通过比较顶点的顶点光滑度与光滑阈值的大小，可以确定细分区域。为了降低形变时间开销，提高形变速度，文中对判定为需要细分的区域进行一次细分操作，对判定为不需要细分的区域不进行细分，如果θi>θ，则表示需要对该顶点周围三角面片进行细分；如果θi≤θ，则表示不需要对该顶点周围三角面片进行细分。

改进细分算法如下

Step 1.初始状态下将形变区域中所有顶点、边、面都标记为False，表示不需要进行细分。

Step 2.计算顶点光滑度，设定光滑阈值。

Step 3.将每个顶点的顶点光滑度与初始设定的光滑阈值进行比较。

Step 3.1.若顶点光滑度大于光滑阈值，则将该顶点标记为true。

Step 3.2.若一条边上2个顶点都为True，则该边标记为True。

Step 3.3.若一个三角面片上3个顶点都为True，则该面标记为True。标记为True表示该元素需要进行细分。

Step 4.对标记为True的三角面进行Loop细分。

Step 4.1.计算每个三角网格上增加的新E-顶点的位置；更新原始三角网格顶点的位置作为新V-顶点。

Step 4.2.顺次连接新E-顶点，连接新E-顶点与新V-顶点，重新建立连接信息，并计算每个新顶点的法向量和每个新面的法向量，得到新的控制网格。

Step 4.3.将新生成的顶点、边、面标记为False，表示完成对原始三角面片的一次细分操作。

Step 5.当所有顶点、边、面都标记为False时，说明此时的细分曲面满足了细分需求，完成细分操作，生成细分曲面。

采用平均光滑度来度量自适应细分效果，平均光滑度为细分后所有顶点的顶点光滑度之和与模型顶点个数之商，其公式为

(3)

式中θi为细分后每个顶点的顶点光滑度；M为细分后模型的顶点个数。这种方法综合考虑了细分后网格顶点个数对判断细分网格质量的影响，因而可以更加合理的评价细分算法的性能。

4 实验结果及分析

4.1 实验环境及实验数据

实验基于Intel(R)Core(TM)i5-3230 M CPU 2.60 GHz处理器，Intel(R)HD Graphics 4000显卡的笔记本电脑，在Windows 7操作系统，Visual Studio 2019开发环境下，采用C++语言并利用VTK开源库，将文中改进的基于顶点光滑度的三角网格自适应细分算法应用在牙龈软组织的形变仿真上。

通过查阅国内外关于自适应细分算法研究的文献发现：近年来对三维网格构成的牙龈软组织进行自适应细分的研究较少，对于软组织方面的文献也较少且不具有代表性；许多自适应细分算法是应用在机械零件或者布料仿真邻域。布料相对机械零件来说，与软组织较为相似，都不属于刚体。因此，选择钟李涛等应用在布料上的自适应细分算法与本章改进的自适应细分算法进行对比[16]。这篇文章虽然将自适应细分算法应用在布料仿真上，但主要是为了对三维模型进行自适应细分，因此算法应该都是相通的。

将改进的细分算法(简记为文中算法)与钟李涛等采用的基于顶点权重变形度的细分算法(文献[16])分别应用在牙龈软组织形变仿真上并进行对比。为了能准确地对比仿真结果，文中选用顶点个数、面片个数、总形变时间、细分时间、细分时间占比以及平均光滑度6个指标来进行分析。实验中对牙齿施加较小的力使牙齿平移或旋转，在大量牙颌模型测试的基础上选取一口牙颌模型中下颌的3颗牙齿(磨牙、前磨牙、切牙)进行数据展示分析，下颌牙齿模型如图4所示，顶点数60 171，面片数120 338。

图4 下颌牙齿模型

4.2 数值度量结果分析

牙龈形变过程包括前期外力作用下的形变和自适应细分下的形变2个步骤，因此总形变时间包括外力作用下的形变时间和细分时间2部分。其中，前期外力作用下的形变在文献[27]中已经进行分析，主要分析自适应细分产生的形变。图5～图8为对形变区域采用不同自适应细分算法细分三角网格后，形变区域顶点个数和面片个数的对比情况。从图5、6、7、8可以看出，自适应细分增加了顶点个数以及面片个数，并且改进算法相对文献[16]算法细分后顶点个数和面片个数都较大。因此，相比未进行自适应细分的情况来说，增加自适应细分算法会使整个牙龈形变时间增加，即总形变时间增加。为了更好的对比细分算法，这里主要对比自适应细分时的网格细分时间。通过对比不同细分算法的细分效率和细分效果，对改进算法进行分析。牙龈网格的细分速度通过细分时间占比来度量，细分时间占总形变时间越小，细分速度越快，细分效率越高；牙龈网格的细分效果通过平均光滑度来度量，平均光滑度越小，细分后牙龈褶皱越少，细分效果越好。

图5 牙齿平移时细分后顶点个数对比

图6 牙齿平移时细分后面片个数对比

图7 牙齿旋转时细分后顶点个数对比

图8 牙齿旋转时细分后面片个数对比

牙齿平移牙龈曲面网格细分效率对比见表1，牙齿旋转牙龈曲面网格细分效率对比见表2，2个表中分别对比了2种算法下3类牙齿平移和旋转后的牙龈总形变时间、细分时间、细分时间占比以及平均光滑度。从表中可以看出，不论是在牙齿平移的情况下，还是在牙齿旋转的情况下，改进算法相对文献[16]算法，虽然细分后顶点个数和面片个数相对稍大，但通过空间换时间使细分时间减少了。改进算法在自适应细分过程中通过计算顶点光滑度从整体上一次性对顶点1-邻域区域光滑度进行衡量，相对文献[16]算法中通过计算基于三角面片面积的顶点权重变形度来定义高变形区、中变形区以及低变形区的方法来说，节省了自适应细分判定时间，从而提高了细分效率。从细分时间占比一列可以看出，文献[16]算法的细分时间占整个牙龈形变仿真时间平均为23.56%，而文中算法细分时间占比平均为19.44%，因此改进算法的细分效率更高，细分时间占比平均约节约了4.12%。从平均光滑度一列可以看出，不论是对牙齿进行平移还是旋转，不论是对磨牙、前磨牙还是切牙进行操作，改进算法细分后网格平均光滑度更小，网格光顺质量更好。

表1 牙齿平移牙龈曲面网格细分效率对比

表2 牙齿旋转牙龈曲面网格细分效率对比

4.3 视觉效果分析

图9、图10为对1号牙齿(磨牙)进行平移和旋转后的整体细分效果和局部细分效果；图11,图12为对2号牙齿(前磨牙)进行平移和旋转后的整体细分效果和局部细分效果；图13，图14为对3号牙齿(切牙)进行平移和旋转后的整体细分效果和局部细分效果。局部细分区域为整体细分效果图中红色实线方框所选区域；局部细分效果图中红色虚线圆框所选区域为不同算法自适应细分效果对比较为明显的区域。图中分别对比了细分前、文献[16]算法以及改进算法这3种算法下，牙齿平移或旋转后的牙龈的实体模型效果和网格模型效果。实体模型中白色部分表示牙齿，红色部分表示牙龈；网格模型中白色线条表示牙齿三角网格，红色线条表示牙龈三角网格，细分算法就是作用于这些牙龈三角网格。从图中可以看出，对3类牙齿进行平移或旋转操作时，改进算法相比文献[16]算法来说，能够很好的对牙龈形变区域三角网格进行细分，这是因为，文献[16]算法中采用三角面片面积作为权重来计算顶点权重变形度，对于面积相同且符合阈值约束的规则三角形与狭长三角形难以很好的区分，在细分区域判定过程中将实际不符合光滑度条件的狭长三角形当做与其面积相同且规则的三角形来进行处理，从而没能进行很好的细分。而改进算法中采用的顶点光滑度，是通过计算顶点1-邻域三角面片对的法向量夹角平均值来判定细分区域的，这种方法从整体上对曲面光滑度进行衡量，因而产生的细分三角网格较为规则，生成的细分曲面较为光滑。因此，改进算法能够很好的识别需要细分的区域，进而改善牙龈软组织的形变效果，使形变后牙龈表面形变区域三角网格更加接近规则的正三角形、分布更加均匀，曲面光顺质量更好。

图9 1号牙齿(磨牙)平移牙龈细分效果对比

图10 1号牙齿(磨牙)旋转牙龈细分效果对比

图11 2号牙齿(前磨牙)平移牙龈细分效果对比

图12 2号牙齿(前磨牙)旋转牙龈细分效果对比

图13 3号牙齿(切牙)平移牙龈细分效果对比

图14 3号牙齿(切牙)旋转牙龈细分效果对比

5 结 论

1)提出采用顶点光滑度作为自适应细分区域的判定准则，对虚拟牙齿矫正系统中牙齿移动后牙龈的形变区域进行自适应细分，从而使牙龈表面三角网格光顺质量更好。该算法通过比较每个顶点周围1-邻域内相邻面片对的法向量夹角平均值与光滑阈值的大小关系，来决定细分区域，对于细分区域采用Loop细分算法细分三角网格。

2)在真实扫描的牙颌三维模型数据上进行牙龈软组织形变仿真三角网格细分对比实验的结果表明，改进的自适应细分算法相对基于顶点权重变形度的细分算法来说，能够更好的识别需要细分的区域，细分时间占比平均约节约了4.12%；平均光滑度对细分效果的评价更合理，细分的三角网格更规则、分布更均匀，曲面光顺质量更好，较好地满足了软组织形变仿真中真实性与高效性的要求。

3)主要研究的是自适应细分算法中的细分区域选择问题，但在自适应细分过程中不同细分精度的网格之间可能会产生裂缝，后续还需研究牙冠和牙龈连接处协同细分处理的问题。