游戏引擎中的空间数据结构与算法：碰撞、导航与可见性

本文采用“结构概览 + 应用分析”的组织方式：前半部分讨论各类数据结构与算法的定义、适用范围、关键实现逻辑、使用方法与示例流程；后半部分讨论它们在碰撞检测、导航寻路和大世界可见性系统中的组合方式。 说明：记忆并不可靠。笔者记忆力有限，因此将许多内容整理为文档，以便反复复习。游戏引擎是复杂的大型软件系统，涉及多个领域；本文内容基于不同阶段遇到的实际问题和个人理解整理。

阅读顺序可按需调整：需要补充基础时从第 1 章开始；需要解决具体问题时参阅第 2~4 章；需要快速回顾时参见第 7.4 节。

核心结论可概括为三点：

• 碰撞检测：首先通过空间索引筛选潜在碰撞对，随后由几何算法计算接触信息；高速物体需额外启用连续碰撞检测（CCD）。
• 导航：将可行走表面烘焙为导航网格，在多边形图上执行 A* 生成走廊，再通过漏斗算法拉直路径，最后由局部避障处理动态障碍。
• 可见性：依次执行距离/空间粗筛、视锥剔除和遮挡剔除；大世界还需叠加分块流送、HLOD 与坐标精度处理。

第 0 章 空间查询的统一框架

游戏引擎中表面差异较大的若干系统，在底层可归约为同一类问题：给定一个空间区域或一条空间路径，快速检索与之相关的对象。

所有这些查询都可以拆成同一个三段式：

空间索引用于降低 \(N_{candidate}\) 的规模，精确测试负责从候选中得到最终结果。索引只解决候选集问题，不保证几何正确性；这是理解后续内容的首要原则。

flowchart LR
    Q["查询：点 / 球 / 盒 / 射线 / 视锥 / 路径"] --> B["空间索引粗筛"]
    B --> C["候选对象集合"]
    C --> F["过滤：层、标签、距离、朝向、状态"]
    F --> E["精确测试：几何 / 遮挡 / 代价"]
    E --> R["结果：命中 / 最近 / 可见集 / 路径"]
    U["对象移动、增删、流送"] -.-> B

空间索引本身也有维护成本，其总成本可表示为：

部分结构查询开销较低但更新开销较高；另一些结构更新开销较低但查询候选较多。结构选型本质上取决于更新模式，而非仅取决于查询复杂度。

0.1 结构/算法速查表

表 0-1 汇总各类结构/算法的定位。第 1 章逐项展开，第 2~4 章讨论其在具体管线中的应用。

此外，R-tree、kd-tree、球树等结构也可用于空间查询。R-tree 更接近面向磁盘或静态 GIS 的 BVH，kd-tree 更适合点定位和离线加速；实时游戏中最常用的仍是网格、BVH、八叉树和 SAP。

第 1 章 数据结构与算法概览

本章为结构/算法介绍模块，不绑定具体引擎模块。每项按统一框架说明：

• 定义：结构或算法解决的问题；
• 特点：适用范围与限制；
• 特殊逻辑：影响正确性的关键实现细节；
• 使用方法：插入、查询与更新方式；
• 示例：具体数值或场景示例；
• 执行流程：执行顺序图示；
• 代价与限制：复杂度之外的工程成本。

1.1 均匀网格与空间哈希

定义：将世界划分为固定大小的网格单元，每个对象按其包围盒覆盖的单元登记；查询时仅访问查询区域覆盖的单元。

特点

• 查询通过坐标计算直接定位网格单元，无需树遍历，常数开销较低。
• 适用于尺寸接近、分布相对均匀且频繁移动的对象，例如子弹、碎片、掉落物、人群和 MMO 的 AOI。
• 对象尺寸差异较大时性能会退化：单个大型对象可能覆盖大量网格单元。
• 世界边界固定时可使用稠密数组；世界范围无限或对象稀疏时应使用哈希表。

struct CellCoord { int x, y, z; };

CellCoord ToCell(const Vec3& p, float cellSize) {
    return {
        (int)std::floor(p.x / cellSize),
        (int)std::floor(p.y / cellSize),
        (int)std::floor(p.z / cellSize)
    };
}

// 简化版：用哈希表存稀疏网格
std::unordered_map<uint64_t, std::vector<Entity>> buckets;

void Insert(Entity e, const AABB& box) {
    CellCoord lo = ToCell(box.min, cellSize);
    CellCoord hi = ToCell(box.max, cellSize);
    for (int z = lo.z; z <= hi.z; ++z)
    for (int y = lo.y; y <= hi.y; ++y)
    for (int x = lo.x; x <= hi.x; ++x)
        buckets[Hash(x, y, z)].push_back(e);
}

特殊逻辑

网格结构有三类典型问题：

1. 单元尺寸决定候选数量。经验上可取典型对象直径的 12 倍。角色高度为 1.8m 时，单元边长可取 24m；过小会导致大型对象覆盖大量单元，过大则会使单元内候选对象过多。
2. 大型对象跨越多个单元。倒伏树木、大型载具或建筑可能覆盖数百个单元。可采用分层网格、将大型对象单独存入“超大对象列表”，或使用 BVH/八叉树处理异构尺寸。
3. 候选重复。两个对象的 AABB 在多个单元中重叠时，同一对象对会被多次发现。查询阶段需通过 pair key 去重，或仅按对象中心所在单元登记，并额外检查边界。

工程实现中还需注意：

• 负坐标必须使用 floor，不能直接进行整数截断，否则 -0.1 与 0.1 会落入同一单元。
• 热路径应避免频繁使用 std::unordered_map；可使用扁平 std::vector 配合开放寻址哈希，或采用覆盖固定世界范围的稠密数组。
• 大世界通常仅对 XZ 平面分格，Y 轴按楼层或层级处理；这样可将单元数量从立方级降至平方级。

使用方法

• 插入：计算 AABB 覆盖的单元范围，将对象 ID 写入对应单元的桶。
• 查询：计算查询形状覆盖的单元范围，收集桶内对象，再以精确形状过滤。
• 更新：对象移动并跨越单元时，从旧单元删除并插入新单元；未跨越单元则不更新索引。
• 删除：按对象记录的单元列表逐个移除，避免全表扫描。

示例

一个 100m × 100m 的平面，单元边长 5m，共 20 × 20 = 400 个单元。场景中存在 1000 发子弹，查询角色周围 15m 范围：

• 查询覆盖约 3 × 3 = 9 个单元；
• 平均每个单元 2.5 发子弹，候选数量约为 22；
• 与遍历 1000 发子弹相比，候选数量约降至 1/45。

若将单元边长改为 1m：

• 单元数量增至 10000；
• 一个 10m 长的飞行器将覆盖约 100 个单元；
• 插入与删除开销显著增加。

