Как делает 3D коллизию / работа обнаружения объектов?
I'v всегда задавался вопросом это. В игре как GTA, где существуют 10-е тысяч объектов, как игра знает, как только Вы находитесь на медицинском пакете?
Не может возможно быть слушателя события для каждого объекта? Итерация не хороша также? Я просто задаюсь вопросом, как это на самом деле сделано.
5 ответов
На это нет ответа, но большие миры часто разделены пространством, используя что-то по линиям квадтрия или кд-дерева , что приносит время поиска ближайших соседей ниже линейного времени (дробная мощность, или в худшем случае O( N^(2/3)) для 3D-игры). Эти методы часто называют BSP для разбиения двоичного пространства.
Что касается обнаружения столкновений, каждый объект также обычно имеет ограничивающий объем сетку (набор полигонов, образующих выпуклый корпус), связанную с ним. Эти сильно упрощенные сетки (иногда просто куб) не рисуются, а используются при обнаружении столкновений. Наиболее простым методом является создание плоскости, перпендикулярной линии, соединяющей средние точки каждого объекта с плоскостью, пересекающей линию в средней точке линии. Если ограничивающий объем объекта имеет точки по обеим сторонам этой плоскости, то это является столкновением (достаточно протестировать один из двух ограничивающих томов против плоскости). Другим методом является расширенный алгоритм определения расстояния GJK. Если вам нужен учебник для погружения, Посмотрите NeHe Productions' OpenGL урок #30.
Кстати, ограничительные тома могут быть использованы и для других оптимизаций, таких как то, что называется окклюзионные запросы . Это процесс определения того, какие объекты находятся за другими объектами (окклюдерами) и, следовательно, не нуждаются в обработке/отображении. Ограничение объема также может быть использовано для отбраковки , которая является процессом определения того, какие объекты находятся вне перспективного объема просмотра (слишком близко, слишком далеко, или за пределами угла зрения) и, следовательно, не нуждаются в отрисовке.
Как отметил Кюлотан, использование ограничивающего объема может генерировать ложные срабатывания при обнаружении окклюзии и просто не работает вообще для некоторых типов объектов, таких как тороиды (например, просмотр отверстия в пончике). Правильно иметь такие объекты, как окклюзия, - это совсем другой поток на портале-объёме .
.Распространенным методом в движках игровой физики является метод развертки и отсечения. Это объясняется в примечаниях Дэвида Барафа к SIGGRAPH (см. Главу «Движение с ограничениями»). Havok определенно использует это, я думаю, что это опция в Bullet, но я не уверен насчет PhysX.
Идея состоит в том, что вы можете смотреть на перекрытия AABB (ограничивающих прямоугольников, выровненных по оси) на каждой оси; если проекция AABB двух объектов перекрывается на всех трех осях, то AABB должны перекрываться. Вы можете относительно быстро проверить каждую ось, отсортировав начальную и конечную точки AABB; между кадрами существует большая временная согласованность, поскольку обычно большинство объектов движутся не очень быстро, поэтому сортировка не сильно меняется.
Как только функция sweep-and-prune обнаруживает перекрытие между AABB, вы можете выполнить более детальную проверку объектов, например, сфера или коробка. Если детальная проверка выявляет столкновение, вы можете разрешить столкновение, применив силы, и / или вызвать игровое событие или воспроизвести звуковой эффект.
Можно использовать множество оптимизаций.
Во-первых - любой объект (например, с индексом i) ограничен кубом, с координатами центра CXi,CYi, и размером Si.
Во-вторых - обнаружение столкновений работает с оценками:
a) Найти все пары кубов i,j с условием: Abs(CXi-CXj)<(Si+Sj) AND Abs(CYi-CYj)<(Si+Sj)
b) Теперь мы работаем только с парами, попавшими в a). Мы более точно вычисляем расстояния между ними, что-то вроде Sqrt(Sqr(CXi-CXj)+Sqr(CYi-CYj)), объекты теперь представлены в виде наборов нескольких чисел простых фигур - кубов, сфер, конусов - и используем формулы геометрии для проверки пересечений этих фигур.
c) Объекты из b) с обнаруженными пересечениями обрабатываются как коллизии с вычислениями по физике и т.д.
.Correct. Обычно для каждого объекта нет слушателя событий. Часто в памяти имеется небинарная древовидная структура, имитирующая вашу карту игр. Представьте себе карту метро/подземки. Эта структура памяти представляет собой набор вещей в игре. Вы - игрок, монстры и предметы, которые вы можете подобрать, или предметы, которые могут взорваться и причинить вам вред. Так что по мере перемещения игрока по игре указатель объекта перемещается в структуре памяти игры/карты.
смотрите Как я должен знать свои игровые объекты о вещах, которые их окружают?
Четырехугольники и осьминоги , еще одно четырёхугольник - популярные способы, использующие пространственное разбиение для этого. Более поздний пример показывает уменьшение на 97% обработки при поиске коллизий методом перебора по паре
.