计算机图形学PPT课件.ppt

第二章 光栅图形学
直线段的扫描转换算法
圆弧的扫描转换算法
多边形的扫描转换与区域填充
字符
裁剪
反走样
消隐
1
可编辑课件
直线段的扫描转换算法
数值微分法（DDA算法）
中点画线法
Bresenham画线算法
2
可编辑课件
数值微分法（Digital Differential Analyzer ）
基本思想
假定直线的起点、终点分别为：（x0,y0), (x1,y1)，且都为整数。
已知过端点P0 (x0, y0), P1(x1, y1)的直线段L(P0,P1);直线斜率为
按照y=kx+b计算相应的y坐标。
3
可编辑课件
数值微分(DDA)法
设步长为x，有xi+1 =xi + x
则yi+1= kxi+1+b= kxi+kx+b= yi+kx
因为光栅点的单位是1，对每一个x方向的增量x =1时; 有yi+1 = yi+k 。即：当x每递增1，y递增k(即直线斜率)。
经过round()函数处理得到显示的光栅点(x,round(y))坐标。
xi+1 =xi+1
yi+1= yi+k
栅格交点表示像素点位置
(X i , Yi)
(X i+1 ,Yi + k)
(X i , Int(Yi +))
。
。
。
。
4
可编辑课件
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)法
5
可编辑课件
例：画直线段P0(0,0)--P1(5,2)
x y+ 　　int(y+ )
0 0+ 　 0
1 + 0
2 + 1
3 + 1
4 + 2
5 + 2
优点：在同一坐标上,不可能连续停留两次。
缺点： 在此算法中，y、k必须是float，且每一步都必须对y进行舍入取整，不利于硬件实现。
算法特点:
注意：网格点表示像素
6
可编辑课件
增量算法：在一个迭代算法中，如果每一步的x、y值是用前一步的值加上一个增量来获得，则称为增量算法。DDA算法就是一个增量算法。
缺点
注意上述分析的算法仅适用于k ≤1的情形。在这种情况下，x每增加1,y最多增加1。当 k 1时，必须把x，y地位互换，y每增加1，x相应增加1/k。
在此算法中，y、k必须是float，且每一步都必须对y进行舍入取整，有浮点数取整运算,不利于硬件实现。
效率低
数值微分(DDA)法
7
可编辑课件
原理：
假定直线斜率0<K<1，且已确定点像素点P（Xp ,Yp ）,则下一个与直线最接近的像素只能是P1点或P2点。设M为中点，Q为交点
问题：现需判断距离理想直线最近的下一个像素点。
中点画线法
8
可编辑课件
当M在Q的下方-> P2离直线更近更近->取P2 。
M在Q的上方-> P1离直线更近更近->取P1
M与Q重合， P1、P2任取一点。
算法原理
如何判断M点在Q点上方还是在Q点下方？
9
可编辑课件
已知：线段两端点(x0,y0)，(x1,y1)
直线方程为： F(x,y)=ax+by+c=0
其中a=y0-y1, b=x1-x0, c=x0y1-x1y0
M
中