[toc]

# 空间划分算法

# 四叉树

1. 每个四叉树节点都有四个子节点，子节点只在需要时创建
2. 创建子节点时会触发切割，即将一个完整的树节点切割成四个等大小的子节点
3. 切割子节点后需要确定切割前节点内的元素都在新节点的哪里，并进行更新

可以用于加速碰撞检测

# 基于四叉树的碰撞检测优化

1. 遍历所有待碰撞检测节点
2. 找到当前节点所在的四叉树节点
3. 对同一四叉树节点内的物体进行碰撞检测 (可暴力)

# 非线性八叉树

Tag: 线性八叉树是非线性八叉树的优化版本，实际上并无太大区别

八叉树实际上和四叉树的创建思路一致，区别不同的是八叉树是进行空间上的划分，每次不断地将空间切分为上四下四的八个子空间 本文参考的八叉树例子来自下述仓库:
https://github.com/AsehesL/SceneSeparateDemo 这个仓库中的示例是使用八叉树和四叉树进行场景的可视化裁剪，案例中使用相机空间的齐次裁剪空间来进行 AABB 裁剪判断。 延迟插入节点方法:

1. 每次插入包围盒时遍历八叉树的八个中心点，判断当前八叉树是否包含这个包围盒
2. 包含这个包围盒直接将包围盒连接到当前节点上
3. 不包含这个包围盒，则进入下一个八叉树深度进行尝试

每次进入八叉树节点检查是否包含包围盒时，调用 CreateNode 函数，如果当前节点存在，则直接返回节点，如果不存在，则创建 和四叉树一致，插入时判断

# BVH 树 (层次包围盒)

BVH 主要分成两个节点

1. 包含 N 个物体的 AABB 叶子节点
2. 包含多个 AABB 的 AABB 节点

# 表面积启发式 SAH

SAH 是通过