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

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

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

Поясню:

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

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

источник

2014-01-15 Springrbua

Как правило, только несколько кругов действительно близко друг к другу. Итак, да, вам понадобятся «n (n-1)» проверки AABB (см. Это 'n!/(N-2)! = N (n-1)'?), Но обычно это всего лишь несколько проверок столкновения. Скажем, AABB является лишь фактором 2 дешевле (это, вероятно, больше), то это ускорение для небольшого 'n' уже. –

Оглядываясь назад, глядя на ссылку, которую вы предоставили, я думаю, что вы действительно правы, что сравнение квадратов не дороже сравнения AABB. У вас будет только ускорение, если вы проверите AABB вместо вычисления квадратных корней, потому что это требует много времени.Я думаю, что ваш метод прекрасен без проверки AABB (может быть еще быстрее: 6 add/subtract + 3 multiply + 1 compare vs 8 add + 4 compare; зависит от вашего компилятора + оборудования, что будет лучше, я бы назвал его галстуком ;-)). –

Итак, AABB полезен, если ваш жесткий диск и/или компилятор быстрее с дополнениями, а затем с умножениями? И если вы используете квадратные корни, которые вам не нужны для кругового столкновения (но многие люди используют их: P). Спасибо за этот быстрый ответ. Можете ли вы опубликовать его в качестве ответа, чтобы я мог отметить его как решение и проголосовать за вас? Спасибо – Springrbua

This comment является правильным ответ. Это зависит от вашего оборудования и компилятора. Если вы сначала используете обнаружение AABB, у вас есть 8 операций добавления + 4 сравнения. Если сравнить квадратное расстояние и квадратные радиусы, вы делаете 6 add/subtract + 3 multiply + 1 compare. Возможно, ваше оборудование и компилятор быстрее сравниваются с умножениями. Но это не должно быть большой разницей в производительности. Если вместо сравнения квадратов использовать квадратные корни (по какой бы то ни было причине), вы должны сделать сравнение AABB, чтобы вычислять квадратные корневые причины, требующие некоторого времени. Есть ofc также лучшие решения, такие как in this answer. Если вам нужно сделать много обнаружений между многими объектами, вы можете подумать об одном из этих решений.

источник

2014-01-20 08:52:05 Springrbua

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

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

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

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

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

источник

2014-01-15 11:05:09

Но в этом случае я всегда должен проверить для n (n-1) круговые круговые итерации. Если я использую AABB, я должен проверить для n (n-1) AABB-пересечения И затем для каждого пересечения AABB другое пересечение круга. Так что у меня нет преимущества при использовании AABB? – Springrbua

Существует алгоритм O (NlogN) для линии развертки с использованием деревьев двоичного поиска, которые найдут прямоугольники, которые пересекаются, затем используют парное пересечение каждого круга в прямоугольнике для получения ответа. Это худший случай O (N^2), тогда как в среднем случае O (NlogN) –

А это еще один алгоритм для обнаружения, если могут столкнуться 2 объекта. Да, это было бы более эффективно, но я не очень нуждаюсь в этом. Я просто задавался вопросом, менее ли «сопоставление квадратного расстояния с квадратными радиусами» менее эффективно, чем «столкновение AABB» и, если необходимо, «сравнение квадратного расстояния с квадратными радиусами». Но я запомню этот метод и, возможно, мне понадобится его в один прекрасный день (: – Springrbua

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

ответ

Смежные вопросы