文档介绍：第二章基本图形的生成与计算
图形的扫描转换(光栅化):确定一个像素集合,用于显示一个图形的过程。步骤如下:
1、确定有关像素
2、用图形的颜色或其它属性,对像素进行写操作。
对一维图形,不考虑线宽,则用一个像素宽的直线来显示图形。二维图形的光栅化,即区域的填充:确定像素集,填色或图案。
任何图形的光栅化,必须显示在一个窗口内,否则不予显示。即确定一个图形的哪些部分在窗口内,哪些在窗口外,即裁剪。
图形显示前需要:扫描转换+裁剪
●裁剪---〉扫描转换:最常用,节约计算时间。
●扫描转换---〉裁剪:算法简单;
直线的生成算法
直线的扫描转换: 确定最佳逼近于该直线的一组象素,并且按扫描线顺序,对这些象素进行写操作。
三个常用算法:
数值微分法(DDA)
中点画线法
Bresenham算法。
直线DDA算法
设直线起点为(x1,y1),终点(x2,y2),则斜率m为
这种方法直观,但效率太低,因为每一步需要一次浮点乘法和一次舍入运算。
增量算法:在一个迭代算法中,如果每一步的x、y值是用前一步的值加上一个增量来获得,则称为增量算法。
DDA算法就是一个增量算法。
计算yi+1= mxi+1+b
= mxi+b+kx
= yi+mx
当x =1; yi+1 = yi+m
即:当x每递增1,y递增m(即直线斜率);
注意上述分析的算法仅适用于m≤1的情形。在这种情况下,x每增加1,y最多增加1。
当m1时,必须把x,y地位互换
1a
1b
2b
2a
3a
3b
4b
4a
(x1,y1)
(x2,y2)
直线从(x1,y1)到(x2,y2)的方向不同,分为8个极限。方向在第1a象限内的直线,取增量Dx=1,Dy=m;在1b象限内的,取增量Dy=1,Dx=1/m。
象限
|dx|>|dy|?
Dx
Dy
象限
|dx|>|dy|?
Dx
Dy
1a
True
1
m
3a
True
-1
-m
1b
False
1/m
1
3b
False
-1/m
-1
2a
Ture
-1
m
4a
Ture
1
-m
2b
False
-1/m
1
4b
False
1/m
-1

,可以得到如下规律:
1、当|dx|>|dy|时
|Dx|=1 ,|Dy|=m
否则|Dx|=1/m ,|Dy|=1
2、Dx,Dy的符号与dx,dy的符号相同
依据上述规律可以生成直线,每生成一条直线做两次除法,画线中的每点做两次加法,所以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;

