计算机图形学课程设计-毕业论文

LH的计算机图形学作业PAGEPAGE1计算机图形学算法基础作业姓名：LH学院：理学院专业：计算数学时间：2010目录1直线段生成算法综述 11.1生成直线的DDA方法 11.1.1DDA算法基本原理 11.1.2DDA算法实现步骤 11.1.3DDA算法程序（或伪程序）描述 21.1.4DDA算法流程图 21.2生成直线的Bresenham算法 31.2.1Bresenham算法基本原理 31.2.2Bresenham算法实现步骤 51.2.3Bresenham算法程序（或伪程序）描述 51.2.4Bresenham算法流程图 51.3中点画线算法 21.3.1中点画线算法基本原理 21.3.2中点画线算法实现步骤 31.3.3中点画线算法程序（或伪程序）描述 31.3.4中点画线算法流程图 31.4生成直线算法的进一步改进 51.5各种直线生成算法的优缺点对比分析 61.6直线生成算法的发展趋势 72椭圆的Bresenham生成算法 72.1椭圆曲率分析 72.2椭圆方程分析 72.3椭圆生成算法 92.3.1算法实现过程 92.3.2算法流程图 102.3.3算法程序描述 113直线段裁剪算法综述 113.1Sutherland-Cohen裁剪算法 113.1.1Sutherland-Cohen算法基本原理 113.1.2Sutherland-Cohen算法实现步骤 113.1.3算法程序（或伪程序）描述 123.1.4算法流程图 123.2中点分割裁剪算法 123.2.1中点分割算法基本原理与实现步骤 123.2.2算法程序（或伪程序）描述 133.2.3算法流程图 133.3梁友栋－Barskey算法 143.3.1梁友栋－Barskey算法基本原理与实现步骤 143.3.2算法程序（或伪程序）描述 153.3.3算法流程图 153.4快速算法 153.5其余一些改进的直线裁剪算法 163.6各种直线裁剪算法的优缺点对比分析 163.7直线裁剪算法的发展趋势 164图形求交技术 164.1求交点算法 164.1.1线与线的交点的求法 174.2.2线与面的交点的求法 184.2求交线算法 194.3包含判定算法 214.4重叠判定算法 264.5凸包计算 265自由曲线曲面造型技术 285.1Bezier曲线和曲面 285.1.1Bezier曲线 285.1.2Bezier曲面 315.2B样条曲线与曲面 325.2.1B样条的递推定义和性质 325.2.2B样条曲线 345.2.5B样条曲面 365.3NURBS曲线与曲面 375.3.1NURBS曲线 375.3.2非均匀有理B样条（NURBS）曲面 395.4Coons曲面 405.4.1基本概念 405.4.2双线性Coons曲面 415.4.3双三次Coons曲面 426CAGD中有关曲线曲面、拼接技术 446.1基本原理 446.2Bezier曲线的的拼接条件 446.3Bezier曲面的的拼接条件 467图形变换技术 487.1二维图形几何变换 497.1.1平移(Translation) 497.1.2旋转(Rotation) 497.1.3变比(scaling) 507.2三维图形几何变换 517.2.1平移 517.2.2旋转 517.2.3变比 547.3参数图形几何变换 547.3.1圆锥曲线的几何变换 547.3.2参数曲线、曲面的几何变换 557.4投影变换 587.4.1平行投影(parallelprojection) 587.4.2透视投影(perspectiveprojection) 608图形消隐算法 618.1扫描线Z-buffer算法 618.2区域子分割算法 618.3光线投射算法 628.4平面公式法 628.5径向预排序法 638.6径向排序法 638.7隔离平面法 638.8深度排序法 638.9光线跟踪法 638.10Z缓冲区法 648.11极值检测法 648.12深度分类方法 648.13八叉树方法 659图形学若干基本算法的实现研究 65参考文献 68附录 68LH计算机图形学作业：共九道题图形学算法基础作业1直线段生成算法综述1.1生成直线的DDA方法1.1.1DDA算法基本原理DDA是数字微分分析式（DigitalDifferentialAnalyzer）的缩写。设直线之起点为，终点为，则斜率为：直线中的每一点坐标都可以由前一点坐标变化一个增量而得到，即表示为递归式：并有关系：递归式的初值为直线的起点，这样，就可以用加法来生成一条直线。1.1.2DDA算法实现步骤具体方法是：按照直线从到的方向不同，分为8个象限（见图1.1）。对于方向在第1a象限内的直线而言，。对于方向在第1b象限内的直线而言，取值。各象限中直线生成时的取值列在表1-1之中。图1.1直线方向的8个象限图表1-1各象限中直线生成时的取值列象限1a1b2a2b3a3b4a4bTFTFTFTF11/m-1-1/m-1-1/m11/mm1m1-m-1-m-1研究表中的数据，可以发现两个规律：1、当时；否则：2、的符号与的符号相同。这两条规律可以导致程序的简化。由上述方法写成的程序如附录1所示。其中steps变量的设置，以及等语句，正是利用了上述两条规律，使得程序变得简练。使用DDA算法，每生成一条直线做两次除法，每画线中一点做两次加法。因此，用DDA法生成直线的速度是相当快的。1.1.3DDA算法程序（或伪程序）描述具体程序见附录1。1.1.4DDA算法流程图（略）1.2中点画线算法1.2.1中点画线算法基本原理假定直线斜率在之间，当前象素点为，则下一个象素点有两种可选择点或。若与的中点称为M，Q为理想直线与垂线的交点。当M在Q的下方时，则取应为下一个象素点；当M在Q的上方时，则取为下一个象素点。这就是中点画线法的基本原理。1.2.2中点画线算法实现步骤下面讨论中点画线法的实现。过点、的直线段L的方程式为，其中，，要判断中点M在Q点的上方还是下方，只要把M代入，并判断它的符号即可。为此，我们构造判别式:

当时，M在L(Q点)下方，取为下一个象素；

当时，M在L(Q点)上方，取为下一个象素；

当时，选或均可，约定取为下一个象素。注意到是的线性函数，可采用增量计算，提高运算效率。若当前象素处于情况，则取正右方象素,要判下一个象素位置，应计算，增量为a。

若时，则取右上方象素。要判断再下一象素，则要计算，增量为。画线从开始，的初值，因，所以。

