计算机图形DDA算法 DDA算法|计算机图形学

本文概述

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
优点：

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

坏处：

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

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）点标绘
下图显示了使用这些点绘制的线。