软件学报
JOURNAL OF SOFTWARE
1999年　第10卷　第11期　Vol.10　No.11　1999



复合三角Bzier曲面求交和裁剪的实现
李际军　柯映林 程耀东
　　摘要　该文利用三角Bzier曲面片的可分割性,解决了迭代收敛、初始交点计算等问题;通过近曲面点、边界点跨越等过程,实现了由一个初始交点将跨越许多曲面片的整条交线跟踪出来的设想.将各交点作为型值点插入曲面中,对三角网格进行三角再划分,以交线为界进行三角网格和型值点的分离,最后重新生成两张复合曲面,实现了裁剪的目的.测试结果显示,此方法简单、可靠,能够满足曲面造型的要求.
　　关键词　复合三角Bzier曲面,三角Bzier曲面片,三角网格,跟踪.
　　中图法分类号　TP391
Procedure of Intersection and Trimming for Composite Triangular Bzier Surface
LI Ji-jun KE Ying-lin CHENG Yao-dong
(Department of Mechanical Engineering Zhejiang University Hangzhou 310027)
　　Abstract　 Using the splitting property of tringular Bzier patch, the problems of iterating and initial intersection point calculating can be solved. By the procedures of near surface point iterating and border points traversing, the whole intersection curve traversing many patches can be traced from one initial intersection point. Inserting intersection points as measure points into surface, retriangulating grids, splitting triangular grids and measure points along intersection curve, the original surface can be trimmed into two composite triangular Bzier surfaces. The experimental results show that this method is simple, robust and applicable for surface modeling.
　　Key words　Composite triangular Bzier surface, triangular Bzier patch, triangular grid, marching.
　　随着自由曲面在几何造型、CAD/CAM等领域中的广泛应用,针对自由曲面的几何处理,如曲面求交、曲面裁剪等成为计算几何中的热门研究课题,并作为完成复杂产品造型及产生数控加工数据的基本手段和衡量曲面造型系统设计能力的主要指标而倍受重视.其中作为曲面裁剪、曲面过渡等基础的曲面求交是最基本和最重要的问题之一.
　　Farin［1］对三角Bzier曲面片做过详细的研究,给出了构造C′连续的复合三角Bzier曲面的条件;Choi［2］系统地介绍了由离散型值点建立G′连续的复合三角Bzier曲面的过程;柯映林［3］在其博士论文中提出了一种准C′连续的复合三角Bézier曲面插值模型.这些方法都成功地解决了离散型值点的三角Bzier曲面插值问题.通过上述方法建立的复合Bzier曲面有一个共同的特点:每张三角Bzier曲面片有一个三角域相对应,整张曲面却没有相对应的参数域.如何对没有单一相对应参数域的复合三角Bzier曲面进行求交是我们在本文中要解决的问题.在此,我们吸收矩形域曲面求交的经验,充分利用和考虑到复合三角Bzier曲面的特点,提出了一种有效的解决方法.由于跟踪法［4,5］的优点就是已知一个交点,通过沿跟踪方向前进一个步长求下一个交点,从而跟踪出整条交线.那么,如何求出每条交线上的一个初始交点就成为求交的关键,在此,我们利用三角Bzier曲面片的分割原理和迭代求精的方法,较好地解决了这个问题.通过引进求近曲面点和边界点的概念,成功地完成了交线由一个曲面片到另一个曲面片的跨越和继续跟踪的过程.这种方法不仅可以解决两张复合三角Bzier曲面有一条交线的问题,也能够解决交线环和多个交线分支的情况.
　　在工程中,许多产品的外表面不能或不便于用完整的曲面来表示,用多张曲面拼接又满足不了造型上的要求或过于困难,因此,往往采用曲面裁剪的处理方法得到所需要的曲面.在曲面裁剪过程中,先将整张曲面在参数域［0,1］［0,1］内映射,然后在形成的曲面裁剪参数域上重组曲面的拓扑关系,建立裁剪曲面的内环和外环［6,7］,其中建立曲面参数域与裁剪参数域间的映射是曲面裁剪算法的关键,这是具有单一的相对应参数域曲面的一般裁剪方法.但是,对于无对应参数域的复合三角Bzier曲面而言,无法建立这种映射关系,自然也就无法采用这种裁剪方法.我们针对这一特点,通过将交点作为型值点插入到曲面的型值点集中,由交点的数据结构找到该交点所在的三角网格［2,3］,将该三角网格重新三角化,并以交线为界进行型值点和三角网格的分离,重新建立拓扑信息,形成与原曲面结构相一致的曲面,较好地解决了上面提到的问题.
1 复合三角Bzier曲面的跟踪求交
1.1 三角Bzier曲面片的分割原理
　　设Pi(i=1,2,3)是ΔT1T2T3内的3个点,Pi关于ΔT1T2T3的面积坐标为(ui,vi,wi)(i=1,2,3),设想ΔT1T2T3上已有一张三角Bzier曲面片(以图1所示的三次三角Bzier曲面片为例),但我们仅对ΔP1P2P3上的部分有兴趣,并希望它表示为ΔP1P2P3上的三角Bzier曲面片(如图2所示).

