陈志杨　倪栋梁

(浙江工业大学计算机学院　浙江 杭州 310000)



采用图形加速的三角网格实时切分

陈志杨倪栋梁

(浙江工业大学计算机学院浙江 杭州 310000)

提出一种采用图形加速的三角网格模型实时切分的方法。针对传统的三角网格实时切分方法普遍效率不高的问题，提出利用OpenGL的拾取机制的快速、有效，将屏幕曲线映射到模型上，得到切分边缘的三角面片。并利用网格的AIF(AdjacencyandIncidenceFramework)数据结构和当前图像场景的视角矩阵优化网格模型交线生成追踪过程。然后将相交的三角面片重新三角化，构建新的拓扑结构。最后分离模型，实现模型的快速切分。实验结果表明，该方法能够快速有效地完成模型的实时切分。

屏幕曲线模型交线模型分离实时切分OpenGL追踪过程

0　引　言

随着逆向工程和扫描技术的应用[1]，三角网格模型及其处理在牙科领域有突破性的应用。能够较容易地获得口腔模型的扫描数据，但是由于很多牙科应用是针对单个牙齿的，比如补牙，故从整个口腔模型中切割出单个牙齿数据(即单齿切分)，对网格算法的实时性和可操作性就有很高的要求。本文针对牙齿模型的单齿切分，研究开发了一套快速、实时的三角网格切分算法。

对于模型切割已有学者做过研究[2-7]，陈矛等人提出了一种基于改进的MC(marchingcubes)快速切割算法；赵新方等人提出了基于拓扑关系的剖切算法。这些算法都是以“刀面模型”对目标模型进行“一刀切”。而在牙科领域，单颗牙齿的切分需要根据牙龈与牙齿的边界处的特征决定切分曲线，于是本文提出根据边界特征做一系列连续的小平面，分别与目标模型求交，得到一系列分割点，再追踪生成切分曲线。

对于三角网格的求交问题，有学者已做过研究[8-15]。周海在细分曲面造型技术研究中提出了基于三角形重心构造包围盒，然后通过包围盒检测的技术进行求交计算[12]，该方法求交效率不高，而且容易出现漏交现象；李宁等人在优化的三角网格曲面求交算法中提出了层次包围盒方法，以三角形与子包围盒是否相交为依据确定三角形所属的子包围盒[13]，该方法虽然能解决漏交问题，但是更耗费时间，而且包围盒的方法主要适用于两张三角网格曲面求交的情况；蒋钱平等人提出了基于平均单元格的快速求交算法[14]；郑军红等人提出了基于拓扑关系的交线快速生成方法[15]。

本文的研究目标是实现实时三角网格快速求交与切分算法。考虑到之前的很多网格求交算法在求交的完整性、求交效率和实时性等方面的不足，本文通过OpenGL的拾取机制实现网格求交曲线的实时绘制，并根据OpenGL的场景视角实现快速求交计算[16，17]。在实时性和求交效率方面较其他方法在求交效率等方面有较大提升。本文提出的算法主要思路分为如下几个步骤：(1) 绘制屏幕曲线；(2) 映射屏幕曲线到三角网格模型上，找到穿透三角面片；(3) 求交计算，追踪生成交线；(4) 边缘相交三角面片重新三角化；(5) 模型分离。在本方法中，利用OpenGL的拾取机制以及鼠标滑动时的场景的视角矩阵，可以有效提高穿透三角面片的检测和求交计算的效率。

1　算法描述

本文的主要算法如下：(1) 开始切分时，根据当前视角在需要切分的边界处绘制屏幕曲线；(2) 将屏幕曲线实时地映射到三角网格模型上，得到一系列连续的穿透三角面片以及各三角面片上的穿透点，这里采用OpenGL的交互式拾取机制来完成，具体操作就是对屏幕曲线上的每一个点做一次拾取操作，得到对应的穿透三角面片和穿透点；(3) 根据穿透点与对应的穿透三角面片进行求交计算，得到边界分割点；(4) 根据AIF快速搜索算法追踪这些边界分割点[18]，得到一条切分曲线；(5) 旋转视角，重复上述操作，直到得到一条闭合的切分曲线；(6) 根据闭合的切分曲线将切分曲线上的三角形重新三角化[19]，建立新的拓扑关系[20]；(7) 根据新的拓扑关系，以闭合的切分曲线为边界分离曲线两侧的三角形。

