Столкновения в реальном мире
Вот моя проблема. Я создаю игру, и мне интересно, как это делать. У меня есть несколько примеров для анализа и поиска лучшего решения.
Я скажу это заранее, я не использую какую-либо стороннюю физическую библиотеку, но я собираюсь сделать это в доме. (поскольку это образовательный проект, у меня нет расписаний, и я хочу учиться)
У меня есть 2 типа сетки, для которых мне приходится совершать столкновения для:
1) Статические сетки (которые перемещаются по экрану, но не имеют ЛЮБОЙ анимации)
2) Консервированные /Boned Meshes (анимированные)
На самом деле у меня есть это решение (довольно хакерское: |)
Прежде всего, у меня есть тест против некоторого ограничивающего тома, который заключает в себе полный меш (капсула в моем случае), после:
1) Для статических сеток я делю их вручную в блоках (на моделере), и для каждого из этих блоков я использую тест сферы /AABB. (работает отлично, но его немного беспорядочно нарезать каждую сетку: P) (я попробовал автоматическую систему для разделения сетки через плоскости, но это дает плохие результаты:()
2) Для анимированного Mesh-ATM я деля по сетке во время выполнения на x блоков (где x - количество костей). Каждый блок содержит вершину, для которой эта кость является основным фактором. (Иногда работает, иногда дает очень плохие результаты.: |)
Обратите внимание, что разделение сетки выполняется во время загрузки, а не каждый раз (в противном случае оно будет работать как слайд-шоу: D)
И вот вопрос:
Какая самая разумная идея для использования в этих двух случаях?
Любой материал для меня, чтобы изучить эти методы? (с некоторыми исходными кодами и объяснениями будет еще лучше (язык не важен, когда я понимаю алгоритм, реализация проста))
Можете ли вы аргументировать, почему это решение лучше других?
Я слышал много разговоров о kd-tree, octree и т.д., Тогда как я понимаю их структуру, я пропускаю свою утилиту в сценарии обнаружения столкновений.
Спасибо большое за ответы!!!
EDIT: попытка найти пример K-Dop с некоторым объяснением в сети. Все еще ничего не нашли.:( Любые подсказки?
Я заинтересован в том, КАК K-Dop может быть эффективно протестирован с другими типами ограничивающих томов и т.д.... но документация в сети кажется крайне недостаточной.: (
Ответы
Ответ 1
Наиболее распространенные подходы, используемые во многих современных играх AAA, - это упрощенное коллизия "k-DOP" для StaticMeshes и упрощенное представление физического тела для SkeletalMeshes.
Если вы используете Google для "столкновения kDOP" или "многогранников с дискретной ориентацией", вы должны найти достаточно ссылок. По сути, это ограничивающий объем, определяемый несколькими плоскостями, которые перемещаются снаружи в направлении сетки, пока не произойдет коллизия треangularьника. "K" в kDOP определяет, сколько из этих плоскостей используется, и в зависимости от вашей геометрии и вашего "k" вы можете получить действительно хорошие приближения.
Для SkeletalMeshes наиболее распространенным методом является определение простой геометрии, которая прикрепляется к конкретным костям. Эта геометрия может быть коробкой или сферой. Эта модель столкновения может быть использована для довольно точного обнаружения столкновений анимированных сеток.
Если вам нужно коллизия для каждого треangularьника, то "Теорема о разделяющей оси" - это поисковый запрос Google. Это полезно для особых случаев, но 75% ваших потребностей в обнаружении столкновений должны быть покрыты вышеупомянутыми методами.
Имейте в виду, что вам, скорее всего, потребуется более высокий уровень отклонения ранних столкновений, чем ограничивающий объем. Как только у вас появится много объектов в мире, вам нужно будет использовать "пространственное разделение", чтобы как можно раньше отклонить группы объектов от дальнейшего тестирования.
Ответ 2
Перед выполнением комплексного обнаружения столкновений вы должны выполнить базовое обнаружение.
Использование сфер или прямоугольников в качестве ограничивающих объемов - ваш лучший выбор. Затем, если это обнаруживает столкновение, переходите к более сложным методам.
То, что я получаю, просто часто бывает лучше и быстрее. Обтекание ограничивающих объемов и разделение сетки дорогостоящее, не говоря уже о сложном. Вы, кажется, на правильном пути, хотя.
Как и при программировании игр, существует несколько способов обнаружения столкновений. Мой совет станет простым. Возьмите куб и подстройте свои подпрограммы, а затем теоретически вы сможете использовать любую другую модель. Что касается примеров, я бы проверил gamedev.net, так как у них есть интересные статьи. Многое или мое домашнее обнаружение столкновений - это комбинация многих методов, поэтому я не могу рекомендовать окончательный ресурс.
Ответ 3
Ответ на вопрос сводится к тому, насколько вам точен?
Ясно, что сферические прямоугольники являются наиболее тривиальными. С другой стороны шкалы вы обнаруживаете полное обнаружение столкновения сетчатой сетки треугольника, которое должно происходить каждый раз, когда объект перемещается.
Механизм разработки игр основывается на искусстве приближения (я скрывался в игровых дискуссиях GameDev.net много лет назад).
Мое мнение таково, что вам понадобится какой-то ограничивающий эллипсоид, связанный с каждым объектом. Объект может быть общим многомесячным объектом, сеткой или сеткой subesh. Это должно обеспечить "приличное" количество приближений.
Ответ 4
Возьмите книгу Кристера Эриксона, Обнаружение столкновений в реальном времени. Он обсуждает эти самые вопросы очень подробно.
Читая статьи, помните, что в реальном игровом приложении вы будете работать с жесткими ограничениями памяти и времени - вы получите 16,6 мс за кадр и все! Так что будьте осторожны с любой статьей или статьей, в которой серьезно не обсуждается использование памяти и ЦП алгоритма.