实现AABB Tree（轴对齐包围盒树）是高效物理模拟和光线追踪的关键。由于其主要用于动态场景的粗略阶段，实现时需要重点关注动态更新和树的质量。
以下是实现 AABB Tree 时需要注意的几个核心问题和最佳实践：
🏗️ 结构设计与构建 (Structure and Construction)
1. 节点数据结构
节点是树的基本单元，需要设计得足够精简和高效：
- 包围盒 (AABB): 存储该节点 AABB 的最小点 (min) 和最大点 (max) 坐标。
- 子节点/父节点索引: 使用索引（而非指针）来引用父节点和子节点。这对于内存局部性、缓存友好性（Cache-friendly）以及后续的内存管理（例如，使用池分配器）非常重要。
- 叶子数据: 如果是叶子节点，需要存储其引用的几何体索引或指针。
2. 优质的树构建启发式 (High-Quality Heuristics)
树的质量（平衡性和紧凑性）直接决定了查询性能。
- 构建准则: 在递归划分物体集合时，选择能最大程度减小子节点 AABB 体积之和或表面积之和的划分轴和划分位置。
- 分割策略: 常见的策略是：
- 找到最长的轴，并沿该轴的中位数或几何中心分割物体。
- 使用SAH (Surface Area Heuristic, 表面积启发式)，这是光线追踪中常用的高级方法，通常能产生查询效率最高的树。
🔄 动态更新与平衡 (Dynamic Updates and Balancing)
AABB Tree 的主要难点在于物体移动后如何高效地更新树结构，同时避免树变得不平衡。
1. 动态插入的成本函数
在插入一个新的 AABB（代表一个移动后的物体）时，必须选择一个最佳的兄弟节点。
- 最小体积增长 (Minimum Volume Increase): 遍历树，在每个分支节点选择将新 AABB 插入到能导致父节点 AABB 体积增量最小的子树。
- 代表 AABB 的体积。选择成本最低的路径。
- 最小化表面积 (Minimum Surface Area): 有时最小化AABB 的表面积增长会产生更好的效果。
2. 节点“增肥” (Fattening AABBs)
这是处理动态物体的关键优化。
- 原理: 不是让节点 AABB 刚好包裹其物体，而是让它稍微变大一点（“增肥”）。
- 好处: 只要物体移动的范围仍在其“增肥 AABB”内，就无需更新树结构。只有当物体移出这个增肥 AABB 时，才需要将其从树中移除并重新插入，这大大减少了每帧的树更新操作。
3. 树的平衡 (Rebalancing)
随着物体不断移动、移除和插入，树结构可能变得失衡，导致查询效率退化到 。
- 旋转操作 (Rotation): 像 AVL 或红黑树一样，使用旋转操作来重新平衡节点，但 AABB Tree 的平衡是基于几何质量而非深度。例如，可以使用旋转操作来优化一个父节点和它的兄弟节点 AABB 之间的重叠体积。
- 渐进式重构: 不要在每一帧完全重建树，而是在每次更新或经过一定时间后，对树中质量较差的子树进行局部的重新平衡或重构。
🚀 碰撞查询 (Overlap Query)
1. 递归/迭代查询
查询操作（找到与给定 AABB 重叠的所有叶子 AABB）应采用深度优先（DFS）或广度优先（BFS）的遍历策略。
- 核心逻辑: 从根节点开始，如果当前节点的 AABB 与查询 AABB 不重叠，则跳过整个子树，这是 BVH 效率的来源。如果重叠，则递归检查其子节点。
2. 成对碰撞查询
粗略阶段的最终目标是找出可能碰撞的物体对 。
- 自相交 (Self-Intersection): 在查询时，通常会将树与自身的 AABB 进行查询，收集所有重叠的叶子 AABB 对。
- 去重: 确保每对碰撞只报告一次，例如，只报告 而不报告 。
3. 连续碰撞检测 (CCD) 的考虑
如果需要处理高速移动的物体（避免“穿透”问题），需要将 AABB 扩展为一个扫掠体（Swept AABB），它包含物体在当前帧到下一帧之间的整个移动轨迹。查询时，用另一个物体的 Swept AABB 进行重叠测试。