Задача взаимного размещения многогранников. Построение характеристического многогранника. Система плагинов
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
? v - вершина многогранника P2, f - грань многогранника P1, c1, тАж c3 - вершины f. Вектор n - нормаль грани f. Рассмотрим множество ребер e1, тАж, em инцидентных вершине v. Для каждого ребра ei определим вектор li, начинающийся в вершине v и направленный вдоль ребра ei, то есть li = vi - v, где vi вершина ребра отличная от v. Тогда скольжение вершины v по грани f возможно лишь в том случае, если угол между li и n строго меньше 90о, для i = 1тАж m. В результате такого скольжения выбранная вершина v0, вычерчивает треугольную грань t, получаемую из f путем сдвига на вектор v0 - v, т.е. её вершины задаются следующим образом: pi = ci + (v0 - v), i = 1тАж3.
Стоит отметить, что нормаль полученной грани будет сонаправлена n.
Рис. 1. Скольжение вершины по грани
Грань подвижного многогранника скользит по вершине неподвижного
Пусть v - вершина многогранника P1, f - грань многогранника P2, c1, тАж c3 - вершины f. Возможность скольжения v по f проверяется аналогично предыдущему случаю. В результате скольжения образуется грань t, вершины которой определяются следующим образом: pi = - c3-i + (v0 + v), i = 1тАж3.
Т.е. грань t получена путем отражения всех вершин грани f относительно начала системы координат, в которой они заданы, и сдвига их на вектор v + v0. В отличие от предыдущего случая нормаль грани t, направлена против нормали грани f.
Рис. 2. Скольжение грани по вершине
Ребро подвижного многогранника скользит по ребру неподвижного
Пусть e1 - ребро неподвижного многогранника, e2 - ребро подвижного. Пары вершин a1, a2 и b1, b2 - концы ребер e1 и e2 соответственно. Направляющими векторами v1 и v2 ребра e1 назовем вектора перпендикулярные ребру e1 и направленные внутрь прилегающих к нему граней. Аналогично u1 и u2 направляющие векторы ребра e2. Определим вектор n следующим образом, n = (b2 - b1) x (a2 - a1). Этот вектор задает нормаль плоскости скольжения. Ребро e1 может скользить по ребру e2 лишь в том случае, если двугранные углы, образованные прилежащими к ним гранями, расположены по разные стороны от плоскости скольжения. Иными словами, значения v1*n, v2*n имеют один знак, а u1*n, u2*n - другой. В результате скольжения образуются две треугольные грани t1 и t2, составляющие параллелограмм. Вершины этого параллелограмма - точки:
p1 = a1 - b1 + v0
p2 = a1 - b2+ v0
p3 = a2 - b2+ v0
p4 = a2 - b1+ v0
Для того чтобы нормаль граней была направлена вовне характеристического многогранника, необходимо задать правильный обход вершин. Введем вектор n0 = n1 + n2, где n1 и n2 нормали граней прилежащих к ребру e1, и вектор np = (p4 - p3) x (p3 - p2).
Если вектора n0 и np сонаправлены, то t1 = (p1, p2, p3), t2 = (p1, p3, p4), в противном случае t1 = (p3, p2, p1), t2 = (p4, p3, p1).
Рис. 3. Скольжение ребра по ребру
После проверки всех возможных случаев скольжения и построения соответствующих им граней алгоритм завершает свою работу. Результатом его работы является построенный характеристический многогранник, все грани которого - треугольники.
Оценка вычислительной сложности
Пусть V1, E1, F1 - количество вершин, ребер и граней многогранника P1, а V2, E2, F2 - те же характеристики для многогранника P2. При построении характеристического многогранника выполняется V2*F1 проверок скольжений вершины по грани, F2*V1 проверок скольжений грани по вершине и E1*E2 проверок скольжений ребра по ребру. Таким образом, вычислительная сложность алгоритма пропорциональна величине T=V2*F1 + F2*V1 + E1*E2. Поскольку для каждого из многогранников P1, P2 выполнены соотношения Ei < 3*Vi, Fi < 2*Vi, то T < 13*<