スポンサーサイト

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

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

GJK アルゴリズム 説明

2008年02月01日 01:51

結構立ちましたが、GJKについてようやっとまとめれたのでアップしたいと思います。
同じように悩んだ方の手助けになればいいかな?って思います。
実装は簡単なんですけど、この記事用のサンプルは組んでません!
ヒマが出来て組めたらアップします。



GJK アルゴリズムは凸多面体同士が重なっているかどうかを調べるアルゴリズムです。
どれだけめり込んだか?を調べるアルゴリズムは Johnson's Distance アルゴリズムっていう別のアルゴリズムになりますが、
やっていることは、非常に良く似ています。

まず、GJK アルゴリズムの前提になっている、ミンコフスキー差について解説します。
ミンコフスキー差というのは、2つの物体の差の Swept Volume になります。
要するに、物体AとBがあった時に、B を原点で反転したもの(原点対称)を物体 A の周り(表面)で
移動させたときに生じる領域のことです。

図にすると一発でわかると思いますので、図にしてみます。
便宜上、2次元で表現します。

物体A(五角形)とB(三角形)
minkowski1.png


物体B を原点中心にして反転
minkowski2.png


反転した物体Bを原点を軸に、物体Aの周りを移動させる。
minkowski3.png

minkowski4.png


物体BがAの周りを移動して出来上がった領域が
minkowski5.png


ミンコフスキー差(A∪-B)になる。
minkowski6.png


また、凸包同士のミンコフスキー差は凸包になります。
少し考えれば当たり前ですね。
凹んでる場所がない物体の周りを同じく凹みがない物体が移動したところで、凹む部分が出来るわけないです。


さて、このミンコフスキー差、重要な性質があります。
それは、「重なっている物体のミンコフスキー差は原点を含む」という性質です。

要するに、凸包がぶつかっているかどうか?はミンコフスキー差が原点を含んでいるかどうか?の問題に摩り替えることが出来るわけです。
けれども、毎回ミンコフスキー差を求めるのは処理が重くて話になりません。
そこで、サポート写像というものを利用します。

これは、ミンコフスキー和(凸包)のある方向の写像(内積)はミンコフスキー差を形成する凸包Aと凸包Bのそれぞれの写像の和に等しいということです。
要するにある方向のベクトルを v とすると、、、
(A∪-B)・v = A・v - B・v (ミンコフスキー差なので、B を -B としている。ミンコフスキー和なら (A∪B)・v = A・v + B・v )
ということです。

図にすると、、、
support.png

この A・v の部分と B・v の部分を引いたものが (A∪-B)・v になっているわけです。

このサポート写像を利用すれば、ミンコフスキー差のある方向のベクトルの写像を求めたいとき、
凸包Aと凸包Bそれぞれの形状で写像を求めれば、実際にミンコフスキー差を求めなくとも結果が得られるわけです。

ミンコフスキー差の中心点は凸包Aの中心点と一緒なので、任意の方向の写像が求まれば、物体の領域がわかります。
よって、原点を含んでいるかどうか?の処理も可能になるわけです。


次に、どうやって原点を含んでいるか?をチェックするかですが、これは「単体(simplex)」を利用します。

単体とは、その次元上で一番簡単な(頂点の少ない)形状の事を言います。
1次元なら線分、2次元なら三角形、3次元なら四面体になります。
次元数+1個の頂点で形成される物体のことで、これは必ずその次元での凸包になります。
想像できませんが、4次元なら頂点が5つで出来る物体になるわけです。
(3次元に写像した時に四面体になる形状なんて理解できるほうがおかしいよねw)

なぜ単体を利用しないといけないのか?
ちょっと考えるとわかりますが、単体というのは、その次元上で領域を構成できる最小の物体だからです。


ここからが本題です。今までのは GJK アルゴリズムを理解する上での前知識になります。
実際に GJK アルゴリズムはどのようにしてミンコフスキー差が原点を含んでいるかチェックしているかというと、、、

あ、ここからの話は全てミンコフスキー差で出来た凸包上の話になります。

GJK01.png


01:まず、中心と原点を結ぶベクトルを求めます。
GJK02.png


02:このベクトルと凸包のサポート写像が一番小さい点を求めます。
GJK03.png


03:次に 02 で求めた点と原点を結んだベクトルのサポート写像が一番小さい点を求めます。
GJK04.png

GJK05.png


04:この時点で2点になったので、02 と 03 の線を結び線分を作ります。
GJK06.png


05:04 の線分の原点との最接近点を求め、最接近点と原点を結んだベクトルを求めます。
GJK07.png


06:05 で求めたベクトルのサポート写像が一番小さい点を求めます。
GJK08.png


