计算机图形学.ppt

第二章光栅图形学2.1直线段的扫描转换算法数值微分法（DigitalDifferentialAnalyzer）数值微分(DDA)法voidDDALine(intx0,inty0,intx1,inty1,intcolor)
intx；
floatdx,dy,y,k;
dx=x1-x0;dy=y1-y0;
k=dy/dx;y=y0;
for(x=x0;xx1;x++)
drawpixel(x,int(y+0.5),color);
y=y+k;

例：画直线段P0(0,0)--P1(5,2) 增量算法：在一个迭代算法中，如果每一步的x、y值是用前一步的值加上一个增量来获得，则称为增量算法。DDA算法就是一个增量算法。
缺点
注意上述分析的算法仅适用于k≤1的情形。在这种情况下，x每增加1,y最多增加1。当k1时，必须把x，y地位互换，y每增加1，x相应增加1/k。
在此算法中，y、k必须是float，且每一步都必须对y进行舍入取整，有浮点数取整运算,不利于硬件实现。
效率低
原理：当M在Q的下方->P2离直线更近更近->取P2。
M在Q的上方->P1离直线更近更近->取P1
M与Q重合，P1、P2任取一点。

已知：线段两端点(x0,y0)，(x1,y1)
直线方程为：F(x,y)=ax+by+c=0
其中a=y0-y1,b=x1-x0,c=x0y1-x1y0
构造判别式：d=F(M)=F(xp+1,yp+0.5)=a(xp+1)+b(yp+0.5)+c
当d<0，M在直线(Q点)下方，取右上方P2；
当d>0，M在直线(Q点)上方，取右方P1；
当d=0，选P1或P2均可，约定取P1；

能否采用增量算法呢？

若d≥0，中点M在直线上方，取正右方像素P1(Xp+1,Yp)
再下一个像素的判别式为：
d1=F((Xp+1)+1,Yp+0.5)=a(Xp+2)+b(Yp+0.5)+c
=d+ad的增量为a
若d＜0，中点M在直线下方，取右上方像素P2(Xp+1,Yp+1)
再下一个像素的判别式为：
d2=F((Xp+1)+1,(Yp+1)+0.5)=a(Xp+2)+b(Yp+1.5)+c
=d+a+bd的增量为a+b画线从(x0,y0)开始，d的初值
d0=F(x0+1,y0+0.5)
=a(x0+1)+b(y0+0.5)+c
=F(x0,y0)+a+0.5b
=a+0.5b
由于只用d的符号作判断，为了只包含整数运算,
可以用2d代替d来摆脱小数，提高效率。
优点：
只有整数运算，不含乘除法
可用硬件实现

voidMidpointLine(intx0,inty0,intx1,inty1,intcolor)
{inta,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(x<x1)
{if(d<0){x++;y++;d+=d2;}
else{x++;d+=d1;}
drawpixel(x,y,color);
}/*while*/
}/*midPointLine*/
例：用中点画线法P0(0,0)P1(5,2)
a=y0-y1=-2b=x1-x0=5
d0=2a+b=1d1=2a=-4d2=2(a+b)=6Bresenham算法设直线方程为：，其中k=dy/dx。因为直线的起始点在像素中心，所以误差项d的初值d0＝0。
X下标每增加1，d的值相应递增直线的斜率值k，即d＝d＋k。
一旦d≥1，就把它减去1，这样保证d在0、1之间。
当d≥0.5时，最接近于当前像素的右上方像素（xi＋1，yi＋1）
而当d<0.5时，更接近于右方像素（xi＋1，yi）。
为方便计算，令e＝d-0.5，e的初值为-0.5，增量为k。
当e≥0时，取当前像素（xi，yi）的右上方像素（xi＋1，yi＋1）；
而当e<0时，更接近于右方像素（xi＋1，yi）。算法步骤为：
1.输入直线的两端点P0(x0,y0)和P1(x1,y1)。
2.计算初始值△x、△y、e=-0.5、x=x0、y=y0。
3.绘制点(x,y)。
4.e更新为e+k，判断e的符号。若e>0，则(x,y)更新为(x+1,y+1)，同时将e更新为e-1；否则(x,y)更新为(x+1,y)。
5.当直线没有画完时，重复步骤3和4。否则结束。程序如下：BresenhamLine(intx0,inty0,intx1,inty1,intcolor)
{intx,y,dx,dy;
floatk,e;
dx=x1-x0;
dy=y1-y0;
k=dy/d