计算机图形学算法基础作业

《计算机图形学算法基础作业》由会员分享，可在线阅读，更多相关《计算机图形学算法基础作业（82页珍藏版）》请在装配图网上搜索。

1、计算机图形学算法基础作业姓名： LH 学院： 理学院 专业： 计算数学 时间： 2010-12-31 LH 的计算机图形学作业I目录1 直线段生成算法综述.11.1 生成直线的 DDA 方法.11.1.1 DDA 算法基本原理.11.1.2 DDA 算法实现步骤.11.1.3 DDA 算法程序（或伪程序）描述.21.1.4 DDA 算法流程图.21.2 生成直线的 Bresenham 算法.31.2.1 Bresenham 算法基本原理.31.2.2 Bresenham 算法实现步骤.51.2.3 Bresenham 算法程序（或伪程序）描述.51.2.4 Bresenham 算法流程图.51

2、.3 中点画线算法.21.3.1 中点画线算法基本原理.21.3.2 中点画线算法实现步骤.31.3.3 中点画线算法程序（或伪程序）描述.31.3.4 中点画线算法流程图.31.4 生成直线算法的进一步改进.51.5 各种直线生成算法的优缺点对比分析.61.6 直线生成算法的发展趋势.72 椭圆的 Bresenham 生成算法.7LH 的计算机图形学作业II2.1 椭圆曲率分析.72.2 椭圆方程分析.72.3 椭圆生成算法.92.3.1 算法实现过程.92.3.2 算法流程图.102.3.3 算法程序描述.113 直线段裁剪算法综述.113.1 Sutherland-Cohen 裁剪算法.

3、113.1.1 Sutherland-Cohen 算法基本原理.113.1.2 Sutherland-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 其余一些改进的直线裁剪算法.16LH 的计算机图

4、形学作业III3.6 各种直线裁剪算法的优缺点对比分析.163.7 直线裁剪算法的发展趋势.164 图形求交技术.164.1 求交点算法.164.1.1 线与线的交点的求法.174.2.2 线与面的交点的求法.184.2 求交线算法.194.3 包含判定算法.214.4 重叠判定算法.264.5 凸包计算.265 自由曲线曲面造型技术.285.1 Bezier 曲线和曲面.285.1.1 Bezier 曲线.285.1.2 Bezier 曲面.315.2 B 样条曲线与曲面.325.2.1 B 样条的递推定义和性质.325.2.2 B 样条曲线.345.2.5 B 样条曲面.365.3 NUR

5、BS 曲线与曲面.375.3.1 NURBS 曲线.375.3.2 非均匀有理 B 样条（NURBS）曲面.395.4 Coons 曲面.40LH 的计算机图形学作业IV5.4.1 基本概念.405.4.2 双线性 Coons 曲面.415.4.3 双三次 Coons 曲面.426 CAGD 中有关曲线曲面、拼接技术.44nCnG6.1 基本原理.446.2 Bezier 曲线的的拼接条件.44001122CGCGCG、6.3 Bezier 曲面的的拼接条件.460011CGCG、7 图形变换技术.487.1 二维图形几何变换.497.1.1 平移(Translation).497.1.2 旋