由于我们使用的只是的符号，而且的增量都是整数，只是初始值包含小数。因此，我们可以用代替来摆脱小数，写出仅包含整数运算的算法程序。1.2.3中点画线算法程序（或伪程序）描述具体程序见附录21.2.4中点画线算法流程图（略）1.3生成直线的Bresenham算法1.3.1Bresenham算法基本原理本算法由Bresenham在1965年提出。设直线从起点到终点。直线可表示为方程。其中我们讨论先将直线方向限于1a象限（图1.1）在这种情况下，当直线光栅化时，x每次都增加1个单元，即。而y的相应增加应当小于1。为了光栅化，只可能选择如图1.2两种位置之一。图1.2的位置选择图1.2中的位置选择或者选择的原则是看精确值与及的距离d1及d2的大小而定。计算式为：如果，则，否则。因此算法的关键在于简便地求出的符号。将式（1.2.1）、（1.2.2）、（1.2.3）代入，得用乘等式两边，并以代入上述等式，得是我们用以判断符号的误差。由于在1a象限，总大于0，所以仍旧可以用作判断符号的误差。为：误差的初值P1，可将x1,y1，和b代入式（2.1.4）中的而得到：1.3.2Bresenham算法实现步骤综述上面1.3.1的推导，第1a象限内的直线Bresenham算法思想如下：1、画点(x1,y2);计算误差初值P1=2dy-dx;i=1；2、求直线的下一点位置：xi+1=xi+1；ifPi>0则yi+1=yi+1；否则yi+1=yi；3、画点（xi+1,yi-1）；4、求下一个误差Pi+1；ifPi>0则Pi+1=Pi+2dy-2dx;否则Pi+1=Pi+2dy；5、i=i+1;ifi<dx+1则转2；否则end。1.3.3Bresenham算法程序（或伪程序）描述由上述算法思想编制的程序见附录3。这个程序适用于所有8个方向的直线（图1.1）的生成。程序用色彩C画出一条端点为和的直线。其中变量的含义是：P是误差；const1和const2，是误差的逐点变化量；inc是y的单位递变量，值为1或-1；tmp是用作象限变换时的临时变量。程序以判断为分支，并分别将2a,3a象限的直线和3b,4b象限的直线变换到1a,4a和2b,1b方向去，以求得程序处理的简洁。1.3.4Bresenham算法流程图（略）1.4生成直线算法的进一步改进除过前面所讲到的3种基本直线生成算法外，还有一些其它的方法，由于过多，这里仅列举几种如下：（1）二步法。虽然Bresenham直线生成算法是一效率很高的算法，但是人们仍在寻找更有校的算法。1987年又有人提出了一种二步法。即每循环一次不是绘制一个像素，而是绘制两个像素，这样无疑可把生成直线的速度提高一倍。（2）改进的Bresenham算法。对于对于传统的直线生成算法，人们往往把注意力集中在算法本身，却忽略了算法之外的一些有用信息:画线之前，从起点坐标和终点坐标，我们就可以获知该线段的斜率，由此可进一步得出在主轴方向连续走l个步长，在副轴方向才走一个坐标单位，这就是本算法提高Bresenham算法执行效率的一个方面。提高算法效率的第二个方面是利用线段本身的对称性，则新算法所产生的起点一侧的半条线段与用Bresenham算法产生的相同。至于终点一侧的半条线段，可以看成以终点为起点线段的生成。算法实现：特殊地，对于水平线()，垂直线()和对角线()，它们都可直接装人帧缓冲器，而无需进行画线算法处理。从以上的描述可以实现优于Bresenham的直线生成算法。其中待生成直线的已知数据为:为线段起点的横、纵坐标；为线段终点的横、纵坐标。算法的输人数据为:，。（3）基于类最佳逼近的散步直线生成算法。一种新的直线逼近方法—类最佳逼近,基于这种逼近方法,斜率的直线和斜率为的直线具有某种互补性质。利用该性质,设计出一种新的三步直线方法,该算法揭示了直线计算的互补性,理论简单,精度达到最好。这种算法改善了Bresenham算法和双步算法的计算效率。该算法对于硬件实现将更有益处。除此之外直线生成算法还有对称扫描四步增量画线算法、基于Bresenham的高效直线生成集成算法、基于Bresenham算法的四步画直线算法、基于直线特性的直线生成集成算法、基于自适应步长的直线生成算法、基于等分像素点的直线生成算法、6步直线生成算法、基于对角线行程的直线生成算法等等。1.5各种直线生成算法的优缺点对比分析DDA算法的优点是：绘制实数直线效果好，误差小；缺点是：实现较复杂，不利于硬件实现。因为该算法涉及到实数乘除法运算，y与k必须用浮点数表示，而且每一步都要对y四舍五入后取整。中点画线算法优点是：只有整数运算，不含乘除法；可用硬件实现。Bresenham算法的优点是：1、不必计算直线之斜率，因此不做除法；2、不用浮点数，只用整数；3、只做整数加减法和乘2运算，而乘2运算可以用硬件移位实现。4、Bresenham算法速度很快，并适于用硬件实现。1.6直线生成算法的发展趋势（略）2椭圆的Bresenham生成算法2.1椭圆曲率分析椭圆（为沿轴方向的长半轴长度，为沿轴方向的短半轴长度，且），曲率为，在第一象限，将对求导数，有，即曲率为减函数，在点（即）处的曲率；在点（即）处的曲率。半径为的圆的曲率为，半径为的圆的曲率为，两圆的曲率关系为，则两圆的曲率在椭圆上点与的曲率之间，四者的关系为：。2.2椭圆方程分析根据椭圆及圆的曲率分析，椭圆弧分别由半径为和的圆弧逼近生成。为了更准确的由圆弧生成椭圆弧，在椭圆弧上确定一点，将椭圆弧分成曲率较小和曲率较大的两段，椭圆方程为：。其中为沿轴方向的长半轴长度，为沿轴方向的短半轴长度，且。由于椭圆的对称性，这里只要讨论第一象限椭圆弧的生成。将椭圆弧分为上下两部分，以弧上曲率为-1的点（即法向量两个分量相等的点）作为分界。该椭圆上一点处的法向量为：结合椭圆方程可计算出分界点的坐标为：。以点为分界点，将第一象限的圆弧分成曲率较大和较小的两段弧。如图2.1所示，的椭圆弧，与半径为的圆在点到的圆弧上对应。在椭圆弧上任取一点，过作垂直线与圆交于点，连接圆心与点，与轴的夹角为。则椭圆的参数方程可表示为：圆的参数方程可表示为：对于同一，椭圆弧上存在唯一的点与圆弧上的点对应，并且对应点的坐标存在如下关系：图2.1圆弧与椭圆弧对应点之一图2.2圆弧与椭圆弧对应点之一如图2.2所示，半径为的圆上，从点到的圆弧与椭圆上的椭圆弧对应，在椭圆弧上任取一点，过作垂直线与圆交于点，连接圆心与点，与轴的夹角为。则椭圆的参数方程可表示为：圆的参数方程可表示为：对于同一，椭圆弧上存在唯一的点与圆弧上的点对应，并且对应点的坐标存在如下关系：2.3椭圆生成算法当圆弧上的点从沿着图2.1、图2.2的对应关系方向变化到时，椭圆弧上相对应的点也从该方向变化到。2.3.1算法实现过程1、计算分界点。2、用Bresenham算法生成两段圆弧、。半径为，；半径为，。3、将圆弧进行比例变换：方向的比例系数为1，方向的比例系数为；将圆弧进行比例变换：方向的比例系数为，方向的比例系数为1。4、如图2.3，已知椭圆上在第一象限的点，则椭圆上另外三个象限与点对称的点分别为，因此只要画出在第一象限的图形，即可得到整个椭圆的图形。图2.3椭圆对称性2.3.2算法流程图椭圆的Bresenham算法流程图如下：椭圆上点的Y坐标大于0椭圆上点Y的坐标大于开始计算分界点椭圆上点的Y坐标大于0椭圆上点Y的坐标大于开始计算分界点用Bresenham算法计算圆弧计算对应圆弧上的点结束用Bresenham算法计算圆弧YNYN图2.4椭圆的Bresenham算法流程图2.3.3算法程序描述具体程序实现见附录5。3直线段裁剪算法综述裁剪：确定图形中哪些部分落在显示区之内，哪些落在显示区之外,以便只显示落在显示区内的那部分图形。这个选择过程称为裁剪。直线段裁剪算法是复杂图元裁剪的基础。复杂的曲线可以通过折线段来近似，从而裁剪问题也可以化为直线段的裁剪问题。3.1Sutherland-Cohen裁剪算法3.1.1Sutherland-Cohen算法基本原理Sutherland–Cohen算法分成两步。第一步是判断直线段是否完全在窗口内，若在则该线段称为完全可见的；或可显然的决定线段完全在窗口的外边，称为完全不可见；对不能判断完全可见或完全不可见的线段则要进行第二步处理。这时需要计算出直线段和窗口边界的一个交点，这个交点把直线分成两段，把其中一段显然完全不可见的线段抛弃，对余下的部分再作第一步判断，重复上述过程，直到直线段最后余下的部分可以用第一步的判断得出肯定结论为止。3.1.2Sutherland-Cohen算法实现步骤基本思想：对于每条线段分为三种情况处理分为三种情况处理:（1）若完全在窗口内，则显示该线段，简称“取”之。（2）若明显在窗口外，则丢弃该线段，简称“弃”之。（3）若线段不满足“取”或“弃”的条件，则在交点处把线段分为两段。其中一段完全在窗口外，可弃之。然后对另一段重复上述处理。为快速判断，采用如下编码方法：每个区域赋予4位编码（如图3.1所示）：其中：x100110000001x100110000001101000000010010001010110xLxRyTyB图3.1区域编码图3.2线段不能用编码确定若完全在窗口内code1=0,且code2=0,则“取”若明显在窗口外code1&code2≠0，则“弃”在交点处把线段分为两段。其中一段完全在窗口外，可弃之。然后对另一段重复上述处理。计算线段与窗口边界的交点 if(LEFT&code!=0) { x=XL; y=y1+(y2-y1)*(XL-x1)/(x2-x1);} elseif(RIGHT&code!=0) { x=XR; y=y1+(y2-y1)*(XR-x1)/(x2-x1);} elseif(BOTTOM&code!=0){ y=YB; x=x1+(x2-x1)*(YB-y1)/(y2-y1);}elseif(TOP&code!=0){ y=YT; x=x1+(x2-x1)*(YT-y1)/(y2-y1);}3.1.3算法程序（或伪程序）描述过程clip描述了这一算法。其中用一个集合(top,bottom,right,left)来表示端点的编码。具体程序见附录6。3.1.4算法流程图（略）3.2中点分割裁剪算法3.2.1中点分割算法基本原理与实现步骤与前一种Cohen-Sutherland算法一样首先对线段端点进行编码，并把线段与窗口的关系分为三种情况：完全可见、完全不可见和线段与窗口有交。对前两种情况，进行一样的处理。对于第三种情况，用中点分割的方法求出线段与窗口的交点。求线段与窗口的交点如下：设要裁剪的线段是。中点分割算法可分成两个过程平行进行，即从出发找出离最近的可见点（图3.3中的A点），和从出发找出离最近的可见点（图3.3中的B点）。这两个最近可见点的连线就是原线段的可见部分。从出发找出最近可见点的办法是先求的中点，若不能定为显然不可见，则取代替，否则取代替，再对新的求中点。重复上述过程，直到长度小于给定的小数为止。图3.4是求的最近可见点的算法框图。求的最近可见点的算法框图是一样的，只要把和交换即可。在显示时可取成一个像素的宽度，对分辨率为的显示器来说，上面讲的二分的过程最多只要做N次。由于计算机过程只要做加法和除2，所以特别适合用硬件来实现。如果允许两个找最近点的过程平行进行，这样的话可使裁剪速度加快，增加算法效率。图3.3中点分割算法3.2.2算法程序（或伪程序）描述具体程序见附录7。3.2.3算法流程图中点分割算法框图如图3.4。可见否?可见否??显然不可见显然不可见?exit原线完全不可见exit否否否否是是是是图3.4中点分割算法框图3.3梁友栋－Barskey算法3.3.1梁友栋－Barskey算法基本原理与实现步骤设要裁剪的线段是，的坐标是。和窗口边界交于A、B、C、D四点，见图3.5。算法基本思想是从A，B和三点中找出最靠近的点，图3.5中要找的点是，从C，D和三点中找出最靠近的点，图3.5中要找的点是C点。那么就是上的可见部分。xxyyTyBxLxRABCD图3.5是可见部分具体计算时要把写成参数方程其中。把窗口边界的四条边分成两类，一类称为始边，另一类称为终边。参数化形式写出裁剪条件:可以统一表示为形式：当且，则线段完全在边界外，，则该线段平行于裁剪边界并且在窗口内；当的情况下：当,线段从裁剪边界延长线的外部延伸到内部；当,线段从裁剪边界延长线的内部延伸到外部。对于每条直线，可以计算出参数和，它们定义了在裁剪矩形内的线段部分，的值由线段从外到内遇到的矩形边界所决定。对这些边界计算。取0和各个值之中的最大值。的值由线段从内到外遇到的矩形边界所决定。对这些边界计算。取1和各个值之中的最小值。如果，则线段完全落在裁剪窗口之外，被舍弃。否则裁剪线段由参数的两个值，计算出来。3.3.2算法程序（或伪程序）描述具体程序见附录8。3.3.3算法流程图（略）3.4快速算法在实际绘图时，常出现大部分线段是可见的，或大部分线段为显然不可见。因而用最少的操作去判断被裁剪的线段是否属于这两种情况则可以提高裁剪的效率。此外，尽量减少比较和四则运算，也是提高效率的重要措施。这样会使程序长一点，但由于效率高，在软件包中值得采用。用这样的算法确定一根显然不可见线段平均只要做3.6次比较，确定一根完全可见线段要用8次比较，而用Sutherland-Cohen算法做同样工作则分别要做11次和10次比较。快速算法在最快的情况下要和四条边求交点，这要用10次加减法、5次乘除法和13次比较。采用Sutherland-Cohen算法要做16次加减法、8次乘除法和35次比较。此外后者还要多次调用过程合作集合运算，这些都使它比快速算法效率低。3.5其余一些改进的直线裁剪算法除过前面所讲到的4种基本直线裁剪算法外，还有一些其它的裁剪方法，由于过多，这里仅列举几种如下：（1）具有最少算术运算量的二维线裁剪算法。见文献：王骏，梁友栋，彭群生，具有最少算术运算量的二维线裁剪，《计算机学报》，1991年第7期。（2）一个有效的多边形窗口的线裁剪算法。见文献：刘勇奎等，一个有效的多边形窗口的线裁剪，《计算机学报》，1999年第11期。（3）一种基于几何变换的高效的线裁剪新算法。见文献：汪乱，吴锐迅，蔡士杰。一种基于几何变换的高效的线裁剪新算法。《软件学报》，1998，9(10):728一733。（4）任意多边形窗口的线裁剪算法。见文献：孙岩，唐棣:任意多边形窗口的线裁剪，《2000年图形学会议专刊))。3.6各种直线裁剪算法的优缺点对比分析Sutherland-Cohen直线裁剪算法要计算直线段与窗口边界的交点，这不可避免地要进行大量的乘除运算，必会降低程序的执行效率。而中点分割裁剪算法却只需用到加法和除2运算，而除2运算在计算机中可以简单地用右移一位来实现，从而提高算法的效率。所以特别适合硬件实现，同时也适合于并行计算。3.7直线裁剪算法的发展趋势（略）4图形求交技术4.1求交点算法求交点可以分两种情况：求线与线的交点以及求线与面的交点。4.1.1线与线的交点的求法1、直线段与直线段的交点假设二条直线的端点分别为则它们可以用向量形式表示为：其中，。构造方程对三维空间中的直线段来说，上述方程实际上是一个二元一次方程组，由三个方程式组成。可以从其中两个解出，再用第三个验证解的有效性：若第三个方程成立则说明找到了解，否则说明两条直线不相交。当所得的解是有效解时，可用二个线段方程之一计算交点坐标，例如。我们还可以根据向量的基本性质，直接计算s与t：对（4.1.1）两边构造点积得由于CXD同时垂直于C和D，等式右边为零。故有类似地有完整的算法还应判断无解与无穷多解（共线）的情形，以及考虑数值计算误差造成的影响。2、直线段与二次曲线的交点不失一般性，考虑平面上一条直线与同平面的一条二次曲线的交。假设曲线方程为，直线段方程为,则在交点处有。当曲线为二次曲线时，上述方程可写为用二次方程求根公式即可解出t值。3、圆锥曲线与圆锥曲线的交点圆锥曲线有代数法表示、几何法表示与参数法表示。在进行一对圆锥曲线的求交时，把其中一条圆锥曲线用代数/几何法表示为隐函数形式，另一条表示为参数形式（如二次NURBS曲线）。将参数形式代入隐函数形式可得关于参数的四次方程，可以使用四次方程的求根公式解出交点参数。得到交点后可再验证交点是否在有效的圆锥曲线段上。4.2.2线与面的交点的求法1、直线段与平面的交点（如图4.1）图4.1线段与平面求交考虑直线段与无界平面的求交问题。把平面上的点表示为，直线段上的点表示为，二者的交点记为。假设线段不平行于平面，则它们交于，即等式两边点乘，得由于既垂直于B，又垂直于C，故有可解出 类似求得如果是直线与平面区域求交点，则要进一步判断点是否在平面上的有效区域中，其算法可参见4.2节。2、圆锥曲线与平面的交点圆锥曲线与平面求交时，可以把圆锥曲线表示为参数形式，并把圆锥曲线的参数形式代入平面方程，即可得到参数的二次方程进行求解。3、圆锥曲线与二次曲面的交点圆锥曲线与二次曲面求交时，可把圆锥曲线的参数形式代入二次曲面的隐式方程，得到参数的四次方程，用求根公式求解。4.2求交线算法求交线显然是指求面与面的交线，下面讨论几种常见的情况。1、平面与平面的交线在CAD中一般使用平面上有界区域。先考虑最简单的情形。两个平面区域分别由定义。如果它们不共面而且不分离，则必交于一直线段。这条直线必落在所定义的无限直线上。注意这是个含有四个未知数，三个方程式的方程组，只要分别与八条边界线方程：联立，即可求出线段的两个端点的参数。在上述方程组中，只要找到两组解，就可以不再对剩余其它方程组求解。找到的两组解就是所求的交线段端点参数。当两个一般的多边形（即既可能是凸的，也可能是凹的，甚至可能带有内孔）相交时，可能有多段交线。我们可以把两个多边形分别记为A和B，用如下的算法求出它们的交线：（1）把A的所有边与B求交，求出所有有效交点；（2）把B的所有边与A求交，求出所有有效交点；（3）把所有交点先按y，再按x的大小进行排序；（4）把每对交点的中点与A和B进行包含性检测，若该中点即在A中又在B中，则该对交点定义了一条交线段。2、平面与二次曲面的交线求平面与二次曲面的交线有两种方法：代数法和几何法。用代数法考虑平面与二次曲面求交问题时，可以把二次曲面表示为代数形式：可以通过平移与旋转坐标变换把平面变为XOY平面，对二次曲面进行同样的坐标变换。由于在新坐标系下平面的方程为，所以新坐标系下二次曲面方程中，把含z项都去掉即为平面与二次曲面的交线方程（在新坐标系下）。对该交线方程进行一次逆坐标变换即可获得在原坐标系下的交线方程。在具体实现时，交线可以用二元二次方程系数表示（代数表示），辅之以局部坐标系到用户坐标系的变换矩阵。这种方法的缺点是，每当需要使用这些交线时，都要进行坐标变换。例如，判断一个空间点是否在交线上，必须先对它进行坐标变换，变到平面上，再进行检测。需要绘制该交线时，也要先在局部坐标系下求出点坐标，再变换到用户坐标系下的坐标。所以交线采用另一种方法（几何表示）更合理。几何方法存储曲线的类型（椭圆、抛物线或双曲线），以及定义参数（中心点、对称轴、半径等大小尺寸）的数值信息，使用局部坐标系到用户坐标系的变换，把局部坐标系下的定义参数变换到用户坐标系直接使用。这第二种方法使用较少的变换，但需要用计算来判断曲线的种类，及计算曲线的定义参数。由于浮点运算的不精确性，容易发生判错类型以及定义参数误差过大的问题。当平面与二次曲面的交线需要精确表示时，往往采用几何法求交。二次曲面采用几何表示，平面与二次曲面求交时，根据它们的相对位置与角度（根据定义参数），直接判断交线类型，其准确性大大优于用代数法计算分类的方法。几何法不需要对面进行变换，所以只要通过很少的计算就可以得到交线的精确描述。由于存储的信息是具有几何意义的，所以判断相等性、相对性等问题时，可以确定有几何意义的容差。下面以平面一球求交为例，说明几何法求交算法。平面用一个记录p表示，p的两子域p.b,p.w分别代表平面上一点与平面法向量。球面用记录s表示。它的两个子域s.c,s.r分别代表球面中心和半径。则可写出平面与球面相交的算法如下：plane_sphere_intersect(p,s)planep;spheres;{d=球面中心到平面的有向距离；if(abs(d)=s.r){二个面相交于一（切）点s.c-d*p.w;}elseif(abs(d)>s.r){两个面无交；}else{所求交线是圆。其圆半，半径，圆所在平面法向量为c=s.c-d*p.w;r=sqrt(s.r2-d2);w=p.w;}}一个平面与一个圆柱面可以无交、交于一条直线（切线）、二条直线、一个椭圆或一个圆，可以用两个面的定义参数求出它们的相对位置关系和相对角度关系，进而判断其交属于何种情况，并求出交线的定义参数。平面与圆锥的交线也可类似求出。3、平面与参数曲面的交线最简单的方法是把参数曲面的表示代入平面方程得到用参数曲面的参数s、t表示的交线方程另一种方法是用平移和旋转变换对平面进行坐标变换，使平面成为新坐标系下的平面。再用相同的变换应用于参数曲面方程得到参数曲面在新坐标系下的方程由此得交线在新坐标系下的方程为。4.3包含判定算法在进行图形求交时，常常需要判定两个图形间是否有包含关系。如点是否包含在线段、平面区域、三维形体中，线段是否包含在平面区域、三维形体中，等等。许多包含判定问题可转化为点的包含判定问题，如判断线段是否在平面上可以转化为判断其两端点是否在平面上。因此下面主要讨论关于点的包含判定算法。判断点与线段的包含关系，也就是判断点与线的最短距离是否位于容差范围内。造型中常用的线段有三种：1、直线段；2、圆锥曲线段（主要是圆弧）；3、参数曲线（主要是Bezier，B样条与NURBS曲线）。点与面的包含判定也类似地分为三种情况。下面分别讨论。1、点与直线段的包含判定假设点坐标为，直线段端点为，，则点P到线段的距离的平方为当时，认为点在线段（或其延长线）上，这时还需进一步判断点是否落在直线段的有效区间内。只要对坐标分量进行比较，假设线段两端点的x分量不等（否则所有分量均相等，那么线段两端点重合，线段退化为一点），那么当与反号时，点P在线段的有效区间内。2、点与圆锥曲线段的包含判定以圆弧为例，假设点的坐标为，圆弧的中心为，半径为，起始角，终止角。这些角度都是相对于局部坐标系x轴而言。圆弧所在平面为先判断点是否在该平面上，若不在，则点不可能被包含。若在，则通过坐标变换，把问题转换到二维的问题。给定中心为，半径为，起始角，终止角的圆弧，对平面上一点，判断P是否在圆弧上，可分二步进行。第一步判断P是否在圆心为，半径为的圆的圆周上，即下式是否成立：第二步判断P是否在有效的圆弧段内。3、点与参数曲线的包含判定设点坐标为，参数曲线为。点也参数曲线的求交计算包括三个步骤：（1）计算参数值，使到的距离最小；（2）判断是否在有效参数区间内（通常为）；（3）判断与的距离是否小于。若（2），（3）步的判断均为“是”，则点在曲线上；否则点不在曲线上。第一步应计算，使得最小，即最小根据微积分知识，在该处即用数值方法解出值，再代入曲线参数方程可求出曲线上对应点的坐标。第（2）、（3）步的处理比较简单，不再详述。4、点与平面区域的包含判定设点坐标为，平面方程为。则点到平面的距离为若，则认为点在平面上，否则认为点不在平面上。在造型系统中，通常使用平面上的有界区域作为形体的表面。在这种情况下，对落在平面上的点还应进一步判别它是否落在有效区域内。若点落在该区域内，则认为点与该面相交，否则不相交。下面以平面区域多边形为例，介绍有关算法。判断平面上一个点是否包含在同平面的一个多边形内，有许多种算法，这里仅介绍常用的三种：叉积判断法、夹角之和检验法以及交点计数检验法。（1）叉积判断法假设判断点为。多边形顶点按顺序排列为。如图4.2所示。令。那么，在多边形内的充要条件是叉积的符号相同。叉积判断法仅适用于凸多边形。当多边形为凹时，尽管点在多边形内也不能保证上述叉积符号都相同。这时可采用后面介绍的两种方法。图4.2叉积判断法（2）夹角之和检验法假设某平面上有点和多边形，如图4.3所示。将点分别与相连，构成向量。假设角。如果，则点在多边形之外，如图4.3(a)所示。如果，则点在多边形之内，如图4.3(b)所示。可通过下列公式计算：令,，则，所以且的符号即代表角度的方向。图4.3夹角之和检验法在多边形边数不太多（<44）的情况下，可以采用下列近似公式计算。其中为常数。当时，可判在多边形内。当时，可判在多边形外。证明略。（3）交点计数检验法当多边形是凹多边形，甚至还带孔时，可采用交点计数法判断点是否在多边形内。具体做法是，从判断点作一射线至无穷远：求射线与多边形边的交点个数。若个数为奇数，则点在多边形内，否则，点在多边形外。如图4.4所示，射线a,c分别与多边形交于二点和四点，为偶数，故判断点A，C在多边形外。而射线b,d与多边形交三点和一点，为奇数，所以B，D在多边形内。当射线穿过多边形顶点时，必须特殊对待。如图2.5.4所示，射线f过顶点，若将交点计数为2，则会错误地判断F在多边形外。但是，若规定射线过顶点时，计数为1，则又会错误地判断点E在多边形内。正确的方法是，若共享顶点的两边在射线的同一侧，则交点计数加2，否则加1。按这种方法，E点计为2，所以在多边形外；F点计数为１，所以在多边形内。图4.4交点计数法5、点与二次曲面/参数曲面的包含判定假设点坐标为，二次曲面方程为，则当时，认为点在该二次曲面上，在造型系统中，通常使用裁剪的二次曲面。在这种情况下，还要判断点是否在有效范围内。裁剪的二次曲面通常用有理Bezier或有理B样条的参数空间上的闭合曲线来定义曲面的有效范围，故要把点所对应的参数空间的参数坐标计算出来，再判断该参数坐标是否在参数空间有效区域上。6、点与三维形体的包含判定判断点是否被三维形体所包含，可先用前面的方法判断点是否在三维形体的表面上，然后判断点是否在形体内部，其方法因形体不同而异。下面以凸多面体为例说明。设凸多面体某个面的平面方程为，调整方程系数的符号，使得当时，点位于该平面两侧中包含该凸多面体的一侧。于是要检验一个点是否在凸多面体内部，只要检验是否它对凸多面体的每一个面均满足以上的不等式即可。4.4重叠判定算法进行求交计算时，常涉及判断两个几何形体是否重叠。下面讨论几种常见的情况。判断空间一点与另一点是否重叠，只要判断两点之间的距离是否小于0即可。判断两条线段是否重叠，可先判断它们是否共直线，只要判断一条线段上任意两点是否在另一条线段所在的直线上，或是比较两条线段的方向向量并判断一条线段上任意一点是否在另一条线段所在的直线上。若两条线段不共线，则它们不可能重叠；否则可通过端点坐标的比较来判断两线段的重叠部分。判断两个平面的重叠关系，一种方法是判断一个平面上的不共线三点是否在另一平面上；另一种方法是先比较两个平面的法向量，再判断一个平面上的某点是否在另一平面上。4.5凸包计算一个图形的凸包，就是包含这个图形的一个凸的区域。例如，一个平面图形的凸包可以是一个凸多边形，一个三维物体的凸包可以是一个凸多面体。一个图形的凸包不是唯一的。在进行图形求交计算时，为了减小计算量，经常要在求交之前先进行凸包计算。如果两个图形的凸包不相交，那么显然它们不可能相交，就不必再对它们进行求交了。否则这两个图形有可能相交，需要进一步计算。包围盒是一种特殊而又十分常用的凸包。二维的包围盒是二维平面上的一个矩形，它的两条边分别与两条坐标轴x，y平行，可以表示为两个不等式：，；三维空间中的包围盒是一个长方体，其长、宽、高分别与三条坐标轴平行，表示为三个不等式：，，。两个包围盒相交的充要条件是它们在每一个坐标轴方向上都相交。由于判定两个包围盒的相交情况比较容易，所以包围盒成为最常用的一种凸包。求多边形或多面体的包围盒是相当简便的。只要遍历其所有顶点，就可以找出多边形或多面体在各个坐标轴方向上的最大、最小坐标值，从而确定包围盒。对于已近似化为多边形或多面体的含有曲线曲面的几何体，也可以用同样的方法求出包围盒。对于一般的几何形体，则要根据其具体性质来求取其包围盒。在进行含有曲线、曲面的几何体的求交时，常常先求取它们的一个凸多边形或凸多面体的凸包，由于凸多边形和凸多面体间的求交相对简单，可以节省一定的计算量。例如，Bezier、B样条和NURBS曲线曲面具有凸包性质，其控制多边形或控制网格是其本身的凸包。在进行此类曲线曲面的求交计算时，就常先用其控制多边形或控制网格求交。一般的凸包的求法因具体情况而异，下面举一个求圆弧凸包的例子。设圆弧段的圆方程为，圆弧起始角为，终止角为。对圆弧计算凸包如图4.5所示。先根据起始角与终止角求出相应的弧端点坐标，进而求出弧的弦中点。再用的正、余弦或下式计算弧中点：则该弧的包围盒顶点为。图4.5圆弧的凸包5自由曲线曲面造型技术在计算机图形学中，常用的曲线曲面的类型有：Bezier曲线曲面、B样条曲线曲面、Coons曲面（又称孔斯曲面）以及它们的有理形式。5.1Bezier曲线和曲面5.1.1Bezier曲线1．定义

