Захаров С.С. Учебное пособие по дисциплине Компьютерная графика

Подождите немного. Документ загружается.

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ЭКОНОМИКИ,

СТАТИСТИКИ И ИНФОРМАТИКИ

Кафедра Математического обеспечения и технологий программирования

Захаров С. С.

Учебное пособие по дисциплине

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

Москва 2006

Содержание

Содержание....................................................................................................................................2

1. Введение.....................................................................................................................................3

2. Основные понятия машинной графики...................................................................................3

2.1 Обработка графической информации................................................................................3

2.2 Области применения машинной графики.........................................................................4

2.3 Растры против векторов......................................................................................................6

3. Аффинные преобразования и проектирование.......................................................................8

3.1 Аффинные преобразования на плоскости.........................................................................8

3.2 Однородные координаты точки.......................................................................................11

Пример..................................................................................................................................12

3.3 Аффинные преобразования в пространстве....................................................................13

Пример..................................................................................................................................15

3.4 Проектирование и его виды..............................................................................................16

4. Растровые алгоритмы..............................................................................................................19

4.1 Растровая развертка отрезка.............................................................................................19

4.2 Отсечение отрезка.............................................................................................................21

4.3 Определение принадлежности точки многоугольнику.................................................23

4.4 Закраска области, заданной цветом границы..................................................................23

4.5 Пересечение произвольного луча с простейшими геометрическими объектами.......25

5. Алгоритмы удаления невидимых линий и поверхностей...................................................26

5.1 Отсечение нелицевых граней...........................................................................................27

5.2 Удаление невидимых линий. Алгоритм Робертса..........................................................27

5.3 Алгоритм Аппеля...............................................................................................................28

5.4 Удаление невидимых граней. Метод z-буфера...............................................................29

5.5 Алгоритмы упорядочения.................................................................................................29

Метод сортировки по глубине............................................................................................29

Метод двоичного разбиения пространства.......................................................................30

5.6 Метод построчного сканирования...................................................................................31

5.7 Алгоритм Варнака.............................................................................................................31

6. Аппроксимация кривых и поверхностей...............................................................................32

6.1 Сплайн – функции.............................................................................................................33

Случай одной переменной..................................................................................................33

Случай двух переменных....................................................................................................34

6.2 Сплайновые кривые...........................................................................................................35

Кривые Безье........................................................................................................................36

Геометрически непрерывные кривые................................................................................39

7. Освещение и методы закраски...............................................................................................40

7.1 Закраска методом Гуро.....................................................................................................42

7.1 Закраска методом Фонга...................................................................................................43

8. Хранение графических данных..............................................................................................44

8.1 Алгоритмы сжатия данных...............................................................................................44

Групповое кодирование (RLE)...........................................................................................45

LZW-сжатие.........................................................................................................................46

8.2 Пример форматов графических файлов..........................................................................47

Microsoft Windows Bitmap..................................................................................................47

Глоссарий.....................................................................................................................................51

Литература....................................................................................................................................52

1. Введение

За последние десять лет, персональный компьютер из инструмента для

профессионалов превратился в общедоступное и необходимое средство, без которого

сегодня немыслима никакая аналитическая деятельность. В связи с постоянным ростом

числа пользователей ПК и, одновременно, с общим понижением необходимого для их

работы профессионального уровня, современная индустрия программного обеспечения

накладывает на специалиста в этой области дополнительные требования.

В настоящее время к программному обеспечению (продукту) предъявляются не

только требования надежности и эффективности, но также удобства использования и

наглядности. На смену бесконечным таблицам с числовыми результатами моделирования,

оценки, анализа и т. д. пришли простые для понимания графики и диаграммы; на смену

двумерным чертежам и схемам — понятные и реалистичные трехмерные модели.

Очевидно, что практически любое приложение, будь то программа финансового анализа

или компьютерная игра, в той или иной мере нуждается в указанных средствах.

Компьютерная графика как неотъемлемая часть науки программирования в целом дает в

руки будущего специалиста по информационным технологиям необходимые средства для

облегчения работы пользователя, то есть для реализации удобных и наглядных программ.