图1 三角Bzier曲面片

图2 三角Bzier曲面片分割示例
　　设P∈ΔT1T2T3,且P∈ΔP1P2P3,P关于ΔT1T2T3的面积坐标为(u,v,w),关于ΔP1P2P3的面积坐标为,则

上式即为以“老”用“新” 表示的同一点的坐标变换式,这样,我们有

其中,新的控制顶点i,j,k(i+j+k=n)的计算式为
i,j,k=(u1E1+v1E2+w1E3)i(u2E1+v2E2+w2E3)j(u3E1+v3E2+w3E3)kf000.
1.2 近曲面点的计算
　　这里介绍计算空间一点到三角Bzier曲面片R(u,v)的最近点(称为近曲面点)的方法［2］.设空间一点为G,为了采用迭代方法计算曲面片上距G最近的点R(u*,v*),假定已有一个初始点,如图3所示.

图3 近曲面点的计算

为了使e的模最小,将其Taylor展开

令

我们有


　　迭代过程如下:
　　(1) 输入空间点G和曲面片的初始点;
　　(2) 计算的偏微分Ru,Rv和d=G-;
　　(3) 由上式计算
　　(4) 若(为极小量),返回否则转(2).
通过迭代,一般2～3次即可计算出精确的参数值u*和v*.
1.3 初始交点的迭代求精［4,8,9］
　　针对我们所研究的复合三角Bzier曲面求交问题,我们需要计算出每两张曲面片的一个交点作为初始交点(原因在下面分析),可采用这样的方法进行:根据每张曲面片的控制顶点(如图1所示)建立最大最小包围盒,通过包围盒判断两张曲面片是否可能相交(称这两张曲面片为一个曲面对),若相交,则进行迭代计算精确的初始交点.若能求出一个满意的交点,记录它并停止;否则,对每张曲面片进行分割,形成新的曲面对,把对应的各子曲面片的平均参数值作为近似参数值,对应曲面上的两点的中点作为近似交点坐标,在原曲面片上进行迭代.用这种方法进行计算,要么判断出两张曲面片不相交,要么能够计算出一个交点,要么在分割达到控制精度时仍无法求出交点.在第3种情况下,我们记录一个最有可能的曲面对作为最终的近似交点,这个交点不能作为跟踪的起始点,仅可用来供其他交点判断该曲面对是否是交线的继续.
　　初始交点的求精,实际上就是将该点迭代至真正的交线上.这里所介绍的方法既用于初始交点的求出过程,也用于跟踪过程.如图4所示,设两个曲面为R(u,v),S(s,t),初始近似交点为M,M在R,S上的两个近曲面点为P,Q,P,Q处的切平面分别为FR,FS,过P,Q的中点作垂直于FR,FS的辅助平面,这3个平面交于G,通过G计算近曲面点,如果两个近曲面点位于给定的误差精度内,则认为二者是一个点,即交点,近曲面点的参数值即为交点的参数值;否则以G替代M,重复上面的过程.

