Построение триангуляции поверхности заметаемого объёма при движении произвольного множества треугольников Swept Volume Construction Problem. - презентация

1 Построение триангуляции поверхности заметаемого объёма при движении произвольного множества треугольников Swept Volume Construction Problem

2 План доклада Предварительные определения Постановка задачи Вращение пространства с помощью кватернионов Поэтапное описание алгоритма Сопутствующие алгоритмы на графах Применение алгоритма на практике

3 Постановка задачи – предварительные определения Треугольник – Ориентация - Правильная триангуляция

4 Постановка задачи – предварительные определения Пиксель – Воксель – Воксельное представление

5 Постановка задачи – предварительные определения Кватернион – Преобразование пространства- Изоморфизм i * j = k Q = { x 0 + x 1 * i + x 2 * j + x 3 *k, x i } i 2 = - 1 k 2 = - 1 j 2 = - 1

6 Постановка задачи – предварительные определения Граф – Дерево- Цикл

7 Общая постановка задачи Необходимо построить правильную триангуляцию поверхности объёма, заметённого при перемещении произвольного множества треугольников Т вдоль заданной траектории М при заданной допустимой погрешности E

8 Общая постановка задачи

9 Результат работы алгоритма

10 Вращение пространства с помощью кватернионов

11 Связь с матрицами движения

12 Поэтапное описание алгоритма Построение вексельного представления заметаемого объёма Триангуляция вексельного представления Алгоритм состоит из двух относительно несвязных частей :

13 Построение вексельного представления Метод двумерных проекций

14 Построение вексельного представления

15

16

17 Триангуляция вексельного представления Получения базовой триангуляции Выравнивание Уменьшение количества треугольников Обеспечение положительной погрешности

18 Получения базовой триангуляции

19 Выравнивание

20 Уменьшение количества треугольников

21 Результат работы алгоритма

22 Вычислительная сложность алгоритма Алгоритм построения вексельного представления имеет квадратичную сложность по времени и расходу памяти Триангуляция имеет кубическую сложность по времени и памяти

23 Сопутствующие алгоритмы на графах Алгоритмы поиска в ширину на триангуляции Алгоритм выделения циклов из графа

24 Применение алгоритма на практике Автомобилестроение Станкостроение Медицина Дизайн

25 Применение алгоритма на практике

26 Конец Спасибо за внимание! Вопросы?