79

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

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

什么是 A、B 和 C？

4

8 回答 8

74

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

要记住的事情：

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

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

Oc- 和 Quadtrees 的好处是您可以随时停止生成树。如果您想使用图形加速器渲染图形，它只允许您在对象级别上生成树，并在单个绘制调用中将每个对象发送到图形 API。这比发送单个三角形要好得多（如果您完全使用 BSP-Trees，您必须这样做）。

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

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

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

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

于 2008-09-19T10:07:04.623 回答
16

BSP-Trees 和其他类型的 3d-trees 之间最大的实际区别是 BSP-Trees 可以更优化，但只适用于静态几何。这是因为 BSP 树的构建通常非常缓慢，通常需要数小时或数天才能完成典型的静态城市游戏关卡。

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

其他类型的 3d 树（Octrees、Quadtrees、kd-tree、Bounding-Volume-Hierarchy）使用轴对齐的包围体，并且体积（可选）允许重叠，因此不需要在体积上切割包含的对象边界。这些都使得树不如 BSP 树优化，但构建速度更快，并且更容易为动态对象更改。

将这些因素外推到情况...

户外区域通常使用基于高度场的地面表示，简单的高度图或更复杂的地理 MIP 映射技术（如 ROAM）。地面本身不参与 3d 空间划分，只有放置在地面上的物体。

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

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

另请参阅：Octree vs BVH（存档自原来的)、包围体层次教程、BSP 教程。

于 2014-10-22T21:40:01.460 回答
9

BSP 最适合城市环境。

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

八叉树最适合在 3d 空间中有几何图形块时使用，例如太阳系。

于 2008-09-19T09:31:41.353 回答
3

BSP 是加速碰撞检测的好选择，具体取决于您使用的风格。它们在点、线或射线测试中速度特别快，但在体积测试中速度稍慢且复杂一些。

至于它们在图形中的使用，BSP 几乎已经过时了。八叉树适用于诸如总能见度剔除之类的事情，AABB 树也是如此。

于 2008-09-19T09:49:44.320 回答
1

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

于 2008-09-19T05:11:28.063 回答
1

除非您知道自己在做什么，否则总是选择八叉树，这样您就可以停止过度优化并开始研究更严肃的功能。严重的是，瓶颈总是在其他地方，或者您正在围绕一个优化的系统设计代码，最终阻止某些类型的更改。

于 2019-10-16T16:24:16.780 回答
0

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

于 2008-09-19T05:29:40.623 回答
0

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

至于四叉树与八叉树 - 您非常关心多少维度？二维表示四叉树，四维表示八叉树。如前所述，由于四叉树可以在三个空间中工作，但是如果您希望对每个维度进行适当的处​​理，那么八叉树就是要走的路。

于 2008-09-19T05:40:27.790 回答