图形学初识--光栅化直线算法

什么叫做光栅化？

光栅化（Rasterization）是一种计算机图形学技术，用于将几何图形（如矢量图形、3D模型）转换成由像素或点组成的光栅图像（raster image）。这个过程通常在图形硬件（如显卡）上进行，用于生成最终在屏幕上显示的图像。

上面来自chatGPT，对于有图形学基础的人还是很好理解。

我这里单纯用绘制2D图形的两个案例，用大白话简易解释一下：

（1）给屏幕坐标系中的两个点坐标，如何绘制出以这两个点为首尾的直线？这就是直线光栅化的作用；

（2）给屏幕坐标系中三个点，如何绘制以这三个点为顶点的填充三角形？这就是三角形光栅化的作用；

再次声明，以此类推，这些说辞都是方便理解用的，并不专业！

为什么需要光栅化？

计算机图形通常以矢量形式存储和处理，包括点、线、三角形等基本几何形状。

然而，显示设备（如计算机屏幕、手机屏幕）是基于像素的。这意味着最终显示图像需要将矢量图形转换为像素阵列，光栅化正是这个转换过程。

直线的光栅化算法有哪些？

• 数值微分法（DDA）
• Bresenham
• Wu

使用场景比较：

• DDA算法：适合简单的直线绘制，计算过程容易理解，但由于使用浮点数，效率较低
• Bresenham算法：效率高，使用整数运算，适用于大多数应用场景，尤其是实时图形渲染
• Wu算法：用于生成平滑的抗锯齿直线，适合需要高质量图像的应用

咱们重点讲述Bresemham算法！也是最常用的！

Bresemham算法

问题定义：

已知两个点 $p1(x_1,y_1),p2(x_2,y_2)$ 请在屏幕像素空间绘制一条直线。

问题模型简化：

最简单的问题模型满足如下条件：

• $x_1<x_2$
• $y_1<y_2$
• 直线表达式： $y=kx+b$​
• 直线斜率 $k$ 满足：$0<k<1$

概念图如下：

算法核心理解：

顶级理解： 假设当前直线已经通过点 $(x_i,y_i)$ ，那么当 $x_i->x_i+1$ ，此时的 $y_i$ 如何变动呢？如下图所示：

其实 $y_i$ 的变动只有两个选择，要么 $y_i->y_i$ 保持不变，要么 $y_i$ -> $y_{i+1}$ 向上增加一个像素。

这两种情况说人话：一个向正东移动、一个向东北方移动！

问题来了： 那么何时朝正东移动，何时朝东北移动，依据什么呢？如下图所示：

感官上来看： 依据直线是朝下倾斜一点，还是朝上倾斜一点。

数学表达来看： 根据上图的 $d_0$ 和 $d_1$ 谁更大（$d_0$ 更大，表明向下倾斜，反之向上）

让我们开始步入数学公式的殿堂：
d 0 = y i + 1 − k ( x i + 1 ) − b d 1 = k ( x i + 1 ) + b − y i

$$\begin{aligned} d_0 &= y_i + 1 - k(x_i + 1) - b\\ d_1 &= k(x_i + 1) + b - y_i \end{aligned}$$ d0​d1​​=yi​+1−k(xi​+1)−b=k(xi​+1)+b−yi​​

既然要比较 $d_0$ 和 $d_1$ 的大小，咱们就用$d_1$ - $d_0$​ ：
d 1 − d 0 = k ( x i + 1 ) + b − y i − [ y i + 1 − k ( x i + 1 ) − b ] = 2 k ( x i + 1 ) − 2 y i − 1 + 2 b

$$\begin{aligned} d_1 - d_0 &= k(x_i + 1) + b - y_i - [ y_i + 1 - k(x_i + 1) - b ]\\ &= 2k(x_i + 1) - 2y_i - 1 + 2b \end{aligned}$$ d1​−d0​​=k(xi​+1)+b−yi​−[yi​+1−k(xi​+1)−b]=2k(xi​+1)−2yi​−1+2b​

由于模型简化，根据已知条件：
k = y 2 − y 1 x 2 − x 1 Δ x = x 2 − x 1 > 0

$$\begin{aligned} k &= \frac{y_2 - y_1}{x_2 - x_1}\\ \Delta x &= x_2 - x_1 > 0 \end{aligned}$$ kΔx​=x2​−x1​y2​−y1​​=x2​−x1​>0​

