本文原创首发于我的个人博客
由于本文存在大量 LaTeX 代码，建议原站查看

数学里的直线上的点是无穷多的，但是光栅显示器的像素点是有限的，所以只能使用有限的像素去尽可能逼近直线

为了在光栅显示器上用这些离散的像素点去逼近直线，需要知道这些像素点的 $x$x, $y$y 坐标

求法：

1. 求出过点 $P_{0}$P0​, $P_{1}$P1​ 的直线段的方程：

$y = kx + b$y=kx+b

$k=\frac{ \left ( y_{1} - y_{0}\right ) }{ \left ( x_{1} - x_{0}\right ) } \;\;\; \left ( x_{1} \neq x_{0}\right )$k=(x1​−x0​)(y1​−y0​)​(x1​​=x0​)

2. 求 $y$y 的值

假设 $x$x 已知，即从 $x$x 的起点 $x_{0}$x0​ 开始，沿着 $x$x 方向前进一个像素（步长 = 1），可以计算出相应的 $y$y 值

因为像素的坐标是整数，所以 $y$y 值还需要进行取整处理

取整规律：

$P\left(1.7,\;0.8\right) \rightarrow \left(+0.5\right) \rightarrow 取整 \rightarrow P\left(2,\;1\right)$P(1.7,0.8)→(+0.5)→取整→P(2,1)

直线是最基本的图形，一个动画或者真实感图形往往需要调用成千上万次画线程序，因此直线算法的好坏与效率将直接影响图形的质量和显示速度

算法优化：把算法中的乘法消去可以减少计算量，从而提高算法效率

三个直线绘制常用算法：

1. 数值微分法（DDA）
2. 中点画线法
3. Bresenham 算法

1. 数值微分法

引进了增量思想，算法直观、容易实现

原理解析：

在上图中点 $\left(x_{i},\;y_{i}\right)$(xi​,yi​), $\left(x_{i+1},\;y_{i+1}\right)$(xi+1​,yi+1​) 可以表示为：

$y_{i} = kx_{i} + b$yi​=kxi​+b

$y_{i+1} = kx_{i+1} + b$yi+1​=kxi+1​+b

因为存在假设：$x$x 已知，且每次前进步长为 1，所以：$x_{i+1} = x_{i} + 1$xi+1​=xi​+1

则：

$y_{i+1} = kx_{i+1} + b$yi+1​=kxi+1​+b

$\;\;\;\;\;\;\;\;\;\;\;\;\; = k \left(x_{i} + 1\right) + b$=k(xi​+1)+b

$\;\;\;\;\;\;\;\;\;\;= kx_{i} + k + b$=kxi​+k+b

$\;\;\;\;\;\;\;\;\;\;= kx_{i} + b + k$=kxi​+b+k

$\;\;= y_{i} + k$=yi​+k

即：当前的 $y$y 值等于前一步的 $y$y 值 + 斜率 $k$k

这里的斜率 $k$k 也就是式子 $y_{i+1} = y_{i} + k$yi+1​=yi​+k 的增量

这样就把原来一个乘法和加法变成了一个加法

eg. 用 DDA 扫描转换连接两点 $P_{0} \left(0,\;0\right)$P0​(0,0) 和 $P_{1} \left(5,\;3\right)$P1​(5,3) 的直线段

1. 计算 $k$k

$k = \frac{y_{1} - y_{0}}{x_{1} - x_{0}} = \frac{3 - 0}{5 - 0} = 0.6 < 1$k=x1​−x0​y1​−y0​​=5−03−0​=0.6<1

2. 计算像素点坐标

$x$x	$y$y	$int \left(y + 0.5\right)$int(y+0.5)
$0$0	$0$0	$0$0
$1$1	$0+0.6$0+0.6	$1$1
$2$2	$0.6+0.6$0.6+0.6	$1$1
$3$3	$1.2+0.6$1.2+0.6	$2$2
$4$4	$1.8+0.6$1.8+0.6	$2$2
$5$5	$2.4+0.6$2.4+0.6	$3$3

注意：

当 $|k| > 1$∣k∣>1 时

使用上述计算方式可能不能画出直线，因为任意两点之间通过 DDA 算法计算直线，当 $|k| > 1$∣k∣>1 时，结果只有三个点，如果两点之间距离比较远，就会导致光栅点太稀疏，从而不能描绘直线

2. 中点画线法

对 DDA 的改进方案：

1. 提高算法效率

$y_{i+1} = y_{i} + k$yi+1​=yi​+k

