SAT 分离轴算法

[phenomLi]

基础知识

对于检测精度要求高的场景。包围盒便不能满足了，需要一种更加精确的检测方法。碰撞检测系统的细检测使用分离轴算法（SAT）。分离轴算法是一项用于检测凸多边形碰撞的技术。
试想一下，用照明灯照射两个相交多边形到墙上，按照日常经验，无论在哪个角度照射，两个多边形在墙上的投影一定会相互重叠（绿色线段表示投影的重叠部分）：

但是，不相交的多边形在墙上的投影也可能相交：

然而，按照分离轴定律，两个不相交的多边形一定能找到一条轴，它们在这条轴上的投影不相交，也就是一定存在一个角度用电筒照这两个不相交多边形得到不相交的投影：

分离轴算法就是要验证：

两个多边形间是否存在这样一条轴，使得这个两个多边形在这条轴上的投影不相交，只要发现这样一条轴，即可马上判定两个多边形不相交，否则就是相交。这条轴就是分离轴。


要实现算法，即要枚举所有可能的轴判断是否存在投影没有交集的情况，而二维空间中有无数条轴，不可能做到全部遍历。但幸运的是，两个多边形的每条边的法向量包含了这条轴的所有可能性，所以只要枚举所有边的法向量即可。即遍历所有边的法向量，看该法向量是否要找的分离轴。

对于多边形和圆形的碰撞，只要找出多边形离圆形最近的那个顶点，该顶点与圆心之间的连线就是多边形和圆形间的分离轴。

而圆形与圆形间的碰撞的判断便更简单了，只要判断两圆心间的距离与两圆半径的和的大小关系便可。

算法实现

首先，要找出两个图形的所有候选分离轴：

// 获取两个图形的所有候选分离轴
// vector类型是两个点之间的向量
function getAxes(obj1: shapeData, obj2: shapeData): Array<vector> {
        // 保存第一个图形的候选分离轴
    let axesList1: Array<vector>,
        // 保存第二个图形的候选分离轴
        axesList2: Array<vector>;

    /**
     * 找出单个图形的候选分离轴
     * 若图形是多边形，调用getPolyAxes函数获取
     * 若是圆形，则调用getCirAxes函数获取
    */
    axesList1 = obj1 instanceof Array? getPolyAxes(obj1): getCirAxes(obj1, obj2);
    axesList2 = obj2 instanceof Array? getPolyAxes(obj2): getCirAxes(obj2, obj1);

    // 合并两个候选分离轴
    return axesList1.concat(axesList2);
}

getPolyAxes和getCirAxes具体实现如下：

// 获取多边形的候选分离轴
function getPolyAxes(obj: PolygonVex): Array<vector> {
        // 保存候选边结果
    let axesList: Array<vector> = [],

    // 遍历所有顶点
    for(let i = 1, len = obj.length; i < len; i++) {
        // 获取多边形的单个边
        let edge = [vexs[i][0] - vexs[i - 1][0], vexs[i][1] - vexs[i - 1][1]];

        // 将边的法向量加入候选列表
        axesList.push(Vector.nor(edge));
    }

    // 返回候选列表
    return axesList;
}


// 获取圆形的候选分离轴
function getCirAxes(obj1: CircleInfo, obj2: polygonVex): Array<vector> {
        // 保存离离圆心的最短距离
    let minLen: number, 
        // 保存最短距离的顶点的下标
        index = 0,
        // 圆心坐标x
        x = obj1.x,
        // 圆心坐标y
        y = obj1.y,
        // 保存多边形的顶点
        vexs = obj2;

    // 假设距离最短为第一个顶点
    minLen = Vector.len([vexs[0][0] - x, vexs[0][1] - y]);

    // 遍历顶点，找出多边形到圆心距离最小的顶点
    vexs.map((v, i) => {
        let len = Vector.len([v[0] - x, v[1] - y]);

        if(len < minLen) {
            minLen = len;
            index = i;
        }
    });

    // 返回距离最短的顶点与圆心的连线向量
    return [[vexs[index][0] - x, vexs[index][1] - y]];
}

找到候选轴后，便要计算图形在候选轴上的投影长度，计算图形在向量上的投影实现如下：

/**
 * 投影函数
 * @param {Shape} obj 图形
 * @param {vector} sAxis 要将图形投影到的轴
 * @returns {number[]} 投影结果的范围
 */
function project(obj: shapeData, sAxis: vector): number[] {
    // 投影范围
    let range: number[];

    // 若是多边形
    if(obj instanceof Array) {
        let vexs = obj,
            // 遍历所有顶点，求该顶点在轴上的投影长度，将所有顶点在轴上的投影长度保存到数组projection中
            projection = vexs.map(v => Vector.pro(v, sAxis));

        // 选取投影长度的最大与最小值即为多边形在轴上的投影范围
        range = [
            Math.min.apply(Math, projection), 
            Math.max.apply(Math, projection)
        ];
    }
    // 若是圆形
    else {
        let x = obj.x,
            y = obj.y;

        // 圆形在轴上的投影范围即为圆心在轴上的投影长度，再加/减圆的半径
        let len = Vector.pro([obj.x, obj.y], sAxis);
        range = [len - obj.radius, len + obj.radius];
    }

    // 返回投影范围
    return range;
}

有了这些准备，我们便可以编写用于判断多边形的分离轴算法的主函数：

