基于空间多边形三角剖分的曲面分割求交算法

史永丰，张育浩，程 婷，徐保文，林岗山

基于空间多边形三角剖分的曲面分割求交算法

史永丰，张育浩，程 婷，徐保文，林岗山

(金航数码科技有限责任公司，北京 100028)

针对传统曲面分割求交方法存在的平面片的选取、遗漏部分交线段以及交线间断的问题，提出一种基于空间多边形三角剖分的曲面分割求交算法。以等深度分割方法为基础，避免了交线不连续的问题，当分割达到一定层次时以空间多边形近似曲面片，并对空间多边形进行三角剖分，以三角形对的交线近似空间多边形之间的交线，进而以空间多边形的交线近似曲面片的交线，最终得到相交曲面之间的交线。利用曲面片轮廓构造出的空间多边形更加接近曲面片的真实形状，提高了逼近精度，同时对空间多边形进行三角剖分，提高了求交精度，进而降低了丢失交线的可能性。实验验证了该算法比传统的分割法更加精确。

分割法；空间多边形；三角剖分

曲面求交是CAD/CAM和计算机图形学中关键技术点之一，是曲面裁剪、曲面过渡、曲面拼接等技术基础。曲面求交算法常用的有5种：代数法[1-2]、分割法[2-3]、离散法[4-5]、迭代法[2,6]和跟踪法[7-8]。作为其中的一种，曲面分割求交算法是先通过2张曲面片的凸包判断其是否相交，若相交将2张曲面片分别分割成4张小曲面片，再继续利用凸包来做相交判断，直到小曲面片在指定规范下逼近平面的小曲面片。经过如此分割，形成了一列有交近似于平面的小曲面片对。求交过程中，先用平面片逼近小曲面片，然后计算相交平面片之间的交线，并通过平面片之间的交线近似曲面片对的交线。最后把交线段顺序连起来，形成整个曲面片的交线。整个过程的核心思想是曲面细分，用平面代替曲面，将曲面求交转化为平面求交问题。该方法适用性广，计算速度快，算法简单且容易实现。但存在平面片的选取、遗漏部分交线段以及交线间断等不足[3]。

本文以等深度分割算法为基础，借助空间多边形来近似曲面片，提出一种基于空间多边形三角剖分的曲面分割求交算法，其基本思想组成如下：

(1) 确定分割层数，对2张曲面进行分割；

(2)利用曲面凸包，快速检测小曲面片是否相交，舍弃凸包不相交的曲面片；

(3)当分割到一定层次时，利用空间多边形近似曲面片；

(4) 对空间多边形进行三角剖分；

(5)利用三角形对求交算法求出交线段，并利用拓扑关系将求得的交线段首尾连接，形成曲面交线。

1 曲面求交的分割法

1.1 传统曲面分割求交的原理

曲面分割求交的基本原理是：通过曲面凸包快速检测曲面是否相交。如果两者不相交，则根据曲面凸包性质可知，2张曲面不会相交。如果两者相交(2张曲面可能相交)，则运用分割技术分别将 2张曲面一分为四，然后对分割得到的子曲面片重复上述相交检测过程，并抛弃凸包不相交的子曲面片。当分割达到一定层次(等深度分割)或者曲面片在给定精度下已近似平坦(自适应分割)时，就利用平面片(四边形或2个三角形)近似表示曲面片，然后用平面片的交线近似代替曲面片间的交线。最后将分段求得的交线段按照拓扑关系首尾相连，得到整条交线。

1.2 分割求交方法的关键点

对比其他求交方法，分割法的思想简明，效果也比较好，因而获得了广泛的应用。但应注意如下关键点：

(1) 曲面的选取。由于Bézier曲面具有良好分割性质，在处理NURBS曲面求交时，应该将NURBS曲面转化为有理Bézier曲面片，然后再进行求交。

(2) 平面片的选取[3]。等深度分割方法中，当分割达到一定层次时，由于未对子曲面片的平坦度进行判断，故曲面片可能并未达到近似平面片的界值，直接用平面片去代替曲面片会带来逼近误差。通常用曲面片凸包的厚度(取为长度最小的棱长)除以凸包底面(与厚度相对应的面)的面积得到平坦度。

在分割求交方法中，即便曲面片已足够平坦，但其边界曲线的弯曲程度可能很高，由曲面片4个角点构造的平面片采用直线段来近似曲面边界必会带来很大的逼近误差，导致求交的不精确。

(3) 遗漏部分交线段[3]。如图1所示，，点分别为曲线段()与()的交点，直线段1P和1Q为曲线段在给定精度下的近似。由于直线段1P和1Q不相交，曲线()与()之间的交点丢失了。以此类推，得知曲面之间的交线也会出现遗漏。

