Bresenham快速画直线算法

Bresenham快速画直线算法

现在的计算机的图像的都是用像素表示的,无论是点、直线、圆或其他图形最终都会以点的形式显示。人们看到屏幕的直线只不过是模拟出来的,人眼不能分辨出来而已。那么计算机是如何画直线的呢,其实有比较多的算法,这里讲的是Bresenham的算法,是光栅化的画直线算法。直线光栅化是指用像素点来模拟直线,比如下图用蓝色的像素点来模拟红色的直线。

给定两个点起点P1(x1, y1), P2(x2, y2),如何画它们直连的直线呢,即是如何得到上图所示的蓝色的点。假设直线的斜率00,直线在第一象限,Bresenham算法的过程如下: 1.画起点(x1, y1).

2.准备画下一个点,X坐标加1,判断如果达到终点,则完成。否则找下一个点,由图可知要画的点要么为当前点的右邻接点,要么是当前点的右上邻接点。

2.1.如果线段ax+by+c=0与x=x1+1的交点y坐标大于(y+*y+1))/2则选右上那个点 2.2.否则选右下那个点。 3.画点 4.跳回第2步 5.结束

算法的具体过程是怎样的呢,其实就是在每次画点的时候选取与实现直线的交点y坐标的差最小的那个点,例如下图:

关键是如何找最近的点,每次x都递增1,y则增1或者不增1,由上图,假设已经画了d1点,那么接下来x加1,但是选d2 还是u点呢,直观上可以知道d2与目标直线和x+1直线的交点比较近即纵坐标之差小也即与(x+1, y+1)点纵坐标差大于0.5,所当然是选d2,其他点了是这个道理。

一、 算法原理简介:

算法原理的详细描述及部分实现可参考:

http://www.cs.helsinki.fi/group/goa/mallinnus/lines/bresenh.html

假设以(x, y)为绘制起点,一般情况下的直观想法是先求m = dy /dx(即x每增加1, y的增量),然后逐步递增x, 设新的点为x1 = x + j, 则y1 = round(y + j * m)。可以看到,这个过程涉及大量的浮点运算,效率上是比较低的(特别是在嵌入式应用中,DSP可以一周期内完成2次乘法,一次浮点却要上百个周期)。

下面,我们来看一下Bresenham算法,如Fig. 1,(x, y +ε)的下一个点为(x+1, y + ε + m),这里ε为累加误差。可以看出,当ε+m < 0.5时,绘制(x + 1, y)点,否则绘制(x + 1, y + 1)点。每次绘制后,ε将更新为新值:

ε = ε + m ,如果(ε + m) <0.5 (或表示为2*(ε + m) < 1) ε = ε + m – 1, 其他情况

将上述公式都乘以dx, 并将ε*dx用新符号ξ表示,可得

ξ = ξ + dy, 如果2*(ξ + dy) < dx ξ = ξ + dy – dx, 其他情况

可以看到,此时运算已经全变为整数了。以下为算法的伪代码: ξ ← 0, y ← y1 For x ← x1 to x2 do

Plot Point at (x, y) If (2(ξ + dy) < dx) ξ ←ξ + dy Else

y ← y + 1,ξ ←ξ + dy – dx End If End For 二、 算法的注意点:

在实际应用中,我们会发现,当dy > dx或出现Fig.2 右图情况时时,便得不到想要的结果,这是由于我们只考虑dx > dy,且x, y的增量均为正的情况所致。经过分析,需要考虑8种不同的情况,如Fig. 3所示:

联系客服:779662525#qq.com(#替换为@) 苏ICP备20003344号-4