2　分割线的实时生成

考虑到单齿切分操作的便利性和实时性，本文允许采用交互式实时绘制的方法对网格进行切分。通过鼠标实时在屏幕上的运动，捕获运动轨迹并实时得到运动轨迹和网格的交线。为此，本文通过如下三个步骤来实现：(1) 鼠标拖动，绘制屏幕曲线；(2) 穿透面片检测；(3) 求交计算，交线追踪生成。

2.1基于OpenGL的穿透交点快速生成及穿透三角面片检测

通过鼠标拖动，在屏幕上获得的曲线是一系列紧密的二维离散屏幕点，需要将这些点映射到三维空间网格模型上。点的映射过程通过当前的场景视角来进行，即每一个点都有一条通过屏幕向里的射线，这条射线穿过模型中的三角面片，记录该面片及射线与该面片的交点。这样记录每一个点的映射即可找到一系列的穿透面片及对应穿透交点，这一系列的穿透三角面片即为切分曲线上的三角面片。这整个过程采用OpenGL的选择机制来实现映射过程的加速。

在本文中，通过利用OpenGL的选择机制，每个点都可以快速有效地找到映射的穿透三角面片，极大地简化并加速了在海量三角面片中的检测。对于屏幕曲线上的每个点通过OpenGL的反映射得到该点对应的近截面和远截面上的两个点，这两点之间的连线将穿过模型上的三角面片(如图1所示)，该面片即为穿透面片，并记录对应穿透交点。当模型是三维，就会出现连线穿过多个三角面片的情况，此时选取离近截面最近的穿透三角面片。

图1　穿透三角面片检测

上述过程可以为每一个屏幕点找到一个穿透三角面片，然而屏幕点的密集性必然会出现多个屏幕点映射后穿透同一个三角面片，如图2左侧图形所示。经过本文验证，每个三角面片只需保留一个穿透交点就已足够完成求交计算并保留求交曲线的特征。为方便计算，对于同一三角面片上的多个穿透点，本文选择只保留第一个穿透点，如图2右侧图所示。

图2　多点穿透同一个三角面片只保留第一个点

2.2交线的追踪生成

上述过程中得到一系列穿透三角面片及其穿透交点，根据这些信息，可以追踪生成一条交线，步骤如下：

(1) 计算每个三角面片上对应点的视角向量。在2.1节中提到过穿透面片检测时会得到远近截面上的两个点，该两点之间的向量即为视角向量：

a=(x0,y0,z0)

(1)

(2) 通过相邻两三角面片的对应穿透点之间的方向向量(如图3向量b所示)与其中一点的视角向量(如图3向量a所示)做求交平面，两三角面片之间存在一定的夹角，平面计算方法如下：

方向向量：

b=(x2-x1,y2-y1,z2-z1)

(2)

其中(x1,y1,z1)，(x2,y2,z2)为两三角面片上各自保留的穿透点。

令：

bx=x2-x1

(3)

by=y2-y1

(4)

bz=z2-z1

(5)

则计算求交平面法向量为：

c=a×b

(6)

则：

cx=x0by-y0bx

(7)

cy=z0bx-x0bz

(8)

cz=y0bz-z0by

(9)

根据法向量即可求得求交平面：

cx(x-x2)+cy(y-y2)+cz(z-z2)=0

(10)

该平面将横穿该两相邻三角面片。

图3　方向向量与视角向量做平面

(3) 将步骤(2)中根据式(1)-式(10)所求的平面与图3中两三角面片的共边求交，并记录交点。

(4) 将一系列穿透三角面片及穿透交点分别做如上步骤，即可得到一系列的分割点，如图4所示。

图4　穿透面片经求交计算得到的交点

(5) 将上述计算得到的一系列分割点按顺序依次连接，即可在模型上得到一条求交曲线，如图5所示。

图5　模型上的求交曲线

2.3穿透面片不连续处理

前文已提到过屏幕曲线只是一系列离散的屏幕点，当这些屏幕点映射到空间模型上时，很有可能会出现得到的一系列穿透三角面片并不是连续的，如图6所示。图中第四个离散点和第五个离散点中间有一个三角面片并没有被选中，图中用一个叉号标记该三角面片，该三角面片使整个穿透三角面片不连续，故将该三角面片称为“被跳跃的三角形”。

