lect07_14 (Раздаточные материалы)

Компьютерная графикаЛекция 716/17 октября 2014Графический процессГеометрическое моделированиеАлексей Викторович ИгнатенкоЛаборатория компьютерной графики имультимедиаВМК МГУТри части: две вводных + более подробноо геометрическом моделированииЗадача синтеза изображенийГрафический процессГеометрическое моделированиеЗадача синтеза изображений –визуальное представление информацииТекстЗнания,идеиИзображениеОбработка изображений, зрение и графикасвязаны по данным и алгоритмамАнализизображений• Вход:Изображение• Выход:ИзображениеОбработкаизображенийКомпьютерноезрение• Вход:Изображение• Выход:Модель• Вход:Модель• Выход:ИзображениеКомпьютернаяграфикаСинтезизображенийТри части: две вводных + более подробноо геометрическом моделированииЗадача синтеза изображенийГрафический процессГеометрическое моделированиеКомпьютерная графика изучаетмодели и алгоритмы синтезаМодельАлгоритмсинтезаИзображениеГрафический процесс: типовая последовательностьприменения алгоритмовЦветокоррекцияГаммаПолутонированиеГеометрическая модельМодель освещенияМодель анимацииМодельПолучение проекцииЗаливкаАлгоритмсинтезаИзображениеВ геометрическое моделирование входят методыполучения, представления и обработки моделейМетодыпредставлениямоделей(структурыданных)МетодыполучениямоделейМетодыобработкимоделейГеометрическоемоделированиеСуществует три основных способаполучения геометрических моделейРучное моделирование• Пакеты моделирования Maya,AutoCad и т.п.Автоматизированноемоделирование• 3D-сканирование• Реконструкция по фотографиямБиблиотеки моделей• Повторное использование созданныхмоделейАнимация – крайне сложная задача дляручного моделированияРучноемоделированиеСинтезированнаяанимацияЗахват движения(motion capture)Для освещения модели надо иметь модельматериалов и модель источников светаМодельматериаловМодельисточниковсветаМодельосвещенияМатериалы и источники света обычноимеют параметрические моделиМатериалы• Модель отражения/пропускания• Ручное моделирование• Фотографии (или сканы)Источники света• Ручное моделирование• Фотографии (HDR)Алгоритмы синтеза изображений решают задачусоздания изображения по набору моделейГеометрияМатериалыСветАнимацияРезультирующееизображениеЗадача этапа вывода – перевестицифровое изображение в свет• Результирующее изображение выводится в:– Буфер кадра (монитор)• Преобразование изображения в излучение• Гамма-коррекция• Цветокоррекция– Файл• Сжатие изображений или видео– Принтер• Полутонирование и т.п.Три части: две вводных + более подробноо геометрическом моделированииЗадача синтеза изображенийГрафический процессГеометрическое моделированиеМодель – абстрактное представлениесущности реального мира• Модель – это абстрактноепредставление сущности реальногомираМатематическое моделированиефизических, химических процессов ит.п.• Компьютерное моделированиеДанные о физических объектах немогут быть целиком введены вкомпьютерНужно ограничить объем хранимойинформации об объекте• Задача: найти вид модели,наилучшим образом отвечающийрешаемой задачеВ компьютерной графике применяетсягеометрическое моделирование• Моделирование объектовразличной природы спомощью геометрическихтипов данных• Принципы выбора модели– Соответствие поставленнойзадаче– Максимально использоватьвозможности графическойсистемы– Учесть задачи обработки иредактирования моделиСуществует огромное количествогеометрических моделей и их видов•••••••••ВоксельноеТочечное представлениеКонструктивная геометрияКаркасное представлениеГраничное представление первого порядкаГраничные представление высших порядковНа основе изображенийГибридные модели…«Представление» -- синоним модели, ноесть и тонкостиОдин и тот же объект может иметь несколькопредставлений (моделей)Представления могут быть получены как из исходногообъекта, так и путем преобразования другогопредставления объектаобъект 1объект 2Модель 1 Модель 2Модель 3 Модель 4«Представления объекта 1» «Представления объекта 2»Будем рассматривать сплошные телаРассматриваем сплошные тела (solid models)Можно выделить поверхность и объемМодели трехмерных объектовРазличные характеристики модели нужны дляправильного выбора типа моделиСтруктура данныхАлгоритмпостроенияТипичные свойствапредставления(алгоритмы)Количествопамяти,необходимое дляхранения моделиОбластьприменениямоделей в данномпредставленииКаждую модель можно характеризоватьпо набору параметровОбъем/Поверхность• Какие свойства трехмерного объекта описывает модель?Дискретное/Непрерывное• Содержится ли в модели информация о дополнениидискретных данных до непрерывных?Явное/Параметрическое• Способ получения трехмерных координат точек,принадлежащих моделиСистемы координат необходима для любойтрехмерной моделиYYYZXXXZДвухмернаяПравосторонняяЛевосторонняяВоксельная модель – дискретизацияпространства по равномерной сеткеСтруктура– Равномерная сетка, каждыйэлемент которой показывает,если в нем часть объекта– Ячейка называется воксель(voxel = volume element)– Каждый воксель принимаетзначение 0 или 1– Может также задаватьплотность (0-1)Способ получения– Дискретизация трехмерныхданных на равномерной сеткеВоксельная модель: описывает объем• Описывает объем• Дискретное представление:приближение реальногообъекта!• Плохо описываются частиобъекта, не параллельныесторонам воксельного куба• Явное представление• Размер данныхпропорционален кубуразрешения сетки– 1 байт на точку:2000 x 2000 x 2000 = 7,45 Гб !Воксельное представление: типичныеалгоритмыПространственные алгоритмы– Вычисление объема объекта– Нахождение центра масс– Булевы операции ( пересечение, объединение)Плохо работают алгоритмы, требующие понятияповерхности!Октодерево – иерархический вариантвоксельной модели• Рекурсивное разбиениепространства на восемьоктант• Ветвь дерева:– Код = B (черный) - заполнено– Код = W (белый) - пусто– Код = G (серый) – частично• Эти подразбиты на 8 потомковСтруктура данных октодерева: типичнаярекурсивная иерархическая структураstruct OctoTreeNode{BYTE Value;OctoTreeNode* Children[8];};Октодерево применяется для оптимизациивоксельного представления• Свойства:– Позволяет хранить информациютолько о блоках, относящихся кобъекту– Число элементовпропорционально площадиповерхности объекта, т.е.квадрату разрешения– Для разреженных моделейпозволяет уменьшить размер втысячи раз!• Способ получения– Из воксельного представленияили напрямую, черездискретизациюВариант линейной записи 1: пути к листовымузлам• Октанты деревапронумерованы от 0 до 7• Конструирование адресакаждой ветви дерева, кромекорня.• Адрес ветви уровня i –последовательности i чисел от0 до 7 – путь от корня к этойветви• Символ X: если впоследовательности чиселменьше, чем максимальноеразрешение• Линейная запись дерева естьпросто сортированный массивадресов ветвей с кодом"черный"Линейная запись 1: {03,1X,51,53}Линейная запись 1: {03,1X,51,53}Линейная запись 1: {03,1X,51,53}Линейная запись 1: {03,1X,51,53}Линейная запись 1: {03,1X,51,53}Вариант линейной записи 2: обход дерева вглубину• Обход дерева вфиксированномпорядке• Трехсимвольнаязапись– «B»: черная ветвь– «W»: белая ветвь– «(» : серая ветвьЛинейная запись 2:((WWWBWWWWBWWW(WBWBWWWWWWЛинейная запись 2:((WWWBWWWWBWWW(WBWBWWWWWWЛинейная запись 2:((WWWBWWWWBWWW(WBWBWWWWWWЛинейная запись 2:((WWWBWWWWBWWW(WBWBWWWWWWОктодерево часто применятся для хранениявоксельных данных и при визуализации• Удобно для синтеза:– Переменный уровень детализации– Вывод back-to-front• Усложняются операции, требующие информациио смежных ячейках• Сложно с анимацией, нужно перестраиватьдеревоТочечное представление заменяет регулярнуювоксельную сетку на нерегулярную• Наборнеструктурированныхточек• Требования по памятипропорциональныколичеству точек• Дискретное, явноепредставлениеТочечное представление: структура• Массив точек с атрибутами– Атрибуты: положение, цвет,нормаль, размер• Описывает толькопринадлежащие объекту частипространства• Явное хранение координат =>возможное увеличениеразмера• Нет связанности,инциндентности => длявыполнения преобразованийобычно строятсядополнительные структурыданных (октодерево)Конструктивная геометрия: эффективноописывает и поверхность и объем• Структура– Набор базовых примитивов• сфера, куб, цилиндр...– Операции по их комбинированию• Способ получения– Ручное моделирование• Свойства– Описывает объем и поверхность (!)– Непрерывное– ЯвноеЗадается набор операций для базовыхпримитивов• Перенос/поворот/масштабирование• Теоретико-множественные:• Объединение• Разность• ПересечениеПоследовательность операций задаетфинальный объектdiff(union(trans1(Block1),trans2(Block2)),trans3(Cylinder))Разбор последовательности выполненияопераций над теламиdiff(union(trans1(Block1), trans2(Block2)),trans3(Cylinder))Разбор последовательности выполненияопераций над теламиdiff(union(trans1(Block1), trans2(Block2)),trans3(Cylinder))Разбор последовательности выполненияопераций над теламиdiff(union(trans1(Block1), trans2(Block2)),trans3(Cylinder))Разбор последовательности выполненияопераций над теламиdiff(union(trans1(Block1), trans2(Block2)),trans3(Cylinder))Структура данных для конструктивнойгеометрии – направленный ациклическийграф• Дерево из операций и базовыхобъектов• Корень – результирующийобъект• Листья – базовые примитивы• Число потомков равно числуоперандов операции• Из-за повторногоиспользования превращается внаправленный ациклическийграф.Конструктивная геометрия эффективно работает с«объемными» задачами, но также имеет понятиеповерхностиПространственные алгоритмы– вычисление объема объекта– нахождение центра масс– ...Есть понятие поверхности!Основной недостаток – на практике можно построить толькосинтетическиТакже сложно визуализироватьОбъект можно моделировать черезвыделение характерных точек и реберКаркасноепредставлениеiXYZ111121-113-1-114-111511-161-1-17-1-1-18-11-11(1,2)2(2,3)3(3,4)4(5,6)5(5,6)6(6,7)7(7,8)8(8,5)9(1,5)10(2,6)11(3,7)12(4,8)Каркасное представление: неоднозначнаяинтерпретация для случая сплошных телНужна дополнительнаяинформация!Как верноотобразить?Граничное представление содержит не толькокаркас, но граниКусочная аппроксимацияповерхности объектаРассматриваемпредставления первогопорядка: линейнаяинтерполяцияСтруктура данных:вершины + граниГраничные представления различаются по способамхранения информации о гранях и ребрах• Явное представление• Индексированное по вершинам• Индексированное по ребрам• «Крылатое» представлениеЯвное представление хранит списокгранейГрани• Каждая грань – полигон,состоящий изпоследовательностикоординат вершин• Объект состоит из набораграней• Недостатки– Взаимоотношения гранейзаданы неявно– Координаты вершиндублируются– Алгоритмы поискаинцидентных ребертребуют полного перебораf1f2f3f4f5f6Координаты,x1 y1 z1, x2 y2 z2, x3 y3 z3 x4 y4 z4,x6 y6 z6, x2 y2 z2, x1 y1 z1 x5 y5 z5,x7 y7 z7, x3 y3 z3, x2 y2 z2 x6 y6 z6,x8 y8 z8, x4 y4 z4, x3 y3 z3 x7 y7 z7,x5 y5 z5, x1 y1 z1, x4 y4 z4 x8 y8 z8,x8 y8 z8, x7 y7 z7, x6 y6 z6 x5 y5 z5Индексированное по вершинамхранит индексы вершин• Выделение координатвершин в отдельнуюструктуру• С гранямиассоциируются некоординаты вершин, аиндексы в массивекоординат вершин• Недостатки– Аналогично явномупредставлениюВершиныКоординатыГраниВершиныv1x1 y1 z1f1v1 v2 v3 v4v2x2 y2 z2f2v6 v2 v1 v5v3x3 y3 z3f3v7 v3 v2 v6v4x4 y4 z4f4v8 v4 v3 v7v5x5 y5 z5f5v5 v1 v4 v8v6x6 y6 z6f6v8 v7 v6 v5v7x7 y7 z7v8x8 y8 z8Индексированное по ребрам хранитиндексы ребер и индексы вершин• Грани определяютсячерез ребра• Ребра задаютсявершинами• Вершины задаютсяположением впространствеРебВершВершКоордГрнРебраe1v1 v2v1x1 y1 z1f1e1 e2 e3 e4e2v2 v3v2x2 y2 z2f2e9 e6 e1 e5e3v3 v4v3x3 y3 z3f3e10 e7 e2 e6e4v4 v1v4x4 y4 z4f4e11 e8 e7 e3e5v1 v5v5x5 y5 z5f5e12 e5 e4 e8e6v2 v6v6x6 y6 z6f6e12 e11 e10 e9e7v3 v7v7x7 y7 z7e8v4 v8v8x8 y8 z8e9v5 v6e10v6 v7e11v7 v8e12v8 v5«Крылатое» представление связываетграни, ребра, вершины• “Winded-Edge”• Добавляетсяинформация овзаимномрасположении гранейСтруктура данных построена вокругребраstruct Edge{Vertex* X;Vertex* Y;Face* FaceLeft;Face* FaceRight;Edge* LeftPred;Edge* LeftSucc;Edge* RightPred;Edge* RightSucc;};РеброВершиныГраниЛевый обходПравый обходNameBeginEndLeftRightPredSuccPredSuccaXY12bdecПример основной таблицы дляпирамидыEdgeVerticesFacesLeft TraverseRight TraverseNameStartEndLeftRightPredSuccPredSuccaAD31efbcbAB14cafdcBD12abdedBC24ecbfeCD23cdfafAC43dbaeНужны еще две таблицы: для вершин идля реберVertex NameIncident EdgeAaBbCdDeFace NameIncident Edge1a2c3a4bГраничное представление: типичныеалгоритмы•••••Проверка правильности заданияВычисление габаритного объемаВычисление нормали в точкеВычисление кривизны поверхностиНахождение точки пересечения с лучом иликривой• Определение положения точки относительноповерхностиГраничные представления высшихпорядковКонтрольные точки + способ интерполяции 2-гопорядка и выше (полиномы Берштейна, например)Итоги••••Задача синтеза изображенийГрафический процессГеометрическое моделированиеМодели трехмерных объектов–––––Воксельное (+октарное дерево)Точечное представлениеКонструктивная геометрияКаркасное представлениеГраничное представление (явное, индексированное повершинам, ребрам, «крылатое»)– Граничные представление высших порядков.