5·空间数据结构

空间数据结构

• 八叉树
  • 作用：3D空间范围查询（快速找到范围内包含的所有测试对象）
  • 数据结构：八叉树
  • 实现
    • 节点属性：映射的3DAABB包围盒（用左下前，右上后两个点表示），子节点指针（8个），父节点指针，是否是空节点（没有测试对象存储），是否是叶节点（到达最大层级），当前层级，测试对象数组
    • 空间划分（自顶向下）：
      • 依次遍历每个测试对象，将其插入到树中
      • 插入节点：
        • 返回条件：
          • 如果测试对象不在节点内：返回
          • 如果测试对象在节点内，节点是叶节点：插入（数组），返回
          • 如果测试对象在节点内，节点没有子节点，节点是空节点：插入（数组），返回
        • 状态转移：
          • 如果测试对象在节点内，节点没有子节点，节点测试对象数量==1：创建子节点，递归（所有子节点），将原测试对象重新插入
          • 如果测试对象在节点内，节点有子节点：递归（所有子节点）
    • 范围查询（自顶向下）：
      • 指定玩家的包围盒, 维护测试对象数组
      • 返回条件：
        • 如果包围盒和节点不相交：返回
        • 如果包围盒和节点相交内，节点是叶节点：加入（所有对象），返回
        • 如果包围盒和节点相交，节点没有子节点，节点是空节点：返回
        • 如果包围盒和节点相交，节点没有子节点，节点测试对象数量==1: 加入（这个对象）
      • 状态转移：
        • 如果包围盒和节点相交，节点有子节点：递归（所有子节点）
      • 遍历测试对象数组，如果测试对象在包围盒内，就加入到结果数组
    • 玩家更新：每帧都会调用范围查询，支持不同的包围盒位置
    • 动态插入：
      • 对新的测试对象调用插入，以便更新八叉树，范围查询将根据新的八叉树查询
    • 动态删除：
      • 找到要删除测试对象所在的节点，并删除测试对象
      • 查询测试对象数目（自顶向下）：
        • 返回条件：
          • 如果为叶节点：加入
          • 如果节点没有子节点，节点测试对象数量==1: 加入
          • 如果节点没有子节点，节点为空节点：返回
        • 状态转移：如果有子节点：递归（所有子节点）
      • 刷新树（自底向上）：
        • 返回条件：如果当前是根节点：返回
        • 状态转移：查询测试对象数目（当前节点的根节点），如果剩余数目为1：删除（所有子节点），剩余的唯一测试对象放在父节点中，递归（父节点）
    • 动态修改：
      • 删除测试对象 + 插入测试对象
• 四叉树：
  • 数据结构：四叉树
  • 把所有3D变为2D：比如包围盒，树子节点数量……
• 3d-Tree
  • 作用：3D空间最近邻查询（找到和一个点最近的测试对象），k近邻查询（找到和一个点最近的k个测试对象）
  • 适用场景：静态场景
  • 数据结构：二叉树
  • 实现
    • 空间划分（自顶向下）：
      • 返回条件：
        • 如果当前节点的测试对象总数为1个：不用创建子节点
        • 如果当前节点的测试对象总数为2个：仅创建左节点
      • 状态转移：
        • 维度选择：依次按照xyzxyz……维度 / 每次按照哪个维度最大（距离）
        • 排序 + 找到中位数节点：三路快排 + 返回mid节点
        • 递归（所有子节点）
    • 最近邻查询
      • 找到玩家所在的节点（自顶向下）：
        • 返回条件：如果当前为叶节点：返回
        • 状态转移：按照当前层的维度，用玩家此维度值 和mid节点此维度值比较，如果<=：递归左，否则递归右
      • 搜索（自顶向下）：
        • 返回条件：
          • 如果当前节点不存在测试对象：返回
          • 如果当前节点到玩家距离 <= 最小距离，不存在子节点：更新最小距离，更新球体半径，返回
          • 如果节点和球体不相交：返回
          • 如果当前节点到玩家距离 > 最小距离：返回
        • 状态转移：如果节点和球体相交，如果当前节点到玩家距离 <= 最小距离：更新最小距离，更新球体半径，递归
      • 查询（自底向上）：
        • 返回条件：如果当前节点为根节点：返回
        • 状态转移：
          • 玩家所在的节点位置和玩家位置做差作为半径绘制球体
          • 如果对侧节点（左->右，右->左）和球体相交：搜索
          • 如果对侧节点和球体不相交：跳过
          • 如果父节点到玩家距离 <= 最小距离：更新最小距离，更新球体半径，递归（父节点）
          • 如果父节点到玩家距离 > 最小距离：递归（父节点）
    • k近邻查询
      • 单个值 -> 优先队列（大顶堆，大的值优先级高）
      • 比较方式：
        • 如果队列元素不足k个，就通过测试
        • 如果队列元素到达k个，和最近邻思想一致
      • 比较元素：top元素
      • 更新方式：把top弹出，将新的更近节点push
• 2d—Tree
  • 数据结构：二叉树
  • 更改3D为2D：面变为线，球体变为圆形，包围盒……