5·空间数据结构

空间数据结构

• 八叉树
  • 适用条件：适用于3维空间（不一定非要正方体区域，可以为长方体），物体均匀分布可以提高查询效率
  • 思想：将空间划分并用八叉树表示，
    • 空间->树节点, 整个空间->根节点，最小空间->叶节点，
    • 物体存放在叶节点内
    • 对于n叉树的每个节点子节点有n个
  • 作用：范围查询（快速找到范围内包含哪些物体）
  • 算法细节：
    • 玩家类
      • 属性：玩家位置，可视网格体，相机，弹簧臂，包围盒（中心为玩家位置，长宽高范围）
      • 函数：移动（前后左右上下），旋转视角（上下，左右）
    • 测试对象类
      • 属性：网格体，关联节点
      • 函数：设置关联节点，获取关联节点，获取当前位置，设置大小
    • 测试对象生成器类：
      • 属性：生成数量
      • 函数：生成测试对象：通过随机数，在指定范围内随机生成
    • 包围盒类
      • 属性：使用轴对齐包围盒AABB，由左下右上两个点表示，左下（x最小，y最小，z最大），右上（x最大，y最大，z最小）
      • 函数：
        • 获取中心点：min，max在3个维度xyz分别相加/2
        • 获取大小：边长一半的长度，min，max在3个维度xyz分别相减/2

        • 两个包围盒是否相交：在任意一个维度xyz，第一个包围盒的min > 第二个包围盒的max

          第二个包围盒的min > 第一个包围盒的max，即两个包围盒错位，就不相交，否则相交

    • 包围盒工具类
      • 绘制包围盒：ue的DrawDebugBox方式，给出包围盒中心位置和大小
      • 测试对象是否在包围盒内：在3个维度xyz，如果测试对象 >= min && 测试对象 <= max，则在包围盒内
      • 两个包围盒是否相交：……
    • 树节点类
      • 属性：包围盒，层级（在8叉树的层级，制定了最多层数，从0层计数），索引（0——8），父节点，下一个节点，是否是空节点，子节点数组，包含的测试对象数组
      • 方法：
        • 获取：
          • 是否为空节点：子节点数组为空，测试对象数组为空
          • 是否为叶节点：层级为最大层
          • 节点包含的测试对象数目：
            • 返回条件：如果子节点数组==0，则表明是叶节点，如果测试对象数量==0，则返回空，表示没有测试对象，如果测试对象数量==1，则返回这个测试对象
            • 状态转移：遍历子节点数组，如果是空节点就跳过，否则递归调用子节点函数，来更新数量
        • 创建：
          • 创建n个子节点：首先获取包围盒的中心，计算每个子节点的包围盒，new创建节点，添加到子节点数组，
          • 将测试对象插入到树中：
            • 返回条件：
              • 当前是叶节点/空节点，直接插入，并设置测试对象关联节点，
              • 如果和包围盒不相交，就返回
            • 状态转移：
              • 如果子节点数量==0并且测试对象数量==0，直接插入到这个节点
              • 如果测试对象数量==1，没有子节点，创建n个子节点，将新和原测试对象都递归插入到树中
              • 如果子节点数量！=0，将测试对象递归插入到树中
        • 重置：
          • 重置测试对象：获取测试对象关联的节点，如果不为空，尝试移除测试对象，如果移除成功，并刷新树，将测试对象插入到树中
        • 释放：
          • 尝试移除测试对象：如果测试对象仍在包围盒内，不能移除，否则从测试对象数组中移除它，并将测试对象的关联节点置为空
          • 释放子节点数组：遍历每个子节点，先delete释放子节点成员指针，再delete子节点，然后将指针置为nullptr，最后将数组clear
          • 刷新树：
            • 返回条件：如果是根节点不能被释放，直接返回
            • 状态转移：获取节点包含的测试对象数目，如果为0/1则空间需要向上变化，先释放父节点的子节点，如果还有1个，则将测试对象插入到树中，再递归调用父节点的函数，自底向上刷新
    • 树类
      • 属性：根节点，总包围盒，最大层
      • 方法：
        • 插入测试对象：根节点调用重置测试对象的节点
        • 范围查询：
          • 返回条件：
            • 如果包围盒和玩家包围盒不相交返回，
            • 如果节点是空节点返回，
            • 如果节点是叶节点，遍历节点的所有测试对象，添加到数组，并返回
            • 如果是非叶节点测试对象数量为1，添加到数组，并返回
          • 状态转移：否则如果存在子节点递归调用此函数
    • 主Main
      • 开始时：
        • 生成所有测试对象
        • 划分空间：遍历所有测试对象，插入测试对象
      • 每帧：
        • 绘制包围盒
          • 状态转移：绘制当前节点，遍历子节点递归调用此函数
        • 范围查询：调用范围查询函数，找到所有和玩家包围盒相交的叶包围盒，内的所有物体，遍历这些物体，检查是否在玩家包围盒内
  • 总结
    • 划分空间：
      • 创建包裹所有测试对象的包围盒
      • 依次遍历每个测试对象，将其插入到树中，它是从根节点开始自顶向下的插入过程，一个非叶节点，最多保存一个对象，如果超过了一个对象，则要创建8个子节点，插入到子节点中，其中叶节点可以包含多个对象
    • 动态更新：
      • 动态新增测试对象：如上，自顶向下插入
      • 动态删除测试对象：将它从所在的关联节点中移除，找到父节点所有子节点包含的数量，如果为0/1个，这些子节点都要删除，对父节点继续更新，直到非0/1/到根为止，也就是自底向上刷新过程
      • 动态更新测试对象：首先做删除操作，再做插入操作
      • 总之就是调用上面重置函数
    • 范围查询：
      • 自顶向下查询，如果包围盒和玩家包围盒不相交，跳过, 否则对子节点查询，如果查询到叶节点/非叶节点但测试对象为1个/空节点，就返回并添加相应的测试对象
      • 遍历所有查询到的测试对象，检查是否在玩家包围盒内
    • 动态范围查询：每帧如上的范围查询
