基于重新参数化的Bézier曲面求交算法.pdf

第43卷第3期2023年5月DOI:10.13954/ki.hdu.2023.03.004杭州电子科技大学学报（自然科学版）Journal of Hangzhou Dianzi University(Natural Sciences)Vol.43 No.3May 2023基于重新参数化的Bzier曲面求交算法庞乾一，王振飞，陈小雕（杭州电子科技大学计算机学院，浙江杭州310 0 18)摘要：现有的参数曲面求交算法在求得一系列交点之后，需要再次用B样条插值才能表示出交线，且求得的交线无法保证精确落在任一给定曲面上。针对这一问题，提出一种基于重新参数化的求交算法。首先，通过曲面升阶加密曲面的控制网格，并求2 个曲面控制网格的交线；然后，将交线映射到参数域，通过分段B样条曲线拟合，将拟合结果作为牛顿迭代的初值；最后，运用牛顿迭代求得更精确的参数域交线。相比于传统跟踪算法，该算法可直接得到交线的有理多项式表示形式，且求得的交线严格落在其中一个曲面上，在计算的交点个数更少的同时获得更高的逼近精度，并通过仿真实验验证了算法的精确性和有效性。关键词：Bzier曲面求交；重新参数化；控制网格；B样条曲线拟合中图分类号：TP391.41文献标志码：A文章编号：10 0 1-9 146（2 0 2 3)0 3-0 0 2 4-0 60 引 言参数曲面求交是计算机辅助几何设计中基本且重要的问题，也是布尔运算的基础。Bzier曲面和NURBS曲面作为最常用的参数曲面，其求交运算广泛应用于计算机动画1、曲面裁剪2 、数控加工3、制造仿真4、地质建模5 等领域。常用的Bzier参数曲面求交方法包括代数法4、网格离散法6 、送代法7 、跟踪法8 1等。代数法将2 个参数曲面相交问题转化为非线性方程组的求解问题，仅在计算低阶曲面相交时有效，虽然可以通过函数合成9获得相交线的精确表示，但其阶数过高，无法在实际中使用。网格离散法将曲面离散为由三角平面片组成的网格，将参数曲面相交问题转化为三角形面片之间的求交运算，通用性强，但曲面的划分需要足够细密，计算耗时明显增加。迭代法根据初始交点在2 个曲面上的投影点，通过四参数迭代法求解下一交点，不能单独使用迭代法，且要求交点初值尽可能准确，否则迭代不收敛，无法得到满足精度要求的交点。跟踪法从提前求出的初始交点出发，根据交线的几何特性，按照一定的步长迭代计算后继交点，将这些离散点按顺序连接并再次用B样条拟合。跟踪法存在漏交问题，在法向共线点处的跟踪方向产生的交点不连续，且收敛速度慢，不稳定。文献10 采用基于交线微分形式的跟踪公式计算后继交点，解决了法向共线点处交点间断不连续的问题，但是，若精度要求很高，则需要很小的跟踪步长，导致跟踪步数和耗时均显著增加。上述曲面求交方法在求得一系列交点之后，需要再次用B样条插值才能表示出交线，且求得的近似曲面交线不能严格落在任何一个曲面上。为此，本文提出一种基于重新参数化的Bzier曲面求交算法，把曲面控制网格的交线近似为曲面的交线，并将其映射到参数域进行拟合，在计算交点个数较少的同时得到较高的逼近精度，且求解出的交线严格落在指定的一个曲面上。收稿日期：2 0 2 2-0 8-0 9基金项目：国家自然科学基金面上资助项目（6 197 2 12 0）作者简介：庞乾一（1998 一），男，研究方向：计算机图形学。E-mail:。通信作者：陈小雕，教授，研究方向：计算机图形学与计算机辅助设计。E-mail：x i a o d i a o h d u.e d u.c n。第3期1算法原理1.1曲面控制网格的求交曲面控制网格求交的基本思想是先将2 个曲面都升阶10 次从而加密曲面的控制网格，再将控制网格转化为三角网格，每个三角形对应空间中的1个平面，将曲面对求交转化为三角面片对求交。曲面经过升阶之后，控制网格变得更加细密，划分的三角面片也更多。直接对所有三角网格进行三角面片对的求交，效率较低。故本文根据Moller11 提出的三角形对求交思想进行三角形对快速求交。假设三角形Ti的顶点为VVi,V2，所在平面为Fi；三角形T2的顶点为V,Vi，V 2,所在平面为F2。首先，判断三角形TI与三角形T2所在平面是否相交。平面F2的计算公式如下：式中,X为平面F2上任意一点,N2=(V-V)(V-V2),d2=-NV。将三角形T的3个顶点分别代人式（1），得到各顶点到平面F2的距离为：若Dv0,i=0,1,2成立，且符号相同，则三角形Ti位于三角形T2所在平面F2的同侧，说明三角形Ti与三角形T,不相交；否则，三角形Ti与三角形T2所在平面F2相交。继续上述步骤，判断三角形T2是否与三角形Ti所在平面Fi相交,若2 次判断都相交，则说明三角形Ti与T,可能相交,再进行后续相交算法的处理。这种方法通过预先的三角形相交测试，提前排除了大量不相交的三角形对，从而减少了三角形求交计算量，提高了效率。然后，根据三角形的3条边与对方三角形的交点求得三角形对的交线段，将所有相交三角形对的交线段依次相连，得到控制网格的交线。1.2参数域上的交线拟合张量积形式的Bzier曲面定义为：p=p(u,)=br.,B(u)B,(u)0u,1,bi,E R式中,B（u）和B（）分别为m和n次的Bernstein基函数,bi,（i=O,l，,m;j=0,l，,n）为曲面的控制顶点。张量积形式的Bzier曲面参数域是一个矩形域。将曲面控制网格的交线段映射到曲面各自的矩形参数域中。根据Bzier曲面的性质，曲面控制网格的4个角点也正好是Bzier曲面的4个角点。即p（0,0）=b o.0，p（1,0）=b m.0，p（0,1）=b o.n，p(1,1）=bmn。将控制网格沿着u向、向分别均等分，即控制网格沿向的n十1个点映射到参数域向的值为六(i=0,1.,m),沿u向的m+1 个点映射到参数域u向的值为(i=0,1,.m)。n首先，采用1.1节中求交方法求得交点的重心坐标，将交点直接映射到2 个曲面各自的参数域，得到参数域中的交点坐标，并将这些交点按顺序连接，得到控制网格交线映射到参数域中的折线段。由于交点在两曲面的控制网格重心坐标并不相同，所以映射到两曲面各自参数域中的折线段也不相同。然后，用分段2 次均匀B样条分别拟合2 个曲面参数域中的折线段。B样条的节点矢量采用均匀节点，即uo=.=u,=O,u-=.=up=l,uj+r=式中，r为B样条的拟合次数，k为节点矢量的个数，q为B样条控制顶点的个数。将2 个曲面参数域交线按照u向或者向分为2 段，对这2 段都使用6 个控制点的2 次B样条曲线进行拟合，得到2 个曲面各自参数域中拟合后对应的多段B样条曲线。1.3重新参数化函数的牛顿迭代求精将2 个曲面参数域中的分段2 次B样条曲线作为重新参数化函数，分别代人到2 个曲面中，得到曲庞乾一，等：基于重新参数化的Bzier曲面求交算法XN2+d2=0Dv=VN2+d2i=0,1,2i=0j=0mq-+1j=1,2,-r25(1)(2)(3)(4)26面上的2 条曲线。当这2 条曲线之间的Hausdorff距离足够小时，可将其中1条曲线当作2 个曲面的交线。由此，设置每一段的牛顿迭代目标函数为：F(a11,b11,a12,b12,a21,b21,a22,b22)=min式中，a1,b1,a12,b12,a21,b21a22，b 2 2 为其中一段的2 条拟合B样条曲线的4个中间控制点的u向和向坐标,S（i（t)，y i（t)）和S，（2（t)，y 2（t)）分别为将2 个曲面各自的一段拟合B样条曲线作为重新参数化函数代人后得到的曲线。从1.2 节曲线的分段参数区间内映射到参数域的交点值中均匀取样4个点，作为牛顿迭代的初始值。因为给出的初始值已是较为接近的结果，所以点映射到参数域经过不超过10 次的迭代即可使得目标函数小于某个阈值，从而可以认为迭代得到的结果就是最终的近似交线。设置最大迭代次数为30次，如果某段拟合结果的Hausdorff距离在达到最大迭代次数时的结果仍然不满足精度要求，就将该段按照u向或者向二分，然后再分别用2 次B样条拟合迭代求解。得到曲面S.上的重新参数化函数(z;(t)，y（t)后，对应的交线即可近似表示为S.（a;(t)，y(t)），因此，对应的近似交线一定落在曲面S;，i=1,2 上。2实例分析通过2 个数值实例来验证本文提出算法的有效性。算法的控制参数如下：牛顿迭代目标函数的精度为10-7，Hausdorff距离阅值设定为10-，送代最大次数为30。实验在CPU为Intel(R）Co r e(T M)i5-6300HQ2.3GHz，内存为12 GB的6 4位win10操作系统的PC上运行。例12 个2 X2次Bzier曲面相交，Hausdorff 距离阈值为10-。(0,0,2.5)2X2次Bzier曲面1控制点为(一5.5,0,6.2 5)L(5,2,10)(5,一5.5,5.5)2X2次Bzier曲面2 控制点为(-10,4,8)(2,2,4)运用本文算法得到参数域分段2 次B样条拟合曲线，并代人其中1个曲面得到的交线如图1所示。杭州电子科技大学学报（自然科学版）(一5,一10,2.5)(0,4,6.25)(0,4,8)(0,0,0)(-10,6,10)(6,5,5)2023年s(z(t),y(t)-Se(2(t),y2()d(5,一7,2.5)(5,2,6.25)(5,4,10)(5,5,5）(-10,4,8)(11,10,11)(5)11109876543-10-6-226842图1本文算法求得的曲面1和曲面2 交线图曲面1和曲面2 的参数域拟合图分别如图2 和图3所示。0-2-4第3期1.00.90.80.70.60.50.40.30.20.10.00.00.10.20.30.40.50.60.70.80.91.0u向(a)求交映射后的折线图图2曲面1的参数域拟合图1.01.00.90.80.70.60.50.40.30.20.10.00.00.10.20.30.40.50.60.7u向(a)求交映射后的折线图图3曲面2 的参数域拟合图从图2 和图3可以看出，只要经过2 次二分即可得到满足Hausdorff距离精度要求的参数域函数。例2 2 个2 2 次Bzier曲面相交，设定Hausdorff距离阅值为10-3。(0,1,1)2X2次Bzier曲面3控制点为(2,3,3)L(6,3,一6)(8,6,8)(4,2,6)2X2次Bzier曲面4控制点为(0,2,8)(2,4,6)L(0,4,0)(4,8,4)(-2,4,-2)运用本文算法得到参数域分段2 次B样条拟合曲线，并代人其中1个曲面得到的交线如图4所示。108-6420-2-4-6-0图4本文算法求得的曲面3和曲面4交线图庞乾一，等：基于重新参数化的Bzier曲面求交算法0.40.6u(b)分段2 次B样条拟合图0.80.60.40.20.00.80.91.00.0(0,1,1)(2,2,3)(4,5,4)(10,6,-4)(0,0,0)(0,4,8)5432768271.0 r0.80.60.40.20.00.0(5,6,7)(10,8,-2)0.20.2(b)分段2 次B样条拟合图0.80.40.6u1.00.81.028曲面3和曲面4的参数域拟合图分别如图5和图6 所示。1.01.00.90.80.70.60.50.40.30.20.10.00.00.10.20.30.40.50.60.70.8 0.91.0u向(a)求交映射后的折线图图5曲面3的参数域拟合图1.01.0r0.90.80.70.60.50.40.30.20.1F0.00.00.10.20.30.40.50.60.70.80.9 1.0u向(a)求交映射后的折线图图6曲面4的参数域拟合图分别采用本文算法和传统跟踪法进行求交结果精度的比较。传统跟踪法在给出初始点之后，以不同的步长进行跟踪，再将求得的交点用3次B样条插值，得到最终的近似交线，此交线与精确交线的Hausdorff距离值如表1所示，本文算法求得的交线与精确交线的Hausdorff距离如表2 所示。表1传统跟踪法的求交结果与精确交线的Hausdorff距离实例跟踪点数6 点12.0072e-226.2961e-2表2 本文算法的求交结果与精确交线的Hausdorff距离实例二分0 次（1段）11.7499e-229.578 7e-3从表1和表2 可知，与传统的跟踪算法比较，本文算法在二分2 次时精度值即可达到10-3。因为本文算法先对曲面进行有限次升阶，再求控制网格交线从而得到初始值，该初始值已较为接近结果，所以，2个实例中，经过2 3次的区间二分，每段交线的迭代次数不超过10 次即可得到满足精度要求的交线。同时，本文算法中，每段交线在参数域上都是用6 个控制点，2 次B样条拟合，每段端点处有重叠，杭州电子科技大学学报（自然科学版）0.80.60.40.20.00.00.80.60.40.20.00.0跟踪12 个点跟踪18 个点1.791 4e-21.7852e-23.7290e-21.2049e-2二分1次（2 段）二分2 次（3段）3.724 9e-39.3191e-41.125 2e-39.4939e-42023年0.20.4u(b)分段2 次B样条拟合图0.20.4u(b)分段2 次B样条拟合图跟踪2 6 个点1.7727e-29.311 0e-3二分3次（4段）8.726 1e-42.070 7e-40.60.60.80.81.01.0第3期所以二分3次的总控制顶点数只有2 1个，顶点数明显少于传统跟踪法。3结束语本文提出一种基于重新参数化的Bzier曲面求交算法，在计算交点个数更少的同时，获得更高的逼近精度，且交线严格落在其中一个指定的曲面上。算法仍然有较大的改进空间，拟合交点的选取及优化可进一步提升逼近精度。此外，若参数域内对应的曲线形状较为复杂，则需将参数域的交线分为较多段拟合才能得到较为精确的结果，数值计算的耗时和计算稳定性将面临更大的挑战。参考文献1 DULDUL M,OZCETIN M.Intersection curve of two parametric surfaces in Euclidean n-spaceJJ.Acta etCommentationes Universitatis Tartuensis de Mathematica,2021,25(2):259-279.2J BUSE L,BA T L.The surface/surface intersection problem by means of matrix based representationsEJJ.ComputerAided Geometric Design,2012,29(8):579-598.3J JIN Y Q,ZHAO S,WANG Y H.An optimal feed interpolator based on G2 continuous Bzier curves for high-speedmachining of linear tool pathJJ.Chinese Journal of Mechanical Engineering,2019,32(3):121-130.4 VENTURA M,GUEDES SOARES C.Surface intersection in geometric modeling of ship hullsJ.Journal ofMarine Science and Technology,2012,17(1):114-124.5J ELSHEIKH A H,ELSHEIKH M.A reliable triangular mesh intersection algorithm and its application in geologicalmodellingJJ.Engineering with Computers,2014,30(1):143-157.6J LO S H,WANG W X.A fast robust algorithm for the intersection of triangulated surfacesJJ.Engineering withComputers,2004,20(1):11-21.7J PANG X F,PANG M Y.A tracing algorithm for intersection of parametric surface and implicit surfaceCJ/International Conference on Wireless Networks&.Information Systems,Washington,USA,IEEE Computer Society,2009:245-248.8 刘平，何雪明步长自适应追踪法曲面求交技术的研究.计算机工程与应用，2 0 2 0，56（2 1）：2 53-2 59.9J LIN H W,QIN Y,LIAO H W,et al.Affine arithmetic based B-Spline surface intersection with GPU accelerationJ.IEEE Transactions on Visualization&Computer Graphics,2014,20(2):172-181.10 史永丰，程婷，张育浩，等一种改进的基于微分方程的曲面求交跟踪算法 J图学学报，2 0 19，40（2）：290-295.11J MOLLER T.A fast triangle-triangle intersection testJJ.Journal of Graphics Tools,1997,2(2):25-30.庞乾一，等：基于重新参数化的Bzier曲面求交算法29Bzier parametric surface intersection algorithm based on reparameterizationPANG Qianyi,WANG Zhenfei,CHEN Xiaodiao(School of Computer,Hangzhou Dianzi Univrsity,Hangzhou Zhejiang 310018,China)Abstract:In prevailing parametric surface/surface intersection algorithms,after obtaining a set ofintersection points,they need to represent the intersection curves by using B-spline interpolation,while the intersection curves cannot be guaranteed to fall on any given surface.In this paper,anintersection algorithm based on reparameterization is proposed to ensure that the intersection curvesfall on one of the surfaces accurately.Firstly,the control mesh of the surface is encrypted by surfaceelevation,and the corresponding intersection lines of the two control meshes are obtained.Secondly,the intersection lines are mapped to the parameter domain,and the fitting results are taken as theinitial value of Newton iteration through piecewise B-spline curve fitting.Finally,Newton iteration isapplied to obtain more accurate intersection curves in the parameter domain.As a result,thealgorithm can directly get the rational polynomial representations of the intersection curves withoutusing interpolation,and the intersection curves are strictly on one of the two given surfaces.Simulation results show both accuracy and effectiveness of the proposed algorithm.Key words:Bezier surface intersection;reparameterization;control mesh;B-Spline curve fitting