アンバランスからバランスの取れたBSPツリーに変換しますか？

Question

私は私がバランスBSPツリーにアンバランス BSPを変更する方法を示し例を必要としています。

私を助けてください。

Answer 1

Quakeでは、これは実際にマッパーに任せられています。 Quake BSPコンパイラは、起点からボリュームを二等分し始めます(0, 0, 0)。したがって、よりバランスのとれたBSPフレンドリなマップを作成するために、マッパーは3つの軸のすべてで原点を中心にジオメトリを中心に配置する必要があります。

私はあなたの問題にも同様の戦略が当てはまると思います。あなたのBSPノードの絶対的な境界（最小値と最大値）を見つけて、中央のポイントを計算してください。ここで、ツリーのパーティションを作成する必要があります。あなたのマップが完全に対称でない限り、完全にバランスのとれたツリーを達成することはできません。しかし、実際的な目的のために、これはあなたを比較的近づけます。