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

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

---

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

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

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

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

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

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

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

広いフェーズは、次のような剛体のペアを見つける責任があります。 潜在的に シミュレーションに含まれるボディのセット全体の中から、衝突し、確実に衝突していないペアを除外します。このステップでは、剛体の数に応じて非常に適切にスケーリングして、 または （（ 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) d2y > 0.0f) return FALSE; return TRUE;

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

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

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

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

ザ・ 並べ替えとスイープ メソッド（別名 スイープとプルーン ）は、剛体シミュレーションで使用するための物理プログラマーの間でお気に入りの選択肢の1つです。ザ・ 弾丸物理学 たとえば、エンジンにはこのメソッドの実装があります。 btAxisSweep3 クラス。

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

並べ替えとスイープのアルゴリズムでは、すべてを挿入します b そして です 単一のリスト内の値をスカラー値で昇順に並べ替えます。それから私達は 掃く またはリストをトラバースします。いつでも b 値が検出されると、対応する間隔が次の別のリストに保存されます。 アクティブな間隔 、そしていつでも です 値が検出されると、対応する間隔がアクティブな間隔のリストから削除されます。いつでも、すべてのアクティブな間隔が交差しています。 （チェックアウト デビッドバラフの博士論文 、p。詳細は52。使用することをお勧めします このオンラインツール 間隔のリストは、シミュレーションの各ステップで再利用できます。ここで、を使用してこのリストを効率的に再ソートできます。 挿入ソート 、ほぼソートされたリストのソートに適しています。

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

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

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

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

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

狭いフェーズ

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

凸面と凹面の形状

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

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

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

ザ・ 凸包 形状のは、それを完全に含む最小の凸形状です。 2次元の凹多角形の場合、各頂点に釘を打ち、すべての釘に輪ゴムを巻き付けるようなものです。ポリゴンまたは多面体、またはより一般的には点のセットの凸包を計算するには、使用するのに適したアルゴリズムは次のとおりです。 クイックハル アルゴリズム。平均時間計算量は または （（ n ログ 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 エッジの角度はエッジベクトルに垂直で、ポリゴンの外側を指します。各ポリゴンの各エッジについて、他のポリゴンのすべての頂点がであるかどうかを確認する必要があります。 前に エッジの。

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

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

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

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

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

サポート機能

に サポート機能 s に（（ d ）形状の境界上の点を返しますにベクトル上で最も高い射影を持つ d 。数学的には、内積が最も高くなります。 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 highest) { highest = dot; support = v; } } return support; }

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

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

小切手 ジーノ・ヴァン・デン・ベルゲンの論文 他の形状の中でも、円柱や円錐のサポート関数の例をさらに見つけることができます。

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

ミンコフスキー和

ザ・ ミンコフスキー和 2つの形のにそしてBと定義されている：

つまり、に含まれるすべてのポイントの合計を計算しますにそしてB。結果は次のようになります インフレ にとB。

同様に、 ミンコフスキーの違い なので：

ミンコフスキー和として書くこともできますにと-B：

凸型の場合にそしてB、A⊕B凸面でもあります。

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

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

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

言い換えれば、間の距離にそしてBから出てくる最短のベクトルの長さですににB。このベクトルはに含まれていますA⊖Bそしてそれは最小の長さのものであり、その結果、原点に最も近いものになります。

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

シンプレックス

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

GJKの動作

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

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

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

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

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

GJKアルゴリズムの詳細で詳細な説明については、論文をご覧ください。 凸オブジェクトの衝突検出のための高速で堅牢なGJK実装 、Gino vandenBergenによる。のブログ dyn4j 物理エンジンにも GJKへの素晴らしい投稿 。

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

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

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

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

ザ・ 侵入深さ の長さです 最小並進ベクトル （MTV）は、交差する形状を変換して他の形状から分離できる最小のベクトルです。

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

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

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

EPAアルゴリズムは論文に記載されています 3Dゲームオブジェクトでの近接クエリと侵入深さの計算 、Gino van denBergenによっても書かれました。 dyn4jブログにも EPAについての投稿 。

継続的な衝突検出

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

継続的な衝突検出技術は、 いつ シミュレーションの前のステップと現在のステップの間で2つの物体が衝突しました。彼らは計算します 影響の時間 、そのため、時間を遡ってその時点での衝突を処理できます。

衝撃の時間（または接触の時間） t c 2つの物体間の距離がゼロになる瞬間です。時間に沿った2つの物体間の距離の関数を書くことができれば、私たちが見つけたいのは最小のものです ルート この関数の。したがって、衝突計算の時間は 求根問題 。

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

形状が円であると仮定して、問題を単純化しましょう。 2つのサークルの場合 C 1そして C 2、半径付き r 1そして r 2、ここで重心 バツ 1そして バツ 2重心と一致する（つまり、重心を中心に自然に回転する）場合、距離関数は次のように記述できます。

ステップ間の直線運動を考慮すると、次の関数を次の位置に記述できます。 C 1から t 私 -1に t 私

からの線形補間です バツ 1（（ t 私 -1）に バツ 1（（ t 私 ）。同じことができます バツ 2。この区間では、別の距離関数を記述できます。

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

非円の連続衝突検出

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

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

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

たとえば、物体の1つの角速度が高すぎる場合など、収束するのに非常に多くの反復が必要になる場合があります。

衝突の解決

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

参考文献

衝突検出アルゴリズムや技術などの衝突物理学についてより深く理解することに興味がある場合は、この本 リアルタイムの衝突検出 、クリステルエリクソンによる、必需品です。

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

関連： ロボットプログラミング入門チュートリアル