计算机图形DDA算法

本文概述

• DDA算法
• 对称DDA

DDA代表数字差分分析仪。它是行扫描转换的增量方法。在这种方法中, 计算是在每个步骤中执行的, 但要使用先前步骤的结果。

假设在步骤i, 像素为（xi, yi）

步骤i的方程式yi = mxi + b ………………….方程1

Next value will be yi+1=mxi+1+b……………..equation 2 m = yi+1-yi=∆y…………………..equation 3 yi+1-xi=∆x………………….equation 4 yi+1=yi+∆y ∆y=m∆x yi+1=yi+m∆x ∆x=∆y/m xi+1=xi+∆x xi+1=xi+∆y/m

情况1：当| M | <1时（假设x12）x = x1, y = y1设置∆x = 1 yi + 1 = y1 + m, x = x + 1直到x = x2

情况2：当| M | <1时（假设y12）x = x1, y = y1设置∆y = 1 xi + 1 =, y = y + 1直到y→y2

优点：

1. 比直接使用线性方程式的方法要快。
2. 此方法不使用乘法定理。
3. 它使我们能够检测x和y值的变化, 因此不可能两次绘制相同的点。
4. 重新定位点时, 此方法会给出溢出指示。
5. 这是一种简单的方法, 因为每个步骤仅涉及两个附加步骤。

坏处：

1. 它涉及浮点加法四舍五入。舍入误差的累积导致误差的累积。
2. 四舍五入操作和浮点操作会消耗大量时间。
3. 更适合使用该软件生成线。但是它不太适合硬件实现。

DDA算法

步骤1：开始算法

步骤2：将x1, y1, x2, y2, dx, dy, x, y声明为整数变量。

步骤3：输入x1, y1, x2, y2的值。

步骤4：计算dx = x2-x1

步骤5：计算dy = y2-y1

步骤6：如果ABS（dx）> ABS（dy）, 则step = abs（dx）否则

第7步：xinc = dx / step yinc = dy / step分配x = x1分配y = y1

步骤8：设定像素（x, y）

第9步：x = x + xinc y = y + yinc设置像素（圆形（x）, 圆形（y））

步骤10：重复步骤9, 直到x = x2

步骤11：结束算法

示例：如果使用DDA从（2, 3）到（6, 15）画了一条线。生成该线需要多少点？

解决方案：P1（2, 3）P11（6, 15）

x1 = 2 y1 = 3 x2 = 6 y2 = 15 dx = 6-2 = 4 dy = 15-3 = 12 m =

为了计算x的下一个值, 需要x = x +

实现DDA线描算法的程序：

#include<graphics.h>
#include<conio.h>
#include<stdio.h>
void main()
{
	intgd = DETECT , gm, i;
	float x, y, dx, dy, steps;
	int x0, x1, y0, y1;
	initgraph(&gd, &gm, "C:\\TC\\BGI");
	setbkcolor(WHITE);
	x0 = 100 , y0 = 200, x1 = 500, y1 = 300;
	dx = (float)(x1 - x0);
	dy = (float)(y1 - y0);
	if(dx>=dy)
           {
		steps = dx;
	}
	else
           {
		steps = dy;
	}
	dx = dx/steps;
	dy = dy/steps;
	x = x0;
	y = y0;
	i = 1;
	while(i<= steps)
	{
		putpixel(x, y, RED);
		x += dx;
		y += dy;
		i=i+1;
	}
	getch();
	closegraph();
}

输出：

对称DDA

数字差分分析仪（DDA）根据其微分方程生成线。直线方程为

DDA的工作原理是, 我们以与x和y的一阶导数成比例的小步长同时增加x和y。在直线的情况下, 一阶导数是常数, 并且与∆x和∆y成比例。因此, 我们可以通过将x和y分别增加ϵ ∆x和ϵ ∆y来生成一条线, 其中ϵ的数量很小。有两种生成点的方法

1.在每个增量步长后四舍五入到最接近的整数, 四舍五入后, 我们在所得的x和y处显示点。

2.舍入使用算术溢出的一种替代方法：x和y保留在具有整数和小数两部分的寄存器中。都小于1的递增值被重复加到小数部分, 每当结果溢出时, 相应的整数部分就会递增。 x和y寄存器的整数部分用于绘制线。在对称DDA的情况下, 我们选择ε= 2-n, 其中2n-1≤max（| ∆x |, | ∆y |）<2π

用对称DDA绘制的线如图所示：

示例：如果使用对称DDA从（0, 0）到（10, 5）绘制了一条线

1.执行多少次迭代？

2.将产生多少个不同的点？

解决方案：给定：P1（0, 0）P2（10, 5）x1 = 0 y1 = 0 x2 = 10 y2 = 5 dx = 10-0 = 10 dy = 5-0 = 0

P1（0, 0）将被视为起点P3（1, 0.5）点未绘制P4（2, 1）点已绘制P5（3, 1.5）点未绘制P6（4, 2）点已绘制P7（5, 2.5） ）点未标绘P8（6, 3）点已标绘P9（7, 3.5）点未标绘P10（8, 4）点已标绘P11（9, 4.5）点未标绘P12（10, 5）点标绘

下图显示了使用这些点绘制的线。