Компьютерная графика

Программа курса «Компьютерная графика».

1.

Организационно-методический раздел

1.1 Название курса Компьютерная графика Направление – 552800 Информатика и вычислительная техника. Раздел – общепрофессиональные дисциплины. Компонент – федеральный. 1.2 Цели и задачи курса Основная цель курса: ознакомить студентов с основными задачами машинной (или компьютерной) графики, включая задачи реалистической визуализации и анимации, подходами к их решению, алгоритмами их решения, с необходимыми сведениями из вычислительной геометрии и геометрического моделирования: конструирование кривых и поверхностей, модельные и видовые координатные преобразования, построение полигональных сеток и т.д. В целом материал курса ориентирован на практическое усвоение: студент должен уметь программировать графические приложения в среде Windows, осуществляющих растеризацию кривых и многоугольников, клиппирование плоских областей, визуализацию объемных плотностей, визуализацию научных данных, динамические графические приложения. 1.3 Требования к уровню освоения содержания курса Студент должен понимать основные алгоритмы, применяемые в современных графических редакторах и графических программных средствах, их возможности и ограничения. Кроме того студенты должны уметь практически применить полученные знания при необходимости разработки соответствующих графических функций в прикладных программах. 1.4 Формы контроля Итоговый контроль. Для контроля освоения дисциплины учебным планом предусмотрены дифференциальные зачеты в каждом из двух семестров. Текущий контроль. В течение семестра выполняются практические работы в виде графических приложений в среде Visual Studio 6 и Windows: 7 заданий в 1-ом семестре и 3 задания во 2-ом семестре. Выполнение указанных видов работ является обязательным для всех студентов, а результаты текущего контроля служат основанием для выставления оценок в ведомость контрольной недели на факультете. 2

Содержание дисциплины

2.1 Новизна Предлагаемый специальный курс является новым. Большинство курсов по машинной (или компьютерной) графике, преподаваемым в технических ВУЗах, посвящено изучению работе с тем или иным графическим редактором типа 3DStudio или AutoCAD. В отличие от них данный курс посвящен преподаванию алгоритмических основ машинной графики. Разница примерно такая же как между обучением работы на станке и обучением тому как сделан этот станок. Аналогично данному построены курсы в небольшом числе ВУЗов страны, например, на факультете ВМиК МГУ. За рубежом на факультетах типа Computer Science компьютерная графика изучается достаточно глубоко 1

как теоретически, так и практически. Например, в университетах США компьютерной графике посвящается до 6 семестров. В рамках этого курса была разработана методика преподавания динамической трехмерной графики и программная система SmogDX/3D для поддержки методики. 2.2

Тематический план курса

Количество часов Лаборатор Самостояте Наименование разделов и Лекци Семина ль-ная тем и ры ные работа работы Введение 2 Создание графических 2 4 приложений с использованием Graphical Device Interface Пиксельные области 2 4 Растеризация 1 алгебраических кривых Алгоритмы 2 6 клиппирования многоугольников Визуализация в научных 2 6 вычислениях Аппроксимация полутонов 2 2 Фильтрация изображений 2 2 Визуализация объемных 2 4 плотностей Элементы вычислительной 2 геометрии Преобразования координат 5 6 Конструирование кривых с 2 локальной модификацией Конструирование 4 1 параметрических поверхностей Полигональные сетки и 2 1 текстуры Введение в трехмерную 2 графику Локальная модель 2 4 освещенности и закраска Простейшая трассировка 2 4 лучей Алгоритм обратной 3 8 рекурсивной лучевой трассировки Методы ускорения 3 лучевой трассировки Метод световых сеток 2 Введение в DirectX и 2 SmogDX/3D Основной объект сцена 2 2 Фреймы в SmogDX/3D 2 3 Материал поверхности 3 3

Всег о Часо в 2 6

6 1 8 8 4 4 6 2 11 2 5 3 2 6 6 11 3 2 2 4 5 6 2

Программирование динамики объектов сцены Создание сложных динамических приложений Программирование на OpenGL Уравнение визуализации Итого по курсу:

3

4

7

2

2

4

4

6

10

4 68

4 0 72

0

140

