Задача взаимного размещения многогранников. Построение характеристического многогранника. Система плагинов

Задача взаимного размещения многогранников. Построение характеристического многогранника. Система плагинов

Введение

В компьютерном моделировании наиболее распространенный способ представления трехмерных объектов - аппроксимация их с помощью многогранников. Взаимное размещение многогранников - это широкий класс геометрических задач, включающий в себя такие задачи как:

-   проверку пересечения многогранников, каким-либо образом размещенных в пространстве,

-   определение, можно ли один или несколько многогранников поместить внутрь другого без пересечений,

-   оптимальное размещение, т.е. размещение многогранников таким образом, чтоб не было пересечений и некоторый функционал достиг минимума,

-   вычисление расстояния между двумя многогранниками,

-   поиск траектории движения подвижного многогранника от одной точки к другой, такой чтоб он не пересекался с неподвижным многогранником

и другие.

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

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

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

Постановка задачи

многогранник алгоритм вычислительный плагин

Даны два многогранника в трехмерном пространстве, без самопересечений, необязательно выпуклые. Считаем, что их грани - треугольники. Это несерьезное ограничение, поскольку любую многоугольную грань можно представить в виде набора треугольных. Один из многогранников неподвижен, другой может перемещаться посредством параллельного переноса. Необходимо построить структуру данных, посчитав которую один раз, можно затем быстро определять, пересекаются многогранники или нет.

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

Таким образом, если построить характеристический многогранник, то проверка пересечения двух многогранников будет сведена к определению, лежит ли точка внутри характеристического многогранника. Эта задача относится к классу задач геометрического поиска [1]. Для ее решения строят специальную структуру данных [2], с использованием которой вычислительная сложность проверки, лежит ли точка внутри многогранника, составляет O (log N), где N - количество его граней.

Помимо работы над алгоритмом требовалось создать Среду для разработки и тестирования алгоритмов проверки пересечений. Моей задачей была реализация одной из подсистем Среды, а именно Системы плагинов.

Обзор существующих алгоритмов построения характеристических многогранников

Прежде чем описывать существующие алгоритмы, дадим альтернативное определение характеристического многогранника. Пусть P₁ - неподвижный многогранник, P₂ - подвижный многогранник. Считаем, что в качестве v₀ взята точка ноль в системе координат P₂. Определим множество A, равное множеству точек, лежащих внутри многогранника P₁, плюс его граница. Иными словами, A - множество точек, ограниченное многогранником P₁. Аналогично для многогранника P₂ определим множество B.

Для произвольных множеств точек X, Y определим следующие операции:

X = {-x | x  X} - отражение множества относительно начала координат.

X + Y = {x + y | x  X, y  Y} - сумма Минковского двух множеств.

Вычислим множество С = A + - B. Утверждается, что граница этого множества - искомый характеристический многогранник. Действительно, пусть точка v₀ = 0  С. Это значит, что существуют a  A и b  B такие, что a - b = 0. То есть a = b, значит, множества A и B имеют общую точку, а, следовательно, многогранники P₁ и P₂ пересекаются (либо касаются, в случае если точка 0 лежит на границе C). Аналогично показывается, что, если С не содержит точку 0, то многогранники не пересекаются. Таким образом, граница множества С - характеристический многогранник. Стоит отметить, что это определение применимо не только к многогранникам, его можно использовать и для других объектов (к примеру, при построении характеристического множества для сферы и многогранника). В научных публикациях задачу построения характеристического многогранника часто называют задачей построения суммы Минковского двух многогранников.

Алгоритмы для выпуклых многогранников

Алгоритм, основанный на построении выпуклой оболочки

Пусть даны два многогранника P₁ и P₂. V - множество вершин P₁, U - множество вершин P₂. Определим множество точек W = V + - U. Построим выпуклую оболочку множества W. Граница этого множества - искомый характеристический многогранник [3].

Алгоритм, основанный на скольжениях

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

Алгоритмы для невыпуклых многогранников

Алгоритм, использующий разбиение на выпуклые многогранники

