清华大学出版社计算机图形学
基本图形生成算法
主讲:XXX
制造科学与工程学院
基本图形生成算法
什么是图形的扫描转换(或光栅化)?
光栅显示器-> 一个象素的矩阵
确定一个象素集合及其颜色,用于显示出一个图形的过程。
图形光栅化的研究内容
直线段的扫描转换算法
圆弧的扫描转换算法
多边形的扫描转换与区域填充
字符
裁剪
反走样
消隐
直线段的扫描转换算法
直线的扫描转换: 确定最佳逼近于该直线的一组象素,并且按扫描线顺序,对这些象素进行写操作。
三个常用算法:
数值微分法(DDA)
中点画线法
Bresenham算法。
数值微分(DDA)法
基本思想
已知过端点的直线段L:
直线斜率为
从的左端点开始,向右端点步进。步长=1(个象素),计算相应的y坐标;取象素点(x, round(y))作为当前点的坐标。
作为最底层的光栅图形算法,在通常的CAD/图形系统中,会被大量应用,因此,哪怕节约一个加法或减法,也是很了不起的改进。
以上算法效率直观可行,但效率较低,由此出发点,引入增量算法的思想。
计算
当时;
即:当x每递增1,y递增k(即直线斜率);
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; xx1, x++)
drawpixel (x, int(y+), color);
y=y+k;
注意上述分析的算法仅适用于k≤1的情形。在这种情况下,x每增加1, y最多增加1。
当k1时,必须把x,y地位互换,y每增加1,x相应增加1/k。
k<1 示意图
数值微分算法本质:用数值方法解微分方程,通过对x和y各增加一个小增量,计算下一步的x、y值。
增量算法:迭代算法中,每一步的x、y值是用前一步的值加上一个增量来获得。
DDA算法是一个增量算法。
直线的扫描转换 来自淘豆网www.taodocs.com转载请标明出处.