2.3 Содержание отдельных разделов и тем Введение Цели и задачи курса. Широкое определение компьютерной графики (КГ), основные разделы: Иллюстративная КГ (ИКГ), распознавание образов, обработка изображений. Основные задачи ИКГ: методы графического представления данных, алгоритмы, языки КГ, графические программные средства. Графический стандарт ГКС. Сегментированный дисплейный файл, сегмент, примитивы вывода, атрибуты. Примитивы и устройства ввода. Режимы ввода: опрос, запрос, событие. Графические метафайлы. Создание графических приложений с использованием Graphical Device Interface Краткий курс работы в среде Windows Visual C++ 5 или 6. Создание графических приложений с интерфейсом Single Document/View с использованием Graphical Device Interface. Правила сдачи задач по электронной почте. Критерии для выставления оценок за курс. Пиксельные области (ПО) а) 4-связные и 8-связные ПО; б) внутренне определенные ПО, внутренне заполняющие алгоритмы; в) гранично определенные ПО, гранично заполняющие алгоритмы; г) рекурсивный алгоритм, span-алгоритм; д) заполнение ПО шаблоном; е) аффинные преобразования над ПО. Хранение изображений (растров) в файлах. ВМР-файл. Растеризация алгебраических кривых Задача растеризации алгебраических кривых. Алгоритм Брезенхэма для отрезков. Идея алгоритма Брезенхэма для растеризации окружностей. Алгоритмы клиппирования многоугольников Многоугольники, определения. Ориентированные многоугольники. Характеристическая функция. Растеризация многоугольников (идея). Алгоритм растеризации треугольника на основе алгоритма Брезенхэма. Клиппирование многоугольников: алгоритм СазерлендаХоджмана, алгоритм Вейлера-Азертона. Теоретико-множественные операции (ТМО) над многоугольниками. Понятие регуляризованных ТМО, схема алгоритма для регуляризованных объединения, пересечения и разности.

Визуализация в научных вычислениях Что изучается по графику функции. Графические представления функций одной, двух, трех и более переменных. Методы понижения размерности. Задача "Изолинии", задача "Векторные поля", задача "Лица Чернова". Перевод координат: вещественные <=> растровые. Аппроксимация полутонов Аппроксимация полутонов: за счет увеличения пространственного разрешения и без увеличения. Матрицы дизеринга. Алгоритм упорядоченного возмущения, алгоритм и рекуррентное соотношение для матриц. Алгоритм Флойда-Стайнберга. Дизеринг цветных 3

изображений. Перевод цветного изображения в черно-белое. Пересчет на удвоенное разрешение. Фильтрация изображений Гамма монитора, гамма-коррекция, яркость, контраст. Пересчет (увеличение до 16 бит при промежуточных вычислениях). Антиалиасинг. Основная идея (в пикселе часть объекта мира). Алиасинг анимаций (по времени). Регуляризация функций. Сглаживающий фильтр. Запись ядра (матрицы) бокс-фильтра. По-пиксельные операции. Основные задачи обработки изображений: коррекция изображения, улучшение изображения, структурный анализ. Оператор Робертса, дифференцирование, алгоритм, порог. Что будет, если взять значение порога больше (меньше)? Примеры популярных фильтров: сглаживание, подчеркивание краев, тиснение, повышение резкости, акварелизация, медианный фильтр. Что делать, если интенсивность получается меньше 0 или больше 255? А что делать если цветные изображения? Для сглаживающих, для дифференцирующих? Композиция изображений, альфа-канал. Визуализация объемных плотностей (ОП) Что такое ОП? Простейшие модели визуализации ОП: функция передачи прозрачностью, функция передачи цветом. Оптическая модель взаимодействия света с ОП (скалярным полем). Только поглощение. Только эмиссия. Поглощение + эмиссия. Случай раздельного назначения параметров поглощения и эмиссии. Случай модели частиц. Формулы приближенного вычисления. Элементы вычислительной геометрии Точка, вектор, расстояние на плоскости и в 3Д, .... Уравнения отрезка на плоскости и в 3Д: деление 1, параметрическое. Пересечение отрезков на основе параметрической формы. Уравнения луча на плоскости и в 3Д: параметрические, с направляющим вектором. Уравнение прямой на плоскости как линейное уравнение. Нормаль. Расстояние до точки. Функции угла между векторами, лучами, прямыми. Уравнение плоскости в 3Д как линейное уравнение. Нормаль. Расстояние до точки. Барицентрические координаты (отрезок, треугольник, тетраэдр). Деление единицы. Выпуклая оболочка множества точек. Преобразования координат Понятия модельных, видовых, анимационных преобразований. Векторная алгебра, базисы. Линейные и аффинные преобразования. Сдвиг, масштабирование и поворот на плоскости. Матричные записи для линейных. Задача поворота относительно точки (невозможно представить одной матрицей из-за сдвига). Примеры задания графики в языке PostScript. Однородные координаты и 2Д преобразования. Соглашения о записи вектора: строка / столбец. Запись и применение преобразований. Левосторонняя и правосторонняя СК. Положительное вращение вокруг осей. Однородные координаты и 3Д преобразования. Представление поворотов через углы Эйлера. Преобразование твердого тела. Из чего состоит матрица? Поворот вокруг произвольной оси. Кватернионы. Сферическая интерполяция. Видовое преобразование: перспективное и параллельное проецирование. Пирамида видимости (POV), видимый объем. Матрицы проецирования, вывод. Преобразование видимого объема к полукубу. Алгоритм Z-буфера. Применение буфера глубины. Конвейер преобразования координат: модельные СК – мировая СК – СК камеры – полукуб – клиппирование – плоскость изображения – порт вывода. Преобразование координат через базисы. Задание камеры. Конструирование кривых с локальной модификацией Кривизна и кручение. Параметрические кривые на плоскости и в пространстве. Метод Эрмита, метод Безье. Геометрические свойства отрезка кривой Безье. В-сплайны. Геометрические свойства В-сплайновой кривой. Сопряжение участков кривых (Эрмит, Безье). Геометрическая и параметрическая непрерывности. Морфинг кривых. 4

