-
Notifications
You must be signed in to change notification settings - Fork 1
Аналитическая часть
Целью данной статьи является исследование методов разбиения пространства с целью получения минимального времени поиска столкновений (их также принято называть коллизиями) в физической симуляции. Для её достижения требуется создание программы, в которой будет иметься возможность симулировать движение переменного количества объектов и применять различные алгоритмы обнаружения столкновений.
Для реализации данных требований использовалась двухмерная модель движения одинаковых по массе и размерам шаров в ограниченном пространстве. В определённой степени это схоже с поведением частиц, участвующих в Броуновском движении. Шары могут сталкиваться с границами области и между собой. В обоих случаях для них применяется модель абсолютного упругого удара. Для упрощения не рассматриваются вращения шаров вокруг собственной оси, так как это не имеет значения для основной задачи работы. Трение в системе также не учитывается для сохранения её динамичности в процессе исследования.
В данной задаче наиболее удобным является заполнить в начальный момент времени сцену заданным количеством шаров с случайными позициями и векторами скоростей. После чего моделируя вышеописанные явления можно получить динамическую симуляцию, в которой случайным будут происходить ситуации, которые представляют интерес для поставленной задачи.
Как было отмечено выше, основное внимание данного исследования уделено анализу и сравнению алгоритмов поиска столкновений. Данная тема является достаточно широко исследованной и поэтому существует значительное количество подходов разбиения пространства. В рамках поставленной задачи рассматриваются лишь некоторые из данных методов.
Этот метод является самым простым решением задачи поиска. Его принцип заключается в том, что каждый объект сцены проходит проверку на столкновение со всеми иными объектами. В моделируемой сцене всеми объектами являются шары, что сильно упрощает определение наличия столкновения между двумя объектами: нужно сравнить расстояние между центрами с двойным радиусом. В случае если расстояние меньше или равно, считается, что два объекта столкнулись.
Преимуществом данного метода является:
- Простота реализации
- Не требует создания дополнительных структур
- Универсальность
Недостатком метода является сложность O(n^2), что означает быстрый рост временных затрат при увеличении количества объектов на сцене. Однако, данный алгоритм остаётся наилучшим решением для анализа небольшого количества объектов, что будет продемонстрированно далее.
Суть всех следующих алгоритмов разбиения пространства заключается в том, что для проверки на предмет коллизии также будет использован полный перебор, но только для объектов в ограниченной области пространства. Такие проверки осуществляются для всех подобластей, которые структурируются с помощью деревьев для создания иерархии.
Наиболее известный алгоритм разбиения пространства. Принцип работы у него следующий.
- Изначально создаётся структура корневого дерева, в которую будут добавляться объекты.
- После нескольких добавлений достигается "критическое количество" шаров в данной области. Cоздаются деревья, разбивающие её на 4 одинаковые прямоугольные части. Общая вершина данных прямоугольников располагается ровно в центре делимого пространства. Объекты распределяются по новым подобластям.
- После добавления всех объектов, производится обход по дереву и в каждом концевом узле (то есть неразделённой области) применяется алгоритм полного перебора для поиска столкновений.
Проверка вхождения шара в подобласть производится сравнением координат углов прямоугольника области и описанного вокруг шара квадрата. Если обнаруживается их пересечение, то считается, что тело принадлежит области.
Описанный алгоритм имеет ряд модификаций. Некоторые из них также представляют интерес для исследования, и поэтому будут затронуты в данной работе
Является вариацией дерева квадрантов, но вместо разбиения на четыре одинаковые области применяется девять областей. Фактически исследование этой модификации нацелено на определение оптимального количества разбиений. Такое деление позволяет сильнее дробит области дерева, и таким образом ведёт к уменьшению глубины дерева. Это потенциально может снизить общее время обработки за счёт меньшего количества переходов по дереву.
Зачастую, распределение даже достаточно большого количества объектов не является равномерным, что приводит к неравномерному заполнению подобластей в алгоритме дерева квадрантов. Данная проблема может быть решена перемещением центра разбиения таким образом, чтобы обеспечить максимально близкое по количеству объектов заполнение подобластей. Зачастую, такого результата можно достигнуть, если в качества точки разбиения использовать среднюю от координат всех центров объектов (в данной симуляции оно совпадает с центром масс системы).
В таком случае требуется учитывать все шары находящиеся в рассматриваемой области, что несколько меняет алгоритм. В первую очередь следует добавить все шары в корневую область, после чего вычислить центр масс всех шаров и произвести разбиение на подобласти с распределением в них объектов.
Вычисление координат средней точки всех тел является вычислительно затратным занятием. Центр каждого шара будет учитываться при каждом разбиении, поэтому в среднем один шар будет учтён log4(n) раз, где n - число объектов в системе. Всего дополнительные вычисления будет произведены примерно n*log4(n) раз. Для уменьшения затрат вычисления средних координат можно осуществлять для, к примеру, 100 случайно выбранных шаров в области.
Как видно из названия, в данном методе разбиение пространства происходит на две равные части. Сцена является прямоугольником, поэтому её деление производится по диагонали и образует два одинаковых прямоугольных треугольника. Их разбиение осуществляется по медиане к самой длинной стороне. Полученные части удобнее всего обозначить как левая и правая относительно вектора, лежащего вдоль границы (при разбиении прямоугольника направление вектора берётся от нижней вершины, в треугольнике - от угла).
При подобном делении усложняется задача определения принадлежности объектов к областям. Определить положение точки относительно разделяющего отрезка можно с помощью векторного произведения вектора, лежащего вдоль него, и вектора от конца отрезка до рассматриваемой точки. Точки лежащие правее разделителя будут иметь положительное векторное произведение, левее - отрицательное. Для проверки шара на принадлежность к правой области следует использовать самую "правую" точку окружности (центр шара + вектор радиуса, направленный перпендикулярно к разделителю). Аналогично для левой области.
Принципиальным отличием от вышеописанных алгоритмов является отсутствие иерархии разбиения. Всё поле делится на одинаковые прямоугольные области (называемые "корзинами", от анг. bin). В общем случае алгоритм предназначен для оценки наличия пересечения множества прямоугольных областей. Для этого каждая корзина представляется массивом объектов, которые частично или полностью попадают в данную область.
Для занесения объекта в клетки нужно вычислить клетки, в которых расположены вершины объекта с минимальными и максимальными координатами. После чего во все корзины расположенные в области между найденными клетками заносится рассматриваемый объект. Применительно к данной задаче, шары описываются прямоугольниками с координатами углов (x-r, y-r) и (x+r, y+r), где (x, y) - центр, r - радиус. Стоит отметить, что использование размера корзин меньше 2r не имеет смысла, так как некоторые клетки будут полностью внутри шаров.
После добавления в структуру всех шаров для обнаружения всех столкновений достаточно проверить корзины с 2+ шарами. При небольшой плотности заполнения поля производить обход всех корзин неэффективно. Чтобы обходить только необходимые клетки можно воспользоваться дополнительной структурой связанного списка. В него заносятся клетки по достижению в них двух шаров.
Явным недостатком является зависимость занимаемой памяти от площади контролируемого пространства, что делает проблемным его использование для обширных сцен.
В разбиении пространства с помощью деревьев возникает проблема определения принадлежности шаров, расположенных на границе двух и более подобластей. Такой шар может иметь столкновения с телами из всех занимаемых им областей, поэтому следует занести его в массивы каждого из деревьев.