LH的计算机图形学作业
8 图形消隐算法 ...................................................................... 61
8.1 扫描线Z-buffer算法 ..................................................... 61 8.2 区域子分割算法 .............................................................. 61 8.3 光线投射算法 .................................................................. 62 8.4 平面公式法 ...................................................................... 62 8.5 径向预排序法 .................................................................. 63 8.6 径向排序法 ...................................................................... 63 8.7 隔离平面法 ...................................................................... 63 8.8 深度排序法 ...................................................................... 63 8.9 光线跟踪法 ...................................................................... 63 8.10 Z缓冲区法 ..................................................................... 64 8.11 极值检测法 .................................................................... 64 8.12 深度分类方法 ................................................................ 64 8.13 八叉树方法 .................................................................... 65 9 图形学若干基本算法的实现研究 .......................................... 65 参考文献 ................................................................................ 68 附录 ....................................................................................... 68
V
LH计算机图形学作业：共九道题
图形学算法基础作业
1 直线段生成算法综述
1.1 生成直线的DDA方法 1.1.1 DDA算法基本原理
DDA是数字微分分析式（Digital Differential Analyzer）的缩写。设直线之起点为（x1,y1），终点为（x2,y2），则斜率k为：
k=y2-y1dy =x2-x1dx直线中的每一点坐标都可以由前一点坐标变化一个增量?Dx,Dy?而得到，即表示为递归式：
xi?1?xi?Dxyi?1?yi?Dy并有关系：Dy ? m ? Dx
递归式的初值为直线的起点（x1,y1），这样，就可以用加法来生成一条直线。
1.1.2 DDA算法实现步骤
具体方法是：
按照直线从（x1,y1）到（x2,y2）的方向不同，分为8个象限（见图1.1）。对于方向在第1a象限内的直线而言，Dx?1，Dy?m。对于方向在第1b象限内的直线而言，取值Dy?1，Dx?1/m。各象限中直线生成时Dx, Dy的取值列在表1-1之中。
图1.1 直线方向的8个象限图
1
LH计算机图形学作业：共九道题
表1-1 各象限中直线生成时Dx, Dy的取值列
象限 1a 1b 2a 2b 3a 3b 4a 4b dx?dyT F T F T F T F ? Dx 1 1/m -1 -1/m -1 -1/m 1 1/m Dy m 1 m 1 -m -1 -m -1 研究表中的数据，可以发现两个规律：
Dy=1 1、当dx?dy时Dx=1, Dy=m；否则：Dx=1/m，2、Dx, Dy的符号与dx, dy的符号相同。这两条规律可以导致程序的简化。由上述方法写成的程序如附录1所示。其中steps变量的设置，以及Dx=dx/steps; Dy=dy/steps等语句，正是利用了上述两条规律，使得程序变得简练。
使用DDA算法，每生成一条直线做两次除法，每画线中一点做两次加法。因此，用DDA法生成直线的速度是相当快的。 1.1.3 DDA算法程序（或伪程序）描述
具体程序见附录1。 1.1.4 DDA算法流程图
（略） 1.2 中点画线算法
1.2.1 中点画线算法基本原理
假定直线斜率k在0?1之间，当前象素点为(xp,yp)，则下一个象素点有两种可选择点P1(xp?1,yp)或P2(xp?1,yp?1)。若P1与P2的中点(xp?1,yp?0.5)称为M，Q为理想直线与x?xp?1垂线的交点。当M
2
LH计算机图形学作业：共九道题
在Q的下方时，则取P2应为下一个象素点；当M在Q的上方时，则取P1为下一个象素点。这就是中点画线法的基本原理。 1.2.2 中点画线算法实现步骤
下面讨论中点画线法的实现。过点(x0,y0)、(x1,y1)的直线段L的方程式为F(x,y)?ax?by?c?0，其中a?y0?y1,b?x0?x1，
c?x0y1?x1y0，要判断中点M在Q点的上方还是下方，只要把M
y并判断它的符号即可。为此，我们构造判别式: 代入F(x,，
d?F(M)?F(xp?1,yp?0.5)?a(xp?1)?b(yp?0.5)?c
当d?0时，M在L(Q点)下方，取P2为下一个象素； 当d?0时，M在L(Q点)上方，取P1为下一个象素； 当d?0时，选P1或P2均可，约定取P1为下一个象素。
注意到d是xp,yp的线性函数，可采用增量计算，提高运算效率。 若当前象素处于d?0情况，则取正右方象素P1(xp?1,yp),要判下一个象素位置，应计算d1?F(xp?2,yp?0.5)?a(xp?2)?b(yp?0.5)?c?d?a，增量为a。
若d?0时，则取右上方象素P2(xp?1,yp?1)。要判断再下一象
?素，则要计算d2?F(px增量为
2p,?y1?.5p)?a(?xp2?)b?(y?，1?.5?)cda?b。画线从
0(x0,y0)开始，
d的初值
d0?F(0?x1?,y?。 00.5)，因?FF(x(0x,y0),?0y，)所以ad0?0a?.0.5b5b0? 由于我们使用的只是d的符号，而且d的增量都是整数，只是初始值包含小数。因此，我们可以用2d代替d来摆脱小数，写出仅包含整数运算的算法程序。 1.2.3 中点画线算法程序（或伪程序）描述
具体程序见附录2 1.2.4 中点画线算法流程图 （略）
1.3 生成直线的Bresenham算法 1.3.1 Bresenham算法基本原理
本算法由Bresenham在1965年提出。设直线从起点（x1, y1）到终点。直线可表示为方程y=kx+b。其中 （x2, y2） 3
LH计算机图形学作业：共九道题
b=y1?k?x1
k=y2-y1dy=
x2-x1dx我们讨论先将直线方向限于1a象限（图1.1）在这种情况下，当直线光栅化时，x每次都增加1个单元，即 xi?1=xi+1。而y的相应增加应当小于1。为了光栅化，yi+1只可能选择如图1.2两种位置之一。
图1.2 yi+1的位置选择
图1.2中 yi+1的位置选择yi-1=yi 或者 yi+1=yi+1
选择的原则是看精确值y与yi及yi+1的距离d1及d2的大小而定。计算式为：
y=m?xi+1?+b d1=y-yi d2=yi+1-y (1.2.1)(1.2.2)
(1.2.3)0则yi+1=yi+1，否则yi+1=yi。因此算法的关键在于简便如果d1-d2>，
2符号。将式（1.2.1）地求出d1-d的、（1.2.2）、（1.2.3）代入d1-d2，
得
d1-d2=2y-2yi-1=2dy(xi+1)-2yi+2b-1 dx用dx乘等式两边，并以Pi=dx?d1-d2?代入上述等式，得
Pi=2xidy-2yidx+2dy+dx?2b-1? (1.2.4)
d1-d2是我们用以判断符号的误差。由于在1a象限，dx总大于0，所以
Pi仍旧可以用作判断符号的误差。Pi?1为：
Pi+1=Pi+2dy-2dx?yi+1-yi? (1.2.5)
i得到：误差的初值P1，可将x1, y1，和b代入式（2.1.4）中的xi, y而
4