Раздел 2. Компьютерная графика

6. Отображение графической информации: интерактивная компьютерная графика, деловая, иллюстративная графика, обработка образов в машинном зрении, основы теории цвета, цветовые системы RGB, CMYK, VHS, методы формирования цвета, основные виды графики (растровая, векторная, фрактальная), основные стандарты компьютерной графики.

Под компьютерной графикой обычно понимают автоматизацию процессов подготовки, преобразования, хранения и воспроизведения графической информации с помощью ЭВМ. Под графической информацией понимаются модели объектов и их изображения. Основные области применения компьютерной графики:

• Научная графика. Появилось первым. Назначение – визуализация объектов научных исследований, графическая обработка результатов расчетов, проведение вычислительных экспериментов с наглядным представлением их результатов.

• Деловая графика. Это область компьютерной графики часто используемой в различных учреждениях: плановые показатели, статистические сводки, отчетная документация, т.е. с помощью деловой графики создают иллюстративные материалы.

• Иллюстративная графика. Эти программные средства используют для произвольного рисования, как если бы это делали на бумаге с помощью кисточек, карандашей, циркуля, линейки и т.п. Пакеты иллюстративной графики (графические редакторы) не имеют производственной направленности, и поэтому их относят к прикладному ПО общего назначения.

• Художественная и рекламная графика. С ее помощью создаются рекламные ролики, мультфильмы, компьтерные игры, видеоуроки, видеопрезентации и т.п.

• Мультимедиа. Это объединение высококачественного изображения на экране компьютера (в том числе графической анимации и видеокадров) с реалистичным звуковым сопровождением.

Машинное зрение и анализ изображений

Цель машинного зрения - принятие решений о реальных физических объектах и сценах, основываясь на воспринимаемых изображениях. Машинное зрение теснейшим образом взаимодействует с областью обработки изображений, часто трудно однозначно отнести возникающие задачи и применяемые методы решения к одной из этих областей. В задачи, рассматриваемые в рамках машинного зрения, в частности, входят:

• Обнаружение/распознавание/отслеживание объектов, обладающих определенными свойствами (в самом широком смысле) на статическом изображении и в видеопотоке;

• Восстановление 3D формы по 2D изображениям с помощью:

• Стереореконструкции карты глубины (Shape from stereo);

• Реконструкции поля нормалей и карты глубины по закраске полутонового изображения;

• Реконструкции карты глубины по текстуре (Shape from texture)

• Определению формы по перемещению (Shape from motion)

• Выделение на изображениях структур определенного вида (например краев - резких переходов яркости), сегментация изображений (например на области, однородные по определенному признаку);

• Анализ оптического потока (нахождения перемещения пикселей между двумя изображениями);

Приложения методы Computer Vision находят в следующих областях:

• Мультимедия-приложения, игры (реальный пример - автоматическое создание модели игрока для Quake3);

• Естественный интерфейс человек-компьютер, основанный на жестах, мимике и голосовых командах пользователя, не обремененный устройствами "удобными компьютеру" (клавиатурой, мышью) - human-centered computing;

• Медицина (автоматический анализ медицинских изображений – рентген, томография, УЗИ);

• Охранные системы;

• Системы распознавания рукописного и печатного текста;

• Сжатие видео с учетом содержимого передающегося видеопотока;

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

Каждый цвет спектра характеризуется своей длиной волны, то есть он может быть совершенно точно задан длиной волны или частотой колебаний. Световые волны сами по себе не имеют цвета. Цвет возникает лишь при восприятии этих волн человеческим глазом и мозгом. Деление спектра на семь цветов, введенное Ньютоном - чистая условность. Цвет предметов возникает, главным образом, в процессе поглощения волн. Цвета, которые используют белый свет, вычитая из него определенные участки спектра, называются субтрактивными (вычитательными).

Цветовая модель RGB

На мониторах с электронно-лучевыми трубками цвета создаются в результате бомбардировки люминофора тремя электронными лучами. Черный цвет получается, когда интенсивность всех трех составляющих равна нулю, белый - при сложении всех цветов максимальной интенсивности. Это называется аддитивной (суммирующей) моделью Red (красный), Green (зеленый), Blue (синий).

В современных компьютерах воспроизводится 256 (от 0 до 255) значений каждого из трех цветов, следовательно, общее количество возможных цветов на мониторе = 256 в третьей степени = 16,7 млн. Суммарный цвет зависит от того, какое количество каждой из цветовых компонент присутствует в изображении. Красный: R = 255, G = 0, B = 0; желтый: R = 255, G = 255, B = 0; оттенки серого (от черного к белому) при равных значениях всех трех составляющих. Белый цвет, если все значения равны 255.

Цветовая модель HSB

В основе модели Hue (тон), Saturation (насыщенность), Brightness (яркость) лежит модель RGB. Модель HSB призвана упростить работу с цветами, так как она максимально приближена к принципу восприятия цвета человеческим глазом.

Тон - спектральные цвета (чистые цвета солнечного спектра) или цветовые тона (Hue) располагаются по цветовому кругу и характеризуются положением на нем, которое определяется величиной угла в диапазоне от 0 до 360°:

0° соответствует красному, 120° - зеленому, 240° - синему

Эти цвета обладают максимальной насыщенностью и яркостью (100%).

Насыщенность (Saturation) изменяется в горизонтальной плоскости от 0 до 100%. При значении насыщенности 0% любой цвет становится белым.

Яркость (Brightness) - параметр, определяющий затеммненность или освещенность тона, изменяется в вертикальной плоскости. При значении яркости 0% любой цвет становится черным.

Модель HSB более удобна для создания гармоничных сочетаний цветов, оставаясь при этом (в сущности) моделью RGB.

Цветовая модель CMYK

