続GJK

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

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

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

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

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


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


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

GJKアルゴリズム

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

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

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

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

レムケ法とチムニー

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

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

そんなわけで、レムケ法（Lemke's Algorithm)を使ってLCP解きました。
内点法じゃないのは、内点法だと２次と３次なら４〜５回で収束が期待できるけど、１次の問題だと５０回ぐらい適応しないと収束できないこともあるからです。
どうせ、３次元で拘束条件が４つの行列（スラック変数と人為変数入れるから７行１１列になる）を解くだけだから、内点法とそれほど変わらないはず。
拘束が１０００とかだとさすがにきついけどね。

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


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

こんなヤツです



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