5

OBB には、位置 (x,y)、速度 (x,y)、方向 (Matrix) があります。定期的な更新が与えられると、OBB は互いに衝突し、成功したと見なされた移動の一部を返す必要があります。

GPWiki の Polygon テスト ( http://gpwiki.org/index.php/Polygon_Collision ) を見てきましたが、オブジェクトの移動や完全に OBB 内にあるオブジェクトは考慮されていません。

Real Time Collision Detection という本の第 4 章: バウンディング ボリュームで 3D OBB について説明していますが、3 次元でテストする方法は 2D よりも著しく複雑です。

4

5 に答える 5

4

2 つの方向付けられた境界ボックス間の衝突検出をテストするには、分離軸定理 ( SAT ) を使用します。実際、SAT は任意の 2 つの凸形状間の衝突検出に使用できます。この手法は、理解するのがそれほど複雑ではなく、適度なパフォーマンスを備えています。この定理は簡単に 3D に拡張できます。

編集：

アルゴリズムは、2 つのオブジェクト間に平面を適合させることが可能かどうかを判断しようとします。そのような平面が存在する場合、オブジェクトは分離され、交差できません。

オブジェクトが分離されているかどうかを判断するには、オブジェクトを平面の法線に投影し、間隔を比較して重なり合っているかどうかを確認します。

したがって、2 つの分離したオブジェクトの間に収まる平面は無限にあることは明らかです。しかし、ほんの一握りの飛行機をテストするだけでよいことが証明されています。

ボックスの場合、テストされる分離面は、両方のボックスの軸に等しい法線を持つ面であることを示すことができます。したがって、2 つのボックスの場合、合計で 4 つの分離面をテストするだけで済みます。4 つの平面のうち、箱を分離する分離平面を見つけると、箱が交差できないことがわかり、衝突なしフラグが返されます。

4 つの平面がボックスを分離できない場合、ボックスは交差している必要があり、そこで衝突が発生します。

于 2009-04-19T03:27:22.927 に答える
2

別の提案（封じ込めをカバーし、より安価だと思います）：

#1 の 4 つの頂点のいずれかが #2 の内側にあるかどうかを確認し、次に #2 の 4 つの頂点のいずれかが #1 の内側にあるかどうかを確認します。これについて私が提案する方法は次のとおりです。

チェックしている #1 の頂点が v で、#2 の 4 つの頂点が v1 ... v4 であるとします。#2 の向きで 5 つの頂点すべてを逆回転します。(方向行列 M でベクトル u を逆回転するには、u に M 転置: M^T u を乗算します。これは、慣例では方向が左乗算で機能すると仮定します。) 結果の 2 番目のボックスを #2' と呼びます。 v' が含まれているかどうかをすぐに確認できます。

#2 - stop の内側に #1-頂点が見つかった場合は、交差点があります。それ以外の場合 - 続行します。

いくつかの最適化がすぐに頭に浮かびます (おそらく、頂点の回転されていないコピーを各ボックスに保存できますか?サイズが固定されている場合は、それらを比較して、可能な封じ込めの 1 つをすぐに排除し、3 つの潜在的なテストを保存できますか?)膨大な数のボックス ペアに適用している場合、このテストはそのままで十分に安価なはずです。

動きに関しては、そこに好きなだけ深く入ることができます-「連続衝突」を調べて、自分の目で確かめてください. （ステファン・ルドンの素敵な作品を特に覚えています）。私は、この手の込んだことを行うゲームはないと心から信じています。実際に非常に速く動いている場合は、時間ステップを細分化して、各位置/方向のサブイテレーションで衝突チェックを実行できます。

(編集:) それについては、別の議論がありました。

于 2009-04-19T03:46:31.693 に答える
1

任意の方向 (「回転」を意味すると仮定) を持つ 2 つの境界ボックス (つまり、四角形) がある場合、次のようにします。

  • 初期位置 (バウンディング ボックスが交差していないと想定) から始めて、各ボックスをその速度に基づいて前方に移動します (ただし、時間の経過とともに動きを適用します)。
  • 変換された各バウンディング ボックスの角の座標を見つけます。これらの 4 つの座標は、境界ボックスのエッジを構成する 4 つの線分の端点を定義します。
  • 境界ボックス #1 について、その各線分と境界ボックス #2 の 4 つの線分との交差をテストします。たとえば、ここで説明されているように、2 つの線分の交点を計算するための標準的な方程式を使用してこれを行うことができます。
  • 交点があった場合は、交点の座標と適用した既知の平行移動を使用して、成功した移動の割合を計算します。
  • 更新ごとに上記の手順を繰り返します。

編集:大まかな擬似コード(コメントで議論されたものを組み込んだもの)は次のようになります:

...test for intersections between the OBB edges...
if any intersections are found{
    ...run code for when OBBs are partially overlapping...
}else{
    P = line segment whose endpoints are the OBB centers;
    ...test for intersections between P and OBB edges...
    if P intersects edges of both OBBs{
        ...run code for when OBBs are not touching...
    }else{
        ...run code for when one OBB is completely inside the other...
    }
}
于 2009-04-19T02:47:33.147 に答える
0

平面上のすべてのオブジェクトを追跡するには、おそらく四分木 (ウィキペディアを参照) を実装する必要があります。残念ながら、衝突検出用に実装したことはありませんが、他の人が四分木を使用して同様のシナリオを作成できたようです。

于 2009-04-19T08:00:26.763 に答える
-1

あなたは 2D と言っていますが、3D はもっと複雑だとも言っています。衝突検出では、基本的に 2 つの形状が互いに交差するかどうかをテストします。2D では、バウンディング ボックスを使用すると、これらは長方形になります。アルゴリズムを使用して、長方形が交差するかどうかを確認し、長方形が別の長方形に完全に含まれているかどうかを確認する必要があります (単純なアルゴリズムの 3 つのテスト)。3D の場合、これらは立方体です。同じこと。このオブジェクトとオブジェクトの交差のマトリックスを見て、必要なものを見つけてください。オブジェクト自体の交差を確認し、一方が他方の中に完全に含まれていることを確認します。

この手順は、バウンディング ボックスだけでなく、バ​​ウンディング スフィアや、凸包、ポリゴン、または完全な 3D オブジェクト内の実際のオブジェクト自体にも拡張できます。最終的な結果は、オブジェクトが時空間を移動するにつれて、オブジェクトの表面が衝突するか、お互いの内部にあるかどうかになります。粒度が粗すぎて、モデリングしている状況では衝突する必要がありますが、最終的に互いに通り過ぎてしまう場合は、追加のレイ バウンドの交差テストを実行して、オブジェクトが他のオブジェクトの境界と交差します。

于 2009-04-19T02:01:21.870 に答える