执行流程

flowchart LR
    A["对象 AABB"] --> B["计算覆盖的格子范围"]
    B --> C["逐格插入对象 ID"]
    C --> D["查询形状覆盖格子"]
    D --> E["收集候选并去重"]
    E --> F["精确形状测试"]

1.2 四叉树、八叉树与松散八叉树

定义：四叉树为二维形式，八叉树为三维形式；当节点内对象数量超过阈值时分裂为四个或八个子节点，对象数量减少后再合并。

特点

该结构适用于静态或半静态场景，例如地形、建筑、植被、关卡几何和可见性层次。查询从根节点开始，若节点区域与查询区域不相交，则对整棵子树剪枝。

特殊逻辑

• 分裂阈值：节点内对象数超过 N 时分裂，低于 M 时合并。N 过小会导致树深增加，N 过大则退化为线性列表。
• 最大深度：必须设置上限，否则对象重合时可能无限分裂。

对象跨越节点边界是该结构的主要问题，常见处理方式有三种：

• 对象仅挂载到包含其中心的节点，查询时同时测试相邻节点；
• 将对象复制到所有相交的叶子节点，查询时去重；
• 使用松散八叉树（loose octree）：每个节点的实际包围盒按 looseness 系数（常见 1.5~2.0）扩张，对象按中心分配；只要对象未越出松弛边界，就无需重新插入。

松散八叉树的作用是为动态对象预留移动余量，避免对象在节点边界附近频繁删除与插入。该结构适用于大世界静态场景与少量动态物体并存的场合。

示例

一个 1024m × 1024m 的场景，四叉树最大深度为 5：

• 第 0 层为 1024m，第 1 层为 512m，……第 5 层为 32m；
• 叶子单元尺寸为 32m × 32m；
• 场景中分布 200 棵静态树，查询角色周围 100m 范围时，仅需访问覆盖该圆形的若干叶子节点，无需遍历全部 200 棵。

执行流程

flowchart TD
    R["根节点 1024m"] --> A["西北 512m"]
    R --> B["东北 512m"]
    R --> C["西南 512m"]
    R --> D["东南 512m"]
    A --> A1["继续分裂到 32m 叶子"]
    B --> B1["对象少，保持粗粒度"]
    C --> C1["继续分裂到 32m 叶子"]
    D --> D1["对象少，保持粗粒度"]

代价与限制

• 对象跨越边界会导致重复或漏查；松散八叉树可缓解该问题，但无法完全消除。
• 每帧重建整棵树通常不可接受；静态部分应只构建一次，动态对象使用独立层级。
• 指针式树结构的缓存局部性较差；热路径可将其扁平化为数组。
• 分裂/合并阈值若仅凭经验设定，可能导致树过深或过浅。

1.3 BVH：现代引擎最通用的空间索引

定义：BVH（Bounding Volume Hierarchy）是一种二叉树结构，叶节点存放一个或少数几个对象，内部节点的 AABB 为子节点 AABB 的并集。

struct BVHNode {
    AABB bounds;
    int left;      // 内部节点：左孩子索引
    int right;     // 内部节点：右孩子索引
    int object;    // 叶子：对象索引
    bool isLeaf;
};

构建过程的核心是节点划分策略，最常用的方法是 SAH（Surface Area Heuristic）：

其含义是：若左子节点的包围盒面积较大，则射线或视锥进入该区域的概率更高，应承担更高的期望遍历成本。SAH 枚举候选切分并选择期望成本最小的方案；工程上通常采用“分桶 SAH”，将候选切分数量从 \(O(n)\) 降至常数级。

特点

主要优点：

• 对尺寸差异较大的对象具有较好的稳定性；
• 射线、视锥与范围查询可复用同一棵树；
• 动态 BVH 支持插入、删除和旋转平衡，Box2D 的 b2DynamicTree 为典型实现；
• 可扁平化为数组，具备良好的缓存局部性。

主要代价：

• 构建与重构开销较高；
• 动态更新会降低树质量，需要定期重构；
• 遍历存在分支预测与指针跳转开销，极端情况下性能不如网格。

特殊逻辑

常用的工程优化是 fat AABB：将叶节点包围盒按固定 margin 扩张。对象在小范围内移动时仅更新叶子 bounds，不改变树结构；只有越出 fat bounds 时才删除并重新插入。

使用方法

• 构建：递归选择切分轴和切分点，生成孩子，叶子里存对象。
• 查询：维护一个栈；节点不相交就跳过；叶子做精确测试；需要最近命中时按距离优先遍历近孩子。
• 更新：删除旧叶子、插入新叶子、refit 祖先；必要时旋转或重建子树。

示例

四个对象 A、B、C、D：

• 首先将 A+B 合并为一个节点，将 C+D 合并为一个节点；
• 然后将这两个节点合并为根节点；
• 射线从左上射入，先测试根节点，再测试较近的子节点；若 A+B 节点不相交，则跳过整棵子树，仅测试 C、D。

执行流程

flowchart TD
    R["根 AABB：A+B+C+D"] --> L["左节点：A+B"]
    R --> R2["右节点：C+D"]
    L --> A["叶子 A"]
    L --> B["叶子 B"]
    R2 --> C["叶子 C"]
    R2 --> D["叶子 D"]

代价与限制

• 每帧重建 BVH 开销较高；动态对象应使用动态树或分层索引。
• 仅执行 refit 而不重建会导致包围盒逐渐膨胀，查询性能下降。
• 射线遍历若不对子节点排序，会优先测试较远节点，产生额外开销。
• 大型对象会增大祖先节点 AABB，降低剪枝效率；可将其放入单独列表或使用分层结构。

1.4 Sweep and Prune：时间相干性与增量排序

定义：SAP 沿单一坐标轴对所有对象的 AABB 端点排序；扫描过程中维护活动列表，仅对活动列表中的对象检测另外两个轴。

特点

其性能优势主要来自时间相干性，而非渐进复杂度：物理对象相邻两帧的位置变化通常较小，端点数组接近有序，使用插入排序可使更新开销接近 \(O(n)\)。

适用场景：ragdoll、大量尺寸相近的动态刚体、连续运动的角色。
不适用场景：大型静态物体与大量小物体混合，或对象尺寸差异极端。

特殊逻辑

1. 端点排序：每个 AABB 在所选轴上具有两个端点；左端点进入活动列表，右端点离开。
2. 活动列表：扫描至左端点时，将当前对象与活动列表中的每个对象检测另外两个轴；扫描至右端点时将其移除。
3. 增量排序：帧间仅执行插入排序，避免每帧调用完整的 std::sort。
4. 轴选择：选择方差最大的轴，或每帧动态选择轴；单轴分布退化时效果会下降。
5. 大型对象：横跨整个场景的对象会长期保留在活动列表中，导致候选数量急剧增加。

