COLLADAは最近出てきた3Dフォーマットの一つで、有名メーカが協賛している点は
数あるフォーマットの中でも変り種なのですが、野村XXの愛するLightWaveは蚊帳の外です。
というかNewtekの掲示板の書き込みを見ると、なんかどーでもいいよそんなのって雰囲気が漂ってました。
それはともかく、無いものは作ってしまえというわけでPluginを作り始めました。
あまりにもニッチな気がするので、国内に見切りをつけて(?)海外の皆さん向けにこっちのページで公開します。
興味をもたれた方は覗いてやってください。
技術的にどーというもんでもないので、黙々とコードを書き連ねるのみです。

ちょっと困ったバグがあるので修正記事をお待ち下さい(04/12/27)

今回はOBBTreeによる衝突判定をXファイルで使ってみることにします。
といっても、もはや前回でコアの部分は出来てしまっているので、さくっと実装するだけです。
ベースはウマイハナシの「DirectX9のアニメーションな話」のサンプルを使います。
DirectXのバージョンをDirectX 9.0 SDK Update (Summer 2003)に上げたのに伴って、
若干コードを変更しましたが、ほぼ一緒です。
OBBTreeに関して追加した部分は、// added for OBBTree とコメントを付けておきました。
まずは、親子付けモデルからチャレンジ。
CAllocateHierarchy::CreateMeshContainer 内でメッシュからOBBTreeを作るだけです。
衝突判定については、2つのモデルの全メッシュに含まれるOBBTree同士で判定を行えばOKです。
CD3DXObject::CheckCollision として追加しました。
メッシュに名前が付いていれば、特定のメッシュ間での衝突判定を行うこともできます。
この辺はニーズに合わせて作ってください。
以上で完成、楽勝ですね。
ここまでだと簡単すぎて面白くないので、次はワンスキンモデルでやってみます。
取り掛かる前に、モデルデータの持ち方についておさらいしておきましょう。
親子付けモデルの場合、親子付けされたフレームにそれぞれメッシュがくっついています。
一方、ワンスキンモデルの場合親子付けされたフレーム(ボーンを表す)と一つのメッシュからできています。
要は、メッシュがばらされているか、一つにまとまっているかの違いと言えます。
ワンスキンモデルはこの一つのメッシュをボーンの移動に合わせて、変形させています。
つまりボーンを動かしてみないと、メッシュの形状が決まらないので、
まともにOBBTreeを作ろうと思ったら、変形するたびにOBBTreeを作り直す必要が生じます。
さすがにそんな重い処理はやってられません。
ここで改めてワンスキンモデルの挙動を観察してみると、
ごく小さな領域である関節部分が滑らかに変形する以外は親子付けモデルと変わらないことが分かります。
大半の場所の頂点は一つのボーンの影響しか受けていないと見なして構いません。
もちろんモデルによって様々な例外もあるでしょうが、
人体モデルを例に取ると、ひざを曲げたからと言って腕の肉が移動することはないわけで、
腕の肉はやはり腕の骨によって移動するものです。
そこで、全ボーンのうち最も強く影響を受けているボーンに頂点が所属していると考えてメッシュを分割し、
擬似的な親子付け状態にしてから、OBBTreeを作ってあげます。
メッシュを保持しているD3DXMeshContainer構造体の中に
ID3DXSkinInfo型のポインタ変数があって、これのメンバ関数に
GetNumBoneInfluences、GetBoneInfluenceという奴がいます。
googleで検索してみても、MSのサイトくらいしか引っかからないので、
世界中で自分しか使ってないんじゃないかという不安に駆り立てられますが、
前者でボーンの影響を受けている頂点数、後者で頂点のインデックス値とウェイト値が分かります。
OBBTreeを作る時は3角ポリゴン単位で分割しなければならないので、
3つの頂点が影響を受けているボーンのウェイト値を全部足して、
その最大、つまり一番影響が大きいと考えられるボーンにそのポリゴンが所属していると見なします。
このようにして、各ボーンに対してメッシュを分割し、そのメッシュからOBBTreeを作ってあげれば完成です。
注意点としては、頂点座標がワールド座標系になっている(?)ので、
各ボーンのローカル座標系に変換してからOBBTreeを作らなければなりません。
ボーンのボーンのオフセット行列はGetBoneOffsetMatrixで取得できます。
一回OBBTreeを作ってしまえば、親子付けモデルもワンスキンモデルも等価に扱う事ができます。
んー、実に便利。
というわけで、今回のソース。
ロボット(LWからパチッてきた)が親子付けで、4号ちゃんがワンスキンです。
毎度お約束ですが、エラーチェックは最低限であり、
このサンプルの使用によるいかなる不幸も当方では責任を負いかねます。
4号ちゃんのスカートを見ていると、OBBとモデルとのずれが見えると思います。
逆にこの程度のずれが許容できるなら、使えるということですね。
ちなみにOBBを実行時に作るよりも、Xファイルにユーザーデータな話のネタと合わせて、
あらかじめ作っておいたOBBをXファイルに書いておく方がハッピーかと思います。
今回のネタは、全自動で衝突判定をやれるという点が最大の魅力です。
なにせ電波の缶詰は人材不足なので(笑)
マンパワーの溢れる商用世界の場合、デザイナーさんに手作業で
OBBを作ってもらった方が効率的なものになるでしょう。
一度自動で作ったものを、手作業で修正するといったハイブリッド方式が実用的です。
衝突判定は、ポリゴン数、精度、速度、メモリ、(&人件費)の要求等々、
色々な事情を鑑みて、落しどころを見つけるのが、実は一番難しい気がします。
何年か後にはCPUパワーごり押して、ボクセル単位の判定を行う時代になってないかなーとか
期待しています、果たして？

