我有一个由二进制空间分区树给出的 3d 体积。通常这些是由多边形模型和已经存储在树节点内的分割多边形组成的。
但我的不是，所以我没有多边形。每个节点都没有，但它是切割平面（例如，由法线和原点距离给出）。 因此，树仍然代表一个实心的 3D 体积，由所做的所有切割定义。但是，为了可视化，我需要此体积的多边形网格。如何有效地重建？
粗略的方法是将叶子的无限半空间转换为足够大的极点（例如立方体），并将它们中的每一个向上推到树上，通过它经过的每个节点的平面切割它。这似乎非常昂贵，因为树可能是不平衡的（例如，如果由凸多面体愚蠢地制成）。有什么经典的解决方案吗？
为了恢复多边形表面，您需要与平面相交。其中，多边形的每个顶点由三个平面的交点生成，每个边由两个平面的交点生成。但是，要使这种高效和数字稳定并非易事。所以我建议使用qhalf，这是 qhull 的一部分。可以在此处找到qhalf输入和输出的文档。当然，您可以将qhull（以及qhalf中的功能）用作库。