利用多边形切割进行分离轴算法优化

[phenomLi]

最近两个星期，都在实验室硬刚物理引擎。昨天写到了碰撞检测的凹多边形与凹多边形碰撞的判断，源用了以往的思路：将凹多边形分割为多个子凸多边形，然后再遍历两个凹多边形的子凸多边形进行判断。一气呵成地，写下了下面的代码：

for(子多边形1 in 凹多边形1) {
    for(子多边形2 in 凹多边2) {
        // 分离轴测试
        SAT(子多边形1, 子多边形2);
    }
}

但是写完之后我看着它竟有点不爽，两个凹多边形，每一帧都这样搞，O(n^2)的复杂度里面再进行分离轴测试？大家都知道分离轴测试是整个碰撞检测流程里面最昂贵的部分，这样很可能造成性能问题（以前没有意识到这个问题，现在想起来恍然大悟）。

那么有没有优化的办法呢？一番思考后我找到了一些苗头：两个凹多边形发生碰撞，绝大部分情况下都是各种单独某个子多边形间的碰撞，而凹多边形剩下的很大一部分是与碰撞无关的，如下图：

没错，这就是优化的切入点，所以现在问题的关键就是如何快速过滤掉这些不可能发生碰撞的子多边形。看到关键字“快速过滤”，很自然地，就想到了包围盒。也就是说，我们可以对每个子多边形都创建一个包围盒，在进行分离轴检测前首先用包围盒过滤大部分与碰撞无关地子多边形。此时感觉一扇通往真相地大门就要开启了。

正当我准备开干时，脑海中又突然闪过一条重要地信息：记得之前看到过，任意多边形都可以被划分为若干个子三角形。这一点太重要了！换句话说，我们可以不需要再去区分凹多边形和凸多边形，对于任意的多边形，我们都把他分割为多个小三角形，然后再为每个小三角形创建包围盒即可！小三角形的粒度比子多边形要更细，也就是说使用小三角形能过滤更多无关的部分，而在最后进行的分离轴测试中，测试的只是两个三角形间的碰撞，这效率是很高的。

现在，任意多边形间的碰撞最终都会收敛为两个三角形的碰撞。我们现在要解决的问题便是：如何分解多边形为多个三角形？

多边形的分割

其实多边形的分割算法是很简单，但有一个前提就是多边形顶点必须按照顺时针或者逆时针排序。在有序的顶点中分割三角形大致流程如下：

1. 任取多边形上一个顶点A，该点即为分割点

2. 然后再取A的上一个点B

3. 再取这个A的下一个点C，这时ABC三个点组成了一个三角形ABC

4. 把这个三角形ABC从多边形中切掉

5. 循环以上步骤，直到多边形顶点数 === 3，停止

如上图，有多边形012345，以顶点1作为分割点，可分割出三角形012。

以上流程在凸多边形中运行良好，但是对于凹多边形，要有一些细节需要注意：

如图有凹多边形012345，在选取顶点0作为分割点时，可以看到顶点4在得到的三角形015内部，这是不合理的。另外，在选取顶点4作为分割点时，得到的三角形543不在多边形内部，这种情况也是不可取的。

那么怎么解决呢？不难发现，第一个问题中，有可能被一个生成的三角形包含的那个点只可能是一个凹点，若是凸点是不可能被包含的。第二个问题中也能看出，若生成的一个三角形不在多边形内部，那么你选取的那个点一定是个凹点，我们只要避免选取凹点作为切割点就可以避免这种情况。

现在就可以总结得出，切割凹多边形，选取切割点时，只要：

• 分割点生成的三角形不会包含住凹点

• 选取的分割点不是凹点

就可以了。

代码实现

这次我放伪代码算了，估计以后也是放伪代码了。感觉放实代码格局太小了，而且又难看懂，not friendly。

/**
 * 将多边形分割为多个小三角形
 * 作用：分割成多个小三角形后，对每个小三角形生成包围盒，在碰撞检测可以遍历小三角形，进行包围盒相交检测，
 * 可以过滤掉多边形没有发生碰撞的部分，大大提升性能
 */
function 分割(顶点集) {

    凹点集 = 寻找凹点(顶点集);

    while(true) {

        // 3个顶点才能构成一个三角形，小于3个顶点说明分割完毕，退出
        if(顶点集顶点数量 < 3) break;

        // 寻找切割点
        for(顶点 in 顶点集) {
            // 选取顶点
            当前三角形 = [上一个顶点, 当前顶点, 下一个顶点];

            // 若当前图形没有凹点（凸多边形）或若当前顶点不是凹点并且当前三角形不包含凹点，则取用
            if(没有凹点 || (当前顶点不是凹点 && 当前三角形不包含凹点)) {
                break;
            };
        }

        三角形集添加(当前三角形);

        // 在图形中移除一个分割点
        顶点集移除(当前顶点);
    }

    return 三角形集;
}

效果

另外

其实这里还要一些优化的地方我没提到，就是分割后的三角形，由于要进行分离轴测试，所以要获取三角形的所有轴。但是由于分割出来的三角形肯定有若干条边是在多边形内部的，在碰撞发生时，这些边根本不可能会被碰到，所以这些边的轴也可以不用计算。如图： 图中轴A，轴B，是有用的，要保留，而由于轴C对应边蕴含在多边形内部，所以轴C我们舍去不要。

这意味着什么呢？这意味着我们在进行分离轴测试三角形时，要测试的轴会变得很少，最好的情况下，只要测试一个轴就可以了（其余两个轴的边都在多边形内部，所以舍去了），这可以使分离轴测试的复杂度最优时可达到O(n)。这是很厉害的一种优化。我在我的代码中已经完成了具体的轴取舍算法，但是我在这篇文章没有包含，因为这样代码量太多了，而且核心内容还是多边形的分割。

[kunshen1]

受益匪浅

[onrefy]

想问下这里的凹点怎么找啊，之前的文章里只有凹凸边形状查找

[phenomLi]

想问下这里的凹点怎么找啊，之前的文章里只有凹凸边形状查找

可以利用叉乘，思路是遍历边，然后判断下一条边是否都在上一条边的同侧（凸多边形的性质），若发现一条在另一侧，那么这条边和这条边的上条边的公共定点就是凹点。