j3259の日記： 当たり判定

地形を読み込んだはいいけど、なにしろデカいので当たり判定をどうするか考えないといけない。
球体とか直方体でおおまかな当たりをつけて、当たったら三角形の総当りみたいな方法でお茶を濁すわけにはいかない。

人物は高めの身長でも縦横高さ 2m がせいぜい。読み込んだ地形のデータは東西に 9310 m、南北に 13950 m ある。当然毎回当たる事になる。頂点数は 931 x 1395 の 1% つまり 12987点取ったので、三角形の数も大体そのぐらいだと思う。人物は 581三角形。総当りすると酷いことになる。7545447回二つの三角形が交差するかを調べることになる。
ここで BSP を使うと計算数が一気に減る。人物と地形がそれぞれ一つの三角形だけ交わってると仮定する。人物と地形だと地形の方が大きいので、とりあえず人物を十分に大きい直方体 B_B0 で近似する。地形を包む大きさの直方体を B_A0 として、B_B0 がその中に入るのを確認。次に B_A0 を長辺で二分にした B_A1、B_A1' が B_B0を含むかを計算する。仮定によりどっちか片側にのみ含まれて地形の半分を無視できる。こうやってどんどん地形を半分に切っていけば log₂(12987) = 14回半分に割るだけでいい。ここで最終的に地形側で B_B0 と交差する三角形が T_{0 .. 9} まで十個ぐらいあるとする。それぞれに対して今度は B_B0 を二分していって最終的にどの三角形同士が交差するかを求める。log₂(581) = 10。半分に割った時には左右比べる必要があるから合計で 28回の直方体同士の交差判定、10 * 20 の直方体と三角形の交差判定で 228回分の計算に数が減るわけだから 7545447回の三角形交差の比較よりは現実味を帯びてくる。