【Collision Detection】

衝突判定について語るｽﾚ。
aabb obb bsp その他オリジナル。
学会発表を目標にします。

(ΦωΦ)ﾌﾌﾌ･･･

1jikan chikaku 2get nashi kayo...sugeeyo!

3get zusaaaaaaaar--------------------------

ライブラリ紹介スレにあったやつだけど、

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

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

新スレおめでとうビーム　(ノ ^ ▽ ＾ )ノ‥‥━━━━━☆ピーー

以前しょぼいシューティング作ってて思ったんだけど、
早い弾と小さなあたり判定のものってどうやってあたりをとるの？
あたり判定１ドットの時機に、１処理で１６ドット進む弾をどうやって
あたったってことにしてよいのか謎です。

Ａ　　・→　自
Ｂ　　　　　自　　・→

最小の処理単位でＡからＢまで移動しちゃうような小さくて早いものの判定。
Ｂ描画した時点で手遅れな感じですが…。
こんなレベル低い話禁止？

>>6
描画と内部の処理は別物だと考えましょう。
描画秒６０回、当たり判定秒１８０回とか。
ベクトルや面積で考えるより楽。

ABベクトルが自キャラと衝突したか見れば良い。
Cマガのこてつさんの記事に書いてあったはず。

>>7
　それは問題ありすぎ。８氏の言うように時機と弾のベクトルの
交点で見るべきだよ。もちろん、その前に大雑把な矩形で簡単に
当たりを取ってから…みたいな高速化の必要はあるけど。

　というかレベル低すぎ。

>>7-9
すごくありがとう。
ベクトルとか考えたこともないけど、避けられそうも無いので調べます。
レベル低すぎでごめんよ。まじで。

ここは「学会発表を目標」にするスレッドです！
レベルの低い話題は避けてください！！

>>9
微分すんの？速い弾だけ判定回数増やせばいいじゃん。

>>12
多分線で当ったほうが早いよ、float 最近速いし・・・

＞ここは「学会発表を目標」にするスレッドです！
＞レベルの低い話題は避けてください！！
そもそも、コリジョン判定自体、低レベルなベース処理じゃん。

>>14
３Ｄ空間上のコリジョン判定となると結構高度な内容もあると思うが・・・

NiGHTSみたいに３D空間の中でわっかをくぐったかどうか高速に
判定する方法を教えてください。

Ray and Plane Collision
ttp://www.gametutorials.com/Tutorials/OpenGL/OpenGL_Pg3.htm

>>16
わっかを2次元で考えて、
キャラが -r < キャラの通過位置 < r (r:半径)
とかなのかなー。

MagicSoftwareのソースをコピペで終了だな
http://www.magic-software.com/Intersection3D.html

あと、こことかのリンク先見れ
http://www.realtimerendering.com/int/

>>19
ラップしてそのまま売ったりしない限り商用利用も可能なんだね。
太っ腹だ。

>>14
ｺﾞﾗｧ。 じゃぁ、今まで誰も思い付かなかった、３Ｄ空間上の２つのオブジェクト衝突判定アルゴリズム書いてみろよ。
ｱﾎの癖にｲｷｶﾞｯﾃﾝｼﾞｬﾈｪﾖｵ。

しかも、今までになく高速なやつな。 一つのオブジェクトに含まれる三角形数は任意だ。

3Dでポリゴンベースの厳密な当たり判定って意味あるんですか？
地面との接地はまじめにやんないといけないかも知れんけど。

>>22
>>14が言う低レベルって、
「アセンブラは低レベル言語」の「低レベル」の意味だと思ったが…。

ところで、
俺的にはトーラスとトーラスのコリジョンが気になってる。
３次元上の円と円の最短距離を求められればできそうなんだが、
良い方法が思いつかない。

…神よお導きを…

つーか、３Ｄ空間上での移動する物体同士の衝突判定って
どの程度まで真面目にやるべき？
境界箱？境界球？それともポリゴン単位でキッチリやる？？

球でOK！
ってのが多いんだっけ？

パフォーマンスや内容にふさわしい接触判定が吉と出ておりますぅ。

28が正解。
バウンディングボックス（直方体・球等）で大まかな判定やって衝突してる場合、必要とあらば更に精密なデテクションやる。
シューティングゲーだったら、精密衝突判定にオブジェクトVS線分判定は必要。
ゲの場合、インチキをできる限り使う。　これ常識。
あんま、レベル下げないように。　

>>25
方程式で表せる物体だったら、連立方程式で交点を解いたら？

>>26
表示モデルから少ないポリゴンで構成された表示モデルを含む
凸多面体を作ると単純な箱や球よりオシャレかも？
http://www.melax.com/hull/index.html

コリジョン検知よりカリングの方が気になる今日この頃

>>32
俺もカリング気になる。

判定貧弱なゲームは萎え。

コリアンコレクション(韓国集合)？

保守age

CatmullRom曲面とかの法線って偏微分して外積して求めるのですか？
近傍３点を拾って外積ですか？
おおざっぱなhightフィールドの当たりに使いたいのですけど・・・

2Dで２つの長方形が重なっているかどうかの判定はできるのですが
重なっている領域の座標を求める計算式ありませんか？

自前で書くとif文の行列になってｲﾔｿな感じなので。

