计算机图形学课程设计
计算机图形学算法基础作业
姓名： LH
学院：理学院
专业：计算数学
时间： 2010-12-31
目录
1 直线段生成算法综述 (1)
1.1 生成直线的DDA方法 (1)
1.1.1 D D A算法基本原理 (1)
1.1.2 D D A算法实现步骤 (1)
1.1.3 D D A算法程序（或伪程序）描述 (2)
1.1.4 D D A算法流程图 (2)
1.2 生成直线的Bresenham算法 (3)
1.2.1 B re s e nh a m算法基本原理 (3)
1.2.2 B re s e nh a m算法实现步骤 (5)
1.2.3 B re s e nh a m算法程序（或伪程序）描述 (5)
1.2.4 B re s e nh a m算法流程图 (5)
1.3 中点画线算法 (2)
1.3.1 中点画线算法基本原理 (2)
1.3.2 中点画线算法实现步骤 (3)
1.3.3 中点画线算法程序（或伪程序）描述 (3)
1.3.4 中点画线算法流程图 (3)
1.4 生成直线算法的进一步改进 (5)
1.5 各种直线生成算法的优缺点对比分析 (6)
1.6 直线生成算法的发展趋势 (7)
2 椭圆的Bresenham生成算法 (7)
2.1 椭圆曲率分析 (7)
2.2 椭圆方程分析 (7)
2.3 椭圆生成算法 (9)
2.3.1 算法实现过程 (9)
2.3.2 算法流程图 (10)
2.3.3 算法程序描述 (11)
3 直线段裁剪算法综述 (11)
3.1 Sutherland-Cohen裁剪算法 (11)
3.1.1 S ut h e rl a nd-C oh e n算法基本原理 (11)
3.1.2 S ut h e rl a nd-C oh e n算法实现步骤 (11)
3.1.3 算法程序（或伪程序）描述 (12)
3.1.4 算法流程图 (12)
3.2 中点分割裁剪算法 (12)
3.2.1 中点分割算法基本原理与实现步骤 (12)
3.2.2 算法程序（或伪程序）描述 (13)
3.2.3 算法流程图 (13)
3.3 梁友栋－Barskey算法 (14)
3.3.1 梁友栋－B a r s ke y算法基本原理与实现步骤 (14)
3.3.2 算法程序（或伪程序）描述 (15)
3.3.3 算法流程图 (15)
3.4 快速算法 (15)
3.5 其余一些改进的直线裁剪算法 (16)
3.6 各种直线裁剪算法的优缺点对比分析 (16)
3.7 直线裁剪算法的发展趋势 (16)
4 图形求交技术 (16)
4.1 求交点算法 (16)
4.1.1 线与线的交点的求法 (17)
4.2.2 线与面的交点的求法 (18)
4.2 求交线算法 (19)
4.3 包含判定算法 (21)
4.4 重叠判定算法 (26)
4.5 凸包计算 (26)
5 自由曲线曲面造型技术 (28)
5.1 Bezier曲线和曲面 (28)
5.1.1 B ez i e r曲线 (28)
5.1.2 B ez i e r曲面 (31)
5.2 B样条曲线与曲面 (32)
5.2.1 B样条的递推定义和性质 (32)
5.2.2 B样条曲线 (34)
5.2.5 B样条曲面 (36)
5.3 NURBS曲线与曲面 (37)
5.3.1 N UR B S曲线 (37)
5.3.2 非均匀有理B样条（N U R B S）曲面 (39)
5.4 Coons 曲面 (40)
5.4.1 基本概念 (40)
5.4.2 双线性C o o n s 曲面 (41)
5.4.3 双三次C o o n s 曲面 (43)
6 CAGD 中有关曲线曲面n C 、n G 拼接技术 (44)
6.1 基本原理 (44)
6.2 Bezier 曲线的001122C G C G C G 、、、、、的拼接条件
...... 44 6.3 Bezier 曲面的0011C G C G 、、、的拼接条件 .............
46 7 图形变换技术 (49)
7.1 二维图形几何变换 (49)
7.1.1 平移(T r a ns l a ti o n ) (49)
7.1.2 旋转(R o t at i o n) (50)
7.1.3 变比(s c a li n g ) (51)
7.2 三维图形几何变换 (51)
7.2.1 平移 (51)
7.2.2 旋转 (52)
7.2.3 变比 (54)
7.3 参数图形几何变换 (54)
7.3.1 圆锥曲线的几何变换 (54)
7.3.2 参数曲线、曲面的几何变换 (55)
7.4 投影变换 (58)
7.4.1 平行投影(p a r al l e l p ro j e ct i on ) (58)
7.4.2 透视投影(p e r sp e c ti v e p r oj e ct i o n) (60)
8 图形消隐算法 (62)
8.1 扫描线Z-buffer算法 (62)
8.2 区域子分割算法 (62)
8.3 光线投射算法 (62)
8.4 平面公式法 (63)
8.5 径向预排序法 (63)
8.6 径向排序法 (64)
8.7 隔离平面法 (64)
8.8 深度排序法 (64)
8.9 光线跟踪法 (64)
8.10 Z缓冲区法 (64)
8.11 极值检测法 (65)
8.12 深度分类方法 (65)
8.13 八叉树方法 (65)
9 图形学若干基本算法的实现研究 (66)
参考文献 (69)
附录 (69)
图形学算法基础作业
1 直线段生成算法综述
1.1 生成直线的DDA 方法
1.1.1 DDA 算法基本原理
DDA 是数字微分分析式（Digital Differential Analyzer ）的缩写。设直线之起点为11x ,y （），终点为22x ,y （），则斜率k 为：
2121y -y dy k ==x -x dx
直线中的每一点坐标都可以由前一点坐标变化一个增量()x y D ,D 而
得到，即表示为递归式：
i i x
i i y
x 1x D y 1y D +=++=+
并有关系：y x D m D =? 递归式的初值为直线的起点11x ,y （），这样，就可以用加法来生成一条直线。
1.1.2 DDA 算法实现步骤
具体方法是：
按照直线从11x ,y （）到22x ,y （）的方向不同，分为8个象限（见图1.1）。对于方向在第1a 象限内的直线而言，x y D 1D m ==，。对于方向在第1b 象限内的直线而言，取值y x D 1D 1/m ==，。各象限中直线生成时x y D , D 的取值列在表1-1之中。
图 1.1 直线方向的8个象限图
表1-1 各象限中直线生成时x y D , D 的取值列 象限
dx dy ?> x D y D 1a
1b
2a
2b
3a
3b
4a
4b T F T F T F T F 1 1/m -1 -1/m -1 -1/m 1 1/m m 1 m 1 -m -1 -m -1
研究表中的数据，可以发现两个规律：
1、当d x d y >时x y D =1, D =m ；否则：x y D =1/m D =1，
2、x y D , D 的符号与dx, dy 的符号相同。这两条规律可以导致程序的简化。由上述方法写成的程序如附录1所示。其中steps 变量的设置，以及x y D =dx/steps; D =dy/steps 等语句，正是利用了上述两条规律，使得程序变得简练。
使用DDA 算法，每生成一条直线做两次除法，每画线中一点做两次加法。因此，用DDA 法生成直线的速度是相当快的。
1.1.3 DDA 算法程序（或伪程序）描述
具体程序见附录1。
1.1.4 DDA 算法流程图
（略）
1.2 中点画线算法
1.2.1 中点画线算法基本原理
假定直线斜率k 在01之间，当前象素点为p p (x ,y )，则下一个象素点有两种可选择点1p p P (x 1,y )+或2p p P (x 1,y 1)++。若1P 与2P 的中点p p (x 1,y 0.5)++称为M ，Q 为理想直线与p x x 1=+垂线的交点。当M
在Q 的下方时，则取2P 应为下一个象素点；当M 在Q 的上方时，
则取1P 为下一个象素点。这就是中点画线法的基本原理。
1.2.2 中点画线算法实现步骤
下面讨论中点画线法的实现。过点00(x ,y )、11(x ,y )的直线段L 的方程式为F(x,y)ax by c 0=++=，其中0101a y y ,b x x =-=-，0110c x y x y =-，要判断中点M 在Q 点的上方还是下方，只要把M
代入F (x ,y ，
并判断它的符号即可。为此，我们构造判别式: p p p p d F(M)F(x 1,y 0.5)a(x 1)b(y 0.5)c ==++=++++
当d 0<时，M 在L (Q 点)下方，取2P 为下一个象素；
当d 0>时，M 在L (Q 点)上方，取1P 为下一个象素； 当d 0=时，选1P 或2P 均可，约定取1P 为下一个象素。 注意到d 是p p x ,y 的线性函数，可采用增量计算，提高运算效率。
若当前象素处于d 0>情况，则取正右方象素1p p P (x 1,y )+,要判下一个象素位置，应计算1p p p p d F(x 2,y 0.5)a(x 2)b(y 0.5)c d a =++=++++=+，增量为a 。
若d 0<时，则取右上方象素2p p P (x 1,y 1)++。要判断再下一象素，则要计算2p p p p d F(x 2,y 1.5)a(x 2)b(y 1.5)c d a b =++=++++=++，增量为a b +。画线从
00(x ,y )开始，d 的初值00000d F (x 1,y 0.5)F (x ,y )a 0.5b =++=+
+，因00F(x ,y )0=，所以0d a 0.5b =+。 由于我们使用的只是d 的符号，而且d 的增量都是整数，只是初始值包含小数。因此，我们可以用2d 代替d 来摆脱小数，写出仅包含整数运算的算法程序。
1.2.3 中点画线算法程序（或伪程序）描述
具体程序见附录2
1.2.4 中点画线算法流程图
（略）
1.3 生成直线的Bresenham 算法
1.3.1 Bresenham 算法基本原理
本算法由Bresenham 在1965年提出。设直线从起点11x , y （）到终点
22x , y （）
。直线可表示为方程y =k x+b 。其中
11b =y k x -?
2121y -y dy k ==x -x dx
我们讨论先将直线方向限于1a 象限（图 1.1）在这种情况下，当直线光栅化时，x 每次都增加1个单元，即 i i x 1=x +1+。而y 的相应增加应当小于1。为了光栅化，i y +1只可能选择如图1.2两种位置之一。
图 1.2 i y +1的位置选择
图 1.2中 i y +1的位置选择i i y -1=y 或者 i i y +1=y +1
选择的原则是看精确值y 与i y 及i y +1的距离d 1及d2的大小而定。计算式为：
()i i i y =m x +1+b
(1.2.1)d1=y-y
(1.2.2)d 2=y +1-y (1.2.3)
如果d 1-d 2>0，
则i i y +1=y +1，否则i i y +1=y 。因此算法的关键在于简便地求出d 1-d 2的符号。将式（1.2.1）、（1.2.2）、（1.2.3）代入d1-d 2，
得
i i i dy d1-d 2=2y-2y -1=2(x +1)-2y +2b-1dx
用dx 乘等式两边，并以()i P =dx d1-d2代入上述等式，得
()i i i P =2x dy-2y dx+2dy+dx 2b-1 (1.2.4)
d1-d 2是我们用以判断符号的误差。由于在1a 象限，dx 总大于0，所以i P 仍旧可以用作判断符号的误差。i P 1+为：
()i i i i P +1=P +2dy-2dx y +1-y (1.2.5)
误差的初值P1，可将x1, y1，和b 代入式（2.1.4）中的x i , y i 而得到：
1P =2dy-dx
1.3.2 Bresenham 算法实现步骤
综述上面 1.3.1的推导，第1a 象限内的直线Bresenham 算法思想如下：
1、画点(x1, y2); dx x2x1; dy y2y1
=-=-； 计算误差初值P1=2dy-dx; i=1；
2、求直线的下一点位置：
xi+1=xi+1；
if Pi>0 则yi+1=yi+1；
否则yi+1=yi ；
3、画点（xi+1, yi-1）；
4、求下一个误差Pi+1；
if Pi>0 则Pi+1=Pi+2dy-2dx;
否则Pi+1=Pi+2dy ；
5、i=i+1; if i 1.3.3 Bresenham 算法程序（或伪程序）描述 由上述算法思想编制的程序见附录3。这个程序适用于所有8个方向的直线（图 1.1）的生成。程序用色彩C 画出一条端点为11x , y （）和 22x , y （） 的直线。其中变量的含义是：P 是误差；const1和const2，是误差的逐点变化量；inc 是y 的单位递变量，值为1或-1；tmp 是用作象限变换时的临时变量。程序以判断d x >d y 为分支，并分别将2a,3a 象限的直线和3b,4b 象限的直线变换到1a,4a 和2b,1b 方向去，以求得程序处理的简洁。 1.3.4 Bresenham 算法流程图 （略） 1.4 生成直线算法的进一步改进 除过前面所讲到的3种基本直线生成算法外，还有一些其它的方法，由于过多，这里仅列举几种如下： （1）二步法。虽然Bresenham 直线生成算法是一效率很高的算法，但是人们仍在寻找更有校的算法。1987年又有人提出了一种二步法。 即每循环一次不是绘制一个像素，而是绘制两个像素，这样无疑可把生成直线的速度提高一倍。 （2）改进的Bresenham 算法。对于对于传统的直线生成算法，人们往往把注意力集中在算法本身，却忽略了算法之外的一些有用信息:画线之前，从起点坐标和终点坐标，我们就可以获知该线段的斜率，由此可进一步得出在主轴方向连续走l 个步长，在副轴方向才走一个坐标单位，这就是本算法提高Bresenham 算法执行效率的一个方面。提高算法效率的第二个方面是利用线段本身的对称性，则新算法所产生的起点一侧的半条线段与用Bresenham 算法产生的相同。至于终点一侧的半条线段，可以看成以终点为起点线段的生成。 算法实现： 特殊地，对于水平线(y 0?=)，垂直线(x 0?=)和对角线(x y =)，它们都可直接装人帧缓冲器，而无需进行画线算法处理。 从以上的描述可以实现优于Bresenham 的直线生成算法。其中待生成直线的已知数据为:11(x ,y )为线段起点的横、纵坐标；22(x ,y )为线段终点的横、纵坐标。 算法的输人数据为: 11(x ,y )，22(x ,y )。 （3）基于类最佳逼近的散步直线生成算法。一种新的直线逼近方法—类最佳逼近,基于这种逼近方法,斜率[)k 0,0.5∈的 直线和斜率为1k -的直线具有某种互补性质。利用该性质,设计出一种新的三步直线方法,该算法揭示了直线计算的互补性,理论简单,精度达到最好。这种算法改善了Bresenham 算法和双步算法的计算效率。该算法对于硬件实现将更有益处。 除此之外直线生成算法还有对称扫描四步增量画线算法、基于Bresenham 的高效直线生成集成算法、基于Bresenham 算法的四步画直线算法、基于直线特性的直线生成集成算法、基于自适应步长的直线生成算法、基于等分像素点的直线生成算法、6步直线生成算法、基于对角线行程的直线生成算法等等。 1.5 各种直线生成算法的优缺点对比分析 DDA 算法的优点是：绘制实数直线效果好，误差小；缺点是：实现较复杂，不利于硬件实现。因为该算法涉及到实数乘除法运算，y 与k 必须用浮点数表示，而且每一步都要对y 四舍五入后取整。 中点画线算法优点是：只有整数运算，不含乘除法；可用硬件实现。 Bresenham 算法的优点是： 1、不必计算直线之斜率，因此不做除法； 2、不用浮点数，只用整数； 3、只做整数加减法和乘2运算，而乘2运算可以用硬件移位实现。 4、Bresenham 算法速度很快，并适于用硬件实现。 1.6 直线生成算法的发展趋势 （略） 2 椭圆的Bresenham 生成算法 2.1 椭圆曲率分析 椭圆{}c o s ,s i n r a t b t =（ a 为沿x 轴方向的长半轴长度， b 为沿y 轴方向的短半轴长度，且a b >），曲率为22223/2/(sin cos )r k ab a t b t =+，在第一象限()0,/2t π∈，将r k 对t 求导数，有d /d 0r k t <，即曲率为减函数， 在点(,0)a （即0t =）处的曲率2(0)/r t k a b ==；在点(0,)b （即/2t π=）处的 曲率2(/2) /r t k b a π==。半径为a 的圆的曲率为2/a a ，半径为b 的圆的曲率为2/b b ，两圆的曲率关系为22//()b b a a a b >>，则两圆的曲率在椭 圆上点(,0)a 与(0,)b 的曲率之间，四者的关系为：22/1/1//a b b a b a >>>。 2.2 椭圆方程分析 根据椭圆及圆的曲率分析，椭圆弧分别由半径为a 和b 的圆弧逼近生成。为了更准确的由圆弧生成椭圆弧，在椭圆弧上确定一点0P ，将椭圆弧分成曲率较小和曲率较大的两段，椭圆方程为： ()222222F x,y 0b x a y a b =+-=。 其中 a 为沿x 轴方向的长半轴长度， b 为沿y 轴方向的短半轴长度，且 0a b >>。由于椭圆的对称性，这里只要讨论第一象限椭圆弧 的生成。将椭圆弧分为上下两部分，以弧上曲率为-1的点（即法向量两个分量相等的点）作为分界。该椭圆上一点(,)x y 处的法向量为： 22F F N(,)i j 2i 2j x y b x a y x y ??=+=+?? 结合椭圆方程可计算出分界点0P 的坐标为： 222222(/,/)a a b b a b ++。 以0P 点为分界点，将第一象限的圆弧分成曲率较大和较小的两段弧。如图 2.1所示，222[/,]y b a b b ∈+的 椭圆弧，与半径为a 的圆在点1T (0,)a 到222222T (/,/)a a b ab a b ++的圆弧上对应。在椭圆弧上任取一 点1Q ，过1Q 作垂直线与圆交于1P 点，连接圆心与1P 点，与Y 轴的夹角为θ。则 椭圆的参数方程可表示为： ''sin θ,cos θ. x a y b ?=??=?? 圆的参数方程可表示为： sin θ,cos θ.x a y a =??=? 对于同一θ，椭圆弧上存在唯一的点与圆弧上的点对应，并且对应点的坐标存在如下关系： '',(/)y.x x y b a ?=??=?? 图 2.1 圆弧与椭圆弧对应点之一 图 2.2 圆弧与椭圆弧对应点之一 如图 2.2所示，半径为b 的圆上，从点222223T (/,/)a ab b b a b ++到4T (,0)b 的圆弧与椭圆上222(0,/)y b a b ∈+的椭圆弧对应，在椭圆弧上任取一点2Q ，过2Q 作垂直线与圆交于2P 点，连接圆心与2P 点，与Y 轴的夹角为θ。则 椭圆的参数方程可表示为： ''sin θ,cos θ.x a y b ?=??=?? 圆的参数方程可表示为： sin θ,cos θ.x b y b =??=? 对于同一θ，椭圆弧上存在唯一的点与圆弧上的点对应，并且对应点的坐标存在如下关系： ''(/b),y.x a x y ?=??=?? 2.3 椭圆生成算法 当圆弧上的点从(,0)a 沿着图 2.1、图 2.2的对应关系方向变化到(,0)b 时，椭圆弧上相对应的点也从该方向变化到(,0)a 。 2.3.1 算法实现过程 1、计算分界点000P (x ,y )。 2、用Bresenham 算法生成两段圆弧1C 、2C 。1C 半径为a ，222[0,/]x a a b ∈+；2C 半径为b ，222y [0,/]b a b ∈+。 3、将圆弧1C 进行比例变换： x 方向的比例系数为1，y 方向的比例系数为/b a ；将圆弧2C 进行比例变换：x 方向的比例系数为/a b ， y 方向的比例系数为 1。