Столкновения в реальном приложении

Question

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

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

У меня есть 2 типа мешей, для которых я должен делать столкновения:

1) Статические сетки (которые перемещаются по экрану, но не имеют ЛЮБОЙ анимации)

2) Сетчатые / очищенные от костей сетки (анимированные)

На самом деле у меня есть это решение (довольно хаки: |)

Прежде всего у меня есть тест на некоторый ограничивающий объем, который охватывает всю сетку (капсула в моем случае), после:

1) Для статических сеток я делю их вручную на блоки (на моделирующем устройстве), и для каждого из этих блоков я использую тест сферы / AABB. (работает нормально, но немного мешает разрезать каждую сетку: P) (я попробовал автоматическую систему для разделения сетки по плоскостям, но это дает плохие результаты: ()

2) Для банкомата с анимированной сеткой я делю сетку во время выполнения на x блоков (где x - количество костей). Каждый блок содержит вершину, для которой эта кость является основным влияющим фактором. (Иногда работает, иногда дает действительно плохие результаты.: |)

Обратите внимание, что деление сетки выполняется во время загрузки, а не каждый раз (в противном случае это будет работать как слайд-шоу: D)

А вот и вопрос:

Какую наиболее разумную идею использовать для этих двух случаев? Любой материал для меня, чтобы изучить эти методы? (с некоторым исходным кодом и объяснениями было бы еще лучше (язык не важен, когда я понимаю алгоритм, реализация проста)) Можете ли вы аргументировать, почему это решение лучше, чем другие? Я много слышал о kd-tree, octree и т. Д. Хотя я понимаю их структуру, я скучаю по их полезности в сценарии обнаружения столкновений.

Большое спасибо за ответы !!!

РЕДАКТИРОВАТЬ: Попытка найти пример K-Dop с некоторыми объяснениями в сети. Все еще ничего не нашел. Есть какие-нибудь подсказки? Меня интересует, КАК K-Dop может быть эффективно протестирован с другими типами ограничивающих томов и т. Д., Но документация в сети, кажется, сильно отсутствует. (

Answer 1

Перед выполнением сложного обнаружения столкновений вы должны выполнить базовое обнаружение.

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

То, к чему я стремлюсь, просто, лучше и быстрее. Упаковка ограничивающих томов и разбиение сеток обходятся дорого, не говоря уже о сложности. Похоже, вы на правильном пути.

Как и в программировании игр, существует несколько способов обнаружения столкновений. Мой совет будет простым. Возьмите куб и оттачивайте свои процедуры на этом, тогда теоретически вы сможете использовать любую другую модель. Что касается примеров, я бы проверил gamedev.net , поскольку у них есть хорошие статьи. Многое или мое домашнее обнаружение столкновений является комбинацией многих методов, поэтому я не могу порекомендовать конкретный ресурс.

Answer 2

Наиболее распространенными подходами, используемыми во многих современных играх AAA, является упрощенное столкновение "k-DOP" для StaticMeshes и упрощенное представление физического тела для SkeletalMeshes.

Если вы гуглите «столкновение kDOP» или «многогранник с дискретной ориентацией», вы должны найти достаточно ссылок. По сути, это ограничивающий объем, определяемый несколькими плоскостями, которые перемещаются снаружи в направлении сетки, пока не произойдет столкновение треугольника. «K» в kDOP определяет, сколько из этих плоскостей используется, и в зависимости от вашей геометрии и вашего «k» вы получите действительно хорошие приближения с этим.

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

Если вам нужно столкновение для каждого треугольника, то «Теорема о разделяющей оси» - это поисковый запрос Google. Это полезно для особых случаев, но 75% ваших потребностей в обнаружении столкновений должны быть покрыты вышеупомянутыми методами.

Имейте в виду, что вам, скорее всего, потребуется более высокий уровень отказа от ранних столкновений, чем ограничивающий объем. Как только у вас появится много объектов в мире, вам нужно будет использовать «пространственное разделение», чтобы как можно раньше отклонить группы объектов от дальнейшего тестирования.

Answer 3

Забрать Книга Кристера Эриксона , Обнаружение столкновений в реальном времени . Он обсуждает эти самые вопросы очень подробно.

При чтении статей помните, что в реальном игровом приложении вы будете работать с жесткими ограничениями памяти и времени - вы получите 16,6 мс за кадр и все! Так что будьте осторожны с любой статьей или статьей, в которой не обсуждаются серьезно занимаемая памятью и процессор ее алгоритм.

Answer 4

Ответ на вопрос сводится к как точно вам нужно?

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

Физический движок разработки игр полагается на искусство приближения (я скрывался на форумах GameDev.net по математике и физике много лет назад).

Мое мнение таково, что вам понадобится какой-то ограничивающий эллипсоид, связанный с каждым объектом. Объект может быть обычным многосетевым объектом, сеткой или подсеточной сеткой. Это должно обеспечить «приличное» количество приближения.