6、转(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 平行投影(parallel projection).587.4.2 透视投影(perspective projection).60LH 的计算机图形学作业V8 图形消隐算法.618.1 扫描线 Z-buffer 算法.618.2 区域子分割算法.618.3 光线投射算法.628.4 平面公式法

7、.628.5 径向预排序法.638.6 径向排序法.638.7 隔离平面法.638.8 深度排序法.638.9 光线跟踪法.638.10 Z 缓冲区法.648.11 极值检测法.648.12 深度分类方法.648.13 八叉树方法.659 图形学若干基本算法的实现研究.65参考文献.68附录.68LH 计算机图形学作业：共九道题1图形学算法基础作业图形学算法基础作业1 直线段生成算法综述1.1 生成直线的 DDA 方法1.1.1 DDA 算法基本原理DDA 是数字微分分析式（Digital Differential Analyzer）的缩写。设直线之起点为，终点为，则斜率为：11x ,y（）2

8、2x ,y（）k2121y -ydyk =x -xdx直线中的每一点坐标都可以由前一点坐标变化一个增量而得到，即表示xyD ,D为递归式：iixiiyx1xDy1yD 并有关系：yxD m D递归式的初值为直线的起点，这样，就可以用加法来生成一条直线。11x ,y（）1.1.2 DDA 算法实现步骤具体方法是：按照直线从到的方向不同，分为 8 个象限（见图 1.1） 。对于方向11x ,y（）22x ,y（）在第 1a 象限内的直线而言，。对于方向在第 1b 象限内的直线而言，xyD1Dm，取值。各象限中直线生成时的取值列在表 1-1 之中。yxD1D1/ m，xyD , D图 1.1 直线方

9、向的 8 个象限图表 1-1 各象限中直线生成时的取值列xyD , DLH 计算机图形学作业：共九道题2象限dxdy?xDyD1a1b2a2b3a3b4a4bTFTFTFTF11/m-1-1/m-1-1/m11/mm1m1-m-1-m-1研究表中的数据，可以发现两个规律：1、当时；否则：dxdyxyD=1, D= mxyD =1/ m D=1，2、的符号与的符号相同。这两条规律可以导致程序的简化。由上xyD , Ddx, dy述方法写成的程序如附录 1 所示。其中 steps 变量的设置，以及等语句，正是利用了上述两条规律，使得程序变得简练。xyD = dx/steps; D = dy/ste

10、ps使用 DDA 算法，每生成一条直线做两次除法，每画线中一点做两次加法。因此，用 DDA 法生成直线的速度是相当快的。1.1.3 DDA 算法程序（或伪程序）描述具体程序见附录 1。1.1.4 DDA 算法流程图（略）1.2 中点画线算法1.2.1 中点画线算法基本原理假定直线斜率在之间，当前象素点为，则下一个象素点有k01pp(x ,y )两种可选择点或。若与的中点称1ppP (x1,y )2ppP (x1,y1)1P2Ppp(x1,y0.5)为 M，Q 为理想直线与垂线的交点。当M 在 Q 的下方时，则取应pxx12P为下一个象素点；当M 在 Q 的上方时，则取为下一个象素点。这就是中1

11、P点画线法的基本原理。LH 计算机图形学作业：共九道题31.2.2 中点画线算法实现步骤下面讨论中点画线法的实现。过点、的直线段 L 的方程00(x ,y )11(x ,y )式为，其中，F(x,y)axbyc00101ayy ,bxx0110cx yx y，要 判断中点 M 在 Q 点的上方还是下方，只要把M 代入，并判断它F(x,y)的符号即可。为此，我们构造判别式:ppppdF(M)F(x1,y0.5)a(x1)b(y0.5)c 当时， M 在 L(Q 点)下方，取为下一个象素；d02P 当时， M 在 L(Q 点)上方，取为下一个象素；d01P 当时，选或均可，约定取为下一个象素 。d

12、01P2P1P注意到是的线性函数，可采用增量计算，提高运算效率。dppx ,y若当前象素处于情况，则取正右方象素,要判下一个象素位d01ppP (x1,y )置，应计算，增量为 a。1ppppdF(x2,y0.5)a(x2)b(y0.5)cda 若时，则取右上方象素。要判断再下一象素，则要d02ppP (x1,y1)计算，增量为2ppppdF(x2,y1.5)a(x2)b(y1.5)cdab。画线从开始，的初值ab00(x , y )d，因，所以。00000dF(x1,y0.5)F(x ,y )a0.5b00F(x ,y )00da0.5b 由于我们使用的只是的符号，而且的增量都是整数，只是初

13、始值包dd含小数。因此，我们可以用代替来摆脱小数，写出仅包含整数运算的算2dd法程序。1.2.3 中点画线算法程序（或伪程序）描述具体程序见附录 21.2.4 中点画线算法流程图 （略）1.3 生成直线的 Bresenham 算法1.3.1 Bresenham 算法基本原理本算法由 Bresenham 在 1965 年提出。设直线从起点到终点。直11x , y（）22x , y（）线可表示为方程。其中y = kx+b11b = yk x2121y - ydyk =x -xdxLH 计算机图形学作业：共九道题4我们讨论先将直线方向限于 1a 象限（图 1.1）在这种情况下，当直线光栅化时，x 每

14、次都增加 1 个单元，即 。而 y 的相应增加应当小于 1。为了光栅化，iix1= x +1只可能选择如图 1.2 两种位置之一。iy +1图 1.2 的位置选择iy +1图 1.2 中 的位置选择 或者 iy +1iiy -1= yiiy +1= y +1选择的原则是看精确值与及的距离 d1 及 d2 的大小而定。计算式为：yiyiy +1iiiy = m x +1 +b (1.2.1)d1= y- y (1.2.2)d2 = y +1- y (1.2.3)如果，则，否则。因此算法的关键在于简便地求出d1-d2 0iiy +1= y +1iiy +1= y的符号。将式（1.2.1） 、 （1

15、.2.2） 、 （1.2.3）代入，得d1-d2d1-d2iiidyd1-d2 = 2y-2y -1= 2(x +1)-2y +2b-1dx用乘等式两边，并以代入上述等式，得dxiP = dx d1-d2iiiP = 2x dy-2y dx+2dy+dx 2b-1 (1.2.4)是我们用以判断符号的误差。由于在 1a 象限，总大于 0，所以仍旧可以d1-d2dxiP用作判断符号的误差。为：iP1iiiiP +1= P +2dy-2dx y +1-y (1.2.5)误差的初值 P1，可将 x1, y1，和 b 代入式（2.1.4）中的而得到：xi, yi1P = 2dy-dx1.3.2 Bres

16、enham 算法实现步骤综述上面 1.3.1 的推导，第 1a 象限内的直线 Bresenham 算法思想如下：1、画点(x1, y2); dxx2x1; dyy2y1；计算误差初值 P1=2dy-dx; i=1；LH 计算机图形学作业：共九道题52、求直线的下一点位置：xi+1=xi+1；if Pi0 则 yi+1=yi+1；否则 yi+1=yi；3、画点（xi+1, yi-1） ；4、求下一个误差 Pi+1；if Pi0 则 Pi+1=Pi+2dy-2dx;否则 Pi+1=Pi+2dy；5、i=i+1; if i dy别将 2a,3a 象限的直线和 3b,4b 象限的直线变换到 1a,4a

17、 和 2b,1b 方向去，以求得程序处理的简洁。1.3.4 Bresenham 算法流程图（略）1.4 生成直线算法的进一步改进除过前面所讲到的 3 种基本直线生成算法外，还有一些其它的方法，由于过多，这里仅列举几种如下：（1）二步法。虽然 Bresenham 直线生成算法是一效率很高的算法，但是人们仍在寻找更有校的算法。1987 年又有人提出了一种二步法。即每循环一次不是绘制一个像素，而是绘制两个像素，这样无疑可把生成直线的速度提高一倍。（2）改进的 Bresenham 算法。对于对于传统的直线生成算法，人们往往把注意力集中在算法本身，却忽略了算法之外的一些有用信息:画线之前，从起点坐标和终

18、点坐标，我们就可以获知该线段的斜率，由此可进一步得出在主轴方向连续走 l 个步长，在副轴方向才走一个坐标单位，这就是本算法提高 Bresenham 算法执行效率的一个方面。提高算法效率的第二个方面是利用线段本身的对称性，则新算法所产生的起点一侧的半条线段与用 Bresenham 算法产生的相同。至于终点一侧的半条线段，可以看成以终点为起点线段的生成。LH 计算机图形学作业：共九道题6算法实现：特殊地，对于水平线()，垂直线()和对角线()，它们都可直y0 x0 xy接装人帧缓冲器，而无需进行画线算法处理。从以上的描述可以实现优于 Bresenham 的直线生成算法。其中待生成直线的已知数据为:

19、为线段起点的横、纵坐标；为线段终点的横、纵坐标。11(x ,y )22(x ,y )算法的输人数据为: ，。11(x ,y )22(x ,y )（3）基于类最佳逼近的散步直线生成算法。一种新的直线逼近方法类最佳逼近,基于这种逼近方法,斜率的直线和斜率为的直线具有某种互补性质。k0,0.51 k利用该性质,设计出一种新的三步直线方法,该算法揭示了直线计算的互补性,理论简单,精度达到最好。这种算法改善了 Bresenham 算法和双步算法的计算效率。该算法对于硬件实现将更有益处。除此之外直线生成算法还有对称扫描四步增量画线算法、基于 Bresenham 的高效直线生成集成算法、基于 Bresenh

20、am 算法的四步画直线算法、基于直线特性的直线生成集成算法、基于自适应步长的直线生成算法、基于等分像素点的直线生成算法、6步直线生成算法、基于对角线行程的直线生成算法等等。1.5 各种直线生成算法的优缺点对比分析DDA 算法的优点是：绘制实数直线效果好，误差小；缺点是：实现较复杂，不利于硬件实现。因为该算法涉及到实数乘除法运算，y 与 k 必须用浮点数表示，而且每一步都要对 y 四舍五入后取整。中点画线算法优点是：只有整数运算，不含乘除法；可用硬件实现。Bresenham 算法的优点是：1、不必计算直线之斜率，因此不做除法；2、不用浮点数，只用整数；3、只做整数加减法和乘 2 运算，而乘 2

21、运算可以用硬件移位实现。4、Bresenham 算法速度很快，并适于用硬件实现。1.6 直线生成算法的发展趋势（略）2 椭圆的 Bresenham 生成算法2.1 椭圆曲率分析椭圆（为沿轴方向的长半轴长度，为沿轴方向的cos , sinrat btaxbyLH 计算机图形学作业：共九道题7短半轴长度，且） ，曲率为，在第一象限ab22223/2/(sincos)rkabatbt，将对 求导数，有，即曲率为减函数，在点（即）0,/ 2trktd/d0rkt ( ,0)a0t 处的曲率；在点（即）处的曲率。半径2(0)/r tka b(0, )b/ 2t2(/2)/r tkb a为的圆的曲率为，半

22、径为的圆的曲率为，两圆的曲率关系为a2/a ab2/b b，则两圆的曲率在椭圆上点与的曲率之间，四者的22/()b ba aab( ,0)a(0, )b关系为：。22/1/1/a bbab a2.2 椭圆方程分析根据椭圆及圆的曲率分析，椭圆弧分别由半径为和的圆弧逼近生成。为了更ab准确的由圆弧生成椭圆弧，在椭圆弧上确定一点，将椭圆弧分成曲率较小和曲率较0P大的两段，椭圆方程为：。222222F x,y0b xa ya b其中为沿轴方向的长半轴长度，为沿轴方向的短半轴长度，且axby。由于椭圆的对称性，这里只要讨论第一象限椭圆弧的生成。将椭圆弧0ab分为上下两部分，以弧上曲率为-1 的点（即法向

23、量两个分量相等的点）作为分界。该椭圆上一点处的法向量为：( , )x y22FFN( , )ij2i 2jx yb xa yxy结合椭圆方程可计算出分界点的坐标为：0P。222222(/,/)aabbab以点为分界点，将第一象限的圆弧分成曲率较大和较小的两段弧。如图 2.1 所0P示，的椭圆弧，与半径为的圆在点到222/, ybabba1T (0, )a的圆弧上对应。在椭圆弧上任取一点，过作垂222222T (/,/)aababab1Q1QLH 计算机图形学作业：共九道题8直线与圆交于点，连接圆心与点，与轴的夹角为。则1P1PY椭圆的参数方程可表示为：sin,cos.xayb圆的参数方程可表示

24、为：sin,cos.xaya对于同一 ，椭圆弧上存在唯一的点与圆弧上的点对应，并且对应点的坐标存在如下关系：,( / )y.xxyb a 图 2.1 圆弧与椭圆弧对应点之一 图 2.2 圆弧与椭圆弧对应点之一如图 2.2 所示，半径为的圆上，从点到b222223T (/,/)aabbbab的圆弧与椭圆上的椭圆弧对应，在椭圆弧上任取一点4T ( ,0)b222(0,/)ybab，过作垂直线与圆交于点，连接圆心与点，与轴的夹角为。则2Q2Q2P2PY椭圆的参数方程可表示为：sin,cos.xayb圆的参数方程可表示为：sin,cos.xbybLH 计算机图形学作业：共九道题9对于同一 ，椭圆弧上存

25、在唯一的点与圆弧上的点对应，并且对应点的坐标存在如下关系：( /b) ,y.xaxy2.3 椭圆生成算法当圆弧上的点从沿着图 2.1、图 2.2 的对应关系方向变化到时，椭圆( ,0)a( ,0)b弧上相对应的点也从该方向变化到。( ,0)a2.3.1 算法实现过程1、计算分界点。000P (x ,y )2、用 Bresenham 算法生成两段圆弧、。半径为，1C2C1Ca；半径为，。2220,/xaab2Cb222y0,/bab3、将圆弧进行比例变换：方向的比例系数为 1，方向的比例系数为1Cxy；将圆弧进行比例变换：方向的比例系数为，方向的比例系数/b a2Cx/a by为 1。4、如图

26、2.3，已知椭圆上在第一象限的点，则椭圆上另外三个象限与Q(x,y)点对称的点分别为，因此只要画出在第一象限的Q(x,y)( x,y),( x,y),(x,y)图形，即可得到整个椭圆的图形。图 2.3 椭圆对称性2.3.2 算法流程图椭圆的 Bresenham 算法流程图如下：LH 计算机图形学作业：共九道题10计算分界点000Px ,y用 Bresenham 算法计算圆弧xyT ,T计算对应圆弧上的点结束用 Bresenham 算法计算圆弧xyT ,TYNYN图 2.4 椭圆的 Bresenham 算法流程图2.3.3 算法程序描述具体程序实现见附录 5。3 直线段裁剪算法综述裁剪裁剪：确定

27、图形中哪些部分落在显示区之内，哪些落在显示区之外,以便只显示落在显示区内的那部分图形。这个选择过程称为裁剪。直线段裁剪算法是复杂图元裁剪的基础。复杂的曲线可以通过折线段来近似，从而裁剪问题也可以化为直线段的裁剪问题。3.1 Sutherland-Cohen 裁剪算法3.1.1 Sutherland-Cohen 算法基本原理SutherlandCohen 算法分成两步。第一步是判断直线段是否完全在窗口内，若开始椭圆上点 Y 的坐标大于0y椭圆上点的 Y 坐标大于 0LH 计算机图形学作业：共九道题11在则该线段称为完全可见的；或可显然的决定线段完全在窗口的外边，称为完全不可见；对不能判断完全可见

28、或完全不可见的线段则要进行第二步处理。这时需要计算出直线段和窗口边界的一个交点，这个交点把直线分成两段，把其中一段显然完全不可见的线段抛弃，对余下的部分再作第一步判断，重复上述过程，直到直线段最后余下的部分可以用第一步的判断得出肯定结论为止。3.1.2 Sutherland-Cohen 算法实现步骤基本思想：对于每条线段分为三种情况处理分为三种情况处理:21pp（1）若完全在窗口内，则显示该线段，简称“取”之。21pp21pp（2）若明显在窗口外，则丢弃该线段，简称“弃”之。21pp（3）若线段不满足“取”或 “弃”的条件，则在交点处把线段分为两段。其中一段完全在窗口外，可弃之。然后对另一段重

29、复上述处理。为快速判断，采用如下编码方法：每个区域赋予 4 位编码（如图 3.1 所示）：lrbtCCCC其中：otheryyCotheryyCbt0101minmaxotherxxCotherxxClr0101minmax 100110000001101000000010010001010110 xLxRyTyB 图 3.1 区域编码 图 3.2 线段不能用编码确定若完全在窗口内 code1=0,且 code2=0,则“取”21pp若明显在窗口外 code1&code20，则“弃” 21pp在交点处把线段分为两段。其中一段完全在窗口外，可弃之。然后对另一段重复上述处理。xLH 计算机图形学作

30、业：共九道题12计算线段与窗口边界的交点 222111,yxpyxpif(LEFT&code !=0)x=XL;y=y1+(y2-y1)*(XL-x1)/(x2-x1);else if(RIGHT&code !=0)x=XR;y=y1+(y2-y1)*(XR-x1)/(x2-x1);else if(BOTTOM&code !=0) y=YB;x=x1+(x2-x1)*(YB-y1)/(y2-y1); else if(TOP & code !=0) y=YT;x=x1+(x2-x1)*(YT-y1)/(y2-y1);3.1.3 算法程序（或伪程序）描述过程 clip 描述了这一算法。其中用一个集

31、合(top,bottom,right,left)来表示端点的编码。具体程序见附录 6。3.1.4 算法流程图（略）3.2 中点分割裁剪算法3.2.1 中点分割算法基本原理与实现步骤与前一种 Cohen-Sutherland 算法一样首先对线段端点进行编码，并把线段与窗口的关系分为三种情况：完全可见、完全不可见和线段与窗口有交。对前两种情况，进行一样的处理。对于第三种情况，用中点分割的方法求出线段与窗口的交点。求线段与窗口的交点如下：设要裁剪的线段是。中点分割算法可分成两个过程平行进行，即从出发找01P P0P出离最近的可见点（图 3.3 中的 A 点） ，和从出发找出离最近的可见点（图0P1P

32、1P3.3 中的 B 点） 。这两个最近可见点的连线就是原线段的可见部分。从出发找出最近可见点的办法是先求的中点，若不能定为显然不0P01P PmP0mP P可见，则取代替，否则取代替，再对新的求中点。重复上述0mP P01P Pm1P P01P P01P PmP过程，直到长度小于给定的小数 为止。1mPP图 3.4 是求的最近可见点的算法框图。求的最近可见点的算法框图是一样0PP1P的，只要把和交换即可。0P1P在显示时 可取成一个像素的宽度，对分辨率为的显示器来说，上面讲的NN22二分的过程最多只要做 N 次。由于计算机过程只要做加法和除 2，所以特别适合用硬件来实现。LH 计算机图形学作

33、业：共九道题13如果允许两个找最近点的过程平行进行，这样的话可使裁剪速度加快，增加算法效率。图 3.3 中点分割算法3.2.2 算法程序（或伪程序）描述具体程序见附录 7。3.2.3 算法流程图中点分割算法框图如图 3.4。可见否?0Pm01P(PP )/ 21mPP ?显然不可见01P P显然不可见?0mP P0mPP1mPP0PPexit原线完全不可见0mPPexit否否否否是是是是图 3.4 中点分割算法框图LH 计算机图形学作业：共九道题143.3 梁友栋Barskey 算法3.3.1 梁友栋Barskey 算法基本原理与实现步骤设要裁剪的线段是，的坐标是。和窗口边界交于01P PiP

34、iix ,y ,i0,101P PA、B、C、D 四点，见图 3.5。算法基本思想是从 A，B 和三点中找出最靠近的点，0P1P图 3.5 中要找的点是，从 C，D 和三点中找出最靠近的点，图 3.5 中要找的点0P1P0P是 C 点。那么就是上的可见部分。0P C01P PxyyTyBxLxRABCD0P1P图 3.5 是可见部分0P C具体计算时要把写成参数方程01P P00 xxx tyyy t其中。把窗口边界的四条边分成两类，一类称为始边，1010 xxx , yyy 另一类称为终边。参数化形式写出裁剪条件:L1RB1TXxuxXYyuyY 可以统一表示为形式：kkqup 111221

35、311441pxqxXLpxqXRxpyqyYBpyqYTy 当且，则线段完全在边界外，则该线段平行于裁剪边界并0kp0kq0kq且在窗口内；当的情况下：当,线段从裁剪边界延长线的外部延伸到内部；当0kp0kp,线段从裁剪边界延长线的内部延伸到外部。kp0对于每条直线，可以计算出参数和，它们定义了在裁剪矩形内的线段部分，1u2uLH 计算机图形学作业：共九道题15的值由线段从外到内遇到的矩形边界所决定。对这些边界计算。1u0pkkkpqr/取 0 和各个值之中的最大值。的值由线段从内到外遇到的矩形边界所决定1ukr2u。对这些边界计算。取 1 和各个值之中的最小值。如果，0pkkkpqr/2u

36、kr21uu 则线段完全落在裁剪窗口之外，被舍弃。否则裁剪线段由参数的两个值，计算u1u2u出来。3.3.2 算法程序（或伪程序）描述具体程序见附录 8。3.3.3 算法流程图（略）3.4 快速算法 在实际绘图时，常出现大部分线段是可见的，或大部分线段为显然不可见。因而用最少的操作去判断被裁剪的线段是否属于这两种情况则可以提高裁剪的效率。此外，尽量减少比较和四则运算，也是提高效率的重要措施。这样会使程序长一点，但由于效率高，在软件包中值得采用。用这样的算法确定一根显然不可见线段平均只要做3.6 次比较，确定一根完全可见线段要用 8 次比较，而用 Sutherland-Cohen 算法做同样工作

37、则分别要做 11 次和 10 次比较。快速算法在最快的情况下要和四条边求交点，这要用 10 次加减法、5 次乘除法和 13 次比较。采用 Sutherland-Cohen 算法要做 16次加减法、8 次乘除法和 35 次比较。此外后者还要多次调用过程合作集合运算，这些都使它比快速算法效率低。3.5 其余一些改进的直线裁剪算法除过前面所讲到的 4 种基本直线裁剪算法外，还有一些其它的裁剪方法，由于过多，这里仅列举几种如下：（1）具有最少算术运算量的二维线裁剪算法。见文献：王骏，梁友栋，彭群生，具有最少算术运算量的二维线裁剪， 计算机学报 ，1991 年第 7 期。（2）一个有效的多边形窗口的线裁

38、剪算法。见文献：刘勇奎等，一个有效的多边形窗口的线裁剪， 计算机学报 ，1999 年第 11 期。（3）一种基于几何变换的高效的线裁剪新算法。见文献：汪乱，吴锐迅，蔡士杰。一种基于几何变换的高效的线裁剪新算法。 软件学报 ，1998，9(10): 728 一733。（4）任意多边形窗口的线裁剪算法。见文献：孙岩，唐棣:任意多边形窗口的线LH 计算机图形学作业：共九道题16裁剪， 2000 年图形学会议专刊)。3.6 各种直线裁剪算法的优缺点对比分析Sutherland-Cohen 直线裁剪算法要计算直线段与窗口边界的交点，这不可避免地要进行大量的乘除运算，必会降低程序的执行效率。而中点分割裁剪