Конструирование параметрических поверхностей Параметрические поверхности. Параметрические линии на поверхностях и касательные к ним. Нормаль к поверхности. Пример задания уравнения для пути фрезы. Конструирование участков поверхностей. Билинейная функция. Линейчатая поверхность, построенная на опорных кривых. Участок поверхности по методу Кунса. Участок поверхности по методу Эрмита. Участок поверхности по методу Безье. Геометрические свойства. В-сплайны. Сшивка двух участков поверхности. Суперквадрики. Особые случаи параметризации. Поверхности вращения. Другие моделирующие преобразования: скручивание, экструзия и т.п. Морфинг поверхностей. Полигональные сетки и текстуры Полигонализация поверхностей. Фактура: текстура, bump mapping. Пирамидальная интерполяция. Выборка: Nearest, Linear, MIPMAP. Текстурные системы координат. Способы покрытия: flat, cylindrical, spherical, chrome. Пример неверного задания сетки куба для текстурирования. Введение в трехмерную графику Цели и задачи курса. Реалистическая визуализация. Введение, исторический обзор методов и аппаратных возможностей. Проволочные представления (Wireframe). Алгоритм марширующих кубиков для построения изоповерхностей. Удаление невидимых линий. Алгоритм подвижного горизонта. Очерки или линии силуэта. Локальная модель освещенности и закраска Упрощенная модель зрения (или сведения из психофизиологии – колбочки, палочки, цвет). Полосы Маха. Диапазон различаемых яркостей. Локальная модель освещенности, рассеянный свет, диффузное отражение, зеркальное отражение. Закраска по Гуро, закраска по Фонгу. Полигональные приближения гладких поверхностей. Модель Торренса-Спэрроу. Простейшая трассировка лучей Основные элементы сцены. Камера. Отраженный и преломленный лучи. Нахождение пересечений луча с основными элементами сцены: а) сфера; б) бокс; в) плоский многоугольник в пространстве г) треугольник. Алгоритм обратной рекурсивной лучевой трассировки Схема алгоритма. Правила ограничения дерева трассировки. Методы повышения качества изображений (удаление лестничного эффекта) – рендеринг на субпиксельном уровне, фильтрация. Методы ускорения лучевой трассировки Пространственные структуры данных: иерархические ограничивающие объемы (боксы, сферы), сетки, иерархические сетки, октодеревья, kd-деревья. Достоинства и недостатки этих структур при изображении динамических сцен. Кластеризация источников света. Метод световых сеток Недостатки лучевой трассировки – отсутствие диффузных переотражений. Компонент рассеянного света. Световые сетки для прямой освещенности. Тени. Мягкие тени. Введение в DirectX и SmogDX/3D Общие сведения об системе DirectX. Общие сведения об объектно-ориентированной системе SmogDX: сцена (основной объект), камера, порт вывода, мировая система координат, фреймы, модельная система координат, геометрические элементы, источники света, материалы, текстуры, анимации. Основной объект – сцена Методы класса CD3DMainObject. Пульс – динамика сцены. 5