前回OBBツリーを作る所まで行ったので、続いて2つのOBBツリー間で衝突判定を行ってみます。
まずは、2つのOBB同士の衝突判定を考えます。
2つの箱A,Bが重なっていないことを保障するのは意外と簡単で、要は箱の影を観察するだけです。
影が2つに分離していれば、箱がくっついているはずはありません。
影というと、直感的に平面(=2次元)に落ちるものを想像してしまいますが、
直線(=1次元)に落ちるものでも構いません。
直線に落ちた影が分離しているかどうかの判定は、球の衝突判定に近いものになります。
影を落とす直線(以下、分離軸)をL、
箱Aの3軸の向き(単位ベクトル)をA1,A2,A3、その長さをa1,a2,a3、
同様に箱Bの3辺の向きをB1,B2,B3、その長さをb1,b2,b3、
箱の中心同士を結んだ線分をTとすると、
箱Aの中心と影が最長になる頂点を結んだ線分の影の長さraは|a1A1L|+|a2A2L|+|a3A3L|で、
箱Bの中心と影が最長になる頂点を結んだ線分の影の長さrbは|b1B1L|+|b2B2L|+|b3B3L|で、
Tの影の長さtは|TL|で表されます。
この辺は絵で見た方がわかり易いので、こちらの論文のFigure2を見ましょう。
球の衝突判定では、中心間の距離と半径で判定する所を、
OBBではtとra,rbを使って判定し、t>ra+rbであれば衝突していないことが分かります。
ここで少し厄介なのが、t<=ra+rbだからといって必ずしも衝突しているとは言い切れない点です。
ある方向から落とした影が重なっていても、他の方向から落とした影が分離していれば、
衝突していないことになります。
では、一体幾つの方向の影をチェックすれば充分なのかというと実は15パターンで済みます。
昔の偉い人がそういっているのだから間違いありません。
偉い人が言うには分離軸は、箱Aの3軸、箱Bの3軸、箱Aと箱Bの軸同士の外積9本(=3x3)の
計15パターン選べば良いのだそうです。
というわけで、t>ra+rbであるかどうかを各分離軸について15回計算すれば判定できます。
しかし、この計算を馬鹿正直に行う必要はありません。
前回OBBTreeを作る時にOBBの3軸をXYZ方向に揃える行列を作ってあります。
一旦揃えてしまえば、3軸が(1,0,0),(0,1,0),(0,0,1)と0と1のみで
表現されるので、t>ra+rbの計算をかなり省略する事ができるようになります。
ついでに分離軸が外積の場合は、内積と外積の関係式(PxQ)・R=(RxP)・Q=(QxR)・Pとか
箱Aの2軸の外積は残る1軸になるとかいった式整理を行うと、外積計算をする必要がないことも分かります。
お暇な方は紙と鉛筆でちょちょいと計算してみると面白いかもしれません。
お忙しい方はソースコードをご覧下さい。
これで2つのOBB同士の衝突判定ができるようになったので、
次は2つのOBBツリー同士(ツリーA,ツリーB)の衝突判定に移ります。
ぶっちゃけ、総当りで全てのOBBの組み合わせを試してやれば判定できます。
もちろんそんな事をすれば、OBBの数が増えると酷い目にあうのは目に見えているので、
2分木の特徴を生かして、枝刈をしながら探索します。
ツリーは最初1つのOBBから始まって、それを2つに細分化したもの、
さらに4つに細分化したもの…、という風に作られているので、
ある細分化レベルで衝突していないと判定されれば、
それよりも細かく分けたOBBをチェックする必要はなくなります。
不要なチェックを避けながら、2つのOBBツリーの最も細分化されたレベル同士で
衝突が起こっているのが分かれば、無事チェック終了になります。
再帰でさくっと書けるので大して難しくありません。
ただし、衝突判定を行いたいオブジェクトが移動している場合、
OBBも移動させなければ正しい判定ができません。
ワールド座標系でツリーAが行列matAで移動され、ツリーBが行列matBで移動されている時、
ツリーAのローカル座標から眺めたツリーBの移動は、matAの逆行列とmatBの乗算で表されます。
この行列を使ってツリーBに含まれるOBBを全て移動させてから判定を行えばOKです。
余談ですが、回転と平行移動を表す行列matAの逆行列は
回転行列の逆行列が転置行列になる性質を利用すると少ない計算量で求めることができます。
ところが面白いことに、我が家の環境(Pen4 2G SDRAM)ではD3DXMatrixInverseを使った方が
計算が速いという結果が出ました。
CPUに対する最適化の結果なのか…うーん？
逆行列に限らず行列計算はD3DXを使った方が高速に動く場合が多いようです。
そんなこんなで、今回のソース。
いつものことながら、エラーチェックは最低限であり、
このサンプルの使用によるいかなる不幸も当方では責任を負いかねます。
次回はアニメーションするXFileにOBBで衝突判定をつけてみます。

