Проблема обнаружения столкновения по окружности

11

В настоящее время я занимаюсь разработкой клона прорыва и столкнулся с препятствиями на пути обнаружения столкновения между шаром (круг) и кирпичом (выпуклый многоугольник), работающим правильно. Я использую тест обнаружения столкновения Circle-Line, где каждая линия представляет и край на кирпиче выпуклого многоугольника.

Большую часть времени тест Circle-Line работает должным образом, а точки столкновения определяются правильно.

Обнаружение столкновения работает правильно.

Однако, иногда мой код обнаружения столкновений возвращает false из-за отрицательного дискриминанта, когда мяч фактически пересекает кирпич.

Обнаружение столкновения не удалось.

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

/* 
 * from and to are points at the start and end of the convex polygons edge.
 * This function is called for every edge in the convex polygon until a
 * collision is detected. 
 */

bool circleLineCollision(Vec2f from, Vec2f to)
{
    Vec2f lFrom, lTo, lLine;
    Vec2f line, normal;
    Vec2f intersectPt1, intersectPt2;
    float a, b, c, disc, sqrt_disc, u, v, nn, vn;
    bool one = false, two = false;

    // set line vectors
    lFrom = from - ball.circle.centre;      // localised
    lTo = to - ball.circle.centre;          // localised
    lLine = lFrom - lTo;                    // localised
    line = from - to;

    // calculate a, b & c values
    a = lLine.dot(lLine);
    b = 2 * (lLine.dot(lFrom));
    c = (lFrom.dot(lFrom)) - (ball.circle.radius * ball.circle.radius);

    // discriminant
    disc = (b * b) - (4 * a * c);

    if (disc < 0.0f)
    {
        // no intersections
        return false;
    }
    else if (disc == 0.0f)
    {
        // one intersection
        u = -b / (2 * a);

        intersectPt1 = from + (lLine.scale(u));
        one = pointOnLine(intersectPt1, from, to);

        if (!one)
            return false;
        return true;
    }
    else
    {
        // two intersections
        sqrt_disc = sqrt(disc);
        u = (-b + sqrt_disc) / (2 * a);
        v = (-b - sqrt_disc) / (2 * a);
        intersectPt1 = from + (lLine.scale(u));
        intersectPt2 = from + (lLine.scale(v));

        one = pointOnLine(intersectPt1, from, to);
        two = pointOnLine(intersectPt2, from, to);

        if (!one && !two)
            return false;
        return true;
    }
}

bool pointOnLine(Vec2f p, Vec2f from, Vec2f to)
{
    if (p.x >= min(from.x, to.x) && p.x <= max(from.x, to.x) && 
        p.y >= min(from.y, to.y) && p.y <= max(from.y, to.y))
        return true;
    return false;
}
jazzdawg
источник
Я не могу найти никакой разницы между линией и линией ...
FxIII
Тест pointOnLine можно упростить и выполнить до вычисления фактической точки.
FxIII
как рассчитывается sqrt_disc?
FxIII
Извините, FxIII Я, должно быть, немного запутался, когда я локализовал свои векторы, я не понимал, что векторы будут одинаковыми, если их вычитать друг из друга. Я немного очистил свой код перед тем, как опубликовать статью, и забыл вставить sqrt_disc = sqrt(disc);обратно. Большое спасибо за ответ ниже, он мне очень помог.
Jazzdawg

Ответы:

20

Сегмент, идущий от А до В, может быть вычислен как

P (t) = A + D · t, где D - B - A, а t проходит от 0 до 1

Теперь круг центрируется на начале координат (переместите A и B, если необходимо, чтобы поместить центр в начало координат), и имеет радиус r .

У вас есть пересечение, если для некоторого t вы получите, что P имеет ту же длину r или, что эквивалентно, что длина P в квадрате эквивалентна

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

P · P = ( A + D · t) · ( A + D · t) =

A · A + 2 A · D t + D · D

Мы хотим выяснить, для какого t мы получаем P · P = r², поэтому мы задаемся вопросом, когда

A · A + 2 A · D t + D · D t² = r²

или когда

D · D t² + 2 A · D t + A · A -r² = 0

это очень известное квадратное уравнение

at² + bt + c = 0

с

a = D · D ; b = 2 A · D и c = A · A -r²

Мы должны проверить, положителен ли определитель b² - 4ac, и поэтому мы находим 2 значения t, которые дают нам точки пересечения P (t).

t должно быть между 0 и 1, в противном случае мы нашли решения, которые лежат на прямой, проходящей через A и B, но до A или после B

[РЕДАКТИРОВАТЬ]

Поскольку другие вопросы могут найти некоторую помощь в этом ответе, я решил попытаться упростить рассуждения в этом редактировании, используя некоторые изображения. исходное состояние Это начальное условие. Теперь сосредоточимся на сегменте A_B

Сегмент, идущий от А до Б

D - это вектор, который перемещает A в B, поэтому, если t находится между 0 и 1, D · t является «правильной дробью» D, поэтому точка A + D · t лежит в сегменте A_B : коричневые точки появляются, когда t между 0 и 1, а темно-зеленый - при t> 1.

Теперь мы можем упростить вещи, если переместим центр круга в начало координат. Это всегда можно сделать, потому что это просто изменение системы координат, которая сохраняет геометрию, углы, пересечение, меры и т. Д.

круг движется к центру

Теперь у нас есть простой способ вычислить длину P, когда t изменяется, и сказать, для чего t P пересекает границы круга.

Примеры

Как вы видите, длина P ' больше r, а P " меньше r. Поскольку длина вектора и r являются положительными числами, отношение порядка быть больше или меньше, чем сохраняется, вычисляем соотношение между длинами квадрат и радиус в квадрате. P * 1 и P * 2 - это точка, которая делает | P | ² равным r²

Как уже упоминалось в разделе перед редактированием, мы получаем квадратное уравнение, где t - наша переменная. Как известно, значения решения t варьируются от случая, когда t является парой комплексных чисел - это означает отсутствие пересечения; случай, когда t имеют два равных решения - это означает, что существует одно пересечение; случай, когда есть два различных решения - это означает, что есть два пересечения.

Дискриминантный используется для различения предыдущее состояние и проверка валидность делается на т , чтобы увидеть , если это действительное пересечение , но вне нашего сегмента - то есть решение т должно быть реальным и между 0 и 1 , следует считать правильное пересечение , что падение в сегменте A_B

FXIII
источник
3
Это правильный алгоритм для использования. Действительно хорошее описание того, как это работает, можно найти в Real Time Rendering Third Edition , стр. 787–791. Если вы можете найти его в библиотеке, стоит посмотреть.
Дарси Рейнер
4
С 8-м ответом на этот ответ я набрал 2k очков репутации. Я очень ценю доверие, которое вы мне оказали. Это и признание моих усилий, и стимул продолжать прилагать все усилия для получения максимально качественного ответа. Спасибо
FxIII
Подожди, правильно ли это учитывает два угловых случая? Например, окружность может пересекать плоскость, определяемую линией вне t0 <= t <= t1, но немного дотягивать до конечных точек отрезка. Вам необходимо проверить минимальное расстояние между конечными точками линии и окружностью. Если это расстояние меньше радиуса окружности, то линия была достигнута.
Дарси Рейнер
@DarcyRayner Вы имеете в виду случай, когда обе точки находятся внутри области круга?
FxIII