请选择 进入手机版 | 继续访问电脑版

硬汉嵌入式论坛

 找回密码
 立即注册
查看: 8299|回复: 7
收起左侧

[客户分享] 安富莱TFT例程中采用的画线算法-Bresenham画线算法

[复制链接]

38

主题

136

回帖

40

积分

初级会员

积分
40
发表于 2014-7-29 11:42:28 | 显示全部楼层 |阅读模式
Bresenham算法的优点是:
1、不必计算直线之斜率,因此不做除法;
2、不用浮点数,只用整数;
3、只做整数加减法和乘2运算,而乘2运算可以用硬件移位实现。

Bresenham算法速度很快,并适于用硬件实现。


基本上Bresenham画线算法的思路如下:


// 假设该线段位于第一象限内且斜率大于0小于1,设起点为(x1,y1),终点为(x2,y2).
// 根据对称性,可推导至全象限内的线段.
1.画起点(x1,y1).
2.准备画下个点。x坐标增1,判断如果达到终点,则完成。否则,由图中可知,下个要画的点要么为当前点的右邻接点,要么是当前点的右上邻接点.
2.1.如果线段ax+by+c=0与x=x1+1的交点的y坐标大于M点的y坐标的话,下个点为U(x1+1,y1+1)
2.2.否则,下个点为B(x1+1,y1+1)
3.画点(U或者B).
4.跳回第2步.
5.结束.





这里需要细化的是怎么判断下个要画的点为当前点的右邻接点还是当前点的右上邻接点.
设线段方程:ax+by+c=0(x1<x<x2,y1<y<y2)
令dx=x2-x1,dy=y2-y1
则:斜率-a/b = dy/dx.
从第一个点开始,我们有F(x,1,y1) = a*x1+b*y1+c=0
下面求线段ax+by+c=0与x=x1+1的交点:
由a*(x1+1)+b*y+c = 0, 求出交点坐标y=(-c-a(x1+1))/b
所以交点与M的y坐标差值Sub1 = (-c-a(x1+1))/b - (y1+0.5) = -a/b-0.5,即Sub1的处始值为-a/b-0.5。
则可得条件当 Sub1 = -a/b-0.5>0时候,即下个点为U.
反之,下个点为B.
代入a/b,则Sub1 = dy/dx-0.5.
因为是个循环中都要判断Sub,所以得求出循环下的Sub表达式,我们可以求出Sub的差值的表达式.下面求x=x1+2时的Sub,即Sub2
1.如果下下个点是下个点的右上邻接点,则
Sub2 = (-c-a(x1+2))/b - (y1+1.5) = -2a/b - 1.5
故Sub差值Dsub = Sub2 - Sub1 = -2a/b - 1.5 - (-a/b-0.5) = -a/b - 1.代入a/b得Dsub = dy/dx -1;
2.如果下下个点是下个点的右邻接点,
Sub2 = (-c-a(x1+2))/b - (y1+0.5) = -2a/b - 0.5
故Sub差值Dsub = Sub2 - Sub1 = -2a/b - 0.5 - (-a/b-0.5) = -a/b. 代入a/b得Dsub = dy/dx;
于是,我们有了Sub的处始值Sub1 = -a/b-0.5 = dy/dx-0.5,又有了Sub的差值的表达式Dsub = dy/dx -1 (当Sub1 > 0)或 dy/dx(当Sub1 < 0).细化工作完成。


于是pcode可以细化如下:
// Pcode for Bresenham Line
// By SoRoMan
x=x1;
y=y1;
dx = x2-x1;
dy = y2-y1;
Sub = dy/dx-0.5; // 赋初值,下个要画的点与中点的差值
DrawPixel(x, y); // 画起点
while(x<x2)
{
x++;
if(Sub > 0) // 下个要画的点为当前点的右上邻接点
{
  Sub += dy/dx - 1; //下下个要画的点与中点的差值
  y++; // 右上邻接点y需增1
}
else// 下个要画的点为当前点的右邻接点
{
  Sub += dy/dx;  
}
// 画下个点
DrawPixel(x,y);
}

