何时使用二元空间分区、四叉树、八叉树？

StackOverflow https://stackoverflow.com/questions/99796

题

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

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

A、B、C 是什么？

有帮助吗？

解决方案

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

要记住的事情：

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

如果数据是三维的，八叉树和 BVH（边界体积层次结构）会受益。如果您的几何实体聚集在 3D 空间中，它也能很好地工作。（看 八叉树与 BVH)

Oc 和四叉树的好处是您可以随时停止生成树。如果您想使用图形加速器渲染图形，它允许您在对象级别生成树，并将单个绘制调用中的每个对象发送到图形 API。这执行 很多 比发送单个三角形更好（如果您充分使用 BSP 树，则必须这样做）。

BSP 树确实是一个特例。它们在 2D 和 3D 中工作得非常好，但生成良好的 BSP 树本身就是一种艺术形式。BSP 树的缺点是您可能必须将几何体分割成更小的部分。这可以增加数据集的总体多边形数量。它们非常适合渲染，但更适合碰撞检测和光线追踪。

BSP 树的一个很好的特性是它们将多边形汤分解为可以从任何相机位置从后到前完美渲染（反之亦然）的结构，而无需进行实际排序。每个视点的顺序是数据结构的一部分，并在 BSP 树编译期间完成。

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

所有提到的树都只是树科。还有松散八叉树、kd 树、混合树和许多其他相关结构。

其他提示

BSP 树与其他类型的 3d 树之间最大的实际区别是 BSP 树可以更优化，但仅适用于 静止的 几何学。这是因为 BSP 树的构建速度通常非常慢，对于典型的静态城市游戏关卡通常需要数小时或数天的时间。

BSP 树需要更长的时间来构建的两个主要原因是（a）它们使用非轴对齐的分割平面，这需要更长的时间才能找到最佳位置，以及（b）它们在轴边界上细分几何体，确保没有对象穿过分割平面。

其他类型的 3d 树（八叉树、四叉树、kd 树、边界体积层次结构）使用轴对齐的边界体积，并且体积（可选）允许重叠，因此不需要在体积上切割包含的对象边界。这些都使得树的优化程度不如 BSP 树，但构建速度更快，并且更容易针对动态对象进行更改。

将这些因素推断到情况中......

室外区域通常使用基于高度场的地面表示，无论是简单的高度图还是更复杂的地理 mip 映射技术（如 ROAM）。地面本身不参与 3D 空间划分，仅参与放置在地面上的物体。

具有许多更简单且相似的几何体实例（房屋、树木、小行星等）的世界通常会使用非 BSP 树（例如 BVH），因为将几何体放入 BSP 树意味着复制和拆分每个实例的详细几何形状。

相反，没有实例的大型自定义静态网格物体（例如城市场景或复杂的室内环境）通常会使用 BSP 树来提高运行时性能。BSP 树在节点边界上分割几何体这一事实有助于渲染性能，因为 BSP 节点可以用作预先组织的三角形渲染批次。BSP 树还可以针对遮挡进行优化，从而避免需要绘制 BSP 树中已知位于其他几何体后面的部分。

也可以看看： 八叉树与 BVH, 包围体层次结构教程, BSP教程.

BSP 最适合城市环境。

当您使用地形高度图等时，四叉树最适合。

当 3d 空间中有大量几何体（例如太阳系）时，八叉树最适合。

BSP 是加速碰撞检测的一个不错的选择，具体取决于您使用的风格。它们在点、线或射线测试中特别快，对于具有体积的东西来说速度稍慢并且稍微复杂一些。

至于它们在图形中的使用，BSP 几乎已经过时了。八叉树和 AABB 树一样，非常适合粗略可见性剔除之类的事情。

我对 BSP 没有太多经验，但我可以说，当您渲染的场景很高时，您应该使用八叉树而不是四叉树。也就是说，高度超过宽度和深度的一半——这是一个小的经验法则。一般来说，八叉树不会比四叉树带来巨大的成本，而且它们有可能加快速度。YMMV。

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

BSP 更适合您只想进行遮挡的更小、更简单的空间。如果您想要给定光线的所有交点，则需要升级到四叉树/八叉树。

至于四叉树 vs.八叉树 - 您最关心多少个维度？二维表示四叉树，四个表示八叉树。如上所述，四叉树可以在三维空间中工作，但如果您希望每个维度都得到适当的处理，那么八叉树是最佳选择。

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top