给定空间n+1个点的位置矢量，则Bezier参数曲线上各点坐标的插值公式是：其中，构成该Bezier曲线的特征多边形，是n次Bernstein基函数：Bezier曲线实例如图5.1所示。图5.1三次Bezier曲线2．Bezier曲线的性质（1）端点性质1曲线端点位置矢量由Bernstein基函数的端点性质可以推得，当时，；当时，。由此可见，Bezier曲线的起点、终点与相应的特征多边形的起点、终点重合。2切矢量因为，其中，所以当时，，当时，，这说明Bezier曲线的起点和终点处的切线方向和特征多边形的第一条边及最后一条边的走向一致。

3二阶导矢，当时，，当时，，表明：2阶导矢只与相邻的3个顶点有关，事实上，r阶导矢只与(r+1)个相邻点有关，与更远点无关。将代入曲率公式，可以得到Bezier曲线在端点的曲率分别为：4阶导函数的差分表示次Bezier曲线的阶导数可用差分公式为：其中高阶向前差分矢量由低阶向前差分矢量递推地定义：（2）对称性。由控制顶点，构造出的新Bezier曲线，与原Bezier曲线形状相同，走向相反。因为：这个性质说明Bezier曲线在起点处有什么几何性质，在终点处也有相同的性质。（3）凸包性由于且，这一结果说明当变化时，对某个值，是特征多边形各项定点的加权平均，权因子依次是。在几何图形上，意味着Bezier曲线在中各点是控制点的凸线性组合，即曲线落在构成的凸包之中，如图5.2所示。图5.2Bezier曲线凸包性（4）几何不变性。