Предлагаемая дисциплина является необходимой для будущего математика-

программиста, так как находит свое применение в программных продуктах практически

для любой отрасли.

В данном курсе будут изучаться, в основном, базовые понятия, математические

методы и часто применяемые алгоритмы, а не на языковых средства или методы

различных графических библиотек. Дисциплина включает также ряд обзорных тем.

Программы по данной дисциплине могут создаваться на любом языке программирования,

будь то C++, Pascal или Basic и для любой операционной системы, будь то DOS, Windows

или UNIX.

2. Основные понятия машинной графики

2.1 Обработка графической информации

При обработке информации, связанной с изображением на мониторе, выделим

четыре основных направления: распознавание образов, обработку изображений,

машинную графику и когнитивную графику.

Основная задача распознавания образов в преобразовании уже имеющегося

изображения на формально – понятный язык символов. Распознавание образов есть

совокупность методов, позволяющих получить описание изображения, поданного на вход,

либо отнести заданное изображение к некоторому классу. При этом рассматриваемое

изображение часто преобразуется в более абстрактное описание – набор чисел, набор

символов или граф. Одной из интересных задач распознавания образов является так

называемая скелетизация, при которой восстанавливается некоторая основа объекта, его

«скелет».

Символически распознавание

изображений, или система

технического зрения COMPUTER

VISION (CV), может быть описана

так:

Изображение ОписаниеCV

Рисунок 2.1.1

 вход – изображение;

 выход – символ (текст) (рисунок 2.1.1)

Обработка изображений рассматривает задачи, в которых и входные и выходные

данные являются изображениями. Примерами обработки изображений могут служить:

передача изображений вместе с устранением шумов и сжатием данных, переход от одного

вида изображения (полутонового) у другому (каркасному), контрастирование различных

снимков, а также синтезирование имеющихся изображений в новые, например по набору

поперечных сечений объекта построить продольные сечения или восстановить сам объект.

Тем самым система обработки

изображений IMAGE PROCESSING

(IP) имеет следующую структуру:

 вход – изображение;

 выход – изображение (рисунок

2.1.2)

Компьютерная (машинная) графика воспроизводит изображение в случае, когда

исходной является информация неизобразительной природы. Например, визуализация

экспериментальных данных в виде графиков, гистограмм или диаграмм, вывод

информации на экран в компьютерных играх, синтез сцен для тренажеров.

Можно сказать, что компьютерная графика рисует, опираясь на формальное

описание и имеющийся набор средств.

Символически систему

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

COMPUTER GRAPHICS (CG)

можно представить следующим

образом:

 вход – формальное описание;

 выход – изображение

(рисунок 2.1.3)

В последние несколько лет от компьютерной графики отделилось еще одно

самостоятельное направление, получившее название когнитивной графики. В случае

когнитивной графики на выходе мы также получаем изображение, однако описание,

поступающее на вход вовсе не обязано быть формальным (то есть четким и однозначным).

Примером может послужить генерация трехмерных сцен по описанию на естественном

(человеческом) языке, который как известно неоднозначен, избыточен и неточен.

Основной целью изучаемого кура является именно компьютерная (машинная)

графика.

2.2 Области применения машинной графики

На сегодняшний день практически невозможно представить себе компьютер, не

имеющий графических возможностей. Простейший пример таких возможностейs—

графический интерфейс пользователя, завоевавший в той или иной реализации

практически весь сектор персональных компьютеров и рабочих станций, а также

получивший широкое распространение на серверах. Основными достоинствами

графического интерфейса являются наглядность и простота использования. Однако,

интерфейсs— это лишь средство для управления работой компьютера, графические же

возможности этим не ограничиваются, их применение обширноs— от простейших

иллюстраций и движущихся изображений до красочных презентаций и сложнейших

Изображение ИзображениеIP

Рисунок 2.1.2

Формальное

описание

ИзображениеCG

Рисунок 2.1.3

спецэффектов для кино. Без графики сегодня немыслима работа дизайнеров,

проектировщиков, архитекторов, специалистов по радиоэлектронике и многих других.

