ツリー構造を使用して複雑なジオメトリの衝突検出性能を向上させるにはどうすればよいですか？

Question

VRコントローラを使用して多数の3Dオブジェクトとやり取りすることを可能にするWebVR-Vive-Draggingに似たVRアプリケーションを構築しました。これは、ユーザーがVRコントローラでオブジェクトをつかんで、移動または拡大縮小できることを意味します。

私のアプリケーションでは、衝突検出メカニズムは、ユーザーが現在VRコントローラでタッチしている正しいTHREE.Meshオブジェクトを検出します。最初は、シーン内のすべての3Dオブジェクトを反復処理し、境界球とコントローラの境界球を比較します。重複するオブジェクトは、適切なオブジェクトを見つけるためにTHREE.Raycasterでテストされます。これを実現するために各VRコントローラに3つのTHREE.Rayオブジェクトをセットアップしました。

問題：複雑な3Dオブジェクトがシーン内に存在する頂点の非常に大きな数の幾何学的形状を有する、すなわちTHREE.Meshオブジェクトは、次いで、衝突検出時のレイキャスティングが非常に遅くなります。したがって、私の問題は、シーン内の3Dオブジェクトの数ではなく、1つのオブジェクトのジオメトリの複雑さです。

オブジェクトのジオメトリを、含まれている頂点を参照して一連の境界ボックスに分割する方法を探しました。これにより、ボックスを最初にテストすることができます。その後、含まれている頂点をレイキャスティングに使用することができます。

OctreeまたはR-Treeなど、高速空間検索のためのツリーデータ構造があります。私はthreeocttreeがジオメトリをより小さなチャンクに分割することを可能にしていますが、これは古くなっているようです（Three.js r60）。

私の質問：誰でも、私の現在のレイキャスティングの衝突検出アプローチよりも良い解決法を知っていますか？より速い衝突検出を実現するために、Three.jsで複雑なジオメトリ分割を構築する方法はありますか？そうでない場合は、将来のThree.jsバージョンで、より高速な検索を可能にするような内部ジオメトリ分解を行うことが役立つ可能性があります。

Answer 1

Octreeは、複雑なメッシュのレイキャストを高速化する必要があるこれらの問題に対して私が個人的に見つける最も簡単な解決策です。いくつかの選択肢はBVH、K-Dツリー、およびRツリーです。

シーン全体に対して1つを更新する必要がないように、非自明なメッシュごとに別々のオクトリーを保存することができます。また、オブジェクトが変形されていて、変形されていない場合、メッシュに格納されているオクトリーを更新する必要はありません。オクトリーのAABBとの交点をテストする前に、オブジェクトの変換行列の逆数でレイを変換するだけです。

また、k-meansクラスタリングからオクツリー（空間クエリを高速化するのではなくセグメンテーションを決定するためにそれらを使用する）までのさまざまなテクニックを使用して、メッシュをセグメント化するまで、何百万ものポリゴンと頂点にまたがるメッシュをセグメント化しました接続性/隣接性データに基づいています。つまり、メッシュトラバーサル、レンダリング、および「サブメッシュLOD」のローカライズされた形式を可能にするためにキャッシュミスを減らすためにこれを行いました。ピッキング、レイキャスティング、衝突検出の場合は、オクトリーやBVHなどの空間インデックスを使用することをおすすめします。そうすれば、すべての単一の三角形をテストする必要がなくなります。