Desc:
碰撞检测是适用于碰撞处理的一部分，碰撞处理可以分为三个部分：碰撞检测，碰撞计算，碰撞响应。碰撞检测的结果通常是一个布尔量，它告知了是否存在两个或者更多的物体相撞；而碰撞计算求出物体间碰撞的实际交点；最终，碰撞响应决定针对两个物体的碰撞，该采取什么样的行动
优化的思路
减少检测的数量
通过四叉树或者八叉树，将地图分块，每次只检测当前角色附近区域的块
减少检测的计算
将除角色外的物体视作静态，发射射线去检测碰撞
射线的碰撞检测
一般通过向角色的下方位置发射射线去根据距离检测位置，如果是负的，说明需要向上，不适用于复杂的场景(角色发生旋转，这是不能通过脚的位置向下发出射线，需要不同方向发射不同射线)
动态BVH树的动态碰撞检测
动态包围盒层次结构（Dynamic BVH）是一种数据结构，用于加速射线追踪等计算机图形学应用程序。它是一个树形结构，每个节点表示一组物体的包围盒，而叶节点表示单个物体的包围盒
动态BVH树
BSP树的动态碰撞检测
二叉空间分割树，在多边形剪切方面出色，在碰撞检测方面高速
使用BSP进行碰撞检测的本质是减少了树的遍历和搜索，前期派出了大量的多边形，在最后仅仅对少数面进行碰撞检测
构建
球体树方法(加速构建)
分割
将所有的平面组成一个树，平面将空间分割为前后两个部分，这两个部分再被其他平面分割成更小的空间
分割
生成算法
缺点
· 耗时
· 不解决可见表面确定的问题?
代码
用途
随机地图生成
随机地图生成2d
网格切割
自动生成室内portal
自动生成导航网格
导航网格（Nav Mesh）是一种表示凸多边形的节点，目前主流游戏的游戏AI寻路中最常用的节点种类。通过用导航网格，A*寻路所要搜索的节点数量大大减少且变得灵活。
因此我们可以预先计算可移动地形和静态障碍，得到一个不规则的大地图形状（可能有凹处也可能有中空处），然后以该形状的所有边来构造一棵BSP树来分割得到若干个凸多边形房间，而这些分割出来的每个凸多边形都是一个导航网格
构建CSG几何体
而BSP树可以很好的处理和表示这些CSG几何体，UE4引擎中的几何体编辑就是采用BSP方式
渲染顺序优化（不实用、已淘汰过时）