问题标签 [bsp-tree]

我有一个由二进制空间分区树给出的 3d 卷。通常这些是由多边形模型制成的，并且分割的多边形已经存储在树节点中。

但我的不是，所以我没有多边形。每个节点都只有一个剖切面（例如，由法线和原点距离给出）。因此，树仍然代表一个实体的 3d 体积，由所有切割定义。但是，为了可视化，我需要这个体积的多边形网格。如何有效地重建它？

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

我有一个用于在等距游戏中进行深度排序的 BSP 树（我尝试了无数其他方法），它似乎很接近，但在我的游戏中我无法拆分资产。因此，拦截当前平面的项目，我只需将它们添加到“后面”和“前面”节点（如http://www.seas.upenn.edu/~cis568/presentations/bsp-techniques.pdf中所建议的） ）。

当我遍历树（从最低深度​​到最高深度）时，我只渲染一次精灵（我第一次接近它），但这似乎将一些精灵在显示顺序中放置得太低。

对此的任何见解将不胜感激。顺便说一句，这是在（主要是）C for iOS 中。

提前谢谢（我试着在这里回答一些问题，但你们都太快了！）。

我一直在研究 Quake 3 BSP 加载器。但是我无法正确渲染面部。

这是地图的顶点。这是我在地图上渲染人脸时发生的情况。

这是渲染的代码：

完整源代码：

所以我一直在实现我的第一个 BSP 树，我认为我发现我的逻辑存在缺陷。我对如何真正正确地重构它以使其按应有的方式工作感到非常迷茫。

这是构造函数（解释如下）：

简而言之，我们接收到一个std::vector< Polygon* >带有任意数量的堆分配的 Polygon 对象的 typedefed。然后我们想把它们分成两类：在某个中心元素前面的和后面的。自然地，我们声明了两个具有相同 typedef 的列表，front并back分别称它们为 和 。

首先，我们选择一个多边形（最终我想找到一个看起来最适合根分区平面的多边形），然后我们遍历我们的原始列表，检查以下三种情况之一：

（注意 -为简洁起见，我只是将我们的根分区多边形命名为root）

• POSITION_FRONT：我们知道列表中的当前多边形在root前面，所以我们自然地将这个多边形添加到我们的前面列表中。

• POSITION_BACK: 与 position 相同，唯一的区别是这个多边形在root后面。

• POSITION_SPLIT: 我们无法确定这个多边形是在根的前面还是后面，所以我们把它分成两部分，并将它的前后部分插入到各自的列表中。

最后，一旦我们将多边形划分为它们的前列表和后列表，我们将进一步细分我们的空间，使用根作为初始细分的基础。

现在，我们执行非常相似的操作序列，关键区别在于我们进一步细分已经分区的空间，直到每个多边形在节点树中具有给定位置，即在其父节点之前或之后。当然，我们递归地执行此操作。

我目前看到的问题在于POSITION_SPLIT上面 switch 语句中的案例评估：

结合其他两个因素：

• 对于从给定的参考参数中获得的每个多边形polygons，我们pop_back()在将其分配给临时对象后将其保存在列表中的指针。

• 与前面提到的相结合，每次调用都会SplitSpace(...)产生一个检查，看看它收到的列表是否为空。如果是这样，则什么都不做，并且该列表的递归细分已经完成。

由于这两个因素，我不禁认为，在POSITION_SPLIT案例评估中，第二次调用是没有用的：在第二次调用（以容纳拆分的后面部分）SplitSpace(...)之前，列表将被耗尽。

问题

那么，解决这个问题的方法是什么，至少能让我回到正确的轨道上呢？

我需要一个示例来说明如何将不平衡的 bsp 更改为平衡的 bsp 树。

请帮我。

我正在使用 Binary Space Partitioning Tree制作碰撞检测系统。我有两种对象：

• 需要检查与其他对象碰撞的动态对象（角色、射弹），
• 静态对象（如墙壁）不进行相互碰撞测试，但只能针对动态对象进行测试。

为此，我使用了两种数据结构：用于存储所有动态对象的列表，以及包含每个对象（动态或静态）的 BSP 树。因此，每个动态对象都存储在两个结构中。

最后，我通过遍历我的列表并使用树来测试每个对象来执行我的碰撞检测，如下所示：

然而，在这一点上，我没有想到：两个动态对象之间的每次碰撞检查都会进行两次。例如 ：

组合测试：

• dyna - dyna （处理无用的情况）
• 动态-静态1
• dynA - dynB
• dynB - dynA（同上）
• dynB - 静态1
• dynB - dynB

为了跳过无用的检查，我想在每个对象上添加一个属性Order：它将是对象构造时给出的唯一标识符，并像这样使用：

这样，每个对象组合只进行一次碰撞检查。

我的问题是：如果这种技术是正确的（我的意思是它是一个好的设计吗？），并且由于每个对象在 C# 中都有一个唯一的引用，我可以像这样直接比较它们的引用吗：（？）

我们可以使用object.ReferenceEquals来查看两个引用是否相等，但是我们可以对这些引用进行实际比较吗？

我正在尝试从未排序的浮点数组构建二叉树以进行分配，但我无法弄清楚。我的目标是将未排序xdata的大小数组发送ndata到函数build_tree()，该函数使用函数 create_node() 创建一个新节点。在数组大小大于 1 的情况下，它将调用该函数paritition_data()（它工作正常，但我将它放在问题的底部以供参考），它将交换数组值的顺序，以便所有值小于mid落在它的左边，而更大的值在它的右边。该函数返回nleft， 左边的值的数量mid。然后我想递归调用partition_data()创建新的left和right子节点。我认为正是在这一步我的程序似乎失败了，尽管它编译，但程序似乎partition_data()无限递归调用，我不知道为什么。我很感激任何帮助。

这里是partition_data()：

我试图从粒子中理解以下函数假设，该函数确定了一条线的方程，该方程表示为位于线上的两个点的坐标数组：[x1，y1，x2，y2]。返回方程的函数是：

我不明白这个函数返回的 3 元素数组如何对应于直线方程。我感谢任何帮助，让我了解这个功能在做什么。

我正在从 3d 空间中的三角形构建 BSP 树。在构建 BSP 树之前，所有三角形都已转换为视图空间。因此，我使用点 (0, 0, 0) 作为观察者眼睛的位置，并从远到近遍历树并将所有访问过的三角形添加到列表中。

然后我遍历列表并使用正交投影变换三角形并将它们绘制到屏幕上。这在大多数情况下都有效，但有时我会因为错误的三角形排序而得到奇怪的伪影。如果我改用透视投影，这永远不会发生。

为什么正交投影会发生这种情况？解决正交投影下的可见性问题时，BSP 树是否不起作用？还是我需要采用我的眼睛位置？