整数区画に飛ばしたレイが通った区画を列挙してく例えばマインクラフトのように3Dゲームだけれども立方体が単位になっているゲームでは、置かれている物の位置が整数座標で表現されます。岩の位置座標が(3,6,10)という感じです。キャラクタの移動などは整数単位という事はなくて、いつも通りの浮動小数点だったりします。いう世界で例えばある浮動小数点座標からレイを飛ばして、置かれている物をピッキングしたいという状況を考えてみます。2Dで考えてみよういきなり3Dで考えると頭がぐるぐるしてくるので、まずは2Dで理屈を考えてみます。整数区画の中でレイを飛ばすというのは下図のような状況です:S地点からレイをGまで飛ばしています。この時このレイは(-2,0)、(-1,0)、(0,0)、(0,1)、(1,1)、(2,1)の区画をこの順番で通って行きます。これらのどこかに対象物があれば、このレイは先の順番で一番最初に見つかる対象物と衝突する事になります。レイの長さが凄まじく長くなければ(レイが通った区画が何千もあるとか)、衝突物を先頭から線形で検索しても大したコストにはなりません。この順番をどうやって取得していけば良いのでしょうか?S地点からGへ向かって進んでいくと「区画の境界」を必ずまたぐ事に気が付きます。上の図の場合、またいだ境界の先にある区画は必ずレイが通っています:黄色い座標がその境界線上の交点です。これを探っていけば良さそうです。S地点からスタートしてみましょうか。境界交差テスト上図のS地点付近を拡大します:S地点は区画(-2,0)に所属しています。ちなみにこの整数座標は区画の左下の小数座標とシンクロしてます。これ、後で大事になってきますので今からルールとして定めておきます。レイは右上に伸びています。このレイがどの境界線と最初に衝突するのか?これはSが所属している区画を囲む境界線以外はありません。レイは右上に向かっているので、その中でも右側の境界線(X-Side)と上の境界線(Y-Side)がその候補に挙がります。上図ではX-Sideと交差しているのがわかりますが、地点Sの位置によってはY-Sideと先に交差する事もあり得ます。どちらが先に交差するかは、それぞれの黄色い交差点までの距離を比較すれば良さそうです。距離が近い方の黄色い点を含んでいるのが欲しい境界線です。そこで、ベクトルの性質をうまく利用してみましょう。地点Sからスタートして右上に向かうベクトルVは、と表せます。ここから上のレイを含む線分上の任意の点Pは、となります。aは任意の数値で0≦a≦1の範囲ならレイ上になります。とあるaの値の時にX-Side側の境界線上に達しますし、別のaの値でY-Side側の黄色い点の座標にもなります。上の図の場合、X-Side側のaの方がY-Side側よりも値が必ず小さくなります。これが肝です!上の式を成分別に書き直してみましょう:上のPx(a)は黄色い点のX座標、Py(a)はY座標になります。Sx、Vxは既知の値、と言う事は例えばX-Side上にある黄色い点の座標は、Px(a)=-1が確定していますから、と黄色い点に達するためのaの値が求まってしまいます。同じ事はY-Sideにある黄色い点にも言えて、Py(a)=1がわかっていますので、とY-Side側の黄色い点に達するまでのaの値もわかります。X-Side、Y-Side双方のaが求まるのですから、後はこれを比較して小さい方のaの境界線を採用すれば良いんです。境界線を採用したら区画も決まります。Y-Side側だったらY座標側をプラス1すれば良いのは言わずもがなです。これで判定が一巡しましたので、次の通過区画の検索に移ります。上図のように先程と同様に区画(-1,0)に対してX-Side側とY-Side側が境界線の候補です。双方の境界線上に交点が存在しています。先と全く同じようにPx(a)=0、Py(a)=1を代入して双方のaを計算、比較して小さい方の境界線を採用します。上の図だとまたX-Sideですね。X-Sideをまたいだ区画(0,0)が採用となります。後は同じ事を地点Gまで繰り返すだけです:計算を繰り返すといつかX-Side及びY-Side上の交点を求めた時に算出されるaが1.0以上(レイを越えてしまう)ので、そこで計算終了となります。この方法ではいくつかの例外に対処しておく必要があります。例外の一つ目は交点が「角」にある場合です。X-Side、Y-Sideどちらのaも同じ値になった場合に交点は区画の角に位置してしまいます。この場合、X-Side側とY-Side側の両方が含まれる事になるでしょう。角を含む区画も採用となります:このため、衝突区画を順に追ってレイとの衝突を検知する時に、上の場合は3つの区画が同時に衝突している事を知らせる必要があります。「角の時にはX-Side、Y-Side側は無視してもいいんじゃない?」という考えもありますが、そうすると角に「衝突しない点」が生まれてしまいます。角に向けて弾を発射したらX-Side、Y-Sideどちらのオブジェクトにも当たらなかったという状況が生まれてしまいますので、双方は採用した方が無難です。例外その2はレイが軸に平衡の場合です。黄色い点の座標を求める時の式を再度見てみます:aを計算する時に分母にレイの方向ベクトルの各成分が存在しています。これが0だとaは無限大に吹っ飛んでしまいます。数学上では問題ありませんが、プログラム上では好ましくありません。対処は簡単で、VxかVyが0だったらaの値をプログラム計算上で取りうる最大の値にしてしまいます。すれば確実に他方が採用されます。VxやVyに極小な値を入れておくというのも考えられますが、方向ベクトルを意図的に曲げると例えば地点Sが境界線上にある場合に計算誤差が出る可能性があります。このようにかなり簡単で逐次的にレイが通る区画をその順番で列挙して行けるのですが、実はこのままだと不都合が起こるパターンがあるんです。それは「方向ベクトルVの成分のいずれかがマイナス」だった場合です。下図をご覧ください:S地点から2つのレイが飛んでいます。右側はベクトルVのX成分がプラスの場合、左側はマイナスの場合です。先程までのアルゴリズムはレイが右上(ベクトルVのX,Y成分いずれもプラス)のケースで、X-Sideは暗黙に「所属区画のX成分+1」でした。X成分がマイナスの場合、上図の-X-Sideの座標は「所属区画のX成分」そのものです。この場合分けが必要になってしまうわけです。これ、些細に見えるかもしれませんが、Y成分側も同じことが言えますし、3Dに拡張するとZ成分も入ってきます。ある時はX-Sideが+1で、また別の時はZ-Sideはそのまま...みたいなのって、ちょっとやばそうですよね。そこで、アルゴリズムは最初から見てきた「すべての成分がプラス」の物しか使いません!ではレイのベクトルの成分にマイナスが入って来たらどうするか?それは「鏡写し」にしてしまうんです。下図をご覧ください:上の左側がレイの方向ベクトルのX成分がマイナスの場合です。区画内の数値は区画座標のX成分です。これをY軸でそっくりそのまま本当に鏡写ししたのが上の右側。方向が右上に直ったのがわかりますね。これを元の座標に戻したのが下の方の図です。区画座標の値の絶対値が変わっていて、1減ってますね。1」という計算例です。0.6)から始まっています。方向ベクトルの成分がマイナスだった場合、まずその成分をプラスにしてしまいます。次に始点(終点も)の同成分の符号も反転します。後は先のアルゴリズムで区画を検索していきます。衝突が見つかった区画の座標の同成分は先の計算式で変換します。);}}こんな感じです。3Dに拡張ここまで2Dの区画について見てきました。これは3Dに簡単に拡張できます。始点や終点が3次元になって、境界としてZ-Sideが追加されるだけです。各境界に達するまでの係数aの求め方も全く一緒です:求めた3つのaのうち一番小さいaが直近の境界面です。例外処理も基本的に一緒ですが、パターンがちょっと増えます。az)とした時、一番小さい物が2個及び3個出てくることがあります。ax,ayが同じ値になった場合、これは区画(立方体)のX-SideとY-Sideがクロスする辺に境界交点がある事を意味します。azがすべて同じ値になった時、これは境界交点が立方体の角にある事を意味します。レイと衝突している2D整数領域。レイと衝突している2D整数領域。0;}結果は第3引数の整数座標の配列の配列にどばーっと返ります。この配列のが示す区画の座標を順次調べていけば、レイが最初に衝突するオブジェクトがわかります。