这是指某些几何特性不随坐标变换而变化的特性。Bezier曲线的位置与形状与其特征多边形顶点的位置有关，它不依赖坐标系的选择，即有：（参变量是的置换）（5）变差缩减性。

若Bezier曲线的特征多边形是一个平面图形，则平面内任意直线与P(t)的交点个数不多于该直线与其特征多边形的交点个数，这一性质叫变差缩减性质。此性质反映了Bezier曲线比其特征多边形的波动小，也就是说Bezier曲线比特征多边形的折线更光顺。（6）仿射不变性对于任意的仿射变换：即在仿射变换下，的形式不变。5.1.2Bezier曲面

基于Bezier曲线的讨论，我们可以方便地可以给出Bezier曲面的定义和性质，Bezier曲线的一些算法也可以很容易扩展到Bezier曲面的情况。1.定义设为个空间点列，则次张量积形式的Bezier曲线为：其中是Bernstein基函数，依次用线段连接点列中相邻的两点所形成的空间网络，称之为特征网格。Bezier曲面的矩阵表示式是：在一般实际应用中，不大于4。2．性质除变差减小性质外，Bezier曲线的其它性质可推广到Bezier曲面：（1）Bezier曲面特征网格的四个角点正好是Bezier曲面的四个角点，即。（2）Bezier曲面特征网格最外一圈顶点定义Bezier曲面的四条边界；Bezier曲面边界的跨界切矢只与定义该边界的顶点及相邻一排顶点有关，且、、和（图5.3打上斜线的三角形）；其跨界二阶导矢只与定义该边界的顶点及相邻两排顶点有关。（3）几何不变性。（4）对称性。（5）凸包性。图5.3双三次Bezier曲面及边界信息5.2B样条曲线与曲面以Bernstein基函数构造的Bezier曲线或曲面有许多优越性，但有两点不足：其一是Bezier曲线或曲面不能作局部修改；其二是Bezier曲线或曲面的拼接比较复杂。1972年，Gordon、Riesenfeld等人提出了B样条方法，在保留Bezier方法全部优点的同时，克服了Bezier方法的弱点。5.2.1B样条的递推定义和性质 1．定义