PS:一般优化:
为避免小数转整数以及除法运算,由于Sub只是用来进行正负判断,所以可以令Sub = 2*dx*Sub = 2dy-dx,则
相应的DSub = 2dy - 2dx或2dy.
思考1:如果Sub = 0时,会产生取两个点都可以的问题。这个问题还没深入。


一. 实验目标:用Bresenham算法绘画直线。
二. 算法描述:
设:p1=2dy-dx
    综述上面的推导,第1a象限内的直线Bresenham算法思想如下:
1、画起点(x1,y1), dx=x2-x1,dy=y2-y1,计算误差初值
      p1=2dy-dx;         i=1;
2、求直线的下一点位置: x(i+1)=x(i+1);
      if  p(i)>0 则y(i+1)=y(i+1);否则y(i+1)= y(i);
3、画点(x(i+1),y(i+1));
4、求下一个误差p(i+1);
   if p(i)>0   则   p(i+1)= p(i)+2dy-2dx;
            否则  p(i+1)=p(i)+2dy;
5、i=i+1;  if i<dx+1则转2;
否则end
Bresenham算法的优点是:
1、不必计算直线之斜率,因此不做除法;
2、不用浮点数,只用整数;
3、只做整数加减法和乘2运算,而乘2运算可以用硬件移位实现。
   Bresenham算法速度很快,并适于用硬件实现。
三.  程序源码:
int BresenhamLine ( int x1 , int y1 , int x2 , int y2 , int c)
{
int dx , dy ;
int tx , ty ;
int inc1 , inc2 ;
int d , iTag ;
int x , y ;
putpixel ( x1 , y1 , c ) ;
if ( x1 == x2 && y1 == y2 )  /*如果两点重合,结束后面的动作。*/
  return 1 ;
iTag = 0 ;
dx = abs ( x2 - x1 );
dy = abs ( y2 - y1 );
if ( dx < dy )   /*如果dy为计长方向,则交换纵横坐标。*/
{
  iTag = 1 ;
  Swap ( & x1 , & y1 );
  Swap ( & x2 , & y2 );
  Swap ( & dx , & dy );
}
tx = ( x2 - x1 ) > 0 ? 1 : -1 ;    /*确定是增1还是减1*/
ty = ( y2 - y1 ) > 0 ? 1 : -1 ;
x = x1 ;
y = y1 ;
inc1 = 2 * dy ;
inc2 = 2 * ( dy - dx );
d = inc1 - dx ;
while ( x != x2 )     /*循环画点*/
{
  if ( d < 0 )
   d += inc1 ;
  else
  {
   y += ty ;
   d += inc2 ;
  }
  if ( iTag )
   putpixel ( y , x , c ) ;
  else
   putpixel ( x , y , c ) ;
  x += tx ;
}
return 0;
}
Swap ( int * a , int * b )   /*交换*/
{
int tmp ;
tmp = * a ;
* a = * b ;
* b = tmp ;
}
回复

使用道具 举报

18

主题

321

回帖

375

积分

高级会员

积分
375
发表于 2019-4-10 15:47:11 | 显示全部楼层
本帖最后由 王海靖 于 2019-4-10 15:48 编辑

