問題タブ [broad-phase]

最初から、衝突検出は O(n^2) の問題のように感じます。

多数のオブジェクトがあり、各オブジェクトが他のオブジェクトと衝突しているかどうかを確認する必要があります。ただし、各オブジェクトを他のすべてのオブジェクトに対してチェックするのは非常に非効率的であることを私は知っています。2 つのボールが互いに近くにさえないのに、なぜ比較的コストのかかる 2 つのボール間の衝突チェックを行うのでしょうか?

私が取り組んでいる簡単なプログラムの例を次に示します。

1000 個のボールがある場合、単純な衝突検出を使用すると、1000^2 (100 万) のコレクション チェックが発生します。この衝突チェックは、すぐに私のアプリケーションのボトルネックになりました。大まかなフェーズの剪定を実装する必要があります。

2D の円形オブジェクトで作業する場合、衝突チェックを削除するにはどのようなテクニックを使用する必要がありますか? QuadTrees、BSP、空間ハッシュなどについて読んだことがありますが、このユースケースに最も適した方法を整理するのは困難です。

何が最も効果的かについて誰か知っている人はいますか?

私は 2D 物理エンジンを構築しており、ブロード フェーズの衝突検出を追加したいと考えていますが、2 つまたは 3 つのタイプしか知りません。

• すべてを他のすべてと照合します (O(n^2) の複雑さ)
• Sweep and Prune (ソートとスイープ)
• Binary Space Partition についての何か (これを行う方法がわからない)

でも確かにもっとオプションがありますよね？彼らは何ですか？また、それぞれの基本的な説明または説明へのリンクを提供できますか?

私はこれを見てきましたが、私のニーズに最適なものではなく、利用可能なアルゴリズムのリストを求めています.

この場合、「ブロード フェーズ コリジョン検出」は、シミュレーション内のどのボディが十分に接近しているかを判断するために物理エンジンによって使用される方法であり、さらなる調査と、場合によってはコリジョンの解決を保証します。

並べ替えとスイープのブロードフェーズ システムを作成しようとしていますが、オーバーラップ レポートの段階でパフォーマンスの問題が発生しました。

私のペア レポート コードは、ボトルネックがある場所です。

基本的なアイデアは、すべての軸についてオーバーラップ ペアの一時的なリストを生成し、次に X のすべてのペアについて、ペアが Y と Z に存在するかどうかを確認することです。スタッキング キューブとコンテインメントを処理するために、ペアの生成にいくつかの追加チェックがあります。エッジケース。ペア生成コードは次のとおりです。

プロファイリングによって検出されたボトルネックは、== 演算子を介してペアを比較するときに発生します。これは、チェック自体のオーバーヘッドではなく、このようなチェックが多数実行されたためだと思われます。

次のように報告コードをペアにします。

私がソートとスイープ/スイープとプルーンで読んだ資料は、重複ペアの高速検索に対処する高速な方法、または実際には、効率的な方法で同等のペアを他の軸で検索する方法について詳しく説明していません。明らかに何かが足りないので、何か助けていただければ幸いです。