与Bezier曲线得定义方法类似，B样条曲线方程定义为：

其中，是控制多边形的顶点，称为阶(次)B样条基函数，其中每一个称为B样条，它是一个称为节点矢量，即非递减的参数序列所决定的阶分段多项式，也即阶（次)多项式样条。B样条有多种等价定义，在理论上较多地采用截尾幂函数的差商定义。我们只介绍作为标准算法的deBoor-Cox递推定义，又称为deBoor-Cox公式。约定0/0=0。该递推公式表明：欲确定第个阶B样条，需要用到共个节点，称区间为的支承区间。曲线方程中，个控制顶点，要用到个k阶B样条。它们支撑区间的并集定义了这一组B样条基的节点矢量。2．B样条曲线类型的划分

曲线按其首末端点是否重合，区分为闭曲线和开曲线。闭曲线又区分为周期和非周期两种情形，周期闭曲线与非周期闭曲线的区别是：前者在首末端点是C2连续的，而后者一般是C0连续的。非周期闭曲线可以认为是开曲线的特例，按开曲线处理。

B样条曲线按其节点矢量中节点的分布情况，可划分为四种类型。假定控制多边形的顶点为，为阶（次)，则节点矢量是

。

（1）均匀B样条曲线

节点矢量中节点为沿参数轴均匀或等距分布，所有节点区间长度，这样的节点矢量定义了均匀的B样条基。图5.4是均匀B样条曲线实例。图5.4三次均匀的B样条曲线

