资讯

历史

科技

环境与自然

成长

游戏

财经

文学与艺术

美食

健康

家居

文化

情感

汽车

三农

军事

旅行

运动

教育

生活

星座命理

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

创作时间:

作者:

@小白创作中心

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

引用

CSDN

https://blog.csdn.net/u010092716/article/details/139142761

什么叫做光栅化？

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

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

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

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

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

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

为什么需要光栅化？

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

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

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

数值微分法（DDA）
Bresenham
Wu

使用场景比较：

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

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

Bresemham算法

问题定义：

已知两个点$p_1(x_1,y_1), p_2(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$更大，表明向下倾斜，反之向上）

让我们开始步入数学公式的殿堂：

$$
\begin{aligned}
d_0 &= y_i + 1 - k(x_i + 1) - b\
d_1 &= k(x_i + 1) + b - y_i
\end{aligned}
$$

既然要比较$d_0$和$d_1$的大小，咱们就用$d_1 - d_0$：

$$
\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}
$$

由于模型简化，根据已知条件：

$$
\begin{aligned}
k &= \frac{y_2 - y_1}{x_2 - x_1}\
\Delta x &= x_2 - x_1 > 0
\end{aligned}
$$

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

$$
\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}
$$

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

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

迭代模型：

$$
\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}
$$

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

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

令$i=1$，带入$(x_1, kx_1 + b)$

咱们得到：

$$
\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}
$$

重申目标：

我们需要通过$p_i$的正负值，从而决定$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}
$$

所以我们发现：$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}$，直到所有！