スタッフBLOG

おはようございます。本日の当番、プログラマーのK.Yです。

処理を減らすための数学も６個目のお題になりました。
今回は当たり判定の処理をする時に役に立ちそうな話をしたいと思います。

といっても当たり判定全体の話ではなく、
その判定で使う処理のひとつである
「平面上の任意の点がそのポリゴンの中に入っているのかどうか」
についての話になります。

図で示すと以下のような感じになります。

この図で色の変わっているポリゴンが当たっているポリゴンです。

どのポリゴンに当たっているのかが分かれば
例えば移動するオブジェクトが地面や建物などにぶつかった際に、
その当たったポリゴンの法線を使うことで跳ね返りの計算をしたり
ぶつかった時のエフェクトを出す方向を決定することなどができます。

　
それでは、図１を見ながら、
ぶつかった点がどのポリゴンと当たっているかを調べていってみましょう。

方法としましては、ぶつかった点をＰ、ポリゴンの各頂点をＡＢＣとした時、
それぞれのベクトルの外積や内積を使うことで調べていきます。

ちなみに、外積や内積の計算は以下のようになります。

------------------------------------------------------------
２つのベクトルを
v1 = ( x1, y1, z1 )
v2 = ( x2, y2, z2 )
とする時

v1 v2 の外積 = ( y1 * z2 - z1 * y2,　… Ｘ
　　　　　　　　　　　z1 * x2 - x1 * z2,　… Ｙ
　　　　　　　　　　　x1 * y2 - y1 * x2 ) … Ｚ

v1 v2 の内積 = x1 * x2 + y1 * y2 + z1 * z2
------------------------------------------------------------

というわけで、まずはそれぞれの外積を計算します。

１：ベクトルＡＢとＡＰの外積
２：ベクトルＢＣとＢＰの外積
３：ベクトルＣＡとＣＰの外積

次にそれぞれの外積とポリゴンの法線が同じ方向に向いているのかを調べます。

４：１で求めた外積とポリゴンの法線との内積
５：２で求めた外積とポリゴンの法線との内積
６：３で求めた外積とポリゴンの法線との内積

この４・５・６で求めたそれぞれの内積の符号が同じ場合、
その点はポリゴンの中にあると判断できます。

しかし、これをそのまま使っていては処理負荷がかかってしまうので、
まずは処理の順番を変えたりしてみます。

例えば、上の順番を １→４→２→５→３→６ のように変えると、
５の判定でポリゴンの外にあると分かった時点で
以降の３・６を計算する必要がなくなり、
判定する対象のポリゴンを次に移すことができます。

これで少しは処理軽減はできた感じがしますが、
この場合でも６まで処理が行って初めて
ポリゴンの外だと判定されることもあるため、
まだまだ処理負荷としては重そうです。

次はこの計算を何か他の方法で処理の軽減ができないかを考えてみましょう。

　
ここからはゲームの仕様にもよりますし使いどころも限られてしまいますが、
例えばプレイヤーやＮＰＣなどのオブジェクトが地面の上を移動している時に
どのポリゴンの上に乗っているのかを判定する場面を考えてみます。

図２のようにＹ座標が０の地面の上にオブジェクトがいる時、
立っている座標がポリゴンの中にあるのかを同じように判定してみます。

まずは上と同じ１の計算をします。

１：ベクトルＡＢとＡＰの外積

　ベクトルＡＢ　　 = ( x1, 0, z1 )
　ベクトルＡＰ　　 = ( x2, 0, z2 ) とする時
　（両ベクトルともＹの値は０）

　ＡＢとＡＰの外積 = ( 0,　　　　　　　　　… Ｘ
　　　　　　　　　　　　z1 * x2 - x1 * z2, … Ｙ
　　　　　　　　　　　　　0 ) 　　　　　　　　… Ｚ

このようにして外積を計算してみましたが、
ここで求めた外積のうちＸとＺの値が０になっていることに注目します。

すなわち、ここで比較する必要があるのは外積の中でもＹの値のみになり、
わざわざ外積の計算でＸＹＺを求めなくても、それぞれのベクトルの
z1 * x2 - x1 * z2 の値を比較するだけで判定が可能になります。

そうなると、本来なら外積を求めた後で行なっていた内積の計算も
必要がなくなるため、さらなる処理軽減が可能になりました。

図２の場合、Ｙ座標が０という平らな地面での判定でしたが、
地面に傾斜がある場合でも、そのオブジェクトを真上から見た場合、
結局ＸＺ平面だけに注目すればいいことになり、
Ｙ座標を０として判定するのと同じ結果が得られるということになります。

場面としては限られてしまいますが、
「オブジェクトが地面の上を移動する時」
という条件を入れることで、なかなかの処理軽減ができました。

　
このように、ゲーム中には
「この条件の場合に限っては、この処理は省くことができる」
という場面が結構あったりします。

少しでも快適にゲームを動かすためにも、
省けそうな処理が無いかどんどん探していってみましょう。