计算机图形学——直线生成算法 - 《计算机图形学》

一、综述
二、程序框架
三、算法描述
四、运行结果
五、算法对比

一、综述

直线的扫描转换是指在图形输出设备上，按照扫描线的顺序，确定一组最佳逼近于直线的像素点并对像素进行写操作。直线生成的具体问题是已知直线的两个端点,要求在图像输出设备上从起点到中点通过逐次循环迭代，找到最接近直线的像素点集合。

所涉及的算法有三种：DDA算法、B算法和重点分割法。在MFC环境中测试三种算法并对比分析三种算法的误差及效率。

二、程序框架

程序为MFC：

CCgDrawLineView.h为视图层的头文件，负责声明各种成员变量和成员函数；
CCgDrawLineView.cpp为视图层的源文件，负责实现直线的三种绘制、误差分析并显示、圆与圆弧绘制的功能。
CCgEditControl.h为窗口面板中的按键及文本定义成员变量及成员函数。
CCgEditControl.cpp实现面板的功能，如点击按键绘制图像、分析误差等。

三、算法描述

1. DDA算法

（1）将给定端点作为输入参数；

（2）初始化，初值加上0.5确保精度；

（3）计算起止点水平和垂直的差值dx和dy，选取较大者为最大位移，并作为迭代步数step；

（4）从起始点开始确定相邻两点间的增量并进行地推计算。

若dx>dy,且x1dy,且x1>=x2，则x和y方向上的增量分别为-1和斜率-m；
若dx<=dy,且x1=x2，则x和y方向上的增量分别为-1/m和-1。

（5）重复上一步直到循环结束；

（6）将所求得坐标取整并设置颜色值。

源代码参考：

//DDA算法
void DDAline(int x0, int y0, int x1, int y1, CDC* pDC)
{
    //误差参数
    float distance = 0.0f; //生成点距理想直线的距离
    float kaverage = 0.0f; //生成点和起点连线的斜率平均值
    float xp, yp; //垂足点的坐标
    int step = abs(x1 - x0) >= abs(y1 - y0) ? abs(x1 - x0) : abs(y1 - y0);
    float dx = (float)(x1 - x0) / step;
    float dy = (float)(y1 - y0) / step;
    float m = (float)(y1 - y0) / (float)(x1 - x0);
    float x = x0 + 0.5f;
    float y = y0 + 0.5f;
    for (int i = 0; i < step; i++)
    {
        pDC->SetPixel((int)x + m_wndWidth / 2, (int)m_wndHeight / 2 - y, RGB(255, 0, 0));
        //计算垂足坐标
        xp = (y - y0 + x / m + m * x0) / (m + 1 / m);
        yp = -1 / m * (xp - x) + y;
        distance += sqrtf((x - xp) * (x - xp) + (y - yp) * (y - yp)); //生成点距离直线的距离累加值
        if (x != x0)
            kaverage += fabs(y - y0) / fabs(x - x0); //计算生成点和起点连线的斜率平均值
        x += dx ;
        y += dy;
    }
    ddaError = distance / step; //误差为距离的平均值
    ddaSmooth = fabs(kaverage / step - m); //平滑度为斜率的平均值
}

2. B算法

（1）确定最大位移方向并计算误差初值e = 2 * min - max;（min和max分别为水平距离和垂直距离的最值）

（2）设置点(Xi, Yi) 的颜色值，并求下一误差ei+1；

如果 ei > 0 则ei+1 = e - 2 * max;；
否则ei+1 = ei + 2 * min；

（3）根据不同象限，确定x和y变化符号的正负，进行下一次循环；

（4）如果没有结束，则转到步骤2，3；否则结束。

源代码参考：