// SAT分离轴
function SAT(obj1: shapeData, obj2: shapeData): boolean {
    // 首先获取两个图形的所有候选轴
    let axes = getAxes(obj1, obj2);
    
    // 遍历所有候选轴，算出两个图形分别在每条候选轴的投影范围
    for(let i = 0; i < axes.length; i++) {
            // 第一个图形的投影
        let pro1 = project(obj1, axes[i]),
            // 第二个图形的投影
            pro2 = project(obj2, axes[i]);

        // 若只要发现有一条轴上投影不相交，则可马上判断图形不相交，返回false
        if(!isOverlaps(pro1, pro2)) {
            return false;
        }
    }

    // 所有投影都相交，返回true
    return true;
}

对于判断两个图形在轴上是否相交，可以抽象为检测两条共线线段的相交，也就是可以利用上一节提到的isOverlaps函数。

而对于圆形间碰撞的判断，可以另外单独判断：

// 检测圆形间的碰撞
function circleContact(obj1: CircleInfo, obj2: CricleInfo): boolean {
        // 计算两圆圆心的距离
    let centerDistance = Math.sqrt(Math.pow(obj1.x - obj2.x, 2) + Math.pow(obj1.y - obj2.y, 2)),
        // 计算两圆半径的和
        sumRadius = obj1.r + obj2.r;

    // 判断两圆是否相交
    return centerDistance > sumRadius? false: true;
}

由于图形间有多种碰撞可能：

• 多边形和多边形碰撞

• 多边形和圆形碰撞

• 圆形和圆形碰撞

所以，我们要对这些情况进行分类处理：

function SATDetection(obj1: Shape, obj2: Shape): boolean {
    // 若两个图形都是圆形，然后直接调用circleContact快速判断
    if(obj1 instanceof Circle && obj2 instanceof Cricle) {
        return circleContact(obj1, obj2);
    }
    // 否则调用SAT算法判断
    else {
        return SAT(obj1, obj2);
    }
}  

在最后，我们利用一个SATDetection对碰撞类型进行简单的分类。到这里，分离轴算法的内容已经大致介绍完毕，我们的碰撞检测系统也大致完成。但是，该算法有一个缺陷就是只能判断凸多边形的碰撞，我们要支持任意多边形的话，还要对多边形进行判断和分割。

我们秉着对技术的追求，对碰撞系统进行最后的完善，下一节将介绍凹多边形的判别和分割算法的介绍和实现。

[conanjunn]

有个问题想请教下，用投影长度大小来比较得到投影最边缘的两个点，应该有个前提是这个多边形所有的点必须是在x轴（或者Y轴）的同一侧吧？ 要不然可能出现得到的点不是最边缘的点的情况

[phenomLi]

有个问题想请教下，用投影长度大小来比较得到投影最边缘的两个点，应该有个前提是这个多边形所有的点必须是在x轴（或者Y轴）的同一侧吧？ 要不然可能出现得到的点不是最边缘的点的情况

不是很理解你的意思，投影都是投影在法线上的，没有严格意义上的x或者y轴

[conanjunn]

有个问题想请教下，用投影长度大小来比较得到投影最边缘的两个点，应该有个前提是这个多边形所有的点必须是在x轴（或者Y轴）的同一侧吧？ 要不然可能出现得到的点不是最边缘的点的情况

不是很理解你的意思，投影都是投影在法线上的，没有严格意义上的x或者y轴

红线假设为AB边的法线，现在求C点的投影长度
projection = vexs.map(v => Vector.pro(v, sAxis)); 这段代码得到的投影长度，是图里绿色部分的长度是吧？ 我看代码理解为是黄色线的长度

[phenomLi]

有个问题想请教下，用投影长度大小来比较得到投影最边缘的两个点，应该有个前提是这个多边形所有的点必须是在x轴（或者Y轴）的同一侧吧？ 要不然可能出现得到的点不是最边缘的点的情况

不是很理解你的意思，投影都是投影在法线上的，没有严格意义上的x或者y轴

红线假设为AB边的法线，现在求C点的投影长度
projection = vexs.map(v => Vector.pro(v, sAxis)); 这段代码得到的投影长度，是图里绿色部分的长度是吧？ 我看代码理解为是黄色线的长度

就是黄色的线段没错，如果红线指向的方向为x轴正方向，则C的投影值为正，B为负

[conanjunn]

有个问题想请教下，用投影长度大小来比较得到投影最边缘的两个点，应该有个前提是这个多边形所有的点必须是在x轴（或者Y轴）的同一侧吧？ 要不然可能出现得到的点不是最边缘的点的情况

不是很理解你的意思，投影都是投影在法线上的，没有严格意义上的x或者y轴

红线假设为AB边的法线，现在求C点的投影长度
projection = vexs.map(v => Vector.pro(v, sAxis)); 这段代码得到的投影长度，是图里绿色部分的长度是吧？ 我看代码理解为是黄色线的长度

就是黄色的线段没错，如果红线指向的方向为x轴正方向，则C的投影值为正，B为负

我没算上负号。。。 是我弄错了。 感谢回答~

[phenomLi]

有个问题想请教下，用投影长度大小来比较得到投影最边缘的两个点，应该有个前提是这个多边形所有的点必须是在x轴（或者Y轴）的同一侧吧？ 要不然可能出现得到的点不是最边缘的点的情况

不是很理解你的意思，投影都是投影在法线上的，没有严格意义上的x或者y轴

红线假设为AB边的法线，现在求C点的投影长度
projection = vexs.map(v => Vector.pro(v, sAxis)); 这段代码得到的投影长度，是图里绿色部分的长度是吧？ 我看代码理解为是黄色线的长度

就是黄色的线段没错，如果红线指向的方向为x轴正方向，则C的投影值为正，B为负

我没算上负号。。。 是我弄错了。 感谢回答~

没事 希望可以多交流