ビデオゲームの物理チュートリアル-パートII：固体オブジェクトの衝突検出

これは、ビデオゲームの物理に関する3部構成のシリーズのパートIIです。 このシリーズの残りの部分については、以下を参照してください。

パートI：剛体力学の概要
パートIII：拘束された剛体シミュレーション

このシリーズのパートIでは、剛体とその動きについて説明しました。 ただし、その議論では、オブジェクトは相互に作用しませんでした。 追加の作業がないと、シミュレートされたリジッドボディは互いに直接通過するか、「相互侵入」する可能性があります。これは、ほとんどの場合望ましくありません。

ソリッドオブジェクトの動作をよりリアルにシミュレートするには、移動するたびに衝突するかどうかを確認する必要があります。衝突する場合は、速度を変更する力を加えるなど、何かを行う必要があります。彼らは反対方向に動くだろうと。 これは、衝突の物理学を理解することがゲーム開発者にとって特に重要な場所です。

パートIIでは、衝突検出ステップについて説明します。これは、2Dまたは3Dの世界に散在している可能性のある多数のボディ間で衝突しているボディのペアを見つけることで構成されます。 次の最後の記事では、これらの衝突を「解決」して相互侵入を排除する方法について詳しく説明します。

この記事で参照されている線形代数の概念のレビューについては、パートIの線形代数のクラッシュコースを参照してください。

ビデオゲームにおける衝突物理学

剛体シミュレーションのコンテキストでは、2つの剛体の形状が交差している場合、またはこれらの形状間の距離が小さな公差を下回っている場合に、衝突が発生します。

シミュレーションにn体がある場合、ペアワイズテストで衝突を検出する計算の複雑さはO （ n 2 ）であり、これはコンピューター科学者を苛立たせます。 ペアワイズテストの数は、ボディの数とともに2次関数的に増加し、任意の位置と方向にある2つの形状が衝突しているかどうかを判断することはすでに安価ではありません。 衝突検出プロセスを最適化するために、通常、ブロードフェーズとナローフェーズの2つのフェーズに分割します。

ブロードフェーズは、シミュレーションに含まれるボディのセット全体の中から、衝突する可能性のあるリジッドボディのペアを見つけ、確実に衝突しないペアを除外する役割を果たします。 このステップは、 O （ n 2 ）時間計算量を十分に満たすために、剛体の数に応じて非常に適切にスケーリングできる必要があります。 これを実現するために、このフェーズでは通常、衝突の上限を確立するバウンディングボリュームと組み合わせたスペースパーティショニングを使用します。

狭いフェーズは、衝突している可能性のある広いフェーズによって検出された剛体のペアで動作します。 これは、衝突が実際に発生しているかどうかを判断する改良ステップであり、検出された衝突ごとに、後で衝突を解決するために使用される接触点を計算します。

次のセクションでは、ブロードフェーズとナローフェーズで使用できるいくつかのアルゴリズムについて説明します。

ブロードフェーズ

ビデオゲームの衝突物理学の幅広いフェーズでは、どの剛体のペアが衝突している可能性があるかを特定する必要があります。 これらのボディは、ポリゴンや多面体のような複雑な形状をしている可能性があります。これを加速するためにできることは、より単純な形状を使用してオブジェクトを囲むことです。 これらのバウンディングボリュームが交差しない場合、実際の形状も交差しません。 それらが交差する場合、実際の形状が交差する可能性があります。

いくつかの一般的なタイプのバウンディングボリュームは、方向付けされたバウンディングボックス（OBB）、2Dの円、および3Dの球です。 最も単純なバウンディングボリュームの1つである軸整列バウンディングボックス（AABB）を見てみましょう。

AABBは単純であり、優れたトレードオフを提供するため、物理プログラマーから多くの愛を得ています。 2次元AABBは、C言語では次のような構造体で表すことができます。

 typedef struct { float x; float y; } Vector2; typedef struct { Vector2 min; Vector2 max; } AABB;

minフィールドはボックスの左下隅の位置を表し、 maxフィールドは右上隅を表します。

