直线光栅化-Bresenham算法

设直线方程为 \(y=kx+b\) ，其中 \(k = \Delta y/\Delta x\) 。 当 \(0<k<1\) 时，从 \(x\) 轴开始取样。已知 \(P_{k}(x_{k},y_{k})\)，那么 \(P_{k+1}(x_{k+1},y_{k+1})\) 坐标值等于 \((x_{k}+1,y_{k})\) 或 \((x_{k}+1,y_{k}+1)\) 。

定义 \(d_{lower}=y(x_{k+1})-y_{k}\) ， \(d_{upper}=(y_{k}+1)-y(x_{k+1})\) ， 决策参数 \(P=\Delta x(d_{lower}-d_{upper})\)。

整理决策参数方程得：

其中 \(C\) 为常数等于 \((2b-1)\Delta x+2\Delta y\) 。

当 \(P_{k}\ge0\) 时 \(d_{lower}\ge d_{upper}\)，则 \(y_{k+1}=y_{k}+1\) ；如果 \(d_{lower}<d_{upper}\) ，则 \(y_{k+1}=y_{k}\) 。

将决策方程化为递推式 \(P_{k+1}-P_{k}=2\Delta y-2\Delta x(y_{k+1}-y_{k})\) 。其中 \(y_{k+1}-y_{k}\) 的值取决于 \(P_{k}\) 。如果 \(P_{k}\ge0\) 则 \(y_{k+1}-y_{k}=1\) ，否则 \(y_{k+1}-y_{k}=0\) 。

则决策方程的递推式为：

将初始坐标 \(y_{1}=\frac{\Delta y}{\Delta x}x_{1}+b\) 带入决策参数方程，得初始决策参数为 \(P_{1}=2\Delta y-\Delta x\) 。

同理，当 \(-1<k<0\) 时，定义 \(d_{lower}=y_{k}-y(x_{k+1})\) ， \(d_{upper}=y(x_{k}+1)-(y_{k}-1)\) ， 决策参数 \(P=\Delta x(d_{lower}-d_{upper})\)。

整理得决策参数方程为：

那么递推方程为：

其中 \(C\) 为常数等于 \(-(2b+1)\Delta x-2\Delta y\) 。同理得初始决策参数为 \(P_{1}=-2\Delta y-\Delta x\) 。

综上，我们可以根据直线斜率的值将Bresenham算法的递推方程分为五种情况：

情况一、当 \(0<k<1\) 时。

从 \(x\) 轴依次取样，并使用下列递推式计算 \(x_{k+1}\) 对应的 \(y_{k+1}\) 的值：

当 \(P_{k}\ge 0\) 时，有 \(y_{k+1}=y_{k}+1\) ；当 \(P_{k}<0\) 时，有 \(y_{k+1}=y_{k}\) 。

情况二、当 \(-1<k<0\) 时。

从 \(x\) 轴依次取样，并使用下列递推式计算 \(x_{k+1}\) 对应的 \(y_{k+1}\) 的值：

当 \(P_{k}\ge 0\) 时，有 \(y_{k+1}=y_{k}-1\) ；当 \(P_{k}<0\) 时，有 \(y_{k+1}=y_{k}\) 。

情况三、当 \(k>1\) 时。

交换 \(x\) 和 \(y\) 变量，此时 \(k'=\frac{1}{k}\in(0,1)\) ，此时转换为情况1。即从 \(y\) 轴开始取样，并通过递推式计算 \(y_{k+1}\) 对应的 \(x_{k+1}\) 的值。

当 \(P_{k}\ge 0\) 时，有 \(x_{k+1}=x_{k}+1\) ；当 \(P_{k}<0\) 时，有 \(x_{k+1}=x_{k}\) 。

情况四、当 \(k<-1\) 时。

交换 \(x\) 和 \(y\) 变量，此时 \(k'=\frac{1}{k}\in(-1,0)\) ，此时转换为情况2。即从 \(y\) 轴开始取样，并通过递推式计算 \(y_{k+1}\) 对应的 \(x_{k+1}\) 的值。

当 \(P_{k}\ge 0\) 时，有 \(x_{k+1}=x_{k}-1\) ；当 \(P_{k}<0\) 时，有 \(x_{k+1}=x_{k}\) 。

情况五、当 \(k\) 不存在或 \(k = 1\) 或 \(k=-1\) 时。

对于特殊的直线，可直接绘制，无需使用Bresenham算法。

热门相关：骑士归来   霸皇纪   仗剑高歌   豪门闪婚：帝少的神秘冷妻   大神你人设崩了