39、算法却只需用到加法和除 2 运算，而除 2 运算在计算机中可以简单地用右移一位来实现，从而提高算法的效率。所以特别适合硬件实现，同时也适合于并行计算。3.7 直线裁剪算法的发展趋势（略）4 图形求交技术4.1 求交点算法求交点可以分两种情况：求线与线的交点以及求线与面的交点。4.1.1 线与线的交点的求法1、直线段与直线段的交点假设二条直线的端点分别为则它们可以用向量形式表示为：P1P2Q1Q2， P t = A+Bt (0t1)Q s = C+Ds (0s1) 其中，。AP1BP2P1CQ1DQ2Q1，构造方程A+Bt = C+Ds (4.1.1)对三维空间中的直线段来说，上述方程实际上是一

40、个二元一次方程组，由三个方程式组成。可以从其中两个解出，再用第三个验证解的有效性：若第三个方程成s,t立则说明找到了解，否则说明两条直线不相交。当所得的解是有效解时，可用iit , s（）二个线段方程之一计算交点坐标，例如。 iiP t= A+Bt我们还可以根据向量的基本性质，直接计算 s 与 t：对（4.1.1）两边构造点积得C X DA+Bt = C X DC+Ds（）（）（）由于 CXD 同时垂直于 C 和 D，等式右边为零。故有(C D) At(C D) B 类似地有LH 计算机图形学作业：共九道题17(AB) Cs(AB) D 完整的算法还应判断无解与无穷多解（共线）的情形，以及考虑

