数值微分
DDA(Digital Differential Analyzer)画线算法
首先在这里给不想读大篇幅的朋友，直接写上DDA算法的核心实现代码：
DDA算法代码
上面这个只针对斜率绝对值小于1的。
// 实现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算法如下：
void DDADrawLine::DDALine(int xa, int ya, int xb, int yb)
{
GLfloat delta_x, delta_y, x, y;
int dx, dy, steps;
dx = xb - xa;
dy = yb - ya;
if (abs(dx)>abs(dy))
{
steps = abs(dx);
}
else
{
steps = abs(dy);
}
delta_x = (GLfloat)dx / (GLfloat)steps;
delta_y = (GLfloat)dy / (GLfloat)steps;
x = xa;
y = ya;
// glClear(GL_COLOR_BUFFER_BIT);
glBegin(GL_POINTS);
glVertex3f(x, y, 0);
for (int i = 1; i <= steps; i++)
{
x += delta_x;
y += delta_y;
glBegin(GL_POINTS);
glVertex3f(x, y, 0);
glEnd();
}
}
运行结果如下：
DDA算法输出结果.png
DDA算法的主要核心思想是在直线段的扫描转换算法的基础上，去掉效率比较低下的乘法操作。因此需要引入相关的增量思想。
增量思想
增量描述图
接下来利用斜截式方程进行一个增量的推导：
DDA推导公式
这个式子的含义是：当前步的y值等于前一步的y值加上斜率k，这样就把惩罚变成了一个加法，提高了在计算机中的运行效率。
DDA算法小例
我们来看用DDA扫描转换连接两个点$P_0(0, 0)$ 和 $P_1(5, 3)$ 线段的过程。
DDA算法实例
整个的执行过程如下：
DDA算法实例过程
代码实现
接下来我们来建立一个工程来实现一个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();
}
以及其运行效果：
这里写图片描述
针对任意斜率直线的DDA算法如下：
void DDADrawLine::DDALine(int xa, int ya, int xb, int yb)
{
GLfloat delta_x, delta_y, x, y;
int dx, dy, steps;
dx = xb - xa;
dy = yb - ya;
if (abs(dx)>abs(dy))
{
steps = abs(dx);
}
else
{
steps = abs(dy);
}
delta_x = (GLfloat)dx / (GLfloat)steps;
delta_y = (GLfloat)dy / (GLfloat)steps;
x = xa;
y = ya;
// glClear(GL_COLOR_BUFFER_BIT);
glBegin(GL_POINTS);
glVertex3f(x, y, 0);
for (int i = 1; i <= steps; i++)
{
x += delta_x;
y += delta_y;
glBegin(GL_POINTS);
glVertex3f(x, y, 0);
glEnd();
}
}
运行结果如下：
DDA算法输出结果.png
