碰撞检测:分离轴定理-圆与多边形

Question

我一直在尝试基于Randy Gaul的C++Impulse Engine实现圆和多边形之间的碰撞检测，并严格遵循代码，但算法从未返回true。

这是JSFiddle。(为了方便起见，使用HTML5 Canvas API渲染身体)

代码片段(只是冲突检测)：

const circPoly = (a, b) => {
let data = {},
center = a.pos;
data.contacts = [];
center = b.mat.clone().trans().mult(center.clone().sub(b.pos));
let sep = -Number.MAX_VALUE,
faceNorm = 0;
for (let i = 0; i < b.verts2.length; ++i) {
let sep2 = b.norms[i].dot(center.clone().sub(b.verts2[i]));
if (sep2 > a.radius) return data;
if (sep2 > sep) { sep = sep2; faceNorm = i; }
}
let v1 = b.verts2[faceNorm],
v2 = b.verts2[faceNorm + 1 < b.verts2.length ? faceNorm + 1 : 0];
if (sep < 0.0001) {
data.depth = a.radius;
data.norm = b.mat.clone().mult(b.norms[faceNorm]).neg();
data.contacts[0] = data.norm.clone().vmult(a.pos.clone().sadd(a.radius));
return data;
}
let dot1 = center.clone().sub(v1).dot(v2.clone().sub(v1)),
dot2 = center.clone().sub(v2).dot(v1.clone().sub(v2));
data.depth = a.radius - sep;
if (dot1 <= 0) {
if (center.dist2(v1) > a.radius * a.radius) return data;
let norm = v1.clone().sub(center);
norm = b.mat.clone().mult(norm);
norm.norm();
data.norm = norm;
v1 = b.mat.clone().mult(v1.clone().add(b.pos));
data.contacts[0] = v1;
} else if (dot2 <= 0) {
if (center.dist2(v2) > a.radius * a.radius) return data;
let norm = v2.clone().sub(center);
norm = b.mat.clone().mult(norm);
norm.norm();
data.norm = norm;
v2 = b.mat.clone().mult(v2.clone().add(b.pos));
data.contacts[0] = v2;
} else {
let norm = b.norms[faceNorm];
if (center.clone().sub(v1).dot(norm) > a.radius) return data;
norm = b.mat.clone().mult(norm);
data.norm = norm.clone().neg();
data.contacts[0] = data.norm.clone().vmult(a.pos.clone().sadd(a.radius));
}
return data;
};

注意，b.verts2是指现实世界坐标中多边形的顶点。

我知道Vector类没有问题，但由于我对变换矩阵没有太多经验，该类可能是这些错误的根源，尽管它的代码几乎完全来自脉冲引擎，所以它应该可以工作。如前所述，即使确实发生了碰撞，算法也总是返回false。我在这里做错了什么？我试着去掉早期的返回，但这只是返回了奇怪的结果，比如负坐标的接触点，这显然不太正确。

编辑：修改了向量类的垂直函数，使其以与脉冲引擎相同的方式工作(两种方式都是正确的，但我认为一种是顺时针方向，另一种是逆时针方向——我还修改了顶点，以反映逆时针方向)。不幸的是，它仍然没有通过测试。

https://jsfiddle.net/khanfused/tv359kgL/4/

Answer 1

有很多问题，我真的不明白你想做什么，因为它看起来太复杂了。为什么矩阵有trans？？？为什么要用Y向上屏幕作为变换的坐标系？？？(修辞)

在第一个循环中。

• 第一个是测试法向量的距离每个垂直的，应该测试垂直的位置
• 此外，您还可以使用vec.dot函数来查找距离返回距离的平方。但你测试半径，你应该测试if(sep2 < radius * radius)
• 你的比较方式不对如果小于半径平方(不大于)，则进行测试
• 然后，当你在半径内检测到垂直时，你会返回数据物体，但忘记把在圆圈内找到的vert放上去CCD_ 5阵列
• 我不知道保持指数最多的意图是什么距离vect为，但函数的其余部分对我？？？：(我试着去理解它

您所需要做的就是

检查poly上是否有任何vert比半径更近，如果是这样，则您有一个拦截(或完全在内)

然后你需要检查每个线段的距离

如果你不需要截距(或者如果你需要截距，则可以使用下面的截距)，可以为每个线段使用一个或另一个。

// circle is a point {x:?,y:?}
// radius = is the you know what
// p1,p2 are the start and end points of a line
checkLineCircle = function(circle,radius,p1,p2){
var v1 = {};
var v2 = {};
var v3 = {};
var u;
// get dist to end of line
v2.x = circle.x - p1.x;
v2.y = circle.y - p1.y;
// check if end points are inside the circle
if( Math.min(
Math.hypot(p2.x - circle.x, p2.y - circle.y),
Math.hypot(v2.x, v2.y)
) <= radius){
return true;
}
// get the line as a vector
v1.x = p2.x - p1.x;
v1.y = p2.y - p1.y;
// get the unit distance of the closest point on the line
u = (v2.x * v1.x + v2.y * v1.y)/(v1.y * v1.y + v1.x * v1.x);
// is this on the line segment
if(u >= 0 && u <= 1){
v3.x = v1.x * u;  // get the point on the line segment
v3.y = v1.y * u;
// get the distance to that point and return true or false depending on the 
// it being inside the circle
return (Math.hypot(v3.y - v2.y, v3.x - v2.x) <= radius);
}
return false; // no intercept
}

对每一行都这样做。为了节省时间，请将圆心变换为多边形局部，而不是变换多边形上的每个点。

如果您需要拦截点，请使用以下功能

// p1,p2 are the start and end points of a line
// returns an array empty if no points found or one or two points depending on the number of intercepts found
// If two points found the first point in the array is the point closest to the line start (p1)
function circleLineIntercept(circle,radius,p1,p2){
var v1 = {};
var v2 = {};
var ret = [];
var u1,u2,b,c,d;
// line as vector
v1.x = p2.x - p1.x;
v1.y = p2.y - p1.y;
// vector to circle center
v2.x = p1.x - circle.x;
v2.y = p1.y - circle.y;
// dot of line and circle
b = (v1.x * v2.x + v1.y * v2.y) * -2;
// length of line squared * 2
c = 2 * (v1.x * v1.x + v1.y * v1.y);
// some math to solve the two triangles made by the intercept points, the circle center and the perpendicular line to the line.
d = Math.sqrt(b * b - 2 * c * (v2.x * v2.x + v2.y * v2.y - radius * radius));
// will give a NaN if no solution
if(isNaN(d)){ // no intercept
return ret;
}
// get the unit distance of each intercept to the line
u1 = (b - d) / c;
u2 = (b + d) / c;
// check the intercept is on the line segment
if(u1 <= 1 && u1 >= 0){  
ret.push({x:line.p1.x + v1.x * u1, y : line.p1.y + v1.y * u1 });
}
// check the intercept is on the line segment
if(u2 <= 1 && u2 >= 0){  
ret.push({x:line.p1.x + v1.x * u2, y : line.p1.y + v1.y * u2});
}
return ret;
}

我将让你来做多边形迭代。