Разобьем многогранники P₁ и P₂ на несколько многогранников так, чтобы новые многогранники были выпуклые. Для каждой пары многогранников, такой, что один многогранник принадлежит разбиению P₁, а другой - разбиению P₂, построим характеристический многогранник (любым из рассмотренных выше способов). Объединив все построенные выпуклые характеристические многогранники, получим искомый характеристический многогранник. То, что полученный объект действительно является характеристическим многогранником, следует из свойств суммы Минковского:

(A U B) + C = (A + C) U (B + C)

(A U B) + (C U D) = (A + C) U (B + C) U (A + D) U (B + D)

и т.д. для произвольного количества множеств.

У этого метода есть существенные проблемы. Во-первых, если исходные многогранники сложные, то количество многогранников в разбиении будет велико, а, следовательно, количество выпуклых характеристических многогранников, которые нужно построить, также будет велико. Во-вторых, разработать эффективный метод объединения большого количества многогранников достаточно проблематично. Все это может привести к низкой производительности программной реализации алгоритма. Этот алгоритм и способы его оптимизации описаны в [4].

Алгоритмы, основанные на скольжениях

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

В работе [7] приводится алгоритм, в котором части граней характеристического многогранника удаляются с помощью булевых операций. Из-за того, что для каждой построенной грани нужно решать задачу булевого вычитания невыпуклых многоугольников, при реализации этого алгоритма могут возникнуть проблемы с производительностью.

В данной же работе рассматривается другой способ удаления частей грани. Его идея заключается в том, что построенные грани разрезаются друг другом, а затем производится удаление ненужных частей путем проверки пересечения исходных многогранников.

В работе также описаны оптимизации, которые можно применить, чтоб получить эффективный алгоритм.

Алгоритм построения характеристического многогранника для случая выпуклых исходных объектов

Опишем процедуру построения характеристического многогранника для случая, когда оба исходных объекта являются выпуклыми многогранниками. Пусть P₁ - неподвижный многогранник, P₂ - подвижный многогранник, v₀ - выбранная точка в системе координат P₂. В результате скольжения P₂ по P₁, v₀ описывает характеристический многогранник P.

При условии, что P_1, P₂ - выпуклые многогранники, P - также выпуклый. Грани многогранника P образуются в результате следующих видов скольжений:

•        вершина подвижного многогранника скользит по грани неподвижного

•        грань подвижного скользит по вершине неподвижного

•        ребро подвижного скользит по ребру неподвижного

•        грань подвижного скользит по грани неподвижного

•        ребро подвижного скользит по грани неподвижного

•        грань подвижного скользит по ребру неподвижного

Три последних случая являются вырожденными и в рамках данной работы рассматриваться не будут, т.е. мы считаем, что исходные данные таковы, что в них не возможны вырожденные скольжения. Рассмотрим каждый из невырожденных случаев скольжений отдельно.

Вершина подвижного многогранника скользит по грани неподвижного

Пусть v - вершина многогранника P₂, f - грань многогранника P₁, c₁, … c₃ - вершины f. Вектор n - нормаль грани f. Рассмотрим множество ребер e₁, …, e_m инцидентных вершине v. Для каждого ребра e_i определим вектор l_i, начинающийся в вершине v и направленный вдоль ребра e_i, то есть l_i = v_i - v, где v_i вершина ребра отличная от v. Тогда скольжение вершины v по грани f возможно лишь в том случае, если угол между l_i и n строго меньше 90^о, для i = 1… m. В результате такого скольжения выбранная вершина v_0, вычерчивает треугольную грань t, получаемую из f путем сдвига на вектор v₀ - v, т.е. её вершины задаются следующим образом: p_i = c_i + (v₀ - v), i = 1…3.

Стоит отметить, что нормаль полученной грани будет сонаправлена n.

Рис. 1. Скольжение вершины по грани

Грань подвижного многогранника скользит по вершине неподвижного

Пусть v - вершина многогранника P₁, f - грань многогранника P₂, c₁, … c₃ - вершины f. Возможность скольжения v по f проверяется аналогично предыдущему случаю. В результате скольжения образуется грань t, вершины которой определяются следующим образом: p_i = - c_3-i + (v₀ + v), i = 1…3.

Т.е. грань t получена путем отражения всех вершин грани f относительно начала системы координат, в которой они заданы, и сдвига их на вектор v + v₀. В отличие от предыдущего случая нормаль грани t, направлена против нормали грани f.

