发布时间 : 星期一 文章计算机图形学各种算法的作业（偏于理论）更新完毕开始阅读d669a0c2d5bbfd0a795673b5
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
LH计算机图形学作业：共九道题
P1=2dy-dx
1.3.2 Bresenham算法实现步骤
综述上面1.3.1的推导，第1a象限内的直线Bresenham算法思想如下：
1、画点(x1, y2); dx?x2?x1; dy? y2?；y1计算误差初值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 由上述算法思想编制的程序见附录3。这个程序适用于所有8个方向的直线（图1.1）的生成。程序用色彩C画出一条端点为（x1, y1）和的直线。其中变量的含义是：P是误差；const1和const2，是（x2, y2）误差的逐点变化量；inc是y的单位递变量，值为1或-1；tmp是用作象限变换时的临时变量。程序以判断dx>d为y分支，并分别将2a,3a象限的直线和3b,4b象限的直线变换到1a,4a和2b,1b方向去，以求得程序处理的简洁。 1.3.4 Bresenham算法流程图 （略） 1.4 生成直线算法的进一步改进 除过前面所讲到的3种基本直线生成算法外，还有一些其它的方法，由于过多，这里仅列举几种如下： （1）二步法。虽然Bresenham直线生成算法是一效率很高的算法，但是人们仍在寻找更有校的算法。1987年又有人提出了一种二步法。 5 LH计算机图形学作业：共九道题 即每循环一次不是绘制一个像素，而是绘制两个像素，这样无疑可把生成直线的速度提高一倍。 （2）改进的Bresenham算法。对于对于传统的直线生成算法，人们往往把注意力集中在算法本身，却忽略了算法之外的一些有用信息:画线之前，从起点坐标和终点坐标，我们就可以获知该线段的斜率，由此可进一步得出在主轴方向连续走l个步长，在副轴方向才走一个坐标单位，这就是本算法提高Bresenham算法执行效率的一个方面。提高算法效率的第二个方面是利用线段本身的对称性，则新算法所产生的起点一侧的半条线段与用Bresenham算法产生的相同。至于终点一侧的半条线段，可以看成以终点为起点线段的生成。 算法实现： 特殊地，对于水平线(?y?0)，垂直线(?x?0)和对角线(x?y)，它们都可直接装人帧缓冲器，而无需进行画线算法处理。 从以上的描述可以实现优于Bresenham的直线生成算法。其中待生成直线的已知数据为:(x1,y1)为线段起点的横、纵坐标；(x2,y2)为线段终点的横、纵坐标。 算法的输人数据为: (x1,y1)，(x2,y2)。 （3）基于类最佳逼近的散步直线生成算法。一种新的直线逼近方法—类最佳逼近,基于这种逼近方法,斜率k??0,0.5直线和斜率为1?k?的的直线具有某种互补性质。利用该性质,设计出一种新的三步直线方法,该算法揭示了直线计算的互补性,理论简单,精度达到最好。这种算法改善了Bresenham算法和双步算法的计算效率。该算法对于硬件实现将更有益处。 除此之外直线生成算法还有对称扫描四步增量画线算法、基于Bresenham的高效直线生成集成算法、基于Bresenham算法的四步画直线算法、基于直线特性的直线生成集成算法、基于自适应步长的直线生成算法、基于等分像素点的直线生成算法、6步直线生成算法、基于对角线行程的直线生成算法等等。 1.5 各种直线生成算法的优缺点对比分析 DDA算法的优点是：绘制实数直线效果好，误差小；缺点是：实现较复杂，不利于硬件实现。因为该算法涉及到实数乘除法运算，y与k必须用浮点数表示，而且每一步都要对y四舍五入后取整。 6