Обнаружение столкновений: Теорема о разделяющей оси - круг против многоугольника

Question

Я пытался реализовать обнаружение столкновений между кругами и полигонами на основе 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)
• И у вас есть сравнение неправильным способом, вы должны проверять, если радиус меньше квадрата (не больше)
• Затем, когда вы обнаружите вершину в радиусе, вы вернете объект данных, но забудете поместить вершину, найденную внутри круга, на data.contacts массив.
• Я не уверен, каково намерение сохранить индекс самого дальнего вектора, но тогда остальные функции для меня не имеют смысла????:(и я попытался это понять.

Все, что вам нужно сделать, это

Проверка, если какие-либо вершины в поли ближе, чем радиус, если это так, то у вас есть перехват (или полностью внутри)

Затем вам нужно проверить расстояние каждого отрезка

Может быть сделано для каждого отрезка линии следующим образом, если вам не нужны перехваты (или ниже, если вам нужны перехваты), используйте только одну или другую.

// 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;
    }

Я оставлю это на ваше усмотрение, чтобы сделать итерацию многоугольника.