Рис. 2. Скольжение грани по вершине

Ребро подвижного многогранника скользит по ребру неподвижного

Пусть e₁ - ребро неподвижного многогранника, e₂ - ребро подвижного. Пары вершин a₁, a₂ и b₁, b₂ - концы ребер e₁ и e₂ соответственно. Направляющими векторами v₁ и v₂ ребра e₁ назовем вектора перпендикулярные ребру e₁ и направленные внутрь прилегающих к нему граней. Аналогично u₁ и u₂ направляющие векторы ребра e₂. Определим вектор n следующим образом, n = (b₂ - b₁) x (a₂ - a₁). Этот вектор задает нормаль плоскости скольжения. Ребро e₁ может скользить по ребру e₂ лишь в том случае, если двугранные углы, образованные прилежащими к ним гранями, расположены по разные стороны от плоскости скольжения. Иными словами, значения v₁*n, v₂*n имеют один знак, а u₁*n, u₂*n - другой. В результате скольжения образуются две треугольные грани t₁ и t₂, составляющие параллелограмм. Вершины этого параллелограмма - точки:

p₁ = a₁ - b₁ + v₀

p₂ = a₁ - b₂+ v₀

p₃ = a₂ - b₂+ v₀

p₄ = a₂ - b₁+ v₀

Для того чтобы нормаль граней была направлена вовне характеристического многогранника, необходимо задать правильный обход вершин. Введем вектор n₀ = n₁ + n₂, где n₁ и n₂ нормали граней прилежащих к ребру e₁, и вектор np = (p₄ - p₃) x (p₃ - p₂).

Если вектора n₀ и np сонаправлены, то t₁ = (p₁, p₂, p₃), t₂ = (p₁, p₃, p₄), в противном случае t₁ = (p₃, p₂, p₁), t₂ = (p₄, p₃, p₁).

Рис. 3. Скольжение ребра по ребру

Оценка вычислительной сложности

Пусть V₁, E₁, F₁ - количество вершин, ребер и граней многогранника P₁, а V₂, E₂, F₂ - те же характеристики для многогранника P₂. При построении характеристического многогранника выполняется V₂*F₁ проверок скольжений вершины по грани, F₂*V₁ проверок скольжений грани по вершине и E₁*E₂ проверок скольжений ребра по ребру. Таким образом, вычислительная сложность алгоритма пропорциональна величине T=V₂*F₁ + F₂*V₁ + E₁*E₂. Поскольку для каждого из многогранников P₁, P₂ выполнены соотношения E_i < 3*V_i, F_i < 2*V_i, то T < 13*V₁*V₂. Значит, вычислительная сложность алгоритма равна O(V₁*V₂).

Проверка пересечений с помощью характеристических многогранников

Пусть дано множество многогранников P₁, …, P_n. Необходим метод, позволяющий для двух произвольных многогранников P_i, P_j быстро определить, пересекаются они или нет. Предлагается следующее решение этой задачи:

1.       Для каждой пары многогранников выделяем подвижный многогранник, фиксируем точку v₀ и строим характеристический многогранник. Не важно, какой именно многогранник будет подвижным. При проверке пересечений имеет значение положение многогранников относительно друг друга.

2.       Для характеристических многогранников строим структуры для геометрического поиска.

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

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

Построение характеристического многогранника, при условии, что исходные объекты необязательно выпуклые

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

Построение характеристического многогранника состоит из 3-х шагов:

1)      Дополнительная проверка вершин и ребер.

2)      Построение граней.

)        Удаление частей граней.

Дополнительная проверка вершин и ребер

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

Дополнительная проверка для вершин

Пусть проверяем вершину v. e₁, …, e_m - ребра инцидентные v. Для каждого ребра e_i определим вектор l_i = v_i - v, где v_i вершина ребра отличная от v. Введем вектор l = l₁ + … + l_m. Пусть n_i,0, n_i,1 - нормали граней прилежащих к e_i. Определим вектор n = n_1,0 + n_1,1 + … + n_m,0 + n_m,1. Тогда если угол между векторами n и l меньше 90^о, то вершина v утоплена и не может участвовать ни в одном из скольжений.

Рис. 4. Утопленная вершина

Дополнительная проверка для ребер

