【Collision Detection】

test

test

誰かレビューﾖﾛ


4 名前： 名前は開発中のものです。 [sage] 投稿日： 02/03/07 17:13 ID:???
ライブラリ紹介スレにあったやつだけど、

AABB(axis-aligned bounding box)を使用した3Dの衝突検知ライブラリ。
小メモリで高速(かも)らしい。
http://www.codercorner.com/Opcode.htm
ColDet - Free 3D Collision Detection Library
衝突判定ライブラリ。
http://photoneffect.com/coldet/

この辺ってつかえるの？使ったことある人いる？

coldet
のサンプルコードみてみた。
判定したいものをオブジェクトとして登録

CollisionModel3D* model = newCollisionModel3D();
CollisionModel3D* model2 = newCollisionModel3D();

// (ry

model->addTriangle(0.0f, 1.0f, 0.0f,-1.0f,-1.0f, 1.0f, 1.0f,-1.0f, 1.0f);
model->addTriangle(0.0f, 1.0f, 0.0f, 1.0f,-1.0f, 1.0f, 1.0f,-1.0f,-1.0f);
model->addTriangle(0.0f, 1.0f, 0.0f, 1.0f,-1.0f,-1.0f,-1.0f,-1.0f,-1.0f);
model->addTriangle(0.0f, 1.0f, 0.0f,-1.0f,-1.0f,-1.0f,-1.0f,-1.0f, 1.0f);

model->finalize ();

model2->addTriangle(0.0f, 1.0f, 0.0f,-1.0f,-1.0f, 1.0f, 1.0f,-1.0f, 1.0f);
model2->addTriangle(0.0f, 1.0f, 0.0f, 1.0f,-1.0f, 1.0f, 1.0f,-1.0f,-1.0f);
model2->addTriangle(0.0f, 1.0f, 0.0f, 1.0f,-1.0f,-1.0f,-1.0f,-1.0f,-1.0f);
model2->addTriangle(0.0f, 1.0f, 0.0f,-1.0f,-1.0f,-1.0f,-1.0f,-1.0f, 1.0f);

model2->finalize ();

そんで判定は
BOOL collision=model->collision (model2);
if (collision==TRUE)
{
// (ry
}

こんな感じ。

OpenGL official で紹介されてたやつ
http://www.cs.unc.edu/~geom/I_COLLIDE/index.html

なんだこのレベルの低いスレは。
学会発表目指すんなら凹判定でも実現してみろよ

まあだいたい凸多角形を作る段階で
既にものすごいキツイし、
真面目な衝突判定はレベル高いよ。
おまいらメッシュオブジェから破綻の無い凸多角形を作る
アルゴリズムを挙げてみんしゃれ。

ねえねえ
2Dでさ
移動する二つの点が交錯するかどうかの判定って
時間をz軸とした3時限空間上での線分の距離判定と一緒？

>>91
ただ交差するかしないかだったら
L1=P1+tV1
L2=P2+tV2
L1^2+L2^2=0
(V1^2+V2^2)t^2+2(P1･V1+P2･V2)t+P1^2+P2^2=0
を解けばOKか、
距離判定はf=L1^2+L2^2これを微分したやつか。

違うよね
thx

>>93
いや方向性は間違っていない。
ただそんな難しいことをしなくても
そのケースは足りるというだけで。

こ

＞＜；

回転する物体の当たり判定はできるのですが、回転する物体の壁ズリ処理の方法が解らなくて困っています。
どのように処理すればいいのでしょうか？
どなたかよろしければ、アドバイスをお願いします。

>>97
仕様を述べよ。
「回転する物体の壁ズリ」じゃ曖昧なんで、仕様がないと、
何答えても「そうじゃなくて・・・」とか言われそうで答える気がしない。

いちおう言っとくけど、実際に仕様を出せば答えてあげると
約束してるわけじゃないから、勘違いしないでね。

>>98
今できているあたり判定の方法は２Ｄなのですが、
４頂点セットして(四角形)四角形の辺を求め、さらにその辺の法線ベクトルを求めます。
その辺の法線と頂点(衝突相手)を内積した、すべての値が負の値なら当たりというようにチェックしています。

ここから壁ズリ処理をしようと思い、頂点(衝突相手)と辺の外積を取って辺から頂点(衝突相手)までの距離は求められたのですが
そこからどういう計算をすれば壁ズリができるのか方法が解らずに困っています。

変な説明ですみません。

なかなかうまくいかないので質問させてください。
多面体同士の衝突検知をしていて、
もしも分離面が発見できなかったら(干渉していたら)、
2分サーチで衝突時間(ある範囲で接近あるいは干渉すれば衝突とする)
を探しています。
dt進めて干渉してしまっていたら今度はdt/2で止めてみる。
まだ衝突していなかったら3dt/4にしてみる……という具合です。
長時間動かしていても結構うまく動きます。
でもたまに、衝突時間を発見できずに無限ループに陥ってしまうのです。
どのような原因が考えられるでしょうか。
同じような問題が起こった方はいないでしょうか？