という行列で原点に移動され、3辺はXYZ軸に平行になります。
この行列を使えば、ある点がOBBの中にあるかどうかを判定することができます。
ある点を行列によって移動させた結果の座標(x,y,z)が、同様に移動されたOBBの中に入っているかチェックします。
移動後のOBBはXYZ軸に平行なので、単にx,y,zと3辺の長さの大小を比較するだけでOK。
とにもかくにも、これでOBBの作成は完了です。
OBBが作れるようになったら、今度はOBBTreeを作りましょう。
OBB自体は只の直方体なので、テレビのようなポリゴンモデルには充分ですが、
飛行機のような複雑なモデルを表すには単純すぎます。
これはOBBを分割して、複数の小さなOBBにすれば解決できます。
一番簡単な分割方法は、OBBの一番長い辺を2等分するようにOBBをぶった切る方法です。
OBBを2つに分割した結果、それぞれのOBBに含まれる頂点を使って、再度OBBを計算しなおします。
かくして1つのOBBが2つに、2つのOBBが4つに、4つのOBBが8つに…と、
どんどん細かく分割していくことができます。
ただし、一つのポリゴンを構成する3頂点は同じOBBの中にいなければならないので、
ポリゴンの中心点が入っている方のOBBに3頂点全てを放り込みます。
あと、分割した結果、全ての頂点が片側のOBBに入ってしまっては分割した意味が無いので、
一番長い辺を2等分しても駄目だった場合は、残り2つの辺で再チャレンジし、
それでも分割できない場合は、それ以上の分割をあきらめます。
というわけで、今回のソースです。
いわゆる2分木でOBBTreeを表現しているので、再帰関数使っています。
再帰が苦手な人はC言語の本を読み返しましょう。
お約束ですが、エラーチェックは最低限であり、
このサンプルの使用によるいかなる不幸も当方では責任を負いかねます。
そろそろ知恵熱が出てきたので、今回はここまで。
次回は本題の衝突判定です。

追記 04/03/23 mについての記述が抜けていたので追加