文档介绍：第三章直线、圆、椭圆生成算法
图形的扫描转换(光栅化):确定一个像素集合,用于显示一个图形的过程。步骤如下:
1、确定有关像素
2、用图形的颜色或其它属性,对像素进行写操作。
对一维图形,不考虑线宽,则用一个像素宽的直线来显示图形。二维图形的光栅化,即区域的填充:确定像素集,填色或图案。
任何图形的光栅化,必须显示在一个窗口内,否则不予显示。即确定一个图形的哪些部分在窗口内,哪些在窗口外,即裁剪。
浙江大学信息学院计算机图形学
图形显示前需要:扫描转换+裁剪
●裁剪---〉扫描转换:最常用,节约计算时间。
●扫描转换---〉裁剪:算法简单;
浙江大学信息学院计算机图形学
本章内容
?扫描转换直线段
DDA算法
中点画线法
Bresenham画线算法
?圆弧、椭圆弧扫描转换
中点算法
内接正多边形迫近法
等面积正多边形逼近法
生成圆弧的正负法
浙江大学信息学院计算机图形学
直线段的扫描转换算法
直线的扫描转换: 确定最佳逼近于该直线的一组象素,并且按扫描线顺序,对这些象素进行写操作。
三个常用算法:
数值微分法(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 +
浙江大学信息学院计算机图形学