スポンサーサイト

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

上記の広告は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
スポンサーサイト


コメント

    コメントの投稿

    (コメント編集・削除に必要)
    (管理者にだけ表示を許可する)

    トラックバック

    この記事のトラックバックURL
    http://angra.blog31.fc2.com/tb.php/112-e186e70e
    この記事へのトラックバック


    最近の記事


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