ホーム＜ゲームつくろー！＜衝突判定編＜ AABBと点の最短距離
3D衝突編
その11 AABBと点の最短距離
AABB（軸並行境界ボックス：Axis-Aligned Bounding Box）と点の最短距離を求めてみます。これは、後々のもう少し複雑な衝突に対する布石となります。
① AABB
軸並行境界ボックスとは、ワールド空間のXYZ軸に対して各辺が平行な直方体の境界図形を言います。例えば町並みの建物などはこれで表すと便利かもしれませんし、真上から見る3DのSTGに登場する自機や敵機をこの境界ボックスで管理しても良いでしょう。何だかんだで案外使い道のある境界図形です。AABBの各辺は軸に並行なので、座標を読むのがとても簡単です。
AABBと点の最短距離を考えるための布石とするため、まずは「線分と点の最短距離」を考えて見ます。
線分をAB、空間内の点をPとします（下図参照）。
ABはX軸に並行としましょう。右方向を正とするなら、Aの方がBよりも小さいわけです。さてこの時、上の3点に注目します。もし点のX座標がAよりも小さかったら（点P1）、線分までの最短距離は線分AP1となります。反対に点がBよりも大きければ(点P3)、最短距離はBP3です。そして、点がAとBの間にあるならば（点P2）、最短距離はfabs(P2.y - A.y)もしくはfabs(P2.y-B.y)となります（どちらでも同じです）。線分と点の距離は、この場合分けをする事で求める事が出来ます。試しに式に起こしてみましょう。
点の関係 長さ（べき乗） P1 P.x <= A.x (A.y-P.y)^2 + (A.x-P.x)^2 P2 A.x < P.x < B.x (A.y-P.y)^2もしくは(B.y-P.y)^2) P3 B.x <= P.x (B.y-P.y)^2 + (B.x-P.x)^2 = (A.y-P.y)^2 + (B.x-P.x)^2
上の表で、まず真ん中（P2）に注目してください。式にY軸成分しかありませんよね。つまり、点が線分の間にある場合、X座標の事を考えなくても距離が計算できるのが分かります。次に下段に注目です。軸並行なので、点Aと点BのY座標は同じ値になります。よって、太文字のように、点AのY座標でも計算が出来ます。この時、全ての段に(A.y-P.y)^2が出現します！これが場合分けの最適化に繋がります。つまり、点と線分がどの関係にあっても、とりあえずY成分の差のべき乗は計算します。そして、点のX座標がAよりも小さい時かBよりも大きいときだけX軸の差を計算に入れるようにします。
Point P; // 点
Segment Line; // 1次元線分
FLOAT SqLength = 0; // 距離のべき乗
// X軸の計算
if(P.x <= Line.min)
SqLength = (Line.x.min - P.x) * (Line.x.min - P.x); // Line.x.min = A.x
if(P.x >= Line.max)
SqLength = (Line.x.max - P.x) * (Line.x.max - P.x); // Line.x.max = B.x
// Y軸の計算（これは必ず必要です）
SqLength += (Line.y.min - P.y) * (Line.y.min - P.y)
これが、線分と点の距離の計算です。この最適化の感覚がAABBに繋がっていきます。
③ AABBと点の最短距離
線分と点の関係を2次元に拡張してみます。
まず各点のX座標に注目します。P1は左側、P3とP4は右側にあります。この場合境界ボックスの左端もしくは右端と点のX座標との差を考える必要があります。しかし、P2はAABBの間（＝線分ABの間）にありますので、X座標について考える必要がありません。ここまでは先ほどの線分と点の関係と全く同じですよね。
次にY軸方向を見てみます。点P1、P2、P3は境界ボックスの上端よりも上にあります。これは、上端と点のY座標の差を考える必要がある事を示しています。しかしP4は線分BCの間にありますから、Y軸との差は無視できます。これも「線分と点」の関係と一緒ですよね。このことから、AABBと点の距離において次の非常に非常に重要な関係を導けます。
『各軸において、点の軸座標がAABBの最小値以下、もしくは最大値以上だった時、点とそれらの差を考慮する。間だったら無視！』
これは3次元のAABBについても当てはまります。
以上から、3次元のAABBと点の最短距離を計算するプログラムは次のようになります。
3次元のAABBと点との最短距離 FLOAT LenAABBToPoint( AABB &box, Point &p )
{
FLOAT SqLen = 0; // 長さのべき乗の値を格納
int i;
for(i=0; i<3; i++)
{
// 各軸で点が最小値以下もしくは最大値以上ならば、差を考慮
if( p.Get(i) < box.GetMin(i) ) // i=0はX、1はY、2はZの意味です
SqLen += ( p.Get(i) - box.GetMin(i) ) * (p.Get(i) - box.GetMin(i) );
if( p.Get(i) > box.GetMax(i) )
SqLen += ( p.Get(i) - box.GetMax(i) ) * (p.Get(i) - box.GetMax(i) );
}
return sqrt(SqLen);
}
ここでAABB::GetMinメソッドはその軸でのAABBの最小値、AABB::GetMaxメソッドは最大値、Point::Getメソッドは引数の軸番号の値を取得する関数とします。軸を番号化すると何かと便利ですよ。このプログラムにおいて、計算結果がゼロになる事があります。それは「AABBの中に点がある時」です。その場合、3軸とも条件式に当てはまらなくなります。逆に言えば、このプログラムの戻り値によって、AABBと点の含有関係が分かるわけです。
上のプログラムは3次元用ですが、ある軸についてぺったんこにすれば2次元として考える事も出来ます（ちょっとだけ計算効率が落ちますが）。AABBと点の距離を計算できると、「AABBと球」の当たり判定が出きるようになります。球の中心点とAABBの距離を計算して、それが球の半径よりも短ければ衝突しているわけです。さらに、AABBをOOB（有向境界ボックス）に拡張すれば、OOBと点、OOBと球の関係を記述できるようになります。これにOOBとOOBの衝突が加われば、ちょっとしたゲームの衝突判定はだいたい済んでしまいます。その取っ掛かりとしてAABBと点の最短距離は重要なんです。
