计算机图形学学习记录（一） —— DDA画线算法

数值微分

DDA(Digital Differential Analyzer)画线算法

首先在这里给不想读大篇幅的朋友，直接写上DDA算法的核心实现代码：

// 实现DDA算法。
// author: 赵天宇
// date : 2018/03/09
void DDADrawLine::LineDDA(int x0, int y0, int x1, int y1)
{
float x = 0.0;
float y = 0.0;
float m = 0.0;
// 添加增量，实现增量思想
float dx = x1 - x0;
float dy = y1 - y0;
if (dx != 0)
    {
        m = dy / dx;
if (m <= 1 && m >= -1)
        {
            y = y0;
for (x = x0; x <= x1; x++)
            {
                glVertex2i(x, int(y + 0.5));
                y += m;
            }
        }
if (m > 1 || m < -1)
        {
            m = 1 / m;
            x = x0;
for (y = y0; y <= y1; y++)
            {
                glVertex2i(int(x + 0.5), y);
                x += m;
            }
        }
    }
else 
    {
int x = x0;
int y = 0;
        y = (y0 <= y1) ? y0 : y1;
int d = fabs((double)(y0 - y1));
while (d >= 0)
        {
            glVertex2i(x, y);
            y++;
            d--;
        }
    }
}

以及其运行效果：

DDA算法的主要核心思想是在直线段的扫描转换算法的基础上，去掉效率比较低下的乘法操作。因此需要引入相关的增量思想。

增量思想

接下来利用斜截式方程进行一个增量的推到：

yi=kxi+b $$y_i=k{x}_i+b$$

yi+1=kxi+1=b=k(xi+1)+b=kxi+k+b=yi+k $$y_{i+1}=k{x}_{i+1}=b=k(x_i+1)+b=k{x}_i+k+b=y_i+k$$

所以

yi+1=yi+k $$y_{i+1}=y_i+k$$

这个式子的含义是：当前步的y值等于前一步的y值加上斜率k，这样就把惩罚变成了一个加法，提高了在计算机中的运行效率。

DDA算法小例

我们来看用DDA扫描转换连接两个点 P0(0,0) $P_0(0,0)$ 和 P1(5,3) $P_1(5,3)$ 线段的过程。

整个的执行过程如下：

代码实现

接下来我们来建立一个工程来实现一个DDA算法画线的过程。
实验环境：

• 操作系统： Win10 家庭版
• 开发工具： VS2017 + OpenGL + GLUT3.3

首先建立一个DDADrawLine的类：

DrawLine.h:

#pragma once
class DDADrawLine
{
public:
DDADrawLine();
    ~DDADrawLine();
static void DDATest(int argc, char **argv);
static void LineDDA(int x0, int y0, int x1, int y1);
static void GLTest(int argc, char **argv);
};

DDA算法测试方法：

DDA算法画线过程：

DDA算法核心代码：

DrawLine.cpp:

#include "stdafx.h"
#include "DDADrawLine.h"
#include "..\packages\nupengl.core.0.1.0.1\build\native\include\GL\glew.h"
#include "..\packages\nupengl.core.0.1.0.1\build\native\include\GL\freeglut.h"
#include <iostream>
#include <math.h>
float xs = 0.0;
float ys = 0.0;
float xe = 0.0;
float ye = 0.0;
DDADrawLine::DDADrawLine()
{
}


DDADrawLine::~DDADrawLine()
{
}
// 实现DDA画线显示过程
// author: 赵天宇
// date : 2018/03/09
void lineSegement() 
{
    glClear(GL_COLOR_BUFFER_BIT);
    glColor3f(0.0, 0.0, 0.0);
    glBegin(GL_POINTS);
    DDADrawLine::LineDDA(xs, ys, xe, ye);
    glEnd();
    glFlush();
}
// 实现DDA画线算法测试
// author: 赵天宇
// date : 2018/03/09
void DDADrawLine::DDATest(int argc, char **argv)
{
    glutInit(&argc, argv);
    glutInitDisplayMode(GLUT_RGB | GLUT_SINGLE);
using namespace std;
cout << "输入线段起始和终点坐标（范围 0 - 500， 0 - 500）：";
cin >> xs >> ys >> xe >> ye;
    glutInitWindowPosition(50, 100);
    glutInitWindowSize(500, 500);
    glutCreateWindow("DDA画线算法");
    glClearColor(1.0, 1.0, 1.0, 1.0);
    glMatrixMode(GL_PROJECTION);
    gluOrtho2D(0.0, 500, 0.0, 500.0);
    glutDisplayFunc(lineSegement);
    glutMainLoop();
}
// 实现DDA算法。
// author: 赵天宇
// date : 2018/03/09
void DDADrawLine::LineDDA(int x0, int y0, int x1, int y1)
{
float x = 0.0;
float y = 0.0;
float m = 0.0;
// 添加增量，实现增量思想
float dx = x1 - x0;
float dy = y1 - y0;
if (dx != 0)
    {
        m = dy / dx;
if (m <= 1 && m >= -1)
        {
            y = y0;
for (x = x0; x <= x1; x++)
            {
                glVertex2i(x, int(y + 0.5));
                y += m;
            }
        }
if (m > 1 || m < -1)
        {
            m = 1 / m;
            x = x0;
for (y = y0; y <= y1; y++)
            {
                glVertex2i(int(x + 0.5), y);
                x += m;
            }
        }
    }
else 
    {
int x = x0;
int y = 0;
        y = (y0 <= y1) ? y0 : y1;
int d = fabs((double)(y0 - y1));
while (d >= 0)
        {
            glVertex2i(x, y);
            y++;
            d--;
        }
    }
}

void DDADrawLine::GLTest(int argc, char **argv)
{
    glutInit(&argc, argv);
    glutInitDisplayMode(GLUT_DEPTH | GLUT_DOUBLE | GLUT_RGBA);
    glutCreateWindow("Hello OpenGL");

    glutMainLoop();
}