ホーム＜ゲームつくろー！＜衝突判定編＜ OBBと点の最短距離
3D衝突編
その12 OBBと点の最短距離
前章（その11）で「AABBと点の最短距離」をやりました。この章ではさらに先に進んでOBB（有向境界ボックス：Oriented Bounding Box）と点の最短距離を考えて見ます。OBBは回転しているためちょっとだけ面倒なのですが、基本的な考え方はAABBと一緒です。
① 場合分けで「はみ出し部分」を計算するのが鍵
まず最初に、OBBの表し方を説明するために、線分をOBBに見立てて説明します。下の図をご覧下さい。
線分ABの上に「重心G」を定義します。これはABの中点に当たります。線分の向きは方向ベクトルvで表します。これは単位ベクトルとします。重心から線分の端までの長さ（＝線分の半分の長さ）をLと表します。重心を設けるのは3次元空間の直方体のOBBになった時にこの重心がちょうど直方体のど真ん中に来るためです。線分の長さの半分Lとするのは、計算上何かと便利なためです。線分の長さその物にすると「1/2」があちこちに出てきてちょっとやになります。
この前準備を踏まえて、線分と点の位置関係を表した次の図をご覧下さい。
これと似たような図は前章でも出てきました。その図を傾けた状態ですね。前回同様、今回も点の位置関係は3通りあります。線分ABの左端Aよりも左にある点P1についてはAP1の長さが最短です。線分ABの右端よりも右にあるP3だと最短距離はBP3です。そして、点P2の時は、線分ABとの垂線が最短距離となります。点P1や点P3の位置にある時、図の赤線の部分を求める必要が出てきます。ここを「はみ出し部分」と呼ぶ事にしましょう。はみ出し部分の長さ（もしくはベクトル）がわかると、直線ABへの垂線の長さ（ベクトル）を使ってピタゴラスの定理等で最短距離を算出できます。
はみ出し部分の長さを算出する前に、点がP1なのかP2なのかそれともP3なのかを見分ける必要があります。この場合分けは、点Pから直線ABに向けておりゃっと降ろした垂線の交点C1,C2,C3で判断できます。点Cが線分ABに含まれているか否かを見るわけです。そのためには、どうしてもベクトルの力を借りなければなりません。話はそれほど難しくありません。
線分の方向は方向ベクトルvで表されるとしました。このベクトルは単位ベクトルですから、それに線分の半分の長さLのを掛けると、ベクトルGBの長さと等しくなります。式で書くと、
GB = L * v
です。次にベクトルGBを用いてベクトルGC1を表してみます。点C1は直線AB上にありますので、これはベクトルGBを何らかの定数倍したものであることがわかります。つまり、
GC1 = s * GB = s * L * v
となります。このGC1の長さがGAの長さよりも長い時、s<-1となります（逆方向だからマイナスです）。点C2の位置関係の場合、ベクトルGC2の長さから-1<s<1となります。点C3ならばs>1です。つまり、このsを求めてその値がどの範囲にあるかで、3つの場合分けが出来ます。
では具体的にsを求める式を導出してしまいましょう。ベクトルGCはベクトルGPとPCの和で表現できます。うーん…図をご覧下さい(^-^;
上図のような関係にあります。高校の時にやったベクトルの基本ですね。ベクトルGCはs*GBでしたので、それを図内の式に代入すると、
s*GB = GP + PC
となります。ここでとびっきりの必殺技を使います。両辺のベクトルとGBの内積を取ってみます。
sGB・GB = (GP + PC)・GB
s*Dot(GB,GB) = Dot(GP,GB) + Dot(PC,GB)
Dotは内積を表します。ここで注目するのは一番右のDot(PC,GB)です。ベクトルPCはベクトルGBと垂直ですよね。つまり、この項は0になってしまうんです（垂直なベクトルの内積は0です）。また、左辺のように同じベクトルの内積は、そのベクトルの「長さのべき乗」になります。よって上式は、
s*Len[GB] = Dot(GP,GB)
s = Dot(GP,GB) / (Len[GB]*Len[GB])
と書き表せます。分母のGBの長さというのはLです。また分子のGBはL*vでした。よって、
s = L*Dot(GP,v) / (L*L)
= Dot(GP,v) / L
上の式には重心G、方向ベクトルv、長さLそして点の位置Pしかありません。よって、それらを機械的に上の式に代入すれば、sが簡単に出てきます。これで場合分けも簡単です。
② 「はみ出し部分」の計算式
sを求めることで、最初に示した図の場合分けができるようになりました。もう一度図を示します。
実は、はみ出し部分の長さは先ほど求めたsを用いると非常に簡単に求まります。例えばAC1を考えてます。GB=L*vであり、これにsを掛けるとGC1となります。
GC1 = s*L*v
これからAC1は、
AC1 = GC1-GA = GC1+GB = s*L*v + L*v = (s+1)*L*v
と算出できます。
BC3についても見てみましょう。BC3 = GC3-GBですから、
BC3 = GC3-GB = s*L*v - L*v = (s-1)*Lv
となります。「符号が微妙…」と思われるかも知れませんが、ここがうまいところなんです。AC1側のsは常にマイナス値です。よってsの絶対値を使って書き直すと、
AC1 = (-|s|+1)*L*v
になります。一方BC3側のsはプラスです。今BC3ではなくてC3Bだとしますと、
C3B = -BC3 = (1-s)*L*v = (-|s|+1)*L*v
となり、AC1側と全く同じになってしまいました！欲しいのはベクトルの長さですから、ベクトルの向きは気にする必要がありません。しかも、ベクトルvは単位ベクトルですから、この長さというのは掛けている係数そのものになります！！！つまり、はみ出した部分の長さというのは無条件に、
[はみ出した部分の長さ] = (1-|s|)*L ただし |s|>1の時のみ
と算出できます。嬉しいほど簡単になるんです。そして、これを踏まえると、OBBと点の最短距離も非常に簡単に算出できます。
③ OBBと点の最短距離
①で示した線分の表し方はOBBを見据えたものです。ここで、正当にOBBをこれで表現してみます。分かりやすいように2次元のOBBで見てみます：
何か複雑そうですが「はみ出し部分」で考えると簡単なんです。まず方向ベクトルv1に注目します。この方向に平行な線分はABで、はみ出している点はP1,P3そしてP4ですね（青い線で表されています）。このはみ出し部分は先ほどの導出式を使って、
[v1方向についてはみ出した部分の長さ] = (1-|s1|)*L1 ただし |s1|>1の時のみ
と計算が出来ます。次に方向v2について見ると、この方向に対してはみ出しているのは、P1、P2、P3です（赤い線）。これも、
[v2方向についてはみ出した部分の長さ] = (1-|s2|)*L2 ただし |s2|>1の時のみ
と、全く同様に計算が出来ます。結局2次元の長方形のOBBの場合、
最短距離 = Len[(1-|s1|)*L1*v1 + (1-|s2|)*L2*v2] ただし |s1|<1でs1=1、|s2|<1でs2=1とする
と計算が出来ます。Lenの中はベクトルです。最短の長さは、それぞれのはみ出した分のベクトルを足し算して合成ベクトルにしてしまってから計算した方が効率がよくなります。この考え方はそっくりそのまま3次元のOBBにも当てはめる事が出来ます。
ということで、3次元のOBBと点の最小距離を求めるプログラムは次のようになります。
3次元OBBと点の最短距離算出関数 FLOAT LenOBBToPoint( OBB &obb, Point &p )
{
D3DXVECTOR3 Vec(0,0,0); // 最終的に長さを求めるベクトル
// 各軸についてはみ出た部分のベクトルを算出
for(i=0; i<3; i++)
{
FLOAT L = obb.GetLen(i);
if( L <= 0 ) continue; // L=0は計算できない
FLOAT s = D3DXVec3Dot( &(p.GetPos()-obb.GetPos()), obb.GetDirect(i) ) / L;
// sの値から、はみ出した部分があればそのベクトルを加算
s = fabs(s);
if( s > 1)
Vec += (1-s)*L*obb.GetDirect(i); // はみ出した部分のベクトル算出
}
return D3DXVec3Length( &Vec ); // 長さを出力
}
OBBやPointが持つメソッドの意味は、そのままですから問題ないですよね。理論はなんだかこ面倒くさかったのですが、プログラムにするとこんなもんなんです。逆に言えば、これだけでOOBと点の位置関係を記述できるのですから嬉しいものです。
OBBと点の位置関係がわかると、OBBと球の当たり判定があっさりできます。求めた距離が球の半径よりも短かったら「衝突している」と判断すれば良いんです。通常のゲームにおいて、OBBと球の当たり判定ができると相当に柔軟な衝突判定を実現することができます。後はOBBとOBBの衝突ができれば、衝突の大きなステップをクリアしたようなものです。
