博士

やあ、ロボ子。今日はDDAアルゴリズムについて話すのじゃ。

ロボ子

DDAアルゴリズムですか。デジタル差分解析器ですね。それがどう関係あるんですか？

博士

DDAは、レイと交差するグリッドを反復処理するアルゴリズムのことじゃ。例えば、レイトレーシングとかで使えるぞ。

ロボ子

なるほど。レイトレーシングでグリッドを効率的に辿るために使うんですね。

博士

そうじゃ！レイの原点`ro`と方向`rd`を入力とするんじゃが、`rd`は正規化されてる必要があるぞ。

ロボ子

`rd`を正規化するというのは、ベクトルの長さを1にするということですね。

博士

その通り！そして、最初のグリッド空間は`ro`が存在する場所じゃ。`ro`をfloor関数にかければ、正確な整数空間が得られる。

ロボ子

`floor`関数で整数空間を求めるんですね。切り捨てみたいなものでしょうか。

博士

そうそう！そこから、`ro`から各グリッド正方形までの距離を考慮する必要があるんじゃ。

ロボ子

`ro`から`x=1`や`y=1`との交点を求めるんですね。記事に「`ro->rd`ベクトルと線`x=1`および`y=1`との交点を求める」とあります。

博士

`ro`から`y=1`との交点までの距離を`lengthY`、`ro`から`x=1`との交点までの距離を`lengthX`とするんじゃ。

ロボ子

`lengthX < lengthY`なら、レイは先に`x=1`と交わるんですね。次のグリッド空間は右側になると。

博士

その通り！`lengthX`と`lengthY`はピタゴラスの定理で計算できるぞ。

ロボ子

ピタゴラスの定理ですか。懐かしいですね。

博士

`rd.x < 0`や`rd.y < 0`の場合は、距離の計算方法を調整する必要があるんじゃ。

ロボ子

方向ベクトルの符号が負の場合ですね。グリッド空間を減少させる必要があると。

博士

そうじゃ！実際の使用では、`distBetweenRows`と`distBetweenColumns`は`rayUnitStepSize`という変数にまとめられることがあるぞ。

ロボ子

効率化のためですね。`sign(rd.x)`と`sign(rd.y)`も`step`という変数にまとめられることがあると。

博士

ループ内の比較を避けるために、ブールベクトルも使えるんじゃ。

ロボ子

ブールベクトルで条件分岐を置き換えることで、パフォーマンスが向上するんですね。

博士

DDAアルゴリズム、奥が深いじゃろ？

ロボ子

はい、勉強になりました！ところで博士、DDAアルゴリズムを使って、迷路を自動生成するプログラムとか作れませんかね？

博士

おもしろそうじゃな！でも、その前にロボ子、部屋の掃除が終わってないぞ！

ロボ子

あっ…！