一种基于顶点移动的三角面模型虚拟切割算法于素平，王钰（青岛大学信息工程学院，山东青岛266071）问题，提出了一种基于顶点移动的算法。该算法通过切割轨迹生成、顶点移动以及网格重构等来实现。与传统算法相比，对面数近万的模型，顶点移动算法6次切割运行效率大约提高21%；对面数40余万的复杂模型，运行效率大约提高6%；生成的新面片较为均匀且无畸形。
随着计算机辅助设计及虚拟仿真技术的发展，对三角面模型进行的一些虚拟操作在计算机中进行真实感模拟成为一个现实的课题。目前常用的切割算法主要是传统的切割交点保存方法，王卫红等提出的三角网格剖切算法，能够将三角网格的拓扑信息保存，但是容易生成畸形三角面片而不利于后续重复切割操作；李衷怡等提出的平面剖切算法，能够利用已知的平面方程删除部分模型，但无法对切割模型进行分离操作；刘奇等提出的三点成面确定切割路径的方法，会由于在二维坐标转换为三维坐标时产生的误差而无法精确定位切割路径。关于切割交点的确定方法，很多都有介绍，但并不全面，如对三角形面片中有一条边正好落在切割平面上这种情况就没有给出很好的解释。针对以上算法存在的不足，本文提出了一种基于顶点移动的方法进行虚拟切割的算法，并与传统算法进行了比较。结果显示，顶点移动算法不仅很好地解决了畸形面片的问题，而且大大提高了运行效率。
1基于顶点移动的虚拟切割算法1.1算法思想顶点移动算法的思想是：切割过程中，计算出面面相交的交点；计算交点与相邻点的距离，以判断需要做出移动的顶点位置；呆持索引值不变，更改相应的坐标点值。这种算法，通过以移动顶点代替新生成的交点，可减少新顶点的产生，从而避免生成畸形三角面片。
是利用移动顶点算法所做的二维平面效果图，可以看到，利用移动顶点算法，切割前后面片数保持不变。由于是分离操作，需要将交点处的顶点重复保存两遍。
1.2算法实现1.2.1切割路径交互生成切割路径即面面相交所求出的交点按照顺序（或逆序）排列而形成的路径。设平面方程为1研究生fa主要研究方向I为虚拟现实与仿真技术三角面片由3个顶点连结而成，因此，求面面相交即可转化为求点面相交。
首先，需针对切割面可能出现的各种情况进行相交测试，以判断切割平面是否与三角面模型相交。如果不相交，表明无需完成切割运算；若相交，则根据平面方程求解面面相交的交点坐标，然后按一定顺序将其保存。两种情况，其算法步骤是不相同的。
设i为控制面片循环次数为控制面片中点数循环的次数；um为面片计数器；flag为判断面片中每条边是否面线相交的标志位；F为判断每个面片是否面面相交的标志位。算法步骤如下：切割平面与三角面模型不相交如果j〈第i个面片中的点数，则j+ 1，转向2，否则转5；如果i小于三角面模型中的面片数，则i=i+ 1，转向2否则转7；如果num等于面片总数，则跳出循环，结束切割操作，否则进行切割平面与三角面模型相交的运算过程。
切割平面与三角面模型相交遍历面模型中每个三角面片的每一条边，设该边的两个顶点分别为P1，P2，法向量向右，令D1若要保留右边模型，则其判断是否保存顶点和交点坐标值的准则为：如果D1>0且D2>0，则保存顶点P2坐标值；如果DO 0且D2〈0，则保存交点坐标值；如果D1 若要保留左边模型，则其判断是否保存顶点和交点坐标值的准则为：如果D10且D2〈0，则保存交点坐标值；如果D1〈0且Dx>0，则保存顶点P1坐标值和交点坐标值（与要保留右边模型时的保存顺序正好相反）如果D1需要注意的是：要获得切割路径，在保存交点坐标值之前，要进行重复性判断。只有当该交点与先前保存的交点坐标值不同时，才需要将其保存；对重复的交点只需要记录索引值即可。 1.2.2移动顶点求出交点值是为移动顶点做基础，只有获得交点的位置后，顶点坐标的移动才准确。顶点的移动遵守就近原则，即根据求出的交点坐标位置，判断与交点相邻的两个顶点到该交点的距离大小，将距离交点较小的顶点移动到交点位置处。 在移动顶点时，若两交点的位置距离三角形某一顶点非常接近，且顶点到两个交点的距离大小相等，则将其移动到交点所在边的边距较大的交点处，另一个交点也移动到该处，如a所示；若两交点分别位于该边的中点处，则将除两边公共顶点之外的两个顶点移动到相应的交点位置上，如b所示。 经过顶点移动，不会再出现狭长三角形或与原模型中的三角形不同数量级的小三角形，有利于网格再次切割操作。 1.2.3网格重构经过切割路径的生成及顶点移动，所得到的切割后的面片将全部是三角形结构，无需对其再进行三角化处理，按照顺时针或逆时针方向将各个面片的顶点信息排列保存即可。如果要做切割删除操作，只需要保存部分模型点和面片信息；如果要做切割分离操作，则将切割路径处的点信息保存两次即可。 2顶点移动算法与传统算法比较在VC平台上结合OpenGL图形库，通过程序从切割后的效果演示和运行效率两个方面对传统算法和顶点移动算法进行比较和分析。 2.1切割效果比较切割操作实际上是求解面面相交的过程。传统算法是要求出相交的交点，但由于算法的局限性，使之会产生各种畸形三角形，见所示。这些畸形三角形，有的是三角形有一个角的角度非常小（a）有的是切割后生成的三角形与原三角形不是一个数量级（b）还有的是为了保证算法的封闭性和完整性，切割后要对生成的四边形进行三角化处理，当对狭长四边形三角化后所形成的狭长三角形（c）。畸形三角形的出现，会给重复切割带来很大误差。使用顶点移动算法，只生成少量新顶点，切割顶点大部分依靠移动原顶点完成，生成三角面片较为均匀，不易生成畸形面片。 所示为一切割模型与切割平面，分别使用传统算法和顶点移动算法进行切割，其效果图见所示。从图中可以看到，使用传统算法，生成新的切割交点，并产生畸形三角面片，三角面片大小差距也较大；使用移动顶点算法，没有新交点生成，生成的面片也较为均匀。 2.2切割效率比较对所示的医学图像三维重建后生成的点数为2 498、面数为9992的下颂骨模型，分别用顶点移动算法和传统算法进行切割。由于模型是非均匀的，所以切割算法的时间与切割次数不成任何比例关系。共切割6次，其每一次切割运行的时间及切割后的点数见表1所示。从表中可以看出，随着切割次数的递增，相比传统算法，顶点移动法时间提高率越来越大。结果说明：随着切割次数增加，顶点移动算法运行效率越来越高。完成6次切割，其运行效率相比传统算法提高21%传统算法之所以每次切割运行时间较长，是因为每完成一次切割要铺笕切割路径上的交从而耗费了大量的时间。d.表1对同一模型两种算法每次切割运行时间及切割后点数切割次数传统算法顶点移动法运行时间/ms切割后的点数/个运行时间/ms切割后的点数/个运行时间减少率/改变模型的点数和面数，并用顶点移动法及传统算法进行切割，其**次切割所运行的时间见表2所示。由表中数据可知，对于较小的面模型，两种算法的运行时间相差不大；但随着模型点数和面数的增加，顶点移动算法的优势逐渐突出，对面数40余万的复杂模型，其运行效率提高近6%.表2对不同的模型两种算法切割运行时间模型传统算法运行时间/ms顶点移动算法点数/个面数/面运行时间/ms运行时间减少率/ 3顶点移动算法的应用为进一步验证顶点移动算法的应用效果，对所示的下颂骨模型根据其定位的切割路径进行了纵向、横向及多次切割，其切割后分离效果图见所示。a为对点数为110 085，面数为440196的颞骨模型，对其进行虚拟切割，其切割后分离效果图见b，c所示。从图中可以看出，利用顶点移动算法对复杂模型切割后，面片均匀，效果很好。 a侧面图b垂直方向图c正面图下颌骨模型及切割定位a纵向切割b多次切割c横向切割顶点移动法切割后分离效果图b分离后网格效果图c分离后面模型效果图颞骨模型切割分离效果结语虚拟切割的准确性及运行效率是衡量算法优劣的重要标准。本文针对传统切割算法的不足之处，提出了顶点移动算法，有效的解决了传统算法中关于产生畸形面片导致重复切割误差增大、顶点数量的增加加剧存储负担以及切割面片的精确定位等问题，并结合医学图像三维重建模型进行了全面而详实的实例验证，从不同的角度比较了传统算法与本文提出的算法，给出了比较结果和示意图表。实验证明，顶点移动法具有较好的仿真效果，且运行效率较高。本文算法可在计算机辅助外科、刚性模型切割仿真以及虚拟加工方面有一定的应用。
