我有一个三角形的多边形汤，我想为其构建BSP树。我当前的程序只是通过一次从模型中插入一个随机三角形直到所有三角形都被消耗，来简单地构造一棵BSP树，然后它检查树的深度和广度并记住其获得的最佳分数(最低深度，最低广度) )。

根据定义，最佳深度将为log2(n)(如果将共平面的三角形分组了，深度会更小？)，其中n是模型中三角形的数量，最佳宽度为n(表示未发生分裂)。但是，某些三角形的配置永远无法达到此顶点。

是否有有效的测试来检查我的BSP树的质量？具体来说，我正在尝试为我的程序找到一种方法，让它知道它应该停止寻找更优化的构造。

解决方案

随机构建BSP树，直到我们碰巧找到一棵好树，这确实是非常低效的。

我们不想尝试随机选择一个tri作为分割平面，而是想尝试几个(可能是全部，或者是随机采样)，然后根据启发式方法选择一个。启发式方法通常基于(a)所得子节点的平衡程度，以及(b)拆分的Tris数量。

我们可以通过考虑将Tris的较小或者较大采样作为候选分割平面来权衡性能和质量。

但是最后，我们不能指望为任何实际数据获得完全最佳的树，因此我们可能必须满足"足够好"的要求。

构造最佳树是一个NP完全问题。确定给定的树是否最优是本质上相同的问题。

通过此BSP常见问题解答：

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.