2

私はゲーム エンジンを構築していますが、疑問に思っていました: O(N^log N) の時間の複雑さを持つ衝突検出用のアルゴリズムはありますか?

私はまだコーディングを書いていませんが、O(N^2) アルゴリズムしか考えられません (つまり、衝突があるかどうかを確認するためにオブジェクトのリストをループする 2 つの for ループ)。

アドバイスやヘルプをいただければ幸いです。

ありがとう

4

4 に答える 4

3

空間パーティショニングは、O(n log(n)) ソリューションを作成できます。オブジェクトの正確な構造と性質に応じて、別の空間分割アルゴリズムが必要になりますが、最も一般的なのは octree と BSP です。

基本的に、空間分割の考え方は、オブジェクトが占有するスペースによってオブジェクトをグループ化することです。ノード Y のオブジェクトがノード X のオブジェクトと衝突することはありません (X が Y のサブノードでない限り、またはその逆でない限り)。次に、どのノードに移動するかによってオブジェクトを分割します。私はoctreeを自分で実装しました。

于 2012-05-10T16:35:14.373 に答える
2

オブジェクトを領域ごとに並べ替えることで、チェックの回数を最小限に抑えることができます。( 0,0 に近いオブジェクトと 1000,1000 に近いオブジェクト間の衝突をチェックしても意味がありません)

明らかな解決策は、スペースを連続して半分に分割し、ツリー ( BSP ) 構造を使用することです。これはオブジェクトのまばらな雲に最適ですが、そうしないと、境界近くのオブジェクトが境界のちょうど反対側にあるオブジェクトに衝突するかどうかを常にチェックする必要があります。

于 2012-05-10T16:27:45.670 に答える
2

相互作用の長さが制限されていると仮定します。つまり、2 つのオブジェクトが特定の距離にある場合、それ以上の相互作用はありません。その場合、通常、スペースを適切なサイズのドメインに分割します (たとえば、各方向の相互作用の長さ)。相互作用を粒子に適用するには、他のすべての粒子が相互作用の長さよりも遠くにあることが保証されているため、それ自体のドメインと最も近い隣接ドメインを通過するだけで済みます。もちろん、パーティクルの更新時にドメイン境界が交差しているかどうかを確認し、それに応じてドメイン メンバーシップを調整する必要があります。相互作用するペア数の減少による大幅なパフォーマンスの向上を考慮すると、この余分な簿記は問題ありません。より多くのトリックについては、数値 N-Body-Simulation に関する科学書をお勧めします。

もちろん、各ドメインには、そのドメインにある粒子の独自のリストがあります。シミュレーションで粒子の中心的なリストを持ち、すべてのエントリを調べて、現在のドメインにあるか隣接するドメインにあるかをそれぞれチェックしても意味がありません。

于 2012-05-10T16:29:54.123 に答える
1

私は 3D での位置に oct-tree を使用していますが、これはかなり不均一に分散する可能性があります。ツリー (再) ビルドは、通常、bot O(N log(N)) と非常に高速です。次に、特定の粒子のすべての衝突を見つけることは、O(K) で実行できます。K は粒子ごとの衝突の数です。特に、係数 log(N) はありません。したがって、すべての衝突を見つけるには、ツリーの構築後に O(K*N) が必要です。

于 2012-05-10T17:04:13.557 に答える