北京联合大学应用文理学院

实验报告

课程名称       计算机图形学                                  

实验（实训）名称      直线的扫描转换                        

班级  信息与计算科学 2009级   姓名 袁明     学号 2009010301040        

同组者                                                      

实验（实训）日期                   完成日期               

本实验（实训）所用学时统计

预习        实验（实训）          报告          总计           

评阅意见：                                      成绩          

北京联合大学应用文理学院

实验报告

一、    实验目的

1、掌握用数值微分法进行直线的扫描转换；

2、掌握用中点画线法进行直线的扫描转换；

3、掌握用Bresenham画线法进行直线的扫描转换；

4、学会在C语言环境下图形显示模式的设置。

二、    算法原理介绍

1、数值微分法: DDA（Digital Differential Analyzer）画线算法也称数值微分法，是一种增量算法。它的算法实质是用数值方法解微分方程，通过同时对x和y各增加一个小增量，计算下一步的x、y值。

已知一条直线段L（P0, P1）,其端点坐标为：P0 (x0, y0), P1(x1, y1)。可计算出直线的斜率k为：

k=y1-y0/x1-x0

考虑当x从xiàxi+1时y的变化规律：

  设Dx=xi+1- xi

   xi+1= xi+ Dx

计算yi+1= kxi+1+b= k    (xi+ Dx) +b                     

       = kxi+b+kDx

       = yi+kDx                            

当Dx =1; yi+1 = yi+k

假定端点坐标均为整数，取直线起点P0 (x0, y0)作为初始坐标。画线过程从x的左端点x0开始，向x右端点步进，每步x递增1，y递增k（即直线斜率）；取像素点（x，round（y））作为当前点的坐标。

注意上述分析的算法仅适用于|k| ≤1的情形。在这种情况下，x每增加1,y最多增加1。

当 |k| >1时，必须把x，y地位互换

增量算法：在一个迭代算法中，如果每一步的x、 y值是用前一步的值加上一个增量来获得，则称为增量算法。

 2、中点画线法：

假设x坐标为xp的各像素点中，与直线最近者已确定，为P（xp,yp），那么，下一个与直线最近的像素只能是正右方的P1(xp+1,yp)，或右上方的P2（xp+1,yp+1）两者之一。令M为P1和P2的中点，易知M的坐标为（xp+1,yp+0.5）。

      设Q是理想直线与垂直线x=xp+1

的交点。显然，若M在Q的下方，则P2

离直线近，应取为下一个像素；否则应

取P1。

令a=y0-y1，b=x1-x0，c=x0y1-x1y0。

构造判别式：

     d=a(xp+1)+b(yp+0.5)+c

    d的初始值d0 = a+0.5b

在d≥0的情况下，取正右方像素P1，

    d1=a(xp+2)+b(yp+0.5)+c =d+a

在d<0的情况下，取右上方像素P2，

    d2=a(xp+2)+b(yp+1.5) = d+a+b

         由于我们使用的只是d的符号，而且d的增量都是整数，只是其初始值包含小数。因此，我们可以用2d代替d，来摆脱小数。

         如果进一步把算法中2*a改为a+a等等，那么这个算法不仅只包含整数变量，而且不包含乘除法，适合硬件实现。

3、Bresenham画线算法

过各行各列像素中心构造一组虚拟网格线，按直线从起点到终点的顺序计算直线与各垂直网格线的交点，然后确定该列像素中与此交点最近的像素。

     由图不难看出：若s<t，

则Si比较靠近理想直线，应

选Si;若s≥t，则Ti比较靠近

理想直线，应选Ti。

令dx=x2-x1，dy=y2-y1

递推公式 ：

di的初值： d1=2dy-dx          

当di≥0时，选Ti，

           di+1 =di+2(dy-dx)

当di<0时，选Si，

           di+1=di+2dy

      由于只包含加、减法和左移（乘2）的运算，而且下一个像素点的选择只需检查di的符号，因此Bresenham画线算法很简单，速度也相当快。 

三、    程序源代码

1、数值微分法:

#include"graphics.h"

#include"math.h"

#include"conio.h"

main()

{

void DDALine(int,int,int,int,int);

int gdriver,gmode;

gdriver=DETECT;

initgraph(&gdriver,&gmode,"c:\\tc3.0\\BGI");

DDALine(200,200,500,400,YELLOW);

getch();

closegraph();

return(0);

}

void DDALine(int x0,int y0,int x1,int y1,int color)

{

int x;

float dx,dy,k,y;

dx=x1-x0;

dy=y1-y0;

k=dy/dx;

y=y0;

for (x=x0;x<=x1;x++)

{

putpixel(x,(int)(y+0.5),color);

y=y+k;

}

}

2、中点画线法：

#include"graphics.h"

#include"math.h"

#include"conio.h"

main()

{

void MidpointLine(int,int,int,int,int);

int gdriver,gmode;

gdriver=DETECT;

initgraph(&gdriver,&gmode,"c:\\tc3.0\\BGI");

MidpointLine(200,200,500,400,YELLOW);

getch();

closegraph();

return(0);

}

void MidpointLine(int x0,int y0,int x1,int y1,int color)

