3

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

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

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

4

3 回答 3

3

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

从此BSP 常见问题解答：

问题是分裂与树平衡之一。这些是相互排斥的要求。您应该根据您打算如何使用树来选择构建好树的策略。

于 2008-10-02T16:24:09.720 回答
2

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

与其随机选择一个 tri 来用作分割平面，不如尝试几个（可能是所有这些，或者可能是随机抽样）并根据一些启发式方法选择一个。启发式通常基于 (a) 生成的子节点的平衡程度，以及 (b) 将拆分多少 tris。

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

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

于 2008-10-02T16:20:37.577 回答
1
  • 尝试选择（可能）被大多数平面分割的平面作为分割平面。分割平面不能分割。
  • 尝试选择前后飞机数量接近的飞机。
  • 尝试选择不会导致太多分裂的飞机。
  • 尝试选择与许多其他表面共面的平面

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

于 2012-12-19T04:51:59.330 回答