Фреймы в SmogDX/3D Класс CD3Dframe. Иерархическая структура фреймов. Управление фреймами на основе однородных преобразований координат. Создание геометрии сцены (полигональные сетки). Окрашивание поверхностей сцены, применение полупрозрачных цветов. Динамика – поступательная и вращательная скорости фрейма. Основные методы класса. Программирование геометрических классов. Создание простейшего приложения. Материал поверхности Класс CD3DMaterial. Расчет освещенности в точке в зависимости от материала. Методы класса. Приписывание материала фрейму. Класс CD3DTexture. Понятие текстуры, текстурные координаты. Виды покрытий. Текстурирование поверхностей (сеток) сцены. Декалы или спрайты, класс CD3DDecal. Размещение изображения фона на порту вывода. Программирование динамики объектов сцены Использование скоростей фрейма. Простейший морфинг – изменение положения вершин в сетках. Класс CD3DAnimation – создание сценариев поведения фреймов. Создание сложных динамических приложений Указание мышью на трехмерные объекты сцены. Программирование теней. Инструменты для создания динамических интерактивных приложений в среде SmogDX. Программирование на OpenGL Совпадающие и различающиеся характеристики OpenGL и SmogDX или OpenGL и DirectX. Создание приложений на OpenGL в среде Windows. Уравнение визуализации Уравнение визуализации (rendering equation) – уравнение баланса освещенности в сцене. Особенности лучевой трассировки методом Монте-Карло. Диффузные сцены. Излучательность (radiosity), уравнение излучательности. Расчет изображения сцены методом излучательности. Методы расчета коэффициентов формы: полукуб, МонтеКарло. 2.4

Перечень примерных контрольных вопросов и заданий для самостоятельной работы Для практического усвоения материала студентам предлагается самостоятельно разработать в среде VisualStudio 6.0 на языке C++ графические приложения типа Single Document/View из предлагаемого списка. По всем заданиям студентам предлагаются файлы с формулировками, требованиями и примерными решениями. По материалу 1 семестра предлагаются следующие задания. 1. Освоить программирование в среде VisualStudio 6.0 на языке C++ графических приложений типа Single Document/View. 2. Задача PixDom. Работа с пиксельными областями, программирование алгоритмов заливки. 3. Задача Clip. Программирование алгоритмов клиппирования многоугольников на плоскости. 4. Задача Izo. Разработка программы построения изолиний и цветотоновой карты для функции двух переменных. 5. Задача Vector. Разработка программы построения карты векторных полей. 6. Задача DitherFilter. Программирование простейших фильтров для полноцветных изображений. 7. Задача Fog. Программирование алгоритма визуализации объемных плотностей. 8. Задача Morph. Программирование морфинга параметрически заданных кривых. 9. Задача Wire. Изображение функции двух переменных в виде проволочной модели поверхности. Применения преобразований в однородных координатах (модельные 6

преобразования, преобразования камеры, клиппирование по полукубу, преобразование в экранные координаты). 10. Задача ParWire. Изображение параметрической поверхности в виде проволочной модели поверхности. Применения преобразований в однородных координатах (модельные преобразования, преобразования камеры, клиппирование по полукубу, преобразование в экранные координаты). По материалу 2 семестра предлагаются следующие задания. Задание 1. Разработать программу, реализующую алгоритм рекурсивной лучевой трассировки для визуализации пространственных сцен. Выполняется в 3 этапа: 1. Программа выбора ракурса. Создается простая сцена, состоящая из 1-3 примитивов. Минимальный набор примитивов: плоскость, куб, сфера. Вычисляется габаритный бокс сцены. Пользователь при помощи мыши осуществляет повороты и перемещения бокса для достижения требуемого ракурса. 2. Разработать библиотеку функций, вычисляющих пересечение луча со сферой, с боксом, с плоским выпуклым многоугольником в пространстве. Разработать функции, вычисляющие: нормальный вектор к примитиву в указанной точке, отраженный вектор, преломленный вектор. Для тестирования предлагается унифицированный формат файла. 3. Разработать программу лучевой трассировки на основе программы, выполненной на этапе 1, и библиотеки функций, выполненной на этапе 2. Характеристики программы: а) возможен выбор ракурса изображения сцены в интерактивном режиме (см. этап 1), разрешение изображения определяется клиентской областью окна приложения; б) чтение описания сцены из файла (унифицированный формат); в) все действия выполняются с использованием библиотеки функций, разработанных на этапе 2; г) регулируется глубина дерева трассировки (от одного до трех отражений); д) один из объектов сцены должен быть в движении – имитация смазывания изображения; е) включение/выключение гамма-коррекции. Задание 2. Разработать динамическое приложение, используя систему классов SmogDX. Выполняется в 3 этапа: 1. Простейшее приложение. Разработать собственный геометрический класс. 2. Разработать сценарий анимационного приложения. Запрограммировать геометрические элементы и анимацию элементов сцены. Источники освещения. 3. Применить текстурирование объектов сцены, применить 2-3 материала, использовать 1-2 тени, использовать указание на изображение трехмерного объекта. Задание 3. Разработать динамическое приложение, используя библиотеку OpenGL. Программа должна основываться на иерархическом построении объектов, использовать текстуры, дисплейные списки и стеки координатных преобразований. Глубина стека не менее трех. В сцене должен быть использован один из геометрических объектов, созданных во время выполнения задания 2. 3

