How do I test if a given BSP tree is optimal?

Question

I have a polygon soup of triangles that I would like to construct a BSP tree for. My current program simply constructs a BSP tree by inserting a random triangle from the model one at a time until all the triangles are consumed, then it checks the depth and breadth of the tree and remembers the best score it achieved (lowest depth, lowest breadth).

By definition, the best depth would be log2(n) (or less if co-planar triangles are grouped?) where n is the number of triangles in my model, and the best breadth would be n (meaning no splitting has occurred). But, there are certain configurations of triangles for which this pinnacle would never be reached.

Is there an efficient test for checking the quality of my BSP tree? Specifically, I'm trying to find a way for my program to know it should stop looking for a more optimal construction.

Answer 1

Randomly building BSP trees until you chance upon a good one will be really, really inefficient.

Instead of choosing a tri at random to use as a split-plane, you want to try out several (maybe all of them, or maybe a random sampling) and pick one according to some heuristic. The heuristic is typically based on (a) how balanced the resulting child nodes would be, and (b) how many tris it would split.

You can trade off performance and quality by considering a smaller or larger sampling of tris as candidate split-planes.

But in the end, you can't hope to get a totally optimal tree for any real-world data so you might have to settle for 'good enough'.

Answer 2

Construction of an optimal tree is an NP-complete problem. Determining if a given tree is optimal is essentially the same problem.

From this BSP faq:

The problem is one of splitting versus tree balancing. These are mutually exclusive requirements. You should choose your strategy for building a good tree based on how you intend to use the tree.