图6　穿透面片不连续

经过本文研究发现，因为鼠标移动实时绘制的屏幕曲线是一系列十分密集的屏幕离散点，一般极少出现这种跳跃的情况，而一旦出现这种情况，那么必然是屏幕曲线十分靠近“被跳跃三角形”的一个内角极小的顶点。这种情况下将该顶点作为断裂处(即不连续处)的分割点，并且对于与“被跳跃的三角形”共顶点的碰撞三角面片只保留第一个和最后一个碰撞面片。例如对于图7中第3、第4、第5和第6个穿透点对应的三角面片与“被跳跃的三角形”是共顶点的。该情况下只保留第3个和第6个穿透点的三角面片，而忽略了第4个和第5个穿透点对应的面片，并以该公共顶点作为其中一个分割点，依次连接各分割点，得到求交曲线如图7所示。图中三角面片边上的交点为求交计算得到的一系列分割点。

图7　穿透面片不连续的处理

3　基于交线的网格切分

本文基于第2节中得到的交线来进行网格模型的切分，网格切分主要分如下两个步骤：(1) 切分边缘的网格重新三角化；(2) 模型分离。

网格的重新三角化主要根据交线与三角面片的相交情况来进行，有以下几种情况：(1) 最主要的情况是交线与三角形的两个交点均在边上，该情况只要对四边形部分进行一条对角线的连接，并重新记录拓扑结构即可，如图8所示；(2) 在特殊情况下或者对特殊情况处理后可能出现一个交点与三角形某一顶点重合，另一交点在该顶点对边上，该情况三角形已分为两个三角形，不需要添加新的连线，只需重新记录拓扑结构即可，如图9所示；(3) 当两交点均在三角形顶点上时，即交线与边重合，如图10所示，此时不需要重新三角化，并保持原来的拓扑结构即可。

图8　两交点都在边上的情况

图9　一交点在顶点上的情况

图10　两交点都在顶点上 (即交线与边重合)

模型的分离主要根据上文中网格模型重新三角化时在切割边缘部分建立的新的拓扑结构及原先已存在的拓扑结构来进行。本文以切分曲线为边界，采用广度优先搜索遍历算法来分离模型，主要算法描述如下：

图11　模型分离流程图

(1) 访问切分边界上任意一侧的某一个三角形为起始三角形。

(2) 初始化一个队列为仅包含起始三角形。

(3) 当这个队列为空时，跳到(4)，否则做以下工作：

① 从队列中弹出队首元素。

② 遍历该队首元素三角形的三条边，做如下工作：

如果该边不是边界边，则对该边另一侧的三角形w做如下工作：

如果w未被访问，则：

• 访问w；

• 将w压入队列。

③ 回到(3)。

(4) 将一系列访问到的三角面片从模型中分离出来。分离算法流程如图11所示。

4　实验结果

本文在VC++环境下实现了采用图形加速的牙齿三角网格模型的切分。结合OpenGL实现了三维显示，如图12、图13所示。图12中粗黑色曲线(牙齿与牙龈的交接处)为屏幕曲线映射并求交后得到的切分曲线，其中图12(b)为切分曲线的区部放大图。根据得到的切分曲线，将与切分曲线相交的三角面片重新三角化，并根据AIF快速搜索算法在切分边缘建立新的三角网格拓扑结构。最后根据广度优先遍历算法，以切分曲线为边界，分离流程如图11所示，将需要的部分从模型中分离出来，如图13所示为两颗牙齿被切分下来后的情况，图中被切分下来的牙齿进行了适当的位移。

图12　模型三维显示

图13　沿交线切分后的模型

5　结　语

本文提出的方法通过利用OpenGL的拾取机制和场景视角，简化并加速了切分边缘三角面片的检测，实现了鼠标拖动过程中对三角网格模型的实时切分，有了更好的交互性，相比于其他方法提高了切分效率。

[1]LesPiegl.OnNURBS:ASurvey[J].IEEEComputerGraphics&Applications，1991,11(1):55-71.

[2] 陈矛,唐泽圣,唐龙.三维表面模型的快速切割算法[J].软件学报,1998,9(9):661-664.

[3] 赵新方,周建中,李衷怡，等.三角网格剖切算法的研究[D].武汉:华中科技大学研究生院,1999.