{

int a,b,delta1,delta2,d,x,y;

a=y0-y1;

b=x1-x0;

d=2*a+b;

delta1=2*a;

delta2=2*(a+b);

x=x0;

y=y0;

putpixel(x,y,color);

while(x<x1)

{

if(d<0)

{x++;y++;d+=delta2;

}

else

{x++;d+=delta1;

}

putpixel(x,y,color);

}

}

3、Bresenham画线算法

#include"graphics.h"

#include"math.h"

#include"conio.h"

main()

{

void Integer_Bresenham_Line(int,int,int,int,int);

int gdriver,gmode;

gdriver=DETECT;

initgraph(&gdriver,&gmode,"c:\\tc3.0\\BGI");

Integer_Bresenham_Line(200,200,500,400,YELLOW);

getch();

closegraph();

return(0);

}

void Integer_Bresenham_Line(int x0,int y0,int x1,int y1,int color)

{

int x,y,dx,dy,e,i;

dx=x1-x0;

dy=y1-y0;

e=-dx;x=x0;y=y0;

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

{

   putpixel(x,y,color);

   x=x+1;

   e=e+2*dy;

   if(e>=0)

   {

       y=y+1;

       e=e-2*dx;

   }

}

}

四、       总结与体会

（包括：对实验内容的掌握和理解情况；通过实验过程的收获与体会；经验和教训）

五、       参考文献

（算法来源，以及编程方面使用的参考资料）

 

第二篇：计算机图形学实验报告-实验1直线段扫描转换

计算机图形学

实验报告

班级  计算机工硕班

学号  2011220456  

姓名  王泽晶      

实验一:直线段扫描转换

实验目的

通过本次试验，学生可以掌握直线段的扫描转换算法及其程序设计方法。

实验内容

1.       绘制20*20的网格线，格子X和Y方向间隔均为20像素，网格起始坐标在(20,20)。我们使用此网格模拟像素矩阵（），格子交叉点是像素中心。

2.       输入直线段两端点，可使用以下两种方法之一：

a)         对话框输入

b)         鼠标在网格内以鼠标左键按下-拖动-抬起方式输入。注意：直线段两端点要自动取整到模拟的像素中心位置

3.       进行直线段扫描转换，通过点击鼠标右键调用方式或者菜单调用的方式执行。计算完成后，将扫描转换结果，在模拟的像素矩阵中，使用圆形显示出来。

方法一：直线的中点算法

算法的主要思想：

讨论斜率k∈[1,+∞)上的直线段的中点算法。

   对直线，左下方的端点为（x0，y0），右上方的端点为（x1，y1）。直线段的方程为：

   

             

   现在假定已求得像素（），则如图得

                  

由于直线的斜率k∈[1,+∞)，故m=1/k∈(0,1],则

                

在直线上，区间内存在两个像素NE和E。根据取整原则，当在中点M右方时，取像素NE，否则取像素E，即

       

若取，则上式变为

       

计算的递推公式如下：

      

           =

算法的初始条件为：

        

相应的程序示例：

publicfunction drawLine(pixelDrawer:Function, x0:int,y0:int,x1:int,y1:int):void

{

   

    var dx:Number = x1 - x0;

    var dy:Number = y1 - y0;

    var x:Number;

    var y:Number;

    if ((dx == 0) && (dy == 0) )

    {

        // 两点重合时，直接绘制重合的点

        pixelDrawer( x0, y0 );

        return;

    }

    elseif ( dx==0 )

    {

        // 第二点落在X轴上，直接绘制直线上的点

        var step:Number = dy / Math.abs(dy);

        for (y=y0; y!=y1; y+=step )

            pixelDrawer( x0, y );

    }

    elseif ( dy==0 )

    {

        // 第二点落在Y轴上，直接绘制直线上的点

        step = dx / Math.abs(dx);

        for (x=x0; x!=x1; x+=step )

            pixelDrawer( x, y0 );

    }

   

    var stepX:Number = dx / Math.abs(dx);

    var stepY:Number = dy / Math.abs(dy);

    x = x0, y = y0;

    pixelDrawer( x, y );  // 绘制起点

   

    var k:Number = dy / dx;

    if ( Math.abs(k)<1.0 )  // 斜率<1的情形，以X为自变量递增

    {

        var a:Number = -Math.abs(dy);

        var b:Number = Math.abs(dx);

        var d:Number = 2 * a + b;

        var d1:Number = 2 * a;

        var d2:Number = 2 * (a + b);

        while ( x!=x1 )

        {

            if ( d<0 ) { x += stepX; y += stepY; d += d2; }

            else { x += stepX; d += d1; }

            pixelDrawer( x, y );

        }

    }

    else  // 斜率>=1的情形，以Y为自变量递增

    {

        a = -Math.abs(dx);

        b = Math.abs(dy);

        d = 2 * a + b, d1 = 2 * a, d2 = 2 * (a + b);

        while ( y!=y1 )

        {

            if ( d<0 ) { x += stepX; y += stepY; d += d2; }

            else { y += stepY; d += d1; }

            pixelDrawer( x, y );

        }

    }

    pixelDrawer( x1, y1 );  // 绘制终点

   

}