41、数值计算误差造成的影响。2、直线段与二次曲线的交点不失一般性，考虑平面上一条直线与同平面的一条二次曲线的交。假设曲线方程为 ，f x,y = 0直线段方程为 , 11x, y = x +tdx, y +tdy则在交点处有 。11f x +tdx, y +tdy = 0当曲线为二次曲线时，上述方程可写为2atbtc0用二次方程求根公式即可解出 t 值。3、圆锥曲线与圆锥曲线的交点圆锥曲线有代数法表示、几何法表示与参数法表示。在进行一对圆锥曲线的求交时，把其中一条圆锥曲线用代数/几何法表示为隐函数形式，另一条表示为参数形式（如二次 NURBS 曲线） 。将参数形式代入隐函数形式可得关于参数的四次方

42、程，可以使用四次方程的求根公式解出交点参数。得到交点后可再验证交点是否在有效的圆锥曲线段上。4.2.2 线与面的交点的求法1、直线段与平面的交点（如图 4.1）图 4.1 线段与平面求交LH 计算机图形学作业：共九道题18考虑直线段与无界平面的求交问题。把平面上的点表示为，P u,w = A+uB+wC直线段上的点表示为，二者的交点记为。假设线段不平行于平面，则 Q t = D+tER它们交于，即 R = P u,w = Q tA+uB+wC = D+tE等式两边点乘，得B X C（）B X CA+uB+wC = B X CD+tE（）（）（）（）由于既垂直于 B，又垂直于 C，故有B X C