（2）准均匀的B样条曲线

与均匀B样条曲线的差别在于两端节点具有重复度k，这样的节点矢量定义了准均匀的B样条基。

均匀B样条曲线在曲线定义域内各节点区间上具有用局部参数表示的统一的表达式，使得计算与处理简单方便。但用它定义的均匀B样条曲线没有保留Bezier曲线端点的几何性质，即样条曲线的首末端点不再是控制多边形的首末端点。采用准均匀的B样条曲线就是为了解决这个问题，使曲线在端点的行为有较好的控制，如图5.5所示。图5.5准均匀三次B样条曲线

（3）分段Bezier曲线

节点矢量中两端节点具有重复度k，所有内节点重复度为k-1，这样的节点矢量定义了分段的Bernstein基。

B样条曲线用分段Bezier曲线表示后，各曲线段就具有了相对的独立性，移动曲线段内的一个控制顶点只影响该曲线段的形状，对其它曲线段的形状没有影响。并且Bezier曲线一整套简单有效的算法都可以原封不动地采用。其它三种类型的B样条曲线可通过插入节点的方法转换成分段Bezier曲线类型，缺点是增加了定义曲线的数据，控制顶点数及节点数都将增加。分段Bezier曲线实例如图5.6所示。图5.6三次分段Bezier曲线

