第三讲 基本图形算法.ppt

文档介绍：滁州学院国土信息工程系
主讲孙勇
Email:sunyong_cug@
计算机图形学
第三章直线、圆、椭圆生成算法




DDA算法
中点画线法
Bresenham画线算法
数值微分法(DDA)
假定直线的起点、终点分别为:(x0,y0), (x1,y1),且都为整数。
(X i+1 ,Yi + k)
(X i , Int(Yi +))
(X i , Yi)
栅格交点表示象素点位置
。
。
。
。
数值微分(DDA)法
基本思想
已知过端点P0 (x0, y0), P1(x1, y1)的直线段L
y=kx+b 直线斜率为
这种方法直观,但效率太低,因为每一步需要一次浮点乘法和一次舍入运算。
数值微分(DDA)法
计算yi+1= kxi+1+b
= kxi+b+kx
= yi+kx
当x =1; yi+1 = yi+k
即:当x每递增1,y递增k(即直线斜率);
注意上述分析的算法仅适用于k≤1的情形。在这种情况下,x每增加1,y最多增加1。
当k1时,必须把x,y地位互换
数值微分(DDA)法
增量算法:在一个迭代算法中,如果每一步的x、y值是用前一步的值加上一个增量来获得,则称为增量算法。
DDA算法就是一个增量算法。
数值微分(DDA)法
void DDALine(int x0,int y0,int x1,int y1,int color)
 int x;
float dx, dy, y, k;
dx = x1-x0; dy=y1-y0;
k=dy/dx ; y=y0;
for (x=x0; xx1; x++)

drawpixel (x, int(y+), color);
y=y+k;


数值微分(DDA)法
例:画直线段P0(0,0)--P1(5,2)
x int(y+) y+
0 0 0+
1 0 +
2 1 +
3 1 +
4 2 +
5 2 +
Y = *X
数值微分(DDA)法
缺点: 在此算法中,y、k必须是float,且每一步都必须对y进行舍入取整,不利于硬件实现。