Задача взаимного размещения многогранников. Построение характеристического многогранника. Система плагинов
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
i>V1*V2. Значит, вычислительная сложность алгоритма равна O(V1*V2).
Проверка пересечений с помощью характеристических многогранников
Пусть дано множество многогранников P1, тАж, Pn. Необходим метод, позволяющий для двух произвольных многогранников Pi, Pj быстро определить, пересекаются они или нет. Предлагается следующее решение этой задачи:
1.Для каждой пары многогранников выделяем подвижный многогранник, фиксируем точку v0 и строим характеристический многогранник. Не важно, какой именно многогранник будет подвижным. При проверке пересечений имеет значение положение многогранников относительно друг друга.
2.Для характеристических многогранников строим структуры для геометрического поиска.
.Чтобы проверить пересечение двух многогранников, вычисляем координату фиксированной точки в системе координат неподвижного многогранника и с помощью структуры для геометрического поиска определяем, лежит ли точка внутри характеристического многогранника. Если лежит то многогранники пересекаются, иначе не пересекаются.
Пункты 1 и 2 должны быть выполнены один раз на этапе предрасчета. За счет этого метод позволяет выполнять проверку пересечений большого количества сложных объектов в режиме реального времени.
Построение характеристического многогранника, при условии, что исходные объекты необязательно выпуклые
Постановка задачи звучит аналогично предыдущему случаю с той разницей, что многогранники могут быть невыпуклыми. Характеристический многогранник, который нужно построить, также необязательно будет выпуклым.
Построение характеристического многогранника состоит из 3-х шагов:
1)Дополнительная проверка вершин и ребер.
2)Построение граней.
)Удаление частей граней.
Дополнительная проверка вершин и ребер
Перед тем как начать строить грани для каждой вершины и каждого ребра исходных многогранников производится дополнительная проверка, которая отсеивает те вершины и ребра, которые заведомо не могут участвовать в скольжениях.
Дополнительная проверка для вершин
Пусть проверяем вершину v. e1, тАж, em - ребра инцидентные v. Для каждого ребра ei определим вектор li = vi - v, где vi вершина ребра отличная от v. Введем вектор l = l1 + тАж + lm. Пусть ni,0, ni,1 - нормали граней прилежащих к ei. Определим вектор n = n1,0 + n1,1 + тАж + nm,0 + nm,1. Тогда если угол между векторами n и l меньше 90о, то вершина v утоплена и не может участвовать ни в одном из скольжений.
Рис. 4. Утопленная вершина
Дополнительная проверка для ребер
Пусть проверяем ребро e. Введем вектор u = u1 + u2 (где u1, u2 - направляющие вектора ребра e) и вектор n = n1 + n2 (n1, n2 - нормали прилежащих к e граней). Тогда если угол между векторами n и u меньше 90о, то ребро e утоплено, и не будет рассматриваться при проверке скольжений.
Рис. 5. Утопленное ребро
Построение граней
На этом шаге строятся грани характеристического многогранника, аналогично тому, как это делается для случая выпуклых многогранников. Естественно, рассматриваются только те вершины и ребра, которые прошли проверку на шаге 1.
Удаление частей граней
Полученные грани не обязательно будут гранями характеристического многогранника. Допустим, при одном из скольжений точка v0 описала грань f. В отличие от случая выпуклых многогранников сейчас возможна ситуация, когда во время этого скольжения подвижный многогранник пересекается с неподвижным. Часть грани, которую описывает v0, когда многогранники пересекались нужно удалить. Ключевой момент моей работы - это способ, которым удаляются такие части граней.
Части граней, которые необходимо удалить, находятся внутри нужного нам характеристического многогранника (рис 6). Это следует из свойства: точка v0 находится внутри характеристического многогранника исходные многогранники пересекаются. Остальные части граней образуют поверхность характеристического многогранника.
Рис. 6. Части граней, которые нужно удалить
Грани, построенные на предыдущем шаге, могут пересекаться друг с другом. Грань может лежать частично внутри характеристического многогранника, частично на его поверхности лишь в том случае, если она пересекается с какой-либо другой гранью. Будем разрезать грань пересекающими ее гранями (как именно, будет описано позже). После того, как все такие разрезания будут выполнены, не останется ни одной пары пересекающихся граней. Это значит, что каждая из полученных граней либо полностью лежит на поверхности характеристического многогранника, либо полностью лежит внутри. Грани, которые лежат внутри нужно удалить.
Таким образом, алгоритм удаления частей граней состоит из следующих шагов:
1)Поиск пересекающихся граней
2)Разрезание граней
)Удаление гране?/p>