ゲームつくろ〜質問箱
(現在 過去ログ5 を侮ヲ中)

HOME HELP 新規作成 新着記事 トピック侮ヲ 検索 過去ログ

[ 最新記事及び返信フォームをトピックトップへ ]

■4594 / inTopicNo.1)  カプセルと地形の衝突判定に必要な判定
  
□投稿者/ うる -(2011/07/07(Thu) 12:43:03)
    こんにちは、うるです。
    また質問させて頂きます。

    カプセルと地形の衝突判定は、線分と三角形の最短距離を算出できれば判定が出来ることは理解しました。
    しかし、約一週間程考えたのですが、肝心のアルゴリズムの部分がどうしても分からないので、教えて頂けませんか?

    よろしくお願いいたします。
引用返信 削除キー/
■4597 / inTopicNo.2)  Re[1]: カプセルと地形の衝突判定に必要な判定
□投稿者/ IKD -(2011/07/07(Thu) 21:44:20)
http://marupeke296.com
     うるさん、ご質問頂きましてありがとうございます。
     
     線分と三角ポリゴンの最短距離は次のように考えます。
     
     三角形ABCと線分PQがあるとして、線分と三角形が交差していない場合、以下の5つの距離を計算します:
     
    @ 線分PQと線分AB
    A 線分PQと線分BC
    B 線分PQと線分CA
    C 点Pと三角形ABCを含む平面への距離(点Pが三角形に投影される場合)
    D 点Qと三角形ABCを含む平面への距離(点Qが三角形に投影される場合)

     @〜Bは「線分と線分の最短距離」の問題です。CとDは点から対象とする三角形に垂線を下ろした時、その垂線が三角形と衝突するか調べます。衝突しなければCとDからは最短距離は出てきませんので除きます。
     
     線分と三角形が交差している場合は、もちろん最短距離は0です。
     
     以上から、線分と三角ポリゴンの最短距離を求めるには、
     
    A. 線分と線分の最短距離
    B. 三角形に対する点の投影
    C. 線分と三角ポリゴンの衝突判定

    の3つの事ができれば算出できます。
引用返信 削除キー/
■4607 / inTopicNo.3)  Re[2]: カプセルと地形の衝突判定に必要な判定
□投稿者/ うる -(2011/07/11(Mon) 12:17:42)
    2011/07/11(Mon) 17:14:01 編集(投稿者)

    > IDKさん
    返信ありがとうございます。
    3つほどわからない部分があったので質問させてください。

    > B. 三角形に対する点の投影
    Bの三角形に対する点とは線分の端の部分だということは分かるのですが、投影とはどのような処理を指すのですか?


    > C. 線分と三角ポリゴンの衝突判定
    これは衝突した時に、例えば、交点座標等の何かしらの値が算出されるのですか?


    線分とポリゴンだけだと80FPS出るのですが、線分(カプセル)と線分(三角形)を取るだけで20FPSまで下がってしまいます。
    8文木空間分割等をして軽くしようと思っていますが、面数が約20000個、頂点数が約4000個の地形でカプセルとポリゴンの判定をするとやはり重いのでしょうか?



    ////////////////////// 追加 //////////////////////////////////////////

    > C 点Pと三角形ABCを含む平面への距離(点Pが三角形に投影される場合)
    > D 点Qと三角形ABCを含む平面への距離(点Qが三角形に投影される場合)
    > CとDは点から対象とする三角形に垂線を下ろした時、その垂線が三角形と衝突するか調べます。衝突しなければCとDからは最短距離は出てきませんので除きます。

    > 対象とする三角形に垂線を下ろす。
    この垂線が三角形までの距離だと思い、対象の三角形の法線(正規化)と、点から三角形のどれかの頂点へ向かうベクトルの内積をしてみたのですが、違うような気がしてきたので質問しました。
    『その垂線が三角形と衝突するか』とあるのでD3DXVECTOR3の型だと思うのですが、内積を取るとfloatの型になってしまいます。
    どのようにD3DXVECTOR3の型で三角形に向かうベクトルを取るのでしょうか?


    > 衝突しなければCとDからは最短距離は出てきませんので除きます。
    下ろした垂線の線分と三角形が交差しなければ、必ず線分同士の距離の方が小さくなるということでしょうか?
    それとも、線分同士の距離計算もする必要が無くなったということでしょうか?




    質問が多くなってしまいましたが、ご教授よろしくお願いします。