dtを分割していくうちに、丸め誤差でそれ以上dtを細かく出来ないのに、
さらに分割しようとしているとか？

>>100
分割回数のカウンタを作って、極端に大きくなったときに
ブレイクさせてみればいいじゃない。

私は丸め誤差を理解できてなくてdtの決め方に問題があるのかも…。
dtは次のように計算しています。
基本時間ステップDtを0.01秒とする。
最初dt = Dt;として進めてみる。
行きすぎだったらDt = Dt/2.0;としてdt = dt - Dt;とする。
まだぶつかってなかったらDt = Dt/2.0;としてdt = dt + Dt;とする。
これを繰り返す。
衝突というのは瞬間ではなくて
ある程度幅を持たせているので見付かるはずだと考えていたのです。
すごいスピードで動いてる立体も作ってないです。
もしここまでで問題がないのなら問題は多面体の幾何の方でしょうか。

>>102
ブレイクさせてみたんですが、
そのあと進みませんでした。

>>104
処理が先に進まなくて困っているところでブレイクさせるんだから、
進むわけないだろう。
チェックするのは変数の値だよ。

ちょっときついですね。
衝突を判定するときの、
立体同士の相対速度や距離の閾値に問題がないかどうか、
「これなら大丈夫」っていう自信が持てません。
衝突判定に関して勉強したことが無いので、
本などでちゃんと勉強した方がよさそうです。
でも本屋においてあるの(ゲームの物理とか)を立ち読みした記憶では
洒落にならないぐらいレベルの低いことしか書いてなかった印象があります。
「こんなの当り前だし知ってても何も作れねぇよ」っていう。
「ゲームプログラミングのためのリアルタイム衝突判定」っていう
本をamazonで見付けたんですけど8400円……
こういうのがいいのかなぁ。

行き過ぎのとき
┣●━━━━━━┫
　　　　　　　　　　　　^dt
を
├●──┣━━━┫
　　　　　　^dt
にしてない？

>>107
まだ行き過ぎなのでその半分、その半分、…って続けます。

これはいいアキレスと亀ですね

>>109
でも点に向かってるわけではないですから…。
それにしてもやはり幾何の問題だということがわかりました。
衝突の探索アルゴリズムに穴がありました。
めちゃめちゃ難しいです。
ものすごい動画とか見て、一体どうやってこんなたくさんの剛体
計算するんだよ、って驚きます。

基本的にいかに衝突判定をしないで済ますか？って言う風に考えるのがミソだよね。

球と平面を判定するいい方法ないですか。

点と平面の距離でいいじゃん。

「ゲームプログラミングのためのリアルタイム衝突判定」
これは抜群にいい本だよ。持っていて損は無い。

>100さんのはニュートン法みたいな解決の仕方だねぇ。
単純に考えて、限りなく接触してるような場合とかではいろんなエラーがおきそうな気がするけど。。

普通に計算式で衝突時間求めちゃうのがいいと思う。

>>114
なるほど、かなりよさそう。
で、本の中から恥ずかしながら質問。
行列式
| ax ay az ax^2+ay^2+az^2 1 |
| bx by bz bx^2+by^2+bz^2 1 |
| cx cy cz cx^2+cy^2+cz^2 1 |
| dx dy dz dx^2+dy^2+dz^2 1 |
| ex ey ez ex^2+ey^2+ez^2 1 |
の正負で、
点Eに関して点ABCDの作る球の内外判定ができる理由が分かりません。

>>115
すぐ上にある、円の内外判定の理屈が分かれば
それを3次元に応用するだけだよ。

>>116
ありがとう。
やっと理解できた。
こんなに4次元を考えたのは初めてで訓練になりました。
でもすごくトリッキーな方法に感じられます。

まあおれならライブラリに走っちゃ(ry

このまま自然に考えると行列式っていうのは何次元で考えても、
平行多面体(?呼び方わからない)の符号付体積になるっぽいですけど、
それをわかりやすく説明できる方がいたら教えてください。

この辺のコト考えてると
時々頭の中でヘビがのた打ち回っているようだってなるよな

そういった数学の話をするなら
そもそも「体積」とは何なのか、定義を固めておかないと訳わからなくなるよ。

かたす

行列式ってなにを表してるのかまったくわからん。

線形代数やりなおせ

内積とかもそうだが、それ自体の意味を問うのではなく
どんなことに利用できるかに着目すべき

えぇぇぇ？？
さすがに内積の意味くらいは理解しとかなまずいがな・・・。

んじゃ行列式って例えば何に使うの？

>>127
アフィン変換

行列式がアフィン変換・・・・どうだろうかそれは。

　

自前で干渉判定を作るメリットはなんすか？
フリーのを使うのでは信頼性とか問題あるすか？

ところで、
あけましておめでとうございます。

今年もよろしくお願いします

行列でなく行列式使うのか…