所以，等式两边同乘 $\Delta x$ ，表达式正负号不会发生变化，记 $p_i=\Delta x(d_1-d_0)$

p i = Δ x ( d 1 − d 0 ) = Δ x ∗ [ 2 k ( x i + 1 ) − 2 y i − 1 + 2 b ] = Δ x ∗ [ 2 ∗ y 2 − y 1 x 2 − x 1 ∗ ( x i + 1 ) − 2 y i − 1 + 2 b ] = Δ x ∗ [ 2 ∗ Δ y Δ x ∗ ( x i + 1 ) − 2 y i − 1 + 2 b ] = 2 Δ y ∗ ( x i + 1 ) + Δ x ( − 2 y i − 1 + 2 b ) = 2 Δ y ∗ ( x i + 1 ) − Δ x ( 2 y i + 1 − 2 b ) = 2 Δ y ∗ x i − 2 Δ x y i + [ 2 Δ y + ( 2 b − 1 ) Δ x ]

$$\begin{aligned} p_i &= \Delta x(d_1 - d_0)\\ &= \Delta x * [2k(x_i + 1) - 2y_i - 1 + 2b]\\ &= \Delta x * [2* \frac{y_2 - y_1}{x_2 - x_1} * (x_i + 1) - 2y_i - 1 + 2b]\\ &= \Delta x * [2* \frac{\Delta y}{\Delta x} * (x_i + 1) - 2y_i - 1 + 2b]\\ &= 2\Delta y*(x_i + 1) + \Delta x(-2y_i - 1 + 2b)\\ &= 2\Delta y*(x_i + 1) - \Delta x(2y_i + 1 - 2b)\\ &= 2\Delta y*x_i - 2\Delta xy_i + [2\Delta y + (2b-1)\Delta x] \end{aligned}$$ pi​​=Δx(d1​−d0​)=Δx∗[2k(xi​+1)−2yi​−1+2b]=Δx∗[2∗x2​−x1​y2​−y1​​∗(xi​+1)−2yi​−1+2b]=Δx∗[2∗ΔxΔy​∗(xi​+1)−2yi​−1+2b]=2Δy∗(xi​+1)+Δx(−2yi​−1+2b)=2Δy∗(xi​+1)−Δx(2yi​+1−2b)=2Δy∗xi​−2Δxyi​+[2Δy+(2b−1)Δx]​

推导到这，咱们观察一下：$\Delta y$已知、$\Delta x$已知，所以 $p_i$ 的值就取决于 $x_i$、$y_i$、b的值

因为咱们发现出现了b，b很有可能是浮点数，是不满足咱们这个算法的要求的，于是伟大的思路，要求我们尝试构造递推关系式，来进行对b消去！

迭代模型：
p i = 2 Δ y x i − 2 Δ x y i + [ 2 Δ y + ( 2 b − 1 ) Δ x ] p i + 1 = 2 Δ y ( x i + 1 ) − 2 Δ x y i + 1 + [ 2 Δ y + ( 2 b − 1 ) Δ x ] p i + 1 − p i = 2 Δ y − 2 Δ x ( y i + 1 − y i )

$$\begin{aligned} p_i &= 2\Delta yx_i - 2\Delta xy_i + [2\Delta y + (2b-1)\Delta x]\\ p_{i+1} &= 2\Delta y(x_i+1) - 2\Delta xy_{i+1} + [2\Delta y + (2b-1)\Delta x]\\ p_{i+1} - p_i &= 2\Delta y - 2\Delta x(y_{i+1} - y_i) \end{aligned}$$ pi​pi+1​pi+1​−pi​​=2Δyxi​−2Δxyi​+[2Δy+(2b−1)Δx]=2Δy(xi​+1)−2Δxyi+1​+[2Δy+(2b−1)Δx]=2Δy−2Δx(yi+1​−yi​)​

惊奇的发现，b被消去了，大功告成，这是我们发现：计算 $p_{i+1}$ 的值，只和 $p_i$ 以及 $y_{i+1}$ 和 $y_i$ 有关系！

所以咱们需要单独计算 $p_1$，咱们就用这个公式： $p_i=2\Delta y{x}_i-2\Delta x{y}_i+[2\Delta y+(2b-1)\Delta x]$