（4）非均匀B样条曲线

在这种类型里，任意分布的节点矢量，只要在数学上成立（节点序列非递减，两端节点重复度，内节点重复度）都可选取。这样的节点矢量定义了非均匀B样条基。5.2.2B样条曲线1．局部性由于B样条的局部性，阶B样条曲线上的参数为的一点至多与个控制顶点有关，与其它控制顶点无关；移动该曲线的第个控制顶点至多影响到定义在区间上那部分曲线的形状，对曲线的其余部分不发生影响。2．连续性在重节点处的连续阶不低于。整条曲线的连续阶不低于，其中表示位于区间内的节点的最大重数。3．凸包性在区间，上的部分位于个点的凸包内，整个曲线则位于各凸包的并集之内。4．分段参数多项式在每一区间，上都是次数不高于的参数的多项式，是参数的次分段多项式。

5．导数公式由B样条基的微分差分公式，有：

6．变差缩减性

设平面内个控制顶点构成B样条曲线的特征多边形。在该平面内的任意一条直线与的交点个数不多于该直线和特征多边形的交点个数。

7．几何不变性：B样条曲线的形状和位置与坐标系的选择无关。

8．仿射不变性对任一仿射变换A：

即在仿射变换下，的表达式具有形式不变性。

9．直线保持性

