我最近了解了二进制空间分区树及其在3d图形和碰撞检测中的应用。我还简要阅读了有关四叉树和八叉树的 Material 。什么时候在bsp树上使用四叉树，反之亦然？它们可以互换吗？如果我有足够的信息来填写这样的表格，我将感到满意:
| BSP | Quadtree | Octree
------------+----------------+-------
Situation A | X | |
Situation B | | X |
Situation C | | | X
什么是A，B和C？
最佳答案
您的问题没有明确答案。这完全取决于数据的组织方式。
要记住的事情:
四叉树最适合二维数据，例如导航系统中的 map 渲染。在这种情况下，它比八叉树更快，因为它可以更好地适应几何形状并保持节点结构较小。
如果数据是三维的，则八进制和BVH(边界卷层次结构)将受益。如果您的几何实体聚集在3D空间中，则效果也很好。 (请参阅Octree vs BVH)(从original存档)
八叉树和四叉树的好处是您可以随时停止生成树。如果要使用图形加速器来渲染图形，则它允许您仅在对象级别上生成树，然后通过一次绘画调用将每个对象发送到图形API。这比发送单个三角形要好得多 (如果完全使用BSP-Tree，则必须执行此操作)。
BSP树确实是一个特例。它们在2D和3D中效果很好，但是生成好的BSP树本身就是一种艺术形式。 BSP树的缺点是您可能必须将几何拆分成较小的碎片。这会增加数据集的整体多边形数量。它们非常适合渲染，但是它们对于碰撞检测和光线跟踪则更好。
BSP树的一个不错的特性是，它们将多边形汤分解为可以从任何摄像机位置完美地从头到尾(反之亦然)呈现的结构，而无需进行实际排序。从每个 Angular 来看的顺序是数据结构的一部分，并且是在BSP-Tree编译期间完成的。
顺便说一下，这就是十年前它们如此受欢迎的原因。 Quake之所以使用它们，是因为它允许图形引擎/软件光栅化器不使用昂贵的z缓冲区。
提到的所有树木都是树木家族。有松散的八叉树，kd树混合树以及许多其他相关结构。
关于3d - 何时使用二进制空间分区，四叉树，八叉树？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/99796/