使用方法

• 初始化：按 x 端点排序，建立活动列表。
• 每帧：更新移动对象的端点，插入排序；扫描并生成重叠对。
• 过滤：层、通道、睡眠状态在生成 pair 后立即过滤。

示例

三个盒子在 x 轴：

• A: [0, 2]
• B: [1, 4]
• C: [3, 5]

端点排序：A左0、B左1、A右2、C左3、B右4、C右5。

扫描：

• 0 进入 A，活动列表 {A}；
• 1 进入 B，和 A 测 y/z，得到 A-B；
• 2 A 离开；
• 3 进入 C，和 B 测 y/z，得到 B-C；
• 4 B 离开；
• 5 C 离开。

A-C 在 x 上不重叠，不需要测。

执行流程

flowchart LR
    E0["0: A 左"] --> E1["1: B 左"]
    E1 --> E2["2: A 右"]
    E2 --> E3["3: C 左"]
    E3 --> E4["4: B 右"]
    E4 --> E5["5: C 右"]
    E1 -. "活动列表 {A,B} → 测 A-B" .-> P1["候选对 A-B"]
    E3 -. "活动列表 {B,C} → 测 B-C" .-> P2["候选对 B-C"]

代价与限制

• 对象尺寸差异较大时，活动列表会显著增长。
• 端点相等及浮点误差需要一致的排序规则。
• 单轴排序仅完成第一维筛选，另外两个轴仍需检测；排序完成并不代表检测结束。
• 大世界坐标下端点数值较大，需要注意浮点精度与比较方式。

1.5 其他结构：BSP、Portal、PVS、R-tree

定义：将室内空间划分为房间或凸单元，通过 portal 连接，并预计算每个单元可见的单元集合；运行时仅查询预计算结果。

特点

• 运行时开销很低，适用于室内、走廊、洞穴和固定关卡。
• 预处理开销较高，对动态门、可破坏墙体和移动房间支持较差。
• PVS 采用保守策略：允许过度绘制，但不可漏绘。
• 与视锥剔除为互补关系，不能相互替代。

特殊逻辑

1. 空间单元：BSP 用平面递归切分，或手工划分房间；每个单元通常是凸的。
2. Portal：两个单元之间的连接面（门、窗、走廊口）。可见性通过 portal 传播。
3. PVS 位掩码：每个单元存一个 bitset，记录它能看到的单元集合；运行时取当前相机所在单元的 PVS，再和视锥求交。
4. Anti-portal：用于阻断不应传播的可见性，减少过度保守。
5. 动态物体：PVS 仅处理静态空间；动态物体通常单独执行视锥或遮挡测试。

使用方法

• 离线：切分空间、标记 portal、从每个单元做可见性传播、烘焙 PVS。
• 运行时：相机所在单元 → 取 PVS → 和视锥求交 → 只提交可见单元里的静态物体。
• 动态门：门打开/关闭时切换 portal 状态，或退化为运行时遮挡。

示例

三个房间 A、B、C：

• A 与 B 之间设有门 P1；
• B 与 C 之间设有门 P2；
• A 无法看到 C，因为视线需要经过两次转折。

PVS：

• PVS[A] = {A, B}
• PVS[B] = {A, B, C}
• PVS[C] = {B, C}

相机位于 A 时，仅提交 A、B；C 虽可能位于视锥内，但被墙体遮挡。

执行流程

flowchart LR
    A["房间 A"] ---|"P1 门"| B["房间 B"]
    B ---|"P2 门"| C["房间 C"]
    A -. "PVS[A] = A,B" .-> B
    C -. "PVS[C] = B,C" .-> B

代价与限制

• PVS 内存占用可能较高，最坏情况下与单元数量呈平方关系。
• 动态门/破坏墙需要重新计算或运行时补遮挡。
• 过度保守会导致过度绘制，过度激进则会造成漏绘；漏绘属于可见错误。
• 大世界开放场景不适合纯 PVS，通常改用 HZB 或软件遮挡。

R-tree 更接近面向磁盘或静态 GIS 的 BVH，kd-tree 更适合点定位和离线加速；它们并非实时游戏的主要索引结构，但其设计思想具有参考价值。

1.6 导航网格 / 多边形图

定义：将可行走表面烘焙为一组带邻接关系的凸多边形，角色在多边形图上执行寻路，而非直接在三角形网格上搜索。

特点

• 贴合可行走表面，路径自然，查询精度较高。
• 烘焙开销较高，动态修改较复杂。
• 多边形为凸，内部任意两点的连线不会穿越墙体，便于路径生成。
• 运行时数据通常按 tile 划分，支持流送和局部重建。

特殊逻辑

1. 凸多边形：每个多边形内部可走，边是边界或邻接。
2. 邻接关系：每条边记录相邻多边形；A* 的“邻居”即这些邻接多边形。
3. Off-Mesh Link：跳跃、攀爬、传送、门，单独建链接，带代价和方向。
4. Detail Mesh：多边形用于路径生成，细节网格用于高度查询；角色贴地时通过 detail mesh 获取高度。
5. Tile：大世界按块构建，tile 边界必须正确衔接；仅重建受影响的 tile。

使用方法

• 烘焙：Recast 将三角形场景体素化、分区，并生成 PolyMesh/DetailMesh。
• 查询：最近多边形、随机点、射线、路径。
• 更新：动态障碍切割局部 tile，或运行时用 Off-Mesh Link/避障绕开。

示例

三个多边形 A、B、C：

• A 和 B 共享 portal P1；
• B 和 C 共享 portal P2；
• 从 A 到 C，A* 在图上得到 A → B → C；
• 漏斗算法随后根据 P1、P2 的左右边界，将路径转换为折线。

执行流程

flowchart LR
    A["多边形 A"] ---|"P1"| B["多边形 B"]
    B ---|"P2"| C["多边形 C"]
    A -. "A* 邻居" .-> B
    B -. "A* 邻居" .-> C

代价与限制

• 导航网格与碰撞几何不一致时，会出现“导航网格显示可通行，但实际碰撞体无法通过”的问题。
• agent 半径或高度烘焙不正确，会导致贴墙或过门失败。
• 跨 tile 接缝丢失邻接关系，角色会在边界处受阻。
• 动态障碍变化时每帧重建整张导航网格，会导致性能显著下降。

1.7 A* / Dijkstra：图上的最短路径搜索

定义：A* 以“已付出代价与到终点估计代价之和”对待探索节点排序；Dijkstra 是启发式函数恒为 0 的 A*。

特点

• 图可为网格、导航多边形、路点或分层 cluster。
• A* 的搜索效率通常高于 Dijkstra，因为启发式函数将搜索导向终点。
• 启发式函数不得高估真实代价（admissible），否则无法保证最优性。
• 内存管理与开放列表实现往往比算法本身对性能影响更大。