[4] 花卫华,邓伟萍,刘修国，等.一种改进的不规则三角网格曲面切割算法[J].中国地质大学报,2006,31(5):619-623.

[5] 刘青,姚莉秀.一种基于三角网格结构的医学虚拟切割算法[J].微型电脑应用,2011，27(1): 50-54.

[6]BruynsC,SengerS,MenonA,etal.ASurveyofInteractiveMeshCuttingTechniquesandANewMethodforImplementingGeneralizedInteractiveMeshCuttingUsingVirtualTools[J].JournalofVisualizationandComputerAnimation，2002，13(1)：21-42.

[7]SotirisB,DieterP,TheodoridisY.RevisitingR-treeconstructionprinciples[C]//Proceedingsofthe6thEastEuropeanConferenceonAdvancesinDatabasesandInformationSystems,2002: 149-162.

[8]AhmedHElsheikh,MustafaElsheikh.Areliabletriangularmeshintersectionalgorithmanditsapplicationingeologicalmodeling[J].EngineeringwithComputers, 2014,30(1):143-157.

[9]DavidMcLaurin,DavidMarcum,MikeRemotigue,etal.Repairingunstructuredtriangularmeshintersections[J].InternationalJournalofNumericalMethodsinEngineering, 2013,93(10):266-275.

[10] 肖于,白润才.基于包围盒与空间分解互辅的三角网相交检测方法[C]//2011InternationalConferenceonInformation,ServicesandManagementEngineering(ISME),2011:1500-1503.

[11] 孙殿柱,孙永伟,田中朝,等.三角网格曲面模型快速求交算法[J].北京工业大学学报,2012,38(8):1121-1124.

[12] 周海.细分曲面造型技术研究[D].南京:南京航空航天大学研究生院,2004.

[13] 李宁,田震,张立华,等.优化的三角网格曲面求交算法[J].辽宁工程技术大学学报,2013,32(9): 1269-1273.

[14] 蒋钱平,唐平,袁春风.基于平均单元格的三角网格曲面快速求交算法[J].计算机工程,2008,34(21): 172-174.

[15] 郑军红,陈志杨,叶修梓.基于拓扑关系的交线快速生成方法[J].计算机集成制造系统,2003,9(12):1145-1149.

[16] 李一凡.基于OpenGL的三维建模系统[J].科教导刊，2014,1(1):139-140.

[17] 王新波,朱维杰.基于OpenGL与3DSMax的三维场景建模[J].电子科技,2012,25(1):103-104.

[18] 黄浩,杨杰.基于AIF的三角网格切割方法[J].上海交通大学学报,2008,42(4):564-568.

[19] 秦衡峰,王艺.任意平面/曲面域上的高质量三角化网格生成[D].湘潭大学,2012.

[20] 田中朝,孙殿柱.三角网格曲面重建及求交理论、方法研究[D].山东理工大学,2008.

TRIANGULARMESHREAL-TIMECUTTINGUSINGGRAPHICSACCELERATION

ChenZhiyangNiDongliang

(Shool of Computer Science,Zhejiang University of Technology,Hangzhou 310000, Zhejiang, China)

Thepaperproposesamethodwhichusesgraphicsaccelerationtocuttriangularmeshinreal-time.Fortheproblemofgenerallyinefficientintraditionaltriangularmeshreal-timecuttingmethod,weproposetousethepicking-upmechanicsinOpenGLtomapthescreencurveontomodelfastandeffectively,andthroughtheuseofAIF(adjacencyandincidenceframework)datastructureandtheperspectivematrixofcurrentimagescenetooptimisethetrackingprocessofthegenerationofmeshmodelintersectinglines.Thenwere-triangulatetheintersectingtriangularfacets,andconstructthenewtopologystructure.Finally,wesplitthemodelandimplementthefastcuttingofmodel.Experimentalresultsshowthatthismethodcanaccomplishreal-timetriangularmeshmodelcuttingfastandeffectively.

ScreencurveModelintersectinglinesModelsplittingReal-timecuttingOpenGLTrackingprocess

2014-08-13。浙江省自然科学基金项目(Y1090597)。陈志杨，教授，主研领域：CAD，CAGD，几何造型。倪栋梁，硕士生。

TP391

ADOI:10.3969/j.issn.1000-386x.2016.03.037