因为在计算机中，加法运算是最快的，加法运算里整数加法又是最快的

一般情况下，$y$y 和 $k$k 都是小数，而且每一步运算都要对 $y$y 进行四舍五入后取整，所以可以通过把浮点运算变成整数运算来改进

2. 改变直线方程类型

中点画线法：利用直线的一般式方程

$F \left(x,\;y\right) = 0$F(x,y)=0

$Ax + By + C = 0 \;\;\;\left(其中：A = - \left(\Delta y\right); \;\; B = \left(\Delta x\right); \;\; C = - B \left(\Delta x\right)\right)$Ax+By+C=0(其中：A=−(Δy);B=(Δx);C=−B(Δx))

这样一来，对于直线上的点：$F \left(x,\;y\right) = 0$F(x,y)=0

对于直线上方的点：$F \left(x,\;y\right) > 0$F(x,y)>0

对于直线下方的点：$F \left(x,\;y\right) < 0$F(x,y)<0

原理解析：

每一次在最大位移方向上走一步，而另一个方向走不走取决于中点误差项的判断

假设：$0 \leq |k| \leq 1$0≤∣k∣≤1，所以每次在 $x$x 方向上 $+1$+1，$y$y 方向上的变化情况需要通过判断 $P_{u}$Pu​ 到 $P_{d}$Pd​ 的中点来决定

如图，此时 ideal line 与直线 $P_{u}P_{d}$Pu​Pd​ 有一个交点 $Q$Q，直线 $P_{u}P_{d}$Pu​Pd​ 有一个中点：$M \left(x_{i}+1,\;y_{i}+0.5\right)$M(xi​+1,yi​+0.5)

判断：

• 当 $Q$Q 在 $M$M 上方时，$P_{u}$Pu​ 距离直线更近，则 $P_{u}$Pu​ 为下一像素点
• 当 $Q$Q 在 $M$M 下方时，$P_{d}$Pd​ 距离直线更近，则 $P_{d}$Pd​ 为下一像素点
• 若 $Q$Q 和 $M$M 是同一个点，则 $P_{u}$Pu​ 或 $P_{d}$Pd​ 都可以是下一像素点

如何判断 $Q$Q 在 $M$M 上方还是下方？

1. 把 $M$M 代入理想直线方程：

$F \left(x_{m},\;y_{m}\right) = Ax_{m} + By_{m} + C$F(xm​,ym​)=Axm​+Bym​+C

$令：d = F \left(x_{m},\;y_{m}\right) = F \left(x_{i} + 1,\;y_{i} + 0.5\right)$令：d=F(xm​,ym​)=F(xi​+1,yi​+0.5)

$\;\;= A \left(x_{i}+1\right) + B \left(y_{i} + 0.5\right) + C$=A(xi​+1)+B(yi​+0.5)+C

2. 判断

• 当 $d < 0$d<0 时：$Q$Q 在 $M$M 上方，下一像素点为 $P_{u}$Pu​
• 当 $d > 0$d>0 时：$Q$Q 在 $M$M 下方，下一像素点为 $P_{d}$Pd​
• 当 $d = 0$d=0 时：$Q$Q 等于 $M$M，下一像素点为 $P_{u}$Pu​ 或 $P_{d}$Pd​ 都可以

算法：

