我最近了解了二进制空间分区树及其在3d图形和碰撞检测中的应用。我还简要阅读了有关四叉树和八叉树的材料。什么时候在bsp树上使用四叉树，反之亦然？它们可以互换吗？如果我有足够的信息来填写这样的表格，我将感到满意：

| BSP | Quadtree | Octree
------------+----------------+-------
Situation A |  X  |          |
Situation B |     |     X    |
Situation C |     |          |   X

什么是A，B和C？

解决方案

我对BSP没有太多经验，但是我可以说，当我们渲染的场景很高时，应该在四叉树上使用八叉树。也就是说，高度是宽度和深度的一半以上，这是经验法则。通常，八叉树不会比四叉树带来巨大的成本，它们有潜力使事情加速。 YMMV。

通常这些事情没有明确的答案。我建议A，B和C是空间大小和要区分的东西数量的函数的结果。

BSP更好地用于我们只想进行遮挡的更小，更简单的空间。如果要给定射线的所有交点，则需要升级到四边形/八叉树。

至于四叉树与八叉树，我们非常在乎几个维度？二维表示四叉树，四个表示八叉树。如前所述，四叉树可以在三个空间中工作，但是如果我们希望每个维都得到适当的处理，八叉树是最佳选择。

BSP最适合城市环境。

当我们在地形等上使用高度图时，四叉树最适合。

当我们在3d空间中有大量几何体(例如太阳系)时，Octree最适合。

BSP是加速碰撞检测的好选择，这取决于我们使用哪种口味。在点和线或者射线测试中，它们特别快，对于体积较大的事物，它们的速度稍慢一些，而有些复杂。

至于它们在图形中的使用，BSP几乎已经过时了。八叉树和ABB树木都可以很好地适用于诸如总能见度剔除之类的事情。

问题没有明确的答案。这完全取决于数据的组织方式。

要记住的事情：

四叉树最适合二维数据，例如导航系统中的地图渲染。在这种情况下，它比八叉树更快，因为它可以更好地适应几何形状并保持节点结构较小。

如果数据是三维数据，则八进制和BVH(边界卷层次结构)将受益。如果几何实体聚集在3D空间中，则效果也很好。 (请参阅Octree与BVH)

Ocand Quadtrees的好处是我们可以随时停止生成树。如果要使用图形加速器来渲染图形，则它允许我们仅在对象级别上生成树，然后通过一次绘画调用将每个对象发送到图形API。这比发送单个三角形要好得多(如果完全使用BSP-Tree，则必须执行此操作)。

BSP树确实是一个特例。它们在2D和3D中效果很好，但是生成好的BSP树本身就是一种艺术形式。 BSP树的缺点是我们可能必须将几何图形拆分成较小的部分。这会增加数据集的整体多边形数量。它们非常适合渲染，但是它们对于碰撞检测和光线跟踪则要好得多。

BSP树的一个不错的特性是它们将多边形汤分解为可以从任何摄像机位置完美地从头到尾(反之亦然)呈现的结构，而无需进行实际排序。从每个角度来看的顺序是数据结构的一部分，并且是在BSP-Tree编译期间完成的。

顺便说一下，这就是十年前它们如此受欢迎的原因。 Quake之所以使用它们，是因为它允许图形引擎/软件光栅化器不使用昂贵的z缓冲区。

提到的所有树木都是树木家族。有松散的八叉树，kd树混合树以及许多其他相关结构。