何时使用二元空间分区、四叉树、八叉树？
我最近了解了二元空间划分树及其在 3D 图形和碰撞检测中的应用。 我还简要地阅读了有关四叉树和八叉树的材料。 什么时候你会使用四叉树而不是 bsp 树，反之亦然？ 它们可以互换吗？ 如果我有足够的信息来填写这样的表格，我会很满意：
| BSP | Quadtree | Octree
------------+----------------+-------
Situation A | X | |
Situation B | | X |
Situation C | | | X
A、B 和 C 是什么？
I have recently learned about binary space partitioning trees and their application to 3d graphics and collision detection. I have also briefly perused material relating to quadtrees and octrees. When would you use quadtrees over bsp trees, or vice versa? Are they interchangeable? I would be satisfied if I had enough information to fill out a table like this:
| BSP | Quadtree | Octree
------------+----------------+-------
Situation A | X | |
Situation B | | X |
Situation C | | | X
What are A, B, and C?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（8）
BSP 树和其他类型的 3d 树之间最大的实际区别是 BSP 树可以更优化，但仅适用于静态几何体。 这是因为 BSP 树的构建速度通常非常慢，对于典型的静态城市游戏关卡通常需要数小时或数天的时间。
BSP 树需要更长的时间来构建的两个主要原因是（a）它们使用非轴对齐的分割平面，这需要更长的时间才能找到最佳位置，（b）它们在轴边界上细分几何体，确保没有对象穿过分割平面。
其他类型的 3d 树（八叉树、四叉树、kd 树、边界体积层次结构）使用轴对齐的边界体积，并且体积（可选）允许重叠，因此不需要在体积上切割包含的对象边界。 这些都使得树的优化程度不如 BSP 树，但构建速度更快，并且更容易针对动态对象进行更改。
将这些因素推断到具体情况...
室外区域通常使用基于高度场的地面表示，无论是简单的高度图还是更复杂的地理 mip 映射技术（如 ROAM）。 地面本身不参与 3D 空间划分，仅参与放置在地面上的物体。
具有许多更简单且相似的几何体实例（房屋、树木、小行星等）的世界通常会使用非 BSP 树（例如 BVH），因为将几何体放入 BSP 树意味着复制和拆分每个实例的详细几何形状。
相反，没有实例的大型自定义静态网格物体（例如城市场景或复杂的室内环境）通常会使用 BSP 树来提高运行时性能。 BSP 树在节点边界上分割几何体这一事实有助于渲染性能，因为 BSP 节点可以用作预先组织的三角形渲染批次。 BSP 树还可以针对遮挡进行优化，从而避免需要绘制 BSP 树中已知位于其他几何体后面的部分。
另请参阅：Octree 与 BVH（存档自
原始），边界体积层次教程，BSP 教程。The biggest practical difference between BSP-Trees and other kinds of 3d-trees are that BSP-Trees can be more optimal but only work on static geometry. This is because BSP-Trees are generally very slow to build, often taking hours or days for a typical static urban game level.
The two main reasons BSP-Trees take longer to build are (a) they use non-axis-aligned splitting planes, which take longer to optimally find, and (b) they subdivide geometry on axis boundaries, assuring no objects cross split planes.
Other types of 3d-trees (Octrees, Quadtrees, kd-tree, Bounding-Volume-Hierarchy) use axis-aligned bounding volumes, and volumes are (optionally) allowed to overlap, so contained objects don't need to be cut on volume boundaries. These both make the trees less optimal than BSP-trees, but quicker to build, and easier to change for dynamic objects.
Extrapolating these factors into situations...
Outdoor areas typically use height-field based ground representations, either simple heightmaps or more complex geo-mip-mapping techniques like ROAM. The ground itself doesn't participate in the 3d space partitioning, only objects placed on the ground.
Worlds with lots of instances of simpler and similar geometry (houses, trees, asteroids, etc) will often use a non-BSP-tree (such as a BVH), because putting the geometry into a BSP-tree would mean duplicating and splitting the detail geometry for every instance.
Conversely, a large custom static mesh with no instancing, such as an urban scene, or a complex indoor environment, will typically use a BSP-Tree for improved runtime performance. The fact that the BSP-Tree splits geometry on node-boundaries is helpful for rendering performance, because the BSP nodes can be used as pre-organized triangle rendering batches. The BSP-Tree can also be optimized for occlusion, avoiding the need to draw portions of the BSP-Tree which are known to be behind other geometry.
See also: Octree vs BVH (archived from
original), Bounding Volume Hierarchy Tutorial, BSP Tutorial.你的问题没有明确的答案。 这完全取决于您的数据的组织方式。
需要记住的一点是：
四叉树最适合大多数二维数据，例如导航系统中的地图渲染。 在这种情况下，它比八叉树更快，因为它更好地适应几何形状并保持节点结构较小。
如果数据是三维的，八叉树和 BVH（边界体积层次结构）会受益。 如果您的几何实体聚集在 3D 空间中，它也能很好地工作。 （请参阅Octree 与 BVH) (存档自
原文)Oc- 和四叉树是你可以随时停止生成树。 如果您想使用图形加速器渲染图形，它允许您在对象级别生成树，并将单个绘制调用中的每个对象发送到图形 API。 这比发送单个三角形的性能要好得多（如果您充分使用 BSP 树，则必须这样做）。
BSP 树确实是一个特例。 它们在 2D 和 3D 中工作得非常好，但生成良好的 BSP 树本身就是一种艺术形式。 BSP 树的缺点是您可能必须将几何体分割成更小的部分。 这可以增加数据集的总体多边形数量。 它们非常适合渲染，但更适合碰撞检测和光线追踪。
BSP 树的一个很好的特性是它们将多边形汤分解为可以从任何相机位置从后到前完美渲染（反之亦然）的结构，而无需进行实际排序。 每个视点的顺序是数据结构的一部分，并在 BSP 树编译期间完成。
顺便说一句，这就是它们在 10 年前如此受欢迎的原因。 Quake 使用它们是因为它允许图形引擎/软件光栅器不使用昂贵的 z 缓冲区。
所有提到的树都只是树科。 还有松散八叉树、kd 树、混合树和许多其他相关结构。
There is no clear answer to your question. It depends entirely how your data is organized.
Something to keep in mind:
Quadtrees work best for data that is mostly two dimensional like map-rendering in navigation systems. In this case it's faster than octrees because it adapts better to the geometry and keeps the node-structures small.
Octrees and BVHs (Bounding Volume Hierarchies) benefit if the data is three dimensional. It also works very well if your geometric entities are clustered in 3D space. (see Octree vs BVH) (archived from
original)The benefit of Oc- and Quadtrees is that you can stop generating trees anytime you wish. If you want to render graphics using a graphic accelerator it allows you to just generate trees on an object level and send each object in a single draw-call to the graphics API. This performs much better than sending individual triangles (something you have to do if you use BSP-Trees to the full extent).
BSP-Trees are a special case really. They work very very well in 2D and 3D, but generating good BSP-Trees is an art form on its own. BSP-Trees have the drawback that you may have to split your geometry into smaller pieces. This can increase the overall polygon-count of your data-set. They are nice for rendering, but they are much better for collision detection and ray-tracing.
A nice property of the BSP-trees is that they decompose a polygon-soup into a structure that can be perfectly rendered back to front (and vice versa) from any camera position without doing an actual sort. The order from each viewpoint is part of the data-structure and done during BSP-Tree compilation.
That, by the way, is the reason why they were so popular 10 years ago. Quake used them because it allowed the graphic engine / software rasterizer to not use a costly z-buffer.
All the trees mentioned are just families of trees. There are loose octrees, kd-trees hybrid-trees and lots of other related structures as well.
我对 BSP 没有太多经验，但我可以说，当您渲染的场景很高时，您应该使用八叉树而不是四叉树。 也就是说，高度超过宽度和深度的一半——这是一个小小的经验法则。 一般来说，八叉树不会比四叉树带来巨大的成本，而且它们有可能加快速度。 YMMV。
I don't have much experience with BSPs, but I can say that you should go with octrees over quadtrees when you the scene you're rendering is tall. That is, the height is more than half the width and depth -- little rule of thumb. Generally, octrees won't bring a huge cost over quadtrees and they have the potential to speed things up a decent bit. YMMV.
BSP 是加速碰撞检测的一个不错的选择，具体取决于您使用的风格。 它们在点、线或射线测试中特别快，对于具有体积的东西来说速度稍慢并且稍微复杂一些。
至于它们在图形中的使用，BSP 几乎已经过时了。 八叉树和 AABB 树一样，非常适合粗略可见性剔除之类的事情。
BSPs are a good option for accelerating collision-detection, depending on which flavour you use. They're particularly fast at point and line or ray tests, somewhat less fast and a little more complicated for things with volume.
As for their use in graphics, BSPs are pretty much obsolete. Octrees work well for things like gross visibility culling, as do AABB trees.
BSP 最适合城市环境。
当您使用地形高度图等时，四叉树最适合。
当 3d 空间中有大量几何体（例如太阳系）时，八叉树最适合。
A BSP is best for urban environments.
A Quadtree is best for when you use a height map for terrain, etc.
An Octree is best for when you have clumps of geometry in 3d space, such as a solar system.
通常这些事情没有明确的答案。 我建议 A、B 和 C 是你的空间大小和你要区分的东西数量的函数结果。
Usually these things don't have a clear-cut answer. I would suggest that A,B, and C are the result of a function of the size of your space and the amount of stuff you are differentiating.
BSP 更适合您只想进行遮挡的更小、更简单的空间。 如果您想要给定光线的所有交点，则需要升级到四叉树/八叉树。
至于四叉树与八叉树 - 您最关心多少维？ 二维表示四叉树，四个表示八叉树。 如上所述，四叉树可以在三维空间中工作，但如果您希望每个维度都得到适当的处理，那么八叉树是最佳选择。
A BSP is better for a smaller, simpler space that you only want to do occlusion with. If you want all intersections for a given ray, you'll need to upgrade to a quad/octree.
As for quadtree vs. octree - how many dimensions do you care a lot about? Two dimensions means a quadtree, four an octree. As stated, as quadtree can work in three-space, but if you want each dimension given a proper treatment, an octree is the way to go.
除非你知道自己在做什么，否则总是选择八叉树，这样你就可以停止专注于过度优化并开始研究更重要的功能。 严重的是，瓶颈总是在其他地方，或者您正在围绕优化的系统设计代码，这最终会阻止以后某些类型的更改。
Unless you know what you are doing always go for the octrees so you can stop focusing on overoptimizing and start working on more serious features. Seriously the bottlenecks will always be somewhere else, or you are designing you code around a optimized system which in the end prevents certain types of changes later.