Обнаружение столкновений с использованием сомнений AABB или OBB

Насколько мне известно, большая часть физического движка использует алгоритм AABB + развертки и обрезки для широкой фазы обнаружения столкновений. Деревья практически бесполезны для обнаружения столкновений между динамическими объектами. Однако деревья можно с успехом использовать для статической геометрии.

Проблема с de AABB заключается в том, что объекты должны быть выровнены по осям, иначе вам придется пересчитывать bbox каждый кадр, верно?

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

В целом, пересчет AABB лучше, чем дорогие узкофазные алгоритмы.

Выбор между AABB, OBB, сферами, капсулами... зависит от типа моделирования, которое вы используете, и ваших ограничений (обычно приложений реального времени).

Нужно взвесить все за и против и сделать свой выбор соответственно. Например, тесты с AABB очень быстрые, но вам нужно пересчитывать AABB, когда ваш объект вращается. Однако, если вы работаете с очень сложными объектами и имеете дело с BVH, обновление AABB-дерева довольно сложно. быстро, поскольку вам нужно только пересчитать («с нуля») нижние AABB, а более высокие строятся из дочерних AABB. С OBB тесты обходятся дороже, но вам не нужно будет пересчитывать свои OBB, если вы имеете дело с жесткими объектами.

Если вы решите использовать деформируемые объекты, дерево AABB (или дерево сфер), безусловно, будет лучшей идеей, так как ваше дерево в любом случае нужно будет обновить.

Вопрос в том, что будет дороже: накладные расходы, связанные с обновлением дерева AABB или с тестами наложения с OBB? Все это зависит от ваших симуляций: сложности объектов, среднего количества тестов CD в секунду и т. д. Вы можете найти несколько тестов различных библиотек CD, основанных на разных методах (BVH, сетки...) с различными формами, протестированных на конкретных задачах. Вот пример, который может показаться вам интересным.

Что касается реализации, поскольку все это исследовано много лет назад и реализовано во многих библиотеках, у вас не должно возникнуть никаких проблем. Вы можете взглянуть на Обнаружение столкновений в реальном времени Кристера Эриксона, на все эти вопросы даны ответы и объяснения очень четкие.

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