Учебно-методическое обеспечение дисциплины

3.1 Образцы вопросов для подготовки к устному ответу На дифференцированном зачете предлагаются вопросы, изложенные в пункт 2.3 (см. выше). 3.2

Список основной и дополнительной литературы 1. ГОСТ 27817-88. Системы обработки информации. Машинная графика. Функциональное описание ядра графической системы. – М.: Госстандарт СССР, 1989. 7

2. А.В.Фролов, Г.В.Фролов. Графический интерфейс GDI в MS Windows. (Библиотека системного программиста Т. 14) – М.: "ДИАЛОГ-МИФИ", 1994. 3. Дж. Фоли, А. вэн Дэм. Основы интерактивной машинной графики. В двух книгах. Пер. с англ.-М.:Мир,1985. 4. А. Фокс, М. Пратт. Вычислительная геометрия. Применение в проектировании и на производстве. Пер. с англ. – М.: Мир, 1982. 5. Д. Роджерс. Алгоритмические основы машинной графики. Пер. с англ. – М.: Мир, 1989. (2-ое издание – 2001 год). 6. А.В. Погорелов. Дифференциальная геометрия. – М.: Наука, 1969. 7. N. Max. Optical Models for Direct Volume Rendering. - IEEE Trans. on Visualization and Comput. Graphics. 1995, v. 1, No.2, pp. 99-108 8. Visualization and Computer Animation, 1994, v.5, No.1. 9. У. Пратт, "Цифровая обработка изображений ", т. 1, 2, Москва, Мир, 1982. 10. В. Гилой, "Интерактивная машинная графика", Москва, Мир, 1981 11. Т. Павлидис, "Алгоритмы машинной графики и обработки изображений", Москва, Радио и связь, 1986. 12. В.А.Дебелов, Ю.А.Ткачев. SmogDX – объектно-ориентированная графика для Windows (DirectX и Visual C++). Новосибирск: Сибирское университетское изд-во, 2001, 311 с. 13. В.А.Дебелов, Ю.А.Ткачев. Объектно-ориентированная система машинной графики для Windows (C++ и Microsoft DirectX). – Новосибирск: ИВМиМГ СО РАН, 1999. 14. Н. Томпсон. Секреты программирования трехмерной графики для Windows 95. СПб: Питер, 1997. – 352 с. 15. Е.В. Шикин, Боресков А.В. Компьютерная графика. Динамика, реалистические изображения – М.: "ДИАЛОГ - МИФИ", 1995. 16. Шикин Е.В., Боресков А.В. Компьютерная графика. Полигональные модели. – М.: ДИАЛОГ- МИФИ, 2000. 17. Ю. Тихомиров. Программирование трехмерной графики – СПб.: БХВ – СанктПетербург, 1999. – 256 с. Программу подготовил: д.т.н.

Дебелов В.А.

Программа утверждена на заседании Ученого совета факультета информационных технологий Новосибирского государственного университета 18 декабря 2003 г., протокол заседания №16. Декан ФИТ НГУ, д.ф.-м.н.

М.М.Лаврентьев

8