Bresenham画线算法

kenson · 发表于 2010-6-2 20:05

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 ;

}

kenny1234 · 发表于 2010-6-5 11:20

正在找一些繪圖的方法，謝謝!!

kenson · 发表于 2012-4-1 12:48

下面是Bresenham画线算法分别用C语言和verilog 分别实现，这是我做的LCD控制器里硬件加速的一个模块,其它如画圆，字符，填充等可以以此类推

Bresenham画线算法 C程序如下：
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 )

{

  iTag = 1 ;

  Swap ( & x1 , & y1 );

  Swap ( & x2 , & y2 );

  Swap ( & dx , & dy );

}

tx = ( x2 - x1 ) > 0 ? 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 ;

}

FPGA实现如下verilog HDL :
module line
(
input[31 :0] page_address,

input clk_i,
input rstn_i,
input load_i,

input ack_i,
input signed  [15:0] sx,
input signed  [15:0] sy,
input signed  [15:0] ex,
input signed  [15:0] ey,
input[23:0] f_color_i,
input[23:0] b_color_i,
input[7 :0] data_i,

output[23 :0] data_o,
output[23 :0] addr_o,
output       pset_start_o,
output reg line_over_o
);
reg[23: 0]  addr;
reg[7 :0] rdata_i;
reg signed [15:0] x;
reg signed [15:0] y;
reg signed [15  :0] xsign;
reg signed [15  :0] ysign;

reg signed [16  :0] delta_x;
reg signed [16  :0] delta_y;
reg [16  :0] rdelta_x;
reg [16  :0] rdelta_y;
reg signed [16  :0] i;
reg signed [16  :0] e;
reg  change;
reg [3:0]state;
reg pset_load;
wire  over_o;

// Declare states
parameter S0 = 0, S1 = 1, S2 = 2, S3 = 3,S4 = 4, S5 = 5,S6 =6, S7=7,S40 = 8;
// Determine the next state synchronously, based on the
// current state and the input
always @ (posedge clk_i or negedge rstn_i) begin
  if (! rstn_i)
begin
   line_over_o <= 1'b0;
   rdata_i <= 8'd0;

   addr <= 24'd0;
         xsign <= 16'd0;
         ysign <= 16'd0;
         delta_x <= 17'd0;
         delta_y <= 17'd0;
         i    <= 17'd0;
         e    <= 17'd0;

         pset_load <= 1'b0;
state <= S0;
end

  else
case (state)
S0:
   if(load_i)
   begin
   line_over_o <= 1'b1;


   x    <= sx;
   y    <= sy;
   delta_x <= ex - sx;
   delta_y <= ey - sy;
   state <= S1;
   end
   else
      begin
   line_over_o <= 1'b0;
   state <= S0;
   end

S1:
   begin

   if(delta_x < 0 ) begin rdelta_x <= (~ delta_x )+ 1'b1; xsign<= -1; end
   else          begin rdelta_x <=  delta_x ;       xsign <= 1;  end

   if(delta_y < 0 ) begin rdelta_y <= (~ delta_y )+ 1'b1; ysign <= -1; end
   else          begin rdelta_y <=  delta_y ;       ysign <= 1;  end

   state <= S2;

   end
S2:
   begin
               if(rdelta_x < rdelta_y)
               begin
      delta_x <= rdelta_y;
      delta_y <= rdelta_x;

      change  <= 1'b1;
      end
   else
   begin
      delta_x <= rdelta_x;
      delta_y <= rdelta_y;
      change  <= 1'b0;
   end
   state <= S3;
   end
S3:
   begin
   e       <= ( delta_y * 2 ) - delta_x;
   i       <= 17'd1;
      rdata_i  <= data_i;
   state <= S4;
   end
S4:
   begin
   addr    <=( ( y * 1024 ) + x ) + page_address[23 :0];
   pset_load <= 1'b1;
   state    <= S40;
   end
S40:
   begin
   if(over_o == 1'b1 )
   begin
      pset_load <= 1'b0;
      state <= S5;
   end

   else

      state <= S40;

   end
S5:
   begin
   if( e >= 0 )
   begin
      if(change == 1'b1) x <= x + xsign;
      else             y <= y + ysign;
      e <= e + ( delta_x * 2);
      state <= S5;
   end
   else

      state <= S6;
   end

S6:
   begin
   if( change == 1'b1) y <= y + ysign;
   else                x <= x + xsign;
   e <= e + ( delta_y * 2);
   state <= S7;
   end

S7:
   begin
   if(i < delta_x )
   begin
      i    <= i + 1'b1;
      state <= S4;
   end

   else

   begin
      line_over_o <= 1'b0;
      state <= S0;
   end
   end

endcase
end

endmodule

		自动登录	找回密码
密码			请使用微信账号登录和注册会员