//B算法
void Bline(int x0, int y0, int x1, int y1, CDC* pDC) {
    //误差参数
    float distance = 0.0f; //生成点距理想直线的距离
    float kaverage = 0.0f; //生成点和起点连线的斜率平均值
    float xp, yp; //垂足点的坐标
    float m = (float)(y1 - y0) / (float)(x1 - x0);
    int x = x0, y = y0, dx = x1 - x0, dy = y1 - y0;
    int max = (abs(dy) > abs(dx)) ? abs(dy) : abs(dx);
    int min = (abs(dy) > abs(dx)) ? abs(dx) : abs(dy);
    float e = 2 * min - max;
    for (int i = 0; i < max; i++)
    {
        pDC->SetPixel((int)x + m_wndWidth / 2, (int)m_wndHeight / 2 - y, RGB(0, 0, 255));
        //计算垂足坐标
        xp = (y - y1 + x / m + m * x1) / (m + 1 / m);
        yp = -1 / m * (xp - x) + y;
        distance += sqrtf((x - xp) * (x - xp) + (y - yp) * (y - yp)); //生成点距离直线的距离累加值
        if (x != x0)
            kaverage += (float)fabs(y - y0) / (float)fabs(x - x0); //计算生成点和起点连线的斜率平均值
        if (e >= 0)
        {
            e = e - 2 * max;
            (abs(dy) > abs(dx)) ? (dx >= 0 ? x++ : x--) : (dy >= 0 ? y++ : y--);
        }
        e += 2 * min;
        (abs(dy) > abs(dx)) ? (dy >= 0 ? y++ : y--) : (dx >= 0 ? x++ : x--);
    }
    bError = distance / max; //误差为距离的平均值
    bSmooth = fabs(kaverage / max - m); //平滑度为斜率的平均值
}

3. 中点分割法

（1）将直线段求中点坐标，若可以细分，则进行一次递归；

（2）如果中点坐标无法继续递归，则设置改像素的颜色值；

（3）执行至所有点都完成了颜色值的设置，程序结束。

源代码参考：

//中点分割算法
void Midpoint(int x0, int y0, int x1, int y1, CDC* pDC) {
    if (abs(x0 - x1) <= 1 && abs(y0 - y1) <= 1) {
        pDC->SetPixel((int)((x0 + x1) / 2 + 0.5) + m_wndWidth / 2, (int)m_wndHeight / 2 - ((y0 + y1) / 2 + 0.5), RGB(0, 255, 0));    }
    else {Midpoint(x0, y0, (x0 + x1) / 2, (y0 + y1) / 2, pDC);
        Midpoint((x0 + x1) / 2, (y0 + y1) / 2, x1, y1, pDC);}
}

中点分割算法误差分析：

//中点分割算法误差分析
void MidpointAnalyse(int x0, int y0, int x1, int y1, CDC* pDC) {
    //误差参数
    float distance = 0.0f; //生成点距理想直线的距离
    float kaverage = 0.0f; //生成点和起点连线的斜率平均值
    float xp, yp; //垂足点的坐标
    static int x00 = x0, y00 = y0, x11 = x1, y11 = y1; //记录起始点的坐标
    float m = (float)(y11 - y00) / (float)(x11 - x00);
    int dx = x11 - x00, dy = y11 - y00;
    int max = (abs(dy) > abs(dx)) ? abs(dy) : abs(dx);
    if (abs(x0 - x1) <= 1 && abs(y0 - y1) <= 1) {
        pDC->SetPixel((int)((x0 + x1) / 2 + 0.5) + m_wndWidth / 2, (int)m_wndHeight / 2 - ((y0 + y1) / 2 + 0.5), RGB(0, 255, 0));
        //计算垂足坐标
        xp = (y00 - y1 + x00 / m + m * x1) / (m + 1 / m);
        yp = -1 / m * (xp - x00) + y00;
        distance += sqrtf((x00 - xp) * (x00 - xp) + (y00 - yp) * (y00 - yp));  //生成点距离直线的距离累加值
        kaverage += (float)fabs((y0 + y1) / 2 + 0.5 - y0) / (float)fabs((x0 + x1) / 2 + 0.5 - x0); //计算生成点和起点连线的斜率平均值
        mpSmooth = fabs(kaverage / max - m); //误差为距离的平均值
        mpError = distance / max; //平滑度为斜率的平均值
    }
    else {
        MidpointAnalyse(x0, y0, (x0 + x1) / 2, (y0 + y1) / 2, pDC);
        MidpointAnalyse((x0 + x1) / 2, (y0 + y1) / 2, x1, y1, pDC);
    }
}