图1 曲线交点丢失现象

精度设置的不合理是造成交点丢失现象的主要原因。如图2所示，假如再将2条曲线段分割一次，可得到近似交点ʹ，ʹ。由此可知，适当提高逼近精度可以改善交点丢失的现象。推广可得精度的提高也可以改善曲面求交中交线段遗漏的现象。

图2 曲线进一步分割及曲线交点

(4) 交线间断[3]。由于同一曲面上相接2张曲面片被分割的次数不同，常常会导致交线间断。

2 基于空间多边形三角剖分的曲面分割求交算法

基于空间多边形三角剖分的曲面分割求交的基本原理是：以等深度分割方法为基础，当达到一定分割层次时，即用空间多边形近似表示曲面片，通过对空间多边形进行三角剖分，并以三角形面片的交线近似表示空间多边形间的交线，进一步以空间多边形间的交线近似表示曲面片间的交线。最后将分段求得的交线段按照拓扑关系首尾相连，以获得整条交线。

2.1 算法步骤

输入：2张曲面片。

输出：2条曲面片交线。

步骤1.确定曲面分割的最大层次(通常取为3~4)，初始化交线表。

步骤2.求解2张曲面片的凸包，然后判断2个凸包是否相交，无交则转步骤8，否则转步骤3。

步骤3.若分割层次小于，继续对曲面片进行四叉分割，使每张曲面片都被分为4块。对一张曲面片的每一子曲面片，均将其与另一张曲面片的4个子曲面片求交，即调用步骤2。

步骤4.若分割层次等于，则顺序连接曲面片4条边界的控制顶点，形成空间多边形，以该空间多边形代替原曲面片边界。

步骤5.执行空间多边形的Delaunay三角剖分算法。

步骤6.对一张曲面片的每一个三角形，都分别与另一张曲面片的三角形求交[9-10]。

步骤7.将步骤6中求得的交线顺序连接，检查所得交线与交线表中原有交线是否相连，即检查所得交线的首尾与原交线的首尾是否相连。若相连，则将所得交线连入原有交线; 若不相连，则生成新交线。

步骤8.返回。

2.2 空间多边形的Delaunay三角剖分

简单多边形三角剖分的定义是：将简单多边形分解为一系列三角形，其不相交，且没有不属于原简单多边形的顶点。简单多边形的Delaunay三角剖分以简单多边形的三角剖分为基础，同时其内边都是局部优化的，且分割得到的三角形具有最小内角最大、平均形态比最大的性质[11]。

空间多边形的Delaunay三角剖分算法步骤如下：

输入：空间多边形。

输出：三角剖分后的空间多边形。

步骤1.计算空间多边形点集的最小二乘平面，即距离这些点最近的平面。并将点集投影至最小二乘平面，连接点集，形成平面多边形。

步骤2.按逆时针方向顺序读入平面多边形的顶点，建立链表，并计算出每个结点的凹凸性。

步骤3.取每个凸结点，将点与其相邻2个结点构成的三角形，记为Δ。假如Δ不包含多边形上其他顶点，则计算该三角形的权值(三角形的权值定义为三角形3个内角的最小值)。从所有凸结点构成的三角形中取出权值最大的三角形，记为Δ，把Δ的顶点序号保存到数据结构表中，并从链表中删除中间结点。

步骤4.若链表中的结点个数大于3，则转步骤3；否则转步骤5。

步骤5.由链表中最后3个结点所对应的多边形顶点构成一个三角形，删除链表中最后3个结点。

步骤6.根据Delaunay 准则，通过局部变换，得到平面多边形的Delaunay三角剖分。

步骤7.将剖分结果映射回三维空间，即可完成空间多边形的三角剖分[12]，也即曲面片的三角分割。

2.3 算法分析

本文算法的创新点在于利用空间多边形取代了传统分割方法中的平面片，并对空间多边形进行了三角剖分，提高了逼近精度，故求交精度也相应提高。具体表现为：

(1) 空间多边形的选取。当用平面片近似曲面片时，难以改善曲面片平坦度未达到界值带来的逼近误差，而由曲面片轮廓构造出的空间多边形相对平面片来说更接近曲面片的形状，一定程度上可以降低曲面片的逼近误差，提高了求交精度。

当用平面片近似曲面片时，未考虑到曲面片边界曲线的弯曲带来的近似误差，而本文算法中的空间多边形正是以曲面片的轮廓为基础构造出的，故有效地避免了曲面片边界曲线带来的误差。

相比平面片，空间多边形更能精确表示曲面片的形状，故求交精度更高。

