DDA算法
直线倾向的轴坐标每步加一, 另一个轴的坐标加上斜率, 得到的值取整, 作为像素的XY值
书上给的缺点是取整和浮点数运算很耗时
Bresenham
有点复杂
以 0<斜率<1 为例
f(x) = mx+b
X每步加一
分别算出可能取到的两个Y值与直线在这个点上的真正的取值的差, 即
DiffUpper : y[k+1] - m(x+1) - b
DiffLower : m(x+1) - b - y[k] ( 直线会从这个像素的上半部分穿过, 所以y值一定比像素中心点的y值大 )
再算出两个差值的差
DD = DiffLower - DiffUpper
这里谁减谁无所谓, 因为是靠这个值的符号来决定画哪个像素
到这里因为m是实数的原因, 运算还是浮点数, 为了消除浮点数, 在等式两端乘以deltaX, 即终点和起点的X差值
Sign[k] = ( DiffLower - DiffUpper ) * deltaX
然后, 用Sign[k+1]减去Sign[k], 会得到一个整数的增量, 这个增量经计算会是一个与DD有关的整数
这样, 只要算出第一个点的Sign[0]再不断的加上这个增量, 就能算出下一个点的坐标了
书上给的优点是可以只用整数运算就画出直线
据说可以画任意曲线, 稍微想了一下, 没想出来改进方法, 算了