计算机图形学 之 DDA直线算法(数值微分法)
在数学上,直线就是由无穷多个点组成的, 在计算机屏幕显示的话, 需要做一些处理,对于光栅显示器
光栅显示器上就是用有限多个点去逼近直线, 那么这些有限个点,我们需要知道每一个像素点的坐标(都是整数)
求P0, P1的直线方程
y= kx + b
斜率为
(y1 - y0)
k = --------------- (x1 != x0)
(x2 - x0)
假设 x 已知, 即从x的起点x0开始, 沿x方向 前进一个像素, (步长为1) ,就可以计算出y的值
因为像素都是整数值, 所以求出的y值还要进行整数处理
那么问题就转换成了, 如何 把数学上的一个点, 扫描转换成一个屏幕像素点
比如 p (1.7, 0.8) -> p (1, 0) 或者 p(1.7, 0.8) -> +0.5 -> p (2.2, 1.3) -> p(2, 1)
直线是最基本的图形, 一个动画或真实感图形往往需要调用成千上万次画线程序, 因此直线算法的好坏与效率直接影响图形的质量与速度
因为直线方程是 y = kx + b
为了提高效率, 把计算量减下来, 关键问题是如何把乘法取消
DDA算法引进图形学忠一个很重要的思想 ------增量思想
这个直线是
yi = k xi + b 那么x (i+1) 也满足该式子
y(i+1) = k x(i+1) + b 又因为 x(i+1) = xi + 1, 所以
y(i+1) = k (xi + 1) + b 小括号打开就是
y(i+1) = k xi + k + b 移项
y(i+1) = k xi + b + k = yi + k 到这里就相当于 y的变化就是x每移动一格, y就移动k单位,也就是斜率
所以我们每移动一次x轴, y轴就可以移动k个单位,这样就省去了乘法运算,大大提高了效率
如下所示的例子
k = 3 / 5 = 0.6 < 1
y(i+1) = yi + k
我们从(0, 0) 这个点开始, 每次x加一, y就加0.6 那么x = 1的时候, y = 0.6, 然后进行取整运算,
结果如下表
| x | y | int(y+0.5) |
|---|---|---|
| 0 | 0 | 0 |
| 1 | 0 + 0.6 | 1 |
| 2 | 0.6 + 0.6 | 1 |
| 3 | 1.2 + 0.6 | 2 |
| 4 | 1.8 + 0.6 | 2 |
| 5 | 2.5 + 0.6 | 3 |
当然以上的办法只适合画斜率小于1 的直线,如果斜率大于一, 那么我们需要把x和y对调顺序进行计算, 计算完再换过来
作者：锋霜利雪
