实验报告(Bresenham画线算法)

一、实验目的

根据Bresenham画线算法，掌握绘制直线的程序设计方法。

二、实验原理

    为了说明算法原理，我们首先考虑斜率非负且不超过 1 的直线的光栅化过程。设直线的起点坐标为 (xs , ys)，终点坐标为(xe , ye)，则直线的方程为：

因此，其隐函数表示为：

其中：

显然，对于直线上的点，F(x , y) 等于零；对于直线下方的点，F(x , y) 大于零；而对直线上方的点，F(x,y) 小于零。

假设当前选择的像素点是 (xi , yi)，那么下一步要选择的像素点可能是 NE (xi+1 , yi+1)，也可能是 E (xi+1 , yi)。选择的原则是看哪一个离直线与 x = xi+1 的交点最近。

运用中点法则，我们只需考察中点 M 在直线的哪一侧，即计算：

F(M) = F(xi + 1, yi + 1/2) = a(xi + 1) + b( yi + 0.5) + c

并确定其正负号。由于根据函数值 F(xi+1, yi + 1/2) 进行判定，所以我们定义一个判定函数如下：      di = 2F(xi + 1, yi + 1/2)

根据定义：di = 2a(xi + 1) + 2byi + b + 2c

当 d i < 0 时，M 在直线的上方，取 E 为下一个像素点；当 d > 0时， M 在直线的下方，取 NE 为下一个像素点；当 d = 0时，两者都可以选，我们约定选 E。

    di 的计算需要做 4 次加法和两次乘法。因此，为了有效地计算判定函数，我们需要建立关于 di 的递推公式。显然，di 的变化依赖于下一个像素点选的是 NE 还是 E。

当 di < 0 时，下一个像素点是 E，那么：

di+1= 2F(xi + 2, yi + 1/2) = 2a(xi + 2) + 2byi + b + 2c = di + 2a

当 di > 0 时，下一个像素点是 NE，则：

di+1= 2F(xi + 2, yi + 1 + 1/2) = 2a(xi + 2) + 2b(yi +1)+b+2c

                     = di  + 2a + 2b

由此，得到计算判定函数 di 的递推公式：

    因为直线上的第一个像素点就是直线的起点 (xs, ys)，所以判定函数 di 的初值为：

d0 = 2a(xs + 1) + 2bys + b  + 2c = 2dy - dx

    故满足条件的直线的 Bresnham 算法的步骤如下：

    Step 1.初始化

dx = xe － xs , dy = ye － ys , x = xs , y = ys , d = 2dy －dx；

    Step 2.当 x < xe 时，执行下述操作：

      （1）画像素点 (x, y)；

      （2）求下一个像素点：

x = x + 1；

if (d > 0) then y = y + 1；

      （3）计算判定函数 d：

if (d > 0) then d = d + 2dy － 2dx；

                else  d = d ＋ 2dy；

   Step 3.算法结束。

三、实验程序

#include

#include

#include

#include

#include

void Bresenham_line(int xs,int ys,int xe,int ye,int c)

{

    int dx=abs(xe-xs),dy=abs(ye-ys),i,x=xs,y=ys;

    int twoDX=2*dx,twoDY=2*dy,p=2*dy-dx;

    int s1,s2,interchange=0,temp;

if (xe-xs>=0)

        s1=1;

    else

        s1=-1;

if(ye-ys>=0)

        s2=1;

    else

        s2=-1;

if(dy>dx)

    {

        temp=dx;

        dx=dy;

        dy=temp;

        interchange=1;

    }

for (i=0;i<=dx;i++)

    {

        putpixel(x,y,c);

if(p>0)

        {

            if(interchange)

                x+=s1;

            else

            {

                y+=s2;

                p-=twoDX;

            }

        }

        if(interchange)

            y+=s2;

        else

            x+=s1;

            p+=twoDY;

    }

}

void main()

{ 

    int x1=60,y1=88,x2=345,y2=7,c=GREEN;

    int dx,dy,n,k,f;

    int x,y;

    int gdriver,gmode;

    gdriver=DETECT;

    initgraph(&gdriver,&gmode," ");

    Bresenham_line(x1,y1,x2,y2,c);

    getch();

    closegraph();

}

四、测试结果

x1=60,y1=88,x2=345,y2=7,c=GREEN，则得图如下示：

五、实验总结

本次实验，让我了解到Bresenham算法实现的具体过程，对此算法生成线的过程和特点也有了进一步的了解。Bresenham算法生成直线的速度很快，由于光栅化的影响，直线的亮度明显不均匀。