【计算机图形学】直线的两种生成算法（DDA算法、Bresenham算法）

本文主要是介绍【计算机图形学】直线的两种生成算法（DDA算法、Bresenham算法），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

直线的两种生成算法（DDA算法、Bresenham算法）

---

1.计算机绘制直线的原理

在计算机中，直线的显示并不是连续的，而是离散的点，这是由光栅化的本质决定 的。我们可以把屏幕理解为阴极射线管光栅显示器，这个显示器是由离散可发光的有线 区域单元(像素)组成的矩阵。确定最佳逼近某直线的像素的过程通常叫做光栅化。对于 水平线、垂直线以及 45°线，选择哪些光栅元素是显而易见的，而对于其他方向的直线， 像素的选择就很困难。因此，选择一个重要的算法来实现直线的绘制显得很有必要。

---

2.DDA算法的原理与实现（基于matlab）

DDA 算法是直线算法里最为简单的算法，它的基本思想是高数里的微分算法：

$$\frac{\mathrm{d}y}{\mathrm{d}x}=\frac{y_2-y_1}{x_2-x_1}$$

其有限差分近似解为：

$$\{\begin{array}{l}{x}_{i+1}=x_i+\Delta x\\ y_{i+1}=y_i+\frac{y_2-y_1}{x_2-x_1}\Delta x\end{array}$$

根据这个算法，我们可以将某条线段的两个端点作为输入，并利用这两个端点来将此线段进行微分（迭代求值），在每轮迭代中，将微分得到的每个点单独绘制。最终，所有单独绘制的点就构成了我们所需要绘制的直线。

---

下面给出用matlab实现该算法的完整代码：

function main					%测试函数
clc
clear;
DDA(0,0,30,40,'r')    			%勾三股四弦五function DDA(x1,y1,x2,y2,color)		%DDA算法dx=(x2-x1);dy=(y2-y1);step=max(abs(dx),abs(dy));deltax=dx/step;deltay=dy/step;x=x1;y=y1;hold onfor i=1:stepscatter(round(x),round(y),'.',color)    	  %绘出当前点x=x+deltax;                            		  %更新xy=y+deltay;                             	  %更新yendplot([x1,x2],[y1,y2])                       	  %直接绘制原线以对比grid minor										  %添加网格hold off

运行后得到的效果如下:

上图展示的是在给定较短线段时（长度为50个像素），采用DDA算法绘出的直线情形（上图中的红点部分），其中的蓝色线段是这条线段本身（真实线段）
接下来若将该点设置长一些，即将上面的测试代码改为如下：

function main
clc
clear;
DDA(0,0,100,75,'r')	%勾三股四弦五

则此时的成像效果如下：

上图中的红点即为DDA算法绘制的给定线段，而其中的黄线则为真实线段
可以发现此时点的密集程度大大增加，成像效果相较于上面也就好一些。

---

3.Bresenham算法的原理与实现（基于matlab）

原理：
这里仅展示最简单的一种情况（直线斜率在区间 $(0,1)$ 之间的），其他情况可以类似推导。
设当前像素点为 $P(x_p,y_p)$，下一像素点有两种选择 $P_1$ 或 $P_2$，设 $P_1、P_2$ 的中点为 $M(x_{p+1},y_{p+0.5})$ ，$Q$ 为所画直线与直线 $x=x_{p+1}$ 交点，如下图所示：

当 $Q$ 在 $M$ 上方时，下一像素点取 $P_2$；当 $Q$ 在 $M$ 下方时，下一像素点取 $P_1$。

---

实现：

1. 首先设待画直线的起点和终点坐标分别为 $(x_1,y_1),(x_2,y_2)$，则根据起点和中点坐标可以得到该直线的斜率为 $k=\frac{y_2-y_1}{x_2-x_1}$。我们知道直线方程可以用 $F(x,y)=ax+by+c$ 的形式来表达，此时该直线的斜率 $k=-\frac{a}{b}$，那也就是说我们可以直接令 $a=y_1-y_2,b=x_2-x_1$（只要满足商为 $-k$ 即可）。
   此时 $F(x,y)=x(y_1-y_2)+y(x_2-x_1)+c$，我们再随意带一个点进去（比如 $(x_1,y_1)$），便可求得 $c=x_1{y}_2-x_2{y}_1$ ，即得到该直线的方程为：
   $$\{\begin{array}{l}F(x,y)=ax+by+c=0\\ a=y_1-y_2\\ b=x_2-x_1\\ c=x_1{y}_2-x_2{y}_1\end{array}$$

2. 对于某个点 $(x,y)$，我们要知道其与直线方程 $F(x,y)$ 存在如下关系：
   $$\{\begin{array}{ll}F(x,y)=0，& 在直线上\\ F(x,y)>0，& 在直线上方\\ F(x,y)<0，& 在直线下方\end{array}$$
   因此，我们可以直接将中点 $M(x_{p+1},y_{p+0.5})$ 带入直线方程中：
   即 $d=F(x_{p+1},y_{p+0.5})=a{x}_{p+1}+b{y}_{p+0.5}+c$，我们就可以根据 $d$ 的值来确定下一个像素点：
   $$\{\begin{array}{ll}取P_1和P_2均可（此处取P_1），& d=0\\ 取P_1为下一像素点，& d>0（表示M在直线上方）\\ 取P_2为下一像素点，& d<0（表示M在直线下方）\end{array}$$
   若设当前像素点为 $P(x_p,y_p)$，我们考虑 $d\ge 0$ 和 $d<0$ 两种情况：

• $d\ge 0$，此时 $P_1(x_{p+1},y_p)$ 为下一像素点，则再下一像素点为 $(x_{p+2},y_{p+0.5})$：
  $d^{\prime }=F(x_{p+2},y_{p+0.5})=a{x}_{p+2}+b{y}_{p+0.5}+c=a+(a{x}_{p+1}+b{y}_{p+0.5}+c)=a+d$，此时 $d^{\prime }=a+d$，即增量为 $a$。
• $d<0$，此时 $P_2(x_{p+1},y_{p+1})$ 为下一像素点，则再下一像素点为 $(x_{p+2},y_{p+1.5})$ ：
  $d^{\prime \prime }=F(x_{p+2},y_{p+1.5})=a{x}_{p+2}+b{y}_{p+1.5}+c=a+b+(a{x}_{p+1}+b{y}_{p+0.5}+c)=a+b+d$，此时 $d^{\prime \prime }=a+b+d$，即增量为 $a+b$。

3. 注意到 $d_0$ 的初始化是用 $(x_1,y_{0.5})$ 来计算的：即 $d_0=a+0.5b+c$，且在后面的迭代中， $y$ 始终都含有 0.5。而我们在迭代中判断下一个点纵坐标的取值时仅仅与 $d$ 值的正负有关，因此为了摆脱浮点数的出现，我们统一将所有 $d_i$ 的计算都使用 $2d_i$ 来代替，因此 $d_0=2a+b+2c$，增量 $d^{\prime }=2a$，增量 $d^{\prime \prime }=2a+2b$。

---

下面给出用matlab实现该算法的完整代码：

function main         %测试代码
clc
clear;
Bresenham(0,0,50,40,'r')function Bresenham(x1,y1,x2,y2,color)		%Bresnham算法a = (y1-y2);b = (x2-x1);c = x1*y2-x2*y1;d=2*a+b+c;d1=2*a;d2=2*(a+b);x=x1;y=y1;hold onscatter(x,y,'.',color)for i=x:x2if d<0x=x+1;y=y+1;d=d+d2;elsex=x+1;d=d+d1;endscatter(x,y,'.',color)endplot([x1,x2],[y1,y2])                       %绘制原线以对比grid minorhold off

运行后得到的效果如下：

可以看出，中点算法在 $x$ 轴上进行变化时，$y$上的取值严格按照 Bresenham 的原理进行取值。该算法作为数值微分法（DDA）的改进算法，其采用了直线的一般式方程、增量思想、实现整数加法等优化的思路，其成像的主要思想是以贴合直线为中心，使得这样的算法在绘制出的效果上是优于 DDA 算法的。

END

---

这篇关于【计算机图形学】直线的两种生成算法（DDA算法、Bresenham算法）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---