algorithm - 対称 DDA とはどういう意味ですか?

Question

DDAについて読みました。しかし、対称 DDAという用語に出くわしました。それは何ですか ？DDAとの違いは？

Answer 1

DDA (デジタル ディファレンシャル アナライザー) アルゴリズムは、任意の 2 点間の補間点を直線的に (つまり、直線で) 見つけるために使用されます。これはデジタル コンピューターで行うため、速度は重要な要素です。

直線の方程式は、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 だけインクリメントされます。

対称 DDA - eは、結果の点の両方の座標を丸める必要があるが、非常に効率的に、したがって迅速に行うことができるように選択されます。

具体的には、 eは 1/2^n として選択されます。ここで、2^(n-1) <= max(|Δx|,|Δy|) < 2^n です。言い換えると、行の長さは 2^n に揃えられます。2 つの座標の増分は、e*Δx と e*Δy です。開始座標の適切に選択された初期小数部分を使用: これにより、小数部分が巡回系列にある混合分数としてポイントが生成されます。つまり、短い長さで繰り返されます。したがって、結果の座標は、各座標に 1 つずつ、2 つの固定長のルックアップ テーブルに基づいて簡単に四捨五入できます。

例については、 http://w3.msi.vxu.se/~gsu/DAB726-Ht06/Symm-DDA.pdfを参照してください。
結果の座標の小数部分の循環的な繰り返しに注意してください。