Задача взаимного размещения многогранников. Построение характеристического многогранника. Система плагинов
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
Задача взаимного размещения многогранников. Построение характеристического многогранника. Система плагинов
Введение
В компьютерном моделировании наиболее распространенный способ представления трехмерных объектов - аппроксимация их с помощью многогранников. Взаимное размещение многогранников - это широкий класс геометрических задач, включающий в себя такие задачи как:
-проверку пересечения многогранников, каким-либо образом размещенных в пространстве,
-определение, можно ли один или несколько многогранников поместить внутрь другого без пересечений,
-оптимальное размещение, т.е. размещение многогранников таким образом, чтоб не было пересечений и некоторый функционал достиг минимума,
-вычисление расстояния между двумя многогранниками,
-поиск траектории движения подвижного многогранника от одной точки к другой, такой чтоб он не пересекался с неподвижным многогранником
и другие.
Алгоритмы решения этих задач имеют широкую область применения, включающую программные тренажеры, компьютерные игры, приложения для решения задач упаковки и раскроя, программы для управления роботами.
В рамках этой работы будет рассматриваться одна из задач взаимного размещения многогранников - проверка пересечений для случая, когда многогранники могут перемещаться посредством параллельного переноса. Обычно, эта задача решалась путем иерархического разбиения многогранника на части и вписывания каждой из частей в объект простой формы (как правило, параллелепипед или сферу).
В данной работе предлагается другой подход, основанный на построении вспомогательного объекта - характеристического многогранника, который может быть использован для быстрой проверки пересечений. Построение характеристического многогранника для выпуклых многогранников - относительно простая задача. Гораздо сложнее построить характеристический многогранник, если исходные многогранники не выпуклые. В работе представлен эффективный алгоритм решения этой задачи.
Постановка задачи
многогранник алгоритм вычислительный плагин
Даны два многогранника в трехмерном пространстве, без самопересечений, необязательно выпуклые. Считаем, что их грани - треугольники. Это несерьезное ограничение, поскольку любую многоугольную грань можно представить в виде набора треугольных. Один из многогранников неподвижен, другой может перемещаться посредством параллельного переноса. Необходимо построить структуру данных, посчитав которую один раз, можно затем быстро определять, пересекаются многогранники или нет.
Выберем произвольную точку v0 в системе координат подвижного многогранника (например, можно взять одну из его вершин, либо просто начало координат). Рассмотрим геометрическое место точек, которое описывает точка v0 при всех возможных положениях подвижного многогранника, в которых он касается неподвижного и находится снаружи его. Полученная фигура также является многогранником. Назовем его характеристическим. Этот многогранник обладает одним полезным свойством: точка v0 лежит внутри него, когда подвижный многогранник пересекается с неподвижным, на поверхности, когда многогранники касаются, и снаружи, когда они не пересекаются.
Таким образом, если построить характеристический многогранник, то проверка пересечения двух многогранников будет сведена к определению, лежит ли точка внутри характеристического многогранника. Эта задача относится к классу задач геометрического поиска [1]. Для ее решения строят специальную структуру данных [2], с использованием которой вычислительная сложность проверки, лежит ли точка внутри многогранника, составляет O (log N), где N - количество его граней.
Помимо работы над алгоритмом требовалось создать Среду для разработки и тестирования алгоритмов проверки пересечений. Моей задачей была реализация одной из подсистем Среды, а именно Системы плагинов.
Обзор существующих алгоритмов построения характеристических многогранников
Прежде чем описывать существующие алгоритмы, дадим альтернативное определение характеристического многогранника. Пусть P1 - неподвижный многогранник, P2 - подвижный многогранник. Считаем, что в качестве v0 взята точка ноль в системе координат P2. Определим множество A, равное множеству точек, лежащих внутри многогранника P1, плюс его граница. Иными словами, A - множество точек, ограниченное многогранником P1. Аналогично для многогранника P2 определим множество B.
Для произвольных множеств точек X, Y определим следующие операции:
X = {-x | x X} - отражение множества относительно начала координат.
X + Y = {x + y | x X, y Y} - сумма Минковского двух множеств.
Вычислим множество С = A + - B. Утверждается, что граница этого множества - искомый характеристический многогранник. Действительно, пусть точка v0 = 0 С. Это значит, что существуют a A и b B такие, что a - b = 0. То есть a = b, значит, множества A и B имеют общую точку, а, следовательно, многогранники P1 и P2 пересекаются (либо касаются, в случае если точка 0 лежит на границе C). Ана