Лучший / эффективный способ реализации 3d Collision

16

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

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

Жан-Филипп Леклерк
источник

Ответы:

11

Вам понадобится хороший алгоритм разделения пространства, обычно используемый в 3D - это октреи .

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

Смотрите это изображение: несколько ограничивающих сфер

Рой Т.
источник
12

В конечном счете, я думаю, что ответ на ваш вопрос будет зависеть от потребностей вашего конкретного приложения, поскольку не существует универсального решения для всех. Несмотря на то, что в Интернете есть ряд достойных ресурсов, вы сэкономите много времени и разочарования, если обнаружите обнаружение столкновений Кристера Эриксона в реальном времени. , в которой подробно рассматриваются разнообразные методы и алгоритмы, например C ++ код.

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

http://www.realtimerendering.com/intersections.html

В то же время, поскольку я знаю, что не все могут просто раскошелиться на 70-80 долларов за книгу по желанию, вот некоторые термины, которые вы могли бы рассмотреть:

  • Пространственное разбиение, Octrees, Quadtrees, BSP деревья
  • Деревья БиГ
  • Ограничивающие объемы и ограничивающие объемные иерархии
  • Обнаружение дискретных и непрерывных столкновений
  • Теорема о разделяющей оси
  • Алгоритм GJK
user_123abc
источник