(2) 改善了遗漏交线段的情况。由2.1节分析可知，利用空间多边形近似曲面片提高了算法的逼近精度。本文算法用空间多边形近似曲面片之后，又对空间多边形进行了三角剖分，即对空间多边形进行了细化，故逼近精度得到了提高。

无论是利用空间多边形近似曲面片还是对空间多边形进行三角剖分均提高了算法的精度，精度的提高也改善了丢失交线的现象。

基于空间多边形三角剖分的曲面分割求交算法，不仅考虑了等深度分割方法在交线连接上的优势，同时兼顾了自适应分割方法在曲面平坦度分析上的优势，并且考虑到了曲面片边界的弯曲程度，通过三角剖分提高了逼近精度，有效避免了交线丢失的现象。理论上，基于空间多边形三角剖分的曲面分割求交算法比传统的曲面分割求交算法得出的交点更加精确。本文将进一步通过数值实验验证这一结论。

3 数值试验

3.1 实例

图3为2个3×3的Bézier曲面，红色的点表示Bézier曲面的控制顶点，分别利用曲面分割求交算法与基于空间多边形三角剖分的曲面分割算法对3个曲面进行求交运算。

(a) 传统曲面分割求交算法

(b) 基于空间多边形三角剖分的曲面分割求交算法

图3 2张Bézier曲面

由于曲面分割求交算法与基于空间多边形三角剖分的曲面分割算法在对曲面进行分割以及判断是否相交的方法上是相同的，故只需通过比较分割后的子曲面片的交线是否准确就可判断2种算法的优良。为了便于观察，假设分割2次后得到的其中3个子曲面片已较为平缓(图4)。

图4 2个Bézier子曲面片

分别利用曲面分割求交算法与基于空间多边形三角剖分的曲面分割算法对2个子曲面片进行求交计算，结果如图5和图6所示。其中蓝色的线框表示用于近似曲面片的三角形组，可以看出本文算法得到的线框要比传统的分割算法得到的线框更接近曲面的真实形状，与预期相符。黄色和绿色的线条分别表示2种算法最终求得的交线。在该实例中，2种算法求得的交点见表1和表2中的交点坐标列。

图5 分割求交算法

图6 基于空间多边形三角剖分的分割求交算法

表1 传统的分割算法 交点坐标交点投影之间的距离 (1.1039, 0.0567, 0.3)0.058 8 (1.0472, 0.2821, 0.3)0.232 6 (0.6752, 1.5708, 0.3)0.109 1

表2 基于空间多边形三角剖分的分割算法 交点坐标交点投影之间的距离 (1.3032, 0, 0.3)0.037 3 (1.0113, 1.0113, 0.3)0.039 9 (0.8497, 1.5708, 0.3)0.037 7

3.2 结果分析

将2种算法的求交结果置于一图之中进行比较。图7中黄色线条表示曲面分割求交算法的结果，绿色线条表示基于空间多边形三角剖分的曲面分割求交算法的结果。

通过观察可知，传统的曲面分割求交算法丢失了交线，且求得的交点比本文算法求得的交点距离与真实交点的距离更远，故基于空间多边形三角剖分的曲面分割求交算法要优于传统的曲面分割求交算法。

(a) 2种算法的求交结果对比(一)

(b) 2种算法的求交结果对比(二)

图7 2种算法的求交结果对比

下面通过数值比较2种算法的求交结果。将交点依次投影到2张相交曲面上，计算2个投影点之间的距离。可知，距离越小，则交点的准确度越高。

情况 3.2.1 C1中的集合都是Y中顶点色集合,4,5,6中至少有2种色同时包含在每个C(ui)中,不妨设4,C(ui), i=1,2,…,10,则C2中的集合都不是X中顶点色集合,且至多有3个不是Y中顶点色集合。

依次将所求交点投影到2张曲面，并计算投影点之间的距离。由表1和表2可以看出，本文算法求得的交点投影点之间的最大距离均小于传统分割求交算法求得的交点投影点之间的最小距离，并且在本例中传统的曲面分割求交算法出现了丢失交线的现象，故得出：本文算法要优于传统的曲面分割求交算法。

还有一次，另一位轻功很厉害的刘歆师兄，直接就趁老师睡着，将墨涂到他脸上去了，老夫子醒来，摸了一手的墨，看着手上反印的纹路，也很赞，说：“这些横还是有一些生气的，并不是死蚯蚓。”

注意：

(1) 传统的分割算法用于曲面1，3相交时，出现了交线丢失，故不存在传统的分割算法用于曲面1，3相交时的交点表。

(2) 本例中曲面2，3不相交，故不存在算法用于曲面2，3相交时的交点表。

(2)全年电力、热力延时曲线。根据该医院提供的热力系统、变配电系统的运行记录的数据，得到医院的热力延时曲线和电力延时曲线如图6所示。

