计算机图形学(一)--DDA画线算法

DDA直线绘制算法

  DDA就是数值微分Digital Differential Analyzer)的简称。在一个坐标轴上以单位间隔对线段进行取样,从而确定另一个最靠近路径对应的整数值。

优点

  利用增量思想使得在确定直线中每个点的坐标时只进行一次加法运算

缺点

  由于直线的斜率($k={{y1-y0}\over{x1-x0}}$)有可能是小数,并且在计算出坐标后的值还得进行取整,所以此算法不利于硬件实现

算法思想

直线方程斜截式

  ($y=kx+b$),其中k斜率b是直线在y轴上的截距,而斜率($k={\Delta y \over \Delta x}={{y1-y0}\over{x1-x0}}$)

假设

  现在需要画一条经过点$P_0(2,3)$和点$P_1(17,12)$的直线
  根据直线方程斜截式($y=kx+b$),此时b=0,其中斜率($k={{y1-y0}\over{x1-x0}}={{12-3}\over{17-2}}=0.6$),可以表示为:$y=0.6x$

用图表示

  * 第0个点(2,3)

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 1 2 3 4 5 6 7 8 9 10 11 12 13

  * 第1个点y=0.6x1=0.6,坐标x上加1y加上0.6,取整后(3,4)

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 1 2 3 4 5 6 7 8 9 10 11 12 13

  * 第2个点y=0.6x2=1.2,坐标x上加1y加上1.2,取整后(4,4)

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 1 2 3 4 5 6 7 8 9 10 11 12 13

……

  * 一直到第15个点y=0.6x15=9.0,坐标(17,12)

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 1 2 3 4 5 6 7 8 9 10 11 12 13

  * 至此就完成了一条直线的绘制

增量

  可以看到,上面的方法可以快速的画出一条直线,不过还需要优化一下。之前说的DDA每次确定一个点只需要一次加法运算,但是这里却进行了一次乘法加上一次加法。
  可以看出来,这里的y就是每次斜率加上了上一次的y坐标:
$yi=kx+b$
下一个点表示为
$y
{i+1}=k(x+1)+b$
$\qquad=kx+k+b$
$\qquad=kx+b+k$
可以看到这里的$kx+b$就等于$yi$
所以
$y
{i+1}=y_i+k$

算法实现

  • 先声明一个画线的函数:
    x0:起点x坐标
    y0:起点y坐标
    x1:结束点x坐标
    y1:结束点y坐标
1
2
3
4
void dda(int x0,int y0,int x1,int y1)
{
......
}

当斜率$0<|k|\leq1$时

  斜率小于等于1时可以直接通过递增x方向来计算出y的值,但如果斜率大于1就会出现点不连续的情况。

  • 先计算两个坐标的xy坐标差
1
2
3
float dx=x1-x0;
float dy=y1-y1;
float y=y0;
  • 然后根据($k={\Delta y \over \Delta x}$)求出斜率注:dx为0的情况未考虑进去
1
float k=dy/dx;
  • 之前就已经推导出y的值其实就是每次都用斜率加上前一次的值,所以求y的代码可以这样写
1
y+=k;
  • 再使用循环来绘制所有点,由于这里是斜率小于等于1的情况,所以判断x0是否小于等于结束点的x1作为循环条件
1
2
3
4
for(;x0<=x1;++x0)
{
......
}
  • 再把求y值以及画点的代码添加进去
1
2
3
4
5
for(;x0<=x1;++x0)
{
drawPoint(x0,(int)(y+0.5));
y+=k;
}
  • 完整代码如下 注:未考虑dx为0的情况
1
2
3
4
5
6
7
8
9
10
float dx=x1-x0;
float dy=y1-y1;
float y=y0;

float k=dy/dx;
for(;x0<=x1;++x0)
{
drawPoint(x0,(int)(y+0.5));
y+=k;
}

当斜率$|k|>1$时

  斜率大于1时只需要把计算y值改成计算x值就行了,注意k=dx/dy注:dy可能为0

  • 完整代码如下 注:未考虑dy为0的情况
1
2
3
4
5
6
7
8
9
10
float dx=x1-x0;
float dy=y1-y1;
float x=x0;

float k=dx/dy;
for(;y0<=y1;++y0)
{
drawPoint((int)(x+0.5),y0);
x+=k;
}

适用于任何斜率的方法

  由于上面两种都只针对特定的斜率以及特定的方向绘制直线,所以还得优化下

  • 首先还是得先计算两个坐标的xy的差
1
2
float dx=x1-x0;
float dy=y1-y1;
  • 然后这里多了个steps变量,可以看作是绘制这条直线的点的数量。注:这里引入了math.h头文件用来获取绝对值
1
2
3
4
5
6
int steps=abs(y1-y0);
// 这里是取绘制点数最多的值
if(fabs(dx)>fabs(dy))
steps=abs(x1-x0);
// 注意:在这之后steps可能为0,
// steps为0的话就只需要画一个起点就行了(这里未写出),不需要再执行下面的代码
  • 因为现在是两种情况都要考虑,所以就一次性计算出每一步(step)的xy的增量
1
2
3
4
5
6
7
// 先初始化两个坐标为起点
float x=x0;
float y=y0;
// 然后定义两个x和y的增量变量
// 分别用两点的x、y的差除与需要绘制的点数来获得每绘制结束一个点后需要前进多少
float xinc=dx/steps;
float yinc=dy/steps;
  • 首先第一个点要自己绘制。注:这里引入了math.h头文件进行四舍五入操作
1
drawPoint(round(x),round(y));
  • 剩下的点,绘制steps个就行了
1
2
3
4
for(int i=0;i<steps;++i)
{
......
}
  • 计算当前点的位置,直接xy分别加上增量就行了
1
2
x+=xinc;
y+=yinc;
  • 绘制点的方法不变,把这些放进循环里面
1
2
3
4
5
6
7
8
9
for(int i=0;i<steps;++i)
{
// 注意这里需要放到本次循环开始
// 因为第一个点已经绘制了
x+=xinc;
y+=yinc;

drawPoint(round(x),round(y));
}
  • 完整代码如下 注:未考虑steps为0的情况
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
float dx=x1-x0;
float dy=y1-y1;

int steps=abs(y1-y0);
// 这里是取绘制点数最多的值
if(fabs(dx)>fabs(dy))
steps=abs(x1-x0);

// 先初始化两个坐标为起点
float x=x0;
float y=y0;
// 然后定义两个x和y的增量变量
// 分别用两点的x、y的差除与需要绘制的点数来获得每绘制结束一个点后需要前进多少
float xinc=dx/steps;
float yinc=dy/steps;

// 绘制起点
drawPoint(round(x),round(y));
for(int i=0;i<steps;++i)
{
// 注意这里需要放到本次循环开始
// 因为第一个点已经绘制了
x+=xinc;
y+=yinc;

drawPoint(round(x),round(y));
}

代码地址

dda.c

最后

  DDA的计算方法比直接套用直线方程的效率要高得多。虽然从一个乘法一个加法缩减到了一个加法,但是在进行计算中的浮点运算和取整依旧比较耗时。后面会接触绘制直线的其它算法。