正文
多边形碰撞 -- SAT方法
提示：扫一扫查出行【扫一扫了解最新限行尾号】
复制提示
检测凸多边形碰撞的一种简单的方法是SAT（Separating Axis Theorem），即分离轴定理。
原理：将多边形投影到一条向量上，看这两个多边形的投影是否重叠。如果不重叠，则认为这两个多边形是分离的，否则找下一条向量来继续投影。我们不需要比较很多条向量，因为已经在数学上证明，多边形每条边的垂直向量就是我们需要的向量。
1.AABB
让我们首先以AABB开始（AABB是一种两边分别平行于X-Y轴的矩形）
判断两个AABB是否碰撞，我们只需要投影两次，分别是投影在平行于X轴和Y轴的向量上
由上图可以看见，因为在Y轴方向的投影是分离的，因此可以直接得出结论，即这两个AABB是分离的。
function AABBvsAABB(aabb1, aabb2) {
//check X axis
if(aabb1.xMin > aabb2.xMax)
return false;
if(aabb1.xMax < aabb2.xMin)
return false;
//check Y axis
if(aabb1.yMin > aabb2.yMax)
return false;
if(aabb1.yMax < aabb2.yMin)
return false; return true;
}
效果：---点击运行---
（点击产生AABB，碰撞的变红，否则变黄）
2.圆
圆的碰撞检测也能用SAT，就是要把两个圆投影在两个圆心连线的向量上。比较半径和与圆心距离，如果半径和大于圆心距离则碰撞。
代码：
注：通常为了优化，都是用平方而不是开方（sqrt好慢的）
function CircleVsCircle(c1, c2) {
var xSqr = c1.centerX - c2.centerX;
xSqr *= xSqr;
var ySqr = c1.centerY - c2.centerY;
ySqr *= ySqr;
//get the distance^2
var distanceSqr = xSqr + ySqr; var radiusSum = c1.radius + c2.radius; if(distanceSqr <= radiusSum*radiusSum)
return true;
else
return false;
}
效果：---点击运行---
（点击产生圆）
3.多边形
（1）找出两个多边形所有边的垂直向量；
（2）将两个多边形投影到垂直向量上，判断投影是否相交，如果不相交则两个多边形不相交，否则选下一条垂直向量继续进行投影判断。
代码：
function PolyVsPoly(p1, p2) {
//check the normal in p1
for(var i = 0; i < p1.points.length-1; i++) {
var edge = Minus(p1.points[i], p1.points[i+1]);
var normal = Normal(edge); var isOverlap = CheckCollide(normal, p1, p2);
if(!isOverlap)
return false;
} //check normal in p2
for(var i = 0; i < p2.points.length-1; i++) {
var edge = Minus(p2.points[i], p2.points[i+1]);
var normal = Normal(edge); var isOverlap = CheckCollide(normal, p1, p2);
if(!isOverlap)
return false;
} return true;
}function CheckCollide(axis, p1, p2) {
var min1 = Dot(p1.points[0], axis);
var max1 = Dot(p1.points[0], axis);
for(var k = 1; k < p1.points.length; k++) {
var v = Dot(p1.points[k], axis);
if(v > max1)
max1 = v;
if(v < min1)
min1 = v;
} var min2 = Dot(p2.points[0], axis);
var max2 = Dot(p2.points[0], axis);
for(var k = 1; k < p2.points.length; k++) {
var v = Dot(p2.points[k], axis);
if(v > max2)
max2 = v;
if(v < min2)
min2 = v;
} if(!IsOverlap(min1, max1, min2, max2))
return false; return true;
}
效果：---点击运行---
（使用方向键来移动，碰撞的变红，否则变黄）
4.圆与多边形
（1）找出多边形每条边的垂直向量，多边形最接近圆心的点到圆形的直线的垂直向量
（2）将圆和多边形投影到垂直向量上，再进行判断。
（其实和多边形之间的碰撞很像，这里就不浪费篇幅了）
总结：
SAT很简单，就是投影 + 重叠判断。
SAT只适用于凸体，毕竟凹体中间空缺的部分在投影后信息就消失了。
一些关于SAT的网站：
http://gamedevelopment.tutsplus.com/tutorials/collision-detection-with-the-separating-axis-theorem--gamedev-169