图4 初始交点的求精
　　我们的目的是求出一个初始交点,这个交点必须满足控制精度,并且0≤u,v,(u+v)≤1.这是因为我们研究的是有界曲面片,所求的交点不可超出参数值范围.采用上面的方法求交点,有可能遇到切平面彼此平行的情况,更多的是求出的交点参数值小于0或大于1,这些问题的出现是由于初始点的选取不当而造成的,利用三角Bzier曲面片的分割就可以解决这个问题.
1.4 边界点的计算
　　边界点的计算有如下的应用:首先,如果跟踪的交点位于曲面片的界外,利用边界点的计算将该点迭代至边界上(即求出边界点),而不是通过改变跟踪步长的方法近似计算边界点;其次,利用边界点和前面介绍的求取近曲面点的方法,求出相邻的曲面片,从而顺序跟踪出整条交线.假设交点为R(u,v),S(s,t),为了计算边界上的点,令R(u,v)-S(s,t)的模最小,并且利用Taylor展开,我们可以得到如下的方程.


当‖R(u,v)-S(s,t)‖＜ε(ε为极小值)时,停止迭代.应用以上3式,可分别迭代计算出位于u=0,v=0,w=0边界上的点.
1.5 跟踪过程
　　我们研究的是复合三角Bzier曲面,一般地,每条交线将穿越许多曲面片.由于引进边界点和近曲面点的计算方法,所以在交线的每一个独立分支上,必须有一个交点作为初始点,否则该分支在后继步骤中将被遗漏.离散点的特点就是杂乱无章,如果适当地控制三角Bzier曲面片的分割控制精度,则基本上可以保证至少可以求出每条交线上的一个交点.另外,也可以通过补加测点来加以改进.我们的这种算法可以保证某交线段上只要有一个初始交点,就可以跟踪出整条交线(所以,假设每两张曲面片只计算一个交点是可行的).
一般地,将交点在两张曲面片上的法矢量的叉积作为跟踪的方向［4,5,10］:

