How to check if a given BSP tree is optimal?

Question

I have a polygonal triangle soup for which I would like to build a BSP tree. My current program simply creates a BSP tree, inserting a random triangle from the model one at a time, until all the triangles are consumed, and then checks the depth and width of the tree and remembers the best result it achieved (lowest depth, lowest width).

By definition, the best depth will be log2 (n) (or less if the grouped triangles are grouped?), Where n is the number of triangles in my model, and the best width will be n (this means that no splitting has occurred). But there are certain configurations of triangles for which this peak will never be reached.

Is there an effective test to check the quality of my BSP tree? In particular, I am trying to find a way for my program to know that this should stop looking for a more optimal design.

Answer 1

Building an optimal tree is an NP-complete problem. Determining whether a given tree is optimal is essentially the same problem.

From this BSP faq :

The problem is splitting compared to balancing trees. They are mutually exclusive requirements. You should choose your strategy to create a good tree based on how you intend to use the tree.

Answer 2

BSP, , , .

, tri , (, , , ) . , , (), , () .

, -.

, , , , , "".

Answer 3

• , () . .
• , , .
• Try to choose a plane that does not cause too many splits.
• Try to choose a plane that will be coplanar with lots of other surfaces.

You will need to measure these criteria and come up with a scoring system to decide which one is likely to be a good choice for the separation plane. For example, the farther the balance, the more points it loses. If it causes 20 splits, then the penalty is -5 * 20 (for example). Choose the one that works best. You do not need to try every polygon, just find a pretty good one.