When to use Binary Space Partitioning, Quadtree, Octree?我最近了解了二进制空间分区树及其在3d图形和碰撞检测中的应用。 我还简要阅读了有关四叉树和八叉树的材料。 什么时候在bsp树上使用四叉树，反之亦然？ 它们可以互换吗？ 如果我有足够的信息来填写这样的表格，我将感到满意：
什么是A，B和C？ 您的问题没有明确答案。这完全取决于数据的组织方式。 要记住的事情： 四叉树最适合大多数二维数据，例如导航系统中的地图渲染。在这种情况下，它比八叉树更快，因为它可以更好地适应几何形状并保持节点结构较小。
如果数据是三维的，则八进制和BVH(边界卷层次结构)将受益。如果您的几何实体聚集在3D空间中，则效果也很好。 (请参阅Octree与BVH)(存档于 八叉树和四叉树的好处是您可以随时停止生成树。如果要使用图形加速器来渲染图形，则它允许您仅在对象级别上生成树，然后通过一次绘画调用将每个对象发送到图形API。这比发送单个三角形要好得多(如果您完全使用BSP-Tree，则必须执行此操作)。 BSP树确实是一个特例。它们在2D和3D中效果很好，但是生成好的BSP树本身就是一种艺术形式。 BSP树的缺点是您可能必须将几何拆分成较小的碎片。这会增加数据集的整体多边形数量。它们非常适合渲染，但是它们对于碰撞检测和光线跟踪则更好。 BSP树的一个不错的特性是，它们将多边形汤分解为可以从任何摄像机位置完美地从头到尾(反之亦然)呈现的结构，而无需进行实际排序。从每个角度来看的顺序是数据结构的一部分，并且是在BSP-Tree编译期间完成的。 顺便说一下，这就是十年前它们如此受欢迎的原因。 Quake之所以使用它们，是因为它允许图形引擎/软件光栅化器不使用昂贵的z缓冲区。 提到的所有树木都是树木家族。有松散的八叉树，kd树混合树以及许多其他相关结构。 BSP树与其他3d树之间最大的实际区别是BSP树可以更优化，但仅适用于静态几何体。这是因为BSP树通常构建起来很慢，对于典型的静态城市游戏级别来说通常要花费数小时或数天。 BSP树需要花费更长的时间来建立的两个主要原因是：(a)它们使用了非轴对齐的分割平面，这需要更长的时间才能最佳地找到；(b)它们在轴边界上细分了几何形状，确保没有对象穿过分割平面。 其他类型的3d树(八角树，四叉树，kd树，边界体积层次结构)使用轴对齐的边界体积，并且体积可以(可选)重叠，因此不需要按体积切割包含的对象边界。两者都使树不如BSP树最佳，但构建起来更快，并且更容易更改动态对象。 将这些因素推断为情况... 室外区域通常使用基于高度场的地面表示，可以是简单的高度图，也可以使用更复杂的地理映射技术，例如ROAM。地面本身不参与3d空间分区，仅参与放置在地面上的对象。 具有许多简单且相似的几何体实例(房屋，树木，小行星等)的世界通常会使用非BSP树(例如BVH)，因为将几何体放入BSP树将意味着复制和拆分几何体。每个实例的细节几何。 相反，没有实例化的大型自定义静态网格物体(例如城市场景或复杂的室内环境)通常将使用BSP-Tree来提高运行时性能。由于BSP节点可以用作预组织的三角形渲染批处理，因此BSP树在节点边界上拆分几何图形这一事实有助于渲染性能。 BSP-Tree也可以针对遮挡进行优化，从而避免了绘制BSP-Tree已知位于其他几何图形后面的部分的需要。
另请参见：《 Octree与BVH》(从 BSP最适合城市环境。 当您将高程图用于地形等时，四叉树最适合。 当您在3d空间中有大量几何体(例如太阳系)时，Octree最适合。 BSP是加速碰撞检测的好选择，这取决于您使用哪种口味。它们在点和线或射线测试中特别快，对于体积较大的事物，速度稍慢一些，而复杂度则稍高一些。 至于它们在图形中的使用，BSP几乎已经过时了。八进制和ABB树木都可以很好地用于总可见性剔除等工作。 我对BSP的经验不足，但是我可以说，当您渲染的场景很高时，应该在四叉树上使用八叉树。也就是说，高度是宽度和深度的一半以上-几乎没有经验法则。通常，八叉树不会比四叉树带来巨大的成本，它们有潜力使事情加速。 YMMV。 除非您知道自己在做什么，否则总是会选择八叉树，这样您就可以停止专注于过度优化而着手开发更重要的功能。严重的是，瓶颈总是存在于其他地方，或者您正在围绕优化的系统设计代码，最终最终阻止了某些类型的更改。 BSP最好用于只希望进行遮挡的更小，更简单的空间。如果要给定射线的所有交点，则需要升级到四边形/八叉树。 至于四叉树还是八叉树-您在乎多少尺寸？二维表示四叉树，四个表示八叉树。如前所述，四叉树可以在三个空间中工作，但是如果您希望每个维度都得到适当的处理，那么八叉树是您的最佳选择。 通常，这些事情没有明确的答案。我建议A，B和C是空间大小和要区分的东西数量的函数的结果。 |