特殊逻辑

• \(g(n)\)：从起点到 \(n\) 的真实代价；
• \(h(n)\)：从 \(n\) 到终点的估计；
• 每次从开放列表取 \(f\) 最小的节点；
• 如果发现更小的 \(g\)，更新父节点并将节点重新放回开放列表（reopen）；
• 网格常用欧氏距离或八方向 octile 距离；导航网格常用欧氏距离。

使用方法

• 节点：多边形/格子/路点。
• 边：邻接关系 + 代价（距离、坡度、区域类型、风险）。
• 开放列表：二叉堆。
• 关闭列表：visited stamp 或布尔数组，避免每帧分配哈希表。
• 结束：到达目标，或开放列表空（不可达）。

示例

3×3 网格（只允许上下左右移动），S 在左上，G 在右下，中间有障碍：

S . .
. # .
. . G

从 S 出发，A* 会优先探索 \(f\) 小的格子；绕过中间的 #，最终得到一条 4 步路径。Dijkstra 同样可找到该路径，但会向四周均匀扩展，探索更多节点。

执行流程

flowchart TD
    A["起点加入开放列表"] --> B["取 f 最小的节点"]
    B --> C{"是终点？"}
    C -->|是| D["回溯父节点，输出路径"]
    C -->|否| E["遍历邻居，计算 g"]
    E --> F{"g 更小？"}
    F -->|是| G["更新父节点，加入开放列表"]
    F -->|否| H["跳过"]
    G --> B
    H --> B

代价与限制

• 启发式不可采纳，路径不是最优。
• 不 reopen，遇到更优路径也不更新。
• 每次查询都分配大量节点或哈希表，导致 GC 或分配器压力较大。
• 仅按距离计算代价，忽略坡度、门、跳跃和危险区域。
• 目标不可达时直接失败，缺少“最接近可行点”的降级策略。

1.8 漏斗算法：多边形走廊收紧

定义：A* 生成由若干多边形构成的走廊；漏斗算法沿 portal 的左右边界逐步收紧，输出一条尽可能短的折线路径。

特点

• 仅处理几何收紧，不重新执行寻路。
• 计算开销较低，通常作为路径后处理的最后一步。
• 依赖正确的 portal 顺序与左右边界定义。
• 相比“取多边形中心再平滑”的方法更可靠，因为它严格尊重可行走区域边界。

特殊逻辑

1. Portal：相邻多边形的共享边，有左端点和右端点。
2. 漏斗：从起点开始，左边界和右边界张开。
3. 收紧：每经过一个 portal，检查新左右边界是否穿过旧边界。
4. 输出角点：如果新边界穿过旧边界，前一个角点必须保留，输出它并重置漏斗。
5. SSF：Mikko Mononen 的 Simple Stupid Funnel Algorithm 是最常见实现。

使用方法

• 从 A* 路径生成 portal 列表；
• 初始化左右边界；
• 依次处理 portal，收紧边界；
• 输出起点、角点、终点；
• 可再做一次碰撞/高度修正。

示例

路径经过两个 portal：

• P1 左 L1、右 R1；
• P2 左 L2、右 R2；
• 漏斗从起点张开，经过 P1 后左边界被 L1 限制；
• 经过 P2 时，如果 R2 穿过右边界，说明 P1 的右端点是一个必须保留的角点；
• 输出“起点 → P1 角点 → 终点”的折线。

执行流程

flowchart LR
    S["起点"] --> P1["Portal P1：L1 / R1"]
    P1 --> P2["Portal P2：L2 / R2"]
    P2 --> G["终点"]
    P1 -. "收紧左边界" .-> F["漏斗"]
    P2 -. "穿过旧边界则输出角点" .-> F
    F --> O["输出折线路径"]

代价与限制

• portal 顺序错误会导致路径穿墙。
• 左右端点定义颠倒会使漏斗向错误方向收紧。
• 共线或退化 portal 需要特殊处理。
• 仅拉直路径而不检测碰撞时，动态障碍可能位于路径折线上。

1.9 遮挡剔除方案：HZB、软件遮挡与硬件查询

定义：视锥剔除仅判断物体是否位于画面范围内；遮挡剔除进一步判断位于画面内的物体是否被其他几何体遮挡。

特点

• PVS/Portal 属于预计算方案；HZB 与软件遮挡属于运行时方案。
• 遮挡剔除必须保持保守性，不得剔除实际可见的物体。
• 应先处理大型遮挡物，再测试小型物体；若使用尚未写入深度缓冲的遮挡物执行测试，结果不可靠。
• 通常与 LOD、HLOD 和 GPU culling 配合使用。

特殊逻辑

1. HZB（Hierarchical Z-Buffer）：将深度缓冲构建为 mip 金字塔，每个上层像素存储下层区域的最大深度；测试时将物体 AABB 投影到屏幕，选择合适的 mip 层级，并比较物体最近深度与遮挡深度。
2. 软件遮挡：由 CPU 将大型遮挡物以低分辨率光栅化到深度缓冲，再测试对象 AABB；开销可控，但结果偏保守。
3. 硬件遮挡查询：由 GPU 查询对象是否被遮挡；结果准确，但存在延迟，易造成 GPU 停顿。
4. 延迟一帧：许多方案使用上一帧的深度结果执行本帧剔除，允许少量误差以避免同步等待。

使用方法

• 先执行距离与视锥剔除，减少候选对象；
• 优先提交大型遮挡物，建立深度缓冲；
• 对剩余对象执行 HZB 或软件遮挡测试；
• 通过测试的对象提交渲染；未通过测试的对象在下一帧重新测试或降级处理。

示例

1024×1024 的深度缓冲：

• mip0 1024²，mip1 512²，mip2 256²，mip3 128²；
• 一个物体的屏幕包围盒约 100×40 像素；
• 选 128² 或 256² 的 mip 做一次保守比较；
• 如果物体最近深度大于该区域最大遮挡深度，说明被挡住，剔除。

执行流程

flowchart TD
    D0["深度缓冲 1024²"] --> D1["Mip1 512²：取 2×2 最大深度"]
    D1 --> D2["Mip2 256²"]
    D2 --> D3["Mip3 128²"]
    D3 --> T["物体 AABB 投影 → 选 mip → 比较深度"]
    T --> V{"被挡住？"}
    V -->|是| C["剔除"]
    V -->|否| R["提交渲染"]

代价与限制

• 保守性不足会导致漏绘，使可见物体突然消失。
• 同步回读 GPU 查询结果会造成 GPU 停顿。
• 未按遮挡物优先级排序，在大型遮挡物写入深度前执行测试，结果不可靠。
• 透明物体、特效和粒子通常不参与遮挡深度写入。

1.10 ORCA / RVO：局部避障

