私はカリングが初めてです。一見したところ、ほとんどのオクルージョン カリング アルゴリズムはオブジェクト レベルであり、単一のメッシュを調べていないように見えます。これはゲーム レンダリングに実用的です。
私が探しているのは、特定の視点で遮られている単一のオブジェクト内のすべてのメッシュを高精度でカリングするアルゴリズムです。少なくともO(n log n)である必要があります。単純なメッシュごとの比較 ( O(n^2) ) は遅すぎます。
10,000 以上のメッシュの大きなオブジェクトを操作している場合でも、Blender GUI がオクルードされたメッシュをリアルタイムで識別していることに気付きました。そこではどのようなアルゴリズムが使用されていますか?
Blender は、Bullet 物理ライブラリの動的 AABB ツリー加速構造に基づいて、視錐台カリングとオクルージョン カリングの両方を実行します。オクルーダーとオブジェクトは、それらのバウンディング ボリューム (軸に沿ったバウンディング ボックス) によって表されます。
ビュー錐台カリングは、カメラ錐台が与えられた場合、AABB ツリーをトラバースするだけです。
オクルージョン カリングは、非常に単純なソフトウェア レンダラー (動的な AABB ツリー アクセラレーション構造を使用する基本的なレイ トレーサー) を使用して初期化される深度バッファーの一種であるオクルージョン バッファーに基づいています。オクルージョン バッファの解像度を選択して、精度と効率をトレードすることができます。
ドキュメントも参照してください http://wiki.blender.org/index.php/Dev:Ref/Release_Notes/2.49/Game_Engine#Performance
Blender ソース ツリーからの Blender 実装: Blender\source\gameengine\Physics\Bullet\CcdPhysicsEnvironment.cpp method bool CcdPhysicsEnvironment::cullingTest(PHY_CullingCallback callback, void* userData, PHY__Vector4 *planes, int nplanes, int occlusionRes)
また、Bullet Physics SDK には、Bullet/Extras/CDTestFramework にいくつかの C++ サンプル コードがあります。
メッシュレベルでカリングが行われない理由は、ゲームオブジェクトがすべてのカリングが発生するシーンレベルにあるのに対し、メッシュは非常にダムなレンダラーレベルのオブジェクトであるためです。メッシュレベルのカリングの決定は行われていません。オブジェクトをレンダリングする必要がある場合は、同様のシェーダー状態でプリミティブをバッチ処理する方法にすぎません。
本当にメッシュレベルでカリングする必要がある場合は、メッシュごとに1つのオブジェクトを作成してから、メッシュオブジェクトを含むグループオブジェクトを作成することをお勧めします。メッシュレベルでのカリングは通常それだけの価値がないため、実際にはパフォーマンスが低下する可能性があることに注意してください。ハードウェアへのデータ転送の流れを妨げる可能性があります。
Octreesのようなものを調べましたか?
通常、最初に行うことは、メッシュが互いに閉塞する可能性があるかどうかを確認することです。多くの場合、単純な境界プリミティブ (境界ボックスまたは境界球) を使用します。私の記憶が正しければ、Octreesがこれに役立ちます。
私は実際に私のアプリにとって十分に高速な単純なアプローチを試しました。
メッシュ内の各三角形について、メッシュ内の他の三角形によって遮られていないかどうかを確認します。つまり、O(n2)です。(精度が重要な場合は、少なくとも三角形の角の頂点も確認する必要がありますが、各三角形の中心点が遮られているかどうかを確認するだけで高精度の結果が得られました)。
ペンティアム 4 マシン (c++) では、約 10,000 個の三角形のバイナリ STL オブジェクトが完了するまでに約 1 分かかりました。
アルゴリズムは、最初に三角形を領域サイズや視点からの距離などでソートすることにより、最大 40% まで最適化できます (オクルードする可能性が高いため、より多くのチェックをスキップできます)。
次の最適化ステップは、三角形を octree に配置することです。これにより、オクルージョン チェックの数が大幅に削減されます。