计算机图形学基本光栅图形算法.ppt

第三章 基本光栅图形算法
计算机图形学基本光栅图形算法
本章内容
用Java语言绘图
1
直线的扫描转换
2
圆的扫描转换
3
多边形的扫描转换
4
区域填充
5
字符的生成
6
光栅图形的反走样算法
7
计算机图形学基本光栅图形算法
直线的扫描转换
⊙图形图像是由屏幕上不同亮度不同颜色的光点（像素）组成。在光栅显示器的荧光屏上生成一个对象，实质上是往帧缓存寄存器的相应单元中填入数据。所以
⊙对直线进行光栅化的时候，只能在显示器所给定的有限个像素组成的点阵中确定最佳逼近于该直线的一组像素，用这些像素表示该直线。所以
⊙生成直线的主要工作是：快速找出距离直线最近的网格点，用这些网格点对应的像素表示该直线。
计算机图形学基本光栅图形算法
3
像素逼近直线示意图
图像元素
可寻址点
计算机图形学基本光栅图形算法
4
基本增量算法
设直线 满足 ，由于直线的斜率小于等于1，所以，该直线的扫描转换可从最左端开始， 每次递增一个单位，对每个 ，相应的有
，则
所以， 每增加一个单位， 只需加上一个 ，这样就去掉了乘法运算，提高了算法效率。在该算法中，直线上的所有点的 和 值可由前一点的值加一个基本增量得到，所以该算法称为基本增量算法。
基本增量算法(DDA-digital differential analyzer)
1、基本思想：
计算机图形学基本光栅图形算法
5
基本增量算法
注：
上述讨论只适合 的情况，当 时，只需将 和 的角色互换，即 每次增加一个单位， 每次增加 。
基本增量算法也叫数字微分分析器算法（Digital Differential Analyzer，DDA）。DDA是用数值方法求解微分方程的一种设备，即根据 111和 的一阶导数，在 和 方向上渐进地以小步长移动，由此产生连续的像素坐标 。
计算机图形学基本光栅图形算法
6
2、直线的表示：
设直线的起点坐标为(xs，ys)，终点坐标为(xe, ye)，令Δx＝xe- xs，Δy＝ ye- ys，则直线参数方程为
目标：能快速地求出能很好地表示直线的像素
第 步时
()
计算机图形学基本光栅图形算法
7
3、提高速度的方法：
乘法用加法实现，每一个点坐标都可以由前一个坐标变化一个增量得到。
设(xi,yi)是第i 步得的直线上的点，则直线上第个i+1 点是(xi+1,yi+1)，其中
当Δx> Δy>0，即直线斜率小于1，应使x方向每次增加1，y方向最多增加1，此时取Δt=1/Δx；
同理,当Δy>Δx>0,直线斜率大于1，取Δt=1/Δy，所以
()
令 ，将参数区间[0，1]分为 等份，即 每次的增量为 。
计算机图形学基本光栅图形算法
8
下图中，用公式（）求得的直线 上的点用空心圆表示，但显示时要用像素来表示，即采用四舍五入的办法得到最靠近空心圆点的像素，用这些像素（下图中的实心圆点）来表示直线。
图中实心圆点表示用
DDA方法生成的直线
计算机图形学基本光栅图形算法
9
图中黑点表示用DDA法生成的直线
4、直线的DDA算法程序
void dda(Graphics g, int x1, int x2, int y1, int y2)
{ int k; float x, y, dx, dy;
k = (x2-x1);
if ((y2-y1)>k)
k = (y2-y1);
dx = (float)(x2-x1)