• 四叉树
  • 相比于八叉树需要改动：
    • 2D包围盒和相交检测
    • 树节点变为4个
• kd树——3维
  • 适用场景：静态场景（不支持动态插入测试对象）
  • 特点：kd树是二叉树，空间划分面在测试对象上，空间是不均匀的
  • 思想：一个节点对应 一个分割线、一个空间，一个分割线上的测试对象、空间内的测试对象
  • 作用：最近邻查询，k近邻查询
  • 算法细节：
    • 节点：左右侧节点，包围盒，划分面（也用左下，右上表示），划分维度，测试对象数组
      • 空间划分：
        • 返回条件：空间内不存在元素则返回
        • 状态转移：找到分割线上的元素并设置属性，根据维度和包围盒计算分割线，根据测试对象的数量，如果为1，则返回，如果为2，仅new构建左节点，否则new构建左右节点，传入子数据（子测试对象，子包围盒，子维度，父节点），递归划分空间
      • 找到分割线上的元素：按当前节点维度，对当前节点内所有测试对象排序（测试对象类应重载运算符），返回中位数节点
      • 最近邻搜索：
        • 找到玩家所在的节点：
          • 返回条件：找到叶节点，返回
          • 状态转移：如果仅有左节点，根据当前维度，将元素维度值和玩家位置维度值比较，决定从左侧递归，还是从右侧递归查找，这是自顶向下查询过程
        • 搜索：
          • 返回条件：节点不存在分割线测试对象返回，如果为根节点返回
          • 状态转移：如果当前节点到玩家的距离 < 当前最近节点到玩家距离，就更新最近节点，以玩家为圆心，以当前最近节点到玩家距离为半径，做圆，如果相对包围盒（左->右，右->左）与玩家圆形范围相交，则从左/右侧深搜，从父节点递归最近邻搜索
        • 深搜：（这是因为另一侧树仍可能包含最近节点）
          • 返回条件：如果和圆形不相交返回，如果是叶节点返回，
          • 状态转移：如果当前节点到玩家的距离 < 当前最近节点到玩家距离，就更新最近节点，对左侧递归深搜，对右侧递归深搜
      • k近邻查询
        • 用优先队列维护k近对象

        • 如果 队列为空

          队列元素数量不足k位

          距离更近（<大顶堆.top(),那么pop(),push()）

  • 总结
    • 划分空间：
      • 返回条件：当所有测试对象都位于划分空间下，则停止
      • 状态转移：每层按照维度顺序（比如1层x，2层y，3层z，4层x……），每次对当前子空间测试对象按照当前维度排序，找到中位数，它作为划分空间
    • 最近邻搜索：
      • 自顶向下找到玩家所在的节点，自底向上查询，维护最近测试对象，如果有更近的测试对象则更新，要注意如果以玩家为圆心，最近对象到玩家距离为半径做圆，和相对树有交点，则说明相对树中可能存在更近测试对象，应通过dfs搜索
• kd树——2维
  • 面变为线