Сформулируем точнее основные области применения компьютерной графики:

 Графический интерфейс пользователя. Как уже отмечалось выше, он призван

облегчить взаимодействие человека и компьютера. Являясь относительно

простым в реализации (ограниченное число плоских графических объектов

заранее известного вида, модульность построения изображения и т.п.),

графический интерфейс, тем не менее, может выглядеть достаточно

привлекательно, и его значение трудно переоценить. Основные примеры:

семейство MS Windows, Mac OS, X-Windows для UNIX-подобных систем.

 Создание иллюстративного материала, то есть изображений для последующего

использования в печатной продукции либо в электронных документах. Такие

задачи решаются при помощи графических редакторов различной сложности, в

основномs— растровых (см. ниже). Простейшие редакторы позволяют рисовать

графические примитивы (круг, квадрат, линия, точка и т.д.), закрашивать области

определенным цветом или шаблоном. Профессиональные пакеты предоставляют

гораздо более широкие возможности. Приведем лишь некоторые: работа с

несколькими плоскостями изображения, преобразование цветовой гаммы,

создание сложных визуальных эффектов (размывание, затенение, эффект мазков и

т.п.). Несколько особняком в этой группе стоят векторные графические

редакторы. О достоинствах и недостатках векторной графики мы поговорим в

следующем разделе, а здесь отметим только, что подобные редакторы

используются, в основном, для создания различных схем и не слишком

применимы при работе с фотоизображениями и любыми другими изображениями

сложных предметов (людей, животных, растений). Основные примеры: “MS

Paint” (простейший редактор); “Corel PhotoPaint”, “Adobe PhotoShop”

(профессиональные растровые редакторы); “Corel Draw”, “MS Draw” (векторные

редакторы различной сложности).

 Автоматизированное проектирование двумерных и условно двумерных объектов.

В основном речь идет об электросхемотехнике, но существуют также подобные

программы для проектирования различных коммуникаций и сооружений, для

которых достаточно лишь плана, то есть вида сверху. В смысле использования

графических возможностей компьютера эти программы подобны векторным

графическим редакторам, но отличаются определенной специализацией,

поскольку им приходится отображать ограниченный набор предметов и

проводить достаточно специфические преобразования. И вообще, графика в таких

системахs— функция вторичная, а первичным является проектирование по

заданным параметрам. Наиболее известный примерs— пакет для проектирования

и подготовки к производству печатных плат “PCAD”.

 Создание плоских анимационных роликовs— «движущихся картинок».

Программы для их создания являются логическим продолжением обычных

графических редакторов. Особенно хочется отметить, что использование

векторной графики способно значительно сэкономить затраченные усилия,

поскольку в этом случае можно описать не только движение объекта от кадра к

кадру (это несложно сделать и при использовании растровой графики), но и его

трансформацию. Примеры: “Autodesk Animator” (растровый), “Corel Move”

(векторный).

 Трехмерная (3D

) анимацияs— вершина компьютерного «изобразительного

искусства». Ни о какой растровой графике речь уже не идет, любой объект имеет

точное описание. Отсюдаs— практически неограниченные возможности

построения изображений и манипуляции ими. Имеется возможность работы с

От английского three dimensionss— три измерения.

поверхностями различной структуры (текстурирование, градиентная закраска);

можно создать практически любое освещение и спецэффекты (туман, зеркальная

поверхность и т.п.). Единственным сдерживающим фактором является

быстродействие вычислительной техники, поскольку все алгоритмы для работы с

3D графикой используют большой объем сложных расчетов. В связи с этим

существует два несколько различных подхода к использованию 3D анимации. В

первом из них во главу угла ставится качество и правдоподобность изображения.

При этом на создание одного кадра изображения может потребоваться от

нескольких секунд до нескольких часов (!). Конечным результатом такой работы

обычно является растровый анимационный файл, который потом может

воспроизводиться в реальном времени при достаточно невысоких требованиях к

аппаратуре. Другой подход заключается в обсчете и выводе изображения в

режиме реального времени. Поскольку для относительно плавного движения

необходимо создание не менее десяти-пятнадцати кадров в секунду, а требования

