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

コンピュータグラフィックスにおいて、デジタル微分解析装置( DDA ) は、開始点と終了点の間の間隔にわたって変数を補間するために使用されるハードウェアまたはソフトウェアです。DDA は、線、三角形、および多角形のラスタライズに使用されます。DDA は、遠近法の正確なテクスチャ マッピング、二次曲線、およびボクセルのトラバースなどの非線形関数に拡張できます。

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

${\displaystyle 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 つの座標で単位間隔で線をサンプリングし、もう一方の座標に対して線パスに最も近い対応する整数値を決定します。

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

${\displaystyle y_{k+1}=y_{k}+m}$

${\displaystyle x_{k+1}=x_{k}+1}$

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

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

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

${\displaystyle y_{k+1}=y_{k}+1}$

同様の計算を実行して、負の傾きを持つ線に沿ったピクセルの位置を決定します。したがって、傾きの絶対値が 1 未満の場合、つまり開始極値が左側にある場合は、dx=1 に設定します。 ${\displaystyle x_{\rm {開始}}}$

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

#include <グラフィックス.h> 
#include <iostream.h> 
#include <math.h> 
#include <dos.h> 
#include <conio.h> 

void main ()関数 
{
  浮動小数点数x 、 
  浮動小数点y 、 
  浮動小数点数x1 、y1 、  
  float x2 、y2 、dx 、dy 、ステップ;     
  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 ;  
  私= 0 ;  

  while ( i <=ステップ) {    
    putpixel ( round ( x )、round ( y )、5 );  
    ｘ= ｘ+ ｄｘ;    
    y = y + dy ;    
    i = i + 1 ;    
    遅延（100 ）;
  }

  ゲット();
  クローズグラフ();
}

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

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

• アラン・ワット：3D コンピュータグラフィックス、第 3 版 2000、p. 184 (エッジのラスタライズ)。ISBN 0-201-39855-9