仮想オブジェクトの衝突検出は、視覚化タスクにとって非常に重要な部分です。
挑戦する
そして、タスクは2つのオブジェクトが衝突（衝突）したかどうかを判断することです。
困難は、視覚化プリミティブを他のプリミティブと直接テストする場合、特にシミュレーションに関与する膨大な数のオブジェクトで、衝突計算が不当に大きなリソースを消費するという事実にあります。
このような計算を容易にし、視覚化プリミティブ間で直接チェックしないようにするため（最も時間がかかります）、境界チェックボリュームテクノロジーが発明され、衝突チェックがこのような重要なリソースを消費しないように視覚化オブジェクトを記述できるようになりました精度の損失。
つまり、境界ボリュームは、より複雑なオブジェクトに適合する単純な幾何学的形状です。
境界ボリューム
最もリクエストされた制限ボリューム：
-球（球）。
-座標軸上に配置されたバウンディングボックス（軸に配置されたバウンディングボックス-AABB、翻訳を許してください）。
-オブジェクト指向の境界ボックス（OBB）
-離散指向の多面体。 （離散指向のポリトープ-k-DOP）
-その他。
図1. BVの概要。
k-dop
それぞれに多くの長所と短所がありますが、k-DOPに専念しています。
図2. BVについてわかりやすい。
離散指向の多面体は、事前定義された数の境界面とその方向です。 名前のKは、そのような飛行機の数を表します。
たとえば、2次元4-DOPは、特定の2次元オブジェクトを表す通常の正方形です。 実際、AABBはk-DOPの特殊なケースです。
二次元AABBは4-DOPと同じ正方形です。
また、3次元のAABBは6-DOPと同じキューブです。
ただし、k-DOPはより多くのプレーンを使用することもできます。 そして、前述したように、そのような平面の向きは事前に選択されており、変更されません。
平面の方向は方向ベクトルによって決定され、その法線はセット{-1、0、1}によって制限されます。
たとえば、通常の正方形の場合、方向を持つ4つの平面（0、1）、（1、0）が必要です。
ここでは、2つの平面の方向について説明しますが、下、上、左、右から正方形を制限します。 合計で4つのプレーンがありますが、したがって、次のように書き込むこともあります：（0、±1）、（±1、0）
これらの法線は計算を非常に容易にします。
構造
k-DOPは、最小および最大間隔（スラブ）または距離のみで記述されます。 1つの平面上の2つの値。最終的には処理と保存が非常に簡単です。
図3. k-DOPの間隔。
たとえば、正方形の場合、覚えているように、4つのプレーンが必要です（k = 4）。 したがって、2（k / 2）の最小値と2つの最大値が必要です。
図4.三角形を説明する8-DOP
図4では、座標（3、1）、（5、4）、（1、5）の三角形が8-DOP、つまり8つの平面を使用して、方向ベクトル（1、0）、（0、 1）、（1、1）、（1、-1）。
この多面体を記述する間隔を数えましょう。
方向（1、0）を持つ最初の平面を取り、座標を乗算します。
3 * 1 + 1 * 0 = 3
5 * 1 + 4 * 0 = 5
1 * 1 + 5 * 0 = 1
ここでの最小値は1、最大値は5です。
平面（1、0）は、値1と5によって決定されます。
（0、1）平面の場合、同じ値は1と5です。
（1、1）-4および9。
（1、-1）--4および2。
交差チェック
少なくとも1つの平面が交差しない場合、構造全体も交差しません。
すべての間隔/平面が交差する場合のみ、k-DOP構造自体が交差します。 ただし、説明されているオブジェクトは交差しない可能性があることに注意してください。
したがって、2つのオブジェクトのk-DOP構造が衝突すると、それらのオブジェクトは衝突する可能性があると言われています。
boolオーバーラップ（const KDop＆a、const KDop＆b、unsigned k）
{
for（符号なしi = 0; i <k / 2; ++ i）
{
if（a.min [i]> b.max [i] || a.max [i] <b.min [i]）
{
falseを返します。
}
}
trueを返します。
}
境界ボリューム階層
判明したように、バウンディングボリュームを使用すると、衝突を簡単に確認できますが、少し正確さが失われます。
したがって、単純なオブジェクトの場合、不必要なチェックを除外するために、AABBやk-DOPなどの境界ボリュームを最初にテストし、その後プリミティブに切り替えます。
しかし、複雑に構造化されたオブジェクトでは、境界ボリュームの階層が使用されます。 多くの場合、これらは単なるバイナリツリーであり、ノードは何らかのボリュームで制限された何らかのオブジェクトまたはオブジェクトの一部を定義します。
図5.オブジェクトのツリー。
このようなツリーの使用は、計算の数を減らすために必要です。
明らかに、衝突チェックがオブジェクトに対して直接実行される場合、時間がかかりすぎる可能性があります。 ボリュームの制限を使用すると、このタスクが少し簡単になります。 また、ボリュームを階層システムに制限することにより、オブジェクトの明らかにばらばらの部分を除外することができます。
通常、ツリーの作成は3つの方法のいずれかで行われます。
複雑なオブジェクト（ルートノード）は、それほど複雑ではないオブジェクト（子ノード）に分割されます。 たとえば、オブジェクトがなくなるまで、または何らかの条件が満たされるまで。 （トップダウン方式）
単純なオブジェクト（ノード）は、1つの複雑なルートオブジェクト（ボトムアップメソッド）が残るまで、より複雑なオブジェクトに結合されます。
または、すでに生成されたツリーにオブジェクトを追加します（挿入メソッド）。
このようなバランスのとれたツリーでは、検索の複雑度は他のバランスの取れたバイナリ検索ツリーの複雑度-O（logN）と等しくなります。
最も興味深い質問は、オブジェクトを子に分割する方法です。
左または右のサブツリーに収まるようにオブジェクトの部分を比較する基準は異なる場合があります。
最も単純な方法は、スペースを単純に半分に分割することです。特定の座標より上の座標を持つすべてのオブジェクトは右のサブツリーに移動し、残りはすべて左に移動します。
たとえば、選択した軸に沿って平均値を計算することもできます。
または、中央値を構築します。 または他の方法で。
図6.オブジェクトの別の抽象ツリー。
衝突検索
同様に、2つの階層構造での衝突検索もさまざまな方法で実装できます。
2つのオブジェクトの交差を確認するには、オブジェクトごとにツリー（BVHツリー）を作成する必要があります。ノードは、何らかの種類の境界ボリュームを通じてオブジェクトの一部を定義します。
次に、ツリーをウォークスルーして、あるツリーのノードを別のツリーのノードと比較し、境界ボリュームの交差がある方向にのみ移動する必要があります。
図7.再帰ツリーに一致するオブジェクト。
イラストと情報
1.クリステルエリクソン。 Real-Time Collision Detection、Volume 1-多面体に関する三角形と便利な段落。
2. Hamzah Asyrani SulaimanおよびAbdullah Bade。 衝突検出のための境界ボリューム階層。 -ショベル、バニー、そして衝突、階層について非常に簡単に。
3.ヨハネス・メズガー。 ダイナミックシミュレーション環境での衝突処理：バウンディングボリューム階層。 -木と多面体の間隔。 要約すると、ボリュームを制限する階層構造の主な問題についての論文。
4.ロルフ・ラケンパー。 ゲームプログラミング 衝突検出入門-タイトル誘惑と男性との傑作。 衝突検出の簡単な概要。
5. BVHツリーと離散指向の多面体を使用した交差点または衝突の検索の簡単な実装の例。