浏览量:2,235

布雷森汉姆直线算法

本篇文章,主要介绍布雷森汉姆直线算法,包括一个用glut实现的demo。代码的下载地址为:https://github.com/twinklingstar20/twinklingstar_cn_demo_bresenham-line-algorithm

一.             布雷森汉姆(Bresenham)算法说明

2013-11-12 12-56-53

图1. 在显示器上绘制直线

如图1所示,在显示器上绘制一条直线,直线上一些像素会被启动,由此形成一条直线效果。直线绘制算法是图形学中的一个基本的算法,绘制直线时需要考虑哪些像素需要被启动,这里介绍布雷森汉姆直线绘制算法。它是一种基本的递增算法,基于前一个像素信息就可以计算出下一个像素值,能确定一条直线上哪些像素要启动,而且它的计算只采用整数值,避免了浮点运算运算。

布雷森汉姆算法有几种变种,这里考虑其中的一个中点算法。假设现在要绘制两个端点是(ax,ay)和(bx,by)之间的线段,需要确定介于它们之间的像素序列。为了简化讨论,这里考虑一种特殊的情况,即ax<bx,直线斜率0<k<1的情况。线段的宽是W=bx-ax,高是H=by-ay,则有W>H,所有穿过两个端点的直线都满足下面的一个等式:

-W(y-ay)+H(x-ax)=0

定义一个函数如下所示:

F(x,y) = -2W(y-ay)+2H(x-ax)

如果F(x,y)>0,则说明(x,y)位于直线下;如果F(x,y)<0,则说明(x,y)位于直线上。

2013-11-12 12-57-12

图2. 中点算法的一个参数

图中所示,假设从黑色点(Px,Py)处开始考虑算法,现在考虑在Px+1的位置上,Y方向上最合适的值是Py +1还是Py,即U(Px+1, Py+1)还是L(Px +1,Py)。接着是要判断Q点更靠近U还是L,可以通过计算中间值M(Px+1,Py+1/2),可以使用上面所说的等式,如果F(Mx,My)<0,则点M在直线上,选择L点;如果F(Mx,My)>0,则点M在直线下,选择U点,Y方向上加1。

F(Mx,My)=-2W(Py+1/2-ay) + 2H(Px+1-ax)

接下来,当X方向上的值是Px+2时,判断现在的M取值是M’还是M’’。如果前面一步选择的是L点,则取M’(Px+2,Py+1/2);相反,如果前一步选择的是U点,则取M’’ (Px+2,Py+3/2)。    所以分下面两种情况讨论:

1)  如果前一步F的值是负的,则有Fnext=F(Px+2,Py+1/2)=-2W(Py+1/2-ay) + 2H(Px+2-ax) = F(Mx,My)+2H
2)  如果前一步F的值是正的,则有 Fnext=F(Px+2,Py+3/2)=-2W(Py+3/2-ay) + 2H(Px+2-ax) = F(Mx,My)+2(H-W)

初始情况下M=(ax+1,ay+1/2),则有F(x,y)=-2W(ay+1/2-ay)+2H(ax+1-ax)=2H-W,如果这里没有乘以2的话,就会有浮点数存在了。总结下算法流程就是:

1)  初始化F=2H-W,x=ax,y=ay
2)  将(x,y)的值设置为某种颜色
3)  x += 1
4)  如果F<0,F+=2H;否则,y+=1,F+=-2(W-H)

上述情况指的是特殊情况,接下来讨论一般的情况:

1. ax>bx,W>H的情况

最好别采用将两个端点交换的方法,因为这会产生两个问题:1)多边形绘制时,该方法会消除线段的顺序;2)  在绘制虚线时,错语的绘制顺序,画出的效果也不同。

线段的宽用W’=bx-ax,高是H’=by-ay,采用与上面类似的方法计算,则可以得到下面几个等式。如果两个端点只是绘制顺序颠倒,则有H=-H’,W=-W’。

F(Mx,My)=F(Px-1,Py-1/2)=-2W’(Py-1/2-ay) + 2H’(Px-1-ax)
F(Px-2,Py-1/2)=-2W’(Py-1/2-ay) + 2H’(Px-2-ax)=F(Mx,My)-2H’
F(Px-2,Py-3/2)=-2W’(Py-3/2-ay) + 2H’(Px-2-ax)=F(Mx,My)- 2(H’-W’)

         则ax>bx,W>H>0与ax<bx,W>H>0两种情况可以总结如下:

                   1)如果上一步F值是负的,则有Fnext=F(Mx,My)+2|H| 
                   2)如果上一步F值是正的,则有 Fnext=F(Mx,My)+2|(H-W)|            (结论1)

2. 对于|W|>=|H|的情况,即斜率-1<=k<1的情况,按照上面类似的方法推导,这里就不一一说明,最终也能得到结论(1)。

3. 对于|W|<|H|的情况,即斜率k<-1或者k>1的情况,这时候如果将X坐标轴与Y坐标轴颠倒,这样就可以推出与上面相同的结论,只是原先是X,现在换成了Y。

二.             算法实现

这里用glut库,实现了Bresenham算法,如下面的代码片段所示。代码中,使用到了一些读取像素的操作,参见《像素相关的操作》有详细的介绍。Demo的演示如图3所示,在窗口中点击鼠标左键,不放开鼠标,移到到窗口中的另一个位置,可以绘制直线;键盘上的’U’和’L’,分别提高每个格子占的像素数目,更好的观察算法。

void bresenhamLine(int x1,int y1,int x2,int y2,DWORD color)
{
	int w = x2 - x1;
	int h = y2 - y1;
	int dx = ((w>0)<<1) - 1;
	int dy = ((h>0)<<1) - 1;
	w = abs(w);
	h = abs(h);
	int f , y , x, delta1,delta2;
	if( w > h )
	{
		f = 2*h - w;
		delta1 = 2*h;
		delta2 = (h-w)*2;
		for( x = x1 , y = y1 ; x!=x2 ; x += dx )
		{
			setPixel(x,y,color);
			if( f < 0 )
			{
				f += delta1;
			}
			else
			{
				y += dy;
				f += delta2;
			}
		}
		setPixel(x, y,color);
	}
	else
	{
		f = 2*w - h;
		delta1 = w*2;
		delta2 = (w-h)*2;
		for( x = x1 , y = y1 ; y!=y2 ; y += dy )
		{
			setPixel(x,y,color);
			if( f < 0 )
			{
				f += delta1;
			}
			else
			{
				x += dx;
				f += delta2;
			}
		}
		setPixel(x, y,color);
	}
}

2013-11-12 12-58-22

图3 Demo演示图

三.  参考

1 Computer Graphics using OpenGL, Second Edition

spacer

One comment on “布雷森汉姆直线算法

  1. Anonymous

    楼主, opencv里fillpoly的边缘就是按照这个方法来取整的吗

Leave a reply to Anonymous Cancel reply