При печати на бумагу наносится краска - материал, который поглощает и отражает световые волны различной длины; иными словами краску можно рассматривать как фильтр, который пропускает строго определенные лучи света, вычитая их, и отражая все остальные. При выводе цветного изображения на печать используется субтрактивная цветовая модель CMY: Cyan (голубой), Magenta (пурпурный), Yellow (желтый). В этой модели основные цвета образуются путем вычитания из белого цвета основных аддитивных цветов модели RGB. В таком случае и основных субтрактивных цветов тоже будет три: голубой - Cyan (белый минус красный), пурпурный - Magenta (белый минус зеленый), желтый - Yellow (белый минус синий).

Аддитивная модель подходит для таких средств формирования цветного изображения, как ЭЛТ, прозрачные экраны и позитивные (слайдовые) фотопленки. В них в качестве первичных используются красный, зеленый и синий цвета. Цвет отдельной точки изображения можно охарактеризовать положением в цветовом кубе/ Вдоль осей координатной системы такого цветового куба откладываются интенсивности первичных компонентов. В нормализованном цветовом кубе любой цвет можно представить определенной точкой внутри такого единичного куба.

Субтрактивная цветовая система используется в печатной технологии, включая цветные принтеры, RIP-устройства и офсетные прессы. Для определения заданного цвета здесь используется вычитание различных компонент из белого цвета. Этот процесс носит название субтрактивного смешения.

Виды компьютерной графики.

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

Растровая компьютерная графика.

Основой растрового представления графики является пиксел (точка) с указанием ее цвета. Изображение представляется в виде большого количества точек – чем их больше, тем визуально качественнее изображение и больше размер файла. Т.е. одна и таже картинка может быть представлена с лучшим или худшим качеством в соответствии с количеством точек на единицу длины – разрешением (обычно, точек на дюйм – dpi или пикселов на дюйм – ppi). Кроме того, качество характеризуется еще и количеством цветов и оттенков, которые может принимать каждая точка изображения.

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

Векторное представление заключается в описании элементов изображения математическими кривыми с указанием их цветов и заполненности. Очевидно, такое описание займет значительно меньше места, чем в первом случае. Еще одно преимущество - качественное масштабирование в любую сторону. К сожалению векторный формат становится невыгодным при передаче изображений с большим количеством оттенков или мелких деталей.

Фрактальная компьютерная графика.

Фрактальная графика, как и векторная - вычисляемая, но отличается от нее тем, что никакие объекты в памяти компьютера не хранятся. Изображение строится по уравнению (или по системе уравнений), поэтому ничего, кроме формулы, хранить не надо. Изменив коэффициенты в уравнении, можно получить совершенно другую картину.

Стандартизация в компьютерной графике.

Важную роль в разработке методологии стандартизации машинной графики сыграла конференция в Сейлаке (Франция). На конференции были сформулированы и обсуждены основные условия и проблемы стандартизации. Структура прикладной графической системы, удовлетворяющей сформулированным требованиям, может быть представлена в виде шестиуровневой модели.

Верхний уровень стандартизации - IGES предназначен для обеспечения мобильности компонент САПР. Средний уровень стандартизации - уровень базового графического пакета (GKS) определяется выбором базовых функций системы. Этот интерфейс делает базовую графическую систему независимой от области применения. Нижний уровень стандартизации - уровень связи с виртуальным графическим устройством (CGI) зависит от выбора примитивов ввода/вывода, являющихся абстракцией возможностей устройств. Этот интерфейс делает базовую графическую систему аппаратно-независимой.

Главными организациями формирующими международные стандарты в области информационной технологии являются ISO (International Organization for Standartization) и IEC (International Electrotechnical Commission). Основными стандартами являются :

1. GKS (Graphical Kernel System) - набор базовых функций для 2D аппаратно-независимой машинной графики.

2. GKS-3D (Graphical Kernel System for 3 Dimensions) - расширение GKS для поддержки базовых функций в 3D.

