用于三维地图的二进制空间分区树

Question

我有一个项目，它会拍摄地形图并使其成为3D对象。 当我绘制对象的3D矩形时，它的工作速度非常缓慢。我读了关于BSP树，我并没有真正理解它。有人可以解释如何在3D中使用BSP（也许举一个例子）？以及如何在我的情况下使用它，当地图中的某些山脉覆盖其他部分时，我需要组织矩形以便很好地绘制它们？

Answer 1

在n-D中，BSP树是一种空间分区数据结构，它使用分裂的n-D超平面（或甚至n-D超曲面）递归地将空间分割成单元。

在2D中，整个空间用2D线递归分割（可能是无限的凸多边形）。在3D中，整个空间用3D平面递归分割（成（可能无限）凸多面体）。

1. 如何建立3D一个BSP树（从模型）

   模型由图元列表（三角形或四边形这是我相信你所说的矩形）的。

   从BSP树中的一个初始根节点开始，它表示一个覆盖整个3D空间并最初包含模型的所有基元的单元。

   1. 为所考虑的基元计算最佳分割平面。

      这一步的目标是找到一个平面，将基元分成两组大小基本相同的基元（空间范围相同或基元数相同）。

      一个简单的分裂策略可以是为分裂选择随机的方向（这将是你的平面的法线）。然后沿着该轴在空间上对所有基元进行排序。遍历基元的排序列表以找到将基元分成两组大小相同的位置（即，这只是沿着该轴找到基元的中间位置）。通过这个方向和这个位置，分割平面被定义。然而

      人们通常使用的分裂策略是：

      • 计算所有考虑的原语的centroid。

      • 计算所有考虑的基元的covariance matrix。

      质心给出了分裂平面的位置。

      协方差矩阵的最大特征值的特征向量给出了分割平面的法线，这是基元最分散的方向（以及当前细胞应该分裂的位置）。

   2. 拆分当前节点，创建两个子节点并为其中的每个节点或当前节点分配原语。

      在1.中找到合适的分割平面后，3D空间现在可以被分成两个半空间：一个是正的，由平面法线指向的，另一个是负的（在分割平面的另一侧）。这一步骤的目标是通过将原语分配到它们所属的半空间来减少所考虑的原语的一半。

      根据分裂平面对当前节点的每个基元进行测试，并根据它是在正半空间还是在负半空间将其分配给左侧子节点或右侧子节点。

      一些基元可能与分割平面相交。它们可以被平面剪切成更小的图元（也可以是三角形），以使这些较小的图元完全位于半空间之一内，并且只属于与子节点对应的一个单元。另一种选择是简单地将重叠的基元附加到当前节点。

      递归地将此分割策略应用于创建的子节点（及其各自的子节点），直至满足某些停止分割的标准（通常在当前节点中没有足够的基元）。

2. 如何在3D

   在所有用例使用BSP树，BSP树的层次结构是用来丢弃模型查询无关一部分。

   1. 定位点

      遍历BSP树查询点。在每个节点上，根据查询点的位置向左或向右移动w.r.t.到节点的分割平面。

   2. 计算射线/模型路口

      要找到你的模型相交的射线的所有三角形（你可能需要这个选择你的地图），做一些类似1东西..与遍历BSP树的查询射线。在每个节点上，计算光线与分裂平面的交点。还要检查存储在节点上的基元（如果有的话）并报告与射线相交的基元。继续遍历其节点与光线相交的节点的子节点。

   3. 丢弃隐形数据

      另一种可能的用途是放弃你的模型摆在你的相机的视锥外段（这可能是你所感兴趣的东西在这里）。视锥体完全由六个平面限定，并具有六个四面体。像1.和2.一样，你可以遍历BSP树，递归地检查哪个单元格与视锥体重叠，并且完全丢弃那些没有的单元格（和你的模型的相应部分）。对于平面/视图平截头体相交测试，您可以检查视锥体的6个四边形中的任何四边形是否与平面相交，或者可以保守地近似具有边界体的视锥体（球/轴对齐边界框/定向边界框）甚至是两者的结合。

话虽这么说，解决您的缓慢呈现的问题可能是在其他地方（你可能无法丢弃大量的数据与3D BSP树模型）：

1. 62K方块并不是那么大：如果您使用的是OpenGL，您应该不会单独绘制这些方块或连续地将几何图形流到GPU。您可以将所有顶点放在一个静态顶点缓冲区中，并通过准备一个包含具有三角形或（更好）三角形基元的正方形的索引列表的静态索引缓冲区来绘制四边形，以便在单个绘图调用中绘制相应的正方形。

2. 您的数据是高度结构化（具有标高的规则网格）。如果您碰巧拥有更大的数据集（甚至不再适合内存），那么您不仅需要空间分区（即利用数据的2.5D结构及其规律性，例如quadtree），还可能LOD技术（用更便宜的表示代替部分数据，而不是简单地丢弃数据）。您应该调查地形渲染的LOD技术。​​列出了一些资源（论文+实施）。简化的分块检测可以作为一个起点。