Пусть проверяем ребро e. Введем вектор u = u₁ + u₂ (где u₁, u₂ - направляющие вектора ребра e) и вектор n = n₁ + n₂ (n₁, n₂ - нормали прилежащих к e граней). Тогда если угол между векторами n и u меньше 90^о, то ребро e утоплено, и не будет рассматриваться при проверке скольжений.

Рис. 5. Утопленное ребро

Построение граней

На этом шаге строятся грани характеристического многогранника, аналогично тому, как это делается для случая выпуклых многогранников. Естественно, рассматриваются только те вершины и ребра, которые прошли проверку на шаге 1.

Удаление частей граней

Полученные грани не обязательно будут гранями характеристического многогранника. Допустим, при одном из скольжений точка v₀ описала грань f. В отличие от случая выпуклых многогранников сейчас возможна ситуация, когда во время этого скольжения подвижный многогранник пересекается с неподвижным. Часть грани, которую описывает v₀, когда многогранники пересекались нужно удалить. Ключевой момент моей работы - это способ, которым удаляются такие части граней.

Части граней, которые необходимо удалить, находятся внутри нужного нам характеристического многогранника (рис 6). Это следует из свойства: точка v₀ находится внутри характеристического многогранника ó исходные многогранники пересекаются. Остальные части граней образуют поверхность характеристического многогранника.

Рис. 6. Части граней, которые нужно удалить

Грани, построенные на предыдущем шаге, могут пересекаться друг с другом. Грань может лежать частично внутри характеристического многогранника, частично на его поверхности лишь в том случае, если она пересекается с какой-либо другой гранью. Будем разрезать грань пересекающими ее гранями (как именно, будет описано позже). После того, как все такие разрезания будут выполнены, не останется ни одной пары пересекающихся граней. Это значит, что каждая из полученных граней либо полностью лежит на поверхности характеристического многогранника, либо полностью лежит внутри. Грани, которые лежат внутри нужно удалить.

Таким образом, алгоритм удаления частей граней состоит из следующих шагов:

1)      Поиск пересекающихся граней

2)      Разрезание граней

)        Удаление граней, лежащих внутри характеристического многогранника

Рассмотрим каждый из этих шагов подробней.

Поиск пересекающихся граней

На этом шаге для каждой грани f ищется множество граней, с которыми она пересекается. Вычисляются отрезки, образуемые при пересечении грани f с найденными гранями. Эти отрезки лежат в плоскости грани f. Чтобы ускорить поиск пересекающихся граней, можно использовать, так называемую иерархию ограничивающих объемов [8].

Рис. 7. Пересекающиеся грани

Разрезание граней

После того как для каждой грани найдено множество отрезков, грань необходимо разрезать. Для того чтоб разрезать грань f:

1.       В плоскости f строится триангуляция с ограничениями, в которой в качестве входных точек используются вершины грани f, а в качестве структурных ребер - полученные ранее отрезки. Алгоритмы построения триангуляции с ограничениями рассмотрены в [9].

2.       Грань f заменяется множеством полученных в результате триангуляции треугольных граней.

Рис. 8. Разрезание граней

Удаление граней, лежащих внутри характеристического многогранника

После разрезания образуется множество граней, которое можно разделить на две группы:

·              грани, которые образуют поверхность искомого характеристического многогранника.

·              грани, которые лежат полностью внутри характеристического многогранника.

Грани, принадлежащие второй группе, нужно удалить. Для этого воспользуемся следующим свойством исходных многогранников: они пересекаются тогда и только тогда, когда выделенная точка подвижного многогранника v₀ лежит внутри характеристического. Проверку пересечения многогранников можно осуществлять с помощью какого-либо готового алгоритма. Для того чтоб определить, лежит ли грань внутри характеристического многогранника, достаточно проверить лежит ли внутри ее центр.

Таким образом, для каждой грани:

1.       С помощью алгоритма проверки пересечений проверяется, пересекаются ли исходные многогранники (неподвижный многогранник ставится в начало координат, подвижный - так, чтоб v₀ совпала с центром грани).

2.       Если есть пересечение, то грань удаляется.

Рис. 9. Результат удаления частей граней

Оставшееся множество граней - грани искомого характеристического многогранника.

Оценка вычислительной сложности