3. PHIGS (Programmer's Hierarchical Interactive Graphics System) - набор базовых функций 3D графики аналогичный GKS-3D, но в отличие от GKS-3D, ориентированной на непосредственный вывод графических примитивов, группируемых в сегменты, графическая информация накапливается в иерархической структуре данных. В целом PHIGS ориентирован на приложения, требующие быстрой модификации графических данных, описывающих геометрию объектов.

4. Языковые интерфейсы (Language bindings) - представление функций и типов данных функциональных графических стандартов в стандартизованных языках программирования.

5. CGM (Computer Graphics Metafile) - аппаратно-независимый формат обмена графической информацией. Используется для передачи и запоминания информации, описывающей изображения.

6. CGI (Computer Graphics Interafce) - набор базовых элементов для управления и обмена данными между аппаратно-независимым и аппаратно-зависимым уровнями графической системы.

7. CGRM (Computer Graphics Reference Model) - модель стандартов в машинной графике, которая определяет концепции и взаимосоотношения применительно к будущим стандартам в машинной графике.

8. Регистрация - механизм регистрации стандартизуемых аспектов примитивов вывода, обобщенных примитивов, escape-функций (для доступа к аппаратным возможностям устройств) и других графических элементов.

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

7. Аппаратные средства компьютерной графики: устройства графического ввода/вывода информации, аппаратная организация графических подсистем, графические карты, акселераторы, организация видеопамяти, устройства формирования видеосигнала, основные режимы работы графических карт.

CRT–мониторы. CRT-монитор имеет стеклянную трубку, внутри которой вакуум, т.е. весь воздух удален. С фронтальной стороны внутренняя часть стекла трубки покрыта люминофором. Люминофор - это вещество, которое испускает свет при бомбардировке его заряженными частицами. Для создания изображения в CRT-мониторе используется электронная пушка, которая испускает поток электронов сквозь металлическую маску или решетку на внутреннюю поверхность стеклянного экрана монитора, которая покрыта разноцветными люминофорными точками. Поток электронов на пути к фронтальной части трубки проходит через модулятор интенсивности и ускоряющую систему, работающие по принципу разности потенциалов. В результате, электроны приобретают большую энергию, часть из которой расходуется на свечение люминофора. Люминофор начинает светиться, как было сказано выше, под воздействием ускоренных электронов, которые создаются тремя электронными пушками. Для управления электронно-лучевой трубкой необходима и управляющая электроника, качество которой во многом определяет и качество монитора. Понятно, что электронный луч, предназначенный для красных люминофорных элементов, не должен влиять на люминофор зеленого или синего цвета. Чтобы добиться такого действия используется специальная маска. LCD Мониторы. Экран LCD-монитора представляет собой массив маленьких сегментов (называемых пикселями), которые могут манипулироваться для отображения информации. LCD-монитор имеет несколько слоев, где ключевую роль играют две панели сделанные из свободного от натрия и очень чистого стеклянного материала, называемого субстрат или подложка, которые собственно и содержат тонкий слой жидких кристаллов между собой. Жидкокристаллическая панель освещается источником света (в зависимости от того, где он расположен, жидкокристаллические панели работают на отражение или на прохождение света). Плоскость поляризации светового луча поворачивается на 90° при прохождении одной панели. При появлении электрического поля молекулы жидких кристаллов частично выстраиваются вдоль поля, и угол поворота плоскости поляризации света становится отличным от 90 градусов.

Принтеры. Основное распространение приобрели лазерные принтеры. Основной принцип действия таких принтеров основан на следующей последовательности. Изображение формируется на компьютере в растровой форме и предается на принтер. В соответствии с этими данными для каждой строки, лазер пробегает вдоль фоточувствительного барабана. Там где лазер светился, поверхность заряжается. Далее на барабан сыплется порошок из смеси пигментов и смол. Под действием заряда на барабане порошок прилипает. Затем к барабану прижимается бумага, и порошок переходит нее. Проходя через печь, порошок припаивается к бумаге. Струйный принтер использует чернила для рисования. Имеются резервуары с краской, из них она поступает в так называемое сопло. Сопло представляет собой небольшой канал. В канале встраивается термоэлемент. При резком нагревании образуется пузырек с газом и расширяясь он выталкивает капельку краски. Используя различные краски можно создавать цветное изображение. Матричные принтеры используют методику ударного переноса красителя. Головка с набором иголок движется вдоль листа. Между листом и головкой находиться красящаяся лента. При этом при необходимости иголка ударяет по бумаге сквозь ленту и на бумаге остается точка. После прохода лист поднимается на одну строку и цикл повторяется.

Плоттеры. Планшетный плоттер представляет собой ровную поверхности, над которой ходит головка с карандашами, укрепленная на двух перпендикулярных линейках. При этом плоттер принимает команды в векторном режиме. Так как рисование ведется карандашом то и количество цветов ограничено их количеством. Как правило, планшетные плоттеры небольших размеров. Рулонный плоттер лист прижимает к вращающемуся валику, над которым ходит головка.

Сканер похож на планшетный плоттер, только вместо рисующей головки расположена сканирующая, которая представляет собой ПЗС матрицу.

Видеоадаптер VGA содержит следующие элементы: видеопамять; ROM Video BIOS; контроллер ЭЛТ, или CRTC (Cathode Ray Tube Controller); графический контроллер; контроллер атрибутов; секвенсор (sequencer); цифро-аналоговый преобразователь (ЦАП) данных, хранящихся в ОЗУ ЦАП, или RAMDAC (Random Access Memory Digital-to-Analog Converter); синхронизатор; тактовые генераторы; интерфейс с шиной ввода/вывода; 15-контактный D-образный разъем для подключения монитора. Большинство перечисленных элементов видеоадаптера содержат специальные 8-разрядные регистры, доступные центральному процессору для чтения/записи данных. Эти регистры, как правило, предназначены для управления работой со¬ответствующих элементов видеоадаптера. Модифицируя содержимое этих реги¬стров, CPU управляет работой видеоадаптера.

Помимо регистров в составе указанных элементов, видеоадаптер VGA имеет несколько отдельных регистров, участвующих в процессе формирования видео¬сигнала, в том числе: многоцелевой выходной регистр (предназначен для задания адресов портов ввода/вывода элементов видеоадаптера, начального адреса кадрового буфера и выбора тактового генератора); регистр состояния (доступен только для чтения; используется для синхрони¬зации процесса обновления кадрового буфера с сигналами обратного хода кадровой развертки).

Несмотря на значительные различия в характеристиках и возможностях, акселераторы имеют несколько базовых элементов, обеспечивающих аппаратное ускорение основных этапов ЗD-конвейера: геометрический процессор (Geometry Processor); механизм прорисовки (Rendering Engine); видеопамять; цифро-аналоговый преобразователь (RAMDAC); дополнительные устройства (в зависимости от набора дополнительных мультимедийных функций).Геометрический процессор предназначен для аппаратного ускорения этапов геометрической стадии 3D-конвейера. Механизм прорисовки, часто называемый конвейером рендеринга, является основ¬ной частью типового ЗD-акселератора и включает в себя два элемента: механизм об¬работки элементов текстур (Texel Engine) и механизм обработки итогового кадра (Pixel Engine). Каждый из этих элементов использует свой участок локальной памяти, на¬зываемый буфером текстур и кадровым буфером соответственно. Часто для обо¬значения Texel Engine и Pixel Engine используются термины блок или модуль.

Видеопамять — это специализированное ОЗУ, размещенное на плате видеоадаптера и предназначенное для хранения цифрового образа формируемого изо¬бражения. Синонимами данного понятия являются термины видеобуфер и Video RAM. Видео¬память видеоадаптеров, в которых для построения изображения используется не только своя собственная, но и системная память PC (например, видеоадаптеры с интерфейсом AGP), часто называют локальной, подчеркивая тем самым место ее физического размещения.

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

Область видеопамяти, используемая для хранения цифрового образа изображения, называется кадровым буфером (frame buffer). Как правило, размер кадрового буфера меньше, чем объем видеопамяти. Например, в видеорежиме 640x480/16 кадровый буфер занимает 150 Кбайт из 256 доступных. Помимо кадрового буфера, в видеопамяти хранятся и другие данные, такие, как, например, загружаемые национальные шрифты.

Количество адресуемых ячеек видеопамяти (256 К) превышает адресное пространство (128 К), отведенное операционной системой для обращения к видеопамяти. Поэтому для того чтобы CPU мог обратиться к любой ячейке, видеопамять разбивается на отдельные области, именуемые банками или страницами (обычно на четыре банка размером 64 Кбайт каждый). CPU формирует код адреса в пределах отведенного диапазона, обращаясь тем самым к одноименным ячейкам в четырех различных банках одновременно.

Метод, используемый для адресации видеопамяти, определяется способом хра¬нения информации о цвете пиксела. В графическом режиме она может храниться в формате Packed Display Format (PDF) или в виде цветовых плоскостей. Если для кодирования цвета пиксела используется 8 бит (видеорежим 13h), то применяется метод PDF — формат пакетного (компактного) хранения содержимо¬го кадрового буфера. Согласно формату PDF, номер цвета пиксела целиком хранит¬ся в одной 8-разрядной ячейке кадрового буфера. В формате PDF используется линейная адресация кадрового буфера, не требующая переключения банков. Метод цветовых плоскостей для организации кадрового буфера первоначаль¬но использовался в видеоадаптерах CGA и EGA. Цветовая плоскость — это учас¬ток видеопамяти, представляющий собой матрицу бит, каждый из которых соот¬ветствует отдельному пикселу на экране ЭЛТ. Адресуемым элементом такой плоскости является не байт, а бит. Количество цветовых плоскостей равно коли¬честву бит, отводимых для кодирования цвета пиксела, а их размеры со¬ответствуют разрешению экрана. Важной характеристикой видеопамяти является разрядность ее ячеек, которая определяет разрядность внутренней шины данных видеоадаптера. В современных видеоадаптерах исполь¬зуется 64- или 128-разрядная внутренняя шина, а наиболее совершенные модели видеоадаптеров имеют 256-разрядную шину данных.

Видеосигнал, подаваемый на модуляторы ЭЛТ, а также импульсы строчной и кадровой синхронизации, подаваемые в блок разверток монитора, формируются видеоадаптером на основе цифрового образа формируемого изображения — матрицы NxM n-разрядных чисел. Эти данные за¬носятся центральным процессором PC в память видеоадаптера, или видеопамять. Участок видеопамяти, отведенный для хранения цифрового образа текущего изоб¬ражения (кадра), называется кадровым буфером или фрейм-буфером (от англ. frame buffer— кадровый буфер). Видеоадаптер последовательно считывает (сканирует) со¬держимое ячеек кадрового буфера и формирует на своем выходе видеосигнал, уровень которого пропорционален значениям, хранящимся в каждой из ячеек. Сканирование видеопамяти осуществляется синхронно с перемещением электронного луча по экрану ЭЛТ. В результате яркость каждого пиксела на экране монитора оказывается пропорциональной значению, содержащемуся в соответствующей ячейке па¬мяти видеоадаптера.

Графический режим является основным режимом работы видеосистемы мультимедийного PC. В этом режиме на экран монитора может быть выведено произвольное изображение: текст, рисунок, фотография, анимация или видеосюжет. В частности, в таком режиме работает видеосистема PC под управлением операционной системы Windows. В графическом режиме содержимое каждой ячейки кадрового буфера является кодом цвета соответствующего пиксела экрана.

В текстовом (символьном) режиме, так же, как и в графическом, изображение на экране монитора представляет собой множество пикселов и характеризуется разрешением N x M. Однако, все пикселы разбиты на группы, называемые знакоме¬стами или символьными позициями (character positions или character boxes — сим¬вольные ячейки) размером p x q. В каждом из знакомест может быть отображен один из 256 символов. Типичным текстовым режимом явля¬ется режим 80x25 символов.

8. Алгоритмы растровой графики: основные растровые алгоритмы, отрисовка точки через BIOS, прямая запись в видеопамять посредством API операционной системы, отрисовка отрезка алгоритмом Брезенхема, построение растровой развертки окружности и эллипса, алгоритмы заливки замкнутых фигур с границей заданного цвета, понятие связности, заливка многоугольников, аффинные преобразования, однородные координаты, повороты, сдвиги, переносы в матричном виде, проецирование трехмерных объектов, виды проекций, использование матричного вида при проецировании, особенности проецирования гладких поверхностей.

Как уже отмечалось, все операции по модификации содержимого видеопамяти и регистров видеоадаптера VGA выполняет центральный процессор. Реализация любой графической операции (смена видеорежима, чтение/запись информации в кадровый буфер, управление курсором и т. п.) требует от центрального процессора выполнения весьма длинной последовательности элементарных команд (чтение/запись, перемещение данных в регистрах и др.). Кроме того, во время этих действий в регистры видеоадаптера заносятся константы, значения которых для различных моделей VGA-совместимых адаптеров могут различаться. С целью упрощения про¬цедуры программирования видеоадаптера, а также для обеспечения совместимости аппаратного и программного обеспечения все наборы команд (подпрограммы) CPU, реализующие графические функции, помещаются в специальное ПЗУ, расположен¬ное на плате видеоадаптера VGA. Эти подпрограммы образуют так называемое рас¬ширение базовой системы ввода/вывода (BIOS extension) для решения задач вывода изображения на экран монитора и называются Video BIOS. Фактически Video BIOS — это набор подпрограмм, написанных в кодах ко¬манд центрального процессора и предназначенных для реализации основных функций видеосистемы. Набор этих функций принято называть видеосервисом. Кроме того, Video BIOS содержит множество данных (констант), необходимых для работы в различных видеорежимах, а также сведения о производителе, модели и возможностях видеоадаптера. Видеосервис Video BIOS реализуется с помощью механизма программных прерываний, т. е. путем выдачи прикладной программой центральному процессору команды INT на прерывание с указанием номера прерывания. После завершения программы обработки прерывания CPU возвращается к выполнению приостановленной программы. Архитектурой PC предусмотрены аппаратные и программные прерывания.

Брезенхем предложил алгоритм, обеспечивающий минимизацию отклонения сгенерированного образа от истинного отрезка. Основная идея алгоритма состоит в том, что если угловой коэффициент прямой < 1/2, то естественно точку, следующую за точкой (0,0), поставить в позицию (1,0) (рис. а), а если угловой коэффициент > 1/2, то - в позицию (1,1). Для принятия решения, куда заносить очередной пиксел, вводится величина отклонения Е точной позиции от середины между двумя возможными растровыми точками в направлении наименьшей относительной координаты. Знак Е используется как критерий для выбора ближайшей растровой точки.

Если Е < 0, то точное Y-значение округляется до последнего меньшего целочисленного значения Y, т.е. Y-координата не меняется по сравнению с предыдущей точкой. В противном случае Y увеличивается на 1.

Для простоты и без ограничения общности рассмотрим генерацию 1/8 окружности, центр которой лежит в начале координат. Окружность с центром в начале координат описывается уравнением: X2 + Y2 = R2. Алгоритм Брезенхема пошагово генерирует очередные точки окружности, выбирая на каждом шаге для занесения пиксела точку растра Pi(Xi, Yi), ближайшую к истинной окружности. Рассмотрим генерацию 1/8 окружности по часовой стрелке, начиная от точки X=0, Y=R. Проанализируем возможные варианты занесения i+1-й точки, после занесения i-й. При генерации окружности по часовой стрелке после занесения точки (Xi, Yi) следующая точка может быть (см. рис. 0.1а) либо Pg = (Xi+1, Yi) - перемещение по горизонтали, либо Pd = (Xi+1, Yi-1) - перемещение по диагонали, либо Pv = (Xi, Yi-1) - перемещение по вертикали.

Заливаемая область или ее граница - некоторое связное множество пикселов. По способам доступа к соседним пикселам области делятся на 4-х и 8-ми связные. В 4-х связных областях доступ к соседним пикселам осуществляется по четырем направлениям - горизонтально влево и вправо и в вертикально вверх и вниз. В 8-ми связных областях к этим направлениям добавляются еще 4 диагональных. Используя связность мы может, двигаясь от точки затравки, достичь и закрасить все пикселы области. Простой алгоритм заливки состоит в следующем:

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

• если нет, то пиксел перекрашивается, затем проверяются и если надо перекрашиваются 4 соседних пиксела.

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

• пикселы в строке меняются только на границах;

• при перемещении к следующей строке размер заливаемой строки скорее всего или неизменен или меняется на 1 пиксел.

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

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

Определить принадлежность пиксела многоугольнику можно, например, подсчетом суммарного угла с вершиной на пикселе при обходе контура многоугольника. Если пиксел внутри, то угол будет равен 360°, если вне - 0°.

Вычисление принадлежности должно производиться для всех пикселов экрана и так как большинство пикселов скорее всего вне многоугольников, то данный способ слишком расточителен. Реально используются алгоритмы построчного заполнения, основанные на том, что соседние пикселы в строке скорее всего одинаковы и меняются только там где строка пересекается с ребром многоугольника. Это называется когерентностью растровых строк (строки сканирования Yi, Yi+1, Yi+2 на рис. ). При этом достаточно определить X-координаты пересечений строк сканирования с ребрами. Пары отсортированных точек пересечения задают интервалы заливки. Смена же количества интервалов заливки происходит только тогда, когда в строке сканирования появляется вершина.

Аффинные преобразования. Имеется прямоугольная система координат XY. Каждой точке M соответствует пара чисел (x,y). Введя дополнительную прямолинейную систему координат X*Y*, мы поставим точке М другую пару чисел (x*,y*). Переход от одной системы координат к другой описывается следующими соотношениями.

X*=альфа*х+бета*y+лямбда

У*=гамма*х+сигма*y+мю

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

Наиболее важные случаи в преобразования (1).

Поворот вокруг начальной точки на угол фи

Х*=xcos фи – у sin фи

у*=xsin фи + у cos фи

Растяжение вдоль координатных осей

Х*=альфа х

у*=гамма У

Отражение относительно оси абсцисс

Х*= х

у*=- У

Перенос

Х*= х+лямбда

у*= У+мю

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

Пусть M произвольная точка плоскости с координатами x и y. Однородными координатами данной точки называются любая тройка чисел x1,x2,x3 одновременно не равных 0 и связанных отношением

Х1/х3=х, х2/х3=у

В компьютерной графике как правило точке M(x,y) на плоскости ставится в соответствие точка M(x,y,1) в пространстве. При этом прямая соединяющая начало координат с точкой M может быть описана тройкой чисел вида (hx,hy,h) где h!=0 так как вектор с данными координатами является направляющим для прямой и всегда пересечет плоскость Z=1 в точке M(x,y,1).

Для однородных координат можно записать выражение (1) в виде матричного выражения

Тут произведение на матрицу. Символ | - перенос строки

(х*, у*, 1*)= (х,у,1)[альфа гамма 0 | бета сигма 0 | лямбда мю 1]

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

Матрица вращения

[cos(fi) sin(fi) 0| -sin(fi) cos(fi) 0| 0 0 1]

Матрица растяжения

[alpha 0 0| 0 sigma 0| 0 0 1]

Матрица отражения

[1 0 0| 0 -1 0| 0 0 1]

Матрица переноса

[1 0 0| 0 1 0| lambda mu 1]

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

Преобразования в пространстве. Точка в пространстве описывается тройкой чисел (x,y,z) называемой координатами. Перейдем к однородным координатам, заменив тройку чисел на четверку (hx,hy,hz,h), где h != 0.

Каждая точка в пространстве может быть задана четверкой чисел одновременно не равных 0 определенных с точностью до множителя. Однородные координаты позволяют перейти к матричному подходу при вычислениях в пространстве. Любые аффиные преобразования в трехмерном случае являются суперпозицией вращения, растяжения, переноса, отражений. Поэтому рассмотрим матрицы описывающие данные операции.

Матрица вращения вокруг оси ox на угол fi

[1 0 0 0| 0 cos(fi) sin(fi) 0| 0 -sin(fi) cos(fi) 0| 0 0 0 1]

Матрица вращения вокруг оси oy на угол omega

[cos(omega) 0 –sin(omega) 0| 0 1 0 0| -sin(omega) 0cos(omega) 0| 0 0 0 1]

Матрица вращения вокруг оси oz на угол beta

[cos(beta) sin(beta) 0 0 | -sin(beta) cos(beta) 0 0| 0 0 1 0 |0 0 0 1]

Матрица растяжения

[a 0 0 0 | 0 b 0 0 | 0 0 c 0 |0 0 0 1]

,где

a>0 коэффициент растяжения вдоль оси ох,b>0 коэффициент растяжения вдоль оси оy,c>0 коэффициент растяжения вдоль оси оz

Виды проектирования. При расчетах в трехмерном пространстве для отображения построенного объекта требуется выполнить операцию проецирования на плоскость. Существует множество видов проецирования. Всех их можно разделить на два основных класса центральное и параллельное.

Для получения проекции объекта на плоскость требуется провести прямую через каждую точку объекта и определить координаты пересечения этих прямых с плоскостью проекции. В случае параллельного проецирования все прямые должны быть параллельны. При центральном проецировании все прямые выходят из одной точки - центра. Параллельное проецирование можно рассматривать как частный случай центрального (центр удален от плоскости проецирования на бесконечность).

Рисунок 8

9. Трехмерная графика: алгоритмы отсечения нелицевых граней, ограничивающие тела, разбиение пространства, удаление невидимых линий алгоритмом Робертса, количественная невидимость, алгоритм Аппеля, удаление невидимых граней методом Z- буффера, метод трассировки лучей, алгоритмы упорядочивания граней методом художника, методы двоичного разбиения пространства, алгоритм Варнока, специальные методы оптимизации, метод порталов, потенциально видимые множества граней.

Удаление невидимых линий и поверхностей. Сложность задачи удаления невидимых линий и поверхностей привела к появлению большого числа различных способов ее решения, различных алгоритмов, но наилучшего решения поставленной задачи не существует. Главным недостатком всех алгоритмов является значительный объем вычислений, необходимых для определения удаляемых линий и поверхностей.

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

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

Первый класс - это алгоритмы, работаюшие в объектном пространстве, имеющие дело с физической системой координат (мировые координаты), в которой они описаны.

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

Алгоритмы первого класса используются в тех случаях, когда требуется высокая точность изображения объектов. Синтезируемые в этом случае изображения можно свободно увеличивать (уменьшать) во много раз, сдвигать или поворачивать. Точность вычислений алгоритмов второго класса ограничивается разрешающей способностью экрана. Результаты, полученные в пространстве изображения, а затем увеличенные (уменьшенные) во много раз, не будут соответствовать исходной сцене.

Наиболее часто используются алгоритмы Робертса, Аппеля, Варнока, Вейлера-Азертона, алгоритм, использующий список приоритетов (упорядочений), метод Z-буфера, метод построчного сканирования.

На практике, сравнительный анализ существующих алгоритмов удаления невидимых линий крайне затруднителен. В различных случаях при работе с различными моделями синтезируемого пространства эффективны различные алгоритмы. Даже при работе с одной и той же моделью оказывается, что в зависимости от точки наблюдения следует использовать различные алгоритмы.

Отсечение нелицевых граней. Рассмотрим задачу удаления невидимых линий для многогранника. Несложно заметить, что если вектор нормали грани составляет с вектором, задающим направление наблюдения, тупой угол, то эта грань заведомо не может быть видна. Тупой угол или нет, определяется знаком скалярного произведения векторов. В случае, когда сцена представляет собой один выпуклый многогранник, удаление нелицевых граней полностью решает проблему удаления невидимых линий (в общем случае позволяет значительно сократить кол-во рассматриваемых граней).

Алгоритм Робертса. Самым первым алгоритмом, предназначенным для удаления невидимых линий был алгоритм Робертса. Сначала в нем отбрасываются все ребра, обе определяющие грани которых являются нелицевыми. Следующим шагом является проверка оставшихся ребер со всеми гранями многогранника на закрывание. Возможны следующие случаи :

грань не закрывает ребро;

грань полностью закрывает ребро;

грань частично закрывает ребро (в этом случае ребро разбивается на несколько частей, из к-рых видимыми являются не более двух).

Алгоритм Аппеля. Этот алгоритм основан на понятии количественной невидимости точки, как кол-ва лицевых граней, ее закрывающих. Точка является видимой только в том случае, если ее количественная невидимость = 0.

Метод Z-буфера. Одним из самых простых алгоритмов удаления невидимых граней и поверхностей является метод Z-буфера (буфера глубины). В силу крайней простоты этого метода (OpenGL) часто встречаются его аппаратные реализации. Сопоставим каждому пикселу (x, y) картинной плоскости его расстояние вдоль напрвления проектирования z(x, y) - его глубину. Изначально массив глубин инициализирутся бесконечностью. Для вывода на картинную плоскость произвольной грани она переводится в свое растровое представление и для каждого пиксела этой грани находится его глубина. В случае, если эта глубина меньше значения глубины, хранящегося в Z-буфере, то этот пиксел рисуется и его глубина заносится в Z-буфер.

При реализации всех обсуждавшихся алгоритмов удаления невидимых линий и поверхностей устанавливались приоритеты, т. е. глубины объектов сцены или их расстояния от точки наблюдения. Алгоритмы, использующие список приоритетов, пытаются получить преимущество посредством предварительной сортировки по глубине или приоритету. Цель такой сортировки состоит в том, чтобы получить окончательный список элементов сцены, упорядоченных по приоритету глубины, основанному на расстоянии от точки наблюдения. Если такой список окончателен, то никакие два элемента не будут взаимно перекрывать друг друга. Тогда можно записать все элементы в буфер кадра поочередно, начиная с элемента, наиболее удаленного от точки наблюдения. Более близкие к наблюдателю элементы будут затирать информацию о более далеких элементах в буфере кадра. Поэтому задача об удалении невидимых поверхностей решается тривиально. Эффекты прозрачности можно включить в состав алгоритма путем не полной, а частичной корректировки содержимого буфера кадра с учетом атрибутов прозрачных элементов. Для простых элементов сцены, например для многоугольников, этот метод иногда называют алгоритмом художника, поскольку он аналогичен тому способу, которым художник создает картину. Сначала художник рисует фон, затем предметы, лежащие на среднем расстоянии, и, наконец, передний план. Тем самым художник решает задачу об удалении невидимых поверхностей, или задачу видимости, путем построения картины в порядке обратного приоритета.

Основные идеи, на которые опирается алгоритм Варнока, обладают большой общностью. Они основываются на гипотезе о способе обработки информации, содержащейся в сцене, глазом и мозгом человека. Эта гипотеза заключается в том, что тратится очень мало времени и усилий на обработку тех областей, которые содержат мало информации. Большая часть времени и труда затрачивается на области с высоким информационным содержимым. В каждом случае, по мере сужения сферы интереса, возрастает уровень требуемой детализации. Далее, если на определенном уровне детализации на конкретный вопрос нельзя ответить немедленно, то он откладывается на время для последующего рассмотрения. В алгоритме Варнока и его вариантах делается попытка извлечь преимущество из того факта, что большие области изображения однородны, например поверхность стола в приведенном выше примере. Такое свойство известно как когерентность, т. е. смежные области (пиксели) вдоль обеих осей х и у имеют тенденцию к однородности. Поскольку алгоритм Варнока нацелен на обработку картинки, он работает в пространстве изображения. В пространстве изображения рассматривается окно и решается вопрос о том, пусто ли оно, или его содержимое достаточно просто для визуализации. Если это не так, то окно разбивается на фрагменты до тех пор, пока содержимое подокна не станет достаточно простым для визуализации или его размер не достигнет требуемого предела разрешения. В последнем случае информация, содержащаяся в окне, усредняется, и результат изображается с одинаковой интенсивностью или цветом. Устранение лестничного эффекта можно реализовать, доведя процесс разбиения до размеров, меньших, чем разрешение экрана на один пиксель, и усредняя атрибуты подпикселей, чтобы определить атрибуты самих пикселей.

Метод трассировки лучей - это фотореалистический метод визуализации или рендеринга (rendering), в котором изображение генерируется путем моделирования отражения лучей света в 3D сцене. В реальном мире лучи света исходят из одного или многих источников света и отражаются от объектов пока, в конце концов, не достигнут глаз. При компьютерном моделировании часто более эффективным является распространение лучей от глаза наблюдателя, чем от источников света. Это позволяет сохранить значительное количество времени за счет исключения отслеживания путей лучей идущих до поверхностей, которые не видны наблюдателю. Такой подход используется и в методе трассировки лучей. Лучи света трассируются от глаз наблюдателя (позиции камеры) через каждый пиксель (pixel) видового экрана. Трассировка луча включает проверку всех объектов в сцене на пересечение с этим лучом (объекты моделируются как совокупности поверхностей (граней), которые могут быть ограничены треугольниками, прямоугольниками, или более сложными фигурами, типа 3-D сплайнов. Для таких начальных лучей должно быть определено ближайшее пересечение вдоль каждого луча. После определения видимости рассчитываются освещенность и закраска видимых объектов для каждого пикселя на пути следования лучей. При выполнении расчетов принимаются во внимание положение, цвет и яркость световых источников, включая рассеянное освещение. Цвет поверхности складывается из трех компонентов рассеянного (ambient), локального (local), и глобального (global) освещения. Учитываются также оптические свойства различных поверхностей: цвет (colour), степень отражения (reflectance), прозрачность (transmitance), рассеяние света (refraction), текстура (texture), так как это будет влиять на цвет и яркость луча. Метод трассировки лучей в особенности применим для решения задач, которые требуют реалистического представления отражающих и прозрачных материалов, таких как металл и стекло.

Порталы. Этот метод создан для так называемых indoor environments - т.е. для замкнутого пространства. Суть его в том, что вся сцена разбивается на комнаты. Комнаты связаны между собой полигонами, которые называются порталами. Для отрисовки сцены нам надо отрисовать сначала комнату, в которой находится камера, если камера "видит" какой-то портал, то аналогично рисуем комнату, которую видно через этот портал, отсекая ее по проекции полигона-портала.

BSP - деревья. Метод BSP - деревьев (Binary Space Partitioning Tree) - метод двоичного разбиения пространства. Для начала, нам надо построить двоичное дерево. В качестве главного узла в двоичном дереве берется произвольный полигон. Плоскость, в которой он лежит, делит пространство на два полупространства, в каждом полупространстве берутся следующие произвольные полигоны - это будут следующие узлы дерева; если часть вершин полигона после разбивки лежит в одном полупространстве, а часть - в другом, то он разбивается на 2 полигона. Дерево строится, пока остаются незадействованные в сортировке полигоны.

10. Элементы виртуальной реальности: физические и психологические факторы, учитываемые при создании реалистичных изображений, простая модель освещения, методы закрашивания Гуро, Фонга, расчет освещенности сцен, текстурирование поверхностей, общий метод и частные случаи, пирамидальное фильтрование, прикладное использование трехмерной машинной графики и реалистических изображений.

Построение реалистических изображений включает как физические, так и психологические процессы. Свет, т. е. электромагнитная энергия, после взаимодействия с окружающей средой попадает в глаз, где в результате физических и химических реакций вырабатываются электроимпульсы, воспринимаемые мозгом. Восприятие - это приобретаемое свойство.

Человеческий глаз - очень сложная система. Он имеет почти сферическую форму с диаметром около 20 мм. Воспринимаемый свет с помощью гибкого хрусталика фокусируется на сетчатке глаза, в которой есть два типа рецепторов: колбочки и палочки. В центре задней полусферы глаза собрано 6-7 млн. колбочек, чувствительных только к сравнительно высоким уровням освещенности, причем каждая из них присоединена к отдельному нерву. Колбочки позволяют различать мелкие детали. В сетчатке также находится 75-150 млн. палочек, чувствительных к очень низким уровням освещенности. К одному нерву присоединено сразу несколько палочек, поэтому они не способны различать мелкие детали. Интересно, что цвет воспринимается только колбочками, т. е. при низкой освещенности, когда колбочки теряют свою чувствительность, предметы кажутся черно-белыми.

Интенсивность зеркально отраженного света зависит от угла падения, длины волны падающего света и свойств вещества. Основное уравнение Френеля приводится в любой книге по геометрической оптике. Зеркальное отражение света является направленным. Угол отражения от идеальной отражающей поверхности (зеркала) равен углу падения, в любом другом положении наблюдатель не видит зеркально отраженный свет. Это означает, что вектор наблюдения S совпадает с вектором отражения R. Если поверхность не идеальна, то количество света, достигающее наблюдателя, зависит от пространственного распределения зеркально отраженного света. У гладких поверхностей распределение узкое или сфокусированное, у шероховатых - более широкое.

В простых моделях освещения обычно пользуются эмпирической моделью Буи-Туонга Фонга , так как физические свойства зеркального отражения очень сложны.

Методом Гуро можно получить сглаженное изображение. Для того чтобы изобразить объект методом построчного сканирования, нужно в соответствии с моделью освещения рассчитать интенсивность каждого пиксела вдоль сканирующей строки. Нормали к поверхности аппроксимируются в вершинах многоугольников. Однако сканирующая строка не обязательно проходит через вершины многоугольника. При закраске Гуро сначала определяется интенсивность вершин многоугольника, а затем с помощью билинейной интерполяции вычисляется интенсивность каждого пиксела на сканирующей строке.

Хотя метод Фонга устраняет большинство недостатков метода Гуро, он тоже основывается на линейной интерполяции. Поэтому в местах разрыва первой производной интенсивности заметен эффект полос Маха, хотя и не такой сильный, как при закраске Гуро. Однако, иногда этот эффект проявляется сильнее у метода Фонга, например для сфер. Кроме того, оба метода могут привести к ошибкам при изображении невыпуклых многоугольников. Первая сканирующая строка использует данные из вершин QRS, а вторая, лежащая ниже, берет также данные вершины Р. Это может нарушить непрерывность закраски.

Наложение текстур — наиболее трудоемкий и сложный этап ЗD-конвейера, ко¬торый сопровождается появлением многочисленных дефектов на изображении. Именно на этом этапе используется большая часть разнообразного арсенала аппа¬ратных средств ЗD-акселератора, предназначенного для коррекции изображения.

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

Увеличение размеров объекта при приближении к нему сопровождается мас¬штабированием растровой картинки текстуры. В результате проявляется хорошо известный всем эффект — пикселизация (лестничный эффект). Пути решения проблемы оптимального использования текстур очевидны: при изменении расстояния до объекта необходимо оперативно из¬менять разрешение накладываемых текстур. Для этого в ЗD-акселераторе исполь¬зуется технология, называемая мип-мэппингом (MIP-mapping) или М/Р-текстурированием. Суть ее состоит в том, что в локальной памяти акселератора хранятся несколько вариантов одной и той же текстуры, но с разным разрешением, или уров¬нем детализации (LOD — Level OfDetalization). Размер каждой текстуры следующего уровня в 4 раза больше размера предыдущей. Совокуп¬ность всех вариантов одной и той же текстуры называют MIP-каскадом.

В последнее время трехмерная машинная графика широко используется в различных областях мировой компьютерной индустрии. Так например, компьютерные игры используют самые последние достижения из области 3D-технологий. Кроме того, широкое применение 3D-графика нашла в области создания различных компьютерных тренажеров-симуляторов (автосимуляторы, авиасимуляторы и пр.) Очень распространено использование реалистичных сцен в киноиндустрии: при создании спецэффектов широко используются возможности компьютерной графики.