к оборудованию не должны быть слишком высоки (речь идет в основном о

компьютерных играх), качеством и точностью здесь приходится жертвовать,

упрощая вычисления (например, заменяя арифметику с плавающей точкой

целочисленной), схематизируя освещение и закраску и опуская незначительные

детали. Основные примеры: “3D Studio” (первый подход); практически все игры

типа 3D-action, например “Quake” (второй подход).

 Автоматизированное проектирование 3D объектовs— архитектура, автомобиле-,

корабле- и самолетостроение и многое другое. Использует в основном те же

алгоритмы, что и 3D анимация, причем зачастую оба подхода. Подобные

программы значительно облегчают труд проектировщиков, позволяя не

израсходовав ни грамма материалов и ни копейки денег (если не считать тех

миллионов, которые идут на оплату техники, программ,

высококвалифицированных специалистов и, наконец, электроэнергии) посмотреть

на проектируемый объект с любой стороны, получить изображение

фотографического качества при любом освещении и в любом окружении, «на

лету» подправить какие-то детали и практически сразу увидеть результат.

Разумеется, возможности систем автоматизированного проектирования этим не

ограничиваются, но описание таких функции, как автоматический контроль за

соблюдением определенных параметров объекта (геометрических, стоимостных и

т.п.) выходит за рамки данной работы. В качестве примера приведем одну из

самых современных программ для проектирования автомобилейs— “AutoStudio”

от “Alias/wavefront”. Говорят, одна из новинок фирмы “Mercedes-Benz” (нынеs—

часть “Daimler-Chrysler”), “Mercedes A-classe” был полностью спроектирован при

помощи этой программы, практически без использования моделей и прототипов

«в железе». Вот только после начала выпуска автомобиля оказалось, что он

склонен к переворачиванию…

Таков далеко не полный список областей применения компьютерной графики.

2.3 Растры против векторов

Прежде всего, определимся с терминологией. Графику разделяют на растровую и

векторную. Сегодня эти понятия используются не совсем так, или даже совсем не так, как

они использовались изначально. Было время, когда тип графики определялся типом

монитора и деление было следующим. Если электронно-лучевая трубка (ЭЛТ) монитора

имела строчно-кадровую развертку (растр), то говорили о растровой графике, то есть

графике точек (пикселей

), образующих прямоугольную область, внутри которой можно

От английского pixels— минимальный элемент изображения.

отдельно менять параметры любой точки и эти изменения будут немедленно отображены

на экране монитора. Если же ЭЛТ имела координатную развертку, т.е. луч «умел»

двигаться по некоторой траектории (как правило, по отрезкам прямой), последовательно

обходя набор точек (вершин), то говорили о векторной графике, то есть графике вершин

(векторов

) и соединяющих их линий, когда можно говорить о цвете отдельной линии (в

простейшем случаеs— видима или нет), но никак не точки экрана. Векторные мониторы

имели широкое распространение там, где необходимо было выводить на экран четкие

чертежи (в том числе и трехмерные), ведь, как будет показано далее, в растровой графике

рисование линийs— одна из самых сложных проблем. Главными недостатками таких

мониторов, которые и привели к их практически полному исчезновению, были сложность

создания и невозможность отображения сплошных фигур.

В результате, на сегодняшний день вся графика является растровой, даже та,

которую называют векторной. Во всяком случае, в той части ее реализации, которая

начинается в видеопамяти и заканчивается на экране монитора. В чем же различие? В

способе хранения и обработки. Растровое изображение хранится и обрабатывается как

набор пикселей (или несколько наборов в случае нескольких плоскостей изображения,

что, впрочем, не меняет сути). К тому же, имеет смысл говорить только о плоском

растровом изображении. Векторное изображение хранится и обрабатывается как набор

графических примитивов, т.е. геометрических объектов, описанных аналитически.

Типичным примером графического примитива является треугольник, для которого

хранятся следующие атрибуты: координаты трех вершин (необязательно двумерные) и

цвет (текстура). Можно также хранить цвет каждого ребра треугольника.

Главным достоинством векторного способа обработки и хранения графической

