« 実りの秋とたまるもの | トップページ | フリーゲーム »

2010年10月28日 (木)処理を減らすための数学6

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

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

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

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

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

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

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

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

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

------------------------------------------------------------
2つのベクトルを
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
------------------------------------------------------------

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

1:ベクトルABとAPの外積
2:ベクトルBCとBPの外積
3:ベクトルCAとCPの外積

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

4:1で求めた外積とポリゴンの法線との内積
5:2で求めた外積とポリゴンの法線との内積
6:3で求めた外積とポリゴンの法線との内積

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

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

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

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

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

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

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

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

1:ベクトルABとAPの外積

 ベクトルAB   = ( x1, 0, z1 )
 ベクトルAP   = ( x2, 0, z2 ) とする時
 (両ベクトルともYの値は0)

 ABとAPの外積 = ( 0,         …
            z1 * x2 - x1 * z2, …
             0 )         …

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

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

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

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

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

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

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

follow us in feedly
result = encodeURIComponent( "http://www.accessgames-blog.com/blog/2010/10/post-6853.html" );document.write( "result = " , result );&media=https%3A%2F%2Ffarm8.staticflickr.com%2F7027%2F6851755809_df5b2051c9_z.jpg&description=Next%20stop%3A%20Pinterest">

| | コメント (0) | トラックバック (0)

« 実りの秋とたまるもの | トップページ | フリーゲーム »

プログラマー」カテゴリの記事

コメント

コメントを書く



(ウェブ上には掲載しません)


コメントは記事投稿者が公開するまで表示されません。



トラックバック


この記事へのトラックバック一覧です: 処理を減らすための数学6:

« 実りの秋とたまるもの | トップページ | フリーゲーム »