其中c为跟踪方向矢量,FR,FS为交点处的曲面片的法矢量.至于跟踪步长的选择,已有许多文献论述过［4,5,10］.
　　我们将所有求出的每两张曲面片间的交点组成一个初始交点链表,开始跟踪.
　　(1) 从初始交点链表中取出一个交点;
　　(2) 标志该交点status=1,即表示已经跟踪处理过;
　　(3) 按照一个方向前进一个步长,用交点的迭代求精方法将其迭代至交线上;
　　(4) 判断是否超出边界,若没有超出,转(3),否则,继续;
　　(5) 利用边界点的计算方法计算边界点,并且记录第1个边界点;
　　(6) 在所有的交点中利用边界点和求近曲面点的方法计算出下一个相邻的曲面对及其上的一个交点,标志相邻的交点status=1;如果非第1个边界点与第1个边界点重合,可判断形成交线环;对记录的交点进行处理(如为了裁剪的便利,将第1个边界交点前的交点删去,保证无重复点);若到达曲面的边界,则反向跟踪;否则,转(3),继续;
　　(7) 直至将所有的交点用尽为止,记录所有的交线. 
2 构造基于复合三角Bzier曲面的裁剪曲面
2.1 基于交线的曲面可裁剪的条件
　　随着汽车、造船和模具等工业的发展,为了构造复杂的自由曲面,通常需要对自由曲面进行裁剪,以提高系统的造型能力,但并不是任意相交的两张曲面均可以裁剪.我们知道,任何一张曲面都是由一条外边界环和几条内边界环所围成的,交线在裁剪后将作为裁剪曲面的外边界(或内边界)而存在,所以,关于交线的曲面可裁剪的条件可定义如下.
　　(1) 某交线为环时;
　　(2) 某交线的两个端点落在复合曲面的外边界上;
　　(3) 某交线的两个端点落在复合曲面的某一条内边界环上;
　　(4) 某两条交线的两个端点分别位于外边界和同一内边界上;
　　(5) 某两条交线的端点分别位于两个内边界上;
　　(6) 多条交线的端点顺序位于外边界、几个内边界和外边界上.
　　针对我们研究的复合三角Bzier曲面而言,由于曲面的外边界是逆时针方向定义的,而内边界是顺时针方向定义的.这样,无论对于何种边界,当交线的端点位于某三角Bzier曲面片的边上时,该边的右相邻三角Bzier曲面片为空;如果交线的端点刚好是某三角Bzier曲面片的角点,可通过查阅与该角点相关的边中是否有一条边的右相邻三角Bzier曲面片为空来确定是否为复合曲面的边界.这种方法很快就可以辨别出交线段的可裁剪性.由于边界情况不一,我们采用人工交互的方式选取可裁剪的交线段来进行曲面的裁剪处理.
2.2 交点的插入和三角网格的局域三角化
　　当某条(或几条)交线段符合裁剪条件时,需要将交点作为型值点插入到型值点集中.由于是在三维空间中进行的,且交点是顺序排列的,这为三角网格的局域三角化作好了准备.
　　(1) 对每一个交点,判断是否为三角Bzier曲面片上的角点,若是,则找到该角点,否则将该交点作为一个新的型值点加入到曲面的型值点集中;
　　(2) 根据交点所在的三角Bzier曲面片,由曲面的拓扑信息,找到该交点所在的三角网格,在该网格中记录该交点.
　　对有型值点插入的三角网格,为了维护原有三角Bzier曲面片的拓扑关系,采用如下的三角化原则.
　　(1) 由三角网格的角点和交点中的边界点构成边界链表,其他交点构成内部点链表;
　　(2) 利用文献［2,3］中介绍的三角划分方法进行三角化;
　　(3) 当插入的点在一条边上穿进穿出时,如图5(a)所示三角化;
　　(4) 当插入的点穿越两条边时,如图5(b)所示三角化;
　　(5) 当穿进穿出边的次数多于3时,如图5(c)所示三角化.

图5 三角化情况
　　在三角化的同时,以交线为界标示出新生成的三角网格,如Vi(i=1,2,3,4)为新加入的点,在三角化时将Vi-1Vi左侧的三角网格标示为m-nSide=-1,将Vi-1Vi右侧的三角网格标示为m-nSide=1,而不参与三角化的三角网格初始化为m-nSide=0.我们总的要求是,三角化后的三角网格不得有覆盖的现象,在程序实现的过程中还有其他情况,各种三角化的方法在此均可以应用.
2.3 裁剪曲面的生成
　　三角化完成后,我们就可以将所有的三角网格以交线段为界进行分离.
　　Trim-Seperate(三角网格){
　　　　if (m-nSide==1(or -1)){
　　　　　if (相关三角网格m-nSide==0){
　　　　　　相关三角网格m-nSide=1(or -1);
　　　　　　Trim-Seperate(相关三角网格);}
　　　　}
　　}
这里所讲的相关三角网格是指与3条边相邻的三角网格,该递归函数是从三角网格集中最后一个元素开始的,这样就可以将所有的三角网格分为两组:m-nSide=1的一组和m-nSide=-1的一组.然后,将原复合曲面的型值点进行分离,加入到相应的每一组三角网格中,并重新编号.
　　for (原复合三角Bzier曲面的每一个型值点){
　　　　for (每一组三角网格中的每一个三角网格){
　　　　if (三角网格的角点==型值点){
　　　　　　将该型值点加入到新的曲面型值点集中;
　　　　　　修正该三角网格的角点编号;}
　　　　}
　　}
最后,对两组三角网格重建拓扑关系,构造各自的复合三角Bzier曲面.其中,在按照文献［2,3］方法构造复合三角Bzier曲面时,各型值点的法矢量由原曲面继承得到,而不再进行估算,从而保证了裁剪曲面的良好形态.至此,一张复合三角Bzier曲面被裁剪为两张复合三角Bzier曲面.
3 示例及讨论
　　图6是针对复杂的、插值于由工程实际测量的散乱点得到的复合三角Bzier曲面通过采用上述方法进行求交、裁剪的例子.图6(a)是某汽车立柱被另一张类似曲面所裁开;图6(b)是电风扇叶片被一圆柱所裁的结果;图6(c)是鞋楦的裁剪曲面;图6(d)是某通气管的裁剪曲面.虽然任意两张曲面片间有一条交线的假设有可能导致交线段的丢失,但我们的跟踪方法可以保证,只要知道某交线段上的一个交点(不管该交点位于哪个曲面对上),就可以将整条交线完整地计算出来;尽管三角化在边界上有一定的误差,但只要精度控制合理,在工程上完全能满足要求.