информации (в дальнейшемs— векторной графики) является возможность легко работать

с любым элементом изображения. Не составляет никакого труда переместить, повернуть

или изменить в размерах как отдельный примитив, так и все изображение в целом, причем

операция не внесет искажений и будет обратима, чего нельзя сказать о растровом

изображении. В самом деле, в случае векторным изображением необходимо будет только

поменять координаты вершин треугольника, когда как в растровом придется по довольно

сложным алгоритмам добавлять недостающие пиксели (в случае растяжения) либо

убирать лишние (в случае сжатия), либо закрывать другие части изображения (в случае

поворота и переноса).

А недостатки? Они, как всегда, являются продолжением достоинств. Во-первых, в

силу того, что видеопамять и монитор работают с растровой графикой, для вывода на

экран необходимо произвести растеризацию изображения, т.е. преобразование в

пиксельную форму. Во-вторых, при каждом конкретном размере рисунка растровое

изображение всегда будет иметь лучшее качество, чем векторное. Приведем пример.

Пусть при помощи очень хорошего сканера нам удалось ввести в компьютер растровое

изображение картины «Мона Лиза» размером 2000х3000 точек. Предположим также, что

у нас есть очень хорошая программа для векторизации растровой картинки (а такие

программы есть, напримерs— “Corel Trace”). Полученное с помощью этой программы

изображение будет очень похоже на первоначальное, но в силу особенностей векторной

графики оно будет уступать ему по качеству (будут заметны резкие переходы в цвете от

примитива к примитиву, некоторая «угловатость» и т.д.). Однако, если мы теперь сожмем

оба изображения в десять раз (200х300 точек), разница будет менее заметна, возможно

даже, что векторный вариант будет более четким и узнаваемым. А уж если мы произведем

затем обратную операцию, растровое изображение вообще перестанет быть похожим на

оригинал, а векторное останется все тем же. Еще один пример, на этот раз из области игр.

Предположим, нам надо изобразить монстра на расстоянии десяти шагов от игрока.

Можно сделать безумно красивое изображение, задействовав каждый пиксель,

Вспомним, что с точки зрения многих разделов математики понятия точка A(x, y) и вектор



(x,y)

являются взаимозаменяемыми.

отведенный для этого изображения, чтобы передать всю кровожадность и

отвратительность чудовища. И даже самая тщательная векторная модель монстра не

сможет сравниться с полученным изображениемs— все те же угловатость и резкие

переходы плюс треугольное непонятно что вместо лица (или морды). Но стоит подойти на

пять шагов, и становится ясно, что лучше уж треугольная морда, чем «это».

В растровой графике уже все сделано. Такие же слова были сказаны в свое время

молодому Максу Планку (будущему основоположнику квантовой физики) по поводу

положения дел в теоретической физике. Чем это кончилосьs— общеизвестно. Но на

сегодняшний день все выглядит именно так, и не видно никаких способов что-то

кардинально улучшить (можно только постепенно увеличивать быстродействие

отдельных компонентов системы). Все основные алгоритмы (а некоторые из них мы

рассмотрим далее) были разработаны и отшлифованы уже давно. Затем, для ускорения

вывода изображений и разгрузки центрального процессора, часть этих алгоритмов была

реализована на аппаратном уровнеs— появились 2D акселераторы (видеокарты с

аппаратной поддержкой вывода графических примитивов) и видеобластеры (видеокарты с

аппаратной поддержкой масштабирования изображения). Что еще делатьs— неясно. Но

кто знает, может быть через несколько лет произойдет прорыв в этой области. Такой же,

какой произошел (или продолжает происходить) в области графики векторной.

Сразу оговоримся, речь идет не о векторной графике в целом, а о наиболее широко

используемой ее разновидностиs— 3D графике. И прорыв этот связан не с алгоритмами

3D преобразованийs— они просты и давно известны, а с процессом растеризации. Дело в

том, что различные стадии растеризации изображения (освещение, текстурирование,

формирование Z-буфера) сопряжены с интенсивными вычислениями, а центральный

процессор помимо этого вынужден делать массу другой работы. Выход был найден по

