摘 要：NURBS曲面与平面的求交方法有许多种，代数方法是其中应用较多的一种。针对代数方法中直接求解交线方程往往比较困难的情况，提出了一种相对比较完善的基于等值线法的NURBS曲面与平面的交点和交线的计算方法。该方法首先求取等值线网格与平面的交点，然后再根据具体情况细分网格后建立曲面与平面之间的交线。该方法具有稳定、不易遗漏交线、计算速度较快、容易分段等特点。最后，采用VC.net和OpenGL渲染引擎编制了交线计算程序，验证了该算法的可靠性。
关键词：NURBS曲面曲面与平面求交等值线法曲率控制VC.net
中图分类号: TP391文献标识码：A文章编号：1007-9416(2011)07-0103-03
An Intersection Algorithm of NURBS Surface and Plane Based on the Method of Isoline
SONG Hong-xun1, HAN Yi1,WU Chu-na1
（1.School of Automobile,Chang-an University,Xi’anShaan’xi710064,China）
Abstract：There are many methods to obtain intersection between NURBS surface and plane.Among these methods,algebra method is used in many cases.In order to resolve the difficulty of seeking intersection line in the algebra method,a consummately algorithm for calculating intersection points and intersection lines of NURBS surface and plane based on the method of isoline is presented.The method first calculates the intersection points of the isoline grids and plane,then build the intersection lines of the surface and plane after segmenting the grid depending on the circumstances.This method has the advantage of stabilization, quick calculation, easy segmentation and difficult to omit intersection line.In the end,using VC.net and render engine of OpenGL develop the intersection lines calculation program to verify the reliability of the algorithm.
Key words：NURBSintersection of surface and plane isoline methodcurvature control VC.net
曲面求交算法是CAD/CAM系统中的一个核心算法，广泛应用于实体造型拼合、数控加工、曲面裁剪等运算中。求交算法的质量好坏对整个系统的稳定性和使用程度有着非常直接的影响。根据曲面表示方法的不同，曲面求交主要分为三种:隐式曲面与隐式曲面求交、隐式曲面与参数曲面求交、参数曲面与参数曲面求交。工程设计界广泛将自由型曲面和二次曲面采用非均匀有理B样条（NURBS）方法统一且精确的表达。
针对NURBS曲面与平面（广义隐式曲面的特例））的求交问题，可以采用代数法、几何法、离散法、跟踪法等求交算法进行求解。代数法是利用代数运算，通过求解代数方程的解的方法来进行[1][2]，只是求解的方法各不相同，比较典型的有循环迭代[3]、交点跟踪等[4]。但是这些方法需要难度较高的运算技术，对于较为复杂的方程组几乎无法求解，且只适用于能得出曲面方程的曲面。几何法首先计算求交曲面的形状、大小、相互位置及方向等，然后通过识别交线的形状和类型后精确求出交线，这种方法只适用于简单的曲面求交。离散法是将曲面细化为均可用简单的面片逼近的子曲面片，然后通过求交得到一系列交线段，依次连接交线段即得到所求交线。跟踪法是首先求出初始交点，然后根据交线的局部几何关系跟踪得到下一交点，从而得到整条交线。
虽然大多数学者都采用代数法，但是上述这几种方法都或多或少存在稳定性较差的问题，使得在某些情况下可能存在遗漏交线或交点的可能，无法用于复杂的曲面求交，因此通用性较差，在具体应用中往往还需要与其他方法结合使用。针对这一问题，本文提出了一种比较切实可行的利用等值线细分的方法来求取曲面与平面的交线和交点的算法，并编制了相应的交线计算程序对该算法进行了实例验证。
1、等值线交点计算法
由于平面是广义隐式曲面的一种特例，所以从理论意义
上讲，NURBS曲面与平面的求交问题是参数曲面与隐式曲面求交的一种形式。设平面用隐式曲面表示，曲面方程为:
NURBS曲面用参数曲面表示，曲面方程为:
具体采用如下所示的公式表示[5]。
需要求解平面与曲面在定义域内的交线。
1.1NURBS曲面与平面的求交原理
对于用隐式曲面表示的平面和用参数曲面表示的曲面之间的求交线问题，把NURBS曲面的参数方程代入隐式曲面表示的平面方程后，如果NURBS曲面与平面相交，那么交点的值满足交线方程
此时可以将交线认为是参数域平面内的一条平面曲线，其中，。由于交线方程结构相对复杂，次数一般也很高，对其进行直接求解有一定的难度。通常采用数值迭代法对其进行求解。数值迭代法要求提供迭代的初值，即交线上的初始点值，为了避免存在遗漏交线的可能性，要求至少获得每条交线上的初始点值，而目前还没有找到满意的计算方法求取每条交线上的初始点值。为了避免数值迭代法的初始点值的选取问题，又为了提高算法的稳定性和通用性，减少遗漏交线的可能性，本文结合实例应用情况提出了一种基于等值线法的NURBS曲面与平面的求交算法。
1.2矩形网格单元的生成
曲面参数化后，我们把在定义域内的求解视为二维标量场抽取定义域内的等值线。因此，首先需要建立矩形网格，将参数域沿方向分别作、等分或不等分，即，，，，从而形成了*个矩形网格，每一个矩形网格单元的4个顶点分别为，，，，其对应的函数值分别为（即，以下含义相同）、、及（i=0，1， …，;j=0，1，…，），如图1所示。
若和分的足够大，则可以认为曲面与平面的交线在每一个网格内均是一条直线段。因此交线可以被认为是由一系列直线段所组成的折线，所以计算交线的步骤为:
(1)逐个计算每一网格单元的4条边与交线的交点;
(2)根据该单元与交线的交点，生成该网格单元内的一段交线;
(3)由一系列单元内的交线线段连接后构成交线。
1.3求网格单元与交线的交点
计算网格单元与交线h的交点，主要是计算每个网格单元的4条边与h的交点。假设函数在网格单元内呈线性变化，因此可以采用顶点判定和边上线性插值的方法来计算，具体步骤主要如下:
(1)若，则顶点记为“-”，否则记为“+”;
(2)若网格单元的4个顶点全为“+”或全为“-”，则该网格单元内不存在交线，继续按顺序找寻其他的网格单元。
(3)对于一个网格单元内2个顶点分别为“+”、“-”的单元边，则采用线性插值法计算交线与该单元边的交点。如图1中，设为“-”,为“+”，则采用如下表达式求交点:
也可以对该单元边再进行细分直到误差满足精度要求后再使用线性插值法求交点。
为了控制计算量，显然不能对每一个矩形都进行盲目的细分，而需要根据交线的精度情况区别对待。本文采用曲率控制策略:首先根据上式求出一个近似的交点，然后根据曲面在交点处的曲率半径的大小来确定细分网格时需要满足的跨度，即
;
其中，和分别为曲面上两个沿方向的两曲线在交点处的曲率半径;是比例系数，一般可以取定值。
这样在每一个矩形单元的内部，细分的程度都会不一样，显然近似交点的曲率半径越小的矩形单元内部就越需要进一步细分，而曲率半径较大的矩形单元内部则可能不需要进一步细分。
1.4构建网格内部的交线以及二次细分
利用前面所求得的每个单元格与交线的交点，就能根据拓扑关系建立网格单元内部的交线线段，但是当某一个网格单元的“+ ”、“- ”的顶点呈交叉分布时，则网格单元内部的交线线段可能存在二义性，可能的连接情况有2种形式，如下图2a和图2b所示。
此时需要采用基于St.Andrew的单元剖分方法，通过对网格单元进行再次细分来克服交点二义性的问题,如图3所示。
St.Andrew的单元剖分的基本思想是首先利用单元边中线将网格单元分成4个矩形小单元，并求出中心点（）的函数值，然后根据拓扑关系，假设在每一个细分后的矩形内交线是一段直线段，并依次构造这段交线，若仍然存在二义，则可以继续进行细分，直至不存在二义或者细分的次数足够多到可以缩小为一个交点。
1.5形成交线
将按照以上方法形成的所有交线段首尾连接起来，便形成了需要求解的NURBS曲面与平面的交线。同时也能够统计出交线的分段情况。
2、实例验证
采用本文所阐述的交线求取方法，利用VC.net和OpenGL渲染引擎编制了交线计算程序[6][7]，实现了曲面与平面交线和交点的计算，程序界面如图4a和图4b所示，实践证明本文所阐述的方法具有速度较快，不会遗漏交线，计算稳定等优点。
3、结语
本文结合NURBS曲面和平面的求交特点，建立了一种简单而稳定的曲面与平面的求交算法。该算法既不需要象数值迭代法那样选取初始点，也不会遗漏交线，且具有算法简单、实现方便、可靠性强等优点。在该算法的基础上，编制了曲面与平面的求交例程，对算法进行了验证，达到了准确求交的目的。
参考文献
[1] 张明霞等.NURBS曲面与隐式曲面求交的计算机实现及应用[J].中国造船, 2002,43(3):p.94~98.
[2] 余正生等.一种参数曲面与隐式曲面的求交算法[J].计算机辅助设计与图形学学报,1999, 11 (2): 97~99.
[3] 官火梁等.RCS计算中NURBS曲面和射线求交的快速计算[J].工程图学学报, 2006,01:p.87~91.
[4] 许晓革.曲面离散跟踪求交算法的研究[J]工程图学学报,2005,01:p.61~64.
[5] 施法中.计算机辅助几何设计与非均匀有理B样条[M],北京:高等教育出版社, 2001.
[6]Mason Woo, Jackie Neider, Tom Davis, et al. The official guide to learning OpenGL [M].Version1.2 Addison-Wesley, 2001.
[7]Foley, Van Dam, Feiner,et al. Computer graphics: prinple and practise second edition in C [M]. Pearson Education, 2002.213~222.
作者简介:
宋宏勋(1958- )，男，硕士，高级工程师，主要研究领域为自动控制技术及机电一体化。
韩毅(1975-)，男，陕西三原人，副教授，博士，主要研究领域为机电一体化与项目管理。
吴初娜(1985-)，女，浙江舟山人，博士，主要研究领域为车辆控制与安全。