数学里的直线上的点是无穷多的，但是光栅显示器的像素点是有限的，所以只能使用有限的像素去尽可能逼近直线
为了在光栅显示器上用这些离散的像素点去逼近直线，需要知道这些像素点的 $x$, $y$ 坐标
求法：
1. 求出过点 $P_{0}$, $P_{1}$ 的直线段的方程：
2. 求 $y$ 的值
假设 $x$ 已知，即从 $x$ 的起点 $x_{0}$ 开始，沿着 $x$ 方向前进一个像素（步长 = 1），可以计算出相应的 $y$ 值
因为像素的坐标是整数，所以 $y$ 值还需要进行取整处理
取整规律：
直线是最基本的图形，一个动画或者真实感图形往往需要调用成千上万次画线程序，因此直线算法的好坏与效率将直接影响图形的质量和显示速度
算法优化：把算法中的乘法消去可以减少计算量，从而提高算法效率
三个直线绘制常用算法：
- 数值微分法（DDA）
- 中点画线法
- Bresenham 算法
1. 数值微分法
引进了增量思想，算法直观、容易实现
原理解析：
在上图中点 $\left(x_{i},\;y_{i}\right)$, $\left(x_{i+1},\;y_{i+1}\right)$ 可以表示为：
因为存在假设：$x$ 已知，且每次前进步长为 1，所以：$x_{i+1} = x_{i} + 1$
则：
即：当前的 $y$ 值等于前一步的 $y$ 值 + 斜率 $k$
这里的斜率 $k$ 也就是式子 $y_{i+1} = y_{i} + k$ 的增量
这样就把原来一个乘法和加法变成了一个加法
eg. 用 DDA 扫描转换连接两点 $P_{0} \left(0,\;0\right)$ 和 $P_{1} \left(5,\;3\right)$ 的直线段
1. 计算 $k$
2. 计算像素点坐标
| $x$ | $y$ | $int \left(y + 0.5\right)$ |
|---|---|---|
| $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.4+0.6$ | $3$ |
注意：
当 $|k| > 1$ 时
使用上述计算方式可能不能画出直线，因为任意两点之间通过 DDA 算法计算直线，当 $|k| > 1$ 时，结果只有三个点，如果两点之间距离比较远，就会导致光栅点太稀疏，从而不能描绘直线
2. 中点画线法
对 DDA 的改进方案：
1. 提高算法效率
因为在计算机中，加法运算是最快的，加法运算里整数加法又是最快的
一般情况下，$y$ 和 $k$ 都是小数，而且每一步运算都要对 $y$ 进行四舍五入后取整，所以可以通过把浮点运算变成整数运算来改进
2. 改变直线方程类型
中点画线法：利用直线的一般式方程
这样一来，对于直线上的点：$F \left(x,\;y\right) = 0$
对于直线上方的点：$F \left(x,\;y\right) > 0$
对于直线下方的点：$F \left(x,\;y\right) < 0$
原理解析：
每一次在最大位移方向上走一步，而另一个方向走不走取决于中点误差项的判断
假设：$0 \leq |k| \leq 1$，所以每次在 $x$ 方向上 $+1$，$y$ 方向上的变化情况需要通过判断 $P_{u}$ 到 $P_{d}$ 的中点来决定
如图，此时 ideal line 与直线 $P_{u}P_{d}$ 有一个交点 $Q$，直线 $P_{u}P_{d}$ 有一个中点：$M \left(x_{i}+1,\;y_{i}+0.5\right)$
判断：
- 当 $Q$ 在 $M$ 上方时，$P_{u}$ 距离直线更近，则 $P_{u}$ 为下一像素点
- 当 $Q$ 在 $M$ 下方时，$P_{d}$ 距离直线更近，则 $P_{d}$ 为下一像素点
- 若 $Q$ 和 $M$ 是同一个点，则 $P_{u}$ 或 $P_{d}$ 都可以是下一像素点
如何判断 $Q$ 在 $M$ 上方还是下方？
1. 把 $M$ 代入理想直线方程：
2. 判断
- 当 $d < 0$ 时：$Q$ 在 $M$ 上方，下一像素点为 $P_{u}$
- 当 $d > 0$ 时：$Q$ 在 $M$ 下方，下一像素点为 $P_{d}$
- 当 $d = 0$ 时：$Q$ 等于 $M$，下一像素点为 $P_{u}$ 或 $P_{d}$ 都可以
算法：
算法计算量：为了求得 $d$ 值，需要 $4$ 个乘法，$2$ 个加法
对中点画线法的改进：因为 $d$ 是 $x$, $y$ 的线性函数，所以可以采用增量计算
推导过程：
代入中点坐标求得 $d_{0}$：
假设 $d < 0$
则第一个取的像素点 $P_{0}$ 为 $P_{u} \left(x_{i} + 1,\;y_{i} + 1\right)$
再往下计算一个像素点 $P_{1}$ 的位置：
则 $P_{1}$ 可能是点 $P_{a} \left(x_{i}+2,\;y_{i}+1\right)$ 或者 $P_{b} \left(x_{i}+2,\;y_{i}+2\right)$
则直线 $P_{a}P_{b}$ 的中点为 $M_{1} \left(x_{i}+2,\;y_{i}+1.5\right)$
所以：
假设 $d \geq 0$
则第一个取的像素点 $P_{0}’$ 为 $P_{d} \left(x_{i} + 1,\;y_{i}\right)$
再往下计算一个像素点 $P_{1}’$ 的位置：
则 $P_{1}’$ 可能是点 $P_{a} \left(x_{i}+2,\;y_{i}+1\right)$ 或者 $P_{c} \left(x_{i}+2,\;y_{i}\right)$
则直线 $P_{a}P_{c}$ 的中点为 $M_{1}’ \left(x_{i}+2,\;y_{i}+0.5\right)$
所以：
$$d_{1} = F \left(x_{{m1}'},\;y_{{m1}'}\right)$$计算 $d_{0}$：
直线的第一个像素点坐标为：$P\left(x_{0},\;y_{0}\right)$
因为 $P \left(x_{0},\;y_{0}\right)$ 在直线上，所以满足 $Ax_{0} + By_{0} + C = 0$
所以：
中点画线法算法：
至此，中点画线法算法与 DDA 的算法效率一样好
注意：
一般情况下，$A$、$B$ 都是整数，而 $d_{0}$ 的计算中存在浮点数，浮点数的运算更复杂
但是 $d_{0}$ 的作用只是与 $0$ 比较大小，所以完全可以用 $2d_{0}$ 代替 $d_{0}$，以此可以避免浮点数运算
此时中点画线法算法中只包含整数运算，所以更优于 DDA 算法
3. Bresenham 算法
Bresenham 拥有更优的效率和更广泛的适用范围
基本思想：
通过各行、各列像素中心构造一组虚拟网格线，按照直线起点到终点的顺序，计算直线与各垂直网格线的交点，然后根据误差项（交点距离像素点的距离）的符号确定该列像素中与此交点最近的像素
假设每次 $x+1$，$y$ 的递增（减）量为 $0$ 或 $1$，它取决于实际直线与光栅网格点的距离，这个距离的最大误差是 $0.5$
- 如果 $d < 0.5$，$y$ 的递增（减）量为 $0$
- 如果 $d > 0.5$，$y$ 的递增（减）量为 $1$
- 如果 $d = 0.5$，$y$ 的递增（减）量为 $0$ 或 $1$ 中任意一个
误差项 $d$ 的初值 $d_{0} = 0$
初始之后的 $d = d + k$
一旦 $d \geq 1$，就将其减 $1$，以保证 $d$ 的相对性，且始终在 $0$、$1$ 之间
计算下一个象素点的原理：
算法效率优化：
1. 令 $e = d - 0.5$
将值的大小替换成正负号
- $e_{初} = -0.5$
- 每当 $x + 1$，则 $e = e + k$
- 如果 $e > 0$，则 $e = e - 1$
2. 令 $2e\Delta x = e$
因为 $k = \frac{dy}{dx}$、$dx = \Delta x$
- $e_{初} = -\Delta x$
- 每当 $x + 1$，则 $e = e + 2\Delta y$
- 如果 $e > 0$，则 $e = e - 2\Delta x$
至此，算法全部改进为整数加法，且不受直线方程类型的限制
算法步骤：
- 输入直线的两端点 $P_{0}\left(x_{0},\;y_{0}\right)$ 和 $P_{1}\left(x_{1},\;y_{1}\right)$
- 计算初始值 $\Delta x$、$\Delta y$、$e = -\Delta x$、$x = x_{0}$、$y = y_{0}$
- 绘制点 $\left(x,\;y\right)$
- 将 $e$ 替换为 $e + 2\Delta y$，判断 $e$ 的符号
- 若 $e > 0$，则将 $\left(x,\;y\right)$ 替换为 $\left(x+1,\;y+1\right)$，同时将 $e$ 替换为 $e - 2\Delta y$
- 否则，将 $\left(x,\;y\right)$ 替换为 $\left(x+1,\;y\right)$
- 当直线没有画完时，重复步骤 3 和 4，否则结束
Bresenham 算法很像 DDA 算法，都是加斜率，但 DDA 算法是每次求出一个新的 $y$ 以后取整来画，而 Bresenham 算法是判符号来决定上下两个点，所以该算法集中了 DDA 和中点算法的优点，而且应用范围更广泛
4. 结
以上是基础原理，实现代码🕳