计算机图形学----DDA、Bresenham直线算法

我不是女神ヾ 2022-06-14 08:12 646阅读 0赞

### **一、DDA算法原理** ###

DDA（数值微分算法）算法是一个增量算法。增量算法：在一个迭代算法中，每一步的x、y值是用前一步的值加上一个增量来获得。

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

DDA需要考虑所画直线的斜率k：

当 |k|<1 , x每增加1，y 增加k。

当 |k|>1 , y每增加1，x增加1/k。

![SouthEast][]![SouthEast 1][]

编程实现直线的DDA算法程序；

void CMyView::OnDdaline()
    {
        CDC *pDC=GetDC();              // 获得设备指针
        intx0=100,y0=100,x1=300,y1=200,c=RGB(255,0,0);  //定义直线两端点和直线颜色（红色）
        float x,y,i;
        float dx,dy,k;
        dx=(float)(x1-x0);
        dy=(float)(y1-y0);
        k=dy/dx;//计算斜率
        y=y0; x=x0;
        if(abs(k)<1)
        {   for(;x<=x1;x++)
            {pDC->SetPixel(x,int(y+0.5),c);
            y=y+k;}//x自增，y=y+k
        }
        if(abs(k)>=1)
        {
          for(;y<=y1;y++)
          {pDC->SetPixel(int(x+0.5),y,c);
          x=x+1/k;}
        }
        ReleaseDC(pDC);      //释放设备指针
    }

### 二、Bresenham算法原理 ###

Bresenham算法是计算机图形学领域使用最广泛的直线扫描转换方法。

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

该算法的优点在于可以采用增量计算，使得对于每一列，只要检查一个误差项的符号，就可以确定该列所求的像素。

![SouthEast 2][]

![SouthEast 3][]

直线的Bresenham算法实现：

void CTestView::OnBresenhamline()
    {
        CDC*pDC=GetDC();
        intx1=100,y1=200,x2=600,y2=800,color=RGB(0,0,255);
        inti,x,y,dx,dy;
        float k,e;
        dx=x2-x1;
        dy=y2-y1;
        k=dy/dx;
        e=-0.5;  x=x1; y=y1;//e初值d0-0.5
        for(i=0;i<=dx;i++)
        {   pDC->SetPixel(x,y,color);
           x++;
           e=e+k;
           if(e>=0)  { y++; e=e-1;}
        }
    }

### 三、Bresenham改进算法 ###

上述bresenham算法在计算直线斜率与误差项时用到了小数与除法，可以改用整数以避免除法。由于算法中用到误差项的符号，因此可以做如下替换：e'=2\*e\*dx.

直线的整数Bresenham算法实现：

void CTestView::OnBresenhamline()
    {
        CDC *pDC=GetDC();
        int x0=100,y0=100,x1=500,y1=600,color=RGB(0,0,255);int i,x,y,dx,dy;
        float k,e;
        dx=x1-x0;
        dy=y1-y0;
        e=-dx;
        x=x0; y=y0;
        for(i=0;i<=dx;i++)
         { pDC->SetPixel(x,y,color);
            x++;
            e+=2*dy;
        if(e>=0)
         {y++;e=e-2*dx;} }
         ReleaseDC(pDC);
    }

[http://download.csdn.net/detail/ljheee/9870382][http_download.csdn.net_detail_ljheee_9870382]

[SouthEast]: https://img-blog.csdn.net/20170614152930946?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvbGpoZWVl/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast
[SouthEast 1]: /images/20220614/b076cd4e7e8b4f239ae5b440634dd800.png
[Link 1]: http://baike.baidu.com/item/%E7%BD%91%E6%A0%BC%E7%BA%BF
[SouthEast 2]: /images/20220614/3ffd1a3ffd554adf96981e99d6abdfaa.png
[SouthEast 3]: /images/20220614/3d37359167f6475292e15d122b95f106.png
[http_download.csdn.net_detail_ljheee_9870382]: http://download.csdn.net/detail/ljheee/9870382