定义：每个 agent 在速度空间中为邻居构造速度障碍，并选择最接近期望速度且不会导致碰撞的新速度。

特点

• 用于解决全局路径正确、但运动过程中发生碰撞的问题。
• 计算范围是局部的，不需要重新执行寻路。
• 适用于人群、队伍和大量 NPC。
• 不保证全局最优，也不处理复杂地形；需与导航路径配合使用。

特殊逻辑

1. 速度障碍：如果两个 agent 保持当前相对速度，未来会碰撞，这个相对速度就落在速度障碍里。
2. 半平面：ORCA 将速度障碍近似为半平面约束；每个邻居对应一个约束。
3. 线性规划：在所有半平面约束下，找离期望速度最近的速度。
4. 互惠：两个 agent 各自承担部分避让责任，避免单个 agent 承担全部避让。
5. 时间视野：仅考虑未来一段时间；窗口过短会导致抖动，过长会过度保守。

使用方法

• 每个 agent 有期望速度（来自路径）；
• 收集邻居（空间哈希/BVH）；
• 为每个邻居构造 ORCA 半平面；
• 解线性规划得到新速度；
• 用新速度移动，下一帧重复。

示例

两个 agent 相向而行：

• A 的期望速度向右，B 的期望速度向左；
• 若不执行避让，相对速度将指向碰撞方向；
• ORCA 使 A 略微向右下、B 略微向左下调整；
• 两者以较小横向偏移相互通过，路径仅产生小幅偏移。

执行流程

flowchart LR
    A["期望速度"] --> B["收集邻居"]
    B --> C["构造速度障碍 / 半平面"]
    C --> D["线性规划求新速度"]
    D --> E["移动并更新位置"]
    E --> B

代价与限制

• 邻居数量过多时，线性规划开销较高；应先用空间索引筛选邻居。
• 约束过强会导致抖动，过弱会导致 agent 拥挤。
• 仅处理 agent 之间的避让，不处理静态障碍。
• 与导航路径不一致时，agent 可能被推离可行走面。

第 2 章 碰撞检测：broad phase 与空间索引

第 1 章中的网格、BVH 与 SAP 主要服务于 broad phase；本章讨论它们如何与 narrow phase、CCD 衔接。

碰撞检测的完整链路是：

flowchart LR
    A["物理步 / 角色移动"] --> B["Broad phase：空间索引"]
    B --> C["候选对象对"]
    C --> D["过滤：层、通道、睡眠、触发器"]
    D --> E["Narrow phase：精确几何"]
    E --> F["接触流形 / 穿透深度"]
    F --> G["约束求解 / 位置修正"]
    E -. "高速物体" .-> H["CCD / TOI：高速物体补测"]
    H -. "TOI 接触" .-> G

2.1 Broad phase：候选集筛选

Broad phase 的任务并非计算接触点，而是尽快排除不可能相交的对象对。该阶段允许少量误报，但不可漏报。

常见选型：

• 空间哈希/网格：适用于大量子弹、碎片、掉落物、角色和触发器；对象尺寸接近时综合开销最低。
• BVH/动态树：角色、道具、载具、可破坏物混合；尺寸差异大；还要支持射线和视锥查询。
• SAP：大量尺寸相近的刚体、布娃娃、物理道具。
• 八叉树/松散八叉树：静态场景 + 少量动态对象；大世界分块。

一个典型的 broad phase 循环：

// 伪代码：先收集候选对，再去重
for (Entity a : movingEntities) {
    AABB queryBox = Expand(a.bounds, margin);
    for (Entity b : index.Query(queryBox)) {
        if (a.id >= b.id) continue;          // 每对只处理一次
        if (!LayersCanCollide(a, b)) continue;
        if (!Overlap(a.fatBounds, b.fatBounds)) continue;
        pairs.push_back({a, b});
    }
}

关键工程点：

• 膨胀 AABB（fat AABB）：扩大包围盒，减少对象微动导致的树更新；越出膨胀边界后再重新插入。
• Pair cache：保留上一帧的接触对，减少重复计算；用 generation/handle 防止悬空引用。
• 更新传播：对象移动后，更新叶子 bounds，再向上 refit 祖先；如果树结构失衡到阈值，重建子树。
• 睡眠/岛：静止对象不参与 broad phase 更新；一整片静止刚体作为一个 island 休眠。
• 过滤器：层、碰撞通道、触发器与查询标志应在 broad phase 之后、narrow phase 之前尽可能剔除，避免精确测试处理无效候选。

2.2 Narrow phase：几何算法与空间索引的分工

Broad phase 生成候选对之后，narrow phase 才判断“是否接触、接触位置以及穿透深度”。

常见组合：

需要特别注意的几点：

• 碰撞结果并非简单的布尔值，而是接触流形：包含位置、法线、穿透深度和多个接触点。接触点不足会导致刚体抖动。
• 持续接触需启用 warm starting：沿用上一帧的冲量，否则堆叠稳定性会下降。
• 网格碰撞需处理单面三角形、内部边和退化三角形；角色贴墙移动时的“幽灵碰撞”通常来自内部边。
• Broad phase 的误报可以接受，漏报会造成严重错误，因此索引的保守性比精确性更重要。

2.3 CCD：高速物体的穿透问题

离散碰撞只在离散时间点检测。如果子弹一帧移动 5 米，墙厚 10 厘米，它可能直接从墙的一侧跳到另一侧，中间没有采样点，即 tunneling。

解决方法：

1. Swept AABB / 扫掠形状：将运动轨迹构造为扫掠体，先与静态几何求交。
2. Conservative Advancement：使用当前距离和相对速度推进时间，直到距离小于阈值或到达 TOI。
3. Speculative Contacts：在 broad phase 阶段将“下一帧可能接触”的接触点纳入，使求解器提前处理。
4. Substepping：将一帧划分为多个小步；实现简单但开销较高。

Conservative Advancement 的基本推导：

其中 \(d(t)\) 是当前最近距离。只要距离还大于 0，就以“不会穿透”的速度前进；重复直到接触或超过时间上限。

角色控制器通常不启用完整刚体 CCD，而采用胶囊体 sweep + 滑动 + 台阶检测 + 地面吸附：

• 先沿移动方向对胶囊体执行 sweep；
• 与墙面接触时，将速度投影到墙面并继续滑动；
• 遇到台阶时尝试抬升；
• 最后向下吸附地面，避免下坡时悬空。

2.4 碰撞系统的常见问题

第 3 章 导航寻路：从可行走面到可执行路径

第 1 章已分别讨论导航网格、A*、漏斗算法与 ORCA；本章讨论它们在引擎中如何组合为可执行路径。

导航系统可划分为四个层次：

