基础GamePlay知识-凸多边形碰撞检测（SAT）

在这里插入图片描述

分离轴算法

也称为SAT(Separating Axis Theorem)算法，主要用于凸多边形之间的相交检测，主要思路为寻找分离轴。

分离轴：分离轴是一个向量，可以理解为一条平行于多边形边的线。如果两个凸多边形在分离轴上的投影没有重叠，那么它们在原空间中也不相交。
凸多边形：凸多边形是指其内部的任意两点之间的连线都在多边形内部。凸多边形的特点使得我们可以通过分离轴来判断它们是否相交。
在这里插入图片描述
可以想象，对于每两个要检测相交的多边形，分离轴所在处一定可以是和其中某个多边形的边平行的方向。
那么将多边形往每个边的法线做投影，只要两个多边形投影的线段存在不相交的情况，就说明四边形不相交，图片没有把所有垂线画出来。
在这里插入图片描述

难点

如何求向量的法线

由于多边形的每个顶点我们是已知的，所以需要一个方法快速的得到某个边的法线，这里介绍一种办法，步骤如下

将边向量A关于y = x做对称向量B
比如A(x1,y1)那么对齐向量是B(y1,x1)
将B关于y轴做对称，即为垂直向量
B(y1,x1)的y轴对称向量是C(-y1,x1)
将该垂直向量单位化

喜欢思考的读者一定会疑惑，为什么这样能得到垂直向量呢，看下图
首先是代数层面，满足了 A * C = 0
在这里插入图片描述
其次是几何证明，A的垂直向量是C，只需证明x是90°

如何将多边形投影到向量上

这里有读者肯定会疑惑，如果是把每个点做投影到向量（后称为A）上，首先是计算量大，其次得到的整个多边形投影出来是一个线段，是不是还得得到一个向量的直线方程，去比较点的位置关系。
其实没有那么麻烦，我们只需要得到每个点的世界坐标，将这个坐标当成某个点的向量，然后点乘A，相当于把A当成一个轴，这样就能取得每个点在投影方向上的坐标，或正或负，得到多边形所有的点在这个轴上的坐标，最小和最大的坐标所成线段就是轴上的投影，之后然后用类似矩形AABB检测的办法去比较两个多边形所成投影是否相交即可。
下图橙色区域里面的红蓝绿等向量就是投影结果，箭头只表示在轴上的正负，长度表示大小。
在这里插入图片描述

代码

    /// <summary>
    /// 多边形碰撞检测，利用分离轴定理
    /// </summary>
    /// <param name="polygon1">包含多边形中一系列点的位置</param>
    /// <param name="polygon2">包含多边形中一系列点的位置</param>
    /// <returns></returns>
    private bool Dectect_PolygonAndPolygon(Point[] polygon1, Point[] polygon2)
    {
        for (int i = 0; i < polygon1.Length; i++)
        {
            //和边垂直的投影向量
            Vector3 start = polygon1[i].transform.position;
            Vector3 endPos = polygon1[(i + 1) % polygon1.Length].transform.position;
            Vector3 normal = new Vector3(endPos.y - start.y, start.x - endPos.x).normalized;//对称法求垂直向量，不记得可以去看笔记
            float minProjectA, maxProjectA, minProjectB, maxProjectB;
            ProjectPolygon(normal, polygon1, out minProjectA, out maxProjectA);
            ProjectPolygon(normal, polygon2, out minProjectB, out maxProjectB);
            if (minProjectA > maxProjectB || minProjectB > maxProjectA) { return false; }
        }
        for(int i = 0; i < polygon2.Length; i++)
        {
            Vector3 start = polygon2[i].transform.position;
            Vector3 endPos = polygon2[(i + 1) % polygon2.Length].transform.position;
            Vector3 normal = new Vector3(endPos.y - start.y, start.x - endPos.x).normalized;
            float minProjectA, maxProjectA, minProjectB, maxProjectB;
            ProjectPolygon(normal, polygon1, out minProjectA, out maxProjectA);
            ProjectPolygon(normal, polygon2, out minProjectB, out maxProjectB);
            if (minProjectA > maxProjectB || minProjectB > maxProjectA) { return false; }
        }
        return true;
    }
/// <summary>
/// 将多边形投影到向量上
/// </summary>
/// <param name="axis">投影向量</param>
/// <param name="polygon">多边形</param>
/// <param name="minProject">投影小边界</param>
/// <param name="maxProject">投影大边界</param>
/// <returns></returns>
    private void ProjectPolygon(Vector3 axis, Point[] polygon, out float minProject, out float maxProject)
    {
        float defalut = Vector3.Dot(axis, polygon[0].transform.position);
        minProject = defalut;
        maxProject = defalut;
        foreach(Point point in polygon)
        {
            float cur = Vector3.Dot(axis, point.transform.position);
            if (cur < minProject) minProject = cur;
            else if (cur > maxProject) maxProject = cur;
        }
    }
``