背景
硕士期间研究课题是海洋生物数字孪生，基于各类Boids改进的算法里会有大量的海洋鱼类在三维空间中运动，鱼类之间会有互相感知的过程，同一帧里需要对许多行为进行决策判定，例如同伴鱼、食物、捕食者、栖息地等等。因此打算研究下有什么空间加速算法能够避免暴力迭代，减少开销。既然研究了这个，顺便也把碰撞检测也给弄懂了，想一次性弄的透彻一些，所以基于各个算法实现了一套碰撞检测框架。文章大纲和[1]这篇类似，包含了碰撞检测和空间加速算法。但是对各个算法的原理会简单概括，不对细节进行冗余介绍，但是会对各个算法的优缺点进行总结，并且主要侧重于框架的搭建。
碰撞检测
各种碰撞体
- BoxCollider
- SphereCollider
各种碰撞检测算法
AABB算法（Axis-Aligned Bounding Box)
OBB/SAT算法（Oriented Bounding Box / Seperating Axis Theorem）
OBB不赘述了，是简化成了四条边的SAT
- 分离轴定理：两个凸多边形之间如果不相交，那么必定存在一条线可以将两者进行分割。这条线称之为分割线（Seperating Line）
- 分离轴定理推论：两个凸多边形之间如果不相交，那么必定存在一条轴，让两多边形落在上面的投影线段不相交。这条轴称之为分离轴（Seperating Axis）
所以只要找到了那一条分离轴，就必定可以判断出两个凸多边形不相交。
但是这样找很难找，遍历的范围是无穷的，所以就有了简化的证明方法，来缩小搜索范围（重要推论）
- 重要推论：两个凸多边形之间如果不相交，那么必定存在一条平行于这两个多边形中的某一条边的分割线，同时有一条垂直于该分割线的分割轴，让两多边形落在上面的投影线段不相交。
其实AABB、OBB、SAT我认为都有个共同点，它们都是：只要寻找到一个轴，落在上面的投影没有交叉（Amin > Bmax || Amax < Bmin），则整体都不会有相交。
GJK算法（Gilbert–Johnson–Keerthi 人名缩写）
结论
两个多边形相交 <=> 则它们的闵可夫斯基差集必然包括原点（零向量）
Support函数
输入为方向d，输出是该方向上凸多边形的最远顶点的位置。
闵可夫斯基差集
图形A和图形B中的所有（xx的）点坐标相减，得到的新集合叫闵可夫斯基差集。
碰撞检测算法的切换条件
加粗代表已实现
- Sphere：两者都是Sphere时。
- AABB（可被OBB代替）：两者都是未发生旋转的Box，或者本身就是限制旋转的AABBBox。
- ABBB-圆[3,4]：两者其中一者是未发生旋转的Box，或者本身就是限制旋转的AABBBox，另一者是Sphere。
- OBB（可被SAT代替）：两者都是Box，且其中任意一者存在旋转。
- SAT-多边形-多边形：两者都是凸多边形，且两者都不是Sphere。
- SAT-多边形-圆：两者中其中一者是凸多边形，另一者是圆形。
- GJK：两者中其中一者是凸多边形，且两者都不是Sphere。
- EPA：两者中其中一者是凸多边形，且两者都不是Sphere。
以上SAT、GJK、EPA三选一 - 圆框与AABB矩形框（矩形框不旋转）：其中一者是未发生旋转的Box，或者本身就是限制旋转的AABBBox。另一者是Sphere。
- 分割SAT：两者其中一者是凹多边形，且两者都不是Sphere。
相关算法
判断一个点在一条线的顺时针侧（右）还是逆时针侧（左）
判断一个点是否在一个三角形内
面积法
向量法
无论三角形的连线方向是顺逆时针。只要点在三条边的同侧，就代表点在三角形内部。
判断一个图形是凹是凸
定义：凸多边形是指如果一个多边形的所有边中，任意一条边向两方无限延长成为一直线时，其他各边都在此直线的同旁，那么这个多边形就叫做凸多边形。
实现过程：① 从凸多边形的一个点开始，顺序选择第二个点，连成一条直线。 ②判断剩下所有点是否都在该直线的同一侧。 ③ 反复①过程，遍历完每一条边，如果每条边都满足②，则为凸多边形。
Unity的碰撞检测介绍
在Unity 5.5之前，Unity使用SAT来进行碰撞检测。之后Unity推出了PCM（持久接触流形，Persistent Contacts Manifold）方法，会更高效，无用的碰撞点信息会更少。
现在的项目默认都是PCM了，但是也可以在Project Settings里修改：
空间划分加速算法
BSP，BHV，八叉树，四叉树
框架设计及搭建
参考
[1] https://blog.csdn.net/weixin_42186870/article/details/136147295
[2] https://zhuanlan.zhihu.com/p/177006015
[3] https://www.zhihu.com/question/266499219/answers/updated
[4] https://www.cnblogs.com/zhjblogs/p/16737750.html