DDA算法

DDA代表数字微分分析仪。 它是线扫描转换的增量方法。 在这种方法中，每一步都进行计算，但使用先前步骤的结果。

假设在步骤i，像素为（x_i,y_i)

步骤i的方程线
              y_i=mx_i+b......................方程 1

下一个值将是
              y_i+1=m_xi+1+b.................方程 2
              m =
              y_i+1-y_i=∆y.......................方程 3
              y_i+1-x_i=∆x......................方程 4
              y_i+1=y_i+∆y
              ∆y=m∆x
              y_i+1=y_i+m∆x
              ∆x=∆y/m
              x_i+1=x_i+∆x
              x_i+1=x_i+∆y/m

情况1： 当 |M|<1 时 (假设 x₁2)
              x= x₁,y=y₁ 设置 ∆x=1
              y_i+1=y_1+m,     x=x+1
              直到 x = x₂

情况2： 当 |M|<1 时 (假设 y₁2)
              x= x₁,y=y₁ 设置 ∆y=1
              x_i+1=,     y=y+1
              直到 y → y₂

优点

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

缺点

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

DDA算法

步骤1： 开始算法

步骤2： 将 x₁,y₁,x₂,y₂,dx,dy,x,y 声明为整数变量。

步骤3： 输入 x₁,y₁,x₂,y₂ 的值。

步骤4： 计算 dx = x₂-x₁

步骤5： 计算 dy = y₂-y₁

步骤6： 如果 ABS (dx) > ABS (dy)
            那么 step = abs (dx)
            否则

步骤7： x_inc=dx/step
            y_inc=dy/step
            分配 x = x₁
            分配 y = y₁

步骤8： 设置像素 (x, y)

步骤9： x = x + x_inc
            y = y + y_inc
            设置像素 (Round (x), Round (y))

步骤10： 重复步骤9，直到 x = x₂

步骤11： 结束算法

示例： 如果使用DDA绘制一条从（2，3）到（6，15）的线。 生成这样的线需要多少个点？

解决方案： P₁ (2,3)       P₁₁ (6,15)

                x₁=2
                y₁=3
                x₂= 6
                y₂=15
                dx = 6 - 2 = 4
                dy = 15 - 3 = 12
                m =

为了计算x的下一个值，取 x = x +

实现DDA线绘制算法的程序

输出

对称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，其中2^n-1≤max (|∆x|,|∆y|)<2^π

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

示例： 如果使用对称 DDA 绘制一条从 (0, 0) 到 (10, 5) 的线

1. 执行了多少次迭代？

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

解决方案： 给定：P¹ (0,0) P² (10,5)
                x¹=0
                y¹=0
                x²=10
                y²=5
                dx = 10 - 0 = 10
                 dy = 5 - 0 = 0
               

P¹ (0,0) 将被视为起点
P³ (1,0.5)                 未绘制点
P⁴ (2, 1)                 绘制点
P⁵ (3, 1.5)                 未绘制点
P⁶ (4,2)                 绘制点
P⁷ (5,2.5)                 未绘制点
P⁸ (6,3)                 绘制点
P⁹ (7,3.5)                 未绘制点
P¹⁰ (8, 4)                 绘制点
P¹¹ (9,4.5)                 未绘制点
P¹² (10,5)                 绘制点

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