(3) 由于在图7中加入曲面1，2，3的标记很容易影响图片的直观，且曲面1，2，3可以很清楚地从图中分辨出，故这里不在图7中进行标注。

通过表1和表2数值比较，可得出理论与观察相同的结论：基于空间多边形三角剖分的曲面分割求交算法比传统的曲面分割求交算法得出的交点更加精确。

4 结语与讨论

针对传统曲面分割求交算法中存在的平面片的选取、遗漏部分交线段以及交线间断问题，本文提出了基于空间多边形三角剖分的曲面分割求交算法.该算法不仅能够找到曲面的交线，同时得到的交点要比传统的分割求交算法更加精确，可以预见将本文算法所求交点作为初始点用于迭代法求交，将会提高求交速度、求交精度，并且能有效避免迭代不收敛现象。本文算法适用于带有控制点的曲面求交，特别是Bézier、NURBS曲面。本文算法不适用于数据量庞大、且一般没有用数学形式表示的曲面求交。如何对未有控制点的曲面进行求交，是下一步研究重点。

参考文献

[1] RATT M J, GEISOE A D. Surface/Surface intersection problems [EB/OL]. [2018-06-20]. https://www. researchgate.net/publication/247684327_SurfaceSurface_Intersection_Problems.

[2] 朱永强, 鲁聪达. 自由曲线曲面造型技术的综述[J]. 中国制造业信息化, 2003, 32(5): 110-113.

[3] 李新友. 曲面分割求交方法的实现[J]. 计算机辅助设计与图形学学报, 1989(1): 46-50.

[4] 陈振, 汤军, 廖环宇, 等. 基于曲面方程的三角形网格模型求交方法[J]. 测绘与空间地理信息, 2016, 39(3): 62-64.

[5] 张华, 叶显高, 李德群. 基于网格划分的曲面求交算法[J]. 计算机应用, 1994(6): 54-55.

[6] BARTH, W, LIEGER R, SCHINDLER M. Ray tracing general parametric surfaces using interval arithmetic [J]. The Visual. Computer, 1994, 10(7): 363-371.

[7] 许晓革, 冀阳峰, 杨蕾. 曲面离散跟踪求交算法的研究[J]. 工程图学学报, 2005, 26(1): 61-64.

[8] 黄金贵, 康宝生. 任意曲面间跟踪求交的有效算法[J]. 计算机辅助设计与图形学学报, 1998, 10(6): 499-505.

[9] 罗文龙, 熊高君, 李世吉. 基于二次划分的大规模三角网曲面求交分割法[J]. 物探化探计算技术, 2013, 35(3): 355-359.

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

[11] 马小虎, 潘志庚, 石教英. 基于凹凸顶点判定的简单多边形Delaunay三角剖分[J]. 计算机辅助设计与图形学学报, 1999, 11(1): 1-3.

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

Surface Segmentation Algorithm Based on Spatial Polygon Triangulation

SHI Yong-feng, ZHANG Yu-hao, CHENG Ting, XU Bao-wen, LIN Gang-shan

(Jinhang Digital Technology Co. Ltd., Beijing 100028, China)

Abstract: The problems with the traditional surface segmentation intersection lie in the choice of plane, loss of intersection line and discontinuous intersection line. In view of these problems, this paper proposes a surface segmentation intersection algorithm based on spatial polygon triangulation. The algorithm based on equal depth segmentation avoids the problem of discontinuous intersection line. When the segmentation reaches a certain level, the spatial polygon is used to approximate the surface patch, and the spatial polygon is triangulated. The intersection of the triangular pair is similar to the intersection between the spatial polygons, then the intersection of the spatial polygons is approximated to the intersection of the patches. Finally we get intersection lines between the intersection surfaces. The spatial polygons constructed by the contours of the surface patch are closer to the true shape of the patch, and the approximation accuracy is improved. The triangulation of the spatial polygons improves the accuracy of the intersection, thus reducing the possibility of losing the intersection line. In theory, this algorithm is more accurate than the traditional segmentation method, and the experiment also verifies this conclusion.

Keywords: segmentation method; spatial polygon; triangulation

中图分类号：TP 391.41

DOI：10.11996/JG.j.2095-302X.2019030447

文献标识码：A

文章编号：2095-302X(2019)03-0447-05

收稿日期：2018-08-30；

定稿日期：2018-09-11

第一作者：史永丰(1980-)，男，湖南郴州人，高级工程师，硕士。主要研究方向为CAD、计算机图形学。E-mail：shiyf@avic-digital.com

通信作者：程 婷(1988-)，女，山西晋中人，工程师，博士。主要研究方向为CAGD、CAD、计算机图形学。E-mail：chengt@avic-digital.com