【计算机图形学|直线生成算法】Bresenham画法详解-Toy模板网

这篇具有很好参考价值的文章主要介绍了【计算机图形学|直线生成算法】Bresenham画法详解。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

概述

Bresenham画法是一种用于计算计算机图形中线条的算法，其原理是沿着所需绘制的线段中的像素点进行递增或递减，来进行准确的点阵绘制。

实现该算法的关键在于确定像素在基准线上的位置，以及在每次迭代时进行相应的调整。该算法比传统的直线算法更快且更准确，在低速处理器和低效内存设备上尤其适用。

Bresenham画法的思想可以拓展到曲线绘制、圆形绘制等其他图像绘制领域。

一、判别式推导

假设直线的表达式为 $y = m x + b$ ，并且线段 $A D$ 与线段 $TS$ 相交于点 $M$ ， $TM$ 的长度为 $t$ ， $MS$ 的长度为 $s$ 。实现算法需要计算 $s$ 与 $t$ 的大小关系来确定选择上点或者下点。

bresenham算法,计算机图形学,图形渲染,学习
对于M点以及s与t的大小关系分析得出：

如果给定点 $x_i, y_i)$ 和点 $x_{i+1}, y_{i+1})$ ，使用直线方程式 $y = m x + b$ 。那么，点 $x_{i+1}, y_{i+1})$ 的坐标可以表示为：

$x_{i+1} = x_i + 1 \\ y_{i+1} = m(x_i + 1) + b$

此时，点 $P$ 的坐标为 $x_i, y_i)$ ，点 $S$ 的坐标为 $x_i, y_i+1)$ ，点 $T$ 的坐标为 $x_i+1, y_i+1)$ 。

我们需要计算 $s$ 和 $t$ 的值来判断绘制线段的方向。

首先， $s$ 的值为：

$s = y_{i+1} - y_i = m(x_i + 1) + b - (mx_i + b) = m$

其次， $t$ 的值为：

$\begin{aligned} t &= 2y_{i+1} - 2y_i + 2 \\ &= 2(m(x_i + 1) + b) - 2(mx_i + b) + 2 \\ &= 2m(x_i + 1 - x_i) + 2 \\ &= 2m + 2 \end{aligned}$

假设 $TM$ 的长度为 $t$ ， $SM$ 的长度为 $s$ ，那么 $s - t$ 的值为：

$s - t = (mx_i + b + 1) - y_i - (y_i + 1 - mx_i - b) = 2(mx_i + 1 - y_i)$

因此，我们可以按照下列规则判断绘制线段的方向：

如果 $s - t > 0$ ，根据 M 点在 T 点下面，我们可以得出 M 点到 T 点的距离大于至 S 点的距离。因此，下一个要绘制的点为 T 点。
如果 $s - t < 0$ ，根据 M 点在 T 点上面，我们可以得出 M 点到 T 点的距离小于至 S 点的距离。因此，下一个要绘制的点为 S 点。
如果 $s - t = 0$ ，根据 M 点到 T 和 S 点的距离相等，我们可以随机选择 T 或 S 点作为下一个要绘制的点。

这样，我们就可以根据直线方程和点 $x_i, y_i)$ 来计算 $x_{i+1}, y_{i+1})$ 的坐标，并根据 M 点的位置和距离来确定绘制线段的方向。

二、迭代推导

对于给定的两个点 $x_1, y_1)$ 和 $x_2, y_2)$ ，我们可以通过计算以这两个点为端点的直线的斜率和截距来计算点 $x_1+1, y_1)$ 对应的 $B rese nham$ 算法中的决策参数 $d_{i+1}$ ，以便确定下一个点的位置。具体来说，计算方法如下：

将 $x_1, y_1)$ 和 $x_2, y_2)$ 视为直线上的两个点，我们有：

$\begin{aligned} \Delta x &= x_2 - x_1\\ \Delta y &= y_2 - y_1\\ m &= {\Delta y \over \Delta x}\\ \end{aligned}$

接下来，计算 $s - t$ 的值：

$2\Delta y(x_1+{1\over 2}) + 2b - 2y_1 - 1 = 2\Delta y(x_1+{1\over 2}) - 2\Delta x(y_1+{1\over 2})+2b-1$

将式子两边乘以 $\Delta x$ ，得到：

$\Delta x(s-t) = 2\Delta y\Delta xi-2\Delta xy_i+2b\Delta x-\Delta x$

令 $\Delta x(s-t)$ ，我们可以写成：

$2\Delta yi - 2\Delta xy_{i} + C, \qquad C=2b\Delta x - \Delta x+1$

这个时候，我们需要计算 $d_{i+1}$ 与 $d_{i}$ 的差值。可以通过 $C$ 带来的影响来计算。 $x_{i+1}$ 的变化量为 $1$ ，那么显然有：

$\begin{aligned} di+1 &= 2\Delta y(x_{i+1})-2\Delta x y_i+2b\Delta x - \Delta x + 1\\ &= 2\Delta y(x_i+1)-2\Delta xy_i + 2\Delta y - 2\Delta xy_i + C\\ &= di+2\Delta y - 2\Delta xy_i+ C \end{aligned}$

因此，

$2\Delta y - 2\Delta x(y_{i+1}-y_i)$

至此，我们可以根据 $d i + 1 - d i$ 的大小关系，来确定绘制线段的方向：

当 $\geq 0$ 时，取上点 $T^{'}$ ，即 $y_{i+1}=y_i+1$ ；
当 $d i + 1 - d i < 0$ 时，取下点 $S^{'}$ ，即 $y_{i+1}=y_i$ 。

这样，我们就可以根据两个点的坐标，计算出 $B rese nham$ 算法中的决策参数 $d_{i+1}$ ，并根据 $d i + 1 - d i$ 的大小关系确定绘制线段的方向了。

bresenham算法,计算机图形学,图形渲染,学习

三、计算初值

假设初值为 $x_0, y_0)$ ，根据直线方程 $y = m x + b$ ，可以得到 $mx_0+b-y_0=0$ 。
将此式代入 $d_0=\Delta x(s-t)=\Delta x(2m(x_0+1)+2b-2y_0-1)$ 中，得到
$d_0=\Delta x(2mx_0+2b-2y_0+2m-1)=\Delta x(2m-1)$ 。其中， $m=\frac{\Delta y}{\Delta x}$ ，表示直线的斜率。