Пусть неподвижный многогранник P₁ содержит V₁ вершин, подвижный многогранник P₂ - V₂ вершин.

Вычислительная сложность дополнительной проверки вершин и ребер равна O(V₁ + V₂).

Вычислительная сложность построения граней, как было выяснено ранее, равна O(V₁*V₂).

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

1.       Поиск пересекающихся граней.

На вход подается множество граней, количество которых пропорционально V₁*V_2. Необходимо проверить пересечение каждой грани с каждой. То есть вычислительная сложность этого шага O((V₁*V₂) ²)

2.       Разрезание граней.

Будем считать, что количество отрезков, образуемых при пересечении грани с другими гранями, мало по сравнению с V₁ и V₂. В таком случае, вычислительной сложностью триангуляции можно пренебречь. Значит, вычислительная сложность этого шага пропорциональна количеству граней, то есть равна O(V₁*V₂)

Считаем, что количество граней полученных на предыдущем шаге так же пропорционально V₁*V₂. Для каждой грани нужно сделать проверку, пересекаются ли исходные многогранники. Сложность каждой такой проверки O(V₁*V₂). Значит, вычислительная сложность шага равна O((V₁*V₂) ²).

Итого, вычислительная сложность алгоритма равна O((V₁*V₂) ²).

Время работы алгоритма

Время построения характеристического многогранника для различных входных данных.

Программная реализация

Особенности программной реализации алгоритма

Алгоритм построения характеристического многогранника был реализован на языке C++ с использованием библиотеки STL. Алгоритм оформлен в виде отдельного модуля с удобным интерфейсом, благодаря чему его легко можно использовать в других программах. Для работы с векторами, многогранниками и другими структурами данных была написана собственная математическая библиотека.

Стоит отметить следующие особенности реализации отдельных шагов алгоритма:

1)      Для оптимизации поиска пересекающихся треугольных граней используется дерево ограничивающих параллелепипедов [8].

2)      Проверка пересечений отдельных граней и построение отрезков, вдоль которых грани пересекаются, осуществляется с помощью быстрого алгоритма пересечения треугольников Моллера [10].

)        Триангуляция с ограничениями строится жадным алгоритмом [9]. Выбор этого алгоритма обусловлен тем, что количество элементов участвующих в построении триангуляции невелико: три точки (вершины грани) и несколько отрезков, полученных при пересечении с другими гранями. В перспективе можно попробовать применить другие способы триангуляции и сравнить полученные результаты.

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

За счет всех вышеперечисленных оптимизаций удалось достичь хорошей производительности алгоритма.

Среда для разработки и тестирования алгоритмов

В ходе работы над проектом была создана Среда для разработки и тестирования алгоритмов проверки пересечений. Эта среда позволяет выполнять следующие действия:

1)      Загрузить из файлов многогранники, для которых будут проверяться столкновения.

2)      Редактировать сцену:

a.  Поместить многогранники на сцену (можно помещать несколько копий одного и того же многогранника).

b.      Удалить многогранник со сцены.. Переместить многогранник.

3)      Сохранить/загрузить сцену.

4)      Выбрать алгоритм для проверки пересечений.

)        Запустить предрасчет; предрасчитанные данные будут записаны в файл.

)        Проверить работу алгоритма: пользователь может перемещать многогранники, пересекающиеся объекты будут подкрашиваться другим цветом.

)        Сравнить алгоритмы по времени работы и потребляемой памяти.

Рис. 10. Среда для разработки и тестирования алгоритмов

В Среде можно выделить три подсистемы, взаимодействующие друг с другом:

1)      Система тестирования

2)      Система плагинов

)        Система визуализации

Среда разрабатывалась командой из трех человек, каждый из членов команды отвечал за одну из подсистем. В качестве языка программирования был выбран C++, для визуализации применяется графическая библиотека OpenGL, для создания графического пользовательского интерфейса используется библиотека FOX Toolkit. Моя задача заключалась в написании Системы плагинов.

Система плагинов

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

Каждый плагин представляет собой динамическую библиотеку, содержащую реализацию одного алгоритма. Система плагинов загружает плагины и предоставляет пользователю возможность выбрать один из алгоритмов. Выбранный алгоритм будет использован для обнаружения пересечений.

