スポンサーサイト

--年--月--日 --:--

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

GJK アルゴリズム 説明

2008年02月01日 01:51

結構立ちましたが、GJKについてようやっとまとめれたのでアップしたいと思います。
同じように悩んだ方の手助けになればいいかな?って思います。
[GJK アルゴリズム 説明]の続きを読む
スポンサーサイト

続々GJK

2008年01月10日 01:36

寝る前にちょっとだけ更新。
んでもって、軽めの説明。

GJKのキモとなっている部分は
・凸包同士が重なっているとき、ミンコフスキー差が原点を含む
・ミンコフスキー差を実際に求めなくても、サポート写像を利用することで、
 ミンコフスキー差と指定した方向の内積は求めることが可能
です。

侵入深度は別のアルゴリズムで処理するので、重なっているかどうかさえわかればいいわけです。
GJKアルゴリズムを技巧的にしている部分はクラメルの公式を再帰的に使った高速化の部分ですが、GJKアルゴリズムの本質ではありませんので、理解の妨げになるようなら無視してかまいません。

侵入深度を求める処理は面と原点との距離を求めるのを再帰的に行い、収束するのを待つだけです。


種明かしをすればなんとも単純なアルゴリズムですw

ってことで、次は絵なんかをはさみながら説明したいと思います。

続GJK

2007年12月19日 00:46

GJKアルゴリズムの全容がほぼわかりました。

・・・別に線形相補性問題といてねーじゃん。。。

単体なアフィン包(affine hull)の表面点はアフィン結合(affine combination)であらわされるのと、原点とアフィン包の最接近点は3次元なら4次元ベクトルになり、連立方程式を解いてアフィン結合の係数を求めてました。
実際、3点目まで求まった時点で、4点目はきちんと3次元上で求まりかつ、その時点で原点を含んでるかどうかわかるから最後まで求めなくていいわけですね。
どうせ侵入深度もとめるところは違うアルゴリズムで処理されるので。
侵入深度を求めるのに特化した最適化が施されてたわけです。
本当はきちんと最接近点を求めないとダメです。

クラーメルの公式を再帰的に利用している部分は連立方程式を解いてる部分ですね。
単体が4点(四面体)で出来てる場合、係数を求めるためには4×4の行列を解かないといけないわけです。
しかし単体が3点(三角形)で出来てる場合は、3×3の行列になり、この行列は4x4の行列にも利用できることから「再帰的に利用している」となっているわけです。

この辺はややこしいので、後でまとめます。


やってることは、凸解析の分野ですね。
別に線形相補性問題を解いてるわけじゃなくてちょっとがっかり('A`)
ただ、「原点を含む(もしくはもっとも近い)単体」の構成する点を求めていくところは、線形計画問題の内点法に近いのかな??
内点法はまだ勉強してないので、暇が出来たらちょっとリサーチします。


ってことで、後一回ぐらい続きそうw

GJKアルゴリズム

2007年12月14日 00:29

またまた、寝る準備に入る前に更新。
もうちょっと早くせなだめだなw

やっとGJKアルゴリズムの核がつかめてきました。
LCPを直接解いてないのね・・・。
コードを追ってみたところ、ペネトレーション(貫通)の深度を調べる際は三角形上の点(重心座標で表現)と原点の距離との最小化問題をラグランジュの未定乗数法で解いてました。
ミンコフスキー差で出来た凸多面体を降下法的に枝きりして、原点を囲む最小の四面体を求めた後に使うアルゴリズムだから、GJK本体の実装ではないので、これからGJK本体の実装を解明したいと思います('A`)

もうちょっと先が長そうだなぁ。。
クラメルの公式を再帰的に適応してる部分がいまいちわからない・・・。
元の論文はボリュームがありすぎて、英語がまったくわからない私には荷が重過ぎますw
ってことで、ソースを追ってみますよ、これ(・∀・)

Lemke法使って計算した方がいいかなぁ?って思ったけど、ラグランジュの方法の方が簡単だし誤差も出ないだろうからどうするか微妙。。。
Lemke法自体はラグドールとかの間接の拘束条件とかで使えるだろうから、決して無駄じゃないと思うけどさ・・・。

ついでに

2007年11月28日 01:17

自分用のしおりとして残しておきますw

前回言ったGJKアルゴリズムとペナルティー法を組み合わせるのは自分が思ってたよりも手軽にできました。
実装時間は大体4時間ぐらい?かな。
バネモデルを使った布シミュは作ったことがあったので早く実現できました。

ついでに用語の説明。
ペナルティー法っていうのは、物体同士の当たりが起こった際、侵食された(めり込んだ)分に比例した斥力を適応する一種のバネのことを指すようです。
かなり適当な説明ですがw

当然、場合によっては埋まりまくります。
また、たまに不自然な動きもしますw
しかし、どうせ適応するのはゲームなんで多めに見てくださいw

とりあえず、なんとなく物理シミュレーションもどきが出来たので、次はペナルティー法を使うのではなく、解析力学的な処理も実現したいと思います。
ODEで使用されてる方法です。ヤコビアンとか使うやつね。
前作ったシンプレックス法のプログラムも使えそうだし。多分w

ただ、その前に片付けないといけないこともあるので、しばらく先になりそうです('A`)


最近の記事


上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。