аналогии с растровой графикойs— соответствующие алгоритмы реализовали аппаратно.

Однако, обилие этих алгоритмов и сложность их реализации привели к тому, что с

первого раза далеко не все получилось хорошо. И теперь большое число фирм-

разработчиков 3D акселераторов работают над тем, чтобы заложить в свои детища как

можно больше возможностей, а главноеs— заставить их работать как можно быстрее и как

можно точнее.

3. Аффинные преобразования и проектирование

Вывод изображения на экран монитора и разнообразные действия с ним, в том

числе и визуальный анализ, требуют от пользователя известной геометрической

грамотности. Геометрические понятия формулы и факты, относящиеся к плоскому и

трехмерному случаям, играют в задачах компьютерной графики особую роль.

Геометрические соображения, подходы и идеи в соединении с постоянно

расширяющимися возможностями вычислительной техники являются неиссякаемым

источником существенных продвижений на пути компьютерной графики, ее

эффективного использования в научных и иных исследованиях. Порой даже самые

простые геометрические методики обеспечивают заметное продвижение на различных

этапах решения большой графической задачи.

3.1 Аффинные преобразования на плоскости

Для начала определимся с системами координат. В задачах компьютерной графики

приходится иметь дело с несколькими различными системами координат на различных

этапах решения. Все эти системы являются прямоугольными, то есть все оси

перпендикулярны друг другу. Различия заключаются в направлении этих осей. Например,

от того, какой графической библиотекой мы пользуемся и в какой операционной системе

работаем направление оси ординат может изменяться на противоположное. Наиболее

часто приходится учитывать разницу в направлении оси аппликат. Если ось аппликат

направлена от нас (от зрителя, в глубь монитора и т. д.) система координат называется

левосторонней, если наоборот, то правосторонней.

В компьютерной графике все, что относится к двумерному случаю, принято

обозначать символом 2D

Допустим, на плоскости введена

прямолинейная координатная система. Тогда

каждой точке M ставится в соответствие

упорядоченная пара чисел (x ,y) ее координат

(рисунок 3.1.1). Вводя на плоскости еще одну

прямолинейную систему координат, мы ставим

в соответствие той же точке M другую пару

чисел --

),(

Переход от одной прямолинейной

координатной системы к другой описывается

следующими соотношениями:



 yxx



 yxy

где



,,,,,

-- произвольные числа, связанные неравенством

0





Эти формулы можно трактовать двояко: либо сохраняются координаты точки и

меняется координатная система (рисунок 3.1.2), либо координатная система сохраняется и

меняется положение точки (рисунок 3.1.3).

В дальнейшем мы будем рассматривать приведенные формулы как правило,

согласно которому в заданной системе прямолинейных координат преобразуются точки

плоскости.

В аффинных преобразованиях на плоскости особую роль играют несколько важных

частных случаев, имеющих хорошо прослеживаемые геометрические характеристики.

При исследовании геометрического смысла числовых коэффициентов в приведенных

формулах для этих случаев нам удобно считать, что заданная система координат является

прямоугольной декартовой.

A. Поворот (вокруг начальной точки на угол



) (рисунок 3.1.4) описывается

формулами



sincos

yxx 



cossin

yxy 

Б. Растяжение (сжатие) вдоль координатных осей (рисунок 3.1.5) можно задать так:

От английского two dimensions – два измерения

Рисунок 3.1.2

Рисунок 3.1.3

M (x, y)

Рисунок 3.1.1









0,0 



В. Отражение (относительно оси абсцисс) (рисунок 3.1.6) задается при помощи

формул

xx 

yy 

Г. Перенос описывается так:



xx



yy

Выбор этих четырех частных случаев определяется двумя обстоятельствами:

1. Каждое из приведенных выше преобразований имеет простой и наглядный

геометрический смысл (геометрическим смыслом наделены и постоянные числа,

входящие в формулы).

2. Как доказывается в курсе аналитической геометрии, любое преобразование всегда

можно представить как последовательное исполнение (суперпозицию) простейших

преобразований вида А, Б, В и Г (или части этих преобразований).