《计算机图形学各种算法的作业(偏于理论)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
计算机图形学算法基础作业名院业间姓学专时LH理学院计算数学2010-12-31
1目录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中点ifflj线算法流程图31.4生成直线算法的进一步改进51.5各种直线生成算法的优缺点对比分析61.6直线生成算法的发展趋势7
22椭圆的Bresenham生成算法72.1椭圆曲率分析72.2椭圆方程分析72.3椭圆生成算法92.3.1算法实现过程92.3.2算法流程图102.3.3算法程序描述113直线段裁剪算法综述113.1Sutherland-Cohen裁剪算法111.1.11.1Sutherland-Cohen算法基本原理111.1.2Sutherland-Cohen算法实现步骤111.1.3算法程序（或伪程序）描述121.1.4算法流程图123.2中点分割裁剪算法123.2.1中点分割算法基本原理与实现步骤124.2.2算法程序（或伪程序）描述135.2.3算法流程图133.3梁友栋一Barskey算法143.3.1梁友栋一Barskey算法基本原理与实现步骤144.3.2算法程序（或伪程序）描述155.3.3算法流程图15
33.4快速算法153.5其余一些改进的直线裁剪算法163.6各种直线裁剪算法的优缺点对比分析163.7直线裁剪算法的发展趋势164图形求交技术164.1求交点算法164.1.1线与线的交点的求法174.2.2线与面的交点的求法184.2求交线算法194.3包含判定算法214.4重叠判定算法263.5凸包计算265自由曲线曲面造型技术284.1Bezier[H]/口[U][6].........................................................285.1.1Bezier曲线285.1.2Bezier曲面315.2B样条曲线与曲面325.2.1B样条的递推定义和性质325.2.2B样条曲线345.2.5B样条曲面36
45.3NURBS曲线与曲面375.3.1NURBS曲线375.3.2非均匀有理B样条(NURBS)曲面395.4Coons曲面405.4.1基本概念405.4.2双线性Coons曲面415.4.3双三次Coons曲面426CAGD中有关曲线曲面C“、G”拼接技术446.1基本原理446.2Bezier曲线的C。、G。、CPGPC2^G2的拼接条件446.3Bezier曲面的C。、G。、CPG1的拼接条件467图形变换技术487.1二维图形几何变换497.1.1平移(Translation)497.2三维图形几何变换517.2.1平移517.2.3变比547.3参数图形几何变换54
57.3.1圆锥曲线的几何变换547.3.2参数曲线、曲面的几何变换557.4投影变换587.4.1平行投影(paral1e1projection)587.4.2透视投影(perspectiveprojection)608图形消隐算法618.1扫描线Z-buffer算法618.2区域子分割算法618.3光线投射算法628.4平面公式法628.5径向预排序法638.7隔离平面法638.8深度排序法638.9光线跟踪法638.10Z缓冲区法648.12深度分类方法648.13八叉树方法659图形学若干基本算法的实现研究65参考文献68
6附录68
7图形学算法基础作业1直线段生成算法综述1.1生成直线的DDA方法1.1.1DDA算法基本原理DDA是数字微分分析式（DigitalDifferentialAnalyzer）的缩写。设直线之起点为（x”力）,终点为（X2，y2），则斜率k为：k_y2-y,_dyx2-X]dx直线中的每一点坐标都可以由前一点坐标变化一个增量（D「Dy）而得到，即表示为递归式：Xj+1=Xj+DxYi+1=Yi+Dy并有关系：D=mXDyA递归式的初值为直线的起点（X,力）,这样，就可以用加法来生成一条直线。1.1.2DDA算法实现步骤具体方法是：按照直线从（x”y）到（X2，y2）的方向不同，分为8个象限（见图1.1）。对于方向在第la象限内的直线而言，Dx=l,Dy=m。对于方向在第1b象限内的直线而言，取值Dy=1,Dx=l/m0各象限中直线生成时D、，D,.的JAAJ取值列在表之中。图1.1直线方向的8个象限图表1-1各象限中直线生成时D、，Dy的取值列象限|dx|〉|dy|?D1t°，
8laT1m1bF1/m12aT-1m2bF-1/m13aT-1-m3bF-1/m-14aT1-m4bF1/m-1研究表中的数据，可以发现两个规律：1、当|dx|>|dy|时|Dx|=l」Dj=m；否则：Dx=l/m,|Dy|=l2、Dx，Dy的符号与dx,dy的符号相同。这两条规律可以导致程序的简化。由上述方法写成的程序如附录1所示。其中steps变量的设置，以及D*=dx/steps;Dy=dy/steps等语句，正是利用了上述两条规律，使得程序变得简练。使用DDA算法，每生成一条直线做两次除法，每画线中一点做两次加法。因此，用DDA法生成直线的速度是相当快的。1.1.1DDA算法程序(或伪程序)描述具体程序见附录lo1.1.2DDA算法流程图(略)1.2中点画线算法1.2.1中点画线算法基本原理假定直线斜率k在。1之间，当前象素点为(xp,yp),则下一个象素点有两种可选择点R(Xp+l4)或P2(xp+l,yp+l)o若R与P?的中点3+1*+0.5)称为M,Q为理想直线与x=Xp+l垂线的交点。当M在Q的下方时，则取P2应为下一个象素点；当M在Q的上方时，则取R为下一个象素点。这就是中点画线法的基本原理。1.2.2中点画线算法实现步骤下面讨论中点画线法的实现。过点(x0,y0)>(x“yj的直线段L的方程式为F(x,y)=ax+by+c=O,其中a=y0-y,,b=x0-X1,c=x0y]-xm，要判断中点M在Q
9点的上方还是下方，只要把M代入F(x,y),并判断它的符号即可。为此，我们构造判别式：d=F(M)=F(xp+1,yp+0.5)=a(xp+l)+b(yp+0.5)+c当d<0时，M在L(Q点)下方，取P?为下一个象素；当d>0时，M在L(Q点)上方，取R为下一个象素；当d=0时，选R或P2均可，约定取R为下一个象素。注意到d是Xp,y0的线性函数，可采用增量计算，提高运算效率。若当前象素处于d〉0情况，则取正右方象素耳(Xp+1*),要判下一个象素位置，应计算4=F(xp+2,yp+0.5)=a(xp+2)+b(yp+0.5)+c=d+a,增量为a。若d<0时，则取右上方象素P2(Xp+l*+l)。要判断再下一象素，则要计算d2=F(xp+2,yp+1.5)=a(xp+2)+b(yp+1.5)+c=d+a+b,增量为a+bo画线从(x0,y0)开始，d的初值d0=F(x0+1,y0+0.5)=F(x0,y0)+a+0.5b♦因F(xo,yo)=O,所以d0=a+0.5b0由于我们使用的只是d的符号，而且d的增量都是整数，只是初始值包含小数。因此，我们可以用2d代替d来摆脱小数，写出仅包含整数运算的算法程序。1.2.3中点画线算法程序(或伪程序)描述具体程序见附录21.2.4中点画线算法流程图(略)1.3生成直线的Bresenham算法1.1.1Bresenham算法基本原理本算法由Bresenham在1965年提出。设直线从起点(x“力)到终点(x2,y2)o直线可表示为方程y=kx+b。其中b=y,-k-x1k=y^-y.-空X2-X!dx我们讨论先将直线方向限于la象限(图1.1)在这种情况下，当直线光栅化时，x每次都增加1个单元，即Xj+l=Xj+l。而y的相应增加应当小于1。为了光栅化，％+1只可能选择如图1.2两种位置之一。
10图1.2%+1的位置选择图1.2中yi+1的位置选择丫广1=yi或者Yj+1=Yj+1选择的原则是看精确值y与％及Yi+1的距离d1及d2的大小而定。计算式为：y=m(Xj+1)+b(1.2.1)dl=y-yi(1.2.2)d2=Yj+1-y(1.2.3)如果dl-d2>0,则为+l=yi+l,否则y+l=yi。因此算法的关键在于简便地求出dl-d2的符号。将式(1.2.1)、(1.2.2)、(1.2.3)代入dl-d2,得dl-d2=2y-2yj-l=2—(xi+l)-2yi+2b-l用dx乘等式两边，并以R=dx(dl-d2)代入上述等式，得R=2Xjdy-2yjdx+2dy+dx(2b-l)(1.2.4)dl-d2是我们用以判断符号的误差。由于在la象限，dx总大于0,所以P,仍旧可以用作判断符号的误差。R+1为：P,+l=P,+2dy-2dx(yj+l-yi)(1.2.5)误差的初值Pl,可将xl,yl,和b代入式(2.1.4)中的xi,yi而得至kP,=2dy-dx1.3.2Bresenham算法实现步骤综述上面1.3.1的推导，第la象限内的直线Bresenham算法思想如下：1、画点（xl,y2）;dx=x2-xl;dy=y2-yl；计算误差初值Pl=2dy-dx;i=1；2、求直线的下一点位置：xi+l=xi+l；ifPi>0则yi+l=yi+l；否则yi+l=yi；3,画点（xi+1,yi-1）；
114、求下一个误差Pi+1；ifPi>0则Pi+l=Pi+2dy-2dx;否则Pi+l=Pi+2dy；5、i=i+l;ifi
12从以上的描述可以实现优于Bresenham的直线生成算法。其中待生成直线的已知数据为：（x,yj为线段起点的横、纵坐标；a2»2）为线段终点的横、纵坐标。算法的输人数据为：（x”yj,（x2,y2）o（3）基于类最佳逼近的散步直线生成算法。一种新的直线逼近方法一类最佳逼近，基于这种逼近方法，斜率ke[0,0.5）的直线和斜率为1-k的直线具有某种互补性质。利用该性质，设计出一种新的三步直线方法，该算法揭示了直线计算的互补性，理论简单，精度达到最好。这种算法改善了Bresenham算法和双步算法的计算效率。该算法对于硬件实现将更有益处。除此之外直线生成算法还有对称扫描四步增量画线算法、基于Bresenham的高效直线生成集成算法、基于Bresenham算法的四步画直线算法、基于直线特性的直线生成集成算法、基于自适应步长的直线生成算法、基于等分像素点的直线生成算法、6步直线生成算法、基于对角线行程的直线生成算法等等。1.4各种直线生成算法的优缺点对比分析DDA算法的优点是：绘制实数直线效果好，误差小；缺点是：实现较复杂，不利于硬件实现。因为该算法涉及到实数乘除法运算，y与k必须用浮点数表示，而且每一步都要对y四舍五入后取整。中点画线算法优点是：只有整数运算，不含乘除法；可用硬件实现。Bresenham算法的优点是：1、不必计算直线之斜率，因此不做除法；2、不用浮点数，只用整数；3、只做整数加减法和乘2运算，而乘2运算可以用硬件移位实现。4、Bresenham算法速度很快，并适于用硬件实现。1.5直线生成算法的发展趋势（略）2椭圆的Bresenham生成算法2.1椭圆曲率分析椭圆r={acost,bsint}（。为沿％轴方向的长半轴长度，。为沿y轴
13方向的短半轴长度，且。＞匕），曲率为/=ab/（/sin2/+b2cos2/严，在第一象限，«0,乃/2）,将（对，求导数，有啊/dr＜0,即曲率为减函数，在点Q0）（即r=0）处的曲率（g）=。/〃；在点（0,b）（即1=乃/2）处的曲率（（s/2）=b//。半径为。的圆的曲率为4//,半径为Z?的圆的曲率为6//,两圆的曲率关系为匕//＞。//仅＞。），则两圆的曲率在椭圆上点（。,0）与（0向的曲率之间，四者的关系为：alb2＞\lb＞\la＞bla\2.2椭圆方程分析根据椭圆及圆的曲率分析，椭圆弧分别由半径为。和人的圆弧逼近生成。为了更准确的由圆弧生成椭圆弧，在椭圆弧上确定一点P。，将椭圆弧分成曲率较小和曲率较大的两段，椭圆方程为：F（X,y）=Z?2X2+♦--a2b2=0o其中。为沿x轴方向的长半轴长度，。为沿y轴方向的短半轴长度，且。＞匕＞0。由于椭圆的对称性，这里只要讨论第一象限椭圆弧的生成。将椭圆弧分为上下两部分，以弧上曲率为-1的点(即法向量两个分量相等的点)作为分界。该椭圆上一点(x,y)处的法向量为：AFaFN(x,y)=—i+—j=2b2xi+2a2yjdxdy结合椭圆方程可计算出分界点P°的坐标为：(a2/yla2+b2,b2/y]a2+b2)o以P0点为分界点，将第一象限的圆弧分成曲率较大和较小的两段弧。如图2.1所示，ye厅/后寿■向的椭圆弧，与半径为。的圆在点工。。)到T2(a2/y]a2+b2,ab/y/a2+b2)的圆弧上对应。在椭圆弧上任取一点Qi，过Q1作垂直线与圆交于R点，连接圆心与R点，与Y轴的夹角为0。则
14椭圆的参数方程可表示为：x=asinO,y=/?cos0.圆的参数方程可表示为：x=asinO,Vy=acosO.对于同一0,椭圆弧上存在唯一的点与圆弧上的点对应，并且对应点的坐标存在如下关系：X=X,y'=(b/a)y.图2.1圆弧与椭圆弧对应点之一图2.2圆弧与椭圆弧对应点之一如图2.2所示，半径为。的圆上，从点/"T了',//庐了')到T4(Z>,0)的圆弧与椭圆上ye(0,b2/-Ja2+b2)的椭圆弧对应，在椭圆弧上任取一点Q?，过Q2作垂直线与圆交于P2点，连接圆心与P?点，与丫轴的夹角为6。则椭圆的参数方程可表示为：x=asin9,y=hcosQ.圆的参数方程可表示为：x=〃sinO,Vy=bcosQ.
15对于同一e,椭圆弧上存在唯一的点与圆弧上的点对应，并且对应点的坐标存在如下关系：rIx=(a/b)x,Vy=y-2.3椭圆生成算法当圆弧上的点从(a,0)沿着图2.1、图2.2的对应关系方向变化到(仇0)时，椭圆弧上相对应的点也从该方向变化到(a,0)。2.3.1算法实现过程1、计算分界点P„(x0,y0)o2、用Bresenham算法生成两段圆弧G、C2oG半径为a,xe[0,a2/sla2+b2]；C2半径为b,ye[0,b2/y/a2+b2]o3、将圆弧g进行比例变换：%方向的比例系数为1,y方向的比例系数为0/。；将圆弧C2进行比例变换：X方向的比例系数为y方向的比例系数为io
164、如图2.3,已知椭圆上在第一象限的点Q(x,y),则椭圆上另外三个象限与Q(x,y)点对称的点分别为(-X,y),(-x,-y),(x,-y),因此只要画出在第一象限的图形，即可得到整个椭圆的图形。图2.3椭圆对称性2.3.1算法流程图椭圆的Bresenham算法流程图如下：图2.4椭圆的Bresenham算法流程图
172.3.1算法程序描述具体程序实现见附录5o3直线段裁剪算法综述裁剪：确定图形中哪些部分落在显示区之内，哪些落在显示区之外，以便只显示落在显示区内的那部分图形。这个选择过程称为裁剪。直线段裁剪算法是复杂图元裁剪的基础。复杂的曲线可以通过折线段来近似，从而裁剪问题也可以化为直线段的裁剪问题。3.1SutherIand-Cohen裁剪算法3.1.1SutherIand-Cohen算法基本原理Sutherland-Cohen算法分成两步。第•步是判断直线段是否完全在窗口内，若在则该线段称为完全可见的；或可显然的决定线段完全在窗口的外边，称为完全不可见；对不能判断完全可见或完全不可见的线段则要进行第二步处理。这时需要计算出直线段和窗口边界的一个交点，这个交点把直线分成两段，把其中一段显然完全不可见的线段抛弃，对余下的部分再作第一步判断，重复上述过程，直到直线段最后余下的部分可以用第一步的判断得出肯定结论为止。3.1.2SutherIand-Cohen算法实现步骤基本思想：对于每条线段P1P2分为三种情况处理分为三种情况处理：（1）若P/2完全在窗口内，则显示该线段P/2，简称“取"之。（2）若PR2明显在窗口外，则丢弃该线段，简称“弃”之。（3）若线段不满足“取”或“弃”的条件，则在交点处把线段分为两段。其中一段完全在窗口外，可弃之。然后对另一段重复上述处理。为快速判断，采用如下编码方法：每个区域赋予4位编码（如图3.1所示）：c,chcrc,其中：y>ymaxothero1y 18图3.2线段不能用编码确定code2=0,则“取”2W0,则“弃”一段完全在窗口外，可弃之。然后图3.1区域编码若PQ完全在窗口内codel=0,且若P1P2明显在窗口外codel&code在交点处把线段分为两段。其中对另一段重复上述处理。计算线段5（%,必况/，%）与窗口边界的交点if（LEFT&code!=0）{x=XL;y=y1+(y2-y1)*(XL-xl)/(x2-xl);}elseif(RIGHT&code!=0){x=XR;y=yl+(y2-yl)*(XR-xl)/(x2-xl);}elseif(BOTTOM&code!=0){y=YB;x=xl+(x2-xl)*(YB-y1)/(y2-yl);}elseif(TOP&code!=0){y=YT;x=xl+(x2-xl)*(YT-y1)/(y2-yl);}3.1.1算法程序（或伪程序）描述过程clip描述了这一算法。其中用一个集合（top,bottom,right』eft）来表示端点的编码。具体程序见附录6。2.1.4算法流程图（略）3.2中点分割裁剪算法4.2.1中点分割算法基本原理与实现步骤与前一种Cohen-Sutherland算法一样首先对线段端点进行编码，并把线段与窗口的关系分为三种情况：完全可见、完全不可见和线段与窗口有交。对前两种情况，进行一样的处理。对于第三种情况，用中点分割的方法求出线段与窗口的交点。求线段与窗口的交点如下： 19设要裁剪的线段是P°Pj中点分割算法可分成两个过程平行进行，即从P。出发找出离P。最近的可见点（图3.3中的A点），和从耳出发找出离耳最近的可见点（图3.3中的B点）。这两个最近可见点的连线就是原线段的可见部分。从P。出发找出最近可见点的办法是先求P°R的中点匕，若P°Pm不能定为显然不可见，则取P0Pm代替P°R,否则取PmR代替P（）P,，再对新的P°R求中点匕。重复上述过程，直到P|Pm长度小于给定的小数£为止。图3.4是求P。的最近可见点P的算法框图。求R的最近可见点的算法框图是一样的，只要把P。和R交换即可。在显示时£可取成一个像素的宽度，对分辨率为2Nx2N的显示器来说，上面讲的二分的过程最多只要做N次。由于计算机过程只要做加法和除2,所以特别适合用硬件来实现。如果允许两个找最近点的过程平行进行，这样的话可使裁剪速度加快，增加算法效率。图3.3中点分割算法3.2.2算法程序（或伪程序）描述具体程序见附录7o3.2.3算法流程图中点分割算法框图如图3.4o 20图3.4中点分割算法框图3.3梁友栋一Barskey算法3.3.1梁友栋一Barskey算法基本原理与实现步骤设要裁剪的线段是P°Pi，R的坐标是（Xi，yJ,i=O/。P°R和窗口边界交于A、B、C、D四点，见图3.5。算法基本思想是从A,B和P。三点中找出最靠近R的点，图3.5中要找的点是P。，从C,D和R三点中找出最靠近P。的点，图3.5中要找的点是C点。那么P°C就是P°R上的可见部分。图3.5P°C是可见部分具体计算时要把P°R写成参数方程 21x=x0+Axt、y=y（）+Ayt其中以=*1-*0，力=%70。把窗口边界的四条边分成两类，一类称为始边，另一类称为终边。参数化形式写出裁剪条件：XL 22除过前面所讲到的4种基本直线裁剪算法外，还有一些其它的裁剪方法，由于过多，这里仅列举儿种如下：(1)具有最少算术运算量的二维线裁剪算法。见文献：王骏，梁友栋，彭群生，具有最少算术运算量的二维线裁剪，《计算机学报》，1991年第7期。(2)一个有效的多边形窗口的线裁剪算法。见文献：刘勇奎等，一个有效的多边形窗口的线裁剪，《计算机学报》，1999年第11期。(3)一种基于儿何变换的高效的线裁剪新算法。见文献：汪乱，吴锐迅，蔡士杰。一种基于几何变换的高效的线裁剪新算法。《软件学报》，1998,9(10):728-733。(4)任意多边形窗口的线裁剪算法。见文献：孙岩，唐棣：任意多边形窗口的线裁剪，《2000年图形学会议专刊))。3.5各种直线裁剪算法的优缺点对比分析Sutherland-Cohen直线裁剪算法要计算直线段与窗口边界的交点，这不可避免地要进行大量的乘除运算，必会降低程序的执行效率。而中点分割裁剪算法却只需用到加法和除2运算，而除2运算在计算机中可以简单地用右移一位来实现，从而提高算法的效率。所以特别适合硬件实现，同时也适合于并行计算。3.6直线裁剪算法的发展趋势(略)4图形求交技术4.1求交点算法求交点可以分两种情况：求线与线的交点以及求线与面的交点。4.1.1线与线的交点的求法1、直线段与直线段的交点假设二条直线的端点分别为Pl,P2,QI,Q2,则它们可以用向量形式表示为：P(t)=A+Bt(0 23对三维空间中的直线段来说，上述方程实际上是一个二元一次方程组，由三个方程式组成。可以从其中两个解出s,t,再用第三个验证解的有效性：若第三个方程成立则说明找到了解，否则说明两条直线不相交。当所得的解(tj,Sj)是有效解时，可用二个线段方程之一计算交点坐标，例如P(tJ=A+Bt,。我们还可以根据向量的基本性质，直接计算s与t：对(4.1.1)两边构造点积得(CXD)(A+Bt)=(CXD)(C+Ds)由于CXD同时垂直于C和D,等式右边为零。故有(CxD)A--(CxD)B类似地有(AxB)C3.(AxB)D完整的算法还应判断无解与无穷多解(共线)的情形，以及考虑数值计算误差造成的影响。2、直线段与二次曲线的交点不失一般性，考虑平面上一条直线与同平面的一条二次曲线的交。假设曲线方程为f(x,y)=0,直线段方程为(x,y)=(X]+tdx,y|+tdy),则在交点处有f(X]+tdx,y]+tdy)=O。当曲线为二次曲线时，上述方程可写为at2+bt+c=O用二次方程求根公式即可解出t值。3、圆锥曲线与圆锥曲线的交点圆锥曲线有代数法表示、几何法表示与参数法表示。在进行一对圆锥曲线的求交时，把其中一条圆锥曲线用代数/几何法表示为隐函数形式，另一条表示为参数形式(如二次NURBS曲线)。将参数形式代入隐函数形式可得关于参数的四次方程，可以使用四次方程的求根公式解出交点参数。得到交点后可再验证交点是否在有效的圆锥曲线段上。4.2.2线与面的交点的求法1、直线段与平面的交点(如图4.1) 24图4.1线段与平面求交考虑直线段与无界平面的求交问题。把平面上的点表示为P(u,w)=A+uB+wC,直线段上的点表示为Q(t)=D+tE,二者的交点记为R-假设线段不平行于平面，则它们交于R=P(u,w)=Q(t),即A+uB+wC=D+tE等式两边点乘(BXC),得(BXC)(A+uB+wC)=(BXC)(D+tE)由于BXC既垂直于B,又垂直于C,故有(BXC)A=(BXC)(D+tE)可解出(BxC)A-(BxC)D(BxC)E类似求得（CxE）D-（CxE）A（CxE）B（BxE）D-（BxE）Aco=（BxE）C如果是直线与平面区域求交点，则要进一步判断点是否在平面上的有效区域中，其算法可参见4.2节。2、圆锥曲线与平面的交点圆锥曲线与平面求交时，可以把圆锥曲线表示为参数形式，并把圆锥曲线的参数形式代入平面方程，即可得到参数的二次方程进行求解。 253、圆锥曲线与二次曲面的交点圆锥曲线与二次曲面求交时，可把圆锥曲线的参数形式代入二次曲面的隐式方程，得到参数的四次方程，用求根公式求解。4.2求交线算法求交线显然是指求面与面的交线，下面讨论几种常见的情况。1、平面与平面的交线在CAD中一般使用平面上有界区域。先考虑最简单的情形。两个平面区域分别由P（u,w）,Q（s,t）,u,w,s,tc[O』定义。如果它们不共面而且不分离，则必交于一直线段。这条直线必落在P（u,w）-Q（s,t）=O所定义的无限直线上。注意这是个含有四个未知数，三个方程式的方程组，只要分别与八条边界线方程：u=0,u=l,w=O,w=l,s=O,s=l,t=O,t=l联立，即可求出线段的两个端点的参数。在上述方程组中，只要找到两组解，就可以不再对剩余其它方程组求解。找到的两组解就是所求的交线段端点参数。当两个一般的多边形（即既可能是凸的，也可能是凹的，甚至可能带有内孔）相交时，可能有多段交线。我们可以把两个多边形分别记为A和B,用如下的算法求出它们的交线：（1）把A的所有边与B求交，求出所有有效交点；（2）把B的所有边与A求交，求出所有有效交点；（3）把所有交点先按y,再按x的大小进行排序；（4）把每对交点的中点与A和B进行包含性检测，若该中点即在A中又在B中，则该对交点定义了一条交线段。2、平面与二次曲面的交线求平面与二次曲面的交线有两种方法：代数法和几何法。用代数法考虑平面与二次曲面求交问题时，可以把二次曲面表示为代数形式：Ax2+By2+Cz2+2Dxy+2Eyz+2Fxz+2Gx+2Hy+2Iz+J=0可以通过平移与旋转坐标变换把平面变为XOY平面，对二次曲面进行同样的坐标变换。由于在新坐标系下平面的方程为z=0,所以新坐标系下二次曲面方程中，把含z项都去掉即为平面与二次曲面的交线方程（在新坐标系下）。对该交线方程进行一次逆坐标变换即可获得在原坐标系下的交线方程。在具体实现时，交线可以用二元二次方程系数表示（代数表示），辅之以局部坐标系到用户坐标系的变换矩阵。这种方法的缺点是，每当需要使用这些交线时，都要进行坐标变换。例如，判断一个空间点是否在交线上，必须先对它进行坐标变换，变到z=0平面上，再进行检测。需要绘制该交线时，也要先在局部坐标系下求出点坐标，再 26变换到用户坐标系下的坐标。所以交线采用另一种方法（几何表示）更合理。几何方法存储曲线的类型（椭圆、抛物线或双曲线），以及定义参数（中心点、对称轴、半径等大小尺寸）的数值信息，使用局部坐标系到用户坐标系的变换，把局部坐标系下的定义参数变换到用户坐标系直接使用。这第二种方法使用较少的变换，但需要用计算来判断曲线的种类，及计算曲线的定义参数。由于浮点运算的不精确性，容易发生判错类型以及定义参数误差过大的问题。当平面与二次曲面的交线需要精确表示时，往往采用几何法求交。二次曲面采用几何表示，平面与二次曲面求交时，根据它们的相对位置与角度（根据定义参数），直接判断交线类型，其准确性大大优于用代数法计算分类的方法。几何法不需要对面进行变换，所以只要通过很少的计算就可以得到交线的精确描述。由于存储的信息是具有几何意义的，所以判断相等性、相对性等问题时，可以确定有几何意义的容差。下面以平面一球求交为例，说明几何法求交算法。平面用Is*记录P表示，P的两子域p.b,p.w分别代表平面上一点与平面法向量。球面用记录s表示。它的两个子域s.c,s.r分别代表球面中心和半径。则可写出平面与球面相交的算法如下：plane_sphere_intersect（p,s）planep;spheres;£1=球面中心到平面的有向距离；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、平面与参数曲面的交线 27最简单的方法是把参数曲面的表示(X(S,t),丫($/),2k,。)代入平面方程ax+by+cz+d=0得到用参数曲面的参数s、t表示的交线方程ax(s,t)+by(s,t)+cz(s,t)+d=0另一种方法是用平移和旋转变换对平面进行坐标变换，使平面成为新坐标系下的xoy平面。再用相同的变换应用于参数曲面方程得到参数曲面在新坐标系下的方程(x*,y*,z*)=(x*(s,t),y*(s,t),z*(s,t))由此得交线在新坐标系下的方程为z*(s,t)=O。4.3包含判定算法在进行图形求交时，常常需要判定两个图形间是否有包含关系。如点是否包含在线段、平面区域、三维形体中，线段是否包含在平面区域、三维形体中，等等。许多包含判定问题可转化为点的包含判定问题，如判断线段是否在平面上可以转化为判断其两端点是否在平面上。因此下面主要讨论关于点的包含判定算法。判断点与线段的包含关系，也就是判断点与线的最短距离是否位于容差范围内。造型中常用的线段有三种：1、直线段；2、圆锥曲线段（主要是圆弧）；3、参数曲线（主要是Bezier,B样条与NURBS曲线）。点与面的包含判定也类似地分为三种情况。下面分别讨论。1、点与直线段的包含判定假设点坐标为P（x,y,z）,直线段端点为P1（x”yi，zJ,P2（x2,y2,z2）,则点P到线段PR的距离的平方为d2=(x-x1)2+(y-yl)2+(z-z1)2[(X2-xJ(x-xJ+(y2-yJ(y—yJ+(Z2-zJ(z-zjT[(x2-x,)2+(y2-y1)2+(z2-z,)2]当d2=0时，认为点在线段（或其延长线）上，这时还需进一步判断点是否落在直线段的有效区间内。只要对坐标分量进行比较，假设线段两端点的x分量不等（否则所有分量均相等，那么线段两端点重合，线段退化为一点），那么当X-X1与X-X2反号时，点P在线段的有效区间内。2、点与圆锥曲线段的包含判定 28以圆弧为例，假设点的坐标为（x,y,z）,圆弧的中心为（x0,yo，Zo）,半径为r,起始角四，终止角%。这些角度都是相对于局部坐标系x轴而言。圆弧所在平面为ax+by+cz+d=0先判断点是否在该平面上，若不在，则点不可能被包含。若在，则通过坐标变换，把问题转换到二维的问题。给定中心为（X。，y。），半径为r,起始角终止角巴的圆弧，对平面上一点P（x,y）,判断P是否在圆弧上，可分二步进行。第一步判断P是否在圆心为（x0,y。），半径为r的圆的圆周上，即下式是否成立：7（x-x0）2+（y-y0）2-r<£第二步判断P是否在有效的圆弧段内。3、点与参数曲线的包含判定设点坐标为P（x,y,z）,参数曲线为Q（t）=（x（t）,y（t）,z（t））。点也参数曲线的求交计算包括三个步骤：(1)计算参数t值，使P到Q⑴的距离最小；(2)判断t是否在有效参数区间内(通常为[0,1])；(3)判断Q⑴与P的距离是否小于£o若(2),(3)步的判断均为“是”，则点在曲线上：否则点不在曲线上。第一步应计算t,使得|P-Q⑴|最小，即R(t)=(P-Q(t*P-Q⑴)="Q(t)『最小根据微积分知识，在该处R'(t)=0即Q,(t)[P-Q(t)]=0用数值方法解出t值，再代入曲线参数方程可求出曲线上对应点的坐标。第(2)、(3)步的处理比较简单，不再详述。4、点与平面区域的包含判定设点坐标为P(x,y,z),平面方程为ax+by+cz+d=0。则点到平面的距离为|ax+by+cz+d|7a2+b2+c2 29若r<£,则认为点在平面上，否则认为点不在平面上。在造型系统中，通常使用平面上的有界区域作为形体的表面。在这种情况下，对落在平面上的点还应进一步判别它是否落在有效区域内。若点落在该区域内，则认为点与该面相交，否则不相交。下面以平面区域多边形为例，介绍有关算法。判断平面上一个点是否包含在同平面的一个多边形内，有许多种算法，这里仅介绍常用的三种：叉积判断法、夹角之和检验法以及交点计数检验法。(1)叉积判断法假设判断点为P。。多边形顶点按顺序排列为PR…P/如图4.2所示。令Y=P,-P0,i=l,2,…，n,Vn+1=Y。那么，P0在多边形内的充要条件是叉积Y、X、Y+l(i=1,2,…，n)的符号相同。叉积判断法仅适用于凸多边形。当多边形为凹时，尽管点在多边形内也不能保证上述叉积符号都相同。这时可采用后面介绍的两种方法。 30图4.2叉积判断法(2)夹角之和检验法假设某平面上有点P。和多边形PRPF4P5，如图4.3所示。将点P。分别与匕相连，构成向量Y=p-Po。假设角p,p0p,+i=a。如果£/=0,则»=1点P。在多边形之外，如图4.3(a)所示。如果£%=2万，则点P。在多边形之内，如图4.3(b)所示。6可通过下列公式计算：令Sj=V,XV,+l,Ci=YY+l,则tg(aJ=Si/q，所以％=arctg(&/CJ且%的符号即代表角度的方向。P2(b)Za=2兀的情况图4.3夹角之和检验法在多边形边数不太多(<44)的情况下，可以采用下列近似公式计算必=7c+d,lS,l-lCib%=产”|s,|>|c,|.其中d=0.0355573为常数。当》时，可判此在多边形内。当Z%〈乃时，可判P。在多边形外。证明略。(3)交点计数检验法 31当多边形是凹多边形，甚至还带孔时，可采用交点计数法判断点是否在多边形内。具体做法是，从判断点作•射线至无穷远：(x=x0+u(u>0)|y=yo求射线与多边形边的交点个数。若个数为奇数，则点在多边形内，否则，点在多边形外。如图4.4所示，射线a,c分别与多边形交于二点和四点，为偶数，故判断点A,C在多边形外。而射线b,d与多边形交三点和一点，为奇数，所以B,D在多边形内。当射线穿过多边形顶点时，必须特殊对待。如图2.5.4所示，射线f过顶点，若将交点计数为2,则会错误地判断F在多边形外。但是，若规定射线过顶点时，计数为1,则又会错误地判断点E在多边形内。正确的方法是，若共享顶点的两边在射线的同一侧，则交点计数加2,否则加1。按这种方法，E点计为2,所以在多边形外；F点计数为1,所以在多边形内。5、点与二次曲面/参数曲面的包含判定假设点坐标为P(x0,y0,z0),二次曲面方程为Q(x,y,z)=0,则当|Q(x0,y0,z0)| 32于是要检验一个点是否在凸多面体内部，只要检验是否它对凸多面体的每一个面均满足以上的不等式即可。4.4重叠判定算法进行求交计算时，常涉及判断两个几何形体是否重叠。下面讨论儿种常见的情况。判断空间一点与另一点是否重叠，只要判断两点之间的距离是否小于0即可。判断两条线段是否重叠，可先判断它们是否共直线，只要判断一条线段上任意两点是否在另一条线段所在的直线上，或是比较两条线段的方向向量并判断一条线段上任意一点是否在另一条线段所在的直线上。若两条线段不共线，则它们不可能重叠；否则可通过端点坐标的比较来判断两线段的重叠部分。判断两个平面的重叠关系，一种方法是判断一个平面上的不共线三点是否在另一平面上；另一种方法是先比较两个平面的法向量，再判断一个平面上的某点是否在另一平面上。5.5凸包计算一个图形的凸包，就是包含这个图形的一个凸的区域。例如，一个平面图形的凸包可以是一个凸多边形，一个三维物体的凸包可以是一个凸多面体。一个图形的凸包不是唯一的。在进行图形求交计算时，为了减小计算量，经常要在求交之前先进行凸包计算。如果两个图形的凸包不相交，那么显然它们不可能相交，就不必再对它们进行求交了。否则这两个图形有可能相交，需要进一步计算。包围盒是一种特殊而又十分常用的凸包。二维的包围盒是二维平面上的一个矩形，它的两条边分别与两条坐标轴X,y平行，可以表示为两个不等式：Xmjn 33多边形或控制网格是其本身的凸包。在进行此类曲线曲面的求交计算时，就常先用其控制多边形或控制网格求交。一般的凸包的求法因具体情况而异，下面举一个求圆弧凸包的例子。设圆弧段的圆方程为（x-x0）2+（y-y0）2=r2,圆弧起始角为名,终止角为。2。对圆弧计算凸包如图4.5所示。先根据起始角％与终止角求出相应的弧端点坐标耳，「2，进而求出弧的弦中点匕=（耳+巳）/2。再用（q1+q2）/2的正、余弦或下式计算弧中点R：1+酊则该弧的包围盒顶点为P『R+（P「Pm）尸2+（巳匕）上。图4.5圆弧的凸包5自由曲线曲面造型技术在计算机图形学中，常用的曲线曲面的类型有：Bezier曲线曲面、B样条曲线曲面、Coons曲面(又称孔斯曲面)以及它们的有理形式。4.1Bezier曲线和曲面5.1.1Bezier曲线1.定义给定空间n+1个点的位置矢量P,(i=l,2,---,n),则Bezier参数曲线上各点坐标的插值公式是：P(t)=£pRKt),te[0,l]i=l其中，R构成该Bezier曲线的特征多边形，⑴是n次Bernstein基函数：B1.n(t)=Cn't'(l-t)n-=jyt'(l-t)n"(i=0,1,n)Bezier曲线实例如图5.1所示。图5.1三次Bezier曲线2.Bezier曲线的性质 34(1)端点性质 351曲线端点位置矢量由Bernstein基函数的端点性质可以推得，当t=0时，P(0)=Po；当t=l时，P(l)=Pno由此可见，Bezier曲线的起点、终点与相应的特征多边形的起点、终点重合。切矢量因为P'(t)=ntp,[BTnT(t)-Bw(t)]=n%APBnT(t),其中△Pj=P,+LP,,所1=11=1以当t=0时，P'(O)=n(P,-Po),当t=l时，P'(l)=n(Pn-P.i),这说明Bezier曲线的起点和终点处的切线方向和特征多边形的第一条边及最后一条边的走向一致。3二阶导矢P'(t)=n(n-1)^(Pj+2-2P1+1+P,)Bin_2(t),当t=0时，P(O)=n(n-l)(P2-2P,+Po),当t=l时，P”(l)=n(n-l)(Pn-2P2+Pn_2)，表明：2阶导矢只与相邻的3个顶点有关，事实上，r阶导矢只与(r+1)个相邻点有关，与更远点无关。将P'(O),P"(O),P(1)E⑴代入曲率公式k(t)」I,可以得到Bezier曲线在端点的曲率分别为：k(0)=n-l|(P,-P0)x(P2-P,)|ni(p,-Po)rk(l)=n|(Pn-Pn-.)|3n-l|(Pn-.-Pn-2)X(Pn-Pn-.)|4k阶导函数的差分表示n次Bezier曲线的k阶导数可用差分公式为：pk(t)=：rn^ZAkp，Bgk(t)tG[O,l]其中高阶向前差分矢量由低阶向前差分矢量递推地定义：(2)对称性。由控制顶点Pi*=PI1_i，(i=O,l,…,n),构造出的新Bezier曲线，与原Bezier曲线形状相同，走向相反。因为：5。=1>旧患)=\七及⑴二丑心目吁-->'明式―)，te[O,l]i=0i=0i=0i=0这个性质说明Bezier曲线在起点处有什么儿何性质，在终点处也有相同的性质。(3)凸包性 36由于t><。三1,且0 37i=lj=l其中Bi,m(u)=C_；ui(l-u产,Bjn(v)=C/vj(l-v)n-j是Bernstein基函数，依次用线段连接点列P£i=0,1,…,m,j=0,l,…,n)中相邻的两点所形成的空间网络，称之为特征网格。Bezier曲面的矩阵表示式是：PooPoi…PomRm®Il«Jl|1***Jl|.BOm(v)P(u,v)=[BOn(u),Bln(u),…,(U)]1011ImPnP,...PB(v)_nOnlnm__n,mv/在一般实际应用中，m,n不大于4。1.性质除变差减小性质外，Bezier曲线的其它性质可推广到Bezier曲面：(1)Bezier曲面特征网格的四个角点正好是Bezier曲面的四个角点，即P(0,0)=P00,P(l,0)=Pm0.P(0,l)=P0n,P(l,l)=Pmno(2)Bezier曲面特征网格最外一圈顶点定义Bezier曲面的四条边界；Bezier曲面边界的跨界切矢只与定义该边界的顶点及相邻一排顶点有关，且PooBoPoi、PonKnPon-l、^0^01-1,O^m,!(图5-3打上斜线的三角形)；其跨界二阶导矢只与定义该边界的顶点及相邻两排顶点有关。(3)几何不变性。(4)对称性。(5)凸包性。P（MPGAPao图5.3双三次Bezier曲面及边界信息 385.2B样条曲线与曲面以Bernstein基函数构造的Bezier曲线或曲面有许多优越性，但有两点不足：其一是Bezier曲线或曲面不能作局部修改；其二是Bezier曲线或曲面的拼接比较复杂。1972年，Gordon.Riesenfeld等人提出TB样条方法，在保留Bezier方法全部优点的同时，克服了Bezier方法的弱点。5.2.1B样条的递推定义和性质1.定义与Bezier曲线得定义方法类似，B样条曲线方程定义为：p（t）=fpN,k（t）1=1其中，P,（i=0,l,…,n）是控制多边形的顶点，Njk（t）（i=O,l,…,n）称为k阶（k-l次）B样条基函数，其中每一个称为B样条，它是一个称为节点矢量，即非递减的参数t序列T：t04、W…W1+k所决定的k阶分段多项式，也即k阶（k-l次）多项式样条。B样条有多种等价定义，在理论上较多地采用截尾事函数的差商定义。我们只介绍作为标准算法的deBoor-Cox递推定义，又称为deBoor-Cox公式。约定0/0=0。f_ff_f%⑴=；一丁N,,k.I(t)+丁七一Ni+1,k_,(t)G+k-l—，iLk-&+1该递推公式表明：欲确定第i个k阶B样条Nik(t),需要用到t,，L，…,小，共k+1个节点，称区间[tC为Njk(t)的支承区间。曲线方程中，n+1个控制顶点Pj(i=O,l,…,n),要用到n+1个在阶B样条Njk(t)。它们支撑区间的并集定义了这一组B样条基的节点矢量T=[t0,t”…,1J。2.B样条曲线类型的划分曲线按其首末端点是否重合，区分为闭曲线和开曲线。闭曲线又区分为周期和非周期两种情形，周期闭曲线与非周期闭曲线的区别是：前者在首末端点是个连续的，而后者一般是△连续的。非周期闭曲线可以认为是开曲线的特例，按开曲线处理。B样条曲线按其节点矢量中节点的分布情况，可划分为四种类型。假定控制多边形的顶点为P,(i=O,l,…,n),为k阶(k-l次)，则节点矢量是T=[t0,tP--,tn+k],(1)均匀B样条曲线节点矢量中节点为沿参数轴均匀或等距分布，所有节点区间长度'=17=常数>0。=0,1 39广・,11+1<-1),这样的节点矢量定义了均匀的B样条基。图5.4是均匀B样条曲线实例。(2)准均匀的B样条曲线与均匀B样条曲线的差别在于两端节点具有重复度k,这样的节点矢量定义了准均匀的B样条基。均匀B样条曲线在曲线定义域内各节点区间上具有用局部参数表示的统一的表达式，使得计算与处理简单方便。但用它定义的均匀B样条曲线没有保留Bezier曲线端点的几何性质，即样条曲线的首末端点不再是控制多边形的首末端点。采用准均匀的B样条曲线就是为了解决这个问题，使曲线在端点的行为有较好的控制，如图5.5所示。(3)分段Bezier曲线节点矢量中两端节点具有重复度A,所有内节点重复度为衣-1,这样的节点矢量定义了分段的Bernstein基。B样条曲线用分段Bezier曲线表示后，各曲线段就具有了相对的独立性，移动曲线段内的一个控制顶点只影响该曲线段的形状，对其它曲线段的形状没有影响。并且Bezier曲线一整套简单有效的算法都可以原封不动地采用。其它三种类型的B样条曲线可通过插入节点的方法转换成分段Bezier曲线类型，缺点是增加了定义曲线的数据，控制顶点数及节点数都将增加。分段Bezier曲线实例如图5.6所示。图5.6三次分段Bezier曲线(4)非均匀B样条曲线在这种类型里，任意分布的节点矢量T=[t”…, 40展」，只要在数学上成立(节点序列非递减，两端节点重复度Wk,内节点重复度Wk-1)都可选取。这样的节点矢量定义了非均匀B样条基。5.2.2B样条曲线1.局部性由于B样条的局部性，k阶B样条曲线上的参数为的一点P(t)至多与k个控制顶点P,(j=i-k+l,…,i)有关，与其它控制顶点无关；移动该曲线的第i个控制顶点R至多影响到定义在区间(tj,tj+k)上那部分曲线的形状，对曲线的其余部分不发生影响。2.连续性P(t)在r重节点MkWiWn)处的连续阶不低于k-1-r。整条曲线P(t)的连续阶不低于k-l-L,其中总表示位于区间(tj/n+i)内的节点的最大重数。3.凸包性P(t)在区间国,*),k-lWiWn上的部分位于k个点P1+i，…，耳的凸包Cj内，整个曲线则位于各凸包Cj的并集0g之内。i=k-l4.分段参数多项式P(t)在每一区间也,耳|),k-lWiWn上都是次数不高于k-l的参数t的多项式，P(t)是参数t的k-l次分段多项式。5.导数公式由B样条基的微分差分公式，有：(n 41n'p_p)ZPNk(t)=XPN,k(t)=(k—1)ZNg(t)te[tk.„tn+1]i=i)i=li=lk)6.变差缩减性设平面内n+1个控制顶点P0,P1,…,P”构成B样条曲线P(t)的特征多边形。在该平面内的任意一条直线与P⑴的交点个数不多于该直线和特征多边形的交点个数。7.几何不变性：B样条曲线的形状和位置与坐标系的选择无关。8.仿射不变性对任一仿射变换A：A([P(t)])=XA[P.]Nik(t),tG[tkT，tn+Ji=O即在仿射变换下，P⑴的表达式具有形式不变性。9.直线保持性 42控制多边形退化为一条直线时，曲线也退化为一条直线。1.造型的灵活性用B样条曲线可以构造直线段、尖点、切线等特殊情况，如图5.7所示。对于四阶(三次)B样条曲线P(t)若要在其中得到一条直线段，只要Pi，P,+1,R+2，Pi+3四点位于同一直线上，此时P(t)对应的ti+3 43(四原点共织@二重原点利三代原点©二景节点利=意节点图5.7三次B样条曲线的一些特例5.2.5B样条曲面给定参数轴U和V的节点矢量U=[u0,U|,---,Um1.p]和V=[vo，V],…,丫…],pxq阶B样条曲面定义如下：_m__n_P(u,v)=ZZPK.p(U)Nj.q(V)i=lj=lRj(i=0,1,…,m,j=0,1,…,n)是给定的空间(n+l)x(m+l)个点列，构成一张控制网格，称为B样条曲面的特征网格。Nw(u)和Nj.q(v)是B样条基，分别由节点矢量U和V按deBoor-Cox递推公式决定。B样条曲线的一些几何性质可以推广到B样条曲面，图5.8是一张双三次B样条曲面片实例。图5.8双三次B样条曲面片 445.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样条多项式基函数定义的：名助耳NN。nP（t）=¥=£p,R,.k（t）£"仙）i=1i=l其中，—)0=1,…,n)称为k阶有理基函数；-k⑴是k阶B样条基函数；P,(t)(i=l,…,n)是特征多边形控制顶点位置矢量；g是与R对应的权因子，首末权因子6y0/yn>0,其余gNO,以防止分母为零及保留凸包性质、曲线不因权因子而退化为一点；节点矢量为T=[to，t],tn+J,节点个数是m=n+k+l(n为控制项的点数，k为B样条基函数的阶数)。对于非周期NURBS曲线，常取两端节点的重复度为k,即有：T=[a,…,a,tk+”人…，切,夕分别为k个，在大多数实际应用中，a=O,b=loP(t)在[tj/n+J区间上是一个k-l次有理多项式，P(t)在整条曲线上具有k-2阶连续性，对于三次B样条基函数，具有 45C2连续性。当n=k-l时，k阶NURBS曲线变成k-l次有理Bezier曲线，k阶NURBS曲线的节点矢量中两端节点的节点重复度取成k+1就使得曲线具有同次有理Bezier曲线的端点几何性质。R“k⑴具有k阶B样条基函数类似的性质：(1)局部继承性：Rik(t)=O,t^[ti,tifk]；(2)权性：^Rik(u)=l；i=l(3)可微性：如果分母不为零，在节点区间内是无限次连续可微的，在节点处(k-1-r)次连续可微，r是该节点的重复度；(4)若g=0,则Rik(t)=O；(5)若例=+8,贝ijRjk(t)=1；(6)若叼=+oo,且jHi,则Rj.k(t)=O；(7)若叼=l,j=0,l,…,n,则Ri,k(t)=Nk(t)是B样条基函数；叼=l,j=0,l,…,n,且T=(0,…,0,1,…,1)(0和1分别有k+1个),则Ri,k(t)=Bik(t)是Bernstein基函数。Ri*。)与毛上⑴具有类似的性质，导致NURBS曲线与B样条曲线也具有类似的几何性质：(1)局部性质。k阶NURBS曲线上参数为16匕,必仁口51」的一点P(t)至多与k个控制顶点耳及权因子叼=l(j=i-k+l,…,i)有关，与其它定点与权因子无关；另一方面，若移动k次NURBS曲线的一个控制顶点P,或改变所联系的权因子仅仅影响定义在区间t1，%+/上那部分曲线的形状。(2)变差减小性质。(3)凸包性。定义在非零节点区间te[t”ti+Ju[tk_”t时J上的曲线段位于定义它的k+1个控制顶点P……・•,2的凸包内。整条NURBS曲线位于所有定义各曲线段的控制顶点的凸包的并集内。所有权因子的非负性，保证了凸包性质的成立。(4)在仿射与透射变换下的不变性。(5)在曲线定义域内有与有理基函数同样的可微性。(6)如果某个权因子仍为零，那么相应控制顶点耳对曲线没有影响。(7)若.->8,则当te[t“ti+k]时，P(t)=Pjo(8)非有理与有理Bezier曲线和非有理B样条曲线是NURBS曲线的特殊情况。 465.3.2非均匀有理B样条(NURBS)曲面1.NURBS曲面的定义由双参数变量、分段有理多项式定义的NURBS曲面是：_m__n_££/耳此式11)凡©“)mnP(u，v)==XEPijRi#；j,q(u，v)U,Ve[0,1]ZZQNw(u)Nj.q(v)i=0j=0其中，号是矩形域上特征网格控制点列，%是相应控制点的权因子，规定四角点处用正权因子，即/oMmoMonMmn>0，其余?20。Njp(U)和Njq(v)是p阶和q阶的B样条基函数，Rj.p；j,q(u,v)是双变量有理基函数：„/、/N(u)Nj(v)R，,P；j,q(U，V)=mn-ZZ%Nrp(U)N，q(V)r=0s=0节点矢量U=[Uo，u”...,Um+p]和V=[Vo，V],...,Vn+q]按deBoor递推公式决定。2.NURBS曲面的性质有理双变量基函数Rm，q(u,v)与非有理B样条基函数相类似的性质：(1)局部继承性：Ri.p；j,q(u,v)=O,当U任U，Ui+p]或V《[Vj,Uj+q]；_m__n_(2)权性：XXRi，P;jq(U,V)=l;i=0j=0(3)可微性：在每个子矩形域内所有偏导数存在，在重复度为r的u节点处沿u向是p-r-1次连续可微，在重复度为r的v节点处沿v向是q-r-1次连续可微；(4)极值：若p,q>l,恒有一个极大值存在；(5)R®j,q(u,v)是双变量B样条基函数的推广。NURBS曲面与非有理B样条曲面也有相类似的几何性质，权因子的几何意义及修改、控制顶点的修改等也与NURBS曲线类似，这里不再赘述。5.4Coons曲面1964年，美国麻省理工学院S.A.Coons提出了一种曲面分片、拼合造型的思想，Bezier曲面和B样条曲面的特点是曲面逼近控制网格，Coons曲面的特点是插值，即通过满足给定的边界条件的方法构造Coons曲面。5.4.1基本概念假定参数曲面方程为P(u,v),u,ve[0,l],P(l,v)称为曲面片的四条边界， 47P(0,0),P(0,l),P(l,0),P(l,l)称为曲面片的四个角点。P(u,v)的u向和v向求偏导矢：5P(u,v)Pu(u,v)=:0UDz、0P(u,v)Pv(u,v)=ON分别称为U线和v线上的切矢。边界线P(u,0)上的切矢为：°uv=o同理：Pu(u,l),P、(O,v),Pv(l,v)也是边界线上的切矢。边界曲线P(u,0)上的法向(指参数v向)偏导矢：Pv(u,0)=气山dvv=o称为边界曲线的跨界切矢，同理，Pv(u』),Pu(O,v),Pu(l,v)也是边界曲线的跨界切矢。匕(0，。)=“Uu=0,v=0°Vu=0,v=0 48称为角点P(o,o)的u向和v向切矢，在曲线片的每个角点上都有两个这样的切矢量。Puv(U,V)=P(u,v)dudv称为混合偏导矢或扭矢，它反映了匕对v的变化率或P、,对u的变化率。同样，%(0,0)=d2P(u,v)dudvu=0,v=0称为角点P(o,o)的扭矢，显然，曲面片上的每个角点都有这样的扭5.4.2双线性Coons曲面如果给定四条在空间围成封闭曲边四边形的参数曲线P(u,0),P(u,1),P(0,v),P(1,v),u,ve[0,1],如图5.9所示。怎样构造一张参数曲面P(u,v),u,ve[0,l],使得P(u,v)以给定的四条边界曲线为边界？图5.9四条边界曲线问题的解有无穷多个，我们来看一种最简单的情况。首先，在U向进行线性插值，可以得到以P(0,v)和P(l,v)为边界的直纹面P|(u,v),如图5.10(a):R(u,v)=(1-u)P(0,v)+uP(l,v),u,ve[0,l]再在v向进行线性插值，可以得到以P(u,0)和P(u,l)为边界的直纹面P2(u,v),如图5.10(b)：P2(u,v)=(l-v)P(u,0)+vP(u,l),u,ve[0,l]如果把R(u,v)和P2(u,v)跌加，产生的新曲面的边界是除给定的边界 49外，迭加了一个连接边界两个端点的直边。为此，我们再构造分别过端点P(O,O),P(O,1),P(1,O),P(1,1)的直线段：C(l-v)P(O,O)+vP(O,l)〈ue[O,l]l(l-v)P(l,O)+vP(l,l)L'J然后，以这两条直线段为边界，构造直纹面P3UV)：P3(u,v)=(l-u)[(l-v)P(0,0)+vP(0,1)]+u[(l-v)P(l,0)+vP(l,1)]=[1-U,u]p(o,o)p(i，o)p(o,i)iri-v'p。，疝v_u,vg[0,1]容易验证P(u,v)=Pj(u,v)+P2(u,v)-P3(u,v),u,ve[0,1]便是所要构造的曲而，称之为双线性Coons曲面片。P(u,v)可进一步改写成矩阵的形式:P(u,0)P(u,l)jF-1P(0,0)P(0,l)1-vP(l，。)P。，疝v(5.1)0P(u,v)=-[-l,l-u,u]P(0,v)P(l,v)右端的三阶方阵包含了曲面的全部边界信息，称之为边界信息矩阵，其右下角二阶子块的四个矢量是曲面边界的端点，称之为曲面的角点。上面我们构造了双线性Coons曲面片，可以看出，用它来进行曲面拼合时，可以自动保证整张曲面在边界的位置连续。5.10以两条给定曲线为边界的直纹面5.4.3双三次Coons曲面双线性Coons曲面能够自动保证各曲面片边界位置连续，那么，曲面片边界的跨界切矢是否连续呢？我们对(5.1)对v求偏导后，代入v=0,可得的跨界切矢：Pv(u,v)=P(u,l)-P(u,O)+[l-u,u]PV(O,O)+P(O,O)-P(O,1)PV(1,O)+P(1,O)-P(1,1) 50可见，跨界切矢不仅与该边界端点的切矢有关，还与该边界曲线有关。因此，双线性Coons曲面在曲面片的边界上，跨界切矢一般不连续，也就是说，不能达到曲面片的光滑拼接。为了构造光滑拼接的Coons曲面，除了给定边界信息外，还要给定边界的跨界切矢。也就是说，构造出的Coons曲面片不仅以给定的四条参数曲线为边界，还要保持四条曲线的跨界切矢。假定四条边界曲线为：P(u,0),P(u,l),P(0,v),P(l,v),u,ve[0,1]四条边界曲线的跨界切矢为：Pv(u,0),Pv(u,l),Pu(0,v),Pu(l,v),u,ve[0,l]我们不妨取Hermite基函数F0,耳,G°,G/乍为调和函数，以类似于双线性Coons曲面的构造方法，构造双三次Coons曲面。在u向可得曲面R(u,v):R(u,v)=%(u)P(0,v)+F,(u)P(l,v)+G0(u)Pu(0,v)+G,(u)Pu(l,v)u,ve[0,1]在v向可得曲面P2(u,v)：P2(u,v)=F0(v)P(u,0)+耳(v)P(u,l)+G0(v)Pv(u,0)+G((v)Pv(u,l)u,ve[0,1]对角点的数据进行插值，可得曲面P3(U,V):>(0,0)P(。」)P、.(0,0)Pv(0,D]rFo(v)'P3(u,v)=[^(u),F；(u),G0(u),G1(u)]P(l,0)Pu(0,0)P(l，l)Pu(0,l)Pvd,0)Puv(0,0)pv(l,l)Puv(0，l)F.(v)G0(v)-0)Pud』)Puv(l，0)pUv(ia)JLG.(v).u,ve[0,l]。可以验证曲面P(u,v)=P](u,v)+P2(u,v)-P3(u,v),u,ve[0,l]的边界及边界跨界切矢就是已经给定的四条边界曲线和四条边界曲线的跨界切矢，称之为双三次Coons曲面片。P(u,v)改成矩阵的形式为：0P(u,0)P(u,l)P、(u,0)P,(u,D]TP(0,v)P(0,0)P(0,l)H(o,o)Pv(0.l)F0(v)P(u,v)=-[-I禺(u),耳(u),G°(u),G](u)]P(Lv)p(i，o)P(l，l)Pv(l,0)K(v)Pu(0,v)Pu(0,0)P„(0,l)Puv(0,0)"(0,1)G0(v)一Pu(Lv)Pu(l,0)P„(1,DPuv(l,0)P"l)」u,vg[0,1](5.2)在式(5.2)右边的五阶方阵(即边界信息矩阵)中，第一行与第一列包含着给定的两对边界与相应的跨界切矢，剩下的四阶子方阵的元素由四个角点上的信息组成，包括角点的位置矢量、切矢及扭矢。观察方程(5.1)与(5.2),可以发现：对曲面片满足边界条件的要求提高一阶，曲面方程中的边界信息矩阵就要扩大二阶，并且要多用一对调和函数；边界信息矩阵的第 51一行与第一列包含着全部给定边界信息；余下的子方阵则包含着角点信息。认识了这些规律后，就能容易地构造出满足更高阶边界条件的Coons曲面方程。6CAGD中有关曲线曲面Cn、G)并接技术5.1基本原理几何设计中，一条Bezier曲线往往难以描述复杂的曲线形状。这是由于增加由于特征多边形的顶点数，会引起Bezier曲线次数的提高，而高次多项式又会带来计算上的困难，实际使用中，一般不超过10次。所以有时采用分段设计，然后将各段曲线相互连接起来，并在接合处保持一定的连续条件。下面讨论两段Bezier曲线达到不同阶凡何连续的条件。6.2Bezier曲线的C。、G。、CPGPC2>G?的拼接条件设给定两条Bezier曲线的控制点列P,(i=0,1,…,n),且ai=P「Pi和Qj,其中j=0,l,…,m;bj=Qj-Qj_1。若将P(t)段与Q(t)相连，则要在连接点处达到G°,G',G2级连续的充要条件是：(1)G0级连续的充要条件是：Pn=Q0o即P⑴的终点与Q⑴的起点重合，曲线在连接点处不能保证是光滑连接。(2)Gi级连续的充要条件为两段曲线在连接点处不仅达到G0级连续，且Q'(0)=aP'⑴(a〉0),根据端点性质：P'(l)=叫&(0)=mb1,即=a—an=afan(af>0)m这意味着PnT，Pn=Q0,Q|三点共线且顺序排列。当a'=l时达到Gi级连续，此时不仅具有上述性质，而且P.为Pi和Qo两点连线的中点。(3)G2级连续的充要条件为：两段曲线不仅在连接点处达到G°级和GI级连续，还要求密切平面重合，副法线向量同向且曲率连续，更确切的说曲率矢连续，即G2。则在GI级连续的条件下，并满足方程Qff(0)=a2P71)+pP，(l)o我们将Q"(0)、P"⑴、P")，Pn=Q。、Q,-Q0=a(Pn-Pn-1)代入并整理得至hQ2=^a2+2a+-^-j-+ljPn-2a2+2a+JPn_,+a2Pn_2选择a和0的值，可以利用该式确定曲线段Q⑴的特征多边形Qz，而顶点Q。、Q1已被Gi连续条件所确定。要达到G?连续的话，只剩下顶点Q?可以自由选取。如果从上式的两边都减去打，则等式右边可以表示为（R-Pz）和（Pji-1-Pn-2）的线性组合： 52Q：-Pn=[a2+2a+^（Pn-Pn-1）-a2（Pn_1-Pn-2）这表明Pn_2、Pn_,>Pn=Q。、Q|和Q2五点共面，事实上，在接合点两条曲线段的曲率相等，主法线方向一致，我们还可以断定：P.2和Q2位于Pn-lQl直线的同…侧。假定参数曲线线段P,以参数形式进行描述：Pi=Pi（t）（f6也0，%]）参数连续性要求满足以下条件：1）c°连续（0阶参数连续）：前一段曲线的终点与后一段曲线的起点相同，即P,（册）=P（i+1）（"+1）0）。2）连续（1阶参数连续）：指代表两个相邻曲线段的方程在相交点处有相同的一阶导数，即P,（M）=p（i+i）（%+1）0）且P-储）=p'（M｝。（川）0）。3）。2连续（2阶参数连续）：指两个相邻曲线段的方程在相交点处具有相同的一阶和二阶导数。几何连续性要求满足以下条件：2）G°连续（0阶几何连续）：与0阶参数连续的定义相同，满足：Pi（'ii）=〃（i+l）（%+l）O）3）Gi连续（1阶几何连续）：一阶导数在相邻段的交点成比例（切向量不一定相等）。4）G2连续（2阶几何连续）：指相邻曲线段在交点处其一阶和二阶导数均成比例（此时，两曲线段在交点处的曲率相等）。可以看到，参数连续性是传统意义上的，严格的连续，而儿何连续性只需限定两个曲线段在交点处参数导数成比例，不必完全相等，是一种更直观，易于交互控制的连续性。在曲线，曲面造型中，一一般只用到Cl和G2连续，切矢量(一阶导数)反映了曲线对参数t变化速度，曲率(二阶导数)反映了曲线对参数t变化的加速度。通常。连续必须保证连续，但GI连续并不能保证连续。曲线段在连续处达到连续和Gi连续的光滑程度是相同的，但曲线的变化趋势在这两种情况下不一定相同，在实际应用中，要适当选择曲线段，曲面片间的连续性，是造型物体既能保证其光滑性要求，也能保证其美观性要求。 536.3Bezier曲面的C。、G。、G、G1的拼接条件相对于参数曲线的拼接，参数曲面问题问题要复杂得多，其应用也更为广泛。主要的拼接方法是基于参数连续和几何连续的。1)参数连续如果两个参数曲面p(u,v),q(s,r)具有公共的连接线，称它们是连续的或C°连续的。此时也称为G°连续，即零阶参数连续与儿何连续是等价的，对于两曲面间k阶参数连续如下定义：定义1：两个参数曲面p(〃,v),q(s,r)沿公共连接线p(f)=q⑺具k阶参数连续性(即C*连续)的充要条件是：两曲面在公共连接线上处处满足：―：——rP(t)=-：_-q(t)，du'dvJds'drJ定义2：曲面片p(u,v),ue=[>0，匕]与曲面片q[u,v),ue[uo,uj,v=［匕，匕］在公共边界=夕(〃,匕+)上C11连续的充要条件为—^7=——-9(w，v(+)，i+j=0,1,…,k.2)几何连续定义3：两曲面p(〃,v),q(s,r)沿公共连接线p(f)=g(r)具有Gi连续的充要条件是：它们沿该公共线G°连续，并且处处具有公共的切平面(或公共的曲面法线)。定义4：两曲面p(“，Dq(s,r)沿公共连接线p(r)=q(f)具有G?连续的充要条件是它们沿该公共线Gi连续，并且具有公共的主曲率，及在两个主曲率不相等时具有公共的主方向。定义3,4分别给出了GlG2连续的条件，对于一般的G”连续可由下定义给出定义5：两曲面p(“,v),g(s,r)沿公共连接线p(t)=q(t)具有G*连续的充要条件是两曲面之一可以重新参数化，以至于它们沿公共连线为G*连续的，如式s,r)重新参数化为7G，；),使得9,+Jd'+j-―：——rp(t)= ：~-q(t),du'dvJds'drJ类似曲线几何连续性的定义，曲面的几何连续性1)C-B6zier曲线与Bezier曲线拼接条件。C-B6zier曲线与Bdzier曲线的G°拼接条件为：只要C-Bezier曲线的末端点与Bezier曲线的首端点相同，即 54%=Po(1)C-Bezier曲线与Bezier曲线的C光滑拼接的条件是：在满足(1)的基础上，要求C-Bezier曲线末端点切向与Bezier曲线端点切向相同，即Pi=。()+九(43-42)，义>01)C-Bezier曲线与有理Bezier曲线光滑拼接的条件。C-Bezier曲线与有理Bezier曲线光滑拼接的方法讨论于以上基本相同。2))C-Bezier曲线与B_样条曲线拼接C-B6zier曲线与B_样条曲线达到G°拼接心=Po+4Pi+C-Bezier曲线与B一样条曲线在拼接处有相同的切向B式a)=-P'(0),I>0P2-Po="效一%)，之>0所以，得到C-Bezier曲线与B_样条曲线达到G1拼接条件p2=p0+X(q3-q2)Pi=^(6q3-p0-P2X3X>01)Bezier曲面的拼接在实际应用中，常常应用Bezier曲面来平滑实验数据，也用来交互设计一些简单曲面，甚至用来构造边界条件，然而在曲面设计中，最有效的工具之一是采用G，和G?光滑拼接起来的Bezier曲面。由于Bezier曲面的构造既有矩形域又有三角形域，这样，使得Bezier曲面拼接造型方法应用范围就十分广泛，这是其他造型方法不能比美的。应该说，两类曲面拼接技术是至今最佳的曲面设计方法。定义1两块拼接起来的正则曲面，若拼接线上每一点的切平面连续,则称一阶几何连续(G1)拼接。定义2两块拼接起来的正则曲面，若拼接线上过每一点任意截线的法曲率连续，则称二阶几何连续(G2)拼接。2)双二次有理B6zier曲面光滑拼接设两个有理曲面r(u,v),具有公共边界曲线(位置连续)f:r(l,v)=r(O,v),如图6.1所示 55图6.1有理BGzier曲面的拼接则两个曲面满足Gi的条件为：引理1：两个有理曲面r(a,v),；(“/)满足的充分必要条件为具有公共边界且切平面连续，即r(Lu)=v),ru(0,v)=aru(1,v)+氏(l,v)式中，a,夕为关于v的任意函数。引理2：设有理曲面片r(w,v),r(u,v)具有公共边界曲线，则r(w,v),7(〃#)是61当且仅当0(O,v)=co(v)e(l,v)(3)Qu(0,v)=Cx(v)g(l,v)+c0(v)p](v)Qu(1,v)+Co(v)%(v)Qv(1,v)(4)式中Co(v),cjv),Pi(v)，41(v)是关于公共边界参数v的函数，Q(u,v),Q(u,v)分别为r(u,v),r(u,v)o7图形变换技术在计算机图形学中，常用的图形变换技术有：二维图形的几何变换、三维图形的几何变换、参数图形几何变换。投影变换，在这些变换中又有各种分类的变换，详细如下： 567.1二维图形几何变换7.1.1平移（Translation）平移是将对象从一个位置（x,y）移到另一个位置（X。川的变换（图7.1）oTx=x，-x,Ty=y，一y称为平移距离。平移变换的公式为：X—x+Tx,y-y+Ty.(x«y)图7.1平移变换平移的矩阵运算表示：‘100、[x',y',l]=[x,y,l]010UTy1；简记为p'=pT(Tx,Ty)001o表示平移矩阵。Ty11其中P=[x,y,l],T(T、,Ty)=0I7.1.2旋转（Rotation）旋转是以某个参考点为圆心，将对象上的各点（x,y）围绕圆心转动•个逆时针角度。，变为新的坐标（X、口的变换。当参考点为（0,0）时，旋转的公式为：x'=rcos(a+。)=rcosacos。一rsinasin。y'=rsin(a+ff)=rsinacosO+rcosasin。vx=rcosa,y=rsina,所以上式可化为：x'=xcose—ysinaV一y'=ycos，+xsina 57如果参考点不是(0,0),而是任意一点(Xr，yj,那么，绕(x「,yj点的旋转由三个步骤完成(1)将对象平移T*=—Xr，Ty=y,；(2)按式(7.1)作旋转变换；(3)平移组合这三个步骤的计算公式为：x'=x「+(x-xr)cos0-(y-yr)sin0 58x'=xsxy-ysy图7.3变比变比的矩阵运算表示为：So0、[x,y,l]=[x,y,l]0Sy00U简记为P=pS（Sx，Sy）,其中（Sx，Sy）表示变化矩阵，p=[x,y,l]o7.2三维图形几何变换7.2.1平移设Tx，Ty,Tz是物体在三个坐标方向上的移动量，则有公式：x,=x+Tx 59下述旋转变换公式中，设旋转的参考点在所绕的轴上，绕轴转。角，7.4(a),(b))„方向是从轴所指处往原点看的逆时针方向（图（a）绕z轴旋转（b）绕x轴旋转图7.41绕z轴旋转的公式为：x'=xcos。一ysin。 60[x,y,zl]=[x,y,z,l]0-sin。cos。0、0001,简记为：Rx(0)3绕y轴旋转的公式为：x'=zsin9+xcos6*y-yz'=zcos0—xsin矩阵的运算表达式为：COS。0-sin。0、[x',y',z'l]=[x,y,z,l]0100sin。0cos。0、0001;简记为：Ry⑼如果旋转所绕的轴不是坐标轴，而是一根任意轴，则变换过程变显得较复杂。首先，对物体作平移和绕轴旋转变换，使得所绕之轴与某•根标准坐标轴重合。然后，绕该标准坐标轴作所需角度的旋转。最后，通过逆变换使所绕之轴恢复到原来位置。这个过程须由7个基本变换的级联才能完成。设旋转所绕的任意轴为Pl，P2两点所定义的矢量。旋转角度为。(图7.5)o这7个基本变换是：1T(-x-y「zJ使P1点与原点重合(图7.5(b))；2Rx(a),使得轴PR落入平面xoz内(图7.5(c))；3Ry(p),使pg与z轴重合(图6(d));4Rz(9),执行绕pg轴的。角度旋转(图7.5(e))；5Ry(-。)，作3的逆变换；6Rx(-a),作2的逆变换；7T(xry”zJ,作1的逆变换。 61图7.5旋转角度为8的基本变换 627.2.3变比设Sx,Sy,Sz是物体在三个方向的比例变化量，则有公式:矩阵运算的表达为'Sx000、0Sy0000Sz000[x',y',z',l]=[x,y,z,l]相对于某个非原点参数点（Xf,yf,Zf）进行固定点变比变换，是通过如下级联变换实现的：T(-xr,-yf,-zf)S(Sx,Sy,Sz)T(xf,yf,zf)7.3参数图形几何变换7.3.1圆锥曲线的几何变换圆锥曲线的二次方程是Ax2+Bxy+Cy2+Dx+Ey+F=0,其相应的矩阵表达式是'AB/2[xy1]B/2C、D/2E/2简记为xsxt=o。(1)平移变换：D/2、E/2F,y=01100若对圆锥曲线平移变换，平移矩阵是［=010mn1圆锥曲线矩阵方程是XTrSTTrXT=0o（2）旋转变换：则平移后的 63若对圆锥曲线相对坐标原点作旋转变换，旋转变换矩阵是/cos。sin00、R=-sin0cos00、00"则旋转后的圆锥曲线矩阵方程是XRSRtXt=0o若对圆锥曲线相对(m,n)点作旋转。角变换，则旋转后的圆锥曲线是上述T,、R变换的复合变换，变换后圆锥曲线的矩阵方程是XTrRSRTTrTXT=0o(3)比例变换：若对圆锥曲线相对(m,n)点比例变换，比例变换矩阵为So0、ST=0Sy0,则变换后圆锥曲线的矩阵方程是XTrSTSSTTTRTXT=0、00"对于二次曲面也有与上述类似的矩阵表示和几何变换表达式。7.3.2参数曲线、曲面的几何变换(1)平移变换：若指定一个平移矢量t,对曲线平移t,即对曲线上的每一点P都平移t。平移后的点P*有P*=P+t对于参数曲线和曲面的几何系数矩阵B和代数系数矩阵A,可以直接实现平移变换，即有B*=B+T,T=[t,t,0,0]TB*是经平移后参数曲线的儿何系数矩阵。因为双三次曲面片的系数矩阵是4X4的，故其平移变换矩阵为一tt0o-tt00T=0000()000(2)旋转变换：形体的旋转变换有绕主轴旋转，或绕空间任••直线旋转等多种形式。若令R0表示绕z轴转。角，飞表示绕y轴转B角，R,表示绕x轴转丫角，则点P绕x、y、z轴转丫、B、。角的变换公式是'cos。sin。0、'cosp-sin/0、"00、 64R=RKR广-sin。cos。00100cos/sin/、°oI\Sin〃0cos/??、0-sin/cosy.对于参数曲线或曲面的代数系数矩阵和几何系数矩阵的变换公式是A*=AR,B*=BR对于绕空间任一直线旋转。设空间任一直线(即轴)由矢量定义(即该直线的端点)，空间参数曲线要绕此轴旋转6角，则该变换可以由以下几步完成第一步：平移曲线和此轴，令平移量为r,,使该轴的一端点变为坐标原点，则t=-q,若P为曲线上任一点，则有：P*=Pk第二步：旋转曲线和该轴，使该轴和x轴共线，先绕z轴转-8角，再绕y轴旋转邛角，O=tan1[(y2-y1)/(x2-x1)],p=sin-l((z2—z')/|r2—rj)则P*=[P—rJR叩第三步：绕X轴转丫角，丫=6,则有：P*=[P-r1]RopRr第四步：对第二步的变换求逆，即：P*=[P—rJRo°Rr氏邮；第五步：对第一步的变换求逆，即：日二伊一彳凤国/?即+彳。经过上述五步，即在新的位置上定义了参数曲线。使用几何系数矩阵B实现上述变换的公式是B=[B+T]RopRrR_0p-TT=[-rI,-r1,O,O]T若令Ra=RopRrR-ep 65则令则(3)比例变换:B*=[B+T]Ra-T=BRa+TRa-TT=TR-TaaB*=BR+Taa令比例系数为s,对参数曲线作变比例变换，只要对儿何系数矩阵B作变比例变换即可，也就是B*=sB或B=[sP(),sP1,sPUo,SPU1]T(4)对称反射变换：对称反射变换可用下式表示：B=BRf,其中①对X=0的平面作对称反射变换，则--I00'Rf=010001②对y=0的平面作对称反射变换，则-100-Rf=0-10001③对Z=0的平面作对称反射变换，则'100'Rf=01000-1④对X轴作对称反射变换，则j00一Rf=0-1000-1⑤对y轴作对称反射变换，则--100-R,=01000-1⑥对z轴作对称反射变换，则--100-Rf=0-1000I 66⑦对坐标原点作对称反射变换，则0-1000-1以上讨论了对参数曲线、曲面的控制点及其矢量，即对其几何系数矩阵（或代数系数矩阵）直接进行几何变换的情况。对某些应用，在保持形体拓扑关系不变的情况下，还可以把这类几何变换矩阵的元素为常数的变换转化为其矩阵元素为线性或非线性函数的变换，从而可以扩大几何造型的。7.4投影变换8.4.1平行投影（paraIIe1projection）它使用一组平行投影将三维对象投影到投影平面上去（图7.6）。1正平行投影（三视图）投影方向垂直于投影平面的投影称为正平行投影，我们通常所说的三视图均属于正平行投影。三视图的生成就是把x、y、z坐标系的形体投影到z=0的平面，变换到u、v、w坐标系。一般还需将三个视图在一个平面上画出，这时就得到下面的变换公式，其中（a,b）为u、v坐标系下的值，tx，ty,t,均如图中所示。1）主视图0000a-tb+t,-10002）俯视图-10000—1000000a-t.b—t00003）侧视图a+tyb+tz0 67图7.6三视图2斜平行投影投影方向不垂直于投影平面的平行投影被称为斜平行投影，现在让我们来推导斜平行投影的变换矩阵。下图中的Z=0的坐标平面为观察平面，点（x,y）为点（x,y,z）在观察平面上的正平行投影坐标，点（x',y）为斜投影坐标。（x,y）与（x',y）的距离为L。显然，x=x+Lcosa,y=y+Lsina而L的长度依赖于z,P,即tanP=z/L,L=z/tanp.,1.11.所以x=x+zcosa.y=y+zsinatanptanp令l、=—二,则x'=x+z/]Cosa,y'=y+z/iSina,由此可得:tanpX一10Z(cosaO-X 68y,01Z(sina0yz0000z1000117.4.2透视投影(perspectiveprojection)它使用一组由投影中心产生的放射投影线，将三维对象投影到投影平面上去。由平行投影方法表现三维对象的图，称为正视图和轴测图，由透视投影方法表现三维对象的图，称为透视图。透视投影的视线(投影线)是从视点(观察点)出发，视线是不平行的。不平行于投影平面的视线汇聚的一点称为灭点，在坐标轴上的灭点叫做主灭点。主灭点数和投影平面切割坐标轴的数量相对应。按照主灭点的个数，透视投影可分为一点透视、二点透视和三点透视。下面我们来推导简单的一点透视的投影公式。图7.8投影公式推导图从上图P点在观察平面上的投影我们可以得到描述P，点的参数方程：X=X-XU 69用齐次坐标表示为：X/,10Y/,0100h00其中8图形消隐算法在计算机图形学中，常用的图形消隐算法有：扫描线Z-buffer算法、区域子分割算法、光线投射算法、平面公式法、径向预排序法、径向排序法、隔离平面法、深度排序法、光线跟踪法、Z缓冲区法、极值检测法、深度分类方法、八叉树方法。8.1扫描线Z-buffer算法算法的主要思想是：在处理当前扫描线时，开一个一维数组作为当前扫描线的Z-buffer。首先找出与当前扫描线相关的多边形，以及每个多边形中相关的边对。对每一个边对之间的小区间上的各象素，计算深度，并与Z-buffer中的值比较，找出各象素处可见平面，计算颜色，写帧缓存。对深度计算，采用增量算法。8.2区域子分割算法基本思想是：把物体投影到全屏幕窗口上，然后递归分割窗口，直到窗口内目标足够简单，可以显示为止。首先，该算法把初始窗口取作屏幕坐标系的矩形，将场景中的多边形投影到窗口内。如果窗口内没有物体则按背景色显示；若窗口内只有一个面，则把该面显示出来。否则，窗口内含有两个以上的面，则把窗口等分成四个子窗口。对每个小窗口再做上述同样的处理。这样反复地进行下去。如果到某个时刻，窗口仅有象素那么大， 70而窗口内仍有两个以上的面，这时不必再分割，只要取窗口内最近的可见面的颜色或所有可见面的平均颜色作为该象素的值。7.3光线投射算法算法的思想是：考察由视点出发穿过观察屏幕的一象素而射入场景的一条射线，则可确定出场景中与该射线相交的物体。在计算出光线与物体表面的交点之后，离象素最近的交点的所在面片的颜色为该象素的颜色；如果没有交点，说明没有多边形的投影覆盖此象素，用背景色显示它即可。8.4平面公式法根据解析几何原理，通过标准的平面方程可以判断给定点是在平面的正面还是背面。平面公式法利用此原理来判断观察点位于物体表面的哪一侧，如位于背面一侧，则表面不可见，应被消隐；反之则不可见。对物体的任意表面，可将其划分为若干个平面，再根据平面上任意三点的坐标可以求得其平面方程。标准的平面方程为：Ax+By+Cz+D=0其中A,B,C,D为决定平面的常数。当把一个平面想象成一个凸型多面体时，设观察点坐标为（x,y,z）：如果Ax+By+Cz+D=0,则观察点（x,y,z）是该平面上的一个点；如果Ax+By+Cz+D>0,则观察点（x,y,z）在凸型多面体内部（称该表面是不可见的或隐的）；如果Ax+By+Cz+D<0,则观察点（x,y,z）在凸型多面体外部（称该表面是可见），应被画出。通过对物体进行适当旋转和平移后，可将物体变换到观察点为原点的观察坐标系。如果在观察坐标系中求得了平面的方程Ax+By+Cz+D=0,将观察点为原点坐标系代入上面的判断准则，则可得出如下的简单判据：D>0,则平面不可见，应被隐藏：D<0,则平面式可见面，应被画出。8.5径向预排序法径向预排序法根据物体在三维坐标系XY平面的角位置来判断哪些物体挡住了其他物体，物体的那些表面挡住了其它表面。对具有相同角位置的物体或表面，与观察点较近的将挡住较远的。径向预排序法消隐的要点是先对物体及物体的表面进行由远及近的排序，对具有相同角位置的物体或表面，先画较远的，后面画较近的，这 71样若果较近的物体或表面挡住了较远的物体或表面，则被遮挡的部分被覆盖而实现消隐。但对具有不同角位置的物体或表面，先画哪一个可根据需要来决定。如果存在凹面物体的消隐，一般应先画物体中心部分，再画物体的两侧，以正确的表现互相重叠的凹面模型。8.6径向排序法径向排序法是对径向预排序法的改进算法，使得构造模型的编码能根据观察角度的变化，来自动调整物体或表面的远近顺序即画图顺序，以实现对模型的旋转变化，以便能从不同的角度来观察物体。算法需要检测旋转变换的角度，并随角度的变化而调整物体或表面的远近顺序。8.7隔离平面法隔离平面法主要用于多个物体之间的消隐处理，而基础是平面公式法。其基本原理是，在需要进行消隐处理的两个物体之间建立一个虚拟平面，并根据平面公式法判断出两个物体分别位于该平面的那一侧，以及该平面的那一侧朝向观察点，则可以推论得到位于平面朝向观察点•侧的物体离观察点较近，将遮挡位于平面背向观察点一侧的物体。即位于平面背向观察点一侧的物体应被首先画出，且应进行消隐。8.8深度排序法深度排序法也是主要分析多个物体之间是否存在表面遮挡的消隐算法。其原理是比较不同物体或表面的表示远近的z坐标，在观察点位于原点的观察坐标系中，回值越大的物体或表面离观察点越远，被消隐的可能性越大，应先画出；目值越小的物体或表面离观察点越近，将可能遮挡较远的物体或表面，应后画出。8.9光线跟踪法光线跟踪法也叫光线投影法。一束光线照射在物体上，经反射后，触到人们的眼睛，最接近观察点的表面应该是被画的表面。此法要求分析显示屏幕上的每一点，每个点都要给出能反映表面反射特性及物体亮度特性的颜色参数。8.10Z缓冲区法在这个算法里，不仅需要有帧缓存来存放每个象素的颜色值，还需要一个深度缓存来存放每个象素的深度值。Z缓冲器中每个单元的值是对应象素点所反映对象的z坐标值。Z缓冲器中每个单元的初值取成z 72的极小值，帧缓冲器每个单元的初值可放对应背景颜色的值。图形消隐的过程就是给帧缓冲器和Z缓冲器中相应单元填值的过程。在把显示对象的每个面上每一点的属性（颜色或灰度）值填入帧缓冲器相应单元前，要把这点的z坐标值和z缓冲器中相应单元的值进行比较。只有前者大于后者时才改变帧缓冲器的那一单元的值，同时z缓冲器中相应单元的值也要改成这点的z坐标值。如果这点的z坐标值小于z缓冲器中的值，则说明对应象素已经显示了对象上一个点的属性，该点要比考虑的点更接近观察点。对显示对象的每个面上的每个点都做了上述处理后，便可得到消除了隐藏面的图。Z缓冲区算法的最大优点是简单。它各坐标轴方向上没有任何排序，也没有任何相关性。在屏幕大小一定情况下，算法的计算量也只与多边形个数成正比。缺点是：需要一个额外的z缓冲器；在每个多边形占据的每个像素处都要计算深度值，计算量大；没有利用图形的相关性于连续性。8.11极值检测法极值检测法需与其它消隐算法结合适用，主要用来提高消隐速度。极值检测法通过计算物体表面的显示坐标的极大和极小值来判断这两个表面是否存在重叠。如果一个表面的x显示坐标的极大值小于另一个表面的x显示坐标的极小值，则这两个表面不重叠，可以按任意顺序直接画出。否则，这两个表面存在重叠，需要用其他消隐算法进行消隐处理。9.12深度分类方法它包括：1、在物体空间按照物体的深度次序对多边形进行分类；2、在图像空间根据由远及近的次序对多边形进行扫描转换。在有多个模型存在的场景里，特别是当一个可视面覆盖了另一个可视面时，这种方法是非常有用的。通过比较两个不同平面的Z坐标，首先画出具有最小Z坐标的平面，因为它距离观察者最远；最后面画出距离观察者最近的，具有最大Z坐标的平面。8.13八叉树方法物体的八叉树表示是一种层次数据结构，这种数据结构大大简化了隐藏面的消除。在八叉树表示中，物体上的各元素已按空间位置排成一定顺序，同一层次的八叉树结点组成三维空间中并线性分离的丛，并建立丛的优先技树。由于每一层的八叉树结点均按同一规律 73编码，因此使丛的优先级树适用于同•八叉树的所有结点。故其消隐算法的时间复杂性呈0(n),n为要显示物体的体元数目。9图形学若干基本算法的实现研究所读论文：题目：计算机图形学若干基本算法的实现研究作者：李海军单位：吉林大学博士学位论文时间：2008年4月文章摘要：随着计算机图形设备的不断更新和图形应用领域的不断扩大，计算机图形学理论和技术所包含的内容也在不断的增加。目前，所包含的内容主要有：最基本的直线与曲线生成、绘制；线、多边形的裁剪；隐藏线与隐藏面的消除，以及目前图形学领域中热点研究的内容，包括真实感显示技术，虚拟现实技术，动画与仿真技术，科学计算可视化技术，三维重建技术以及建模与绘制技术等。本文所研究的计算机图形学若干基本算法包括裁剪算法、多边形布尔运算、曲线边多边形分割算法、曲线边多边形面积算法、高维空间距离算法和主成分回归分析法(PCR),具体工作如下：图形的裁剪是计算机图形学的一个基本内容，裁剪是对图形数据进行选择性摘取。它将处于用户规定的窗口或视见区内的图形进行显示或做进一步处理。裁剪是计算机图形学在许多方面应用的基础，例如从不同的物体模型中裁取事物体进行拼接而产生新的物体模型。在三维显示中的隐藏线隐藏而消除和表面阴影处理等技术中有些算法也结合了裁剪算法。裁剪在图形合成中是基础和必须的操作。裁剪的原理并不复杂，但对速度要求很高，提高裁剪速度具有重要的意义。对裁剪算法的研究主要集中在裁剪直线和裁剪多边形两方面。平面简单多边形的布尔运算是计算几何、计算机图形学中的基础问题之一，在几何和实体造型等领域中有着广泛的应用价值。国内外许多专家对此进行了大量有益的探索，并提出了相应的算法，但是这些算法大部分都没有建立完整的数学模型，只局限于对凸多边形进行操作，还有一些算法虽然可以对任意多边形进行操作，但是运算过程大多比较烦琐，而且在某些特殊情况下还不是很有效，甚至无法得出正确的结果。在几何模型的应用中，常常要对模型表示的儿何实体进行分解。在特殊问题的解决中，需要对算法进行分析和设计。常用来表示多边形的方法有：三角化法、梯形化法、凸形分解法、二进制空间分区树法。 74平面多边形的各种分解表示方法在计算机几何造型领域中有着广泛的应用，根据基于三角形的多边形表示方法，通过研究构造的多种算法和它的一些应用，如布尔运算和点的包容测试等，在原有工作的基础上，对算法进行了扩展，使其可以应用到带圆锥曲线边的平面扩展多边形上，提出了平面扩展多边形的分层表示方法，并给出了完整的数学模型和两种典型的构造算法。针对在构造有曲线边多边形分层表示时可能会出现不合理情形，对曲线边进行分割，提出了一些可以利用的分割算法，包括对圆锥曲线边求分割点和切点的算法，对三次Bezier曲线边求可能的自交点的算法，对三次Bezier曲线边求不同形式分割点和切点的算法。复杂几何形状面积的计算，属于计算几何方面的问题。对于复杂的几何形状可以借助于积分或数值方法计算其面积，积分方法是一种目前比较流行的方法。但是积分或数值方法计算得到的几何面积是近似的，而对于大多数工程问题，往往希望得到其精确的平面面积。在实际应用中，不但经常需要计算一般多边形的面积，而且有时还需要计算有曲线边多边形的面积。有曲线边多边形是平面多边形的推广，即允许多边形中一些边是曲线段，也称为扩展多边形。为简便和考虑实用需要，可以假定曲线边是圆锥曲线边或三次Bezier曲线边。本文对圆锥曲线边和三次Bezier曲线边两种曲线边多边形的面积算法分别进行讨论。由对象多个特征组成的特征向量，可以自然地看作是高维数据空间中的一点。许多实际问题涉及到高维数据点。在高维空间中点的超球范围查找问题是：已知一个高维数据点集，输入一个点和半径数值，询问所确定超球范围内包含有给出点集中哪些点。考查了用计算街区和棋盘距离的线性组合来代替计算欧氏距离的方法，这个方法由于减少了乘法计算而明显的可以提高效率。为提高计算精度，需要选择适当的构造线性组合时的系数。还有，本文结合贝叶斯网络提出一种新的回归树学习算法一BRT（BayesianRegressionTree）o在BRT多元回归模型中，需要有变量选择的功能，利用主成分回归分析法（PCR）,在通过正交旋转变换来消除原始数据中的相关性或冗余度的基础上，根据方差贡献率选择特征属性，实现高维属性空间向低维属性空间的映射。学习体会：通过阅读这篇博士论文，让我对各种基本算法有了更深刻的理解，特别是对贝叶斯网络有了更新一步的认识，对于回归分析一部分的研究，将结合高维空间数据分析，应用更多的统计理论，尤其注重贝叶斯网络知识的研究与应用，进一步提高算法的效率。论文中经BRT算法生成的回归树模型LR、LWR和算法相比，预测误差度有不同程度的降低，尤其在连续特征属性较多的情况下有明显的改善。其测试结果从实践的角度验证了基于概率密度估计因变量和根据离散属性值构造局部多叉树（传统的树形回归模型是二叉树）的合理性。 75回归分析是研究事物间变量规律的一种科学方法。也就是说，回归分析研究一个变量或一组变量（即自变量）之变动对另一个变量（因变量）之变动的影响程度，其目的在于根据已知的自变量的变异来估计或预测因变量的变异情况。如何根据样本观测数据估计并检验回归模型及其未知参数判别影响因变量（被解释变量）的重要自变量（亦称为解释变量）；根据自变量的已知值或给定值来估计和预测因变量的条件平均值并给出预测精度等。在多元的回归模型中，需要有变量选择的功能。文中利用主成分回归分析法（PCR），在通过正交旋转变换来消除原始数据中的相关性或冗余度的基础上，根据方差贡献率选择特征属性，实现高维属性空间向低维属性空间的映射。提出了一种基于贝叶斯网络的回归树学习模型。与传统的回归分析主法相比，它还需要假设某一函数能最佳逼近本分布，因而应用范围更广。以达到简化网络结构，提高网络学习效率和准确率的目的。论文以曲线边多边形为主要研究对象，对应的算法也只局限于平面，在今后的研究中，可以把曲线边多边形算法扩展到三维空间，目前为了讨论方便，假设曲线边为圆锥曲线或Bezier曲线，还可以考虑其他的常用曲线边，如样条曲线等。论文中还讨论了曲线边多边形的面积计算，还可以进一步讨论计算三维空间曲面多面体的体积。高维空间中两点距离的计算，文章中是用计算街区和棋盘距离的线性组合来代替计算欧氏距离的方法，虽说能够满足一定的实际需要，但还存在着计算误差问题，在今后的研究中，试图寻找一种计算量小而计算精度又高的新方法。参考文献[1]严蔚敏，吴伟民.数据结构[M],清华大学出版社，1994.[2]谭振强，陈萃萌，曾颜.计算机应用[M],Vollg.No.10,1999.[3]王国谨等.计算机辅助几何设计[M],高等教育出版社，2001.[4]施法叶.计算机辅助几何设计与非均匀有理B样条[M],北京航天航空出版社，2002.[5]孙宏伟，马玉林.数控加工仿真器加工代码的计算机识别[J],CAD/CAPP/CAM及PDM技术，2000(5):24-26.[6]张丽英，孙家瞰，王习贞，等.计算机应用，数控加工后置处理技术[J],计算机辅助设计与制造，1999.12-15.[7]谭哲丽，李克天，郑德涛.参数化转换凸轮轮廓及自动生成NC代码[J].机床与液压，2001(6):29-31.[8]李薇，张永岩.基于CATIA的数控加工程序逆向转换软件开发与应用[J].软件天地，2001(2):55-57.[9]朱心雄.自由曲线曲面技术[M],科学出版社，2000. 76[10]王仁宏等.计算几何[M],科学出版社，2008.6.附录附录1：DDA直线生成程序ddaline(xa,ya,xb,yb,c)intxa,ya,xb,yb,c;(floatdeltax,deltay,x,y;intdx,dy,steps,k;dx=xb-xa;dy=yb-ya;if(abs(dx)>abs(dy))steps=abs(dx);elsesteps=abs(dy);delta_x=(float)dx/(float)steps;delta_y=(float)dy/(float)steps;x=xa;y=ya；set_pixel(x,y,c);for(k=1;k<=steps;k++){x+=delta_x;y+=delta_y;set_pixel(x,y,c);}}附录2：中点画线算法程序voidMidpointLine(intx0,inty0,intx1,inty1,intcolor){inta,b,d1,d2,d,x,y；a=yO-y1；b=x1-xO；d=2*a+b；d1=2*a；d2=2*(a+b)；x=x0；y=y0；drawpixel(x,y,color);while(x 77{if(d<0){x++；y++；d+=d2;}else{x++；d+=d1;}drawpixel(x,y,color);}/*while*/}/*midPointLine*/附录3：适用于直线所有八个方向的Bresenham直线生成算法voidline(x1,y1,x2,y2,c)intx1,y1,x2,y2,c;intdx;intdy;intx;inty;intp;intconst1;intconst2;intinc;inttmp;dx=x2-x1;dy=y2-yl;if(dx*dy>=0)/*准备x或y的单位递变值。*/inc=1;elseinc=-1;if(abs(dx)>abs(dy)){if(dx<0){tmp=xl;/*将2a,3a象限方向*/xl=x2;/*的直线变换到la,4a*/x2=tmp;tmp=yl;/*象限方向去*/yi=y2；dx=-dy;dy=-dy;p=2*dy-dx;constl=2*dy;/*注意此时误差的*/const2=2*(dy・dy);/*变化参数取值.*/x=x1;y=yl; 78set_pixel(x,y,c);while(x 79x+=inc;p+=const2;setpixel(x,y,c);)})附录4：直线生成算法的改进程序bresenham算法的改进程序如下：voidBresenhamline(intxO,intyO,intx1,inty1,intcolor)intx,y,dx,dy,eO;dx=x1-xO;dy=y1-yO;eO=-dx;x=xO;y=yO;for(i=0;i<=dx;i++){putpixel(x,y,color);x++;e0=e0+2*dy;if(eO>=dx)e0=e0-2*dx;if(e0>=0)y++;}附录5：椭圆的Bresenham算法程序#include 80putpixel(-x+300,-y+200,4);putpixel(-x+300,y+200,4);putpixel(x+300,-y+200,4);while(b*b*(x+l) 81}else(d2+=a*a*(-2*y+3);y-;}putpixel(x+300,y+200,4);putpixel(-x4-300,-y+200,4);putpixel(-x+300,y+200,4);putpixel(x+300,-y+200,4);intmain(){voidMidBresenhamllipse(doublea,doubleb);intgdriver=DETECT,gmode;/*自动测试硬件*/registerbgidriver(EGAVGAdriver);/*该函数告诉连接程序在连接时把EGAVGA的驱动程序装入到用户的执行程序中。*/initgraph(&gdriver,&gmode,"c:\\tcM);/*根据测试结果初始化图形*/setbkcolor(CYAN);cleardevice();MidBresenhamllipse(100,80);delay(1000);getch();closegraph();return0;}附录6：直线裁剪的Sutherland-Cohen算法程序#defineLEFT1#defineRIGHT2 82#defineBOTTOM4#defineTOP8intencode(floatx,floaty){intc=0;if(x 83elseif(TOP&code!=0){y=YT；x=xl+(x2-xl)*(YT-yl)/(y2-yl);)if(code==code1){x1=x;y1=y;code1=encode(x,y);)else{x2=x;y2=y;code2=encode(x,y);}displayline(x1,y1,x2,y2);}附录7：直线裁剪的中点分割算法程序/*ZDFG中点分割算法*/#defineLEFT1#defineRIGHT2#defincBOTTOM4#defineTOP8#defineXL150#defineXR350//defineYB150#defineYT300#include 84line(XR,YT,XR,YB);xl=50;yl=200;x2=400;y2=300;setcolor(1);Iine(xl,yl,x2,y2);xx=O;yy=o；xxx=O;yyy=o；draw_ett(xI,yl,x2,y2,&xx,&yy);draw_ett(x2,y2,xx,yy,&xxx,&yyy);if(getch()==,c,||getch()==,C,)clearviewport();setcolor(14);reline(xx,yy,xxx,yyy);getch();closegraph();}reline(intx1,inty1,intx2,inty2)/*重画裁剪后线段*/(line(x1,y1,x2,y2);encode(x,y,code)/*编码，判断各点是否在视口域*/intx,y;int*code;{intc;c=0;if(x 85return;draw_ett(xl,yl,x2,y2,x,y)/*^点判断♦/intx1,x2,y1,y2;int*x,*y;{intcodel,code2,code;intxx,yy;longd,d1,d2;encode(x1,y1,&code1);encode(x2,y2,&code2);if(code2==0){xx=x2;yy=y2；*x=xx;*y=yy;return;}if((codel&code2)!=0)return;L1:xx=(x1+x2)/2;yy=(yl+y2)/2;encode(xx,yy,&code);dl=lL*(yy-yl)*(yy-yl);d2=lL*(xx-xl)*(xx-xl);d=sqrt(d1+d2);if(d<=l){*x=xx;*y=yy;return;}if((code&codel)!=0){x1=xx;yi=yy；else{x2=xx;y2=yy;}gotoL1;)附录8：梁友栋一Barskey算法的直线裁剪程序 86voidLB_LineClip(xl,yl,x2,y2,XL,XR,YB,YT)floatxl,yl,x2,y2,XL,XR,YB,YT;{floatdx,dy,u1,u2;tl=O;tu=1;dx=x2-x1;dy=y2-y1;if(ClipT(-dx,xl-Xl,&ul,&u2)if(ClipT(dx,XR-xl,&ul,&u2)if(ClipT(-dy,yl-YB,&ul,&u2)if(ClipT(dy,YT-yl,&ul,&u2){displayline(xl+ul*dx,yl+ul*dy,xl+u2*dx,yl4-u2*dy)return;)}boolClipT(p,q,u1,u2)floatp,q,*u1,*u2;{floatr;if(P<0){r=q/p;if(r>*u2)returnFALSE;elseif(r>*u1){*u1=r;returnTRUE;}}elseif(p>0){r=p/q;if(r<*u1)returnFALSE;elseif(r<*u2){*u2=r;returnTRUE;})elseif(q<0)returnFALSE;returnTRUE;
此文档下载收益归作者所有
