何时使用二进制空间分区，四叉树，八叉树？
我最近学习了二进制空间分区树及其在3Dgraphics和碰撞检测中的应用。 我也简要地阅读了有关四叉树和八叉树的材料。 你什么时候使用四叉树而不是bsp树，反之亦然？ 它们是可以互换的吗？ 如果我有足够的信息来填写这样的表格，我会很满意：
| BSP | Quadtree | Octree ------------+----------------+------- Situation A | X | | Situation B | | X | Situation C | | | X 什么是A，B和C？
你的问题没有明确的答案。 这完全取决于你的数据是如何组织的。
要记住的事情：
Quadtrees适用于大多数二维数据，如导航系统中的地图渲染。 在这种情况下，它比八分之一更快，因为它更好地适应几何，并保持节点结构小。
如果数据是三维的，则Octrees和BVH（包围体层次）将受益。 如果您的几何实体在3D空间中聚合，它也可以很好地工作。 （见Octree vs BVH ）
Oc-和Quadtrees的好处是，您可以随时停止生成树木。 如果您想使用graphics加速器来渲染graphics，它允许您在对象级别上生成树，并将每个对象通过一次绘制调用发送到graphicsAPI。 这比发送单个三angular形要好得多（如果您完全使用BSP-Tree，则必须执行此操作）。
BSP树真的是一个特例。 他们在二维和三维方面工作得非常好，但是生成良好的BSP-Trees本身就是一种艺术forms。 BSP树有缺点，你可能不得不把你的几何分割成小块。 这可以增加数据集的整体多边形数量。 它们对于渲染很好，但是对于碰撞检测和光线追踪，它们更好。
BSP树的一个不错的属性是，他们将多边形汤分解成一个结构，可以从任何相机位置完全渲染到前面（反之亦然），而不需要进行实际的sorting。 每个观点的顺序都是数据结构的一部分，并在BSP-Tree编译期间完成。
顺便说一句，这就是十年前他们如此受欢迎的原因。 Quake使用它们是因为它允许graphics引擎/软件光栅化器不使用昂贵的z缓冲区。
所有提到的树都只是树的家庭。 松散的八叉树，kd树混合树和许多其他相关结构也是如此。
BSP-Trees和其他types的三维树最大的实际区别是BSP-Trees可以更优化，但只能用于静态几何。 这是因为BSP树通常build造起来非常缓慢，通常需要数小时或数天的时间才能达到典型的静态城市游戏水平。
BSP-Trees花费较长时间build立的两个主要原因是（a）它们使用非轴alignment的分裂平面，这需要花费较长时间才能最佳地发现，并且（b）在轴边界上细分几何体，确保没有物体穿过分裂平面。
其他types的三维树（Octrees，Quadtrees，kd-tree，Bounding-Volume-Hierarchy）使用轴alignment的边界体积，并且（可选）允许体积重叠，因此包含的对象不需要在体积上切割边界。 这些都使树木不如BSP树木最佳，但更快build立，更容易改变的dynamic物体。
将这些因素推断出来
户外区域通常使用基于高度场的地面表示，简单的高度图或更复杂的地理mip映射技术，如ROAM。 地面本身不参与三维空间分割，只有放置在地面上的物体。
世界上有很多简单和相似的几何体（房屋，树木，小行星等）的例子，通常会使用非BSP树（如BVH），因为将几何体放入BSP树意味着复制和分割每个实例的细节几何。
相反，没有实例化的大型自定义静态网格（如城市场景或复杂的室内环境）通常会使用BSP树来提高运行时性能。 BSP-Tree在节点边界上拆分几何对于渲染性能很有帮助，因为BSP节点可以用作预组织的三angular形渲染批处理。 BSP-Tree也可以针对遮挡进行优化，避免需要绘制已知在其他几何体后面的BSP-Tree的部分。
请参阅：“ 八叉树与BVH” ，“ 边界卷层次教程” ，“ BSP教程” 。
BSP最适合城市环境。
Quadtree最适合用于地形等高度图
八叉树最适合用于三维空间中的几何结构，如太阳系。
BSP是加速碰撞检测的一个很好的select，取决于你使用的是哪种口味。 它们在点和线或光线testing方面速度特别快，对于体积较小的物体来说速度稍慢，而且稍微复杂一些。
至于它们在graphics中的使用，BSP几乎已经过时了。 像AABB树一样，Octrees可以很好地处理大视野剔除。
我没有太多的BSP经验，但是我可以说，当你渲染的场景很高的时候，你应该用八叉树来处理四叉树。 也就是说，身高是宽度和深度的一半以上 – 小规则。 一般来说，八叉树不会在四叉树上带来巨大的成本，而且它们有可能加快速度。 因人而异。
通常这些事情没有一个明确的答案。 我build议A，B和C是空间大小和区分的东西的函数的结果。
一个BSP对于一个更小，更简单的空间来说更好，因为你只想做遮挡。 如果你想要一个给定的光线的所有交叉点，你需要升级到四/四叉树。
至于四叉树与八叉树 – 你关心多less维度？ 两个维度是指四叉树，四个八叉树。 如前所述，由于四叉树可以在三维空间中工作，但是如果要让每个维度得到适当的处理，八叉树就是要走的路。
