布雷森汉姆直线算法

布雷森汉姆直线算法(英语:Bresenham's line algorithm)是用来描绘由两点所决定的直线的算法,它会算出一条线段在n维位图上最接近的点。这个算法只会用到较为快速的整数加法、减法和位元移位,常用于绘制电脑画面中的直线。是计算机图形学中最先发展出来的算法。

经过少量的延伸之后,原本用来画直线的算法也可用来画圆。且同样可用较简单的算术运算来完成,避免了计算二次方程式或三角函数,或递归地分解为较简单的步骤。

以上特性使其仍是一种重要的算法,并且用在绘图仪绘图卡中的绘图芯片,以及各种图形程式库。这个算法非常的精简,使它被实作于各种装置的固件,以及绘图芯片的硬件之中。

“Bresenham”至今仍经常作为一整个算法家族的名称,即使家族中绝大部分算法的实际开发者是其他人。该家族的算法继承了Bresenham的基本方法并加以发展,详见参考资料。

演算方法

 
Bresenham直线算法描绘的直线。

假设我们需要由(x0, y0)这一点,绘画一直线至右下角的另一点(x1, y1),x,y分别代表其水平及垂直坐标,并且x1 - x0 > y1 - y0。在此我们使用电脑系统常用的坐标系,即x坐标值沿x轴向右增长,y坐标值沿y轴向下增长。

因此x及y之值分别向右及向下增加,而两点之水平距离为 且垂直距离为 。由此得之,该线的斜率必定介乎于0至1之间。而此算法之目的,就是找出在  之间,第x行相对应的第y列,从而得出一像素点,使得该像素点的位置最接近原本的线。

对于由(x0, y0)及(x1, y1)两点所组成之直线,公式如下:

 

因此,对于每一点的x,其y的值是

 

因为x及y皆为整数,但并非每一点x所对应的y皆为整数,故此没有必要去计算每一点x所对应之y值。反之由于此线之斜率介乎于1至0之间,故此我们只需要找出当x到达那一个数值时,会使y上升1,若x尚未到此值,则y不变。至于如何找出相关的x值,则需依靠斜率。斜率之计算方法为 。由于此值不变,故可于运算前预先计算,减少运算次数。

要实行此算法,我们需计算每一像素点与该线之间的误差。于上述例子中,误差应为每一点x中,其相对的像素点之y值与该线实际之y值的差距。每当x的值增加1,误差的值就会增加m。每当误差的值超出0.5,线就会比较靠近下一个映像点,因此y的值便会加1,且误差减1。

下列伪代码是这算法的简单表达(其中的plot(x,y)绘画该点,abs返回的是绝对值)。虽然用了代价较高的浮点运算,但很容易就可以改用整数运算(详见最佳化一节):

 function line(x0, x1, y0, y1)
     int deltax := x1 - x0
     int deltay := y1 - y0
     real error := 0
     real deltaerr := deltay / deltax    // 假設deltax != 0(非垂直線),
           // 注意:需保留除法運算結果的小數部份
     int y := y0
     for x from x0 to x1
         plot(x,y)
         error := error + deltaerr
         if abs (error) ≥ 0.5 then
             y := y + 1
             error := error - 1.0

一般化

虽然以上的算法只能绘画由左下至右上,且斜率小于或等于1的直线,但我们可以扩展此算法,使之可绘画任何的直线。第一个扩展是绘画反方向,即由右上至左下的直线。这可以简单地透过在x0 > x1时交换起点和终点来做到。第二个扩展是绘画斜率为负的直线。可以检查y0y1是否成立;若该不等式成立,误差超出0.5时y的值改为加-1。最后,我们还需要扩展该算法,使之可以绘画斜率绝对值大于1的直线。要做到这点,我们可以利用大斜率直线对直线y=x反射是一条小斜率直线的事实,在整个计算过程中交换 xy,并一并将plot的参数顺序交换。扩展后的伪代码如下:

 function line(x0, x1, y0, y1)
     boolean steep := abs(y1 - y0) > abs(x1 - x0)
     if steep then
         swap(x0, y0)
         swap(x1, y1)
     if x0 > x1 then
         swap(x0, x1)
         swap(y0, y1)
     int deltax := x1 - x0
     int deltay := abs(y1 - y0)
     real error := 0
     real deltaerr := deltay / deltax
     int ystep
     int y := y0
     if y0 < y1 then ystep := 1 else ystep := -1
     for x from x0 to x1
         if steep then plot(y,x) else plot(x,y)
         error := error + deltaerr
         if error ≥ 0.5 then
             y := y + ystep
             error := error - 1.0

以上的程序可以处理任何的直线,实现了完整的Bresenham直线算法。

最佳化

以上的程序有一个问题:电脑处理浮点运算的速度比较慢,而errordeltaerr的计算是浮点运算。此外,error的值经过多次浮点数加法之后,可能有累积误差。使用整数运算可令算法更快、更准确。只要将所有以上的分数数值乘以deltax,我们就可以用整数来表示它们。唯一的问题是程序中的常数0.5—我们可以透过改变error的初始方法,以及将error的计算由递增改为递减来解决。新的程序如下:

 function line(x0, x1, y0, y1)
     boolean steep := abs(y1 - y0) > abs(x1 - x0)
     if steep then
         swap(x0, y0)
         swap(x1, y1)
     if x0 > x1 then
         swap(x0, x1)
         swap(y0, y1)
     int deltax := x1 - x0
     int deltay := abs(y1 - y0)
     int error := deltax / 2
     int ystep
     int y := y0
     if y0 < y1 then ystep := 1 else ystep := -1
     for x from x0 to x1
         if steep then plot(y,x) else plot(x,y)
         error := error - deltay
         if error < 0 then
             y := y + ystep
             error := error + deltax

历史

Jack E. Bresenham英语Jack E. Bresenham于1962年在IBM发明了此算法。据他本人表示,他于1963年在丹佛举行的美国计算机协会全国大会上发表了该算法,论文则登载于1965年的《IBM系统期刊》(IBM Systems Journal)之中。[1]Bresenham直线算法其后被修改为能够画圆,修改后的算法有时被称为“Bresenham画圆算法”或中点画圆算法

参考资料

  1. ^ Paul E. Black. Dictionary of Algorithms and Data Structures, 美国国家标准与技术研究院. http://www.nist.gov/dads/HTML/bresenham.html页面存档备份,存于互联网档案馆

参阅

  • Patrick-Gilles Maillot's Thesis页面存档备份,存于互联网档案馆) an extension of the Bresenham line drawing algorithm to perform 3D hidden lines removal; also published in MICAD '87 proceedings on CAD/CAM and Computer Graphics, page 591 - 数字微分分析仪算法,描画直线和三角形的一种简单通用方法。
  • 吴小林直线算法,以同样快速的方法绘制反锯齿线。
  • 中点画圆算法,以类似的方法绘画

外部链接