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:
我最近了解了二进制空间分区树及其在3d图形和碰撞检测中的应用。我还简要地阅读了与四叉树和八叉树相关的材料。你何时会在bsp树上使用四叉树,反之亦然?它们可以互换吗?如果我有足够的信息来填写这样的表格,我会感到满意:
| BSP | Quadtree | Octree
------------+----------------+-------
Situation A | X | |
Situation B | | X |
Situation C | | | X
What are A, B, and C?
什么是A,B和C?
7 个解决方案
#1
62
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.
Quadtrees最适用于导航系统中大多数二维的数据,如地图渲染。在这种情况下,它比八叉树更快,因为它更好地适应几何形状并保持节点结构小。
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)
如果数据是三维的,则八叉树和BVH(边界体积层次结构)会受益。如果几何实体聚集在3D空间中,它也可以很好地工作。 (参见Octree vs BVH)
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).
Oc-和Quadtrees的好处是你可以随时停止生成树木。如果您想使用图形加速器渲染图形,它允许您只在对象级别生成树,并通过单个绘图调用将每个对象发送到图形API。这比发送单个三角形要好得多(如果你完全使用BSP-Trees,你必须做的事情)。
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-Trees真的是一个特例。它们在2D和3D中工作得很好,但是生成好的BSP树本身就是一种艺术形式。 BSP-Trees的缺点是您可能需要将几何体分成更小的部分。这可以增加数据集的整数面数。它们很适合渲染,但它们更适合碰撞检测和光线跟踪。
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.
BSP树的一个很好的特性是它们将多边形汤分解成一个结构,可以从任何相机位置完美地渲染回前面(反之亦然),而无需进行实际排序。每个视点的顺序是数据结构的一部分,在BSP-Tree编译期间完成。
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.
顺便说一下,这就是他们10年前如此受欢迎的原因。 Quake使用它们是因为它允许图形引擎/软件光栅化器不使用昂贵的z缓冲区。
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.
提到的所有树木都只是树木的家庭。还有松散的八叉树,kd树混合树和许多其他相关结构。
#2
12
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.
BSP-Trees和其他类型的3d树之间最大的实际区别是BSP-Trees可以更加优化,但仅适用于静态几何。这是因为BSP-Trees通常构建起来非常慢,通常需要数小时或数天才能获得典型的静态城市游戏级别。
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.
BSP-Trees需要更长时间构建的两个主要原因是(a)它们使用非轴对齐的分裂平面,这需要更长的时间来最佳地找到,以及(b)它们在轴边界上细分几何,确保没有物体穿过分裂平面。
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.
其他类型的3d树(八叉树,四叉树,kd树,边界 - 体积 - 层次结构)使用轴对齐的边界体积,并且(可选)允许体积重叠,因此不需要在体积上切割所包含的对象边界。这些都使树木不如BSP树更优化,但构建速度更快,动态对象更容易更改。
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.
室外区域通常使用基于高度场的地面表示,简单的高度图或更复杂的地理mip映射技术,如ROAM。地面本身不参与三维空间划分,只有物体放置在地面上。
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.
具有更简单和相似几何(房屋,树木,小行星等)的大量实例的世界通常会使用非BSP树(例如BVH),因为将几何体放入BSP树将意味着重复和分裂每个实例的细节几何。
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.
相反,没有实例化的大型自定义静态网格(例如城市场景或复杂的室内环境)通常会使用BSP树来提高运行时性能。 BSP-Tree在节点边界上分割几何图形有助于渲染性能,因为BSP节点可以用作预先组织的三角形渲染批次。 BSP树也可以针对遮挡进行优化,从而无需绘制已知位于其他几何体后面的BSP树的部分。
See also: Octree vs BVH, Bounding Volume Hierarchy Tutorial, BSP Tutorial.
另请参阅:八叉树与BVH,边界体积层次教程,BSP教程。
#3
5
A BSP is best for urban environments.
BSP最适合城市环境。
A Quadtree is best for when you use a height map for terrain, etc.
当您使用地形等高度贴图时,Quadtree最适合。
An Octree is best for when you have clumps of geometry in 3d space, such as a solar system.
当您在3d空间中拥有几何体块(例如太阳系)时,八叉树最适合。
#4
3
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.
BSP是加速碰撞检测的好选择,具体取决于您使用的风味。它们在点和线或射线测试中特别快,对于有体积的东西来说速度稍慢,而且稍微复杂一些。
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几乎已经过时了。像AABB树一样,八分之一适用于总体能见度剔除等事情。
#5
0
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的经验,但我可以说当你渲染的场景很高的时候你应该使用四叉树的八叉树。也就是说,高度超过宽度和深度的一半 - 几乎没有经验法则。一般来说,八叉树不会带来超过四叉树的巨大成本,它们有可能加快速度。因人而异。
#6
0
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.
通常这些事情没有明确的答案。我建议A,B和C是你的空间大小和你所区分的东西的函数的结果。
#7
0
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.
对于更小,更简单的空间,BSP更适合您只想要遮挡。如果您想要给定射线的所有交叉点,则需要升级到四/八叉树。
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.
至于四叉树与八叉树 - 你关心多少维度?两个维度表示四叉树,四个八叉树。如上所述,由于四叉树可以在三维空间中工作,但如果您希望每个维度都得到适当的处理,那么八叉树就可以了。
#1
62
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.
Quadtrees最适用于导航系统中大多数二维的数据,如地图渲染。在这种情况下,它比八叉树更快,因为它更好地适应几何形状并保持节点结构小。
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)
如果数据是三维的,则八叉树和BVH(边界体积层次结构)会受益。如果几何实体聚集在3D空间中,它也可以很好地工作。 (参见Octree vs BVH)
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).
Oc-和Quadtrees的好处是你可以随时停止生成树木。如果您想使用图形加速器渲染图形,它允许您只在对象级别生成树,并通过单个绘图调用将每个对象发送到图形API。这比发送单个三角形要好得多(如果你完全使用BSP-Trees,你必须做的事情)。
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-Trees真的是一个特例。它们在2D和3D中工作得很好,但是生成好的BSP树本身就是一种艺术形式。 BSP-Trees的缺点是您可能需要将几何体分成更小的部分。这可以增加数据集的整数面数。它们很适合渲染,但它们更适合碰撞检测和光线跟踪。
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.
BSP树的一个很好的特性是它们将多边形汤分解成一个结构,可以从任何相机位置完美地渲染回前面(反之亦然),而无需进行实际排序。每个视点的顺序是数据结构的一部分,在BSP-Tree编译期间完成。
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.
顺便说一下,这就是他们10年前如此受欢迎的原因。 Quake使用它们是因为它允许图形引擎/软件光栅化器不使用昂贵的z缓冲区。
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.
提到的所有树木都只是树木的家庭。还有松散的八叉树,kd树混合树和许多其他相关结构。
#2
12
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.
BSP-Trees和其他类型的3d树之间最大的实际区别是BSP-Trees可以更加优化,但仅适用于静态几何。这是因为BSP-Trees通常构建起来非常慢,通常需要数小时或数天才能获得典型的静态城市游戏级别。
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.
BSP-Trees需要更长时间构建的两个主要原因是(a)它们使用非轴对齐的分裂平面,这需要更长的时间来最佳地找到,以及(b)它们在轴边界上细分几何,确保没有物体穿过分裂平面。
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.
其他类型的3d树(八叉树,四叉树,kd树,边界 - 体积 - 层次结构)使用轴对齐的边界体积,并且(可选)允许体积重叠,因此不需要在体积上切割所包含的对象边界。这些都使树木不如BSP树更优化,但构建速度更快,动态对象更容易更改。
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.
室外区域通常使用基于高度场的地面表示,简单的高度图或更复杂的地理mip映射技术,如ROAM。地面本身不参与三维空间划分,只有物体放置在地面上。
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.
具有更简单和相似几何(房屋,树木,小行星等)的大量实例的世界通常会使用非BSP树(例如BVH),因为将几何体放入BSP树将意味着重复和分裂每个实例的细节几何。
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.
相反,没有实例化的大型自定义静态网格(例如城市场景或复杂的室内环境)通常会使用BSP树来提高运行时性能。 BSP-Tree在节点边界上分割几何图形有助于渲染性能,因为BSP节点可以用作预先组织的三角形渲染批次。 BSP树也可以针对遮挡进行优化,从而无需绘制已知位于其他几何体后面的BSP树的部分。
See also: Octree vs BVH, Bounding Volume Hierarchy Tutorial, BSP Tutorial.
另请参阅:八叉树与BVH,边界体积层次教程,BSP教程。
#3
5
A BSP is best for urban environments.
BSP最适合城市环境。
A Quadtree is best for when you use a height map for terrain, etc.
当您使用地形等高度贴图时,Quadtree最适合。
An Octree is best for when you have clumps of geometry in 3d space, such as a solar system.
当您在3d空间中拥有几何体块(例如太阳系)时,八叉树最适合。
#4
3
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.
BSP是加速碰撞检测的好选择,具体取决于您使用的风味。它们在点和线或射线测试中特别快,对于有体积的东西来说速度稍慢,而且稍微复杂一些。
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几乎已经过时了。像AABB树一样,八分之一适用于总体能见度剔除等事情。
#5
0
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的经验,但我可以说当你渲染的场景很高的时候你应该使用四叉树的八叉树。也就是说,高度超过宽度和深度的一半 - 几乎没有经验法则。一般来说,八叉树不会带来超过四叉树的巨大成本,它们有可能加快速度。因人而异。
#6
0
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.
通常这些事情没有明确的答案。我建议A,B和C是你的空间大小和你所区分的东西的函数的结果。
#7
0
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.
对于更小,更简单的空间,BSP更适合您只想要遮挡。如果您想要给定射线的所有交叉点,则需要升级到四/八叉树。
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.
至于四叉树与八叉树 - 你关心多少维度?两个维度表示四叉树,四个八叉树。如上所述,由于四叉树可以在三维空间中工作,但如果您希望每个维度都得到适当的处理,那么八叉树就可以了。