スポンサーサイト

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

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

続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年12月12日 00:31

寝る前に更新。
もうちょっと早い時間にやればいいんだけどさw

この前、線形相補性問題(LCP)のことについてちょっとだけ触れてましたが、つい先日LCPを解くプログラムが完成しましたー。
最後、2,3日詰まった箇所は相補性行列(かってに命名)と対応する解の符号が食い違ってたのが問題でした('A`)
ちゃんと意味を確かめながらプログラムしないとダメだね、やっぱり・・・。

そんなわけで、レムケ法(Lemke's Algorithm)を使ってLCP解きました。
内点法じゃないのは、内点法だと2次と3次なら4~5回で収束が期待できるけど、1次の問題だと50回ぐらい適応しないと収束できないこともあるからです。
どうせ、3次元で拘束条件が4つの行列(スラック変数と人為変数入れるから7行11列になる)を解くだけだから、内点法とそれほど変わらないはず。
拘束が1000とかだとさすがにきついけどね。

んで、レムケ法で線形計画問題といてみたら、見事解けました。
(この場合、2次の係数を0とすればOK)
ただ、前回作ったシンプレックス法のプログラムは間違った答えを出すパターンがあることが発覚。
結局、線形計画問題もレムケ法で解くことになりそうですw
レムケ法のC++での実装は見つからなかったから、こっちを公開できればなぁと思います。


さて、たまには違う話も。
つい先日、部屋があまりにも乾燥するので、ネットで加湿器を買っちゃいましたヽ(*´ω`*)ノ
買ったのは前々からほしかったチムニー。

こんなヤツです
chimney


早く届かないかなぁーヽ('∀`)ノ


最近の記事


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