algorithm - 对称 DDA 是什么意思？

Question

我读过 DDA .但我刚刚遇到symmetric DDA 这个术语。它是什么 ？它与 DDA 有何不同？

Answer 1

DDA(数字差分分析仪)算法用于找出任意给定两点之间的线性插值点(即直线)。现在，由于这是在数字计算机上完成的 - 速度是一个重要因素。

直线方程由 m=Δx/Δy eq(i) 给出，其中 Δx = x(2)-x(1) & Δy = y(2)-y(1),
现在使用这个方程式，我们可以计算位于直线上的连续点。但这是光栅图形的离散世界 - 所以我们需要积分坐标。

在简单的 DDA 中，eq(i) 被转换为 m=eΔx/eΔy，其中 e 称为增量因子，是一个正实数。因为将相同的数字放在分子和分母中不会改变任何东西 - 但如果选择得当 - 它可以帮助我们生成离散点，从而减少必须对结果点进行四舍五入的过载。

基本上我们需要做的是:将坐标递增一个固定的小量，从起点开始，每次我们都有一个新点向终点前进。

在简单的 DDA 中 - e 被选为 1/max(|Δx|,|Δy|)，这样一个坐标是整数，只有另一个坐标必须四舍五入。即 P(i+1) = P(i)+(1,Round(e*Δy)) 这里一个坐标递增 1，另一个坐标递增 e*Δy

In symmetric DDA - e is chosen such that though both the co-ordinates of the resultant points has to be rounded off, it can be done so very efficiently, thus quickly.

具体来说，e 被选为 1/2^n，其中 2^(n-1) <= max(|Δx|,|Δy|) < 2^n。换句话说，线的长度被认为是 2^n 对齐的。两个坐标的增量为 e*Δx 和 e*Δy。 With suitably chosen initial fraction part of the beginning coordinates: this causes the points to be generated as mixed fractions whose fractional parts are in a cyclic series, i.e. they repeat over a small length.因此，可以根据两个固定长度的查找表轻松舍入所得坐标，每个查找表对应一个坐标。

引用http://w3.msi.vxu.se/~gsu/DAB726-Ht06/Symm-DDA.pdf举个例子。
注意结果坐标的小数部分的循环重复。