Плагин

Все плагины являются реализацией одного общего интерфейса. Для того чтоб написать новый плагин, необходимо реализовать методы этого интерфейса, а именно:

·        void precompute (Polyhedron[] polyhedrons) - этот метод вызывается, когда приходит запрос выполнить предрассчет.

·        bool checkCollision (Polyhedron poly1, Polyhedron poly2) - в этой функции реализуется проверка пересечений двух многогранников. Функция возвращает true, если объекты пересекаются, и false в противном случае. Для проверки могут быть использованы предрасчитанные данные.

·        void load (ifstream file)

void save (ofstream file) - сохранение и загрузка предрасчитанных данных. Процесс предрасчета для некоторых алгоритмов может занимать много времени, поэтому нужна возможность сохранить результат в файл и загрузить эти данные, когда они будут необходимы, вместо того, чтоб вычислять их заново. Формат, в котором хранить предрасчитанные данные, остается на усмотрение разработчика алгоритма.

После того, как все эти функции реализованы, плагин может быть встроен в среду.

Результаты

В ходе работы над проектом были получены следующие результаты:

1)      Разработан и реализован алгоритм построения характеристического многогранника.

2)      Алгоритм был внедрен в среду, и была показана корректность его работы на различных тестовых данных.

)        Алгоритм был применен для проверки пересечений.

)        Разработана и реализована Система плагинов.

)        Результаты работы докладывались на XLIX Международной Научной Студенческой Конференции. Доклад был удостоен диплома III степени.

Рис. 12. Результат работы алгоритма

Перспективы

В перспективе возможно:

1)      Доработать алгоритм построения характеристического многогранника с учетом случая вырожденных скольжений.

2)      Использовать алгоритм для различных геометрических задач: поиска траектории движения по полигональной поверхности, задачи упаковки.

)        Проанализировать возможность применения метода, основанного на характеристических многогранниках, для случая, когда многогранники могут вращаться.

Определения и обозначения

Определения

Многоугольник - геометрическая фигура, состоящая из 3 или более точек плоскости, не лежащих на одной прямой и попарно соединённых не пересекающимися отрезками.

Многогранник - замкнутая поверхность, составленная из многоугольников, а также тело ограниченное такой поверхностью. Многоугольники, из которых составлен многогранник, называются гранями, их стороны - ребрами, а их вершины - вершинами многогранника.

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

Программная среда - программа для компьютера, предоставляющая спектр функций для решения задач определённого типа или разработки решений, или алгоритмов определённого типа.

Плагин (от plug-in) - независимо компилируемый программный модуль, динамически подключаемый к основной программе, предназначенный для расширения и / или использования её возможностей.

Принятые обозначения

В этой работе вектора, вершины, ребра и грани обозначаются маленькими, курсивными, полужирными латинскими буквами, например: v₀, p, e_i, t.

Многогранники и множества обозначаются большими, полужирными латинскими буквами, например: P₁, X.

Скалярное произведение векторов обозначается следующим образом a * b, а векторное - a x b.

Литература

1)   Препарата Ф., Шеймос М. Вычислительная геометрия: введение - М: Мир, 1989.

2)      Куликов А.И. Некоторые задачи вычислительной геометрии. Изогеометрическое сглаживание и геометрический поиск // Труды конференции GraphiCon - Новосибирск, 2005. - P.382-385.

)        Уханов, М.В. Алгоритм построения суммы многогранников, 2001.

4)   P. Hachenberger. Exact Minkowksi sums of polyhedra and exact and efficient decomposition of polyedra in convex pieces, 2007.

5)      Evan Behar, Jyh-Ming Lien. Extracting the Minkowski Sum Boundary from the Reduced Convolution, 2010.

)        Wein R. Exact and efficient construction of planar Minkowski sums using the convolution method, 2006.

7)      Мошкалев П.С. Разработка программного средства для решения задачи взаимного размещения многогранников, 2009.

8)      Terdiman Pierre. Memory-optimized bounding-volume hierarchies, 2001.

9)      Скворцов А.В. Алгоритмы построения триангуляции с ограничениями // Вычислительные методы и программирование, 2002.

10)     Moller T. A fast triangle-triangle intersection test. Journal of. Graphics Tools, 1997.