Обнаружение столкновения: куча особых случаев?

Я пишу простой физический движок в 2D. Моя первая цель - заставить работать обнаружение столкновений. Я знаю, что мои объекты в конечном итоге будут состоять из примитивных форм, но мне было интересно - будет ли библиотека обнаружения столкновений состоять из набора специальных функций, таких как «rayAndLine», «rectangleRectangle», «rectangleCircle» и т. Д., Или Существует ли общая базовая структура для обнаружения столкновений, которая работает независимо от того, какие примитивы используются для создания формы?

Начало работы по обнаружению столкновений - отличная первая цель для вашего физического движка 2D. Хорошо, что вы решили, что сейчас вы конкретно работаете в 2D, поскольку не все правила в 2D работают в 3D, несмотря на большое количество алгоритмов, связанных с n-размерностью, в какой-то момент вы должны специализировать их (сделайте больше конкретный вариант, например, как перекрестное произведение удовлетворяет только идентичности Якоби в 3D).

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

Архитектура решающих движков: с любым математическим движком мы, по сути, хотим поместить значения в какую-то функцию, и мы ожидаем, что значения окажутся полезными для создания интересного моделирования.

Основные элементы этого процесса должны быть настолько абстрактными, насколько это возможно, в то время как элементарные элементы (наименьшие полезные фрагменты данных / методы) должны быть специфическими для отдельных целей и быть полезными для составления вместе. В нашем случае почти единственным полезным атомарным представлением является 2D-вектор, который должен быть единственным классом объекта, который допускает выражение структуры (x, y), и имеет методы для всех основных математических операций, которые полезны для векторных вычислений в 2D. Сложение, вычитание, нормализация, нормаль (перпендикулярно), кросс-произведение, скалярное произведение, величина / длина и все остальное, с чем вы сталкиваетесь, что конкретно присуще векторам -> векторным операциям или вектору -> действительным числам Если вы используете язык, основанный на классах, простое использование class Vectorкаждого из них как функции-члена или перегрузки оператора будет очень хорошо.

После того, как все атомарные типы будут построены, вы могли бы объединить их алгоритмы в другой слой поверх нашего атомарного типа Vector. Мое движение к будет Lineи Curve. Здесь мы решим, что a Curveвыходит за рамки этого и требует большой специализации (концепция, которую вы упоминаете выше как создание множества специальных случаев). Из Vectorя также хотел бы составить Rectangleкак Vectorпримитив 4 , составить Circleиз вектора с использованием а Vectorи а radius, а затем я бы также составить Polygonиз Vector. Polygonдолжен быть сделан из, Vectorа не Lineздесь, потому что каждая линия будет иметь двойную точку с последней линией в многоугольнике.

Теперь у вас есть фигуры, но мы не знаем, что с ними делать.

Обнаружение столкновений Обнаружение столкновений не является точной наукой, и не существует ни одного идеального алгоритма (или какого-либо другого). Существует множество методов, которые можно использовать для достижения разнообразных эффектов или даже более точных, чем другие. Хотя, в принципе, его можно разделить на несколько разных уровней озабоченности и, таким образом, на несколько разных процессов.

Обнаружение коллизий с широкой фазой - это процесс разделения областей, в которых мы заботимся о том, что может / могло / действительно сталкиваться, и разделяя их для узкофазного процесса. В 2D я бы обычно рекомендовал для этого использовать дерево квадов. Для этого нам понадобится наш, который Rectangleмы построили ранее, и обеспечить его обнаружением коллизий AABB. Это означает ограничивающий прямоугольник с выравниванием по оси, и мы используем его для определения того, что для невращающегося прямоугольника A, Bвнутри которого нет ни одной части прямоугольника A. Из предположения следует, что Bвнутри не может существовать никакой части, Aпоскольку столкновение существует, если они пересекаются.

Четырехъядерное дерево - это рекурсивный процесс, в котором вы определяете максимальную глубину или позволяете количеству объектов вместо этого предотвращать бесконечную глубину рекурсии. Он группирует физические тела в 4 области (отсюда и название) и должен позволять вам обращаться к каждому квадру отдельно. Затем вы входите в каждый из этих четырех четырехугольников и выполняете тот же процесс, который я не буду кратко описывать здесь, но он доступен здесь: https://gamedevelopment.tutsplus.com/tutorials/quick-tip-use-quadtrees- на обнаружение-вероятные-столкновений-в-2d пространства - Gamedev-374

Узкое фазовое столкновениеэто процесс прохождения ваших групп фигур, который мы уже определили, столкнется / может / действительно столкнуться и выполнит более дискретную проверку столкновения, в этот момент времени мы начинаем заботиться, вращаются ли объекты или нет (я выиграл ' Если вы пройдете эти фазы столкновения, посмотрите на обнаружение столкновения с угловым моментом) и какую форму на самом деле имеет их тело столкновения. Для выполнения этой части коллизии вы должны специализировать свои методы, как описано выше (создание специальных функций для AABBvsCircle, OBBvsCircle, CirclevsCircle, PolygonvsPoint, PolygonvsCircle, PointvsCircle и т. Д.). Однако сами эти методы также можно выполнять многоуровневым способом. как указано выше.

Ваши примитивные проверки разделения являются дискретными, специализированными методами обнаружения столкновений или общих из них , как СБ в зависимости от случая использования и все должно просто возвращать либо истинное / ложное значение, или возвращать реляционный объект , такие как Manifold, Joint, и CollisionObjectт.д. , которые будет иметь связь с двумя фигурами, находящимися в столкновении, и любой информацией о них, необходимой для разрешения столкновения, например, насколько глубоко они сталкиваются или с какой скоростью (какие данные вам нужны в вашем коллекторе, зависит от того, какой метод разрешения вы используете). Затем этот объект вы передаете объекту, Solverкоторый должен абстрагироваться от различий между всеми различными формами, которые могут столкнуться, принимая только Manifoldи не принимая какую-либо конкретную информацию о формах.

Резюме . SolverПримем Manifoldпроизведенное, столкнув некоторый примитив Aс некоторым примитивом B, используя сначала широкую фазовую группировку (все против мира), а затем узкую фазовую детекцию (A против B), и если формы не являются полигонными, они должны быть специализированными, Solverтогда получаются либо новые Vectors для позиций и скоростей столкнувшихся фигур, или объекта, который затем PhysicsEnvironmentили Worldможет использовать для разрешения столкновения на своих потомках, затем, наконец, обновите QuadTreeи повторите этот процесс для следующего кадра. Если обе сталкивающиеся фигуры являются полигонами, то специализация должна проводиться только с точки зрения увеличения производительности, в противном случае просто используется теорема о разделении осей.