如何测试给定的 BSP 树是否最优？

Question

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

根据定义，最佳深度为 log2(n)（或者如果共面三角形分组则更小？），其中 n 是模型中三角形的数量，最佳宽度为 n（意味着没有发生分裂）。但是，某些三角形的配置永远无法达到这个顶峰。

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

Answer 1

构建最优树是NP完全问题。确定给定的树是否是最优的基本上是同样的问题。

来自 BSP常见问题解答：

  

问题是分裂对抗   树平衡。这些是相互的   独家要求。你应该   选择你的战略来建立一个   好树根据你的意图   使用树。

Answer 2

随机构建BSP树，直到你有机会获得一个好的，这将真的非常低效。

不是随机选择tri作为分割平面，而是想尝试几个（可能全部，或者可能是随机抽样）并根据一些启发式选择一个。启发式通常基于（a）生成的子节点的平衡程度，以及（b）它将分裂多少tris。

您可以通过考虑将较小或较大的tris采样作为候选分裂平面来权衡性能和质量。

但最终，您无法希望为任何真实数据获得完全最优的树，因此您可能不得不满足于“足够好”。

Answer 3

• 尝试选择（可能）被最多平面分割的平面作为分割平面。分割平面无法分割。
• 尝试选择一架前后飞机数量接近相同的飞机。
• 尝试选择不会造成太多裂缝的平面。
• 尝试选择一个与许多其他表面共面的平面

您必须对这个标准进行采样，并提出一个评分系统来决定哪一个最有可能成为分割平面的最佳选择。例如，越失去平衡，失去的分数就越多。如果它导致 20 次分裂，则惩罚为 -5 * 20（例如）。选择得分最高的一项。您不必对每个多边形进行采样，只需搜索一个相当好的多边形即可。