令 $i$ = 1，带入$(x_1,k{x}_1+b)$

咱们得到：
p 1 = 2 Δ y x i − 2 Δ x y i + [ 2 Δ y + ( 2 b − 1 ) Δ x ] = 2 Δ y x 1 − 2 Δ x ( k x 1 + b ) + [ 2 Δ y + ( 2 b − 1 ) Δ x ] = 2 Δ y x 1 − 2 Δ x ( Δ y Δ x x 1 + b ) + [ 2 Δ y + ( 2 b − 1 ) Δ x ] = 2 Δ y x 1 − 2 Δ y x 1 − 2 b Δ x + 2 Δ y + 2 b Δ x − Δ x ) = 2 Δ y − Δ x

$$\begin{aligned} p_1 &= 2\Delta yx_i - 2\Delta xy_i + [2\Delta y + (2b-1)\Delta x]\\ &=2\Delta yx_1 - 2\Delta x(kx_1+b) + [2\Delta y + (2b-1)\Delta x]\\ &=2\Delta yx_1 - 2\Delta x(\frac{\Delta y}{\Delta x}x_1+b) + [2\Delta y + (2b-1)\Delta x]\\ &=2\Delta yx_1 - 2\Delta yx_1-2b\Delta x + 2\Delta y + 2b\Delta x-\Delta x)\\ &=2\Delta y - \Delta x \end{aligned}$$ p1​​=2Δyxi​−2Δxyi​+[2Δy+(2b−1)Δx]=2Δyx1​−2Δx(kx1​+b)+[2Δy+(2b−1)Δx]=2Δyx1​−2Δx(ΔxΔy​x1​+b)+[2Δy+(2b−1)Δx]=2Δyx1​−2Δyx1​−2bΔx+2Δy+2bΔx−Δx)=2Δy−Δx​

重申目标：

我们需要通过 $p_i$ 的正负值，从而决定 $d_1$ 和 $d_0$ 谁大谁小，从而决定他是往东北方向移动，还是往正东方向移动。

数学表达如下：
y i + 1 = { y i , p i < = 0 即 d 1 < d 0 y i + 1 , p i > 0 即 d 1 > d 0 y_{i+1}=

$$\begin{cases} y_i, & p_i<=0 即d_1 < d_0 \\ y_i + 1, & p_i>0 即d_1 > d_0 \end{cases}$$ yi+1​={yi​,yi​+1,​pi​<=0即d1​<d0​pi​>0即d1​>d0​​

所以我们发现：$y_{i+1}$ 其实是由 $p_i$ 决定的。咱们已知 $p_1$ 自然可以求出 $y_2$，又根据递推关系式：
$$p_{i+1}-p_i=2\Delta y-2\Delta x(y_{i+1}-y_i)$$

自然而然可以迭代计算，求出：$p_2$、$y_3$、$p_3$、$y_4$、…$p_k$、$y_{k+1}$，直到所有！

算法拓展：

前面咱们由于为了推导公式，所以简化了模型，假设了以下条件：

• $x_1<x_2$
• $y_1<y_2$
• 直线表达式： $ y = kx + b$​
• 直线斜率 $k$ 满足：$0<k<1$

但是实际在一个二维平面上，一条直线有八种情况：

• $x_1<x_2$ 且 $y_1<y_2$ 且 $0<k>1$

• $x_1<x_2$ 且 $y_1<y_2$ 且 $k>1$

• $x_1>x_2$ 且 $y_1<y_2$ 且 $0<k>1$

• $x_1>x_2$ 且 $y_1<y_2$ 且 $k>1$

• $x_1<x_2$ 且 $y_1>y_2$ 且 $0<k>1$

• $x_1<x_2$ 且 $y_1>y_2$ 且 $k>1$

• $x_1>x_2$ 且 $y_1>y_2$ 且 $0<k>1$

• $x_1>x_2$ 且 $y_1>y_2$ 且 $k>1$

如下图，这八种情况，其实就对应八个方位：

计算的情形其实也类似，只需要将目标点转换到咱们简化模型状态，然后最后结果再转换回去就可以！

比如：x符号取反、y符号取反、xy互换等等，就不多赘述了！

结尾：喜欢的小伙伴可以点点关注+赞哦

希望对各位小伙伴能够有所帮助哦， 我是航火火，火一般的男人！