Почему я должен использовать AABB для столкновения круг-круг

В моей игре wip я должен реализовать столкновения Круг-Круг. Чтобы реализовать это, я просто вычисляю квадратное расстояние между их центрами. (x1-x2)² + (y1-y2)², Если это меньше, то их квадратные радиусы (r1+r2)² произошло столкновение. Но сегодня я увидел эту ссылку: столкновение Круг-Круг

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

Позволь мне объяснить:

Я делаю обнаружение столкновений AABB для каждого круга с каждым другим. Так что я должен сделать n! / (n-2)! расчеты. n = количество кругов для проверки. Для каждой пары коллизии AABB я должен сделать еще один расчет, если они действительно сталкиваются.

Без обнаружения столкновения AABB я только делаю n! / (n-2)! расчеты, и я не думаю, что эти расчеты так дорого. Как вы думаете?

Источник

2 ответа

Решение

Этот комментарий является правильным ответом. Это зависит от вашего оборудования и компилятора. Если вы сначала используете обнаружение AABB, у вас есть 8 операций добавления + 4 сравнения. Если вы сравниваете квадратное расстояние и квадратные радиусы, вы делаете 6 сложение / вычитание + 3, умножение + 1 сравнение. Возможно, ваше оборудование и компилятор быстрее сравниваются, чем умножаются. Но это не должно быть большой разницей в производительности. Если вы вместо сравнения квадратов используете квадратные корни (по какой-либо причине), вы должны выполнить сравнение AABB по сравнению с первопричиной, для вычисления квадратного корня потребуется некоторое время. Есть также лучшие решения, как в этом ответе. Если вам нужно сделать много обнаружений между многими объектами, вы можете подумать об одном из этих решений.

Источник

Я думаю, что вот способ, которым вы можете сделать это в O (NlogN) в среднем случае, но O(N^2) в худшем: -

  1. Рассмотрим каждый круг как прямоугольник 2R*2R с центром в центре круга.

  2. Используйте алгоритм строчной линии для прямоугольников, который равен O(NlogN + R), где число пересечений.

  3. Пересекающиеся пары прямоугольников могут быть проверены как круги для пересечения, используя ваш алгоритм в O(R^2).

Примечание: если R мало, то это O (NlogN), но если R = O(N), то это O(N^2)

Источник
Другие вопросы по тегам