1. 表示：世界中哪些区域可以行走（导航网格、格子、路点）。
2. 查询：查询点位于哪个多边形，以及最近的可走点位置。
3. 寻路：从起点到终点经过哪些多边形（A*、Dijkstra、分层寻路）。
4. 执行：如何生成自然的移动路径（漏斗拉直、局部避障、人群）。

3.1 四种常见表示

3.2 Recast：导航网格的构建流程

UE 与 Unity 的导航底层均主要基于 Recast/Detour。Recast 负责离线构建，Detour 负责运行时查询。

flowchart LR
    A["三角形场景"] --> B["体素化 / 光栅化"]
    B --> C["高度场 Heightfield"]
    C --> D["紧凑高度场 CompactHeightfield"]
    D --> E["可行走区域标记"]
    E --> F["分水岭分区 Watershed"]
    F --> G["轮廓 Contours"]
    G --> H["多边形网格 PolyMesh"]
    H --> I["细节网格 DetailMesh"]
    I --> J["Detour NavMesh 运行时数据"]

各阶段说明：

• 体素化：将三角形光栅化到规则体素网格，标记实心区域、可行走区域、坡度与高度。
• 高度场：每个 XZ 单元记录若干层 span；多层结构可用于表达桥、楼梯和洞穴。
• 紧凑高度场：移除多余 span，仅保留可行走表面与邻居关系。
• 分水岭分区：根据到障碍物的距离场将可行走区域划分为若干区域，再合并过小区域；该步骤决定导航多边形的形状。
• 轮廓：沿区域边界提取轮廓并简化折线。
• PolyMesh：将轮廓转换为凸多边形，并建立多边形邻接关系。
• DetailMesh：记录每个多边形内部的高度细节，使角色能够贴合斜坡和台阶。
• Detour：将多边形、邻接关系、Off-Mesh Link 与区域代价组织为运行时查询结构。

3.3 运行时数据结构

导航网格的核心并非三角形，而是带邻接关系的多边形图：

• 每个多边形：顶点、中心、法线、区域 ID、代价标志；
• 每条边：相邻多边形索引，或者“墙/边界”；
• Off-Mesh Link：跳跃、攀爬、传送、门；
• 查询结构：按 tile 分块，按 AABB 建 BVH/网格，支持最近多边形查询。

常见查询：

• FindNearestPoly：将任意点吸附到最近的可走多边形；
• FindPath：在多边形图上执行 A*；
• Raycast：沿导航面投射射线，判断两点间是否可直达；
• FindRandomPoint：在可行走面上随机取点；
• GetPolyHeight：获取多边形内部的高度。

UE 中对应 RecastNavMesh、FNavLocation、UNavigationSystemV1 这一层；Unity 中对应 NavMeshSurface、NavMeshAgent、NavMeshLink。名称不同，但底层概念一致。

3.4 A* 在导航系统中的应用

第 1 章已讨论 A* 的基本机制；本节说明其在导航图中的具体应用方式。

A* 的核心公式：

• \(g(n)\)：从起点到 \(n\) 的真实代价；
• \(h(n)\)：从 \(n\) 到终点的启发式估计；
• 只要 \(h\) 不高估真实代价（admissible），A* 就能找到最优路径。

伪代码：

std::priority_queue<Node, std::vector<Node>, CompareByF> open;
open.push(start);
g[start] = 0;

while (!open.empty()) {
    Node cur = open.top(); open.pop();
    if (cur == goal) return Reconstruct(cur);

    for (Edge e : graph.Neighbors(cur)) {
        float ng = g[cur] + e.cost;
        if (ng < g[e.to]) {
            g[e.to] = ng;
            parent[e.to] = cur;
            open.push({e.to, ng + Heuristic(e.to, goal)});
        }
    }
}

工程实现中，以下因素通常比算法本身更影响性能：

• 启发式函数：网格常用欧氏距离或八方向 octile 距离，导航网格常用欧氏距离。权重略大于 1 的 weighted A* 可换取更高搜索速度，但不再保证最优性。
• 数据结构：二叉堆通常足够；节点池与 visited stamp 可避免每帧分配；应避免在每个节点上使用哈希表查询 g。
• 代价模型：不应仅按距离计算代价。草地、沼泽、楼梯、门和跳跃链接都应设置区域代价；A* 的边权应表示“时间/风险”，而非单纯距离。
• 部分路径：目标不可达时返回“最接近目标的可行点”，优于直接失败。
• 分层寻路：大世界先用 HPA*/分层图寻找跨区块走廊，再在局部 tile 上细化。

3.5 漏斗算法：走廊收紧与折线生成

第 1 章已讨论漏斗算法的几何过程；本节说明其在导航管线中的位置。

A* 在多边形图上得到的是依次经过的多边形序列，路径会贴近多边形中心或边界，呈现折线形态。漏斗算法（Funnel Algorithm）将这条走廊收紧为一条尽可能短的折线。

做法：

• 将路径视为一系列 portal（相邻多边形共享的边）；
• 维护一个漏斗，左边界和右边界从起点张开；
• 每经过一个 portal，检查左右边界是否仍然有效；
• 如果新边界穿过旧边界，说明前一个角点必须保留，输出它并重置漏斗；
• 最后输出终点。

Mikko Mononen 的 Simple Stupid Funnel Algorithm（SSF） 是最常见的实现。相比“先取多边形中心再平滑”的方法，它直接处理可行走区域边界，因此更可靠。

3.6 动态障碍、人群与流场

导航数据并非一次烘焙即可长期有效。动态障碍和大量 agent 会引入新的问题：

• 局部避障：ORCA/RVO 根据邻居的速度和半径计算避让速度；它不改变全局路径，仅负责避免与邻近 agent 碰撞。
• 导航网格切割/雕刻：动态障碍将多边形标记为不可走，或在运行时挖洞；需要重建局部 tile。
• Tile Cache：Detour 的 dtTileCache 使用可重建 tile 处理动态障碍，避免重新构建整张导航网格。
• 导航 Invoker：大世界仅在高优先级区域（如玩家附近）动态生成导航，远处不生成。
• 流场（Flow Field）：对大规模单位，先用 Dijkstra 在格子上计算“每个格子指向下一步”的向量场，由所有单位共享；适用于 RTS、塔防和大规模单位寻路。其缺点是动态障碍需要重新计算，且路径质量受格子分辨率限制。
• 分层 A*：将地图划分为 cluster，先计算 cluster 级路径，再计算局部路径；适用于超大世界。

3.7 大世界导航的工程点

• 分块（tile）：每块导航网格独立构建、独立流送；只重建脏 tile。
• Tile 边界：相邻 tile 的边必须正确衔接；否则 agent 会在接缝处受阻。
• 多层：桥、楼梯和洞穴通过多层 navmesh 或 Off-Mesh Link 表达。
• 异步：烘焙与查询不应阻塞主线程；查询可使用快照，避免读取未完成数据。
• 版本：导航数据需携带版本号；热更新或流送时旧路径需可失效。

