何时使用Binary Space Partitioning,Quadtree,Octree？

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

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

什么是A,B和C？

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

要记住的事情:

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

如果数据是三维的,则八叉树和BVH(边界体积层次结构)会受益.如果几何实体聚集在3D空间中,它也可以很好地工作.(参见Octree vs BVH)

Oc-和Quadtrees的好处是你可以随时停止生成树木.如果您想使用图形加速器渲染图形,它允许您只在对象级别生成树,并通过单个绘图调用将每个对象发送到图形API.这比发送单个三角形要好得多(如果你完全使用BSP-Trees,你必须做的事情).

BSP-Trees真的是一个特例.它们在2D和3D中工作得非常好,但是生成好的BSP树本身就是一种艺术形式.BSP-Trees的缺点是您可能需要将几何体分成更小的部分.这可以增加数据集的整数面数.它们很适合渲染,但它们更适合碰撞检测和光线跟踪.

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

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

提到的所有树木都只是树木的家庭.有松散的八叉树,kd树混合树和许多其他相关的结构.

BSP-Trees和其他类型的3d树之间最大的实际区别是BSP-Trees可以更加优化,但仅适用于静态几何.这是因为BSP-Trees的构建速度通常非常慢,通常需要数小时或数天来完成典型的静态城市游戏级别.

BSP-Trees需要更长时间构建的两个主要原因是(a)它们使用非轴对齐的分裂平面,这需要更长的时间来最佳地找到,以及(b)它们在轴边界上细分几何,确保没有物体穿过分裂平面.

其他类型的3d树(八叉树,四叉树,kd树,边界 - 体积 - 层次结构)使用轴对齐的边界体积,并且(可选)允许体积重叠,因此包含的对象不需要在体积上切割边界.这些都使树木不如BSP树更优化,但构建速度更快,动态对象更容易更改.

将这些因素外推到情境中......

室外区域通常使用基于高度场的地面表示,简单的高度图或更复杂的地理mip映射技术,如ROAM.地面本身不参与三维空间划分,只有物体放置在地面上.

具有更简单和相似几何(房屋,树木,小行星等)的大量实例的世界通常会使用非BSP树(例如BVH),因为将几何体放入BSP树将意味着重复和拆分每个实例的细节几何.

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

另请参阅:八叉树与BVH,边界体积层次教程,BSP教程.

BSP最适合城市环境.

当您使用地形等高度贴图时,Quadtree最适合.

当您在三维空间中拥有几何体时,例如太阳系,八角树最适合.