31 марта Графический процесс. Геометрическое моделирование Алексей Викторович Игнатенко

31 марта На лекции Типовая схема графической обработки: графический процесс Геометрическое моделирование Системы координат Разновидности моделей и операции над моделями в различных представлениях

31 марта Графический процесс

31 марта Графический процесс

31 марта Графический процесс: Геометрическое моделирование

31 марта Графический процесс: 3D сканеры $25000 $

31 марта Графический процесс: Трехмерная анимация

31 марта Графический процесс: Материалы

31 марта Графический процесс: Освещение

31 марта Графический процесс: Синтез изображений (экранизация)

31 марта Графический процесс: Хранение и вывод изображений

31 марта Геометрическое моделирование

31 марта Понятие о моделировании Модель – это абстрактное представление сущности реального мира Математическое моделирование физических, химических процессов и др. Компьютерное моделирование Данные о физических объектах не могут быть целиком введены в компьютер Необходимо априори ограничить объем хранимой информации об объекте Задача моделирования найти вид модели, наилучшим образом отвечающий решаемой задаче

31 марта Геометрическое моделирование В компьютерной графике используется геометрическое моделирование моделирование объектов различной природы с помощью геометрических типов данных Выбор модели максимально использовать возможности графической системы учесть задачи обработки и редактирования модели

31 марта Представления объектов Представление объекта = модель объекта Один и тот же объект может иметь несколько представлений (моделей) Представления могут быть получены как из исходного объекта, так и путем преобразования другого представления объекта объект 1 объект 2 Модель 1Модель 2Модель 3Модель 4 «Представления объекта 1»«Представления объекта 2»

31 марта Классификация Рассматриваем сплошные тела Характеристики модели: структура данных; алгоритм построения; количество памяти, необходимое для хранения модели; типичные свойства представления (алгоритмы); область применения моделей в данном представлении. Критерии классификации представлений Объем/Поверхность Какие свойства трехмерного объекта описывает модель? Дискретное/Непрерывное Содержится ли в модели информация о дополнении дискретных данных до непрерывных? Явное/Параметрическое Способ получения трехмерных координат точек, принадлежащих модели

31 марта Системы координат

31 марта Воксельное представление Структура Равномерная сетка, каждый элемент которой показывает, если в нем часть объекта Ячейка называется воксель (voxel = volume element) Каждый воксель принимает значение 0 или 1 Может также задавать плотность (0-1) Способ получения Дискретизация трехмерных данных на равномерной сетке

31 марта Воксельное представление: свойства Описывает объем Дискретное представление: приближение реального объекта! Плохо описываются части объекта, не параллельные сторонам воксельного куба Явное представление Размер данных пропорционален кубу разрешения сетки 1 байт на точку: 2000 x 2000 x 2000 = 7,45 Гб !

31 марта Воксельное представление: типичные алгоритмы Пространственные алгоритмы вычисление объема объекта нахождение центра масс... булевы операции ( пересечение, объединение) Плохо работают алгоритмы, требующие понятия поверхности!

31 марта Воксельное представление: Октодерево Разбиение пространства на восемь октант, которое представляется деревом. Упорядоченно! Располагается вокруг начала его локальной системы координат Октанты первого уровня совпадают с октантами системы координат. Ветвь дерева: Код Код = «черный» Пространство заполнено, лист Код = "белый« Пространство пустое, лист Код = "серый" область пространства частично пуста и частично заполнена. 8 ссылок указывают на подразбиение данной области. Восемь указателей на восемь потомков, пронумерованных от 0 до 7

31 марта Октодерево: свойства Применяется для оптимизации воксельного представления Свойства: Позволяет хранить информацию только о блоках, относящихся к объекту Число элементов пропорционально площади поверхности объекта, т.е. квадрату разрешения Для разреженных моделей позволяет уменьшить размер в тысячи раз! Способ получения Из воксельного представления или напрямую, через дискретизацию

31 марта Линейная запись октодерева 1 Октанты дерева пронумерованы от 0 до 7 Конструирование адреса каждой ветви дерева, кроме корня. Адрес ветви уровня i – последовательности i чисел от 0 до 7 – путь от корня к этой ветви Символ X: если в последовательности чисел меньше, чем максимальное разрешение Линейная запись дерева есть просто сортированный массив адресов ветвей с кодом "черный" Пример: {03,1X,51,53}