编译运行程序得到如下结果：

方法二：直线的数值微分法

算法的主要思想：

   由于课本上已经给出了斜率m∈[-1,1]上的算法，故此处给出斜率m∈[1，+∞〕上的算法，m∈(-∞,-1]上的可同理推导。

   已知待扫描转换的直线为(x0,y0)，，又，则设k=1/m=（即k∈(0,1]）。直线方程为，即。

   以一个像素为单位分割区间[y0，y1]，由x0<x1，故y0<y1，得到[y0，y1]上的一个划分：,,…. ，其中=+1，得到点列，由公式

      

故从直接得到。可能为浮点数，要对它取整，实际得到像素集。初值为：（）=（x0，y0）。

实验内容：

编写自定义的算法类，程序：

publicfunction drawLine(pixelDrawer:Function,  x0:int,y0:int,x1:int,y1:int):void

{

    var dx:int = x1 - x0

    var dy:int = y1 - y0;

    if ( (dx == 0) && (dy == 0) )

    {

        // 两点重合时，直接绘制重合的点

        pixelDrawer(x0, y0 );

        return;

    }

    elseif ( dx == 0 )

    {

        // 第二点落在X轴上，直接绘制直线上的点

        var step:int = dy / Math.abs(dy);

        for ( var y:int=y0; y!=y1; y+=step )

            pixelDrawer( x0, y );

    }

    elseif ( dy == 0 )

    {

        // 第二点落在Y轴上，直接绘制直线上的点

        step = dx / Math.abs(dx);

        for ( var x:int=x0; x!=x1; x+=step )

            pixelDrawer( x, y0 );

    }

    else

    {

        var k:Number = dy / dx;

        if ( Math.abs(k)<1 )  // 斜率<1的情形，以X为自变量递增

        {

            var y2 : Number = 0.0;

            y2= y0;

            step = dx / Math.abs(dx);

            for ( x=x0; x!=x1; x+=step )

            {

                pixelDrawer( x, int(y2 + 0.5) );

                y2 = y2 + k * step;

            }

        }

        else  // 斜率>=1的情形，以Y为自变量递增

        {

            var x2 : Number = 0.0;

            var kInv:Number = 1.0 / k;

            x2 = x0;

            step = dy / Math.abs(dy);

            for (y=y0; y!=y1; y+=step )

            {

                pixelDrawer( int(x2 + 0.5), y );

                x2 = x2 + kInv * step;

            }

        }

    }

    pixelDrawer( x1, y1 );  // 绘制终点

}

编译运行程序得到如图所示结果：                                                                

方法三：生成直线段的Bresenham算法

与中点算法类似，Bresenham算法也是通过在每列像素中确定与理想直线最近的像素来进行直线扫描转换的。为了讨论方便，此处假定直线的斜率在0，1之间。

对直线对直线，左下方的端点为（x0，y0），右上方的端点为（x1，y1）。如图，由到，则d=d+m，一旦d 1时，d=d-1，以保证d始终在0，1之间。

初始条件为：

 

编写成员函数如下：

publicfunction drawLine(pixelDrawer:Function, x0:int,y0:int,x1:int,y1:int):void

{

   

    var dx:Number = x1 - x0;

    var dy:Number = y1 - y0;

   

    var step:Number;

    var x:Number;

    var y:Number;

   

    if ( (dx ==0) && (dy ==0) )

    {

        // 两点重合时，直接绘制重合的点

        pixelDrawer( x0, y0 );

        return;

    }

    elseif ( (dx ==0) )

    {

        // 第二点落在X轴上，直接绘制直线上的点

        step = dy / Math.abs(dy);

        for (y=y0; y!=y1; y+=step )

            pixelDrawer( x0, y );

    }

    elseif ( (dy ==0) )

    {

        // 第二点落在Y轴上，直接绘制直线上的点

        step = dx / Math.abs(dx);

        for (x=x0; x!=x1; x+=step ) pixelDrawer( x, y0 );

    }

    var absDX:Number = Math.abs(dx);

    var absDY:Number = Math.abs(dy);

    var stepX:Number = dx / absDX;

    var stepY:Number = dy / absDY;

    var k:Number = dy / dx;

    if ( Math.abs(k)<1.0 )  // 斜率<1的情形，以X为自变量递增

    {

        var e:Number = -absDX;

        x = x0;

        y = y0;

        for ( var i:Number=0; i!=dx; i+=stepX )

        {

            pixelDrawer( x, y );

            x += stepX;

            e += 2 * absDY;

            if ( e>=0 )

            {

                y += stepY;

                e -= 2 * absDX;

            }

        }

    }

    else  // 斜率>=1的情形，以Y为自变量递增

    {

        e = -absDY;

        x = x0;

        y = y0;

        for (i=0; i!=dy; i+=stepY )

        {

            pixelDrawer( x, y );

            y += stepY; e += 2 * absDX;

            if ( e>=0 ) { x += stepX; e -= 2 * absDY; }

        }

    }

    pixelDrawer( x1, y1 );  // 绘制终点

}

编译运行得到以下结果：