计算机图形学学习记录（三）Breseham画线算法

Breseham算法

首先为了方便直接看算法代码的朋友直接看核心代码和结果，在这里直接贴出算法代码。

void DDADrawLine::BreasehamDrawLine(int x0, int y0, int x1, int y1)
{
    int iTag = 0;
    int dx, dy, tx, ty, inc1, inc2, d, curx, cury;
    glColor3f(1.0f, 0.0f, 0.0f);
    glBegin(GL_POINTS);
    glVertex2i(x0, y0);
    glEnd();
    if (x0 == x1 && y0 == y1)
    {
        return;
    }
    dy = abs(y1 - y0);
    dx = abs(x1 - x0);
    if (dx < dy)
    {
        iTag = 1;
        Swap(x0, x1);
        Swap(x1, y1);
        Swap(dx, dy);
    }
    tx = ((x1 - x0) > 0) ? 1 : -1;
    ty = ((y1 - y0) > 0) ? 1 : -1;
    curx = x0; 
    cury = y0;
    inc1 = 2 * dy;
    inc2 = 2 * (dy - dx);
    d = inc1 - dx;
    while (curx != x1)
    {
        curx += tx;
        if (d < 0)
        {
            d += inc1;
        }
        else
        {
            cury += ty;
            d += inc2;
        }
        if (iTag)
        {
            glBegin(GL_POINTS);
            glVertex2i(cury, curx);
            glEnd();
        }
        else
        {
            glBegin(GL_POINTS);
            glVertex2i(curx, cury);
            glEnd();
        }
    }
}

相关获得的结果是：

算法原理

DDA把算法效率提高到每步只做一个加法。
中点算法进一步把效率提高到每步只做一个整数加法。
Bresenham提供了一个更一般的算法。该算法不仅有好的效率，而且有更广泛的适用范围。

本算法的主要思想是通过将各行、各列像素中心构造成一组虚拟网格线，按照直线七点到终点的顺序，计算直线与各垂直网格线的交点，然后根据误差项的符号确定该列像素中与此交点最近的元素。

假设每次都有 x+1 $x+1$ ， y $y$ 的递增（减）量为0 或者 1， 它取决于实际直线与最近光栅网格点的距离，这个距离的最大误差为0.5。
误差项d的初值 d0=0 $d_0=0$

d=d+k $$d=d+k$$

一旦有 d≥1 $d\ge 1$就把它减去1，保证 d $d$的相对性，且在0、1之间。

可以得到：

⎧⎩⎨xi+1=xi+1 yi+1={yi+1 yiififd>0.5d≤0.5 $$\{\begin{array}{l}{x}_{i+1}=x_i+1\\ y_{i+1}=\{\begin{array}{lll}{y}_i+1& if& d>0.5\\ y_i& if& d\le 0.5\end{array}\end{array}$$

那么问题的关键变成了，如何将现在的Breseham算法提高到整数加法。
我们令 e=d−0.5 $e=d-0.5$ 就有：

⎧⎩⎨xi+1=xi+1 yi+1={yi+1 yiifife>0e≤0 $$\{\begin{array}{l}{x}_{i+1}=x_i+1\\ y_{i+1}=\{\begin{array}{lll}{y}_i+1& if& e>0\\ y_i& if& e\le 0\end{array}\end{array}$$

e>0 $e>0$ , y $y$方向递增1； e<0 $e<0$， y $y$方向不递增。 e=0 $e=0$时，可以任意去上、下光栅点显示。

e初=−0.5 $e_{初}=-0.5$
每走一步有 e=e+k $e=e+k$
if(e>0) $if(e>0)$
e=e−1 $e=e-1$
e初=−0.5 $e_{初}=-0.5$ , k=dydx $k=\frac{dy}{dx}$
由于算法中只用到误差项的符号，于是可以利用 e∗2∗Δx $e\ast 2\ast \mathrm{\Delta }x$来代替 e $e$
e初=−Δx $e_{初}=-\mathrm{\Delta }x$
每走一步有 e=e+2Δy $e=e+2\mathrm{\Delta }y$
if(e>0) $if(e>0)$
e=e−2Δx $e=e-2\mathrm{\Delta }x$
e初=−0.5 $e_{初}=-0.5$ , k=dydx $k=\frac{dy}{dx}$

算法步骤

1. 输入直线的两个端点 P0(x0,y0) $P_0(x_0,y_0)$, P1(x1,y1) $P_1(x_1,y_1)$。
2. 计算初始值 Δx,Δy,e=−Δx,x=x0,y=y0 $\mathrm{\Delta }x,\mathrm{\Delta }y,e=-\mathrm{\Delta }x,x=x_0,y=y_0$。
3. 绘制点 (x,y) $(x,y)$。
4. e $e$更新为 e+2Δy $e+2\mathrm{\Delta }y$， 判断 e $e$的符号。 if(e>0) $if(e>0)$ (x,y)⇒（x+1,y+1） $(x,y)\Rightarrow （x+1,y+1）$， 同时将 e $e$更新为 e−2Δx $e-2\mathrm{\Delta }x$； 否则 (x,y)⇒（x+1,y） $(x,y)\Rightarrow （x+1,y）$
5. 当直线没有画完时，重复3，4的步骤。否则结束。

代码实现

void DDADrawLine::BreasehamDrawLine(int x0, int y0, int x1, int y1)
{
    int iTag = 0;
    int dx, dy, tx, ty, inc1, inc2, d, curx, cury;
    glColor3f(1.0f, 0.0f, 0.0f);
    glBegin(GL_POINTS);
    glVertex2i(x0, y0);
    glEnd();
    if (x0 == x1 && y0 == y1)
    {
        return;
    }
    dy = abs(y1 - y0);
    dx = abs(x1 - x0);
    if (dx < dy)
    {
        iTag = 1;
        Swap(x0, x1);
        Swap(x1, y1);
        Swap(dx, dy);
    }
    tx = ((x1 - x0) > 0) ? 1 : -1;
    ty = ((y1 - y0) > 0) ? 1 : -1;
    curx = x0; 
    cury = y0;
    inc1 = 2 * dy;
    inc2 = 2 * (dy - dx);
    d = inc1 - dx;
    while (curx != x1)
    {
        curx += tx;
        if (d < 0)
        {
            d += inc1;
        }
        else
        {
            cury += ty;
            d += inc2;
        }
        if (iTag)
        {
            glBegin(GL_POINTS);
            glVertex2i(cury, curx);
            glEnd();
        }
        else
        {
            glBegin(GL_POINTS);
            glVertex2i(curx, cury);
            glEnd();
        }
    }
}

相关获得的结果是：