В настоящее время я занимаюсь разработкой клона прорыва и столкнулся с препятствиями на пути обнаружения столкновения между шаром (круг) и кирпичом (выпуклый многоугольник), работающим правильно. Я использую тест обнаружения столкновения 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;
}
источник
sqrt_disc = sqrt(disc);
обратно. Большое спасибо за ответ ниже, он мне очень помог.Ответы:
Сегмент, идущий от А до В, может быть вычислен как
P (t) = A + D · t, где D - B - A, а t проходит от 0 до 1
Теперь круг центрируется на начале координат (переместите A и B, если необходимо, чтобы поместить центр в начало координат), и имеет радиус r .
У вас есть пересечение, если для некоторого t вы получите, что P имеет ту же длину r или, что эквивалентно, что длина P в квадрате эквивалентна r²
Квадрат длины вектора получается при помощи точечного произведения вектора (это так верно, что если человек найдет подходящую операцию для точечного произведения, он может определить новое и непротиворечивое понятие длины)
P · P = ( A + D · t) · ( A + D · t) =
A · A + 2 A · D t + D · D t²
Мы хотим выяснить, для какого 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
источник