如何测试给定的 BSP 树是否最优？
我有一个三角形的多边形汤，我想为其构建一个 BSP 树。 我当前的程序只是通过从模型中一次插入一个随机三角形来构建一棵 BSP 树，直到所有三角形都被消耗为止，然后它检查树的深度和广度并记住它获得的最佳分数（最低深度、最低宽度） ）。
根据定义，最佳深度为 log2(n)（或者如果共面三角形分组则更小？），其中 n 是模型中三角形的数量，最佳宽度为 n（意味着没有发生分裂）。 但是，某些三角形的配置永远无法达到这个顶峰。
是否有有效的测试来检查 BSP 树的质量？ 具体来说，我试图找到一种方法让我的程序知道它应该停止寻找更优化的结构。
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.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
最优树的构建是一个NP完全问题。 确定给定的树是否是最优的本质上是同一个问题。
从这个 BSP 常见问题：
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:
在找到一棵好的 BSP 树之前随机构建 BSP 树的效率真的非常低。
您不想随机选择一个三角形用作分割平面，而是想尝试几个（可能是全部，或者可能是随机采样）并根据某种启发式选择一个。 启发式通常基于 (a) 结果子节点的平衡程度，以及 (b) 它将分割多少个三元组。
您可以通过考虑较小或较大的 tris 样本作为候选分割平面来权衡性能和质量。
但最终，您不能希望为任何现实世界的数据获得完全最佳的树，因此您可能不得不满足于“足够好”。
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'.
您必须对这个标准进行采样，并提出一个评分系统来决定哪一个最有可能成为分割平面的良好选择。 例如，越失去平衡，失去的分数就越多。 如果它导致 20 次分裂，则惩罚为 -5 * 20（例如）。 选择得分最高的一项。 您不必对每个多边形进行采样，只需搜索一个相当好的多边形即可。
You'll have to sample this criteria and come up with a scoring system to decide which one is most likely to be a good choice for a splitting plane. For example, the further off balance, the more score it loses. If it causes 20 splits, then penalty is -5 * 20 (for example). Choose the one that scores best. You don't have to sample every polygon, just search for a pretty good one.