直线光栅化-Bresenham算法

直线光栅化-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})\)

整理决策参数方程得:

\[P_{k}=2\Delta y·x_{k}-2\Delta x·y_{k}+C \]

其中 \(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\)

则决策方程的递推式为:

\[P_{k+1}= \left\{\begin{matrix} P_{k}+(-2\Delta x+2\Delta y),P_{k}\ge 0 \\ P_{k}+2\Delta y,P_{k}<0 \end{matrix}\right. \]

将初始坐标 \(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})\)

整理得决策参数方程为:

\[P_{k}=2\Delta x·y_{k}-2\Delta y·x_{k}+C \]

那么递推方程为:

\[P_{k+1}=\left\{\begin{matrix} p_{k}+(-2\Delta x-2\Delta y),P_{k}\ge 0 \\ P_{k}-2\Delta y,P_{k}<0 \end{matrix}\right. \]

其中 \(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_{1}=2\Delta y-\Delta x \]

\[递推方程: P_{k+1}= \left\{\begin{matrix} P_{k}+(-2\Delta x+2\Delta y),P_{k}\ge 0 \\ P_{k}+2\Delta y,P_{k}<0 \end{matrix}\right. \]

\(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_{1}=-2\Delta y-\Delta x \]

\[递推方程: P_{k+1}=\left\{\begin{matrix} p_{k}+(-2\Delta x-2\Delta y),P_{k}\ge 0 \\ P_{k}-2\Delta y,P_{k}<0 \end{matrix}\right. \]

\(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_{1}=2\Delta x-\Delta y \]

\[递推方程: P_{k+1}= \left\{\begin{matrix} P_{k}+(2\Delta x-2\Delta y),P_{k}\ge 0 \\ P_{k}+2\Delta x,P_{k}<0 \end{matrix}\right. \]

\(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_{1}=-2\Delta x-\Delta y \]

\[递推方程: P_{k+1}=\left\{\begin{matrix} p_{k}+(-2\Delta x-2\Delta y),P_{k}\ge 0 \\ P_{k}-2\Delta x,P_{k}<0 \end{matrix}\right. \]

\(P_{k}\ge 0\) 时,有 \(x_{k+1}=x_{k}-1\) ;当 \(P_{k}<0\) 时,有 \(x_{k+1}=x_{k}\)

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

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

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