Как работает 3D-обнаружение столкновений / объектов?

Question

Как работает 3D-обнаружение столкновений / объектов?

Я всегда задавался этим вопросом. В такой игре как GTA где есть 10s тысяч объектов, как игра знает, как только вы находитесь на пакет здоровья?

не может быть прослушивателя событий для каждого объекта? Повторение тоже не очень хорошо? Мне просто интересно, как это на самом деле сделано.

834 6

algorithm data-structures 3d collision-detection

6 ответов:

Comments

Ничего не найдено.

charstar · Accepted Answer · 2009-12-26 12:42:56

на это нет ответа, но большие миры часто разделяются пространством, используя что-то вроде quadtree или KD-дерево который приносит время поиска для нахождения ближайших соседей ниже линейного времени( дробная мощность, или в худшем случае O(N^(2/3) ) для 3D-игры). Эти методы часто называют BSP для двоичного разбиения.

Что касается обнаружения столкновений, каждый объект также обычно имеет объем ограничивающий сетка (набор полигонов, образующих выпуклую оболочку), связанный с ним. Эти сильно упрощенные сетки (иногда просто куб) не рисуются, но используются при обнаружении столкновений. Самый элементарный метод заключается в создании плоскости, перпендикулярной линии, соединяющей средние точки каждого объекта с плоскостью, пересекающей линию в средней точке линии. Если ограничивающий объем объекта имеет точки по обе стороны от этой плоскости, это столкновение (только вы нужно проверить один из двух ограничивающих объемов против плоскости). Другой метод-это enhanced GJK расстояние. Если вы хотите учебник для погружения, проверьте Nehe Productions' OpenGL урок #30.

кстати, ограничительные Тома могут также использоваться для других оптимизаций, таких как то, что называется запросы окклюзии. Это процесс определения того, какие объекты находятся за другими объектами (окклюдеры) и поэтому не делают необходимо обработать / визуализировать. Ограничительные объемы также могут быть использованы для усеченного выбраковки это процесс определения того, какие объекты находятся за пределами объема перспективного просмотра (слишком близко, слишком далеко или за пределами вашего угла поля зрения) и поэтому не нуждаются в визуализации.

Как отметил Kylotan, использование ограничивающего объема может генерировать ложные срабатывания при обнаружении окклюзии и просто не работает вообще для некоторых типов объектов, таких как тороиды (например, глядя через отверстие в пончике). Имея такие объекты, как эти затеняют правильно-это совсем другая резьба на .

joshperry · Accepted Answer · 2012-12-31 22:53:36

Quadtrees и Octrees,еще одно дерево, являются популярными способами, используя разделение пространства, чтобы достичь этого. Более поздний пример показывает 97%-ное сокращение обработки по парному перебору грубой силы для столкновений.

celion · Accepted Answer · 2009-12-25 18:50:18

распространенным методом в игровых физических движках является метод развертки и обрезки. Это объясняется в Дэвид Baraff-х (см. главу движение с ограничениями). Havok определенно использует это, я думаю, что это вариант в пуле, но я не уверен в PhysX.

идея заключается в том, что вы можете посмотреть на перекрытия AABBs (осевые ограничительные рамки) на каждой оси; если проекция двух объектов aabbs перекрывается на всех трех осях, то AABBs должны перекрываться. Вы можно проверить каждую ось относительно быстро, сортируя начальные и конечные точки AABBs; существует много временной когерентности между кадрами, так как обычно большинство объектов не перемещаются очень быстро, поэтому сортировка не сильно меняется.

после зачистки и чернослив обнаруживает совпадение между AABBs, вы можете сделать более детальную проверку объектов, например, шар и коробка. Если детальная проверка обнаруживает столкновение, вы можете устранить столкновение, применив силы, и/или вызвать игровое событие или воспроизвести звуковой эффект.

kingchris · Accepted Answer · 2017-05-23 15:02:02

правильно. Обычно для каждого объекта нет прослушивателя событий. Часто существует недвоичная древовидная структура в памяти, которая имитирует вашу карту игр. Представьте себе карту метро / метро. Эта структура памяти представляет собой набор вещей в игре. Вы игрок, монстры и предметы, которые вы можете забрать или предметы, которые могут взорваться и причинить вам вред. Так как игрок перемещается по игре, указатель объекта игрока перемещается в структуре памяти игры/карты.

посмотреть как следует У меня есть свои игровые сущности, знающие о вещах вокруг них?

wojakzek · Accepted Answer · 2010-12-21 23:11:50

Я хотел бы рекомендовать твердую книгу Кристера Эриксона по обнаружению столкновений в реальном времени. В нем представлены основы обнаружения столкновений при предоставлении ссылок на современные исследования.

обнаружение столкновений в реальном времени (серия Моргана Кауфмана в интерактивной 3-D технологии)

user224564 · Accepted Answer · 2014-04-30 02:42:44

есть много оптимизаций могут быть использованы. Во-первых - любой объект (скажем, с индексом i, например) омывается куба с координатами центра CXi,CYi и в размере Si Во-вторых - обнаружение столкновений работает с оценками:

a) найти все пары кубов i, j с условием:Abs(CXi-CXj)<(Si+Sj) AND Abs(CYi-CYj)<(Si+Sj)

б) теперь мы работаем только с парами попавшими в а). Рассчитаем расстояния между ними более точно, что-то вроде Sqrt(Sqr(CXi-CXj)+Sqr(CYi-CYj)) объекты теперь представлены в виде наборов из нескольких чисел простых фигур-кубов, сфер, конусов-и мы с помощью геометрических формул проверяем пересечения этих фигур.

C) объекты из б) с обнаруженными пересечениями обрабатываются как столкновения с вычислением физики и т. д.