31 марта Линейная запись октодерева 2 Обход дерева в фиксированном порядке, например, слева направо, сверху вниз (в глубину). Трехсимвольный алгоритм: «B»: черная ветвь «W»: белая ветвь «(» : внутренняя ветвь Пример: ((WWWBWWWWBWW W(WBWBWWWWWW

31 марта Октодерево: типичные алгоритмы Удобно для синтеза: Переменный уровень детализации Вывод back-to-front Усложняются операции, требующие информации о смежных ячейках

31 марта Точечное представление Набор неструктурированных точек Количество памяти, необходимое для хранения модели пропорционально количеству точек (дискретов, sample) Дискретное, явное представление

31 марта Точечное предсталение: структура Массив точек с атрибутами Атрибуты: положение, цвет, нормаль, размер Описывает только принадлежащие объекту части пространства Явное хранение координат => возможное увеличение размера (для «плотных» моделей)

31 марта Точечное представление: свойства, типичные алгоритмы Эффективно аппроксимирует форму объекта По объему памяти обычно более эффективно чем воксельное, но менее эффективно, чем октодерево (или аналогичная структура) Нет связанности, инциндентности => для выполнения преобразований обычно строятся дополнительные структуры данных (октодерево)

31 марта Конструктивная геометрия Структура Набор базовых примитивов сфера, куб, цилиндр... Операции по их комбинированию Способ получения Ручное моделирование Свойства Описывает объем и поверхность (!) Непрерывное представление представление Явное представление

31 марта Конструктивная геометрия: операции с телами Операции Перенос/поворот/масштабирование Теоретико-множественные: Объединение Разность Пересечение

31 марта Конструктивная геометрия: операции с телами 2 diff(union(trans1(Block1), trans2(Block2)), trans3(Cylinder))

31 марта Конструктивная геометрия: структура данных Дерево из операций и базовых объектов Корень – результирующий объект Листья – базовые примитивы Число потомков равно числу операндов операции Из-за повторного использования превращается в направленный ациклический граф.

31 марта Конструктивная геометрия: типичные алгоритмы Пространственные алгоритмы вычисление объема объекта нахождение центра масс... Есть понятие поверхности!

31 марта Каркасное представление iXYZ (1,2)2(2,3)3(3,4) 4(5,6)5 6(6,7) 7(7,8)8(8,5)9(1,5) 10(2,6)11(3,7)12(4,8)

31 марта Каркасное представление: неоднозначная интерпретация Нужна дополнительная информация!

31 марта Грани и ребра Грани (Faces) 1 {A,B,D} 2 {B,C,D} 3 {A,C,D} 4 {A,B,C} Ребра (Edges) a (A,D) b (A,B) …..

31 марта Поверхность Две поверхностиОдна поверхность

31 марта Граничное представление Кусочная аппроксимация поверхности объекта Рассматриваем представления первого порядка (линейная интерполяция) - грани Структура данных: вершины + грани

31 марта Разновидности граничных представлений Различаются по способам хранения информации о гранях и ребрах Явное представление Индексированное по вершинам Индексированное по ребрам Крылатое представление

31 марта Граничное представление: Явное представление Каждая грань – полигон, состоящий из последовательности координат вершин Объект состоит из набора граней Недостатки взаимоотношения граней заданы неявно координаты каждой вершины появляются столько раз, сколько граней имеют эту вершину. Алгоритмы поиска инцидентных ребер требуют полного перебора

31 марта Граничное представление: Индексированное по вершинам Выделение координат вершин в отдельную структуру С гранями ассоциируются не координаты вершин, а индексы в массиве координат вершин Недостатки Аналогично явному представлению ВершиныКоординатыГраниВершины v1x1 y1 z1f1v1 v2 v3 v4 v2x2 y2 z2f2v6 v2 v1 v5 v3x3 y3 z3f3v7 v3 v2 v6 v4x4 y4 z4f4v8 v4 v3 v7 v5x5 y5 z5f5v5 v1 v4 v8 v6x6 y6 z6f6v8 v7 v6 v5 v7x7 y7 z7 v8x8 y8 z8

31 марта Граничное представление: Индексированное по ребрам Грани определяются через ребра Ребра задаются вершинами Вершины задаются положением в пространстве РебВерш КоордГрнРебра e1v1 v2v1x1 y1 z1f1e1 e2 e3 e4 e2v2 v3v2x2 y2 z2f2e9 e6 e1 e5 e3v3 v4v3x3 y3 z3f3e10 e7 e2 e6 e4v4 v1v4x4 y4 z4f4e11 e8 e7 e3 e5v1 v5v5x5 y5 z5f5e12 e5 e4 e8 e6v2 v6v6x6 y6 z6f6e12 e11 e10 e9 e7v3 v7v7x7 y7 z7 e8v4 v8v8x8 y8 z8 e9v5 v6 e10v6 v7 e11v7 v8 e12v8 v5

31 марта Граничное представление: Крылатое представление Добавляется информация о взаимном расположении граней

31 марта Граничное представление: типичные алгоритмы Проверка правильности задания Вычисление габаритного объема Вычисление нормали в точке Вычисление кривизны поверхности Нахождение точки пересечения с лучом или кривой Определение положения точки относительно поверхности

31 марта Граничные представления высших порядков Контрольные точки + способ интерполяции 2-го порядка и выше (полиномы Эрмита, например)

31 марта Литература по теме Алексей Игнатенко. Геометрическое моделирование сплошных тел. Online- журнал «Графика и Мультимедиа» odelirovanie_sploshnyih_tel.html odelirovanie_sploshnyih_tel.html Алексей Игнатенко. Однородные координаты. Online-журнал «Графика и Мультимедиа»

31 марта Итоги Графический процесс Геометрическое моделирование Представления трехмерных данных Воксельное (+октарное дерево) Точечное представление Конструктивная геометрия Каркасное представление Граничное представление (явное, индексированное по вершинам, ребрам, крылатое) Граничные представление высших порядков