2つのAABBが交差するかどうかをテストするには、それらの投影がすべての座標軸で交差するかどうかを確認するだけです。

 BOOL TestAABBOverlap(AABB* a, AABB* b) { float d1x = b->min.x - a->max.x; float d1y = b->min.y - a->max.y; float d2x = a->min.x - b->max.x; float d2y = a->min.y - b->max.y; if (d1x > 0.0f || d1y > 0.0f) return FALSE; if (d2x > 0.0f || d2y > 0.0f) return FALSE; return TRUE; }

このコードには、Box2Dエンジン（バージョン2.3.0）のb2TestOverlap関数と同じロジックがあります。 両方の軸で、両方の順序で、両方のAABBのmin値とmaxの差を計算します。 これらの値のいずれかがゼロより大きい場合、AABBは交差しません。

AABBオーバーラップテストは安価ですが、望ましくないO （ n 2 ）時間計算量があるため、可能なすべてのペアに対してペアワイズテストを実行してもあまり役に立ちません。 AABBオーバーラップテストの数を最小限に抑えるために、ある種のスペースパーティショニングを使用できます。これは、クエリを高速化するデータベースインデックスと同じ原理で機能します。 （PostGISなどの地理データベースは、実際には空間インデックスに同様のデータ構造とアルゴリズムを使用します。）ただし、この場合、AABBは絶えず動き回るので、通常、シミュレーションのすべてのステップの後にインデックスを再作成する必要があります。

均一グリッド、2Dの四分木、3Dの八分木、空間ハッシュなど、これに使用できる空間分割アルゴリズムとデータ構造はたくさんあります。 ソートとスイープ、およびバウンディングボリューム階層（BVH）という2つの一般的な空間分割アルゴリズムを詳しく見てみましょう。

ソートおよびスイープアルゴリズム

並べ替えとスイープの方法（スイープとプルーンとも呼ばれます）は、剛体シミュレーションで使用する物理プログラマーの間で人気のある選択肢の1つです。 たとえば、Bullet Physicsエンジンには、 btAxisSweep3クラスにこのメソッドが実装されています。

1つのAABBの単一の座標軸への投影は、基本的に間隔[ b 、 e ] （つまり、開始と終了）です。 私たちのシミュレーションでは、多くの剛体、つまり多くのAABBがあり、それは多くの間隔を意味します。 どの間隔が交差しているかを調べたいと思います。

並べ替えとスイープのアルゴリズムでは、すべてのb値とe値を単一のリストに挿入し、スカラー値の昇順で並べ替えます。 次に、リストをスイープまたはトラバースします。 b値が検出されると、それに対応する間隔がアクティブな間隔の別のリストに格納され、 e値が検出されると、対応する間隔がアクティブな間隔のリストから削除されます。 いつでも、すべてのアクティブな間隔が交差しています。 （詳細については、DavidBaraffのPh。DThesis、p。52を参照してください。このオンラインツールを使用してポストスクリプトファイルを表示することをお勧めします。）間隔のリストは、シミュレーションの各ステップで再利用でき、効率的に並べ替えることができます。このリストは挿入ソートを使用します。これは、ほぼソートされたリストのソートに適しています。

2次元および3次元では、前述のように、単一の座標軸上でソートとスイープを実行すると、実行する必要のある直接AABB交差テストの数が減りますが、ある座標軸上での見返りは別の座標軸よりも優れている場合があります。 したがって、ソートおよびスイープアルゴリズムのより洗練されたバリエーションが実装されます。 Christer Ericsonは、著書Real-Time Collision Detection （336ページ）で、すべてのAABBを単一の配列に格納し、並べ替えとスイープの実行ごとに1つの座標軸を選択し、配列を次のように並べ替える効率的なバリエーションを紹介しています。クイックソートを使用した、選択した軸のAABBのmin値。 次に、アレイがトラバースされ、AABBオーバーラップテストが実行されます。 並べ替えに使用する次の軸を決定するために、AABBの中心の分散が計算され、分散が大きい軸が次のステップで選択されます。

動的バウンディングボリュームツリー

もう1つの有用な空間分割方法は、 Dbvtとしても知られる動的バウンディングボリュームツリーです。 これは、バウンディングボリューム階層の一種です。

