问题描述
我最近了解到的二进制空间分割树和其应用到3D图形和碰撞检测。我也简要地细读与四叉树和八叉树的材料。当你在BSP树，反之亦然使用四叉树？他们是可以互换？我会满意，如果我有足够的信息来填写表格是这样的：
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
什么是A，B和C？
What are A, B, and C?
推荐答案
没有明确回答你的问题。这取决于你的数据完全是如何组织的。
There is no clear answer to your question. It depends entirely how your data is organized.
东西要记住的：
四叉树最适合的数据主要是二维像地图绘制的导航系统。在这种情况下，它比八叉树快，因为它适应更好的几何形状和保持了节点结构小
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.
八叉树和BVHs（包围盒层次结构）的好处，如果该数据是三维的。它也工作得很好，如果你的几何实体都集中在3D空间。 （见八叉树VS BVH ）
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)
OC-和四叉树的好处是，你可以停止生成树任何时候你的愿望。如果你想使用图形加速器，它允许你刚才生成的树在对象级和发送的每个对象在一个单一的牵伸调用图形API来渲染图形。这将执行多比发送单个三角形（东西你有，如果你使用的BSP树的最大范围内做的）更好。
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树是一种特殊情况真的。他们的工作非常非常好，在2D和3D，但创造良好的BSP树是自己的一种艺术形式。 BSP树有可能需要您的几何拆分成更小的缺点。这可以增加您的数据集的整体多边形计数。他们是很好的渲染，但他们多的冲突检测和射线跟踪更好。
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.
在BSP树的一个很好的特性是它们分解一个多边形汤成，可以完美呈现回前（反之亦然）从任何相机位置没有做一个实际的排序的结构。从每个角度来看顺序是数据结构的过程中BSP树编译一部分完成。
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.
这，顺便说一句，这就是为什么他们是如此受欢迎10年前的原因。地震使用它们，因为它允许图形引擎/软件光栅不使用昂贵的Z缓冲。
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.
提及的所有树木都只是家庭的树木。有松动八叉树，KD树混合树和许多其他相关的结构也是如此。
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.
这篇关于何时使用二进制空间划分，四叉树，八叉树？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！