3

BSP ツリーを作成したい三角形のポリゴン スープがあります。私の現在のプログラムは、すべての三角形が消費されるまで、モデルからランダムな三角形を一度に 1 つずつ挿入して BSP ツリーを構築するだけです。その後、ツリーの深さと幅をチェックし、達成した最高のスコア (最小の深さ、最小の幅) を記憶します。 ）。

定義により、最適な深さは log2(n) (同一平面上の三角形がグループ化されている場合はそれ以下?) になります。ここで、n はモデル内の三角形の数であり、最適な幅は n (分割が発生していないことを意味します) です。しかし、この頂点に達することのない特定の三角形の配置があります。

BSP ツリーの品質をチェックするための効率的なテストはありますか? 具体的には、プログラムがより最適な構造を探すのをやめる必要があることをプログラムが知る方法を見つけようとしています。

4

3 に答える 3

3

最適なツリーの構築は NP 完全問題です。与えられたツリーが最適かどうかを判断することは、本質的に同じ問題です。

このBSP faqから:

問題は、分割とツリーのバランスの 1 つです。これらは相互に排他的な要件です。ツリーの使用方法に基づいて、優れたツリーを構築するための戦略を選択する必要があります。

于 2008-10-02T16:24:09.720 に答える
2

良いツリーが見つかるまでランダムに BSP ツリーを構築するのは、非常に非効率的です。

分割平面として使用するトライをランダムに選択する代わりに、いくつか (おそらくすべて、またはランダム サンプリング) を試して、ヒューリスティックに従って 1 つを選択します。ヒューリスティックは、通常、(a) 結果として生じる子ノードがどの程度バランスが取れているか、および (b) 分割される tri の数に基づいています。

Tris の小さいまたは大きいサンプリングを分割平面の候補として考慮することで、パフォーマンスと品質をトレードオフすることができます。

しかし、最終的には、実世界のデータに対して完全に最適なツリーを取得することは期待できないため、「十分」に落ち着かなければならない場合があります。

于 2008-10-02T16:20:37.577 に答える
1
  • 分割プレーンとして、最も多くのプレーンによって分割される可能性のある (可能性のある) プレーンを選択してください。分割面は分割できません。
  • 前面と背面の平面の数がほぼ同じ平面を選択するようにしてください。
  • 分割が多すぎない平面を選択してください。
  • 他の多くのサーフェスと同一平面上にある平面を選択してください

この基準をサンプリングし、スコアリング システムを考え出して、どの基準が分割面に適している可能性が最も高いかを判断する必要があります。たとえば、バランスが崩れれば離れるほど、より多くのスコアが失われます。20 回の分割が発生した場合、ペナルティは -5 * 20 になります (たとえば)。最も得点が高いものを選択してください。すべてのポリゴンをサンプリングする必要はありません。適切なポリゴンを検​​索するだけです。

于 2012-12-19T04:51:59.330 に答える