3.8 导航常见问题

第 4 章 大世界可见性：附近对象与不可见剔除

第 1 章已讨论 PVS、HZB 与遮挡剔除方案；本章将其放回“附近对象筛选 + 渲染剔除 + 大世界流送”的完整链路。

“角色附近的可见物”涉及两个不同问题，需要分别处理：

若将两者混用，就会出现“背后的交互物因不在视锥内而无法高亮”或“视野外的敌人仍在执行完整 AI 更新”等问题。

4.1 附近交互物的查询流程

典型查询是“以角色为圆心、半径 R 范围内的所有可交互对象”。最直接的做法是球体 overlap，但可通过以下步骤降低开销并提高稳定性：

1. 通过空间哈希或网格获取角色周围 3×3 或 5×5 的单元；
2. 对单元内对象执行距离平方比较，避免开方运算；
3. 按层、标签和状态过滤（可交互、存活、未冷却）；
4. 若玩法需要，使用视线射线确认目标未被墙体遮挡；
5. 按距离、朝向和优先级排序，取前 N 个；
6. 引入迟滞：进入半径与离开半径不同，避免边界抖动导致 UI 频繁闪烁。

// 伪代码：环形扩展 + 提前退出
for (int ring = 0; ring <= maxRing; ++ring) {
    for (Cell cell : CellsInRing(playerCell, ring)) {
        for (Entity e : grid[cell]) {
            if (!IsInteractable(e)) continue;
            float d2 = DistanceSquared(player.pos, e.pos);
            if (d2 > radius * radius) continue;
            candidates.push_back({e, d2});
        }
    }
    // 如果当前环的最小可能距离已经大于已找到的第 N 名，停止
    if (ring * cellSize > NthBestDistance(candidates, N)) break;
}

当对象数量较多时，可使用最大堆维护前 N 个最近对象；若还需考虑朝向，应将“距离 + 角度 + 优先级”合成为统一评分，而非仅按距离排序。

MMO 的 AOI（Area of Interest）采用类似思路，但服务于网络同步：网格 cell、九宫格、距离带、更新频率分级以及进入/离开事件。AOI 网格的 cell 通常大于渲染网格单元，因为网络同步对空间精度要求较低。

4.2 渲染剔除：从粗到细的四级筛选

flowchart LR
    A["场景对象"] --> B["距离 / LOD 粗筛"]
    B --> C["视锥剔除"]
    C --> D["遮挡剔除"]
    D --> E["提交渲染 / GPU Culling"]
    E --> F["阴影、反射等额外 pass"]

第一道：距离与 LOD

远处的小物体可直接剔除，或替换为 imposter/HLOD。距离剔除应最先执行，因为其开销最低。

第二道：视锥剔除

用相机的六个平面测试包围体。球体测试最简单：

若 \(d < -r\)，球体完全位于平面外侧，应予以剔除。AABB 可使用正顶点/负顶点测试；层次结构（BVH/八叉树）可在父节点整体位于视锥外时对整棵子树剪枝。

第三道：遮挡剔除

视锥内的物体不一定看得见，因为它可能被墙、地形、建筑挡住。常见方案：

遮挡剔除的基本原则是：先提交大型遮挡物以建立深度缓冲，再测试小型物体；若使用尚未写入深度缓冲的遮挡物执行测试，结果不可靠。

第四道：GPU Culling

现代引擎通常将可见性测试迁移至 GPU：由 compute shader 执行视锥或遮挡测试，将可见实例写入 indirect draw 参数，避免 CPU 回读。Nanite 等虚拟几何方案进一步使用 cluster 层次与 HZB 进行细粒度剔除。其核心思路仍是“层次结构 + 保守测试 + 批量提交”。

4.3 大世界流送：避免一次性加载整张地图

大世界通常按网格分块：

• World Partition / Cell：将世界划分为 cell，按玩家位置流送；每个 cell 具有独立的 actor 集合。
• Data Layer：同一空间里按玩法层加载（主线、支线、遗迹）。
• HLOD：远处不加载细粒度 actor，改用合并后的代理网格。
• Streaming Source：不仅考虑玩家位置，还需考虑相机、载具和传送门；多个 source 的并集决定加载范围。
• Additive Level / Scene：Unity 用 additive scene + Addressables；UE 用 World Partition + Level Streaming。

Cell 大小的权衡：

• 过小：流送频繁、actor 管理开销大，并可能产生边界 popping；
• 过大：内存峰值高、加载卡顿、HLOD 粒度较粗。

经验上应使“玩家正常移动跨越一个 cell 的时间”大于“异步加载与激活”的时间，并在边界处预留预加载环。

4.4 坐标精度：大世界坐标系统的典型问题

32 位 float 在原点附近精度较高，但离原点越远，最小可表示间隔越大。以 1 单位 = 1 厘米为例：

• 10 km 处，float 间隔约 0.1 厘米；
• 100 km 处，约 1 厘米；
• 1000 km 处，约 8 厘米。

这会导致：

• 角色/物体抖动；
• 碰撞形状错位；
• 阴影、贴花、粒子闪烁；
• 物理求解不稳定。

常见解决：

• Floating Origin / World Origin Rebasing：玩家远离原点后，将世界整体平移回原点，所有物体坐标同步偏移；
• Camera-relative rendering：渲染时以相机为原点计算；
• Large World Coordinates：用 double 或分块局部坐标保存大世界位置；
• 分块局部空间：每个 cell 用自己的局部坐标，跨 cell 时转换。

UE5 的 World Partition 与 Large World Coordinates、Unity 的 floating origin 方案，均用于解决同一类坐标精度问题。

4.5 视线查询：可见性、交互与感知的区别

“这个物体是否可见”在玩法上通常不是视锥问题，而是**视线（Line of Sight）**问题：

• 从角色眼睛/相机向目标发一条射线；
• 命中墙就不可见；
• 只对特定层（世界静态、角色、可交互物）做查询；
• 对高频查询执行缓存或分帧，避免每个交互物每帧执行一次射线检测。

若玩法需要“隔墙高亮”，则不应将视线查询作为唯一判据；应将“感知可见”“UI 可见”“渲染可见”拆分为三个独立概念。

第 5 章 查询加速：索引之外的优化手段

空间索引仅构成查询加速的一部分。实际优化手段可归纳为以下五类：

5.1 减少候选

• 合理的格子尺寸/树的分裂阈值；
• 多级索引：粗层筛选大区域，细层筛选对象；
• 层/标签/通道过滤前置；
• 用包围球做第一轮，AABB 做第二轮，精确形状最后做。

5.2 减少每次测试的成本