43、B X CA = B X CD+tE（）（）（）可解出(B C) A(B C) Dt(B C) E类似求得(C E) D (C E) A(C E) Bu(B E) D (B E) A(B E) C如果是直线与平面区域求交点，则要进一步判断点是否在平面上的有效区域中，其算法可参见 4.2 节。2、圆锥曲线与平面的交点圆锥曲线与平面求交时，可以把圆锥曲线表示为参数形式，并把圆锥曲线的参数形式代入平面方程，即可得到参数的二次方程进行求解。3、圆锥曲线与二次曲面的交点 圆锥曲线与二次曲面求交时，可把圆锥曲线的参数形式代入二次曲面的隐式方程，得到参数的四次方程，用求根公式求解。4.2 求交线算法求交线显

44、然是指求面与面的交线，下面讨论几种常见的情况。1、平面与平面的交线在 CAD 中一般使用平面上有界区域。先考虑最简单的情形。两个平面区域分别由定义。如果它们不共面而且不分离，则必交于一直线P u,w , Q s,t , u, w, s, t 0, 1段。这条直线必落在所定义的无限直线上。注意这是个含有四个P u,w -Q s,t = 0未知数，三个方程式的方程组，只要分别与八条边界线方程：联立，即可求出线段的两个端点的参数。u = 0, u =1, w = 0, w =1, s = 0, s =1, t = 0, t =1在上述方程组中，只要找到两组解，就可以不再对剩余其它方程组求解。找到的两

