AABB树比暴力检测快因将相交查询从O(n²)降至近O(log n)，但需手动实现增量更新、脏标记与节点局部性优化，标准库无现成支持。
为什么AABB树比暴力检测快，但又不能直接套用标准库
因为C++标准库没有现成的AABBTree或DynamicAABBTree——它得自己搭骨架。暴力检测是O(n²)，而AABB树把相交查询压到接近O(log n)（理想情况），前提是树结构平衡、插入/删除开销可控。但别指望std::map或std::vector自动帮你维护包围盒层级关系；它们不感知几何，也不处理重叠更新。
常见错误现象：update()没调用，导致移动后包围盒还是旧的，漏检；或者每次帧都重建整棵树，反而比暴力还慢。
- 核心不是“建树”，而是“增量更新”：只重算受影响的节点，用
refit()而非rebuild() - 叶子节点必须存原始几何引用（比如
const Triangle&），不能深拷贝顶点——否则内存和缓存不友好 - 树节点里存
min/max用glm::vec3或自定义AABB结构，别用std::array<float, 6>，可读性和SIMD对齐都不如明确字段
如何写一个能跑进游戏主循环的AABB树插入/更新逻辑
关键在“惰性更新”和“脏标记”。游戏物体每帧位移后，不立即下推到树底，而是先标dirty = true，等需要查询前统一refit()一次。否则每动一下就递归上提，CPU cache line疯狂失效。
使用场景：刚体移动、角色动画骨骼带动碰撞体、动态地形块加载。
立即学习“C++免费学习笔记（深入）”；
- 插入时用
insert(const AABB& aabb, void* user_data)，返回唯一node_id，后续靠它定位更新 - 更新用
update(node_id, const AABB& new_aabb)，内部只重算该节点到根路径，复杂度O(height) - 避免用
std::shared_ptr<Node>管理节点——指针跳转破坏连续性；改用std::vector<Node>+ 索引，parent_idx、left_idx、right_idx全用int
碰撞查询时怎么避免误报和漏报
AABB树只做粗筛，返回的只是“可能相交”的物体对列表，最终还得用三角形-三角形或射线-三角形等细检。误报来自包围盒太松（比如旋转后没重新计算AABB），漏报基本等于树没正确更新或查询时剪枝条件写错。
错误信息典型例子：query_ray() returns empty while visual debug shows overlap——大概率是射线方向未归一化，或AABB的intersects(ray)实现里用了不稳定的平面测试。
- 查询函数签名建议为
query(const AABB& query_aabb, std::vector<void*>& out)，输出用引用传入，避免每帧分配 - 剪枝条件必须用
!node_aabb.intersects(query_aabb)，而不是node_aabb.contains(query_aabb)——后者太严格，直接跳过所有非完全包含的分支 - 静态物体放一层子树，动态物体另起一棵；混合查询时先查静态再查动态，避免频繁重平衡
性能瓶颈常卡在哪儿，怎么验证
最常被忽略的是内存布局和遍历顺序。AABB树快，是因为节点局部性好、分支预测准；一旦Node结构体里混了虚函数、std::string或指针跳转，L1 cache miss率飙升，速度反超暴力。
用perf record -e cache-misses,instructions ./game看cache miss ratio，超5%就得查结构体对齐和访问模式。
-
Node结构体必须alignas(16)，min/max字段连续排布，别夹着bool dirty——把它挪到最后或打包成uint8_t flags - 遍历时用栈模拟递归（
std::vector<int> stack），别真递归——深度大时栈溢出，且编译器难优化 - 调试时加
#ifdef DEBUG_AABB_TREE宏控制validate()，但发布版必须关掉——它本身是O(n)全遍历
真正麻烦的是运动物体带来的树不平衡，以及多线程写冲突——单个update()可以无锁，但批量update()必须加std::atomic<bool> updating保护，否则refit中途被另一个线程覆盖父节点包围盒。