Dbvtは、各ノードにその子のすべてのAABBをバインドするAABBがあるバイナリツリーです。 剛体自体のAABBは、リーフノードにあります。 通常、Dbvtは、交差点を検出するAABBを指定することによって「照会」されます。 クエリされたAABBと交差しないノードの子は、オーバーラップをテストする必要がないため、この操作は効率的です。 そのため、AABB衝突クエリはルートから開始し、クエリされたAABBと交差するAABBノードに対してのみツリーを再帰的に続行します。 ツリーは、AVLツリーの場合と同様に、ツリーの回転によってバランスをとることができます。

Box2Dには、 b2DynamicTreeクラスのDbvtの高度な実装があります。 b2BroadPhaseクラスは、ブロードフェーズの実行を担当し、 b2DynamicTreeのインスタンスを使用してAABBクエリを実行します。

狭いフェーズ

ビデオゲームの衝突物理学の幅広いフェーズの後、衝突する可能性のある剛体のペアのセットができました。 したがって、各ペアについて、両方のボディの形状、位置、および向きを考慮して、それらが実際に衝突しているかどうかを確認する必要があります。 それらが交差している場合、またはそれらの距離が小さな許容値を下回っている場合。 また、後で衝突を解決するために必要になるため、衝突する物体間の接触点を知る必要があります。

凸面と凹面の形状

ビデオゲームの物理学の原則として、2つの任意の形状が交差しているかどうかを判断したり、それらの間の距離を計算したりすることは簡単ではありません。 ただし、それがどれだけ難しいかを判断する上で非常に重要な1つの特性は、形状の凸面です。 形状は凸面または凹面のいずれかになり、凹面の形状は扱いにくいため、それらに対処するためのいくつかの戦略が必要です。

凸形状では、形状内の任意の2点間の線分は、常に完全に形状の内側にあります。 ただし、凹型（または「非凸型」）の形状の場合、形状内の点を接続する可能性のあるすべての線分に同じことが当てはまるわけではありません。 形状の外側にある線分が少なくとも1つ見つかった場合、その形状は凹型です。

計算上、シミュレーションではすべての形状が凸であることが望ましいです。これは、凸形状で機能する強力な距離および交差テストアルゴリズムが多数あるためです。 ただし、すべてのオブジェクトが凸であるとは限りません。通常、凸包と凸分解の2つの方法でオブジェクトを回避します。

形状の凸包は、それを完全に含む最小の凸包です。 2次元の凹多角形の場合、各頂点に釘を打ち、すべての釘に輪ゴムを巻き付けるようなものです。 ポリゴンまたは多面体、またはより一般的には点のセットの凸包を計算するために使用するのに適したアルゴリズムは、平均時間計算量がO （ n log n ）のクイックハルアルゴリズムです。

明らかに、凸包を使用して凹オブジェクトを表すと、その凹特性が失われます。 オブジェクトは依然として凹状のグラフィック表現を持っているため、「ゴースト」衝突などの望ましくない動作が明らかになる可能性があります。 たとえば、車は通常凹型で、凸包を使って物理的に表現してから箱を置くと、上の空間に箱が浮かんでいるように見えることがあります。

一般に、非現実的な衝突があまり目立たないか、シミュレートされているものに凹型のプロパティが不可欠ではないため、凸包は凹型のオブジェクトを表すのに十分な場合がよくあります。 ただし、場合によっては、凹型オブジェクトを物理的に凹型の形状のように動作させたい場合があります。 たとえば、凸包を使用してボウルを物理的に表すと、その中に何も入れることができなくなります。 オブジェクトはその上に浮かぶだけです。 この場合、凹型の凸型分解を使用できます。

凸分解アルゴリズムは凹形状を受け取り、元の凹形状と和集合が同じである凸形状のセットを返します。 一部の凹型の形状は、多数の凸型の形状でしか表現できず、計算と使用に非常にコストがかかる可能性があります。 ただし、多くの場合、近似で十分であるため、 V-HACDなどのアルゴリズムは、凹多面体から凸多面体の小さなセットを生成します。

ただし、多くの衝突物理学の場合、凸状の分解は芸術家が手作業で行うことができます。 これにより、分解アルゴリズムでパフォーマンスに負担をかける必要がなくなります。 パフォーマンスはリアルタイムシミュレーションで最も重要な側面の1つであるため、一般に、複雑なグラフィックオブジェクトの非常に単純な物理的表現を作成することをお勧めします。 下の画像は、9つの凸形状を使用した2D車の1つの可能な凸分解を示しています。

