前言：在游戏程序中，利用空间数据结构加速计算往往是非常重要的优化思想，空间数据结构可以应用于场景管理、渲染、物理、游戏逻辑等方面。因此，博主将游戏程序中常用的几个空间数据结构整理出这篇笔记，也会持续更新下去，有错误或有未及之处望指出。
四叉树索引的基本思想是将地理空间递归划分为不同层次的树结构。它将已知范围的空间等分成四个相等的子空间，如此递归下去，直至树的层次达到一定深度或者满足某种要求后停止分割。
//示例：一个四叉树节点的简单结构structQuadtreeNode{Datadata;QuadtreeNode*children[2][2];intdivide;//表示这个区域的划分长度};//示例：找到x,y位置对应的四叉树节点QuadTreeNode*findNode(intx,inty,QuadtreeNode*root){if(!root)return;QuadtreeNode*node=root;for(inti=0;i
而八叉树的结构和四叉树基本类似，其拥有8个节点(三维2元素数组)，其构建方法与查询方法也大同小异，不多描述。
四叉树/八叉树的一个问题是，物体有可能在边界处来回，从而导致物体总是在切换节点，从而不得不更新四叉树/八叉树。
而松散四叉树/八叉树正是解决这种边界问题的一种方式：首先它定义一个节点有入口边界(innerboundary)，出口边界(outerboundary)。那么如何判定一个物体现在在哪个节点呢？
在非松散的四叉树/八叉树中，入口边界和出口边界是一样的。而松散四叉树/八叉树的松散，是指出口边界比入口边界要稍微宽些（各节点的出口边界也会发生部分重叠，松散比较符合这种描述），从而使节点不容易越过出口边界，减少了物体切换节点的次数。
随之而来一个问题就是，如何定义出口边界的长度。因为太短会退化成正常四叉树/八叉树，太长又可能会导致节点存储冗余的物体。而在一篇关于松散四叉树/八叉树的论文里，实验表明出口边界长度为入口边界2倍时可以表现得很好。
相比网格，四叉树/八叉树主要是多了层次，它们可以进行区域较大的划分，然后可以对各种检测算法进行分区域的剪枝/过滤。下面提几个应用（实际应用面很广）：
特别适合大规模的广阔室外场景管理。一般来说如果游戏场景是基于地形的（甚至没有高度）（如城市、平原、2D场景），那么适合用四叉树来管理。而如果游戏场景在高度轴上也有大量物体需要管理（如太空、高山），那么适合用八叉树来管理。
具体例子：
如图所示，假设我们想得到绿色点附近（假设小于最小格的长度）有那些红色目标，那么通过四叉树可以快速索引到绿点所在的K区域节点，只对该子节点包含的所有红色目标逐个进行距离检测，这样就可以避免给区域外的大量其它红色目标进行距离检测。
类似上面感知检测。不同划分区域保证不会碰撞的情况下，就能快速过滤与本物体不同区域的其他潜在物体碰撞。
光线追踪渲染，可使用八叉树来划分3D空间区域，从而过滤掉大量不必要的区域。
层次包围盒树（BVH树）是一棵多叉树，用来存储包围盒形状。它的根节点代表一个最大的包围盒，其多个子节点则代表多个子包围盒。
此外为了统一化层次包围盒树的形状，它只能存储同一种包围盒形状。
计算机的包围盒形状有球体/AABB/OBB/k-DOP，若不清楚这些形状术语可以自行搜索了解。
常用的层次包围盒树有AABB层次包围盒树和球体树。
下图为层次AABB包围盒树。把不同形状粗略用AABB形状围起来看作一个AABB形状（为了统一化形状），然后才建立层次AABB包围盒树。
在物理引擎里，由于物理模拟，大部分形状都是会动态更新的，例如位移/旋转都会改变形状。于是就又有一种支持动态更新的层次包围盒树，称之为动态层次包围盒树。它的算法核心大概：形状的位移/旋转/伸缩更新对应的叶节点，然后一级一级更新上面的节点，使它们的包围体包住子节点。
球体是最容易计算的一类包围盒，而且球体树构造速度可以很快，因此球体树可被用作粗略松散但快速的空间划分结构。
快速构造松散球体树的步骤（以三角形物体为例）：
在步骤2中，还可以按X轴，Y轴，Z轴的顺序轮流划分，即第一次步骤2划分用X轴，第二次步骤2划分用Y轴...
在Bullet、Havok等物理引擎的碰撞粗测阶段，使用一种叫做动态层次AABB包围盒树(DynamicBoundingVolumeHierarchyBasedOnAABBTree)的结构来存储动态的AABB形状。然后通过该包围盒树的性质（不同父包围盒必定不会碰撞），快速过滤大量不可能发生碰撞的形状对。
射线检测从层次包围盒树自顶向下检测是否射线通过包围盒，若不通过则无需检测其子包围盒。这种剪裁可让每次射线检测平均只需检测O(logN)数量的形状。通过一个点位置快速挑选该点的几何体也是类似的原理。
对BVH树进行中序遍历的视锥测试，如果一个节点所代表的包围盒不在视锥范围内，那么其所有子节点所代表的包围盒都不会在视锥范围内，则可以跳过测试其子节点。在这个遍历过程中，通过测试的节点所代表的几何体才可以发送渲染命令。
光线追踪渲染，可使用BVH来进行基于物体的划分，这样光线测试也可以过滤掉大量不必要的碰撞物体，效率一般比基于空间的划分还要好上一些。
在BSP树的构建中，利用球体树辅助，可以将复杂度从O(Nlog2N)下降为O(NlogN)的复杂度。
BSPtree是一棵二叉树，中文译名为二维空间分割树，在游戏工业算是老功臣了，第一次被应用用是在1993年的商业游戏《DOOM》上，可是随时渲染硬件的进步，基于BSP树的渲染慢慢淘汰。但是即使在今天，BSP仍是在其他分支（引擎编辑器）不可或缺的一个重要数据结构。
BSPtree在3D空间下其每个节点表示一个平面，其代表的平面将当前空间划分为前向和背向两个子空间，分别对应左儿子和右儿子。
2D空间下，BSP树每个节点则表示一条边，也可以将2D空间划分成前后两部分。
//BSPtree节点结构示例classBSPTreeNode{ Planeplane; //平面 BSPTreeNode*front;//前向的节点 BSPTreeNode*back;//后向的节点 //Datadata;//数据};BSP树的构建3D空间下要构造一棵较平衡的BSP树，则需要尽可能每次划分出一个节点时，让其左子树节点数和右子树节点数相差不多：
一个麻烦的问题是当2个平面形状是相交时，即出现平面形状既可以在前方也可以在后方的情况。这时候就需要一个将该形状切割成两个子形状，从而可以一个添加在前方，一个添加在后方，避免冲突。
判断点在平面前后算法：平面的法向量为\((A,B,C)\)，则平面方程为：\(Ax+By+Cz+D=0\)将点\((x_0,y_0,z_0)\)代入方程，得\(distance=Ax_0+By_0+Cz_0+D\)若\(distance<0\)，则在平面背后；若\(distance=0\)，则在平面中；若\(distance>0\)，则在平面前方。
大型室内场景游戏引擎基本离不开portal系统：
但是对于关卡编辑师来说，对每个房间/大厅/走廊/门...手动放置每个portal无疑是极大的工作量。于是有一种利用BSP树自动生成portal的做法，大致做法是：
建议结合看图理解，一个示例：
根据定义，在BSP树找到了3个凸多边形房间。
在各个相邻房间之间创建好portal点对（2个绿点，绿线表示portal平面）：
基于portal系统运算得到的视野（进行了2次额外的视野剔除）：
portal系统实际上是非常复杂的，但非常有价值（良好优化的室内FPS游戏基本不会缺少它）。由于其适合离线构造的特性，这种系统往往是编辑器程序员所需要使用，这里仅仅只能点下自动生成portal的皮毛，更具体的细节可看本节参考。
导航网格（NavMesh）是一种表示凸多边形的节点，目前主流游戏的游戏AI寻路中最常用的节点种类。通过用导航网格，A*寻路所要搜索的节点数量大大减少且变得灵活。
因此我们可以预先计算可移动地形和静态障碍，得到一个不规则的大地图形状（可能有凹处也可能有中空处），然后以该形状的所有边来构造一棵BSP树来分割得到若干个凸多边形房间，而这些分割出来的每个凸多边形都是一个导航网格。
几何体编辑是一个常见的编辑器功能，设计者往往需要通过基本图形（立方体、球体、圆柱体、圆锥等）来进行并集、交集或差集，从而得到一个复合的几何体，也就是所谓的CSG几何体。
而BSP树可以很好的处理和表示这些CSG几何体，UE4引擎中的几何体编辑就是采用BSP方式。
首先根据摄像机的位置，遍历BSP树找到并记录其位置相对应的叶节点,称之eyeNode，它将会是顺序遍历渲染的一个重要的中止条件。由于eyeNode往往是在一些平面的前面，另一些平面的后面，所以为了达到正确的从近到远的顺序，需要两次不同方向的遍历。
在至少二十多年前，老旧硬件是没有深度缓存，程序员使用BSP树从远到近渲染（从远处到摄像机位置）三角形图元，避免较远的三角形覆盖到较近的三角形上，从而到达正确的三角形图元渲染顺序，这也就是古老的画家算法。
从远处到eyeNode处的遍历顺序：第一次遍历，左中右顺序，从根节点开始，直到eyeNode停止；第二次遍历，右中左顺序，从根节点开始，直到eyeNode停止。
该BSP树节点代表的数据应该是一个三角形（渲染的基本图元），因为恰好三角形也是个平面形状，因此该BSP树节点代表的平面也就是其数据本身。
而今天对于现代渲染硬件来说，虽然对BSP树近到远渲染（从摄像机位置到远处）物体可以减少overdraw（即对像素的重复覆写）开销，但是并不实用，花费昂贵的CPU代价换来少量GPU优化。
k-d树是一棵二叉树，其每个节点都代表一个k维坐标点：
实际上，k-d树就是一种特殊形式的BSP树（轴对齐的BSP树）。
//一种实现方式示例：二维k-d树节点classKdTreeNode{Vector2position;//位置intdimension;//当前所属层的维度KdTreeNode*children[2];//两个子树//Datadata;//数据};举例，一棵k-d树（k=2）的结构如图：
根据第一层划分维度为X，第二层为Y，第三层为X，所以该k-d树（k=2）对应代表划分的空间，看起来应该是这样的：
一个自定义区域一般是一个凸多边形，然后可通过一些编辑器手动设置好其各顶点位置，最终手工划分出一块凸多边形区域。3D凸多面体一般很少用，即使在要求划分区域属于同一XOZ面不同高度的3D世界里，考虑到性能，可能更适合用凸多边形+高度来划分区域。
此外一提，能不用凹多边形就不用。因为许多程序算法都可以应用在凸多边形上，而相对应用于凹多边形上可能行不通或者得用更低效的算法
为了达到自定义区域之间的无缝衔接，游戏程序还往往采用图（或者树）结构来存储这些自定义区域，表示它们之间的联系。
//自定义区块示例classChunk{Datadata;//区域数据std::vector
目标点p对凸多边形每个顶点之间建立一个向量vec（如：v1-p），该向量与其对应的顶点的边edge（如：v2-v1）进行叉乘，得到一个叉积值。若每个叉积值的符号都一样（都是正数/都是负数），则证明点在凸多边形内。否则，则证明点不再凸多边形内。
举个例子：
因为\(sign((v4-p)×(v5-v4))≠sign((v2-p)×(v3-v2))\)，所以可知目标点不在凸多边形内。
自定义区域是非常灵活的，往往可以应用于任何游戏，特别适合非规则世界的游戏。
典型需要灵活划分不规则区块的游戏莫过于赛车游戏，其赛道往往崎岖蜿蜒，所以其实潜在大量区域不必渲染。但因为赛道布局的不规则，所以这些路段区域往往需要手工设置划分。
当汽车在相应的红线区域时，不必渲染其他红线区域（或使用低耗渲染），因为往往汽车的视野基本都是往前看，狭隘的视野可观察到的地方实际上很有限。
当然除了赛车游戏，还有许多其他游戏都需要用到这种划分，减少不必要的渲染。
如图，先将关卡地图划分成①②③④地图块。然后再自定义划分好ChunkA/B/C/D，并且设置好相应规则用于加载地图块：当玩家在ChunkA时，加载①；在ChunkB时加载①②；在ChunkC时加载②③；在ChunkD时加载③④。
这样可以实现一些基本的地图载入衔接，在相应的Chunk能渲染远处本该看到的地图块。
总的来说，游戏开发最常用的空间数据结构是四叉/八叉树、BVH树，而BSP树基本上只能应用于编辑器上，k-d树则几乎没有可以应用的地方。
简单整理了如下表格：
更新1：移除了网格(Grid)的章节，因为只是简单的多维数组，所以精简一下篇幅，其他内容部分修改。
更新2：更新了松散四/八叉树、球体树和快速构造BSP树方法，其他内容部分修改。
更新3：更新了BSP树部分，简略化了kd树。
更新4：简化了大量不必要或者不重要的内容，对一些概念说法进行了修正。