Как работают коллизионные сетки в таких играх, как Zelda на N64?

Недавно я читал о технологии Ocarina of Time /Majoras Mask и обнаружил, что мировое столкновение выполняется с использованием единственной треугольной сетки (вершин, нормалей и т. д.) для всей области. В этой структуре данных также нет признаков предварительно обработанных методов пространственного разбиения.

Какие существуют алгоритмы для выполнения коллизии символов на аналогичной произвольной треугольной сетке, достаточно быстро выполняющейся на платформе, например, N64?

Quake - это современная игра с аналогичной функцией, которая пришла на ум. Я понимаю, что столкновения кик-китов работают, разбивая AABB на плоскости. Если точка находится в AABB, а за всеми плоскостями происходит столкновение. Однако этот метод работает только с использованием кучи отдельных выпуклых объектов для создания сцены столкновения.

Подробности структуры данных Zelda Здесь:

http://wiki.spinout182.com/w/Zelda_64:_Collision_Format http://zeldaspeedruns.com/oot/generalknowledge/zelda-64-engine

EDIT . Мне не нужно знать реальный метод, используемый реальной игрой, примером является Zelda. Я ищу способ достижения аналогичного эффекта при аналогичных аппаратных ограничениях.

5 голосов | спросил Justin Meiners 2 PM000000100000000531 2013, 22:57:05

2 ответа


3

Принимая совет tigoru. Вместо этого я искал, как техника выполняется в Марио 64. (Двигатель Зелды является прямой производной).

Я обнаружил, что этот документ упоминался в обсуждениях Марио 64 несколько раз.

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

  

Алгоритм, представленный в этой статье, предназначен для обнаружения столкновения   против произвольных сеток, хранящихся в виде так называемого многоугольного супа. Когда   обнаружен столкновение, алгоритм будет скользить движущимся объектом вдоль   препятствия, как это обычно наблюдается в 3d компьютерных играх. Перемещение   сущность аппроксимируется эллипсоидом, который дает довольно плотную   подходит для большинства гуманоидных или животных форм.

Алгоритм также решает множество проблем с производительностью:

  

Лично у меня не было проблем с производительностью, а также   должен помнить, что в функции есть две «ранние» точки   который на самом деле пинает довольно часто. Вот несколько статистических данных: I   обошел около нескольких минут на тестовой карте ERA, которая состояла из обоих   ландшафт (построенный из карты высот) и многоугольные сетки, такие как дома,   лестницы и т. д. Всего было отправлено 1,1 млн. треугольников   в течение всего испытательного периода, и приблизительно 40%   обнаружен, чтобы быть обратным и, таким образом, пропущен1. Из оставшихся 700 000   треугольники 65% смогли выйти из функции после   несколько дешевых тестов для вычисления значений времени t0 и t1. Из тех   треугольники, которые раньше не выходили из строя, должны были выполнить проверку развертки   но некоторые могли пропустить развертку, потому что столкновение с внутренним   треугольника. В целом всего около 20%   треугольники, отправляемые в функцию, должны были быть проверены на   столкновение с внутренним или краем треугольника и, таким образом,   полная цена за довольно долгую функцию.

ответил Justin Meiners 12 PM00000080000003931 2013, 20:46:39
2

Я был бы удивлен, если бы они не предварительно обработали этот список полигонов при загрузке в пространственную структуру данных. Это может быть так же просто, как однородная 2D-сетка по всему миру или нечто более сложное, как дерево k-d.

Это позволит вам быстро найти короткий список полигонов, близких к интересующей точке, и затем вы можете проверить каждый из них, чтобы увидеть, столкнулись ли вы.

Любой современный физический движок должен легко обрабатывать статическую сетку полигонов столкновений, используя некоторую форму пространственного подразделения. Например, проверьте btBvhTriangleMeshShape, у которого есть пуля .

ответил Adam 3 AM00000050000004731 2013, 05:19:47

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132