|
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 ;
} |
|
|