デジタル微分解析装置（グラフィックスアルゴリズム）

コンピュータグラフィックスにおいて、デジタル微分解析器（DDA）は、始点と終点の間の区間における変数の補間に使用されるハードウェアまたはソフトウェアです。DDAは、線、三角形、多角形のラスタライズに使用されます。また、遠近法補正テクスチャマッピング、二次曲線、ボクセルのトラバースといった非線形関数にも拡張できます。

直線のような線形ケースに対する最も単純な実装では、DDAアルゴリズムは各x _iについてx _i = x _i−1 + 1, y _i = y _i−1 + mという式を計算することで区間内の値を補間します。ここでmは直線の傾きです。この傾きはDDAでは次のように表すことができます。

m={\frac {y_{\rm {end}}-y_{\rm {start}}}{x_{\rm {end}}-x_{\rm {start}}}}

実際、この線分上にある任意の 2 つの連続する点は、この式を満たす必要があります。

パフォーマンス

DDA方式は、浮動小数点演算または整数演算を用いて実装できます。ネイティブ浮動小数点実装では、補間値（例：座標x、y、深度、色成分など）と出力結果ごとに、1回の加算と1回の丸め演算が必要です。この処理は、高速な加算と丸め演算を備えたFPUが利用できる場合にのみ効率的です。

固定小数点整数演算では、出力サイクルごとに2回の加算が必要であり、小数部オーバーフローが発生した場合は、さらに1回の増分と減算が必要です。小数部オーバーフローの確率は、補間された開始値と終了値の比mに比例します。

DDA はハードウェア実装に適しており、パイプライン化してスループットを最大化できます。

アルゴリズム

線形DDAは、dyとdxの小さい方を、もう一方の単位増分ごとに計算することから始まります。次に、一方の座標で単位間隔ごとに直線をサンプリングし、もう一方の座標について、直線のパスに最も近い対応する整数値を決定します。

正の傾きを持つ直線を考え、傾きが1以下の場合、単位x間隔（dx=1）でサンプリングし、連続するy値を次のように計算します。

y_{k+1}=y_{k}+m

x_{k+1}=x_{k}+1

下付き文字 k は、最初の点を 0 として始まり、終点に達するまで 1 ずつ増加する整数値を取ります。y 値は、画面のピクセルに対応するために最も近い整数に切り上げられます。

傾きが1より大きい直線の場合、xとyの役割を逆にします。つまり、dy=1でサンプリングし、連続するx値を次のように計算します。

x_{k+1}=x_{k}+{\frac {1}{m}}

y_{k+1}=y_{k}+1

同様の計算は、負の傾きを持つ直線上のピクセル位置を決定するために行われます。したがって、傾きの絶対値が1未満の場合、つまり開始端点が左側にある場合は、dx=1 と設定します。 $x_{\rm {start}}<x_{\rm {end}}$

プログラム

C++の DDA アルゴリズムプログラム:

#include <graphics.h> #include <iostream.h> #include <math.h> #include <dos.h> #include <conio.h> void main () { 浮動小数点数x 、  浮動小数点数y 、  浮動小数点数x1 , y1 ,   float x2 、y2 、dx 、dy 、step ;      int i 、gd =検出、gm ;      initgraph ( & gd 、& gm 、"C: \\ TURBOC3 \\ BGI" );    cout << "x1とy1の値を入力してください: " ;   cin >> x1 >> y1 ;     cout << "x2とy2の値を入力してください: " ;   cin >> x2 >> y2 ;      dx = ( x2 - x1 );     dy = ( y2 - y1 );     もし( abs ( dx ) >= abs ( dy ))    ステップ= abs ( dx ) ;   それ以外 ステップ= abs ( dy );   dx = dx /ステップ;     dy = dy /ステップ;     x = x1 ;   y = y1 ;   i = 0 ;   while ( i <=ステップ) {     putpixel ( round ( x ), round ( y ), 5 );   x = x + dx ;     y = y + dy ;     i = i + 1 ;     遅延（100 ）; } getch (); クローズグラフ();}

参照

Bresenham のラインアルゴリズムは、ラインレンダリング用のアルゴリズムです。
増分エラーアルゴリズム
Xiaolin Wuのラインアルゴリズムは、ラインアンチエイリアシングのアルゴリズムです。

参考文献

http://www.museth.org/Ken/Publications_files/Museth_SIG14.pdf

アラン・ワット著『3Dコンピュータグラフィックス』第3版、2000年、184ページ（エッジのラスタライズ）。ISBN 0-201-39855-9