数値的偏微分

>>39
消防の俺にもわかるように丁寧に解説おながいしマス。

>>38
俺もif文オンパーレドになる。
美しい式ないかなぁ？

>>38
俺もif文オンパーレドになる。
美しい式ないかなぁ？

で、ＧｅｏｍｅｔｒｉｃＡｌｇｅｂｌａってなんだったの？
簡潔に幾何演算できるんじゃなかったの？

数値的偏微分って後者のほうですね
CatmullRom曲線自体が使えなくなってきた。
無理から合わせに行くので高さが乱高下

>>38
領域の座標ってのが何を求めたいのか良くわからん…

boolearn演算の&じゃないの？

>>45
重なった部分の長方形のRECTです。

それは誰が書いてもifだらけになります。
ifを減らしたいならmax,minを使うのがいい。

これ既出ですか？

http://www.codercorner.com/Opcode.htm

>>49
禿しくｶﾞｲｼｭﾂ

>>38
凸型多角形のANDなら、「交点」と「他方の領域内にある点」をつながっている順に
並び替えれば目的の領域を得られないかな？
というか、その辺の画像処理関係とかグラフ理論とかの教科書とかに載ってそうだ。

Axis-AlignedなRECT同士なら、「交点」と「他方の領域内にある点」が合計で
4点だけ求まるはずだから､4点のうち最大のY=top, 最小のY=bottom, 最小のX=left,
最大のX=rightですぐ求まらない？

というか、X座標4個とY座標4個のうち、最大と最小をそれぞれ抜けば
それで求まるか。

>>52
いや、その話題はとっくに終わってるし、質問した本人も求め方が分から
ないんじゃなくてifを減らしたいだけだから…

こんなのどう？
http://www.peroxide.dk/download/tutorials/tut10/pxdtut10.html

>>54
基礎すぎる。

>>55
さいですか。。。
んじゃあ、コリジョン判定とレスポンスは 54 のリンク先を使うとして、
判定を行うポリゴンの絞り込みには何を使うのがお勧め？

age

ちゃんと衝突判定の話をしてるのに
レベルを下げんなってしつこく言うから
スレが止まったのに気づかんのかボケども。
お前らは fj 住民か。

…というわけで、このスレは今から低レベルでもOKになりますた。

低レベルでも駄目なわけねーだろ(ﾜﾗ
だれが決めるんだよ

>>59
俺。＝神。
しかしチェーンソーに弱い。

>>58
関係ないけど、今fjとかいうと知らない人っているんだよね。
時代が…

俺もfj行ったことないからな

ということにしたいのですね？

つか、その人もマ板ではじめて知ったんだよ
世の中にはいろいろな人がいるなと。

fjも堕落したものだな。

いい壁ズリできるライブラリないですか？
それともみんな自作?

>>66
ライブラリで提供する程のものじゃないだろ。

せっかくだから、>>66に本当に壁ズリの役にしか立たないライブラリを作ってもらうということで。

抜ける壁ズリ
ぬるぬるした触感で
ときに激しく振動する
くわえこんで離さない

そもそも壁の判定がゲームによってまるで違うんだから
壁ズリだけライブラリ化しようったって無理だろ。

せいぜいテンプレートかインターフェースどまり。

でも移動ルーチンの作り方もゲームによってまるで違うから
インターフェースすら統一なんかできない罠。

ｵｲｵｲ・・どう考えてもﾈﾀだろ

お前はネタと言いたいだけちゃうんかと。

RPGだと、表示モデルは凄くても
当たり判定はHeightMapの配列だけってことも
よくあるんじゃないかな。

ちゃうな

判定種別番号を並べたようなものならあるかもね。
2D時代の様な。

実際、マップに合うように衝突判定も3Dで作ったりすると
データ作成がバカにならん。
でも絵描きが権限持ってるプロジェクトだと、
絵描きのわがままに付き合わされてみんなが迷惑することが多い。

では、絵描きのわがままとは？
「そんな衝突判定だと、絵の描き方に制限ができる」

まあ、気持ちは分かるんだけどね。
でも無限の性能がある機械じゃないんだから、
制限ができるのは当然なんだよ。
うまい妥協点を見つけることが重要なんだよ。

でも、自分の絵に少しでもケチをつけられるのがいやな絵描きは
妥協点を見つけること自体をいやがるんだよね。

グチになっちゃった。スマソ。

保守age

　／￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣
　|　また話題もねぇのに糞スレが上がっているのか。1も必死だな。
　＼
　　　￣￣￣￣Ｖ￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣
　　　　　　 ＿∧,,∧　　∫
　　　　 ＿|＼ミ,,ﾟДﾟ彡　∬
　　　　|＼｀ミ　　 ,,っ━~
　　　 (,＼f'",､ ,,ﾐ＼ ＼
　　　　　 し'J＼ ＼|￣|
　　　　　　　 ＼|￣ . _ |
　　　　　　　　（））￣､））
　　　　　　　∀;~'　　''~'
　　　　　　　┷┳━
　　　　　　　　 ┃
　　　　　　　　（））
　　　　　　　　 '~'

あ

い

誰も居ないようなので借ります

test

test

test

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
アフィン変換

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

　

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

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

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

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