我有一个项目，它拍摄地形图并使其成为3D对象。当我绘制对象的三维矩形时，它的工作速度非常慢。我读过BSP树，但我并没有真正理解它。有人能解释一下如何在3D中使用BSP吗(也许举个例子)？在我的情况下，当地图上的一些山脉覆盖了其他部分，所以我需要组织矩形才能画好它们时，如何使用它？
在n-D中，BSP树是一种空间划分数据结构，它使用划分n-D超平面(甚至n-D超曲面)将空间递归地划分为单元。
在2D中，整个空间被递归地用2D线分割(分成(可能是无限的)凸多边形)。
在3D中，整个空间被递归地用3D平面分割(分成(可能是无限的)凸多面体)。
-
如何在3D中构建BSP树(从模型)
该模型由一系列基本体(三角形或四边形，我相信你称之为矩形)组成。
从BSP树中的初始根节点开始，该节点表示覆盖整个3D空间的单元，最初包含模型的所有基元。
-
为所考虑的基元计算最优分割平面。
此步骤的目标是找到一个平面，该平面将基元拆分为两组大小大致相同的基元(相同的空间范围或相同数量的基元)。
一个简单的分裂策略可以是随机选择一个方向(这将是你飞机的法线)进行分裂。然后沿着这个轴对所有基本体进行空间排序。并遍历已排序的基元列表，以找到将基元拆分为大小大致相等的两组的位置(即，这只是沿着该轴从基元中找到中间位置)。通过这个方向和这个位置，就定义了分割平面。
然而，一种典型的拆分策略是：
-
计算所有考虑的基元的质心。
-
计算所有考虑的基元的协方差矩阵。
质心给出分裂平面的位置。
协方差矩阵的最大特征值的特征向量给出了分裂平面的法线，这是基元分布最广的方向(以及当前单元应该分裂的方向)。
-
-
拆分当前节点，创建两个子节点，并将基本体指定给每个子节点或当前节点。
在1.中找到了一个合适的分裂平面后，3D空间现在可以分为两个半空间：一个是正的，由平面法线指向，另一个是负的(在分裂平面的另一侧)。此步骤的目标是通过将基元分配给它们所属的半空间，将所考虑的基元减半。
根据拆分平面测试当前节点的每个基本体，并将其指定给左或右子节点，具体取决于它是在正半空间中还是在负半空间中。
一些基元可能与分割平面相交。它们可以被平面剪裁成更小的基元(也可以三角化)，以便这些较小的基元完全位于半空间之一内，并且只属于与子节点相对应的单元之一。另一种选择是简单地将重叠的基元附加到当前节点。
将此拆分策略递归地应用于创建的子节点(及其各自的子节点)，直到满足停止拆分的某些标准(通常在当前节点中没有足够的基元)。
-
-
如何在3D中使用BSP树
在所有用例中，BSP树的层次结构都用于为查询丢弃模型中不相关的部分。
-
定位点
使用查询点遍历BSP树。在每个节点上，根据查询点相对于节点的拆分平面的位置向左或向右移动。
-
计算射线/模型交点
要查找模型中与射线相交的所有三角形(您可能需要它来拾取地图)，请执行类似于1.的操作。使用查询射线遍历BSP树。在每个节点上，计算光线与分割平面的交点。还要检查存储在节点上的基本体(如果有)，并报告与光线相交的基本体。继续遍历其单元与光线相交的该节点的子节点。
-
丢弃不可见数据
另一种可能的用途是丢弃位于相机视锥之外的模型片段(这可能是你在这里感兴趣的)。视图截头体由六个平面精确界定，并具有六个四边形面。就像在1中一样。和2.，您可以遍历BSP树，递归地检查哪个单元与视图截头体重叠，并完全丢弃那些不重叠的单元(以及模型的相应部分)。对于平面/视锥体相交测试，可以检查视锥体的6个四边形中是否有任何一个与平面相交，也可以使用边界体积(球体/轴对齐边界框/定向边界框)保守地近似视锥体，甚至可以两者结合。
-
也就是说，你的慢渲染问题的解决方案可能在其他地方(你可能无法用3D BSP树为你的模型丢弃大量数据)：
-
62K正方形并没有那么大：但是，如果您使用OpenGL，则不应单独绘制这些正方形，也不应将几何图形连续流式传输到GPU。您可以将所有顶点放在一个静态顶点缓冲区中，并通过准备一个静态索引缓冲区来绘制四边形，该缓冲区包含具有三角形或(更好的)三角形条带基元的正方形的索引列表，以在单个绘制调用中绘制相应的正方形。
-
您的数据是高度结构化的(带高程的规则网格)。如果你碰巧有更大的数据集(甚至不再适合内存)，那么你不仅需要空间分区(利用数据的2.5D结构及其规律性，如四叉树)，还可能需要LOD技术(用更便宜的表示代替数据片段，而不是简单地丢弃数据)。然后，您应该研究地形渲染的LOD技术。本页列出了一些资源(论文+实现)。可以使用简化的分块LOD作为起点。