45、组LH 计算机图形学作业：共九道题19解就是所求的交线段端点参数。当两个一般的多边形（即既可能是凸的，也可能是凹的，甚至可能带有内孔）相交时，可能有多段交线。我们可以把两个多边形分别记为 A 和 B，用如下的算法求出它们的交线：（1）把 A 的所有边与 B 求交，求出所有有效交点；（2）把 B 的所有边与 A 求交，求出所有有效交点；（3）把所有交点先按 y，再按 x 的大小进行排序；（4）把每对交点的中点与 A 和 B 进行包含性检测，若该中点即在 A 中又在 B 中，则该对交点定义了一条交线段。2、平面与二次曲面的交线求平面与二次曲面的交线有两种方法：代数法和几何法。用代数法考虑平面与二次

46、曲面求交问题时，可以把二次曲面表示为代数形式：222Ax +By +Cz +2Dxy+2Eyz+2Fxz+2Gx+2Hy+2Iz+J = 0可以通过平移与旋转坐标变换把平面变为 XOY 平面，对二次曲面进行同样的坐标变换。由于在新坐标系下平面的方程为，所以新坐标系下二次曲面方程中，把z0含 z 项都去掉即为平面与二次曲面的交线方程（在新坐标系下） 。对该交线方程进行一次逆坐标变换即可获得在原坐标系下的交线方程。在具体实现时，交线可以用二元二次方程系数表示（代数表示） ，辅之以局部坐标系到用户坐标系的变换矩阵。这种方法的缺点是，每当需要使用这些交线时，都要进行坐标变换。例如，判断一个空间点是否在

47、交线上，必须先对它进行坐标变换，变到平面上，再进行检测。需要z0绘制该交线时，也要先在局部坐标系下求出点坐标，再变换到用户坐标系下的坐标。所以交线采用另一种方法（几何表示）更合理。几何方法存储曲线的类型（椭圆、抛物线或双曲线） ，以及定义参数（中心点、对称轴、半径等大小尺寸）的数值信息，使用局部坐标系到用户坐标系的变换，把局部坐标系下的定义参数变换到用户坐标系直接使用。这第二种方法使用较少的变换，但需要用计算来判断曲线的种类，及计算曲线的定义参数。由于浮点运算的不精确性，容易发生判错类型以及定义参数误差过大的问题。当平面与二次曲面的交线需要精确表示时，往往采用几何法求交。二次曲面采用几何表示，

48、平面与二次曲面求交时，根据它们的相对位置与角度（根据定义参数） ，直接判断交线类型，其准确性大大优于用代数法计算分类的方法。几何法不需要对面进行变换，所以只要通过很少的计算就可以得到交线的精确描述。由于存储的信息是具有几何意义的，所以判断相等性、相对性等问题时，可以确定有几何意义的容差。下面以平面一球求交为例，说明几何法求交算法。LH 计算机图形学作业：共九道题20平面用一个记录 p 表示，p 的两子域 p.b, p.w 分别代表平面上一点与平面法向量。球面用记录 s 表示。它的两个子域 s.c, s.r 分别代表球面中心和半径。则可写出平面与球面相交的算法如下：plane_sphere_in