假设给定的参数为 LCDH7_DrawLine( 100 , 100 ,200,200 , 黑色)
void LCDH7_DrawLine(uint16_t _usX1 , uint16_t _usY1 , uint16_t _usX2 , uint16_t _usY2 , uint16_t _usColor)
{
        int32_t dx , dy ;
        int32_t tx , ty ;
        int32_t inc1 , inc2 ;
        int32_t d , iTag ;
        int32_t x , y ;

        LCDH7_PutPixel(_usX1 , _usY1 , _usColor); //在(100.100)的位置画了一个点

        if ( _usX1 == _usX2 && _usY1 == _usY2 )
        {
                return;
        }

        iTag = 0 ;
        /* dx = abs ( _usX2 - _usX1 ); */
        if (_usX2 >= _usX1)           //200>100
        {
                dx = _usX2 - _usX1; //dx=200-100=100
        }
        else
        {
                dx = _usX1 - _usX2;
        }

        /* dy = abs ( _usY2 - _usY1 ); */
        if (_usY2 >= _usY1)         //200>100
        {
                dy = _usY2 - _usY1;//dy=200-100=100
        }
        else
        {
                dy = _usY1 - _usY2;
        }

        if ( dx < dy )  //100=100,不成立
        {
                uint16_t temp;

                iTag = 1 ;
                temp = _usX1; _usX1 = _usY1; _usY1 = temp;
                temp = _usX2; _usX2 = _usY2; _usY2 = temp;
                temp = dx; dx = dy; dy = temp;
        }
        tx = _usX2 > _usX1 ? 1 : -1 ;   //200>100 tx=1
        ty = _usY2 > _usY1 ? 1 : -1 ;  //200>100  ty=1
        x = _usX1 ;                            //x=100
        y = _usY1 ;                            //y=100
        inc1 = 2 * dy ;                       //inc1=2*100=200
        inc2 = 2 * ( dy - dx );             //inc2=2*(100-100)=0
        d = inc1 - dx ;                       // d=200-100=100
        while ( x != _usX2 )               //x=100
        {     
                if ( d < 0 )
                {
                        d += inc1 ;
                }
                else
                {
                        y += ty ;            //y=y+ty=100+1=101
                        d += inc2 ;         //d=d+inc2=100+0=100
                }
                if ( iTag )                   //iatg=0
                {
                        LCDH7_PutPixel ( y , x , _usColor) ;
                }
                else
                {
                        LCDH7_PutPixel ( x , y , _usColor) ; //画点(100,101)
                }
                x += tx ;                                              //x=x+tx=100+1=101
        }        
}
x += tx  是不是应该放在  LCDH7_PutPixel ( x , y , _usColor) 的前面 @eric2013


回复

使用道具 举报

18

主题

321

回帖

375

积分

高级会员

积分
375
发表于 2019-4-10 16:07:27 | 显示全部楼层
按照上述算法,最终的一个点的位置是(199,200)
回复

使用道具 举报

1万

主题

6万

回帖

10万

积分

管理员

Rank: 9Rank: 9Rank: 9

积分
105917
QQ
发表于 2019-4-10 16:08:49 | 显示全部楼层
王海靖 发表于 2019-4-10 15:47
假设给定的参数为  LCDH7_DrawLine( 100 , 100 ,200,200 , 黑色)
void LCDH7_DrawLine(uint16_t _usX1 , u ...

谢谢,回头我测测。
回复

使用道具 举报

3

主题

75

回帖

84

积分

初级会员

积分
84
发表于 2021-12-18 20:51:47 | 显示全部楼层
老大,开头也不对。
line.png
回复

使用道具 举报

1万

主题

6万

回帖

10万

积分

管理员

Rank: 9Rank: 9Rank: 9

积分
105917
QQ
发表于 2021-12-18 21:09:09 | 显示全部楼层
gjeoi 发表于 2021-12-18 20:51
老大,开头也不对。

开发不对,不正常啊,因为第1个点,程序一上来就打印了一次

单步调试看下的程序,应该是你printf打印位置的问题。

末尾的点按照二楼坛友的修改就可以了

QQ截图20211218210906.png


回复

使用道具 举报

3

主题

75

回帖

84

积分

初级会员

积分
84
发表于 2021-12-18 21:23:09 | 显示全部楼层
看漏了开头,开头是正常的
回复

使用道具 举报

1万

主题

6万

回帖

10万

积分

管理员

Rank: 9Rank: 9Rank: 9

积分
105917
QQ
发表于 2021-12-19 08:11:26 | 显示全部楼层
gjeoi 发表于 2021-12-18 21:23
看漏了开头,开头是正常的

是的,printf打印的话,容易忽视这个地方。
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

QQ|小黑屋|Archiver|手机版|硬汉嵌入式论坛

GMT+8, 2024-3-29 02:30 , Processed in 0.179780 second(s), 28 queries .

Powered by Discuz! X3.4 Licensed

Copyright © 2001-2023, Tencent Cloud.

快速回复 返回顶部 返回列表