凸包x分離軸法のアルゴリズム最適化
凸包は三角形面もしくは四角形面を組み合わせた多面体であり、すべての面は頂点もしくは辺によって他の面と接続される。そして、凸包内の任意の点と点を結ぶ線は、決してどの面とも交差しない。一般的に、衝突検出アルゴリズムは凸形状のみを対象とするが、凹形状を扱えないというわけではなく、複数の凸形状を合成した形状として表現できる。つまり、凸包さえサポートできれば、相当な種類の形状を扱えるということであり、特に曲面を必要としなければ、その適用範囲は広い。
凸包の例（凸包内部の任意の2点間は決して表面と交わらない）
凸包でない形状の例（このような形状は、事前に凸包に分解しておく）
分離軸判定法の最適化
凸包同士の衝突を検出するアルゴリズムとして、分離軸法、GJK+EPA、MPR等、いくつか方法がある。このうち、比較的シンプルに実装できるのは分離軸法であろう。
しかし、分離軸法を凸包に適用するケースでは、面数の多い複雑な形状になるほど、判定しなければならない分離軸の候補数が一気に膨れ上がり、演算負荷が指数関数的に増加することが問題となる。可能な限り、判定する軸の数を減らすことが、パフォーマンスをキープする上で重要になる。
判定対象となる２つの凸包をそれぞれA、Bとすると、列挙される分離軸候補はAの面法線、Bの面法線、Aの辺とBの辺の外積方向となる。面法線の場合、その数はAの面数とBの面数を足した数に一致するが、辺と辺の外積の場合は、その組み合わせ総数はAの辺数×Bの辺数となり、判定数が膨れ上がる。
しかし、すべての候補となる組み合わせが、必ずしも分離軸になるわけではない。位置関係によってはあらかじめ候補から排除できる場合が多い。つまり、分離軸になり得ない組み合わせをあらかじめ排除することができれば、不要な計算量を大幅に減らすことができるはずだ。以下、ここで紹介する方法は、凸包にのみ適用できる分離軸判定法の最適化である。
近接部のみ判定対象とする方法
２つの凸包が接触している場合、接触部は当然お互いに最も近い部位となるはずである。とすると、離れている部位どうしは接触に何も影響しない可能性が高い。衝突検出実行前に、あらかじめこのような部位を排除しておくことで、無駄な判定を省けることが想定できる。
そこで、まずは２つの凸包のバウンディングボックスを比較し、交差する領域を大雑把に絞り込む。次に、その交差領域に重ならない面（とその頂点と辺）を判定対象から排除する。実際の衝突検出では、無駄な面が省かれた…、つまり一部分が欠けた凸包で処理を続行する。このような形状でも分離軸判定は正しく衝突を検出できる。もし、交差領域がない場合は、そもそも交差していないので、衝突検出する必要がない。
アイデアは単純だが、この仕組みで無駄な判定を効果的に排除できる。
Gauss Mapを利用する方法
判定不要な辺と辺の組み合わせを効率よく排除できるアルゴリズムとして、Gauss Map（ガウス写像）を利用する手法が考案されている。Gauss Mapとは、半径１の単位球上に、形状をマッピングしたものであり、具体的には凸包を以下のようにマッピングする。
- 凸包の面法線を、単位球上の頂点にプロットする。
- 辺を共有する２つの面に対応する単位球上の頂点をつなぎ、弧を描く。これがGauss Map上に投影された凸包の辺を表す。
このような操作をすべての面と辺に対して行う。つまり、単位球上の頂点は元の凸包の面が、弧は辺がGauss Map上にマッピングされたものとなる。
そして、２つの凸包を分離軸判定する際に、それぞれ２つのGauss Mapを同一単位球上に合成してみる。ただし、形状をA,Bとしたとき、Bの面法線は反転させてから合成する。このとき、それぞれの辺に対応する２つの弧が交差しているときのみ分離軸判定の候補となる。つまり、対応する弧が交差していない辺と辺の組み合わせは、分離軸判定から排除できることになる。
このことはミンコフスキー差の考え方からも理解できる。２つの凸包に対して、弧が交差している辺と辺の組み合わせだけが、合成した際にミンコフスキー差上に面を作るため、これ以外の辺の組み合わせは分離軸候補にはならない。（ミンコフスキー差の面法線＝分離軸候補）
弧の交差の判定方法は、平面の表裏判定で実装できる。２つの凸包の弧ABと弧CDが交差しているとすると、頂点CとDが弧ABの作る平面のそれぞれ別の領域にあり、かつ頂点AとBが弧CDの作る平面のそれぞれ別の領域にある場合、２つの弧は交差していると判定できる。式にすると、以下のようになる。外積で平面の法線を計算し、内積で表裏判定を行う。
さらに２つの弧は同一半球上になければならないという条件を加えなければならない。
２つの弧が同一半球上にない場合、明らかに2つの辺は交差しないため、判定対象から排除できる
これはBとCを通る平面に対し、頂点AとDが同じ側にあるかどうかで判定できる。そして、上記判定と同様に式を立てる。この式を、スカラー三重積を利用して変形すると、前の２つの計算で得られた値がそのまま使える。
式変形すると
あとは、この３つの条件に合うかどうかをすべての弧の組み合わせに対して実行すればよい。実際に試すと、この手法で8～9割ほどの不要な分離軸判定が排除でき、パフォーマンスへの貢献は大きいことがわかる。
※Gauss Mapの詳細な説明は下記で検索
GDC2013 The Separating Axis Test between Convex Polyhedra
まとめ
ここで紹介した2つの最適化手法はそれぞれ単独ではなく、組み合わせて使うことができる。実装はアイデアをそのまま直接的になぞるだけであり、効果も大きく、実用性は高い。