• 距离比较用平方距离，避免 sqrt；
• AABB 先测，OBB/三角形后测；
• SIMD 批量测 4/8 个 AABB；
• 提前返回：首个命中即返回，或达到 N 个结果后停止。

5.3 减少内存跳转

• BVH/八叉树用扁平数组，不用节点指针；
• SoA（Structure of Arrays）代替 AoS，方便 SIMD 和缓存；
• 空间哈希用开放寻址，不用链式 unordered_map；
• 对象句柄用 generational index，避免悬空指针。

5.4 利用时间相干性

• fat AABB：小移动不更新树；
• pair cache：复用上一帧的候选对；
• 缓存最近所在 cell/多边形；
• 增量更新，而不是每帧重建；
• 对静态对象只构建一次，动态对象单独一层。

5.5 并行与预算

• 查询按空间分块并行；
• 每个线程本地网格，最后合并；
• 导航与 AI 查询分帧执行，避免单帧完成全部计算；
• 远距离对象降频更新；
• 为查询设置预算（时间/数量），超出预算时执行降级策略。

5.6 Morton 码与空间局部性

将三维坐标的二进制位交错，可得到一维 Morton 码（Z-order curve）：

它能把空间相邻的格子映射到相近的一维索引，适合：

• 线性八叉树；
• 空间哈希的 key；
• 排序后批量处理；
• GPU 上的空间分块。

其代价是 Morton 序并非完全连续，查询时仍需处理边界；不应仅因结构复杂而放弃更简单的网格方案。

5.7 性能指标

第 6 章 其他模块中的空间查询

空间索引不仅服务于碰撞、导航和渲染。许多模块仅改变了查询形状与更新频率。

以下模块常被忽略，但其空间查询模式具有代表性：

6.1 网络 AOI：同步相关性与可见性的区别

MMO 的 AOI 通常按网格或九宫格管理玩家周围的对象，其关注点是“客户端需要同步哪些实体”，而非“相机是否可见”。具体而言：

• cell 可以比渲染格子大；
• 不同实体有不同更新频率（玩家、NPC、掉落物）；
• 进入/离开需发送事件，不应仅发送全量快照；
• 边界需引入迟滞，避免玩家在单元边缘往返移动导致实体反复创建与销毁；
• 大世界还需考虑跨服与分线，空间索引仅是第一层。

6.2 AI 感知：视锥 + 视线 + 记忆

AI 的“看到玩家”判定通常分为三步：

1. 距离/视锥粗筛：仅检查前方一定角度和距离内的目标；
2. 视线射线：确认目标未被墙体遮挡；
3. 感知记忆：目标离开视野后不立即清除，而是保留一段时间的位置记忆。

大量 AI 不应每帧执行全量扫描。可按帧分桶、按距离降低更新频率、通过空间哈希查询邻居，再将结果写入黑板或感知组件。

6.3 音频：空间查询的简化实现

音频系统通常不需要每帧执行精确几何查询：

• 使用网格或 BVH 查找听者附近的声源；
• 对重要声源执行遮挡射线检测；
• 通过 reverb zone/portal 处理室内外过渡；
• 对远处声源降低更新频率，甚至停止更新。

音频预算通常比渲染和物理更有限，因此近似计算与优先级策略比精确性更重要。

6.4 渲染：空间索引的最终使用方

渲染的剔除链路通常是：

1. 场景空间索引（BVH/八叉树/World Partition cell）；
2. 视锥剔除；
3. 遮挡剔除（HZB/PVS/软件遮挡）；
4. LOD/HLOD 选择；
5. GPU culling + indirect draw。

对超大世界而言，层次结构 + 批量提交比“每个对象单独一次 draw call”更为重要。Nanite 的 cluster 层次、植被 instancing 与 HLOD 合并网格，都是同一思想的不同实现。

第 7 章 系统设计：选型清单

7.1 选型时需确认的八个问题

设计空间查询模块时，应依次确认以下问题：

1. 查询形状：点、球体、盒体、射线、视锥、路径，还是最近 k 个对象？
2. 查询频率：每帧一次、每个角色一次，还是每帧数千次？
3. 对象动态性：静态对象与动态对象的比例如何？两者的索引策略通常不同。
4. 对象尺寸分布：尺寸接近时可选用网格或 SAP；差异较大时宜选用 BVH 或八叉树。
5. 世界规模：是否需要分块、流送与浮点原点重置？
6. 最坏情况：所有对象集中于同一区域、单个对象横跨全图，还是大量对象同时移动？
7. 更新成本：每帧重建 BVH 通常不可接受；每帧重建网格也可能开销过高。
8. 确定性要求：物理或网络回放是否对遍历顺序和浮点行为敏感？

7.2 简化选型树

根据上述问题，可得到如下简化选型路径：

flowchart TD
    A["对象数量是否较大？"] -->|否| B["暴力遍历 + 提前返回"]
    A -->|是| C["对象尺寸是否接近？"]
    C -->|是| D["网格 / 空间哈希 / SAP"]
    C -->|否| E["是否以静态对象为主？"]
    E -->|是| F["八叉树 / BVH / BSP"]
    E -->|否| G["动态 BVH / 分层网格"]
    D --> H["是否需要射线/视锥查询？"]
    F --> H
    G --> H
    H -->|是| I["BVH 或层次网格"]
    H -->|否| J["保持简单方案，先测量瓶颈"]

最后一项判断尤为关键：当对象数量仅为数百时，暴力遍历往往比维护索引更高效。索引的价值来自规模，而非结构复杂度。

7.3 常见实现问题

7.4 核心结论摘要

• 碰撞检测：broad phase 生成候选对象对，narrow phase 计算接触流形；高速物体需启用 CCD。动态树与膨胀 AABB 是常用组合。
• 导航：Recast 负责构建导航网格，Detour 负责运行时查询；A* 生成多边形走廊，漏斗算法拉直路径，ORCA/RVO 处理局部避障；大世界采用分块导航网格与 Navigation Invoker。
• 可见性：依次执行距离/LOD 粗筛、视锥剔除、遮挡剔除与 GPU culling；PVS 适用于室内场景，HZB 与软件遮挡适用于大范围场景。
• 附近交互物：通过空间哈希检索邻接单元，使用平方距离与状态过滤，再执行视线检测、优先级评分与迟滞处理。
• 大世界：采用分块流送、HLOD 与浮点原点重置/局部坐标；单元大小需权衡流送频率与内存占用。
• 查询加速：减少候选数量、降低单次测试成本、改善内存局部性、利用时间相干性，并设置并行与预算策略。
• 选型：优先考虑更新模式，再考虑查询形状；对象数量较少时，暴力遍历可能优于维护索引。

当需要重新梳理问题时，可按以下顺序判断：查询形状 → 候选集 → 精确测试 → 更新成本 → 最坏情况。