交差点のテスト-分離軸定理

分離軸定理（SAT）は、この軸上の形状の正射影が交差しない軸が少なくとも1つ存在する場合にのみ、2つの凸形状が交差しないことを示しています。

通常、2Dの線または2つの形状を分離する3Dの平面を見つける方が視覚的に直感的ですが、これは事実上同じ原理です。 2Dの線に直交するベクトル、または3Dの平面の法線ベクトルは、「分離軸」として使用できます。

ゲーム物理エンジンには、円（3Dの球）、エッジ（単一の線分）、凸多角形（3Dの多面体）など、さまざまなクラスの形状があります。 形状タイプのペアごとに、特定の衝突検出アルゴリズムがあります。 それらの中で最も単純なのは、おそらくサークルサークルアルゴリズムです。

 typedef struct { float centerX; float centerY; float radius; } Circle; bool CollideCircles(Circle *cA, Circle *cB) { float x = cA->centerX - cB->centerX; float y = cA->centerY - cB->centerY; float centerDistanceSq = x * x + y * y; // squared distance float radius = cA->radius + cB->radius; float radiusSq = radius * radius; return centerDistanceSq <= radiusSq; }

SATは円に適用されますが、中心間の距離が半径の合計よりも小さいかどうかを確認する方がはるかに簡単です。 そのため、SATは、凸多角形と凸多角形（または3Dの多面体）など、形状クラスの特定のペアの衝突検出アルゴリズムで使用されます。

形状の任意のペアについて、分離をテストできる軸の数は無限です。 したがって、最初にテストする軸を決定することは、効率的なSATの実装にとって非常に重要です。 幸い、凸多角形のペアが衝突するかどうかをテストする場合、エッジ法線を潜在的な分離軸として使用できます。 エッジの法線ベクトルnはエッジベクトルに垂直であり、ポリゴンの外側を指します。 各ポリゴンの各エッジについて、他のポリゴンのすべての頂点がエッジの前にあるかどうかを確認する必要があります。

テストに合格した場合、つまり、いずれかのエッジで、他のポリゴンのすべての頂点がその前にある場合、ポリゴンは交差しません。 線形代数は、このテストの簡単な式を提供します。頂点aとbを持つ最初の形状のエッジと、他の形状の頂点vが与えられ、 （ v --a ）・nがゼロより大きい場合、頂点は前面にあります。エッジの。

多面体の場合、面の法線と、各形状のすべてのエッジの組み合わせの外積を使用できます。 それはテストすることがたくさんあるように聞こえます。 ただし、処理を高速化するために、最後に使用した分離軸をキャッシュして、シミュレーションの次のステップで再度使用してみることができます。 キャッシュされた分離軸が形状を分離しなくなった場合、前の面またはエッジに隣接する面またはエッジから開始して新しい軸を検索できます。 ボディはステップ間であまり移動したり回転したりしないことが多いため、これは機能します。

Box2Dは、SATを使用して、b2CollidePolygon.cppのポリゴン-ポリゴン衝突検出アルゴリズムで2つの凸多角形が交差しているかどうかをテストします。

距離の計算-Gilbert-Johnson-Keerthiアルゴリズム

多くの衝突物理学のケースでは、オブジェクトが実際に交差している場合だけでなく、オブジェクトが互いに非常に接近している場合にも、オブジェクト間の距離を知る必要がある場合に、オブジェクトが衝突していると見なしたいと思います。 Gilbert-Johnson-Keerthi （GJK）アルゴリズムは、2つの凸形状間の距離とそれらの最も近い点を計算します。 これは、以下で説明するように、サポート関数、ミンコフスキー和、およびシンプレックスを介して凸形状の暗黙的な表現で機能する洗練されたアルゴリズムです。

サポート機能

サポート関数sA （ d ）は、ベクトルdで最も高い射影を持つ形状Aの境界上の点を返します。 数学的には、 dの内積が最も高くなります。 これはサポートポイントと呼ばれ、この操作はサポートマッピングとも呼ばれます。 幾何学的には、この点はdの方向の形状上で最も遠い点です。

ポリゴン上のサポートポイントを見つけるのは比較的簡単です。 ベクトルdのサポートポイントの場合、次のように、頂点をループして、 dとの内積が最も高い頂点を見つける必要があります。

 Vector2 GetSupport(Vector2 *vertices, int count, Vector2 d) { float highest = -FLT_MAX; Vector2 support = (Vector2){0, 0}; for (int i = 0; i < count; ++i) { Vector2 v = vertices[i]; float dot = vx * dx + vy * dy; if (dot > highest) { highest = dot; support = v; } } return support; }

ただし、サポート機能の真の力は、円錐、円柱、楕円などの形状を簡単に操作できることです。 このような形状間の距離を直接計算することはかなり困難であり、GJKのようなアルゴリズムがなければ、通常、物事を単純化するためにそれらを多角形または多面体に離散化する必要があります。 ただし、多面体の表面は、多面体が非常に詳細でない限り、たとえば球の表面ほど滑らかではないため、さらに問題が発生する可能性があります。これにより、衝突検出中のパフォーマンスが低下する可能性があります。 他の望ましくない副作用も現れる可能性があります。 たとえば、「多面体」の球はスムーズに回転しない場合があります。

原点を中心とする球のサポートポイントを取得するには、 dを正規化する必要があります（つまり、同じ方向を指す長さ1（単位長）のベクトルであるd / || d ||を計算します）。 d ）の次に、球の半径を掛けます。

ジノ・バン・デン・ベルゲンの論文をチェックして、他の形状の中でも特に、シリンダーやコーンのサポート機能の例を見つけてください。

もちろん、オブジェクトはシミュレーション空間の原点から移動および回転するため、変換された形状のサポートポイントを計算できる必要があります。 アフィン変換T （ x ）= R x + cを使用して、オブジェクトを変位および回転させます。ここで、 cは変位ベクトル、 Rは回転行列です。 この変換では、最初にオブジェクトを原点を中心に回転させてから、変換します。 変換された形状Aのサポート関数は次のとおりです。

ミンコフスキー和

2つの形状AとBのミンコフスキー和は次のように定義されます。

つまり、 AとBに含まれるすべてのポイントの合計を計算します。 結果は、 AをBで膨らませるようなものです。

同様に、ミンコフスキーの差を次のように定義します。

これは、 Aと-Bのミンコフスキー和として書くこともできます。

凸型AおよびBの場合、 A⊕Bも凸型です。

ミンコフスキーの違いの有用な特性の1つは、前の画像に見られるように、空間の原点が含まれている場合、形状が交差することです。 何故ですか？ 2つの形状が交差する場合、それらには少なくとも1つの共通点があり、それらは空間内の同じ場所にあり、それらの差は実際には原点であるゼロベクトルであるためです。

ミンコフスキー差のもう1つの優れた機能は、原点が含まれていない場合、原点とミンコフスキー差の間の最小距離が形状間の距離になることです。

2つの形状間の距離は次のように定義されます。

言い換えると、 AとBの間の距離は、 AからBに移動する最短のベクトルの長さです。 このベクトルはA⊖Bに含まれており、長さが最も短いベクトルであるため、原点に最も近いベクトルになります。

一般に、2つの形状のミンコフスキー和を明示的に作成することは簡単ではありません。 幸い、ここでもサポートマッピングを使用できます。理由は次のとおりです。

シンプレックス

GJKアルゴリズムは、原点に最も近いミンコフスキー差の点を繰り返し検索します。 これは、各反復で原点に近い一連のシンプレックスを構築することによって行われます。 シンプレックス（より具体的には、整数kのkシンプレックス）は、k次元空間内のk+1個の親和的に独立した点の凸包です。 つまり、2つのポイントの場合、それらは一致してはならず、3つのポイントの場合、それらはさらに同じ線上にある必要があり、4つのポイントがある場合、それらも同じ平面上にある必要はありません。 したがって、0シンプレックスは点、1シンプレックスは線分、2シンプレックスは三角形、3シンプレックスは四面体です。 シンプレックスからポイントを削除すると、その次元が1つ減り、シンプレックスにポイントを追加すると、その次元が1つ増えます。

GJKの動作

これをすべてまとめて、GJKがどのように機能するかを見てみましょう。 2つの形状AとBの間の距離を決定するために、ミンコフスキー差A⊖Bを取得することから始めます。 この点までの距離は元の2つの形状間の距離であるため、結果の形状の原点に最も近い点を検索しています。 A⊖Bのある点vを選択します。これは、距離の近似値になります。 また、現在のテストシンプレックスのポイントを含む空のポイントセットWを定義します。

次に、ループに入ります。 まず、サポートポイントw = sA⊖B （ -v ）を取得します。これは、 vへの射影が原点に最も近いA⊖B上のポイントです。

||の場合w || ||と大差ありませんv || そして、それらの間の角度は（いくつかの事前定義された許容誤差に従って）あまり変化しませんでした。これは、アルゴリズムが収束し、 ||を返すことができることを意味します。 v || 距離として。

それ以外の場合は、 Wにwを追加します。 Wの凸包（つまり、シンプレックス）に原点が含まれている場合、形状は交差します。これは、完了したことも意味します。 それ以外の場合は、原点に最も近いシンプレックス内の点を見つけてから、 vをこの新しい最も近い近似値にリセットします。 最後に、最も近いポイントの計算に寄与しないW内のポイントをすべて削除します。 （たとえば、三角形があり、原点に最も近い点がそのエッジの1つにある場合、このエッジの頂点ではないポイントをWから削除できます。）次に、アルゴリズムが実行されるまで、これらの同じ手順を繰り返します。収束します。

次の画像は、GJKアルゴリズムの4回の反復の例を示しています。 青いオブジェクトはミンコフスキー差A⊖Bを表し、緑のベ​​クトルはvです。 ここで、 vが原点に最も近い点にどのように焦点を合わせているかを確認できます。

GJKアルゴリズムの詳細で詳細な説明については、Gino vandenBergenによる論文「凸オブジェクトの衝突検出のための高速で堅牢なGJK実装」を参照してください。 dyn4j物理エンジンのブログにもGJKに関するすばらしい投稿があります。

Box2Dには、 b2Distance関数のb2Distance.cppにGJKアルゴリズムが実装されています。 継続的な衝突検出のアルゴリズムでは、衝撃計算時にGJKのみを使用します（トピックについては後で説明します）。

Chimpunk物理エンジンは、すべての衝突検出にGJKを使用し、その実装はcpCollision.cのGJK関数にあります。 GJKアルゴリズムが交差を報告する場合でも、侵入深さとともに、接触点が何であるかを知る必要があります。 そのために、次に検討する拡張ポリトープアルゴリズムを使用します。

侵入深さの決定-拡張ポリトープアルゴリズム

上記のように、形状AとBが交差している場合、GJKは、ミンコフスキー差A⊖B内に原点を含むシンプレックスWを生成します。 この段階では、形状が交差していることしかわかりませんが、多くの衝突検出システムの設計では、交差の量と、接触点として使用できるポイントを計算できることが望ましいため、次のようになります。衝突を現実的な方法で処理します。 Expanding Polytope Algorithm （EPA）を使用すると、GJKが中断したところから、原点を含むシンプレックスを使用して、その情報を取得できます。

侵入深さは、最小平行移動ベクトル（MTV）の長さです。これは、交差する形状を他の形状から分離するために平行移動できる最小のベクトルです。

2つの形状が交差している場合、それらのミンコフスキー差には原点が含まれ、ミンコフスキー差の境界上で原点に最も近い点がMTVです。 EPAアルゴリズムは、GJKが私たちに与えたシンプレックスをポリゴンに拡張することによってそのポイントを見つけます。 エッジを新しい頂点で連続的に細分割します。

最初に、原点に最も近いシンプレックスのエッジを見つけ、エッジに垂直な方向（つまり、エッジに垂直でポリゴンの外側を指す）のミンコフスキー差のサポートポイントを計算します。 次に、このサポートポイントを追加して、このエッジを分割します。 ベクトルの長さと方向があまり変わらなくなるまで、これらの手順を繰り返します。 アルゴリズムが収束すると、MTVと侵入深さがわかります。

GJKをEPAと組み合わせて使用​​すると、オブジェクトがすでに交差しているかどうか、または衝突と見なされるのに十分な距離にあるかどうかに関係なく、衝突の詳細な説明が得られます。

EPAアルゴリズムは、同じくGino vandenBergenによって書かれた論文「3Dゲームオブジェクトの近接クエリと侵入深さの計算」で説明されています。 dyn4jブログには、EPAに関する投稿もあります。

継続的な衝突検出

これまでに提示されたビデオゲームの物理技術は、シミュレーションの静的スナップショットの衝突検出を実行します。 これは離散衝突検出と呼ばれ、前のステップと現在のステップの間で発生したことを無視します。 このため、特に動きの速いオブジェクトの場合、一部の衝突が検出されない可能性があります。 この問題はトンネリングとして知られています。

連続衝突検出技術は、シミュレーションの前のステップと現在のステップの間で2つの物体が衝突したときを検出しようとします。 それらは衝撃の時間を計算するので、時間を遡ってその時点での衝突を処理することができます。

衝撃時間（または接触時間） t cは、2つの物体間の距離がゼロになる瞬間です。 時間に沿った2つの物体間の距離の関数を記述できる場合、見つけたいのはこの関数の最小の根です。 したがって、影響計算の時間は、求根問題です。

衝撃計算の時間については、時間t i -1での前のステップと、時間t iでの現在のステップでの体の状態（位置と方向）を考慮します。 物事を簡単にするために、ステップ間の線形運動を想定しています。

形状が円であると仮定して、問題を単純化してみましょう。 半径r1とr2の2つの円C1とC2の場合、重心x1とx2は重心と一致します（つまり、重心を中心に自然に回転します）。距離関数を記述できます。なので：

ステップ間の線形運動を考慮すると、ti-1からtiまでのC1の位置に対して次の関数を書くことができます。

これは、 x 1 （ t i -1 ）からx 1 （ t i ）への線形補間です。 x2についても同じことができます。 この区間では、別の距離関数を記述できます。

この式をゼロに設定すると、 tで2次方程式が得られます。 根は二次方程式を使用して直接見つけることができます。 円が交差しない場合、二次方程式には解がありません。 もしそうなら、それは1つか2つの根をもたらすかもしれません。 ルートが1つしかない場合、その値が影響の時間です。 根が2つある場合、最小の1つは衝撃の時間であり、もう1つは円が分離する時間です。 ここでの影響の時間は0から1までの数値であることに注意してください。これは秒単位の時間ではありません。 これは、衝突が発生した正確な位置に物体の状態を補間するために使用できる単なる数値です。

非円の連続衝突検出

他の種類の形状の距離関数を作成することは、主にそれらの距離がそれらの方向に依存するため、困難です。 このため、通常、衝突と見なされるのに十分な距離になるまで、反復ごとにオブジェクトをどんどん近づける反復アルゴリズムを使用します。

保守的な前進アルゴリズムは、ボディを繰り返し前方に移動（および回転）します。 各反復で、変位の上限を計算します。 元のアルゴリズムは、Brian Mirtichの博士論文（セクション2.3.2）に示されています。これは、物体の弾道運動を考慮したものです。 Erwin Coumans（Bullet Physics Engineの作者）によるこの論文は、一定の線形および角速度を使用するより単純なバージョンを示しています。

アルゴリズムは、形状AとBの間の最も近い点を計算し、ある点から別の点にベクトルを描画し、このベクトルに速度を投影して、モーションの上限を計算します。 これにより、体のどの点もこの投影を超えて移動しないことが保証されます。 次に、この量だけボディを前方に進め、距離が小さな許容値を下回るまで繰り返します。

場合によっては、収束するのに非常に多くの反復が必要になることがあります。たとえば、一方の物体の角速度が高すぎる場合などです。

衝突の解決

衝突が検出されたら、衝突するオブジェクトを互いに跳ね返らせるなど、現実的な方法でオブジェクトの動きを変更する必要があります。 この理論の次の最後の記事では、ビデオゲームの衝突を解決するためのいくつかの一般的な方法について説明します。

参考文献

衝突検出のアルゴリズムや手法などの衝突物理学についてより深く理解することに興味がある場合は、ChristerEricsonによる「 Real- TimeCollisionDetection」という本が必需品です。

衝突検出はジオメトリに大きく依存しているため、Toptalの記事「 Pythonでの計算幾何学：理論から応用まで」は、このトピックの優れた入門書です。