--/--/--COLLADAは最近出てきた3Dフォーマットの一つで、有名メーカが協賛している点は数あるフォーマットの中でも変り種なのですが、野村XXの愛するLightWaveは蚊帳の外です。いうかNewtekの掲示板の書き込みを見ると、なんかどーでもいいよそんなのって雰囲気が漂ってました。それはともかく、無いものは作ってしまえというわけでPluginを作り始めました。あまりにもニッチな気がするので、国内に見切りをつけて(?)海外の皆さん向けにこっちのページで公開します。興味をもたれた方は覗いてやってください。技術的にどーというもんでもないので、黙々とコードを書き連ねるのみです。--/--/--ちょっと困ったバグがあるので修正記事をお待ち下さい(04/12/27)今回はOBBTreeによる衝突判定をXファイルで使ってみることにします。いっても、もはや前回でコアの部分は出来てしまっているので、さくっと実装するだけです。ベースはウマイハナシの「DirectX9のアニメーションな話」のサンプルを使います。若干コードを変更しましたが、ほぼ一緒です。とコメントを付けておきました。親子付けモデルからチャレンジ。内でメッシュからOBBTreeを作るだけです。衝突判定については、2つのモデルの全メッシュに含まれるOBBTree同士で判定を行えばOKです。メッシュに名前が付いていれば、特定のメッシュ間での衝突判定を行うこともできます。この辺はニーズに合わせて作ってください。以上で完成、楽勝ですね。ここまでだと簡単すぎて面白くないので、次はワンスキンモデルでやってみます。取り掛かる前に、モデルデータの持ち方についておさらいしておきましょう。親子付けモデルの場合、親子付けされたフレームにそれぞれメッシュがくっついています。ワンスキンモデルの場合親子付けされたフレーム(ボーンを表す)と一つのメッシュからできています。要は、メッシュがばらされているか、一つにまとまっているかの違いと言えます。ワンスキンモデルはこの一つのメッシュをボーンの移動に合わせて、変形させています。ボーンを動かしてみないと、メッシュの形状が決まらないので、まともにOBBTreeを作ろうと思ったら、変形するたびにOBBTreeを作り直す必要が生じます。そんな重い処理はやってられません。ここで改めてワンスキンモデルの挙動を観察してみると、ごく小さな領域である関節部分が滑らかに変形する以外は親子付けモデルと変わらないことが分かります。大半の場所の頂点は一つのボーンの影響しか受けていないと見なして構いません。腕の肉はやはり腕の骨によって移動するものです。擬似的な親子付け状態にしてから、OBBTreeを作ってあげます。メッシュを保持しているD3DXMeshContainer構造体の中にID3DXSkinInfo型のポインタ変数があって、これのメンバ関数にGetNumBoneInfluences、GetBoneInfluenceという奴がいます。前者でボーンの影響を受けている頂点数、後者で頂点のインデックス値とウェイト値が分かります。OBBTreeを作る時は3角ポリゴン単位で分割しなければならないので、3つの頂点が影響を受けているボーンのウェイト値を全部足して、その最大、つまり一番影響が大きいと考えられるボーンにそのポリゴンが所属していると見なします。このようにして、各ボーンに対してメッシュを分割し、そのメッシュからOBBTreeを作ってあげれば完成です。各ボーンのローカル座標系に変換してからOBBTreeを作らなければなりません。ボーンのボーンのオフセット行列はGetBoneOffsetMatrixで取得できます。一回OBBTreeを作ってしまえば、親子付けモデルもワンスキンモデルも等価に扱う事ができます。いうわけで、今回のソース。ロボット(LWからパチッてきた)が親子付けで、4号ちゃんがワンスキンです。毎度お約束ですが、エラーチェックは最低限であり、このサンプルの使用によるいかなる不幸も当方では責任を負いかねます。4号ちゃんのスカートを見ていると、OBBとモデルとのずれが見えると思います。逆にこの程度のずれが許容できるなら、使えるということですね。ちなみにOBBを実行時に作るよりも、Xファイルにユーザーデータな話のネタと合わせて、あらかじめ作っておいたOBBをXファイルに書いておく方がハッピーかと思います。今回のネタは、全自動で衝突判定をやれるという点が最大の魅力です。電波の缶詰は人材不足なので(笑)マンパワーの溢れる商用世界の場合、デザイナーさんに手作業でOBBを作ってもらった方が効率的なものになるでしょう。一度自動で作ったものを、手作業で修正するといったハイブリッド方式が実用的です。色々な事情を鑑みて、落しどころを見つけるのが、実は一番難しい気がします。--/--/--前回OBBツリーを作る所まで行ったので、続いて2つのOBBツリー間で衝突判定を行ってみます。2つのOBB同士の衝突判定を考えます。2つの箱A,Bが重なっていないことを保障するのは意外と簡単で、要は箱の影を観察するだけです。影が2つに分離していれば、箱がくっついているはずはありません。直線(=1次元)に落ちるものでも構いません。直線に落ちた影が分離しているかどうかの判定は、球の衝突判定に近いものになります。箱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ツリー同士(ツリー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の逆行列は回転行列の逆行列が転置行列になる性質を利用すると少ない計算量で求めることができます。SDRAM)ではD3DXMatrixInverseを使った方が計算が速いという結果が出ました。CPUに対する最適化の結果なのか...うーん?逆行列に限らず行列計算はD3DXを使った方が高速に動く場合が多いようです。そんなこんなで、今回のソース。いつものことながら、エラーチェックは最低限であり、このサンプルの使用によるいかなる不幸も当方では責任を負いかねます。次回はアニメーションするXFileにOBBで衝突判定をつけてみます。--/--/--3Dを扱う上で頭の痛い問題の一つに衝突判定があります。研究されているものの、今ひとつ決定打に欠けます。Box)、バウンディング球を使うものがありますが、一般的にはOBBが一番リーズナブルな手だと思います。OBBにチャレンジすることにしましょう。野村XXに似合わずアカデミックなお話なので間違っていたらご愛嬌。お勉強好きな貴方はこちらの論文を一読すると良いかと。英語が苦手な貴方&私は狩野さんの「3Dグラフィックス数学」を読むのが楽です。簡単に言うと、あるポリゴン群に対してどんな方向を向いていてもかまわないので、それをすっぽりと囲む、できる限り小さな直方体を作りましょうというのがOBBの手法です。この直方体をいかにして作るのかという所が腕の見せ所になります。ここでは、上記論文で紹介されている主成分分析を使うことにしましょう。主成分分析の詳しい話は、googleで引っ掛けるなり、本屋で統計解析の本を買ってくるなりしてください。要は、あるデータ群に対して、その現象を良く表す軸を見つけ出すというのが主成分分析です。古典的手法なので、問題の解き方も良く知られています。OBBではデータとはポリゴンの頂点群なので、x,y,zの3次元のデータが頂点の個数分存在します。それを使って分散共分散行列を作って、その行列の固有ベクトルを計算すると、OBBを表す3つの軸が得られます。ああっ、そこの人逃げないで(笑)大して難しい話ではありません。ソースにするとこんな感じ。Vertex配列に頂点データが入っていて、配列の長さがSizeになります。mは全頂点の平均値です。実対称行列なのでjacobi法で固有ベクトルを求めることができます。オンライン版(英語)はこちら。英語版とはいえ、無料でこの本が読めるのはありがたいですね。5000円位なんで日本語版さくっと買って、本棚に載せておくと賢く見えて素敵です。小難しい理屈が書いてありますが、jacobi法のソースだけを拝借します。先ほどの行列をjacobi法のソースに食わせると、3つの固有値と3つの固有ベクトルを吐き出してくれます。固有値が大きい固有ベクトルほどOBBの長い辺を表します。続いて、全頂点に対して固有ベクトルとの内積を計算して、その中から最大値と最小値を見つけ出します。固有ベクトルは単位ベクトルなので頂点と内積を取ると、固有ベクトルに頂点を射影した時の長さになります。よって最大値から最小値を引くとOBBの辺の長さが得られます。ついでに最大値と最小値を足して2で割ったものに固有ベクトルを掛けてあげれば辺の中点が得られます。3つの固有ベクトル全てで上記計算を行った結果、OBBの3つの辺の向きと長さ、中心が求まります。最後にこのOBBを使うために一つ行列を作っておきます。それはOBBを回転させて3辺をXYZ軸に平行にし、OBBの一つの頂点を原点に移動させるためのものです。|という行列で原点に移動され、3辺はXYZ軸に平行になります。この行列を使えば、ある点がOBBの中にあるかどうかを判定することができます。ある点を行列によって移動させた結果の座標(x,y,z)が、同様に移動されたOBBの中に入っているかチェックします。移動後のOBBはXYZ軸に平行なので、単にx,y,zと3辺の長さの大小を比較するだけでOK。これでOBBの作成は完了です。OBBが作れるようになったら、今度はOBBTreeを作りましょう。飛行機のような複雑なモデルを表すには単純すぎます。これはOBBを分割して、複数の小さなOBBにすれば解決できます。簡単な分割方法は、OBBの一番長い辺を2等分するようにOBBをぶった切る方法です。OBBを2つに分割した結果、それぞれのOBBに含まれる頂点を使って、再度OBBを計算しなおします。して1つのOBBが2つに、2つのOBBが4つに、4つのOBBが8つに...と、どんどん細かく分割していくことができます。一つのポリゴンを構成する3頂点は同じOBBの中にいなければならないので、ポリゴンの中心点が入っている方のOBBに3頂点全てを放り込みます。長い辺を2等分しても駄目だった場合は、残り2つの辺で再チャレンジし、それでも分割できない場合は、それ以上の分割をあきらめます。いうわけで、今回のソースです。いわゆる2分木でOBBTreeを表現しているので、再帰関数使っています。再帰が苦手な人はC言語の本を読み返しましょう。お約束ですが、エラーチェックは最低限であり、このサンプルの使用によるいかなる不幸も当方では責任を負いかねます。知恵熱が出てきたので、今回はここまで。次回は本題の衝突判定です。2003)という、いまいちバージョンの分かりづらい最新版SDKが出てきたので思わずインストールしてしまいました。今回のSDKには色々とHLSLのサンプルが入っていて、その魅力に勝てなかったらしいです。念のため魔砲都市のソースをコンパイルしなおすと、...コンパイルできません。マイナーアップデートでさえ下位互換を取らないとは思いませんでした。今回引っかかったコードはアニメーション関係ばかりでしたが、もしかすると他の部分もこっそり変更されているかも知れませんね。function...とか言っているので、そこらじゅうでconstをつけて回る羽目になりそうです。そんな訳で、HLSLで遊ぶ前に余計な仕事が増えてしまいました。ID3DXAnimationControllerを眺めるとかなり関数が増えたり、変更を受けたりしています。今回は個人的に引っかかった変更点だけを書いておきます。CreateMeshContainerの引数にconstが付きました。GetMaxNumMatricesがなくなりました。それに伴ってCloneAnimationControllerの第1引数にGetMaxNumMatricesの結果を渡していたのをGetMaxNumAnimationOutputsの結果を渡すようになりました。D3DXTRACK_DESCが変わりました。Priorityになりました。AnimTimeの順番が入れ替わってるので注意。SetTimeがなくなりました。それに伴ってAdvanceTimeが追加されました。これは個人的には気に入らない変更です。SetTimeは時間そのものを設定していましたのに対し、AdvanceTimeは前フレームからの差分の時間を渡すようになりました。差分の時間に負の値が許されないので、等価にはなりません。何が面白くないかというと、一つのオブジェクトを異なる時間で複数個レンダリングするのがやりづらくなったってことです。グローバルタイムの使用を止めて、トラック毎のローカルタイムを弄るようにすれば、なんとかなりますけど、あまりエレガントではないですね。SetTrackAnimTimeがなくなりました。それに伴ってSetTrackPositionが追加されました。ヘルプで間違ってSetTrackAnimationTimeと書かれていた挙句、また名前が変わりました。