Реферат Курсовая Конспект
ОСНОВЫ КОМПЬЮТЕРНОЙ ГРАФИКИ - раздел Компьютеры, Министерство Образования И Науки Российской Федерации Федеральное Го...
|
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования
«НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ
ТОМСКИЙ ПОЛИТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ»
А.Ю. Дёмин
О С Н О В Ы К О М П Ь Ю Т Е Р Н О Й
УДК 681.3.06 (082.5)
ББК
Рецензенты
Доктор технических наук,
– заведующий кафедрой программирования Томского государственного университета, профессор
А.Ю. Матросова
Доктор технических наук,
профессор кафедры автоматизированных систем управления
Томского государственного университета систем управления и радиоэлектроники, профессор
М.Ю. Катаев
© ФГБОУ ВПО НИ ТПУ, 2011
© Демин А.Ю. 2011
© Оформление. Издательство Томского
политехнического университета, 2011
Введение
Если заглянуть в историю, то можно проследить, как с момента появления первых ЭВМ люди стремятся разнообразить способы общения человека и машины, приблизившись к уровню общения человека с человеком. Это общение было бы гораздо более ограниченным, если бы не использовало один из наиболее простых способов — язык изображений, образов. Сегодня графические изображения на экране монитора современного персонального компьютера стали для нас нормой, совершенно неотъемлемым атрибутом интерфейса. Спектр применения компьютерной графики, помимо средства интерфейса «человек-машина», чрезвычайно широк: от создания рекламных роликов, компьютерных мультфильмов и игр, кроя одежды, малых и монументальных форм дизайна, компьютерной живописи до визуализации результатов научных изысканий [10]. Можно с уверенностью сказать, что популярность Internet, и в частности WWW, во многом объясняется широким применением графики.
Рынок программного и аппаратного обеспечения компьютерной графики – один из самых динамичных. Об этом можно судить по объему литературы и числу сервисов Internet, посвященных так или иначе компьютерной графике.
Предметом данной работы является обширная область компьютерных наук, посвященная представлению данных в памяти ЭВМ в графической форме. Это самое общее определение, так как под данными можно понимать как непосредственно хранящееся в виде файла изображение в одном из графических форматов, так и протокол обмена командами между пользователем и ЭВМ (то, что мы называем графическим интерфейсом), и битовую последовательность, сформированную для вывода на экран или печатающее устройство. Методы и способы представления и манипуляции этим видом данных относятся к компетенции компьютерной графики.
В работе рассматриваются различные способы представления изображений в памяти ЭВМ, методы и алгоритмы растеризации и обработки растровых изображений, матричные преобразования на плоскости и в пространстве, методы и алгоритмы удаления скрытых линий и поверхностей. Кроме того, приводятся основы использования графической библиотеки OpenGL, а также описываются базовые аппаратные средства, используемые при работе с изображениями.
Программный код, приведенный в пособии, создан в MS Visual Studio 2010 на языке C#.
Представление цвета в компьютере
BMP
BMP (от англ. BitMap Picture) — формат хранения растровых изображений. BMP был создан компанией Microsoft и широко используется в операционных системах семейства Windows.
Глубина цвета в данном формате может быть 1, 2, 4, 8, 16, 24, 32, 48 бит на пиксель, максимальные размеры изображения 65535×65535 пикселей. Однако, глубина 2 бит официально не поддерживается.
Формат BMP является примером хранения полноцветных изображений. В этом случае, цвета пикселей можно определять, явно задавая несколько параметров цвета. Например, в RGB-модели конечный цвет каждого пикселя определяется тремя слагаемыми для трех основных цветов.
В формате BMP есть поддержка сжатия по алгоритму RLE. Алгоритм RLE или алгоритм кодирования повторов оперирует сериями данных, то есть последовательностями, в которых один и тот же символ встречается несколько раз подряд. При кодировании строка одинаковых символов, составляющих серию, заменяется строкой, которая содержит сам повторяющийся символ и количество его повторов.
Рассмотрим изображение, состоящее из строки белых и черных пикселей. Опишем эту строку как:
WWWWBWWWWBBBWWWWBWWWW
Здесь B представляет чёрный пиксель, а W обозначает белый. Если мы применим RLE кодирование к этой строке, то получим следующее:
4W1B4W3B4W1B4W
Файлы формата BMP могут иметь расширения .bmp, .dib и .rle. DIB означает аппаратно-независимый растр (Device Independent Bitmap). При использовании этого формата программист может получить доступ ко всем элементам структур, описывающих изображение, при помощи обычного указателя. Но эти данные не используются для непосредственного управления экраном, так как они всегда хранятся в системной памяти, а не в специализированной видеопамяти. Формат пикселя в оперативной памяти может отличаться от того формата, который должен заноситься в видеопамять для индикации точки такого же цвета. Например, в DIB-формате может использоваться 24 бита для задания пикселя, а графический адаптер в этот момент может работать в режиме HighColor с цветовой глубиной 16 бит. При этом ярко-красная точка в аппаратно-независимом формате будет задаваться тремя байтами 0x0000ff, а в видеопамяти — словом 0xF800.
DDB означает аппаратно-зависимый растр (Device Dependent Bitmap, DDB). Этот формат всегда содержит цветовые коды, совпадающие с кодами видеобуфера, но храниться он может как в системной, так и в видеопамяти. В обоих случаях он содержит только коды цвета в том формате, который обеспечит пересылку изображения из ОЗУ в видеопамять при помощи простого копирования.
Таким образом, достоинством формата BMP является простота обращения к отдельным пикселям на изображении, что может быть использовано при написании демонстрационных программ по компьютерной графике. К недостатком нужно отнести сравнительно большие размеры файлов, хранящих изображения в формате BMP, вследствие не совершенства алгоритма RLE.
Кроме поддержки полноцветных изображений формат BMP может обеспечивать хранения изображений с использованием индексированной палитры. Второй подход заключается в том, что в первой части файла, хранящего изображение, хранится «палитра»,в которой с помощью одной из цветовых моделей кодируются цвета, присутствующие на изображении. А вторая часть, которая непосредственно описывает пиксели изображения, фактически состоит из индексов в палитре.
Формат BMP может использовать режим индексирования цветов при следующих значениях глубины цвета: 1 бит (2 цвета), 2 бита (4 цвета), 4 бита (16 цветов), 8 бит (256 цветов).
Благодаря использованию палитры имеется возможность адаптировать изображение к цветам, присутствующим на изображении. В таком случае изображение ограниченно не заданными цветами, а максимальным количеством одновременно используемых цветов.
Достоинством палитры является возможность существенно сократить размер файла с изображением. Недостатком является возможность потери цветов при ограниченном размере палитры.
TIFF
TIFF (англ. Tagged Image File Format) — формат хранения растровых графических изображений. Изначально был разработан компанией Aldus в сотрудничестве с Microsoft. TIFF был выбран в качестве основного графического формата операционной системы Mac OS X. В настоящее время авторские права на спецификации формата принадлежат компании Adobe.
Принцип хранения данных в TIFF основан на использовании специальных маркеров (тэгов) в сочетании с битовыми последовательностями кусков растра.
Формат TIFF поддерживает большую глубину цвета: 8, 16, 32 и 64 бит на канал при целочисленном кодировании, а также 32 и 64 бит на канал при представлении значения пикселя числами с плавающей запятой.
Структура формата гибкая и позволяет сохранять изображения в режиме цветов с палитрой, а также в различных цветовых пространствах: бинарном (двуцветном), полутоновом, с индексированной палитрой, RGB, CMYK, YCbCr, CIE Lab. Помимо традиционных цветов CMY формат поддерживает цветоделение с большим числом красок, в частности систему Hexachrome компании Pantone. В систему Hexachrome, известную как CMYKOG, добавлены оранжевые и зеленые краски для лучшего представления цветов при печати.
Помимо прочих достоинств формат TIFF позволяет сохранять растровые изображения с компрессией без потери качества. Этот формат поддерживает сжатие без потери качества по алгоритму LZW-компрессии.
Алгоритм Лемпеля — Зива — Велча (Lempel-Ziv-Welch, LZW) — это универсальный алгоритм сжатия данных без потерь данных. Алгоритм на удивление прост. Если в двух словах, то LZW-сжатие заменяет строки символов некоторыми кодами. Это делается без какого-либо анализа входного текста. Вместо этого при добавлении каждой новой строки символов просматривается уже существующая таблица строк. Сжатие происходит, когда код заменяет строку символов. Коды, генерируемые LZW-алгоритмом, могут быть любой длины, но они должны содержать больше бит, чем единичный символ. Первые 256 кодов (когда используются 8-битные символы) по умолчанию соответствуют стандартному набору символов. Остальные коды соответствуют обрабатываемым алгоритмом строкам. Простой метод может работать с 12-битными кодами. Значения кодов 0 - 255 соответствуют отдельным байтам, а коды 256 - 4095 соответствуют подстрокам.
Приведем пример LZW кодирования применительно к изображению. Так, если в изображении имеются наборы из розового, оранжевого и зелёного пикселей, повторяющиеся 50 раз, LZW выявляет это, присваивает данному набору отдельное число (например, 7) и затем сохраняет эти данные 50 раз в виде числа 7. Метод LZW, так же, как и RLE, лучше действует на участках однородных, свободных от шума цветов, он действует гораздо лучше, чем RLE, при сжатии произвольных графических данных, но процесс кодирования и распаковки происходит медленнее.
Кроме LZW-компрессии формат TIFF поддерживает следующие алгоритмы сжатия:
§ RLE;
§ LZ77;
§ ZIP;
§ JBIG;
§ JPEG;
§ CCITT Group 3, CCITT Group 4.
При этом JPEG является просто инкапсуляцией формата JPEG в формат TIFF. Формат TIFF позволяет хранить изображения, сжатые по стандарту JPEG, без потерь данных (JPEG-LS).
GIF
Первая версия формата GIF (Graphics Interchange Format, «Формат для обмена графической информацией») была разработана в 1987 г. специалистами компьютерной сети CompuServe. Этот формат сочетает в себе редкий набор достоинств, неоценимых при той роли, которую он играет в WWW. Сам по себе формат содержит уже достаточно хорошо упакованные графические данные.
Формат GIF использует для хранения изображений индексированную палитру, ограничивающую количество цветов 256 значениями. Размер палитры может быть и меньше. Если в изображении используется, скажем, 64 цвета (26), то для хранения каждого пикселя будет использовано ровно шесть бит и ни битом больше.
Поскольку GIF использует для сжатия LZW алгоритм, то степень сжатия графической информации сильно зависит от уровня ее повторяемости и предсказуемости, а иногда еще и от ориентации картинки. Так как LZW метод сканирует изображение по строкам, то, к примеру, плавный переход цветов (градиент), направленный сверху вниз, сожмется куда лучше, чем тех же размеров градиент, ориентированный слева направо, а последний – лучше, чем градиент по диагонали.
Изменив порядок следования данных в файле, создатели GIFa заставили картинку рисоваться не только сверху вниз, но и, если можно так выразиться, «с глубины к поверхности», – то есть становиться все четче и детальнее по мере подхода из сети новых данных.
Для этого файл с изображением тасуется при записи так, чтобы сначала шли все строки пикселей с номерами, кратными восьми (первый проход), затем четырем (второй проход), потом двум и, наконец, последний проход – все оставшиеся строки с нечетными номерами. Во время приема и декодирования такого файла каждый следующий проход заполняет «дыры» в предыдущих, постепенно приближая изображение к исходному состоянию. Поэтому такие изображения были названы чересстрочными (interlaced).
Другой полезной возможностью формата является использование прозрачности и поддержка анимационных изображений. Для создания анимации используется нескольких статичных кадров, а также информация о том, сколько времени каждый кадр должен быть показан на экране.
PNG
PNG (portable network graphics) - растровый формат хранения графической информации, использующий сжатие без потерь по алгоритму Deflate.
PNG поддерживает три основных типа растровых изображений:
§ Полутоновое изображение (с глубиной цвета 16 бит);
§ Цветное индексированное изображение (палитра 8 бит для цвета глубиной 24 бит);
§ Полноцветное изображение (с глубиной цвета 48 бит).
Формат PNG спроектирован для замены устаревшего и более простого формата GIF, а также, в некоторой степени, для замены значительно более сложного формата TIFF. Алгоритм сжатия Deflate является свободным в отличие от защищенного патентами и соответственно платного LZW, используемого в GIF. В отличии от LZW кодирования, которое позволяет эффективно сжимать горизонтальные одноцветные области, с Deflate сжатием можно забыть про эти ограничения.
В формате GIF один из цветов в палитре может быть объявлен «прозрачным». В этом случае в программах, которые поддерживают прозрачность GIF (например, большинство современных браузеров) сквозь пиксели, окрашенные «прозрачным» цветом будет виден фон. Однако создатели PNG пошли еще дальше, разработав технологию альфа-канала. Альфа-канал позволяет добиться эффекта частичной прозрачности пикселей. Также, в PNG поддерживается гамма-коррекция. Гамма-коррекция - коррекция функции яркости в зависимости от характеристик устройства вывода. Повышение показателя гамма-коррекции позволяет повысить контрастность, разборчивость тёмных участков изображения, не делая при этом чрезмерно контрастными или яркими светлые детали снимка.
Кроме этого PNG формат имеет следующие преимущества перед GIF:
§ практически неограниченное количество цветов в изображении (GIF использует в лучшем случае 8-битный цвет);
§ двумерная чересстрочная развёртка;
§ возможность расширения формата пользовательскими блоками.
К недостатком формата, можно отнести, что PNG изначально был предназначен лишь для хранения одного изображения в одном файле. Поэтому данный формат не поддерживает анимацию. Для решения этой проблемы создана модификация формата APNG.
JPEG
JPEG (Joint Photographic Experts Group, по названию организации-разработчика) - один из популярных графических форматов, основанный на алгоритме сжатия JPEG и применяемый для хранения фотоизображений и подобных им изображений.
Алгоритм JPEG разработан группой экспертов из Международной организации по стандартизации (ISO) специально для сжатия полноцветных 24-битовых изображений.
Процесс сжатия по схеме JPEG состоит из нескольких шагов. На первом шаге производится преобразование изображения из цветовой модели RGB в модель YUV, основанной на характеристиках яркости и цветности.
В модели YUV, Y-компонента – светлота (яркость). Компоненты U и V содержат информацию о цвете.
На следующем после преобразования шаге изображение разделяется на квадратные участки размером 8х8 пикселей. После этого над каждым участком производится дискретное косинус-преобразование (ДКП). При этом выполняется анализ каждого блока, разложение его на составляющие цвета и подсчет частоты появления каждого цвета.
Если говорить научным языком, то JPG использует для сохранения ряды Фурье и при больших степенях сжатия просто отбрасывает члены ряда высшего порядка.
Можно сказать, что JPEG хранит скорость изменения цвета от пикселя к пикселю. Лишнюю с его точки зрения цветовую информацию он отбрасывает, усредняя некоторые значения. Чем выше уровень компрессии, тем больше данных отбрасывается и тем ниже качество
На следующем этапе изображение представляется строками чисел, которые можно сжимать дальше. Поскольку в результате предыдущей обработки строки содержат много нулей, последняя стадия кодирования выполняется по алгоритму Хаффмана, что дает хорошие результаты и позволяет получить файл в 10–500 раз меньше, чем ВМР.
В дополнении к стандарту JPEG, ориентированным прежде всего на сжатие с потерями, был разработан стандарт на сжатие без потерь — JPEG-LS (в котором, однако, предусмотрен также режим сжатия с ограниченными потерями).
Алгоритм сжатия, лежащий в основе JPEG-LS, использует адаптивное предсказание значения текущего пикселя по окружению, включающему уже закодированные пиксели.
К недостаткам сжатия по стандарту JPEG следует отнести появление на восстановленных изображениях при высоких степенях сжатия характерных артефактов (заметных искажений изображения).
Формат PDF (Portable Document Format) предложен фирмой Adobe как независимый от платформы формат, в котором могут быть сохранены и иллюстрации (векторные и растровые), и текст, причем со множеством шрифтов и гипертекстовых ссылок. Для достижения продекларированной в названии переносимости размер PDF-файла должен быть малым. Для этого используется компрессия (для каждого вида объектов применяется свой способ). Например, растровые изображения записываются в формате JPEG.
Для работы с этим форматом компания Adobe выпустила пакет Acrobat. Бесплатная утилита Acrobat Reader позволяет читать документы и распечатывать их на принтере, но не дает возможности создавать или изменять их. Acrobat Distiller переводит в этот формат PostScript-файлы. Многие программы (Adobe PageMaker, CorelDraw, FreeHand) позволяют экспортировать свои документы в PDF, а некоторые – еще и редактировать графику, записанную в этом формате. Обычно в этом формате хранят документы, предназначенные только для чтения, но не для редактирования. Файл в формате PDF содержит все необходимые шрифты. Это удобно и позволяет не передавать шрифты для вывода (передача шрифтов не вполне законна с точки зрения авторского права).
Линейные кривые
При n = 1 кривая представляет собой отрезок прямой линии, опорные точки P0 и P1 определяют его начало и конец. Кривая задаётся уравнением:
B(t) = (1–t) P0 + t P1 t Є [0, 1].
Заполнение многоугольника
Часто возникает задача заполнения многоугольников, заданных набором вершин.
Задача заполнения многоугольников решается в два этапа:
1) сначала проводится операция отсечения многоугольника;
2) затем производится заполнение полученных многоугольников.
Этап отсечения необходим для определения реальных областей многоугольника, которые будут выведены на экран. Это необходимо, если многоугольник больше или выходит за пределы экрана или окна вывода.
Методы устранения ступенчатости
Основная причина появления лестничного эффекта заключается в том, что отрезки, ребра многоугольника, цветовые границы и пр. имеют непрерывную природу, тогда как растровые устройства дискретны.
Лестничный эффект проявляется:
1) при визуализации мелких деталей;
2) при прорисовке ребер и границ;
3) при анимации мелких деталей.
Опишем основные методы устранения ступенчатости.
Метод, основанный на использовании полутонов
В этом эвристическом методе интенсивность пикселя на ребре устанавливается пропорционально площади части пикселя, находящегося внутри многоугольника.
Рис. 4.14. Закраска ребра
На рис. 4.14 приводится многоугольник, ребро которого сгенерировано основным алгоритмом Брезенхейма. Пиксели в этом ребре и внутренние пиксели многоугольника полностью закрашены. Пиксели, находящиеся выше ребра, закрашиваются с различной интенсивностью, которая пропорциональна площади пикселя, попадающего внутрь многоугольника.
Методы обработки изображений
Часто в компьютерной графике возникает задача обработки изображений. Обработка, как правило, заключается в наложении на изображение каких-либо эффектов – это размытие, резкость, деформация, шум и т. д., а также в регулировке уровня яркости и контраста.
Цифровые фильтры изображений
Цифровые фильтры позволяют накладывать на изображение различные эффекты, например: размытие, резкость, деформацию, шум и т. д.
Цифровой фильтр представляет собой алгоритм обработки изображения. Большая группа цифровых фильтров имеет один и тот же алгоритм, но эффект, накладываемый фильтром на изображение, зависит от коэффициентов, используемых в алгоритме.
Фильтрация изображений является одной из самых фундаментальных операций компьютерного зрения, распознавания образов и обработки изображений. Фактически, с той или иной фильтрации исходных изображений начинается работа подавляющего большинства методов.
Преобразования растровых изображений
Компьютерная геометрия
Отображение
В то время как чистое двумерное вращение в плоскости xy осуществляется вокруг оси, перпендикулярной к этой плоскости, отображение определяется поворотом на 180° вокруг оси, лежащей в плоскости ху.
Такое вращение вокруг линии у = х происходит при использовании матрицы .
Преобразованные новые выражения определяются соотношением
.
Вращение вокруг у = 0 получается при использовании матрицы
.
Трехмерное изменение масштаба
Рассмотрим частичное изменение масштаба. Оно реализуется следующим образом:
S(Sx,Sy,Sz,1)= ,
т. е. [x,y,z,1]*S(Sx,Sy,Sz)=[Sx*x,Sy*y,Sz*z,1].
Общее изменение масштаба получается за счет 4-го диагонального элемента, т. е.
[x y z 1] * = [x y z S] = [x* y* z* 1] = [ ].
Такой же результат можно получить при равных коэффициентах частичных изменений масштабов. В этом случае матрица преобразования такова:
S= .
Трехмерный сдвиг
Недиагональные элементы матрицы 3´3 осуществляют сдвиг в трех измерениях, т. е.
[x y z 1]* =[x+yd+hz, bx+y+iz, cx+fy+z, 1].
Трехмерное вращение
Двухмерный поворот, рассмотренный ранее, является в то же время трехмерным поворотом вокруг оси Z . В трехмерном пространстве поворот вокруг оси Z описывается матрицей
Rz( )= .
Матрица поворота вокруг оси X имеет вид
Rx( )= .
Матрица поворота вокруг оси Y имеет вид
Ry( )= .
Результатом произвольной последовательности поворотов вокруг осей x, y, z является матрица
А= .
Подматрицу 3´3 называют ортогональной, так как ее столбцы являются взаимно ортогональными единичными векторами.
Матрицы поворота сохраняют длину и углы, а матрицы масштабирования и сдвига нет.
Полигональные сетки
Полигональная сетка представляет собой совокупность ребер, вершин и многоугольников. Вершины соединяются ребрами, а многоугольники рассматриваются как последовательности ребер или вершин. Сетку можно представить несколькими различными способами, каждый из них имеет свои достоинства и недостатки. Для оценки оптимальности представления используют следующие критерии:
· Объем требуемой памяти;
· Простота идентификации ребер, инцидентных вершине;
· Простота идентификации многоугольников, которым принадлежит данное ребро;
· Простота процедуры поиска вершин, образующих ребро;
· Легкость определения всех ребер, образующих многоугольник;
· Простота получения изображения полигональной сетки;
· Простота обнаружения ошибок в представлении (например, отсутствие ребра или вершины или многоугольника).
Рассмотрим подробнее три способа описания полигональных сеток.
Явное задание многоугольников
Каждый многоугольник можно представить в виде списка координат его вершин:
P = ((x1, y1, z1), (x2, y2, z2), … , (xn, yn, zn))
Вершины запоминаются в том порядке, в котором они встречаются при обходе вокруг многоугольника. При этом все последовательные вершины многоугольника (а также первая и последняя) соединяются ребрами. Для каждого отдельного многоугольника данный способ записи является эффективным, однако для полигональной сетки дает потери памяти вследствие дублирования информации о координатах общих вершин.
Полигональная сетка изображается путем вычерчивания ребер каждого многоугольника, однако это приводит к тому, что общие ребра рисуются дважды – по одному разу для каждого из многоугольников.
Задание многоугольников с помощью указателей в список вершин
При использовании этого представления каждый узел полигональной сетки запоминается лишь один раз в списке вершин V =((x1, y1, z1), … , (xn, yn, zn)). Многоугольник определяется списком указателей (или индексов) в списке вершин. Многоугольник, составленный из вершин 3, 5, 7 и 10 этого списка, представляется как Р = (3, 5, 7, 10).
Такое представление имеет ряд преимуществ по сравнению с явным заданием многоугольников. Поскольку каждая вершина многоугольника запоминается только один раз, удается сэкономить значительный объем памяти. Кроме того, координаты вершины можно легко изменять. Однако все еще не просто отыскивать многоугольники с общими ребрами. Ребра при изображении всей полигональной фигуры по-прежнему рисуются дважды. Эти две проблемы можно решить, если описывать ребра в явном виде.
Явное задание ребер
В этом представлении имеется список вершин V, однако будем рассматривать теперь многоугольник как совокупность указателей на элементы списка ребер, в котором ребра встречаются лишь один раз. Каждое ребро в списке ребер указывает на две вершины в списке вершин, определяющие это ребро, а также на один или два многоугольника, которым это ребро принадлежит. Таким образом, мы описываем многоугольник как P =(E1, ..., E2), а ребро — как Е = (V1, V2, P1, P2). Если ребро принадлежит только одному многоугольнику, то либо P1 либо P2 – пусто.
При явном задании ребер полигональная сетка изображается путем вычерчивания не всех многоугольников, а всех ребер. В результате удается избежать многократного рисования общих ребер. Отдельные многоугольники при этом также изображаются довольно просто.
В некоторых приложениях ребра полигональных сеток являются общими для более чем двух многоугольников. Рассмотрим, например, случай в картографии, когда такие подразделения, как округа, штаты и т. д., описываются многоугольниками. Ребро (или последовательность ребер), представляющее часть границы между двумя штатами, является также границей округа в каждом штате, а возможно, и города. Таким образом, ребро может принадлежать одновременно шести многоугольникам. Если принять во внимание деление городов на районы, избирательные округа и школьные участки, то это число соответственно возрастет. Для таких приложений описания ребер могут быть расширены, чтобы включить произвольное число многоугольников: Е = (V1, V2, P1, P2, …, Pn).
Ни в одном из этих представлений задача определения ребер, инцидентных вершине, не является простой: для ее решения необходимо перебрать все ребра. Конечно, для определения таких отношений можно непосредственно использовать дополнительную информацию.
Удаление невидимых линий и поверхностей
Классификация методов удаления невидимых линий и поверхностей
Задача удаления невидимых линий и поверхностей является одной из наиболее сложных в машинной графике. Алгоритмы удаления невидимых линий и поверхностей служат для определения линий ребер, поверхностей или объемов, которые видимы или невидимы для наблюдателя, находящегося в заданной точке пространства. Необходимость удаления невидимых линий, ребер, поверхностей или объемов проиллюстрирована рис. Ошибка! Источник ссылки не найден.
а б в
Рис. 8.1. Необходимость удаления невидимых линий
На рис. 8.1, а приведен типичный каркасный чертеж куба. Каркасный чертеж представляет трехмерный объект в виде штрихового изображения его ребер. Рис. 8.1, а можно интерпретировать двояко: как вид куба сверху слева или снизу справа. Для этого достаточно прищуриться и перефокусировать глаза. Удаление тех линий или поверхностей, которые невидимы с соответствующей точки зрения, позволяют избавиться от неоднозначности. Результаты показаны на рис. 8.1, б и рис. 8.1, в.
Сложность задачи удаления невидимых линий и поверхностей привела к появлению большого числа различных способов ее решения. Многие из них ориентированы на специализированные приложения. Наилучшего решения обшей задачи удаления невидимых линий и поверхностей не существует. Для моделирования процессов в реальном времени, например для авиатренажеров, требуются быстрые алгоритмы, которые могут порождать результаты с частотой видеогенерации 30 кадр/с. Для машинной мультипликации, например, требуются алгоритмы, которые могут генерировать сложные реалистические изображения, в которых представлены тени, прозрачность и фактура, учитывающие эффекты отражения и преломления цвета в мельчайших оттенках. Подобные алгоритмы работают медленно, и зачастую на вычисления требуется несколько минут или даже часов. Строго говоря, учет эффектов прозрачности, фактуры, отражения и т. п. не входит в задачу удаления невидимых линий или поверхностей. Естественнее считать их частью процесса визуализации изображения. Однако многие из этих эффектов встроены в алгоритмы удаления невидимых поверхностей. Существует тесная взаимосвязь между скоростью работы алгоритма и детальностью его результата. Ни один из алгоритмов не может достигнуть хороших оценок для этих двух показателей одновременно. По мере создания все более быстрых алгоритмов можно строить все более детальные изображения. Реальные задачи, однако, всегда будут требовать учета еще большего количества деталей.
Все алгоритмы удаления невидимых линий (поверхностей) включают в себя сортировку. Порядок, в котором производится сортировка координат объектов, вообще говоря, не влияет на эффективность этих алгоритмов. Главная сортировка ведется по геометрическому расстоянию от тела, поверхности, ребра или точки до точки наблюдения. Основная идея, положенная в основу сортировки по расстоянию, заключается в том, что чем дальше расположен объект от точки наблюдения, тем больше вероятность, что он будет полностью или частично заслонен одним из объектов, более близких к точке наблюдения. После определения расстояний или приоритетов по глубине остается провести сортировку по горизонтали и по вертикали, чтобы выяснить, будет ли рассматриваемый объект действительно заслонен объектом, расположенным ближе к точке наблюдения. Эффективность любого алгоритма удаления невидимых линий или поверхностей в большой мере зависит от эффективности процесса сортировки. Для повышения эффективности сортировки используется также когерентность сцены, т. е. тенденция неизменяемости характеристик сцены в малом.
Алгоритмы удаления невидимых линий или поверхностей можно классифицировать по способу выбора системы координат или пространства, в котором они работают [7]. Выделяют три класса алгоритмов удаления невидимых линий или поверхностей:
¨ Алгоритмы, работающие в объектном пространстве.
¨ Алгоритмы, работающие в пространстве изображения (экрана).
¨ Алгоритмы, формирующие список приоритетов.
Алгоритмы, работающие в объектном пространстве, имеют дело с физической системой координат, в которой описаны эти объекты. При этом получаются весьма точные результаты, ограниченные лишь точностью вычислений. Полученные изображения можно свободно увеличивать во много раз. Алгоритмы, работающие в объектном пространстве, особенно полезны в тех приложениях, где необходима высокая точность.
Алгоритмы же, работающие в пространстве изображения, имеют дело с системой координат того экрана, на котором объекты визуализируются. При этом точность вычислений ограничена разрешающей способностью экрана. Обычно разрешение экрана бывает довольно низким, типичный пример: 512´512 точек. Результаты, полученные в пространстве изображения, а затем увеличенные во много раз, не будут соответствовать исходной сцене. Например, могут не совпасть концы отрезков. Алгоритмы, формирующие список приоритетов, работают попеременно в обеих упомянутых системах координат.
Объем вычислений для любого алгоритма, работающего в объектном пространстве и сравнивающего каждый объект сцены со всеми остальными объектами этой сцены, растет теоретически, как квадрат числа объектов (n2). Аналогично, объем вычислений любого алгоритма, работающего в пространстве изображения и сравнивающего каждый объект сцены с позициями всех пикселей в системе координат экрана, растет теоретически, как nN. Здесь n обозначает количество объектов (тел, плоскостей или ребер) в сцене, а N — число пикселей. Теоретически трудоемкость алгоритмов, работающих в объектном пространстве, меньше трудоемкости алгоритмов, работающих в пространстве изображения, при n < N. Однако на практике это не так. Дело в том, что алгоритмы, работающие в пространстве изображения, более эффективны потому, что для них легче воспользоваться преимуществом когерентности при растровой реализации.
Методы закраски
Тени
Алгоритмы затенения в случае точечных источников света идентичны алгоритмам удаления скрытых поверхностей. В алгоритме удаления скрытых поверхностей определяются поверхности, которые можно увидеть из точки зрения, а в алгоритме затенения выделяются поверхности, которые можно «увидеть» из источника света. Поверхности, видимые как из точки зрения, так и из источника света, не лежат в тени. Те же поверхности, которые видимы из точки зрения, но невидимы из источника света, находятся в тени. Эти рассуждения можно легко распространить на случай нескольких источников света. Отметим, однако, что, используя такой простой подход, нельзя смоделировать тени от распределенных источников света. При наличии таких источников потребуется вычислять как тени, так и полутени.
Поскольку алгоритмы затенения и удаления скрытых поверхностей одинаковы, представляется возможным обрабатывать описание объекта, используя лишь один из этих алгоритмов, последовательно применяя его к точке зрения и к каждому из точечных источников света. Совокупность полученных результатов позволяет определить, какие части объекта видимы наблюдателю и какие видны из одного или нескольких источников света. На основании этой информации осуществляется закраска сцены. Если правильно организовать вычислительный процесс, определение теней можно проводить лишь один раз для серии сцен, которые состоят из одних и тех же объектов, рассматриваемых с различных точек зрения. Источники света предполагаются неподвижными относительно объектов. Все это оказывается возможным потому, что тени не зависят от положения точки зрения.
Детализация поверхностей
Существуют два способа детализации поверхности: цветом и фактурой. В результате применения к гладкой поверхности детализации цветом форма поверхности не изменяется, если же производится детализация фактурой – поверхность становится шероховатой.
Детализация цветом
Детализацию цветом на глубоком уровне легко осуществить путем введения многоугольников детализации поверхности, чтобы выделить особенности (такие, как двери, окна и надписи) на основном многоугольнике (например, на стене здания). Многоугольники детализации поверхности лежат в одной плоскости с основными многоугольниками и так помечены в структуре данных, чтобы алгоритм удаления скрытых поверхностей мог присвоить им более высокие приоритеты, чем основным многоугольникам.
По мере того как детализация цветом становится более тонкой и сложной, непосредственное моделирование при помощи многоугольников становится менее практичным.
Рисование геометрических объектов
Работа с буферами и задание цвета объектов
OpenGL содержит внутри себя несколько различных буферов. Среди них фрейм буфер (где строится изображение), z-буфер, служащий для удаления невидимых поверхностей, буфер трафарета и аккумулирующий буфер.
Для очистки внутренних буферов служит процедура glClear(GLbitfield mask), очищающая буферы, заданные переменной mask. Параметр mask является комбинацией следующих констант:
GL_COLOR_BUFFER_BIT – очистить буфер изображения (фреймбуфер);
GL_DEPTH_BUFFER_BIT – очистить z-буфер;
GL_ACCUM_BUFFER_BIT – очистить аккумулирующий буфер;
GL_STENCIL_BUFFER_BIT – очистить буфер трафарета.
Цвет, которым очищается буфер изображения, задаётся процедурой glClearColor(GLfloat red, GLfloat green, GLfloat blue, GLfloat alpha). Значение, записываемое в z-буфер при очистке, задаётся процедурой glClearDepth(GLfloat depth). Значение, записываемое в буфер трафарета при очистке, задаётся процедурой glClearStencil(GLint s). Цвет, записываемый в аккумулирующий буфер при очистке, задаётся процедурой glClearAccum(GLfloat red, GLfloat green, GLfloat blue, GLfloat alpha).
Сама команда glClear очищает одновременно все заданные буферы, заполняя их соответствующими значениями.
Для задания цвета объекта служит процедура
glColor{3 4}{b s i f d ub us ui}[v](TYPE red, …).
Цифра 3 или 4 указывает на количество требуемых аргументов, а буква, следующая за цифрой, показывает тип аргументов. Например, в процедуру glColor3i будут переданы три параметра целого типа.
Если значение параметра не задано, то оно автоматически полагается равным единице. Версии процедуры glColor, где параметры являются переменными с плавающей точкой, автоматически обрезают переданные значения в отрезок [0, 1].
Процедура glFlush() вызывает немедленное рисование ранее переданных команд. При этом ожидания завершения всех ранее переданных команд не происходит. С другой стороны, команда glFinish() ожидает, пока не будут завершены все ранее переданные команды.
Если нужно включить удаление невидимых поверхностей методом z-буфера, то z-буфер необходимо очистить и передать команду glEnable(GL_DEPTH_TEST). Команду glEnable() можно выполнить только один раз при инициализации системных переменных OpenGL. Очистку z-буфера необходимо производить перед началом построения очередного кадра изображения.
Задание графических примитивов
Все геометрические примитивы в OpenGL задаются в терминах вершин. Каждая вершина задаётся набором чисел, определяющих её координаты в пространстве.
OpenGL работает с однородными координатами (x, y, z, w). Если координата z не задана, то она считается равной нулю. Если координата w не задана, то она считается равной единице.
Под линией в OpenGL подразумевается отрезок, заданный своими начальной и конечной вершинами.
Под гранью (многоугольником) в OpenGL подразумевается замкнутый выпуклый многоугольник с несамопересекающейся границей.
Все геометрические объекты в OpenGL задаются посредством вершин, а сами вершины задаются процедурой
glVertex{2 3 4}{s i f d}[v](TYPE x, …),
где реальное количество параметров определяется первым суффиксом (2, 3 или 4), а суффикс v означает, что в качестве единственного аргумента выступает массив, содержащий необходимое количество координат. Например:
glVertex2s(1, 2);
glVertex3f(2.3, 1.5, 0.2);
GLdouble vect[] = {1.0, 2.0, 3.0, 4.0};
glVertex4dv(vect);
Для задания геометрических примитивов необходимо как-то выделить набор вершин, определяющих этот объект. Для этого служат процедуры glBegin() и glEnd(). Процедура glBegin(GLenum mode) обозначает начало списка вершин, описывающих геометрический примитив. Тип примитива задаётся параметром mode, который принимает одно из следующих значений:
GL_POINTS – набор отдельных точек;
GL_LINES – пары вершин, задающих отдельные точки;
GL_LINE_STRIP – незамкнутая ломаная;
GL_LINE_LOOP – замкнутая ломаная;
GL_POLYGON – простой выпуклый многоугольник;
GL_TRIANGLES – тройки вершин, интерпретируемые как вершины отдельных треугольников;
GL_TRIANGLE_STRIP – связанная полоса треугольников;
GL_TRIANGLE_FAN – веер треугольников;
GL_QUADS – четвёрки вершин, задающие выпуклые четырёхугольники;
GL_QUAD_STRIP – полоса четырёхугольников.
Процедура glEnd() отмечает конец списка вершин.
Между командами glBegin() и glEnd() могут находится команды задания различных атрибутов вершин: glVertex(), glColor(), glNormal(), glCallList(), glCallLists(), glTexCoord(), glEdgeFlag(), glMaterial(). Между командами glBegin() и glEnd() все остальные команды OpenGL недопустимы и приводят к возникновению ошибок.
Рассмотрим в качестве примера задание окружности:
glBegin(GL_LINE_LOOP);
for (int i = 0; I < N; i++)
{
float angle = 2 * M_PI * i / N;
glVertex2f(cos(angle), sin(angle));
}
glEnd();
Хотя многие команды могут находиться между glBegin() и glEnd(), вершины генерируются при вызове glVertex(). В момент вызова glVertex() OpenGL присваивает создаваемой вершине текущий цвет, координаты текстуры, вектор нормали и т. д. Изначально вектор нормали полагается равным (0, 0, 1), цвет полагается равным (1, 1, 1, 1), координаты текстуры полагаются равными нулю.
Преобразование объектов в пространстве
Задание моделей закрашивания
Линия или заполненная грань могут быть нарисованы одним цветом (плоское закрашивание, GL_FLAT) или путём интерполяции цветов в вершинах (закрашивание Гуро, GL_SMOOTH).
Для задания режима закрашивания служит процедура glShadeModel(GLenum mode), где параметр mode принимает значение GL_SMOOTH или GL_FLAT.
Аппаратные средства машинной графики
Математическое и программное обеспечение компьютерной графики нельзя рассматривать в отрыве от аппаратных средств, применяемых на различных этапах работы с изображениями. Все эти средства принято делить на три большие группы:
· устройства ввода (сканеры, дигитайзеры/графические планшеты, цифровые фото- и видеокамеры);
· устройства вывода (мониторы, принтеры, плоттеры, цифровые проекторы);
· устройства обработки (графические ускорители, кодеры MPEG и др.).
Поскольку детальная информация о принципах действия, параметрах и применении вышеперечисленных устройств дается в соответствующих разделах других курсов, например «Периферийные устройства ЭВМ», подробнее остановимся только на аппаратных средствах первой группы, на рынке которых наблюдается в настоящий момент бум новых средств и технологий.
Устройства ввода
Существуют различные технические средства, осуществляющие процесс преобразования изображений в цифровую форму, например: сканеры, дигитайзеры (графические планшеты), цифровые фото- и видеокамеры. В каждом конкретном случае важно правильно выбрать нужное устройство, руководствуясь его техническими характеристиками, для получения оцифрованного изображения с требуемой детальностью и цветовой гаммой.
Фирмы-производители
На мировом рынке представлено достаточно большое число фирм-производителей сканеров. Наиболее популярные модели производят Hewlett-Packard, Agfa, Canon, Mustek.
Дигитайзеры
Дигитайзер (графический планшет) — это устройство, предназначенное для оцифровки изображений, применяемое для создания на компьютере рисунков и набросков (рис. 11.2). Художник создает изображение на экране, но его рука водит пером по планшету. Как правило, планшет используют профессиональные художники для более точной обработки (создания) изображений.
Рис. 11.2. Графический планшет
Кроме того, дигитайзер можно использовать просто как аналог манипулятора «мышь».
Принцип действия
Дигитайзер, или планшет, как его часто называют, состоит из двух основных элементов: основания и курсора, двигающегося по его поверхности. Принцип действия дигитайзера основан на фиксации местоположения курсора с помощью встроенной в планшет сетки. При нажатии на кнопку курсора его местоположение на поверхности планшета фиксируется, а его координаты передаются в компьютер. Сетка состоит из проволочных или печатных проводников с довольно большим расстоянием между соседними проводниками (от трех до шести мм).
Фирмы-производители
Наиболее популярны модели следующих фирм: CalComp, NUMONICS, WACOM.
– Конец работы –
Используемые теги: основы, компьютерной, графики0.06
Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: ОСНОВЫ КОМПЬЮТЕРНОЙ ГРАФИКИ
Если этот материал оказался полезным для Вас, Вы можете сохранить его на свою страничку в социальных сетях:
Твитнуть |
Новости и инфо для студентов