49、tersect(p, s)plane p;sphere s;d=球面中心到平面的有向距离；if(abs(d)=s.r) 二个面相交于一（切）点 s.c-d * p.w;else if (abs(d)s.r) 两个面无交；else 所求交线是圆。其圆半，半径，圆所在平面法向量为c=s.c-d * p. w;r=sqr t(s.r2-d2);w=p.w;一个平面与一个圆柱面可以无交、交于一条直线（切线） 、二条直线、一个椭圆或一个圆，可以用两个面的定义参数求出它们的相对位置关系和相对角度关系，进而判断其交属于何种情况，并求出交线的定义参数。平面与圆锥的交线也可类似求出。3、平面与参数曲面的交线 最

50、简单的方法是把参数曲面的表示代入平面方程 x s,t , y s,t , z s,t（）ax+by+cz+d = 0得到用参数曲面的参数 s、t 表示的交线方程ax s,t +by s,t +cz s,t +d = 0另一种方法是用平移和旋转变换对平面进行坐标变换，使平面成为新坐标系下的平面。再用相同的变换应用于参数曲面方程得到参数曲面在新坐标系下的方程xoy*x , y , z= xs,t , ys,t , zs,t（）（）由此得交线在新坐标系下的方程为。*zs,t0LH 计算机图形学作业：共九道题214.3 包含判定算法在进行图形求交时，常常需要判定两个图形间是否有包含关系。如点是否包含在

51、线段、平面区域、三维形体中，线段是否包含在平面区域、三维形体中，等等。许多包含判定问题可转化为点的包含判定问题，如判断线段是否在平面上可以转化为判断其两端点是否在平面上。因此下面主要讨论关于点的包含判定算法。判断点与线段的包含关系，也就是判断点与线的最短距离是否位于容差范围内。造型中常用的线段有三种：1、直线段；2、圆锥曲线段（主要是圆弧） ；3、参数曲线（主要是 Bezier，B 样条与 NURBS 曲线） 。点与面的包含判定也类似地分为三种情况。下面分别讨论。1、点与直线段的包含判定假设点坐标为，直线段端点为，则点 P 到线P x,y,z1111P x ,y ,z2222Px ,y ,z段

52、的距离的平方为12PP 2222211211211111222212121xxxxyyyyzzzzd2xxyyzzxxyyzz当时，认为点在线段（或其延长线）上，这时还需进一步判断点是否落在直线d20段的有效区间内。只要对坐标分量进行比较，假设线段两端点的 x 分量不等（否则所有分量均相等，那么线段两端点重合，线段退化为一点） ，那么当与反号1xx2xx时，点 P 在线段的有效区间内。2、点与圆锥曲线段的包含判定以圆弧为例，假设点的坐标为，圆弧的中心为，半径为 ，起x, y, z000 x , y , z（）r始角，终止角。这些角度都是相对于局部坐标系 x 轴而言。圆弧所在平面为12 ax+b

53、y+cz+d = 0先判断点是否在该平面上，若不在，则点不可能被包含。若在，则通过坐标变换，把问题转换到二维的问题。给定中心为，半径为 ，起始角，终止角的圆弧，对平面上一点00 x , y（）r12，判断 P 是否在圆弧上，可分二步进行。P x, y（）第一步判断 P 是否在圆心为，半径为 的圆的圆周上，即下式是否成立：00 x , y（）r 2200()()rxxyyLH 计算机图形学作业：共九道题22第二步判断 P 是否在有效的圆弧段内。3、点与参数曲线的包含判定设点坐标为，参数曲线为。点也参数曲线的求P x, y, z Q t = x t , y t , z t交计算包括三个步骤：（1）

54、计算参数 值，使到的距离最小；tP Q t（2）判断 是否在有效参数区间内（通常为） ；t01，（3）判断与的距离是否小于 。若（2） ， （3）步的判断均为“是” ，则 Q tP 点在曲线上；否则点不在曲线上。第一步应计算 ，使得最小，即t P Q t 2R t = P-Q tP-Q t= P-Q t最小根据微积分知识，在该处即R (t) = 0 Q (t) P-Q t= 0用数值方法解出 值，再代入曲线参数方程可求出曲线上对应点的坐标。第（2） 、t（3）步的处理比较简单，不再详述。4、点与平面区域的包含判定设点坐标为，平面方程为。则点到平面的距离为P x, y, zax+by+cz+d

55、= 0 222ax+by+cz+dr =a +b +c若 ，则认为点在平面上，否则认为点不在平面上。在造型系统中，通常使r用平面上的有界区域作为形体的表面。在这种情况下，对落在平面上的点还应进一步判别它是否落在有效区域内。若点落在该区域内，则认为点与该面相交，否则不相交。下面以平面区域多边形为例，介绍有关算法。判断平面上一个点是否包含在同平面的一个多边形内，有许多种算法，这里仅介绍常用的三种：叉积判断法、夹角之和检验法以及交点计数检验法。（1）叉积判断法假设判断点为。多边形顶点按顺序排列为。如图 4.2 所示。令0P12nPPP。那么，在多边形内的充要条件是叉积ii0n1VPP , i1, 2

56、, , n, V1V 0P的符号相同。叉积判断法仅适用于凸多边形。当多边形为iiV X V +1 i1, 2, , n、凹时，尽管点在多边形内也不能保证上述叉积符号都相同。这时可采用后面介绍的两LH 计算机图形学作业：共九道题23种方法。图 4.2 叉积判断法（2）夹角之和检验法假设某平面上有点和多边形，如图 4.3 所示。将点分别与相连，0P12345PP P P P0PiP构成向量。假设角 。如果，则点在多边形之外，i0VPPi0iiPP P1 051 ii 0P如图 4.3(a)所示。如果，则点在多边形之内，如图 4.3(b)所示。可 251 ii0Pi通过下列公式计算：令, ，则，所以