(a)

(b)

(c)

(d)
图6 曲面剪裁的例子
基金项目：本文研究得到国家教育部博士点专项基金和曹光彪科学基金资助.
作者简介：李际军,1967年生,博士生,主要研究领域为CAD/CAM,计算机图形学,反求工程,曲面造型.
　　　　　柯映林,1963年生,博士后,教授，博士生导师,主要研究领域为产品快速设计与制造,CAD/CAM,工程数据可视化,快速原型技术及其在医学中的应用.
　　　　　程耀东,1934年生,教授,博士生导师,主要研究领域为CIMS,CAD/CAM,先进制造技术,机械振动及结构动力学,信号处理.
作者单位：浙江大学机械工程学系　杭州　310027
本文通讯联系人:李际军，杭州 310027,浙江大学机械工程学系
参考文献
　1 Farin G. Curves and Surfaces for Computer Aided Geometric Design (3rd). San Diego: Academic Press, 1991
　2 Choi B K. Surface Modeling for CAD/CAM. New York: Elsevier Science Publishers, 1991
　3 柯映林.离散数据的几何造型技术及其应用研究［博士学位论文］.南京航空航天大学,1992
(Ke Ying-lin. Geometric modeling for three-dimensional scattered data and its application studies ［Ph.D. Thesis］. Nanjing University of Aeronautics and Astronautics, 1992)
　4 Barnhill R E, Kersey S N. A marching method for parametric surface/surface intersection. Computer Aided Geometric Design, 1990,7:257～280
　5 Stoyanov Tz E. Marching along surface/surface intersection curves with an adaptive step length. Computer Aided Geometric Design, 1992,9:485～489
　6 Sheng X, Hirsch B E. Triangulation of trimmed surfaces in parametric space. Computer Aided Design, 1992,24(8):437～444
　7 Piegl, Les A, Tiller Wayne. Geometry-based triangulation of trimmed NURBS surfaces. Computer Aided Design, 1998,30(1):11～18
　8 Mullenheim G. Convergence of a surface/surface intersection algorithm. Computer Aided Geometric Design, 1990,7:415～423
　9 Mullenheim G. On determining start points for a surface/surface intersection algorithm. Computer Aided Geometric Design, 1991,8:401～408
　10 宁涛,马德昌,王亚平等.平面向量场与曲率分析在曲面求交中的应用.计算机学报,1997,20(12):1074～1080
(Ning Tao, Ma De-chang, Wang Ya-ping et al. Application of plane vector field and curvature analysis in surface intersection. Chinese Journal of Computers, 1997,20(12):1074～1080)
本文1998-09-07收到原稿,1998-12-28收到修改稿