07:これで 3 点になったので、三角形を形成します。
GJK09.png

  
08:07 で作った三角形がまず原点を含んでいるか調べます。
  原点を含んでいる場合、ミンコフスキー差を構成する物体同士は重なっていることになります。
  もし重なっていない場合は原点との最接近点を求め、最接近点と原点を結んだベクトルを求めます。
GJK10.png


09:08 で求めたベクトルのサポート写像が一番小さい点を求めます。
  このとき選ばれた点が次元数+1を超えてしまうので、既に選ばれている中でサポート写像が一番遠い点を外します。
GJK11.png


10:08 と 09 を再帰的に繰り返していくと、09 で求めた点が収束します。
  もし、重なっていなかった場合、この点が最接近点になります。
  (実際の再接近点は、この点を構成する A と B の対になっている頂点。
   サポート写像を求めるとき、A と B の頂点で行っていることを思い出してください)
GJK12.png



これが基本的な GJK アルゴリズムの全貌です。


さて、次に Johnson's Distance アルゴリズムの説明に入ります。
GJK アルゴリズムを適応した結果、重なっているのがわかった場合、どれだけめり込んだか?を調べたくなるのが人情です。
そこで、このアルゴリズムの登場です。

ここでもやっぱりミンコフスキー差を利用します。

まず、原点を内包しているのが確定した時点から開始します。
dist01.png


01:内包している単体で原点から一番近い点を求め、原点とその点を結んだベクトルを求めます。
dist02.png


02:このベクトルの方向にある、一番遠い点を求めます。
dist03.png


03:02 の点を追加して、多角形にします。
dist04.png


04:03 で追加された点も含めた状態で、原点と一番近い点を求め、原点と結びベクトルにします。
dist05.png


05:あとは最接近点 = 02 の点に収束するまで 02 ~ 04 を繰り返します。
dist06.png

dist07.png

dist08.png

dist09.png

dist10.png

dist11.png

dist12.png

dist13.png

dist14.png

dist15.png

dist16.png

dist17.png

dist18.png

dist19.png



これで、原点と一番近いミンコフスキー差上の点が求まりました。
実は、この点はミンコフスキー差を構成する凸包 A と凸包 B の距離と等しくなっています。
要するに、めり込んだ深度が求まります。
また、原点と最接近点を結んだベクトルが当たり判定に必要なヒット時の力の向きになります。

なぜ力の向きになるか?
最接近点がボロノイ領域で言う面領域だった場合、最接近点と原点を結んだ線は最接近点を含んだ面と直角になってるわけです。
もし辺領域だった場合は辺に対して直角になります。


また、このアルゴリズムでは最接近点を求めている部分が重いのですが、最接近点は新しく追加された頂点によって出来る面だけ再計算すればいいという点に注意してください。
原点も「ミンコフスキー差で出来た凸包」も移動や回転しているわけではないので、面を構成する頂点がかわらなければ最接近点は変化しないので再計算しなくてもOKです。


以上が GJK アルゴリズムの全貌になります。
種明かしをすれば割と素直なアルゴリズムです。


クラメルの公式を再帰的に利用している部分は、GJK アルゴリズムの四面体の最接近点を求めていく過程で高速化のために使用されています。
前述したとおり、GJKアルゴリズムは線分→三角形→四面体と最接近点を求めているのですが、四面体の最接近点を求める際に使用される方程式(偏微分の連立方程式)は
小行列が三角形の最接近点を求める際に使用された行列と同じものが存在します。

クラメルの公式では連立方程式を解くのに行列式を使用するので、行列式をあらかじめキャッシュすることで、
三角形の最接近点を求めるときは直線の最接近点を求める際に使用した行列式を、四面体では三角形の行列式を再利用できるわけです。

よって、アルゴリズムの本筋とは関係ない部分で、きわめて技巧的な処理です。




そんなこんなで長かったGJKに関する議論も一応これで一区切りです。
後はどうやってこれをゲームに適応するか?の部分でも結構難しい課題が多いのですが、それはまた次の機会に。
スポンサーサイト


コメント

  1. 修行中のPG | URL | L9CVqAGQ

     どうもご無沙汰しております。あるけ様。
    >後はどうやってこれをゲームに適応するか?の部分でも結構難しい課題が多いのですが、それはまた次の機会に。
    おお!次の機会を楽しみに待たせて頂きます。

  2. あるけ | URL | -

    >修行中のPGさま
    どうも、お久しぶりです。

    GJKをゲームに適応する部分、実はPolytopeを凸体に分割するのってNP困難な問題のアルゴリズムなんですよね(´ヘ`;)

    シュタイナー点というのを追加して最適な凸包を構築するのは現在でも研究が進んでいる分野ですので、最適解を出すのはあきらめてます。
    ですので、もうちょっとアルゴリズムを思い浮かぶまでまっててくださいw

  3. | |

    管理人のみ閲覧できます

    このコメントは管理人のみ閲覧できます

コメントの投稿

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

トラックバック

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


最近の記事


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