$y = \left\{\begin{matrix} y+1 & \left(d < 0\right) \\ y & \left(d \geq 0 \right) \end{matrix}\right.$y={y+1y​(d<0)(d≥0)​

算法计算量：为了求得 $d$d 值，需要 $4$4 个乘法，$2$2 个加法

对中点画线法的改进：因为 $d$d 是 $x$x, $y$y 的线性函数，所以可以采用增量计算

推导过程：

代入中点坐标求得 $d_{0}$d0​：

$d_{0} = F \left(x_{m0},\;y_{m0}\right)$d0​=F(xm0​,ym0​)

$\;\;\;\;\;\;\;\;\;\;\;\;\;\;= F \left(x_{i}+1,\;y_{i}+0.5\right)$=F(xi​+1,yi​+0.5)

$\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = A \left(x_{i}+1\right) + B \left(y_{i}+0.5\right) + C$=A(xi​+1)+B(yi​+0.5)+C

假设 $d < 0$d<0

则第一个取的像素点 $P_{0}$P0​ 为 $P_{u} \left(x_{i} + 1,\;y_{i} + 1\right)$Pu​(xi​+1,yi​+1)

再往下计算一个像素点 $P_{1}$P1​ 的位置：

则 $P_{1}$P1​ 可能是点 $P_{a} \left(x_{i}+2,\;y_{i}+1\right)$Pa​(xi​+2,yi​+1) 或者 $P_{b} \left(x_{i}+2,\;y_{i}+2\right)$Pb​(xi​+2,yi​+2)

则直线 $P_{a}P_{b}$Pa​Pb​ 的中点为 $M_{1} \left(x_{i}+2,\;y_{i}+1.5\right)$M1​(xi​+2,yi​+1.5)

所以：

$d_{1} = F \left(x_{m1},\;y_{m1}\right)$d1​=F(xm1​,ym1​)

$\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = F \left(x_{i}+2,\;y_{i}+1.5\right)$=F(xi​+2,yi​+1.5)

$\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = A\left(x_{i}+2\right) + B\left(y_{i}+1.5\right) + C$=A(xi​+2)+B(yi​+1.5)+C

$\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = A\left(x_{i}+1\right) + B\left(y_{i}+0.5\right) + C + A + B$=A(xi​+1)+B(yi​+0.5)+C+A+B

$\;\;\;= d_{0} + A + B$=d0​+A+B

假设 $d \geq 0$d≥0

则第一个取的像素点 $P_{0}'$P0′​ 为 $P_{d} \left(x_{i} + 1,\;y_{i}\right)$Pd​(xi​+1,yi​)

再往下计算一个像素点 $P_{1}'$P1′​ 的位置：

则 $P_{1}'$P1′​ 可能是点 $P_{a} \left(x_{i}+2,\;y_{i}+1\right)$Pa​(xi​+2,yi​+1) 或者 $P_{c} \left(x_{i}+2,\;y_{i}\right)$Pc​(xi​+2,yi​)

则直线 $P_{a}P_{c}$Pa​Pc​ 的中点为 $M_{1}' \left(x_{i}+2,\;y_{i}+0.5\right)$M1′​(xi​+2,yi​+0.5)

所以：

$d_{1} = F \left(x_{{m1}'},\;y_{{m1}'}\right)$d1​=F(xm1′​,ym1′​)

$\;\;\;\;\;\;\;\;\;\;\;\;\; = F \left(x_{i}+2,\;y_{i}+0.5\right)$=F(xi​+2,yi​+0.5)

$\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = A\left(x_{i}+2\right) + B\left(y_{i}+0.5\right) + C$=A(xi​+2)+B(yi​+0.5)+C

$\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = A\left(x_{i}+1\right) + B\left(y_{i}+0.5\right) + C + A$=A(xi​+1)+B(yi​+0.5)+C+A

$= d_{0} + A \;\;\;\;\;$=d0​+A

计算 $d_{0}$d0​：

直线的第一个像素点坐标为：$P\left(x_{0},\;y_{0}\right)$P(x0​,y0​)

$d_{0} = F \left(x_{0}+1,\;y_{0}+0.5\right)$d0​=F(x0​+1,y0​+0.5)

$\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = A \left(x_{0}+1\right) + B \left(y_{0}+0.5\right) + C$=A(x0​+1)+B(y0​+0.5)+C

$\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = Ax_{0} + By_{0} + C + A + 0.5B$=Ax0​+By0​+C+A+0.5B

因为 $P \left(x_{0},\;y_{0}\right)$P(x0​,y0​) 在直线上，所以满足 $Ax_{0} + By_{0} + C = 0$Ax0​+By0​+C=0

所以：

$d_{0} = A + 0.5B$d0​=A+0.5B

中点画线法算法：

$d_{new} = \left\{\begin{matrix} d_{old} + A + B & \left(d < 0\right) \\ d_{old} + A & \left(d \geq 0\right) \end{matrix}\right. \;\;\; d_{0} = A + 0.5B$dnew​={dold​+A+Bdold​+A​(d<0)(d≥0)​d0​=A+0.5B

至此，中点画线法算法与 DDA 的算法效率一样好

注意：

一般情况下，$A$A、$B$B 都是整数，而 $d_{0}$d0​ 的计算中存在浮点数，浮点数的运算更复杂

但是 $d_{0}$d0​ 的作用只是与 $0$0 比较大小，所以完全可以用 $2d_{0}$2d0​ 代替 $d_{0}$d0​，以此可以避免浮点数运算

此时中点画线法算法中只包含整数运算，所以更优于 DDA 算法

3. Bresenham 算法

Bresenham 拥有更优的效率和更广泛的适用范围

基本思想：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-T5cEgkci-1586352023419)(https://cdn.jsdelivr.net/gh/TUFZ/ImgHosting//TUFZ-Img/article/20Apr08A/06.png)]

通过各行、各列像素中心构造一组虚拟网格线，按照直线起点到终点的顺序，计算直线与各垂直网格线的交点，然后根据误差项（交点距离像素点的距离）的符号确定该列像素中与此交点最近的像素

假设每次 $x+1$x+1，$y$y 的递增（减）量为 $0$0 或 $1$1，它取决于实际直线与光栅网格点的距离，这个距离的最大误差是 $0.5$0.5

• 如果 $d < 0.5$d<0.5，$y$y 的递增（减）量为 $0$0
• 如果 $d > 0.5$d>0.5，$y$y 的递增（减）量为 $1$1
• 如果 $d = 0.5$d=0.5，$y$y 的递增（减）量为 $0$0 或 $1$1 中任意一个

误差项 $d$d 的初值 $d_{0} = 0$d0​=0

初始之后的 $d = d + k$d=d+k

一旦 $d \geq 1$d≥1，就将其减 $1$1，以保证 $d$d 的相对性，且始终在 $0$0、$1$1 之间

计算下一个象素点的原理：

$P_{next = }\left\{\begin{matrix} x_{i+1} = x_{i} + 1 \\ y_{i+1} = \left\{\begin{matrix} y_{i} + 1 & \left(d > 0.5\right) \\ y_{i} & \left(d \leq 0.5\right) \end{matrix}\right. \end{matrix}\right.$Pnext=​⎩⎨⎧​xi+1​=xi​+1yi+1​={yi​+1yi​​(d>0.5)(d≤0.5)​​

算法效率优化：

1. 令 $e = d - 0.5$e=d−0.5

将值的大小替换成正负号

$P_{next = }\left\{\begin{matrix} x_{i+1} = x_{i} + 1 \\ y_{i+1} = \left\{\begin{matrix} y_{i} + 1 & \left(e > 0\right) \\ y_{i} & \left(e \leq 0\right) \end{matrix}\right. \end{matrix}\right.$Pnext=​⎩⎨⎧​xi+1​=xi​+1yi+1​={yi​+1yi​​(e>0)(e≤0)​​

• $e_{初} = -0.5$e初​=−0.5
• 每当 $x + 1$x+1，则 $e = e + k$e=e+k
• 如果 $e > 0$e>0，则 $e = e - 1$e=e−1

2. 令 $2e\Delta x = e$2eΔx=e

因为 $k = \frac{dy}{dx}$k=dxdy​、$dx = \Delta x$dx=Δx

• $e_{初} = -\Delta x$e初​=−Δx
• 每当 $x + 1$x+1，则 $e = e + 2\Delta y$e=e+2Δy
• 如果 $e > 0$e>0，则 $e = e - 2\Delta x$e=e−2Δx

至此，算法全部改进为整数加法，且不受直线方程类型的限制

算法步骤：

1. 输入直线的两端点 $P_{0}\left(x_{0},\;y_{0}\right)$P0​(x0​,y0​) 和 $P_{1}\left(x_{1},\;y_{1}\right)$P1​(x1​,y1​)
2. 计算初始值 $\Delta x$Δx、$\Delta y$Δy、$e = -\Delta x$e=−Δx、$x = x_{0}$x=x0​、$y = y_{0}$y=y0​
3. 绘制点 $\left(x,\;y\right)$(x,y)
4. 将 $e$e 替换为 $e + 2\Delta y$e+2Δy，判断 $e$e 的符号
   • 若 $e > 0$e>0，则将 $\left(x,\;y\right)$(x,y) 替换为 $\left(x+1,\;y+1\right)$(x+1,y+1)，同时将 $e$e 替换为 $e - 2\Delta y$e−2Δy
   • 否则，将 $\left(x,\;y\right)$(x,y) 替换为 $\left(x+1,\;y\right)$(x+1,y)
5. 当直线没有画完时，重复步骤 3 和 4，否则结束

Bresenham 算法很像 DDA 算法，都是加斜率，但 DDA 算法是每次求出一个新的 $y$y 以后取整来画，而 Bresenham 算法是判符号来决定上下两个点，所以该算法集中了 DDA 和中点算法的优点，而且应用范围更广泛

4. 结

以上是基础原理，实现代码还是一个没填????

我的个人博客还有更多文章