控制多边形退化为一条直线时，曲线也退化为一条直线。

10．造型的灵活性

用B样条曲线可以构造直线段、尖点、切线等特殊情况，如图5.7所示。对于四阶（三次）B样条曲线若要在其中得到一条直线段，只要四点位于同一直线上，此时对应的的曲线即为一条直线，且和所在的直线重合。

为了使能过点，只要使重合，此时过点(尖点)，尖点也可通过三重节点的方法得到，与三重顶点的效果相似。

为了使曲线和某一直线L相切，只要取位于L上及的重数不大于2。图5.7三次B样条曲线的一些特例5.2.5B样条曲面给定参数轴和的节点矢量和，阶B样条曲面定义如下：

是给定的空间个点列，构成一张控制网格，称为B样条曲面的特征网格。和是B样条基，分别由节点矢量和按deBoor-Cox递推公式决定。B样条曲线的一些几何性质可以推广到B样条曲面，图5.8是一张双三次B样条曲面片实例。图5.8双三次B样条曲面片5.3NURBS曲线与曲面B样条方法在表示与设计自由型曲线、曲面形状时显示了强大的威力，然而在表示与设计初等曲线、曲面时却遇到了麻烦。因为B样条曲线（包括其特例的Bezier曲线）都不能精确表示出抛物线外的二次曲线，B样条曲面（包括其特例的Bezier曲面）都不能精确表示出抛物面外的二次曲面，而只能给出近似的表示。提出NURBS方法，即非均匀有理B样条方法，主要是为了找到与描述自由型曲线、曲面的B样条方法既相统一，又能精确表示二次曲线弧与二次曲面的数学方法。NURBS方法的主要优点：（1）既为标准的解析形状(即前面提到的初等曲线曲面)，又为自由型曲线曲面的精确表示与设计提供了一个公共的数学形式。（2）可修改控制顶点和权因子，为各种形状设计提供了充分的灵活性。（3）与B样条方法一样，具有明显的几何解释和强有力的几何配套技术(包括节点插入、细分、升阶等)。

（4）对几何变换和投影变换具有不变性。

（5）非有理B样条、有理与非有理Bezier方法可以处理为它的特例。

不过，目前在应用NURBS方法中，还有一些难以解决的问题：

（1）比传统的曲线曲面定义方法需要更多的存储空间，如空间圆需7个参数(圆心、半径、法矢)，而NURBS定义空间圆需38个参数。

（2）权因子选择不当会引起畸变。（3）对搭接、重叠形状的处理很麻烦。（4）反求曲线、曲面上点参数值的算法不稳定5.3.1NURBS曲线NURBS曲线是由分段有理B样条多项式基函数定义的：其中，称为阶有理基函数；是阶B样条基函数；是特征多边形控制顶点位置矢量；是与对应的权因子，首末权因子，其余，以防止分母为零及保留凸包性质、曲线不因权因子而退化为一点；节点矢量为，节点个数是（为控制项的点数，为B样条基函数的阶数）。对于非周期NURBS曲线，常取两端节点的重复度为，即有：，，分别为个，在大多数实际应用中，。在区间上是一个次有理多项式，在整条曲线上具有阶连续性，对于三次B样条基函数，具有连续性。当时，阶NURBS曲线变成次有理Bezier曲线，阶NURBS曲线的节点矢量中两端节点的节点重复度取成就使得曲线具有同次有理Bezier曲线的端点几何性质。具有阶B样条基函数类似的性质：（1）局部继承性：；（2）权性：；（3）可微性：如果分母不为零，在节点区间内是无限次连续可微的，在节点处次连续可微，是该节点的重复度；（4）若，则；（5）若，则；（6）若，且，则；（7）若，则是B样条基函数；，且（0和1分别有个），则是Bernstein基函数。

与具有类似的性质，导致NURBS曲线与B样条曲线也具有类似的几何性质：（1）局部性质。阶NURBS曲线上参数为的一点至多与个控制顶点及权因子有关，与其它定点与权因子无关；另一方面，若移动次NURBS曲线的一个控制顶点或改变所联系的权因子仅仅影响定义在区间上那部分曲线的形状。（2）变差减小性质。（3）凸包性。定义在非零节点区间上的曲线段位于定义它的个控制顶点Pi-k+1,···,Pi的凸包内。整条NURBS曲线位于所有定义各曲线段的控制顶点的凸包的并集内。所有权因子的非负性，保证了凸包性质的成立。

（4）在仿射与透射变换下的不变性。（5）在曲线定义域内有与有理基函数同样的可微性。（6）如果某个权因子为零，那么相应控制顶点对曲线没有影响。（7）若，则当时，。（8）非有理与有理Bezier曲线和非有理B样条曲线是NURBS曲线的特殊情况。5.3.2非均匀有理B样条（NURBS）曲面1.NURBS曲面的定义由双参数变量、分段有理多项式定义的NURBS曲面是：其中，是矩形域上特征网格控制点列，是相应控制点的权因子，规定四角点处用正权因子，即，其余。和是阶和阶的B样条基函数，是双变量有理基函数：

节点矢量和按deBoor递推公式决定。2.NURBS曲面的性质有理双变量基函数与非有理B样条基函数相类似的性质：（1）局部继承性：，当或；（2）权性：；

（3）可微性：在每个子矩形域内所有偏导数存在，在重复度为的节点处沿向是次连续可微，在重复度为的节点处沿向是次连续可微；

（4）极值：若，恒有一个极大值存在；

（5）是双变量B样条基函数的推广。

NURBS曲面与非有理B样条曲面也有相类似的几何性质，权因子的几何意义及修改、控制顶点的修改等也与NURBS曲线类似，这里不再赘述。5.4Coons曲面

1964年，美国麻省理工学院S.A.Coons提出了一种曲面分片、拼合造型的思想，Bezier曲面和B样条曲面的特点是曲面逼近控制网格，Coons曲面的特点是插值，即通过满足给定的边界条件的方法构造Coons曲面。5.4.1基本概念假定参数曲面方程为，，称为曲面片的四条边界，称为曲面片的四个角点。的向和向求偏导矢：分别称为线和线上的切矢。边界线上的切矢为：同理：也是边界线上的切矢。

边界曲线上的法向(指参数向)偏导矢：称为边界曲线的跨界切矢，同理，也是边界曲线的跨界切矢。称为角点的向和向切矢，在曲线片的每个角点上都有两个这样的切矢量。称为混合偏导矢或扭矢，它