57、iiiSVXV1iiiCV V1 iiitgS /C且的符号即代表角度的方向。iiiarctg S /Ci图 4.3 夹角之和检验法在多边形边数不太多（ 0 x,y,z（）见的或隐的） ；如果，则观察点在凸型多面体外部（称该表面是可见） ，Ax+By+Cz+D 0，则平面式可见面，应被画出。D abs(dy) steps=abs(dx);else steps=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=ste

58、ps; k+)x+=delta_x;y+=delta_y;set_pixel(x, y, c); 附录附录 2 2：中点画线算法程序：中点画线算法程序void Midpoint Line (int x0,int y0,int x1, int y1,int color) int a, b, d1, d2, d, x, y； a=y0-y1； b=x1-x0；d=2*a+b； d1=2*a；d2=2* (a+b)； x=x0；y=y0； drawpixel(x, y, color); while (xx1) if (d=0) /*准备 x 或 y 的单位递变值。*/ inc=1;elseinc=-

59、1;if (abs(dx)abs(dy) if(dx0) tmp=x1; /*将 2a, 3a 象限方向*/ x1=x2; /*的直线变换到 1a, 4a*/ x2=tmp; tmp=y1; /*象限方向去*/ y1=y2; dx=-dy; dy=-dy; LH 计算机图形学作业：共九道题68 p=2*dy-dx; const1=2*dy; /*注意此时误差的*/ const2=2*(dy-dy); /*变化参数取值. */ x=x1; y=y1; set_pixel(x, y, c); while (xx2) x+; if (p0) p+=const1; else y+=inc; p+=co

60、nst2; set_piexl(x, y, c); else if (dy0) tmp=x1; /* 将 3b, 4b 象限方向的*/ x1=x2; /*直线变换到 2b, 1b */ x2=tmp; /*象限方向去. */ tmp=y1;y1=y2;dx=-dy;dy=-dy;p=2*dx-dy; /*注意此时误差的*/const1=2*dx; /*变化参数取值. */const2=2*(dx-dy);x=x1;y=y1;set_pixel (x, y, c);LH 计算机图形学作业：共九道题69 while (yy2) y+; if(p0) p+=const1; elsex+=inc;p+

61、=const2;set_pixel (x, y, c); 附录附录 4 4：直线生成算法的改进程序：直线生成算法的改进程序bresenham 算法的改进程序如下：void Bresenhamline (int x0,int y0,int x1, int y1,int color) int x, y, dx, dy, e0; dx = x1-x0;dy = y1- y0; e0=-dx; x=x0; y=y0;for (i=0; i=dx) e0=e0-2*dx; if (e0=0) y+; 附录附录 5 5：椭圆的：椭圆的 BresenhamBresenham 算法程序算法程序#include

62、#includevoid MidBresenhamllipse(double a,double b) double x,y, d1,d2;LH 计算机图形学作业：共九道题70 x=0;y=b; d1=b*b+a*a*(-b+0.25); putpixel(x+300,y+200,4); putpixel(-x+300,-y+200,4); putpixel(-x+300,y+200,4); putpixel(x+300,-y+200,4); while(b*b*(x+1)a*a*(y-0.5) if(d10) if(d2=0) d2+=b*b*(2*x+2)+a*a*(-2*y+3); x+;

63、LH 计算机图形学作业：共九道题71 y-; else d2+=a*a*(-2*y+3); y-; putpixel(x+300,y+200,4); putpixel(-x+300,-y+200,4); putpixel(-x+300,y+200,4); putpixel(x+300,-y+200,4); int main() void MidBresenhamllipse(double a,double b); int gdriver=DETECT, gmode; /*自动测试硬件*/ registerbgidriver(EGAVGA_driver); /* 该函数告诉连接程序在连接时把 E

64、GAVGA 的驱动程序装入到用户的执行程序中。 */ initgraph(&gdriver, &gmode, c:tc); /* 根据测试结果初始化图形*/ setbkcolor(CYAN); cleardevice(); MidBresenhamllipse(100,80); delay(1000); getch(); closegraph(); return 0; 附录附录 6 6：直线裁剪的：直线裁剪的 Sutherland-CohenSutherland-Cohen 算法程序算法程序#define LEFT 1#define RIGHT 2LH 计算机图形学作业：共九道题72#defi

65、ne BOTTOM 4#define TOP 8int encode(float x,float y) int c=0; if(xXR) c|=RIGHT; if(xYB) c|=BOTTOM; if(xYT) c|=TOP; retrun c;void CS_LineClip(x1,y1,x2,y2,XL,XR,YB,YT)float x1,y1,x2,y2,XL,XR,YB,YT;/(x1,y1)(x2,y2)为线段的端点坐标，其他四个参数定义窗口的边界 int code1,code2,code; code1=encode(x1,y1); code2=encode(x2,y2); whil

66、e(code1!=0 |code2!=0) if(code1&code2 !=0) return; code = code1; if(code1=0) code = code2; if(LEFT&code !=0) x=XL; y=y1+(y2-y1)*(XL-x1)/(x2-x1); else if(RIGHT&code !=0) x=XR; y=y1+(y2-y1)*(XR-x1)/(x2-x1); else if(BOTTOM&code !=0) y=YB;x=x1+(x2-x1)*(YB-y1)/(y2-y1);else if(TOP & code !=0)LH 计算机图形学作业：共九道题73 y=YT; x=x1+(x2-x1)*(YT-y1)/(y2-y1); 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 7：直线裁剪的中点分割算法程序：直线裁剪的中点分割算法程序/*ZDFG 中点分割算法 */