多くの移動オブジェクト (球体、三角形、ボックス、点など) を処理するのに最適なデータ構造は何だろうと考えていました。Nearest Neighbor と Collsion detection という 2 つの質問に答えようとしています。
伝統的に、R ツリーのようなデータ構造は最近傍クエリに使用され、Oct/Kd/BSP は静的オブジェクトまたは非常に少数の移動オブジェクトを扱う衝突検出問題に使用されることを認識しています。
他にもっと良いものがあることを願うばかりです。
私はすべての助けに感謝します。
octree でシーンを分割し、シーンの一貫性を利用できます。テストしている移動オブジェクトは、その速度に応じて、特定のフレーム数の間、ツリーの特定のノードに配置されます。これは、ノードにあると想定できるため、ノードにない多くのオブジェクトをすばやく切り取ることができることを意味します。もちろん、オブジェクトがパーティションの端に近い場合は、オブジェクトが存在するノードを更新する必要があります。
動く物体には方向と速度があります。オブジェクトの移動方向から垂直分割を使用して、シーンを 2 つのセクションに簡単に分割できます。この分割の反対側にあるオブジェクトはチェックする必要はありません。もちろん、他のオブジェクトの速度を補正します。したがって、他のオブジェクトが適度に遅い場合は、それ以降のチェックから簡単に除外できます。
軸に沿ったバウンディング ボックスなどを使用して、テストする形状を常に単純化します。初期衝突試験
オブジェクトと別の移動オブジェクト間の距離と速度を取得できます。他の移動オブジェクトがより速い速度で同じ一般的な方向に移動している場合、チェックから除外できます。
オブジェクトの形状に応じて、他にも多くの最適化があります。円、正方形、またはより複雑な形状にはすべて、移動中に実行できる特定の最適化があります。
一部のオブジェクトが停止するか、移動を停止できると仮定すると、停止するオブジェクトを追跡できます。これらのオブジェクトは静的オブジェクトのように扱うことができるため、チェックが高速になり、すべての静的最適化手法をそれらに適用できます。
私はもっと知っていますが、頭のてっぺんから何も思いつきません。しばらくこれをしていません。
もちろん、これは衝突検出の方法によって異なります。速度に基づいてオブジェクトの位置を段階的に更新し、静的であるかのようにチェックしていますか。または、形状を押し出し、最初の衝突ポイントを計算することで、速度を補正していますか。前者は、高速で移動するオブジェクトに対して小さなステップが必要です。後者はより複雑で費用がかかりますが、より良い結果が得られます。また、回転するオブジェクトを使用する場合は、少し複雑になります。
衝突検出を行うための興味深い方法の1つは、特別な八分木構造内に編成された軸方向に整列したバウンディングボックス（AABB）を使用することです。AABBは、最大6つの比較を実行するだけでよいため、粗い衝突の計算を非常に迅速に実行できるため、AABBの助けになります。
octree構造で使用する必要のあるトリックがいくつかあります。
1）ノードが占める境界領域は、通常の八分木（八分木が重なり合うことなく空間を分割する場合）の場合の2倍の大きさである必要があります。各ノードは、隣接するノードの面積の半分と重なる必要があるためです。AABBは1つのノードにのみ属することができるため、この余分なサイズとオーバーラップにより、AABBは1つのノードに長期間留まることができます。
2）各ノード（おそらく階層の各レベル）でも、ノードの隣接ノードへのリンクを保持します。これには多くの余分なコードが含まれますが、O（2logn）時間ではなくO（1）時間に近いノード間で要素を移動できます。
octreeがメモリを大量に消費している場合は、スパースoctree構造を使用するように変更して、実際にエンティティを含むゲームワールドの部分のツリーのみを保持することができます。ただし、これは、エンティティがワールド内を移動するときに、フレームごとにより多くの計算を実行する必要があることを意味します。
octreeの代わりに試してみたい他のアイデアは、kd-tree（これが正しい名前だと思います）を使用するか、AABBを使用して構造を下から上に構築することです。
KDツリー（メモリから）は、軸方向に整列した平面を使用してスペースを分割するため、AABBでの使用に適しています。
もう1つのアイデアは、八分木生成を上から下に強制する代わりに（全世界を包むボックスから始めて）、基本エンティティから構築し、最大のものが全世界を包含するまで成長するより大きなAABBを構築します。多くの動きの速いエンティティでどのように機能するかはわかりませんが。
（この種の空間ゲーム開発コーディングを行ってからしばらく経ちました。）
Bounding Spheres は、おそらく多くの移動オブジェクトに役立ちます。オブジェクトの半径の二乗を計算し、その中心から追跡します。2 つのオブジェクトの中心間の距離の 2 乗が、2 つのオブジェクトの半径の 2 乗の和よりも小さい場合、衝突の可能性があります。すべては二乗距離で行われます。平方根はありません。
オブジェクト間の最小二乗距離で最近傍を並べ替えることができます。もちろん、衝突検出は複雑になる可能性があり、非球形のオブジェクトでは、境界球は必ずしも衝突情報を取得するわけではありませんが、衝突を比較する必要があるオブジェクトのツリーを非常にうまくプルーニングできます。
もちろん、オブジェクトの中心を追跡する必要があります。理想的には、境界球のサイズを再計算する必要がないように、各オブジェクトを固定する必要があります (ただし、再計算は特に難しいものではありません。非剛性ですが、複雑になります)。
基本的に、データ構造に関する質問に答えるために、すべてのオブジェクトをマスター配列に保持できます。デカルト座標に基づいてオブジェクトをすばやく並べ替えることができるマスター配列内のオブジェクトへの参照で構成される「領域」配列のセットがあります。「領域」配列には、マスター オブジェクト配列の最大オブジェクト半径の少なくとも 2 倍のオーバーラップが定義されている必要があります (それが可能であれば、オブジェクト境界球のスケーリングとオブジェクト数の問題が明らかに発生します)。
それができたら、領域内のすべてのオブジェクトの距離を互いに比較することにより、簡単な衝突テストを行うことができます。繰り返しますが、ここで領域の定義が重要になります。なぜなら、領域の数と比較の数との大きなトレードオフを行っているからです。ただし、距離の比較が単純な減算 (およびもちろん abs() 演算) に帰着するという理由だけで、少し単純になります。
もちろん、非球状オブジェクト間の実際の衝突検出を行う必要があり、それは自明ではない可能性がありますが、その時点で潜在的な比較の数を非常に劇的に減らしました。
基本的に、これは 2 層のシステムです。1 つ目は領域配列です。これにより、シーンを大まかに並べ替えることができます。次に、リージョン内の距離を比較します。ここでは、衝突したオブジェクトに対して基本的な衝突検出と衝突フラグを立てます。
この種のアルゴリズムには、動的領域決定でツリーを使用して領域サイズを均等にし、「混雑した」領域で領域サイズが急速に大きくなりすぎないようにする余地があるでしょう。ただし、そのようなことは自明ではありません。オブジェクトのサイズが異なると、密度の分類が... 控えめに言っても複雑になるためです。
RDCは、特にオブジェクトがまばらな (交差が少ない) 場合に役立ちます。
スイープとプルーニングのブロード フェーズ + gjk ナロー フェーズ