来自BSP的多边形

Question

我有一个由二进制空间分区树给出的3d体积。通常，这些多边形模型是由多边形模型构成的，拆分的多边形已经存储在树节点内。

但是我的不是，所以我没有多边形。每个节点除了它的剖切面之外什么都没有(例如，法线和原点距离)。因此，树仍然表示由所做的所有切割定义的实体3d体积。然而，为了可视化，我需要一个这个体积的多边形网格。怎样才能有效地重建呢？

粗略的方法是将叶子的无限半空间转换为足够大的多面体(例如，立方体)，并将它们中的每一个向上推到树上，根据它经过的每个节点的平面对其进行切割。这似乎是非常昂贵的，因为树可能是不平衡的(例如。如果愚蠢地由凸多面体制成)。有什么经典的解决方案吗？

Answer 1

为了恢复多边形曲面，您需要使平面相交。其中多边形的每个顶点由三个平面的交点生成，每条边由两个平面的交点生成。但是，使这种高效和数字稳定并不是一项微不足道的任务。所以我建议使用qhull中的qhalf。可以在here中找到qhalf的输入和输出文档。当然，您可以将qhull (以及来自qhalf的功能)用作library。