引用返信 削除キー/
■4613 / inTopicNo.4)  Re[3]: カプセルと地形の衝突判定に必要な判定
□投稿者/ IKD -(2011/07/11(Mon) 22:21:28)
http://marupeke296.com
     投影というのは、主に平面に対して点や図形などを影絵のように写し込む事を言います。平面に対して、指定がなければ鉛直な光を当てた時、映る図形の影が「投影図」です。線分の端の点を三角形に対して垂直に下ろしていくと、三角形を含む平面上に点が「投影」されます。それが三角形の範囲にあるかどうかを調べる必要があるわけです。
     
     衝突判定と言うと、衝突したか否かが分かれば良く、必ずしも衝突点が算出される必要はありません。ただ、線分と三角形の衝突判定であれば、衝突点を算出する値もまず同時に算出されてしまいますので、何かしらの値が算出されるという事であれば「Yes」です。
     
     床ポリゴンのようにポリゴン数が数千〜数万にもなる物との衝突判定を工夫無しにはもちろんしません。昨今のハイエンドマシンでもまともにやっては60FPSは無理です(^-^;;; 空間分割やメッシュ分割などの最適化が絶対必須となります。
     
     CやDの括弧の中に「投影」とあるように、三角形に点を投影するというのは、三角形に対してある点から垂線を下ろしてその三角形との交点を計算するのと同じです。これはまず、三角形を含む平面に対して点を投影し、それが三角形に含まれるかどうかを次に判定します。同じ平面上にある三角形と点が衝突しているか(点が含まれているか)を調べるのは思いの外面倒なのですが、外積を用いると出来ます。
     
     三角形に端点が投影されない(且つ線分と三角形が交差していない)場合、どんなに頑張っても最短距離は三角形の辺上になるはずです。紙で三角形を作って色々と実験してみると体感できると思いますよ(^-^)。理屈をお知りになりたいという事であれば、三角形の各点や線分を数式で表してコネコネするしかありません。ん〜、私は体感をお勧めします(^-^)
引用返信 削除キー/
■4635 / inTopicNo.5)  Re[4]: カプセルと地形の衝突判定に必要な判定
□投稿者/ うる -(2011/07/22(Fri) 10:58:18)
    > IKDさん
    お返事ありがとうございます。
    分かりやすい解説のおかげでカプセルと地形の衝突判定が出来ました!

    しかし、衝突したか否かを判定できるだけで衝突点の算出方法が分かりません。
    衝突判定編のその5の『壁ずり』を地形に使用し、その衝突点の法線ベクトルがどの方向へ向いているのかで、
    『上に立つことが出来る地面』、『上に立つと滑り落ちる地面』、『壁』、『天井』の判定をしようと思っています。

    衝突点はどのような計算をすればいいのでしょうか?
引用返信 削除キー/
■4637 / inTopicNo.6)  Re[5]: カプセルと地形の衝突判定に必要な判定
□投稿者/ IKD -(2011/07/23(Sat) 13:20:25)
http://marupeke296.com
     衝突点の計算は衝突判定よりもさらに難しいのが一般的です。それは、フレーム単位で動くゲームにおいて、時間が離散になってしまうためです。次のフレームで動いてみたらカプセルが地面に埋まっているという事が日常茶飯事で起こります。ちゃんとした衝突点を求めるには、動いている物同士が「離散時間の間のどの時刻で衝突したか」という「衝突時刻」を調べなければなりません。時刻さえわかれば、両方の図形の性質を利用可能なら衝突点を算出できます。
     
     数学的な計算で動いている2者の衝突時刻を知る事が出来る図形はほとんどありません。多分球とか点のように方向性の無い図形くらいです。その他の図形は動きながら回転などされるともうお手上げで、解析的にはまず解けなくなってしまいます。そのため、一般的には「時刻の始点と終点を分割して近似時刻を求める」という方法を採用します。
     
     始点時に衝突していない図形が、終点に辿りついたら衝突していたという場合、その間のどこかで必ず衝突しています。その瞬間を見つけるには、ちょっとずつ時間を進めて都度衝突判定を行えば良いわけです。世に出ている多くの物理エンジンも実際この分割法を使っています。
     
     衝突の瞬間を捉えられたとして、衝突点の算出ですが、衝突判定を行う時に両者の距離の計算をしているはずです。この時大体両者の間の「最短線分」が出ています。地面(ポリゴン)とカプセルでも求めているはずです。衝突の瞬間は、この最短直線の両端が一致しているか、非常に近い位置にあります。なので、その両端点を衝突点として近似しても実用上は殆ど問題ありません。ただ、例えばカプセルが地面に寝そべっている場合、衝突点自体を定義できないという事もあります。そういう例外は特殊ケースとして別考慮が必要です。
     
     結局は、何らかの方法で衝突時刻(≒衝突位置)を算出する事が鍵であるという事です。中々大変ですが、ご検討下さい(^-^;
引用返信 削除キー/



トピック内ページ移動 / << 0 >>

このトピックに書きこむ

書き込み不可

Pass/

HOME HELP 新規作成 新着記事 トピック侮ヲ 検索 過去ログ

- Child Tree -