快速绘制直线之Bresenham算法

时间:14-03-26 栏目:单片机, 编程之美 作者:JH单片机 评论:2 点击: 16,303 次


文章目录

LCD12864快速绘制直线——Bresenham算法,百度说名字够长才有意思。Bresenham算法(布兰森汉姆算法)一种较快速绘制直线的算法,在计算机图形学里面为了栅格化直线设计出来的算法,大幅度提升运算速度。所以这种算法可以应用在一些处理能力不太强的单片机上。

前面一段废话存在的意义是为了避免这篇文章被读者误以为是偏题的零分作文。实际废话才刚开始,博客疏于管理,突然写这么一篇文章,有种不知味的感觉。呃...像进了沙的贝壳,奇痒难忍。实质上是不愿放弃自己的兴趣爱好,因为最近阿浩也迷上了摄影。当然,也“恋”上了GUI(Graphical User Interface)图形用户界面,也才有写这篇文章的冲动。

 

一、Bresenham算法原理

Bresenham算法原理,不想大费周章去解释。呃...德尔塔X、西格玛Y、狼他Z,他们都放假了。阿浩不想去用天花乱坠的数学公式去推理,最终演变出改进算法。但这是阿浩之前干过的一件蠢事,有必要了解详细原理公式推导请移步 《LCD画直线之Bresenham算法

简而言之,此算法采用增量式运算,每一列只需要检查一个误差。采用离散的整数增量来代替斜率增量计算,所以算法可以快速绘制出栅格化直线。

这种原理不难理解,只要就算出直线从起点到终点垂直网格线的焦点,确定那一列像素与交点最近的像素点即可。

 

二、算法的实现

下面,阿浩以一个最基本的直线公式y = kx + b作为绘制直线的算法(k是斜率),相信只要学过数学的对这条公式都非常熟悉。

以上这个公式,有3种情况进行分析,当k=0的时候,直线为水平直线;当k=∞ 无穷大的时候,直线是垂直的,还有一种情况就是普通直线了。于是,我们很简单的就可以根据这三种情况分别得到直线的画法。

但如果是采用此类函数画法,估计单片机要疲劳猝死的节奏(夸张修辞手法,单片机也可以跑 k=(y1-y0) /(x1-x0)的)。不过你也可以弄一个高速晶振,也能很快的画出直线来。

当然,Bresenham算法就是为快速而生。下面给出代码,作为分析。

前提假设我们已经完成了void LCD12864_DrawPoint(x,y,color);这样一个函数在LCD12864上画点。

/*---------------------------
函数名:LCD12864_DrawLine
INPUT:坐标1 坐标2 颜色类型
功能: 在(x0,y0)到(x1,y1)之间画一条直线(Bresenham算法)
---------------------------*/
void LCD12864_DrawLine(unsigned char x0,unsigned char y0,unsigned char x1,unsigned char y1,unsigned char Color)
{
	unsigned int t;
	int xerr=0,yerr=0,delta_x,delta_y,distance;
	int incx,incy;
	unsigned int row,col;
	//坐标越界返回
	if( x0>=LCD_X_MAX||x1>=LCD_X_MAX||y0>=LCD_Y_MAX||y1>=LCD_Y_MAX)
		return;

	delta_x = x1-x0;	//计算X坐标增量 Δx=x1-x0
	delta_y = y1-y0;  	//计算Y坐标增量 Δy=y1-y0
	col = x0;			//起始坐标
	row = y0;

	if(delta_x>0)		//设置单步方向,判断递增方向
		incx=1;
	else
	{
		if( delta_x==0)
			incx=0;		//垂直线
		else
		{
			incx=-1;
			delta_x=-delta_x;	//求X增量的绝对值
		}
	}

	if(delta_y>0)
		incy=1;
	else
	{
		if( delta_y==0)
			incy=0;		//水平线
		else
		{
			incy=-1;
			delta_y=-delta_y;	//求Y增量的绝对值
		}
	}

	if(delta_x > delta_y)		//选取最大值增量
		distance=delta_x;		//选取基本增量坐标轴
	else
		distance=delta_y;
	//画线
	for(t=0;t<=distance+1;t++)
	{
		LCD12864_DrawPoint(col,row,Color);	//每单步递增画一个点
		xerr += delta_x;
		yerr += delta_y;
		if(xerr > distance)
		{
			xerr -= distance;
			col += incx;
		}
		if(yerr > distance)
		{
			yerr -= distance;
			row += incy;
		}
	}
}

三、算法优化

这里所说的算法优化并不是说要去优化Bresenham算法,而是画直线这种原理与LCD点阵显示方式之间的优化。说白了就是显示速度上的优化。

没有最好,只有更好。要分析哪些地方可以优化,就是要找出那些冗余的地方。比如当我们想画一条垂直的直线时,对于每一个牵涉到的字节都有可能要重复的操作8次,这种操作不是简单的画线,而是要先读取再计算最后再写这样的复合操作,重复8次只是为了把整个字节变黑显然是一种不可容忍的冗余。所以要重新根据LCD来优化代码,提高绘制速度。

关于Bresenham算法绘制直线心得就到此结束,不难但需要真正动手去实现它,那才有意义。关于这种算法的详细内容,阿浩建议你阅读一些关于计算机图形学方面的书,对你大有裨益。

 

四、效果“显摆”

所谓点动成线,也就是以上所说的Bresenham算法,以打点方式来绘制直线。(当然阿浩也再次强调,打点有时候效率不高,还望优化)。再则,线动成面,绘制的直线,可以根据多少方式来绘制成一个平面,这还有待阿浩做下一回分解。

效果如下:

LCD12864绘制窗体

本文完。
谢谢阅读。

PS:码个文章还停电,还不让活了。

 
关于本文作者

爱数电,爱模电;爱单片机,爱嵌入式;爱EDA,也爱DSP; 爱Altium Designer,也爱PCB;爱生活,同时也爱微博…… 一个自动化专业的学生,与志同道合者学习交流!!!

QQ 号码:594420349
腾讯微博:http://t.qq.com/kevin_753

项目合作