402

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

Шпаргалка

Информатика, кибернетика и программирование

Технические средства ввода графической информации. Особенности представления цвета в видеоадаптерах EGA и VGA. Элементарные аффинные преобразования в пространстве, составляющие базис операций машинной графики. Понятие текстуры и способы моделирования текстур.

Русский

2012-11-14

951 KB

45 чел.

PAGE  66

Вопросы для экзамена по курсу "Компьютерная графика"

1. Технические средства ввода графической информации.

1. Мышь

 Наиболее распространенным устройством ввода графической информации в ПЭВМ является мышь. Она подключается к компьютеру через интерфейс RS-232. При перемещении мыши и/или нажатии/отпускании кнопок мышь передает в компьютер информацию о своих параметрах (величине перемещения и статусе кнопок). Существует много различных типов устройства мыши, отличающихся как по принципу работы (механический, оптомеханический, оптический), так и по протоколу общения с ЭВМ. "Взаимопонимание" между мышью и ЭВМ при этом достигается с помощью драйвера, поставляемого вместе с мышью. Драйвер отслеживает перемещение мыши и нажатие/отпускание кнопок и обеспечивает работу с курсором мыши на экране дисплея.

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

Работа с мышью организуется через механизм прерываний. Прикладная программа вызывает прерывание 33h, передавая в регистрах необходимые параметры и получая через регистры возвращаемые драйвере) значения. Существуют различные стандарты работы с мышью. Наиболее распространены стандарты IBM Microsoft. Из драйверов наиболее известны mouse.coin и gmouse.com Они поддерживают множество функции мыши, связанных с внешним видом, положением и перемещением курсора, а также с определением состояния кнопок мыши. Для программирования той или иной функции мыши требуется только знать ее номер и параметры, заносимые в регистры перед вызовом прерывания. Обычно номера функций драйвера заменяются их мнемоническими именами в заголовочном файле (например, mouse.h), сами тексты функций собираются в отдельный файле (например, mouse.cpp). Такая пара (mouse.h и mouse.cpp) ориентируется на конкретный драйвер. В [1,4] приводятся варианты программного обеспечения - для драйверов mouse.com и gmouse.com.

Любая библиотека обычно содержит следующие функции:

  •  проверка наличия мыши;
  •  показ/сокрытие курсора мыши (при сокрытии драйвер мыши продолжает отслеживать ее перемещение);
  •  чтение состояния мыши (ее координат и состояния кнопок - нажато/отжато);
  •  передвижение курсора мыши в заданную точку;
  •  установка области перемещения курсора мыши.

По умолчанию форма курсора мыши определяется оборудованием и драйвером. Ее можно изменить. В текстовом режиме курсор мыши отображается на экране совместно с текстовым курсором и представляет собой прямоугольник размером в один символ. Вид изображения при перекрытии курсором мыши чего-либо определяется параметром и передаваемыми функции изображения курсора текстового режима. Эти параметры (маска экрана и маска курсора) состоят из 16 бит и задают мерцание, цвет и фон, также изображаемый при наложении курсора символ. Маска экрана участвует в логической операции AND с атрибутами перекрытого участка экрана, далее выполняется операция XOR с маской курсора. Например, для инвертирования изображения маска экрана - 0xFFFF, маска курсора - 0х770.

 В графическом режиме также имеется курсор по умолчанию (от драйвера). Обычно это небольшая стрелка. Вид курсора также можно изменить. Над маской экрана и маской курсора выполняются аналогично текстовому режиму операции AND и XOR. Но под каждую маску отводится не 16 бит, а по 16 16-битовых величин (int mask[l][15]). Для создания собственного курсора полезна таблица взаимодействия масок:

Маска экрана

Маска курсора

Рез-т на экране

0

0

0

0

1

1

1

0

Не измен.

1

1

Инверсия

 Следует обратить внимание на рациональную реализацию обработки событий от мыши. Не требуете; все время опрашивать драйвер мыши. Ему передается адрес функции, которую следует вызвать при наступлении заданного события. Первый параметр - указатель на функцию, второй параметр - маска событий. События соединяются побитовой операцией ИЛИ. Функция, которая обрабатывает событие, получает маску вызывающего события, маску состояния кнопок мыши. координаты курсора мыши.

2. Сканеры

 Сканеры являются устройствами ввода изображений. Чаще всего их действие основано на оптических принципах. Они осуществляют начальную оцифровку изображений (далее при необходимости производится чистка изображений специальными методами - см. тему "Математические основы компьютерной графики") и передачу их в ЭВМ. В настоящее время фактическим стандартом представления изображений сканерами является формат TWAIN. Этот формат поддерживает большинство драйверов различных сканеров. Конвертация из этого формата в формат какой-либо графической системы выполняется программно.

3. Световое перо

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

4. Диджитайзер (дигитайзер, digitazer, оцифровыватель)

 Устройство ввода точных двумерных координат объекта. Подключается к асинхронному порту СОМ1. Пример дигитайзера - изделие TRUE GRID фирмы Houston Instruments представляет собой панель размером от 130*130 мм до 280*430 мм и снабжаются курсором в виде пера и напоминающей мышь коробочки с лупой, перекрестьем и одной или несколькими клавишами. Выпускает дигитайзеры также фирма Hewlett Packard и ряд др. фирм. Возможны бинарная передача данных, ASCII-строка, целочисленный ASCII-формат.

 Съем координат может производиться в следующих режимах:

• точки (point) -передача абсолютных координат точки, в которой находится курсор, по нажатию клавиши;

• триггер (triggered) - абсолютные координаты точки по запросу компьютера;

• обычный поток (stream) - непрерывная передача абсолютных координат:

• переключаемый поток (switch stream) - аналогично обычному потоку, но включается по нажатии клавиши;

• непрерывная передача относительных координат.


2. Технические средства получения твердой копии графической информации.

1. Графопостроители (плоттеры)

 Это электромеханические устройства, основанные на преобразовании хранящихся в памяти ЭВМ координат изображения в сигналы перемещения механических пишущих узлов. Различные типы графопостроителей имеют различные системы команд, позволяющие управлять механическими узлами, обеспечивающие нанесение изображения как в одном, так и в нескольких цветах, с различными атрибутами (пунктир, штрих-пунктир и т.п.). Обычно "плоттер подключается к компьютеру через асинхронный порт СОМ1. Для выполнения рисунка плоттеру передаются команды (рисование линии, рисование окружности и т.д.), цвет и координаты точек, о6разующих линию. Эти команды образуют графические языки плоттеров.

2. Принтеры  

 Практически любой современный принтер позволяет получать изображение, т.к. выводит информацию по точкам. Каждый символ представляется матрицей точек. Для большинства матричных принтеров размер матрицы 8*12. Управляет принтером специальный набор команд, обычно называемый Esc-последовательностями. Эти команды позволяют задать режим работы принтера, прогон бумаги на заданное расстояние, собственно печать. Чтобы отличить управляющие коды от выводимой информации, они обычно начинаются с кода меньшего, чем 32 (не ASCII-символ). Для большинства команд начальным является символ Esc (код 27) совокупность подобных команд образует язык управления принтером. Каждый принтер имеет свой набор команд. Однако можно выделить набор команд, реализованный на достаточно широком классе принтеров.

 Наиболее просты 9-игольчатые принтеры типа Epson, Star и совместимые с ними. Они имеют команды перевода строки (LF) возврата каретки к началу строки (CR), прогона бумаги до начала новой страницы (FF) установки интервала между строками, печати с нормальной или повышенной плотностью (80 или 120 точек дюйм). 24-игольчатые принтеры (LQ-принтеры) имеют язык управления, являющийся надмножеством языка управления 9-игольчатыми принтерами. Этим достигается программная совместимость. Большинство струйных принтеров на уровне языка управления совместимо с LQ-принтерами. Одним из наиболее распространенных классов лазерных принтеров являются принтеры серии HP LaserJet фирмы Hewlett Packard. Все они управляются языком PCL, также основанным на Еsc-последовательностях.

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

• подтверждение получения данных;

• ожидания (задержки передачи данных до тех пор, пока принтер не сможет начать обработку данных снова;

• отсутствия бумаги.

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

 Некоторые принтеры имеют две модификации - для параллельного и последовательного интерфейса. Лазерные принтеры фирмы Hewlett Packard работают только с последовательным интерфейсом со скоростью передачи данных 9600 бод (бит/сек).


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

 Это основное устройство вывода информации. Большинство дисплеев в качестве формирователя изображения использует электронно-лучевую трубку (ЭЛТ). Paбота ЭЛТ основана на двух физических принципах: влияние электромагнитного поля на поток электронов, движущихся в разреженном пространстве и  свечение люминофоров при их бомбардировке электронами.

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

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

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

Z - конечная точка растра. Движение луча отточки А до точки Z называется прямым ходом луча по кадру. Из точки Z луч быстро перемещается в точку А, сканирование завершается. Время одного полного движения по растру - период кадра.

Реальные дисплеи имеют от 300 до 2000 строк. Изображения, формируемые растровыми дисплеями состоит  из множества точек   пикселов. Термин "пиксел" происходит от английских слов PICTURE ELEMENT. Множество всех пикселов на экране образует матрицу. Размерность матрицы различна для различных устройств, она определяет разрешающую способность дисплея. Управление работой дисплея осуществляет дисплейный контроллер (видеоконтроллер, видеоадаптер, дисплейный адаптер, видеокарта). Он представляет собой плату, вставляемую в соответствующий слот, и поэтому может заменяться. Видеоадаптер выполняет 3 главные функции хранение информации об изображении; регенерацию изображения на экране ЭЛТ; связь с центральным процессором ЭВМ. ЭВМ имеет многочисленные видеорежимы или способы изображения данных на экране дисплея. Каждый видеоадаптер имеет свой набор видеорежимов. Изображение хранится в растровом виде в памяти видеокарты. Аппаратно обеспечивается регулярное (50-70 раз в сек.) чтение этой памяти и отображение ее на экране. Поэтому работа с изображениями сводится к операциям с видеопамятью. Существует 6 общепринятых стандартов видеоконтроллеров. Имеется также множество нестандартных для решения специальных задач. К стандартным видеоконтроллерам относятся:

 Монохромный дисплейный адаптер (Monochrome Display Adapter - MDA) - текстовый, высокое качество изображения, низкая цена;

Цветной графический адаптер (Color Graphics Adapter - CGA). Разрешающая способность в цветном графическом режиме 320*200, в режиме монохромной графики - 640*200. Палитра из 16 цветов, в графическом режиме можно задать любые 4 цвета. Устарел, практически не используется;

Монохромный графический адаптер (Monochrome Graphics Adapter - MGA или, по имени кампании-разработчика Hercules Computer Technology, Hercules Graphics Adapter - HGA). Имеет ту же разрешающую способность, что и MDA, но может работать в графическом режиме. Разрешающая способность 720*348. Изображение качественное, используется широко.

Улучшенный графический адаптер (Enhanced Graphics Adapter - EGA). Разрешение 640*350, 16 цветов. Благодаря новой организации управления памятью и формированием изображения можно смешивать цвета в различных комбинациях из палитры в 64 оттенка для каждого из 16 цветов (оттенки тона. насыщенность). Как правило, обеспечивается совместимость с CGA, в ряде моделей - с MGA (Hercules). Сейчас есть усовершенствованные модели, позволяющие при наличии специального программного обеспечения получать 43 строки на экране и разрешение 640*480;

Видеографическая матрица (Video Graphics Array - VGA). Была создана для PS/2. Развитие EGA. 640*480 точек, воспроизведение 16 цветов из палитры 4096 оттенков. 320*200 при воспроизведении одновременно 256 цветов;

Супер видеографическая матрица (Super Video Graphics Array - SVGA). Стандарта SVGA нет, он рассматривается как расширение VGA. Более высокая частота горизонтальной развертки - ряд частот: 56, 60, 72. Разрешение: 800*600, 1024*768. 1280*1024.


4. Векторная и растровая графика: суть, отличия, области применения.

 

Принципы, положенные в основу работы дисплеев, широко используются в машинной графике как способ формирования изображений. Поэтому часто встречаются термины "ВЕКТОРНАЯ ГРАФИКА" и "РАСТРОВАЯ ГРАФИКА". В первом случае выполняется кусочно-линейная аппроксимация изображений и возникает задача поиска компромисса между временем и точностью построения изображения путем подбора параметров аппроксимации. Во втором случае этот же компромисс выглядит как задача определения параметров растра.


5. Мировые координаты, нормированные координаты, координаты устройства, функция кадрирования.

Для программиста естественно желание определить графические элементы в системе координат решаемой задачи. Устройства вывода, на которых визуализируются графические элементы, требуют, как правило, использования собственных аппаратных координатных систем. Чтобы разрешить это противоречие и добиться независимости от устройств, международным стандартом GKS (Graphical Kernel System - ядро графической системы) определены 3 системы координат.

Задавая элементы своего изображения, прикладной программист использует систему мировых координат (WC - World Coordinate). Эти координаты определяют положение объекта в некотором модельном мире. МИРОВЫЕ КООРДИНАТЫ - независимые от устройства декартовы координаты, которые используются в прикладной программе для задания графических данных ввода-вывода. Вообще говоря, каждый примитив может быть определен в собственной системе мировых координат.

НОРМИРОВАННЫЕ КООРДИНАТЫ задаются в промежуточной, независимой от устройства системе координат и нормированы относительно некоторого диапазона (часто от 0 до 1). Относительное расположение примитивов ввода-вывода определяется отображением мировых координат в нормированные координаты. Нормированные координаты используются при хранении графических образов (в памяти, в файлах и пр.).

Пространство нормированных координат пересчитывается в координаты устройства (Device Coordinate).

КООРДИНАТЫ УСТРОЙСТВА зависят от вида устройства и измеряются в некоторой системе мер (метрической, в дюймах) или в аппаратных единицах.

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

Пример - система автоматизированного проектирования печатных плат PCAD: различные типы дисплеев подключаются с помощью драйверов (конкретный драйвер указывается в файле pcaddrv.sys). Роль нормированной системы координат играет файл *.PLT, который не зависит от типа устройства. Вывод на конкретное устройство выполняют утилиты PCPRINT для принтера, PCPLOTS для плоттера.

Каждая из этих утилит позволяет настроиться на большой перечень устройств соответствующего класса. При этом выполняется преобразование нормированных координат файла *.PLT в координаты устройства По тому же принципу работает Windows95 при формировании заданий на печать. Если памяти достаточно, сначала формируется файл печати в формате расширенного метафайла (EMF). Метафайл формируется быстрее, т.к. не зависит от типа устройства. Далее в фоновом режиме формируется задание на печать с учетом конкретного устройства.

Отображение области действия мировых координат в область действия координат устройства называется ФУНКЦИЕЙ КАДРИРОВАНИЯ.

Изображение, получаемое средствами машинной графики, имеет четко определенную структуру. Атомарным (неделимым) объектом является КООРДИНАТНАЯ ТОЧКА или ПИКСЕЛ. Термин ПИКСЕЛ, введенный для дисплеев, нашел применение в более широком смысле. Это точка, являющаяся атомарным компонентом изображения вне зависимости от того, где и как хранится/отображается рисунок.


6. Понятие графического примитива. Наиболее распространенные графические примитивы и операции над ними.

ГРАФИЧЕСКИЙ ПРИМИТИВ представляет собой либо координатную точку, либо упорядоченную последовательность (не совокупность, а именно последовательность!) координатных точек. Различают графические объекты (и соответственно графические примитивы): нульмерные (точки), одномерные (линии), двумерные (поверхности), трехмерные (тела).

В компьютерной графике все, что относится к двумерным изображениям, обозначают 2D (2-dimension), к трехмерным - 3D (3-dimension).


7. Основные отличия текстового и графического режима видеоадаптера.

Любой современный видеоадаптер может работать в двух режимах: текстовом и графическом. В текстовом режиме экран делится на ячейки, соответствующие размеру символа. Обычно это 40 или 80 колонок, 25 или 50 строк. Каждая ячейка содержит атрибут и символ. Символ выводится на экран в ASCII коде, атрибут указывает, как представляется символ на экране (цвет, интенсивность, мерцание, подчеркивание, инверсное изображение в зависимости от типа видеоадаптера). Язык программирования С и другие языки такого же класса имеют средства управления выводом текста, в том числе управления атрибутами символов.

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

В текстовом режиме верхний левый угол экрана имеет позицию (1,1), координата Х растет вправо, координата Y растет вниз. В графическом режиме верхний левый угол имеет координаты (0,0), координаты Х и Y направлены аналогично.


8. Чем отличаются с точки зрения машинной графики видеоадаптеры EGA,VGA,SVGA,MGA.

Режим обозначается номером и определяется разрешением экрана и количеством цветов.

Номер режима

Разрешение

Кол-во цветов

Номер режима

Разрешение

Кол-во цветов

0Dh

320х200

16

11h (VGA)

640х480

2

0Eh

640х200

16

12h (VGA)

640х480

16

0Fh

640х350

2

13h (VGA)

320х200

256

10h

640х350

16

Каждая видеоплата содержит собственный BIOS для работы с ней и поддержки основных своих функций. Через BIOS можно определить тип адаптера - EGA или VGA, установить нужный режим, системный шрифт заданного размера (8,14 или 16 пикселов высоты), палитру. Для 16-цветных режимов под каждый пиксел отводится 4 бита (24=16). Однако эти биты располагаются не последовательно в одном байте, а разнесены по 4 блокам (битовым или цветовым плоскостям) видеопамяти. Вся видеопамять (обычно 256 К) делится на 4 равные части. Каждому пикселу соответствует по 1 биту каждой плоскости, причем эти биты расположены одинаково относительно начала плоскости (параллельно). Когда процессор выполняя операции чтения/записи видеобуфера по некоторому адресу, этот адрес относится не к одному, а к 4 байтам, каждый из которых размещается в своей битовой плоскости. При выполнении операции чтения из видеобуфера (например, командами MOV reg,mem; LODS; CMP reg.mem и др.) из него извлекается не 1, а 4 байта. Но данные пересылаются не в процессор, а в четыре 8-битовых регистра-защелки (latch - задвижка, щеколда). Каждый из этих регистров соответствует своей битовой плоскости. При выполнении операций записи в видеопамять производится параллельная модификация всех 4 битовых плоскостей. Таким образом за один раз обрабатывается информация о 8 пикселах. Если к видеобуферу обратиться при помощи команд, оперирующих словами, а не байтами, результаты могут быть ошибочными, т.к. алгоритм выполнения операций процессора и видеокарты разный, и результат одной части операции перезаписывается другой ее частью.

Регистры видеокарты делятся на группы. Каждой группе соответствует пара последовательных портов (порт адреса и порт значения). Для записи в регистр значения надо записать сначала номер регистра в порт адреса, затем значение в следующий порт. Добраться до регистров видеокарты можно с помощью ассемблера или функций языка С inportb,  outportb (запись в аппаратный порт). Прототипы функций - в <dos.h>.

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

Графический контроллер имеет 9 регистров, адресуемых через порт 3CEh. Значения регистров задаются через порт 3CF. Содержимое регистров графического контроллера управляет обработкой данных регистров-защелок при чтении/записи. Часть операций в качестве операндов используют байт, т.е. воздействуют отдельно на каждый регистр. Операндом других операций является пиксел, т.е. содержимое регистров-защелок рассматривается как набор из 8 пикселов. Такие операции воздействуют на каждый пиксел в отдельности.

Т.к. разрядность процессора не более 32, требуется специальное формирование значения для пересылка в процессор. Оно осуществляется с помощью масок и зависит от режима чтения/записи. Режим задается в специальном регистре графического контроллера. Этот регистр имеет номер 5. Имеется 2 режима чтения и 3 режима записи для EGA. Для VGA имеется еще один режим записи. Бит 3 регистра определяет режим чтения (0 или 1), биты 1 и 0 - режим записи Остальные биты этого регистра обычно нулевые.

В режиме чтения 0 в процессор передается значение одного из 4 регистров-защелок. Указателем номера регистра-защелки служит специальный регистр считываемого банка (еще одно название битовой плоскости) Этот регистр имеет номер 4. Такое последовательное чтение битовых плоскостей применяется, например, npi записи изображения на диск.

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

Режим записи 0 является наиболее сложным, но дает большие возможности. Операция записи процессора инициирует комбинацию байтных и пиксельных операций. Байт данных от процессора можно использовать для модификации содержимого любых или всех битовых плоскостей и одновременно некоторое заданное значение пиксела можно использовать для модификации всех или любых пикселов. Значение пиксела - еп цвет. В операции задействованы 4 служебных регистра графического адаптера, вместе с байтом данных от процессора воздействующих на регистры-защелки. Например, регистр битовой маски (номер 8) позволяет выделить нужный пиксел, чтобы сопоставить ему определенный цвет. Регистр маски плоскости (относится к группе регистров, адресуемых через порт ЗС4. порт данных - ЗС5) защищает от изменения определенные плоскости. Для формирования значений используются также сдвиговые операции.

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

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

Режим записи 3 поддерживается только адаптером VGA. В [3,4] излагается способ формирования данных для записи в битовые плоскости.

Работа VGA в 256-цветном режиме с разрешением 320*200 имеет особенности. Для одновременного отображения такого количества цветов под каждый пиксел отводится 8 бит. Эти биты идут последовательно образуя 1 байт. Плоскости не используются, видеопамять начинается с адреса 0хА000:0. Точке с координатам (х,у) соответствует байт памяти по адресу 320*у+х. Это стандартный режим с номером (mode) 13.

Существуют также нестандартные режимы адаптера VGA при работе с 256 цветами. Они программируются на ассемблере и позволяют установить повышенное разрешение (320*240 или 360*480). Здесь используются битовые плоскости, в которых в определенном порядке хранятся пикселы. В одной битовой плоскости хранятся пикселы 0,4,8 и т.д., в другой - 1,5,9 и т.д. Здесь также задействованы все служебные регистры, н меняется интерпретация находящихся в видеопамяти значений.

Видеокарты SVGA совместимы с VGA, но имеют большой набор дополнительных режимов. VGA является стандартом, SVGA - его расширение.

В 256-цветном режиме в адаптерах SVGA под каждый пиксел отводится 1 байт, вся видеопамять разбивается на банки одинакового размера (обычно по 64 К). Область адресного пространства

0хА000:0 -0xA000:0xFFF соответствует выбранному банку. Ряд карт позволяет работать сразу с двумя банками.

Практически все различия между картами заключаются в установке режима с заданным разрешением и установке банка с заданным номером. Можно построить библиотеку, распознающую наличие основных SVGA карт (Triedent, Cirrus Logic и др.) и обеспечивающую работу с ними. Связь - через порты 0хЗС4 и 0хЗСЕ, работать можно на Си с привлечением ассемблера.

Ассоциацией стандартов в области видеоэлектроники VESA (Video Electronic Standards Association сделана попытка стандартизации работы с различными SVGA-платами путем добавления в BIOS платы (у видеоадаптеров - свой BIOS) некоторого стандартного набора функций, обеспечивающего получение необходимой информации о карте, установку заданного режима и банка памяти. При этом вводится стандартный набор расширенных режимов. Номер режима - 16-битовое число, биты с 9 по 15 зарезервированы и должны быт; равны 0, бит 8 для VESA-режимов = 1, для «родных» режимов карты = 0.

Таблица основных VESA-режимов:

Номер

Разрешение

Бит на пиксел

Кол-во цветов

Номер

Разрешение

Бит на пиксел

Кол-во цветов

100h

640х400

8

256

111h

640х480

16

64К

101h

640х480

8

256

112h

640х480

24

16М

102h

800х600

4

16

113h

800х600

15

32К

103h

800х600

8

256

114h

800х600

16

64К

104h

1024х768

4

16

115h

800х600

24

16М

105h

1024х768

8

256

116h

1024х768

15

32К

106h

1280х1024

4

16

117h

1024х768

16

64К

107h

1280х1024

8

256

118h

1024х768

24

16М

10Dh

320х200

15

32К

119h

1280х1024

15

32К

10Eh

320х200

16

64К

11Ah

1280х1024

16

64К

10Fh

320х200

24

16М

11Bh

1280х1024

24

16М

110h

640х480

15

32К

Ряд SVGA-карт поддерживает т.н. непалитровые режимы. Здесь для каждого пиксела вместо индекса в палитре непосредственно задается его RGB-значение. Обычно такими режимами являются HiColor (15 или К бит на пиксел) и TrueColor (24 бита на пиксел). Видеопамять, этих режимов устроена аналогично 256-цветны» SVGA: под каждый пиксел отводится 2 байта для HiColor и 3 байта для TrueColor, байты расположены подряд и сгруппированы в банки. Наиболее проста организация TrueColor (16 млн. цветов) -1 байт под каждую из компонент цвета. Для HiColor под каждый пиксел отводится 2 байта. Здесь возможны варианты:

•  каждая компонента занимает по 5 бит, последний бит не используется. Это дает всего 32 тысячи цветов;

•  красная и синяя компоненты занимают по 5 бит, зеленая - 6 бит. Это дает всего 64 тысячи цветов.


9. Особенности представления цвета в видеоадаптерах EGA и VGA.

Известно, что любой цвет является композицией трех основных цветов: Red (красный). Green (зеленый), Blue (синий). Дополнительные цвета - смесь основных:

При различной аппаратной настройке монитора magenta, например, может быть пурпурным, сиреневым, малиновым, вишневым; голубой - бирюзовым.

В зависимости от интенсивности (яркости) каждого из основных цветов в смеси получаем различные оттенки Следовательно, 4-битовая комбинация позволяет закодировать 15 базовых цветов. Кодирование стандартно: 1 - интенсивность, RGB - цвета.

Т.к. емкость видеопамяти ограничена, в ряде случаев возникает конфликт между цветностью и разрешающей способностью. Этим объясняется возможность цветных видеоадаптеров работать в разных режимах (модах), позволяющих увеличивать разрешающую способность (количество точек) за счет уменьшения количества цветов и наоборот. (См. параметр graphmode функции initgraph()) Например, в простейшем случае для адаптера CGA возможны 2 варианта представления изображений: 2 бита на каждый пиксел (4 цвета, 320*200 точек) и 1 бит на каждый пиксел (2 цвета, 640*200 точек).

Для VGA можно получить 640*200 точек при воспроизведении 16 цветов из палитры 4096 оттенков  или 320*200 точек при воспроизведении одновременно 256 цветов. Т.к. видеопамять VGA 256 К, можно также уменьшить число страниц видеобуфера (вместо 2 получить 1, 16 цветов, 640х480 точек).

Практически любой видеоадаптер способен отобразить гораздо больше цветов, чем определяется коли чеством бит, отведенным под один пиксел. Например, монитор EGA адаптера способен отображать 64 цвета т.к. имеет 6-битовый видеосигнал. Видеоадаптер переводит 4-битовый цвет пиксела в 6-битовый видеосигнал Для перевода используется некоторое подобие таблицы, называемое палитрой. Фактически адаптер имеет К специальных внутренних регистров, где для каждого логического цвета хранится его 6-битовое значение видеосигнала (6 бит, т.к. 3 основных цвета + бит интенсивности, следовательно, на каждый цвет - 2 бита). Цвет в палитре задается байтом вида 00rgbRGB. Малые буквы обозначают бит интенсивности соответствующего цвета,

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

(4-битовый атрибут) & (Регистр используемой цветовой матрицы) = Регистр палитры 0-0F h = 6-битовый сигнал, подаваемый на дисплей.

Реализация 16-цветной палитры для VGA гораздо сложнее. Для каждого цвета имеется 18-битовая раскладка по компонентам (6 бит на каждый из 3 основных цветов - в EGA было по 2 бита на цвет). Дополнительные биты дают более тонкую раскладку по интенсивности, т.е. обеспечивают более разнообразное смешивание 3 основных цветов. Схема получения 18-битового сигнала на начальном этапе повторяет EGA, далее задействован еще ряд регистров, операции логического И. .

Помимо поддержки EGA видеоадаптер VGA имеет 256 специальных регистров, где для каждого цвета хранится его 18-битное представление. Обычно BIOS записывает в эти регистры набор цветов, принимаемый по умолчанию. Этот режим используется для получения 256 цветов при разрешении 320*200. Распределение цветов по регистрам видеоадаптера VGA:

Интенсивность

Интенсивность

0h – 0Fh

CGA-совместимые, цвета (по умолчанию)

10h-lFh

Шкала серого

20h - 67h

Синий, красный, зеленый

Высокая

Высокая

Средняя

Низкая

68hAfh

Высокая

Средняя

Средняя

Низкая

B0h - F7h

Высокая

Низкая

Средняя

Низкая

F8h - FFh

Черный

Регистры 0h - 0Fh (h - hex, 16-ричный) обеспечивают CGA-совместимый набор цветов, принимаемый по умолчанию. Регистры 10h - 1Fh содержат упорядоченный по возрастанию набор оттенков серого. Следующие 216 регистров (20h - F7h) содержат 3 группы по 72 цвета, где первая группа (20h - 67h) -цвета повышенной яркости, вторая группа (68h - AFh) - средней, третья (BOh - F71i) - пониженной. Каждая такая группа состоит из трех диапазонов цветов, упорядоченных по снижению яркости. Снижение яркости можно трактовать как увеличение количества белого цвета, подмешанного к основному. Цвета в каждом диапазоне располагаются в порядке перехода от синего через красный к зеленому.

При 16-цветной работе VGA исходному логическому номеру цвета для 6-битовой палитры EGA сопоставляется, как и ранее, значение от 0 до 63. Но это уже не RGB-разложение цвета, а номер одного из 256 регистров, содержащих физический цвет. Для установки значений регистров служит функция void far setrgbpalette(int color, int red, int green, int blue);

 color - логический номер цвета (от 0 до 15 или от 0 до 255 в зависимости от graphmode), остальное - его RGB-интенсивности (используются только младшие байты, только 6 битов каждого байта).

Функция setpalette() присваивает одному из 16 логических цветов значение физического цвета из диапазона 0 - 63. Функция setrgbpalette() делает то же самое, но диапазон цветов шире


10. Как программно осуществляется управление принтером.

 

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

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

Каждая команда является набором символов (имеет символическое имя) или цифр (кодов). Коды просто посылаются на принтер во входном потоке. Чтобы отличить команды от того, что следует напечатать, они предваряются неотображаемым символом, т.е. символом с кодом, меньшим 32. Такому коду не соответствует ни один символ кода ASCII. Обычно в качестве символа начала управляющей последовательности выступает Esc (код 27). Поэтому говорят об Esc-последовательностях управления принтером.

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

int biosprint(int cmd, int byte, int port);

где cmd: 0 - печать символа byte, 1 - инициализация порта принтера, 2 - чтение статуса принтера;

byte - от 0 до 255 (что выводим/посылаем на принтер).

port - определение принтерного порта: 0 - LPT1; 1-LPT2 и

intbyte='\xlB';

biosprint(0,byte,0);

24-игольчатые (или LQ) принтеры включают (расширяют) язык управления 9-игольчатых принтеров. Большинство струйных принтеров по языку управления совместимо с LQ-принтерами.

Среди лазерных принтеров наиболее распространены HP LaserJet фирмы Hewlett Packard. Они управляются языком PCL. Большинство лазерных принтеров других фирм тоже поддерживает этот язык. Для выделения управляющей информации также используются Esc-последовательности, но кодовая строка длиннее, т.к. эти принтеры предоставляют больше возможностей по управлению.


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

Операционная система Windows выводит графику посредством интерфейса графических устройств GDI - Graphic Device Interface. Текст тоже рассматривается как графика. GDI обеспечивает вывод на экран, принтер, плоттер и др. GDI избавляет приложения Windows от необходимости учитывать многие особенности устройств вывода. Например, как мы уже видели в DOS, адресация видеопамяти адаптеров CGA, EGA, VGA, SVGA выполняется по-разному. К тому же представление видеоданных сильно зависит от видеорежима (разное количество байт на пиксел в зависимости от mode). Однако приложения Windows не работают непосредственно с видеопамятью. Вызываются соответствующие функции GDI реализованного в виде DLL. Функции GDI также не работают с аппаратурой. Для выполнения нужной графической операции GDI вызывает драйвер устройства вывода, ориентированный на особенности аппаратуры.

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

Логические устройства дают программисту большую свободу выбора выразительных средств.  Например, логический видеомонитор имеет огромное разрешение, способность отображать практически любой цвет (Реально - до 16 млн. цветов). Если задан цвет для палитры в 16 млн. цветов, а устройство не имеет такой возможности, GDI выбирает наиболее близкий к требуемому цвет. Для монохрома - градации серого.

Ситуация, когда приложение запрашивает у Windows одно, а получает другое, возникает и при работе со шрифтами. Это повышает независимость от аппаратуры по сравнению с MS DOS. В MS DOS при работе с видеоадаптерами указываются конкретные цвета, из файлов загружаются конкретные шрифты Для новых устройств в программу вносятся изменения (хотя бы в связи с новыми именами файлов). Следовательно, программы MS DOS более аппаратно зависимы. Приложения Windows не меняются при смене аппаратуры, требуется только соответствующий драйвер. Чем лучше аппаратура, тем ближе цвет и шрифт будут к запрошенным. Таким образом, в MS DOS можно запросить только то, что имеется, в WINDOWS предложен другой подход к разработке приложений:  запрашивай максимум того, что надо.

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

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

  •  Ми (М0)  - исходное (непрерывное) изображение;
  •  Мр (M1)  - растровая модель (изображение);
  •  Мв (M2)  - векторная модель (изображение);
  •  Мп (МЗ)  - прикладная модель (описание изображения в терминах хранения).

Технология преобразования графических представлений - отображение Q: Ми—Мп. Технологический процесс - отображение Pi, осуществляющее получение i модели по (i-1)-ой:

Pi: M(i-l) — Mi 

Технологическая операция (этап) - отображение T(iJ). внутри осуществляющее преобразование одной модели: TiJ: M(ij-l) —^ MiJ

Укрупненно технология преобразования изображения из начальной модели в конечную:

Исходная модель (Ми)

Процесс сканирования

Задание дискретности, координат и др.

Распознавание цвета …

Запись растра на МД (Мр)

Растровая модель (Мр)

Процесс

растр-векторного 

преобразования.

Считывание с МД

Фильтрация шумов

Выделение средних линий объектов (выделение скелетов)

Выделение контуров объектов

Вычисление характеристик объектов

Выделение непроизводных элементов

Формирование векторной модели (Мв)

Векторная модель (Мв)

Процесс распознавания и

формирования хранимого вида

Разделение объектов

Распознавание логических объектов

(возможно с точностью до графического примитива)

Формирование структуры хранения

Прикладная модель (Мп)


13. Основные этапы растр-векторного преобразования графических объектов.

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

Бинарные изображения более просты. По сравнению с полутоновыми изображениями они имеют ограниченный класс шумов. Основной метод подавления шумов - логическая фильтрация. Наиболее часто встречающийся вид искажений графических изображений - неоднородность формы линий. Это может выражаться в

• изменении толщины (наличии слишком широких или узких участков линий);

• наличии изолированных черных пятен небольших размеров или изолированных пустот внутри линий;

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

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

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

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

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

  •  выделения перепадов яркости;
  •  отслеживания (или обхода) контуров;
  •  сканирующие.

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

Методы отслеживания наиболее проработаны и просты в реализации. Обычно сначала выделяются границы, потом выполняется их аппроксимация. Это требует больших затрат памяти и времени. Более универсальный подход - совмещение отслеживания и аппроксимации. Разработаны специальные алгоритмы.

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

Ряд характеристик объекта удобнее вычислять при растровом представлении. Это площадь объекта, его длина, периметр, центр симметрии дискретного объекта, количество объектов изображения. Разработаны математические методы вычисления этих и других характеристик.

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

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

Третий этап преобразования (Мв—Мп) выполняется с помощью достаточно разработанной теории распознавания образов. Однако существует разрыв между теорией и практикой. Часто в конкретных системах используются технические решения, ориентированные на тот класс объектов, с которым данная система работает. Что касается структур хранения, то современные системы управления базами данных (СУБД) позволяю хранить так называемые BLOB (binare large objects). Конкретный вид бинарной информации при этом значения не имеет. Наиболее распространенные форматы представления изображений будут рассмотрены далее.

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

1. Анализ структуры объекта по принципу иерархии входящих в него элементов с выделением базовых, которые нецелесообразно расчленять далее по соображениям целостности элементов или по характеру задач;

2. Построение математических моделей базовых элементов { Мэi} и представление их в памяти ЭВМ;

3. Анализ структуры объекта с фиксацией всех связей между элементами;

4. Объединение математических моделей базовых элементов для построения математической модели объекта (изображения): Ми = { Мэi};

5. Дополнение математической модели системными (системообразующими) параметрами { SP }, характеризующими объект как систему взаимосвязанных элементов. Примеры параметров: размеры, определяющие взаимное положение элементов, сведения о предельных отклонениях, условиях сопряжения и т.д.;

6. Объединение в группы GP одинаковых параметров математических моделей элементов с целью минимизации общего объема сведений в математической модели объекта М.

Таким образом, математическую модель объекта в общем случае можно представить совокупностью математических моделей элементов, системных параметров и групп параметров: Mи={{Mэi},{SP},{GP}}.

К построенной по таким принципам математической модели предъявляются требования:

1. Простота и компактность представления объекта с целью минимизации памяти;

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

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

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


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

Преобразования на плоскости и в пространстве

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

Основу многих операций компьютерной графики составляют так называемые аффинные преобразования. Греческое слово АФФИНИС означает родственный. Аффинная геометрия - раздел геометрии, изучающий свойства фигур на плоскости и в пространстве, сохраняющиеся при любых аффинных преобразованиях, т.е. инвариантных относительно таких преобразований. Аффинные преобразования обеспечивают точечное взаимно однозначное отображение плоскости или пространства на себя, при котором 3 точкам, лежащим на одной прямой, соответствуют 3 точки, также лежащие на одной прямой. Аффинные преобразования переводят пересекающиеся прямыe в пересекающиеся прямые, параллельные прямые в параллельные прямые. Плоскость аффинно отображается на некоторую плоскость. Существует множество аффинных преобразований. К ним относятся преобразования подобия, сдвиги, сжатия и др. Следовательно, прорисовываются элементарные операции компьютерной графики, не нарушающие геометрических свойств отображаемого объекта.

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

Этот случай можно трактовать двояко:

А) сохраняется точка, изменяется система координат

Б)  изменяются координаты точки относительно неизменной системы координат, т.е. формулы задают отображение, точки М(x,y) в точку М’(x’,y’) в той же координатной системе.

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

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

В машинной графике часто используется матричное представление. Точку можно представить с помощью вектор-столбцов для плоскости |x y|, пространства -|x y z| . Тогда преобразования точек сводятся к операциям над матрицами, что хорошо соответствует возможностям вычислительной техники. В общем виде задача выглядит так. Даны матрицы А и В и задана их взаимосвязь AT = В. Необходимо найти матрицу преобразования. Решением является Т = А-1В, где А-1 - обратная от квадратной матрицы А. Матрица Т - фактически коэффициентов

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

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

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

Начнем рассмотрение элементарных операций с плоскостных. Можно выделить 4 таких операции:

поворот, растяжение (сжатие), отражение, перенос.

Матрица преобразования Т при этом имеет вид.

Для частного случая поворота на 90° (поворот против часовой стрелки относительно начала координат) вид матрицы  | 0 –1 |

   | 1  0  |

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

   

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


15. Элементарные аффинные преобразования на плоскости, составляющие базис операций машинной графики.

Выше было рассмотрено преобразование точек. Т.к. прямая задается координатами двух ее точек, для операций над прямой также можно использовать умножение матриц. Пусть имеется прямая с координатами концов, заданными векторами А[0,1] и В[2,3]. Возьмем произвольно матрицу преобразования T. Эта матрица осуществляет растяжение (или сдвиг). Выполним операцию умножения для точек А и В. A’=A*T=|3 1|; B’=B*T=|11 7|

Матрица размером 2*2 преобразует любую прямую в другую прямую. Точки результирующей линии взаимно однозначны точкам исходной линии (аффинные преобразования). Можно доказать, что данное утверждение распространяется не только на конечные, но и на серединные и все другие точки отрезка прямой. Для машинной графики существенно, что положение любой прямой линии преобразуется в новое положение преобразованием ее граничных точек и последующим проведением линии между полученными точками. Доказано, что использование матрицы 2*2 для преобразования параллельных линий не нарушает параллельности. Как следствие, в результате действия такой матрицы параллелограмм преобразуется в другой параллелограмм. При преобразовании пересекающихся прямых точка пересечения исходной пары линий преобразуется в точку пересечения результирующей пары.

Таким образом, матричное умножение можно использовать для графических построений. Например, можно равномерно или неравномерно менять масштаб фигуры. Если на вершины треугольника воздействует матрица |2 0 0 2| - , координаты увеличиваются в 2 раза. Eсли члены матрицы не равны, фигура искажается.

  

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

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


16. Понятие и прикладное значение однородных координат.

Применение матрицы общего вида 2*2 к началу координат дает результат:

Таким образом, начало координат инвариантно относительно общего преобразования 2х2. Это является ограничением, которое преодолевается с помощью однородных координат.

Пусть М - произвольная точка плоскости с координатами (х,у), вычисленными относительно заданной координатной системы. Однородными координатами этой точки называется любая тройка одновременно неравных нулю чисел x1, x2, х3, связанных с заданными числами соотношением: х1/х3=х; х2/х3=у

Фактически, однородные, координаты дают смещение плоскости, на которой рассматривается фигура, относительно начала координат или, в другой интерпретации, смещение начала координат. Это, по существу, переход к 3-мерному представлению плоских объектов, частный случай пространственного представления.

Рассмотрим более подробно. Введем в 2-мерное представление 3 компонент, равный единице. Тогда вектора будут иметь вид: [ х  у  l ]; [ х'  у'  l ]. Матрица преобразования примет вид: |10 01 mn| ,  так как для выполнения умножения матриц число столбцов, описывающих точку, должно равняться числу строк в матрице преобразования.    [ х  у  l ] * |10 01 mn | =[x+m y+n]=[x' у'].

Матрица 3*2 не квадратная, поэтому она не имеет обратной матрицы. (Вспомним: даны матрицы А и В, задана их взаимосвязь AT = В. Требуется найти матрицу преобразования. Решением является Т = А-1 В, где А-1- обратная от квадратной матрицы А. Матрица Т - фактически матрица коэффициентов можно трактовать и как оператор.) Чтобы получить квадратную обращаемую матрицу преобразования, дополним ее |100 010 mn1|

Третья (единичная) компонента векторов точек не меняется при добавлении элементов.

Полученные результаты можно трактовать как поднятие плоскости, в которой мы работаем, на 1 по оси z.

В более общем случае координаты точки можно представить как (hx, hy, h), h!=0. Следовательно, поднимаем плоскость на h. Практический смысл этого связан с изменением масштаба при вписывании изображения в координаты устройства (мировые координаты -нормированные координаты - координаты устройства). Как правило, координаты устройства являются целыми числами (пикселы), следовательно, точку с координатами (0.5, 0.1, 2.5) представить нельзя. При h=10. получаем (5,1, 25). Другой случай - координаты (80000 40000 1000), что создает угрозу арифметического переполнения. h=0,001 дает (80 40 1).

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

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


17. Элементарные аффинные преобразования в пространстве, составляющие базис операций машинной графики.

Для пространства однородные координаты выглядят как: (x,y,z,l) или, в более общем случае -(hx,hy,hz,1) Преобразование осуществляется аналогично плоскости по формуле AT = В, но матрица преобразования Т имеет размер 4х4 для однородных координат.

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

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

4.
18. Основные виды проекций и соответствующие им аффинные преобразования.

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

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

КЛАССИФИКАЦИЯ ПРОЕКЦИИ

* Параллельные проекции:

1  Ортографическая проекция

2.   Аксонометрическая Проекция

 2.1.  Триметрическая проекция    

 2.2.  Диметрическая проекция .

 2.3. Изометрическая Проекция

 3. Косоугольная проекция

 3.1 Свободная проекция,

 3.2. Кабинетная проекция

* Перспективные проекции:

1.Одноточечная проекция,

2.Двухточечная проекция,

3. Трехточечная проекция

  

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

на плоскость yz имеет вид:

Если плоскость проектирования параллельна координатной плоскости, матрица [Рx] умножается на матрицу сдвига

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

•  триметрию (плоскость находится относительно осей координат под различными углами для каждой оси) -. используется редко;

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

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

Каждая из этих проекций получается комбинацией поворотов, после чего следует параллельное (ортографическое) проектирование. Можно вывести соответствующие матрицы, некоторые подходы обозначены в [ 1 ].

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

•  свободную (угол наклона проектирующих прямых к плоскости отображения равен 45°);

•  кабинетную (частный случай свободной, масштаб по третьей оси в 2 раза меньше).

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

1

0

0

0

0

1

0  

0

a

b

0

0

0

0

0

1

Так, при проектировании на плоскость ху точки с

координатами х=0, у=0, z=l имеем (0 0 1 l) -> (a b 0 l).

Вид матрицы;

Перспективные (центральные) проекции более сложны. Они получаются путем перспективного преобразования и проектирования на некоторую плоскость наблюдения. Вводятся параметры, описывающие центр проектирования, т.е. точку, откуда "смотрят" на объект. Пусть эта точка имеет координаты (0 0 с). Тогда матрица перспективного преобразования в пространстве имеет вид:

1

0

0

0

0

1

0

0

0

0

1

-1/с

0

0

0

1

Выкладки получения: Член матрицы, характеризующий местоположение центра проектирования, выводится из уравнения прямой, проведенной из центра проектирования в некоторую точку объекта. Если мы хотим, например, плоскость наблюдения совместить с плоскостью ху, матрица примет вид, значение в третьем столбце третьей строки отражает факт z = 0 . В общем случае при нахождении центра проектирования на осях z или у или х матрицы преобразования будут иметь соответственно вид:

Это матрицы одноточечных преобразований.

1

0

0

-1/a

0

1

0  

-1/b

0

0

1

-1/c

0

0

0

1

Для произвольного центра проектирования с координатами (а, Ь, с) матрица преобразования:

 

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

Как все это реализовать (запрограммировать)? Здесь удобно использовать объектно-ориентированный подход. Фактически, мы работаем с векторами, т.к. координаты точки - 3 числа. Для класса ВЕКТОР (vector) можно определить систему операций (например, поэлементное сложение и вычитание векторов и т.д.). Определяются также основные функции. Аналогично вводится класс МАТРИЦА (matrix).


19. Геометрические сплайны.

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

Термин "сплайн" происходит от английского spline. Так называлась гибкая полоска стали, с помощь которой чертежники через заданные точки проводили плавные кривые. Используя теорию упругости, можно доказать, что результирующая кривая приближенно является кусочным кубическим многочленом. Он непрерывен и имеет непрерывные первую и вторую производные. Следовательно, кривая имеет постоянную кривизну и разрывы возникают лишь в третьей производной, что для человеческого глаза практически незаметно. Результирующая кривая или поверхность выглядит гладкой. Если вдоль сплайна совершается механическое движение непрерывность второй производной обеспечивает непрерывность ускорения и, следовательно, отсутствие резки изменений приложенной силы. Это очень важно при механической обработке. Поэтому сплайны используют например, при проектировании траектории движения режущего инструмента.

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

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

Пусть на плоскости заданы m точек с координатами (х,, у,), i = 0, 1 ,..., m, причем х0 <x1 <...<xm

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

1. Кривую можно провести непосредственно через исходные точки. Тогда получаем интерполяцию с помощью ломаной. Достоинство: простота, постепенность построения (поэтапность). Недостаток: отсутствие гладкости. даже первая производная имеет разрывы в узлах;

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

где (х, у,)     i = 1 .. m  -  заданные точки

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

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

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

Эта функция обладает свойствами:               

•  с довольно большой точностью часть графика этой функции, заключенного между любыми 2 соседними точками, можно считать многочленом третьей степени;

•  на всем промежутке от начальной до конечной точки эта функция дважды непрерывно дифференцируема

Полeченная функция называется интерполяционным кубическим сплайном.

Более точная формулировка:

ИНТЕРПОЛЯЦИОНЫЙ КУБИЧЕСКИЙ СПЛАЙН - функция S(x), обладающая свойствами:

  1.  График функции S(x) проходит через каждую точку заданного массива, т.е. S(xi)=yi, i=0..m;

На каждом из отрезков [xi, xi+1]i=0,1,..m-1 функция является многочленом третьей степени

3.    На всем отрезке задания (x0, xm) функция S(x) имеет непрерывную вторую производную.

Т.к. на каждом из отрезков [хi хi+1,] сплайн S(x) определяется 4 коэффициентами, для его полного построения необходимо найти 4*m чисел. Эти коэффициенты ищутся, исходя из условия 3, т.е. непрерывности сплайна во всех внутренних узлах, а также непрерывности первой и второй производной. Условия непрерывности накладывают ограничения на коэффициенты. Следовательно, для их определения получаем для всех внутренних узлов 4*m - 2 равенств. Недостающие граничные условия можно получить, задав, например, значения первых производных на концах интервала xxm. Могут быть и граничные условия других типов. Таким образом, для определения коэффициентов решается система  линейных уравнений.

Для изображений в пространстве нужно построить поверхность, проходящую через данные точки пространства. Используется функция 2 переменных, т.е. интерполяционный бикубический сплайн. ИНТЕРПОЛЯЦИОННЫЙ БИКУБИЧЕСКИЙ СПЛАЙН - функция 2 переменных S(x,y). обладающая свойствами:

1. График   функции   S(x,y)   проходит   через   каждую   точку   заданного   массива,   т. S(xi,yj)=Zij, i=0..m,j=0..n;

2. На каждом из прямоугольников |xi,xj+i]*[yj,yj+1,], i=0..m-l, j=0..n-l  функция является многочленом 3-ей степени по каждой из переменных:

3. На всем прямоугольнике задания |x0,xm]*[y0,yn,] функция S(x,y) имеет по каждой переменной непрерывную вторую производную.

Количество коэффициентов бикубического сплайна равно 16*m*n . Как и для одномерного случая, для получения коэффициентов строится система линейных уравнений.

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

Пусть в пространстве (или на плоскости) задан упорядоченный набор точек, определяемый векторами V0-V1-…-Vm. Ломаная V0-V1-…-Vm называется контрольной ломаной, порожденной массивом V = {Vo,V1,...Vm}.

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

Математически кривая Безье описывается полиномиальной функцией, которая осуществляет интерполяцию между начальной и конечной точками интервала. Кривая Безье является гладкой и катается начального (V0 -Vi) и конечного (Vm-1-Vm) отрезков контрольной ломаной. Каждый член полинома соответствует одной из точек интервала. Точки могут рассматриваться в любом порядке, а не только по возрастанию одной из координат). Следовательно, в зависимости от порядка точек получаются разные кривые. Пример - для 4 точек (кубическая кривая Безье):

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

•  степень коэффициентов полинома на 1 меньше количества точек, т.е. зависит от количества точек

•   изменение хотя бы одной точки приводит к изменению вида кривой, при добавлении/изменении хотя бы одной точки набора требуется пересчет всех коэффициентов.

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

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

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

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

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

В бета-сплайнах весовые коэффициенты (в формулах для которых присутствует обозначение бета) ищутся исходя из условий гладкости в точках сопряжения частичных кривых. Математические формулы, обеспечивающие это свойство, известны (непрерывность функции, первой и второй производной). Следовательно, путем ряда математических преобразований ищутся коэффициенты многочленов, в состав которых входят 2 числовые параметра. Эти параметры называются параметрами формы бета-сплайновой кривой: (1 - параметр скоса. (2- параметр напряжения (1 > 0, 2 >= 0). При 1 = 1, 2 = 0 получается кубическая В-сплайновая кривая.

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


20. Алгоритм Брезенхема.

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

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

Плавно изогнутые линии подвергаются кусочно-линейной аппроксимации, минимальный шаг - 1 пиксел. Возможность соединения двух пикселов растровой линией называется СВЯЗНОСТЬЮ. Растровая линия – суть последовательный набор соседних пикселов. Пусть есть 2 пиксела с координатами Pl(xl,yl) и Р2(х2, у2).

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

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

Можно строить 4-и 8-связное представление. Возможны и другие растровые модели. Все зависит от того, какими свойствами требуется наделить полученный образ.

 

Очевидное решение - инициировать последовательно все точки растра, квадратные окрестности которых пересекают данный отрезок. Результатом является 4-связная растровая развертка отрезка. 8-связная решетка включает те точки растра, боковые стороны квадратных окрестностей которых пересекаются с отрезком.

Пусть отрезок имеет координаты концов M(xl,yl) и М2(x2,у2). Уравнение прямой y=k*x+b. Для простоты предположим, что угловой коэффициент 0 < k <= 1 (k не отрицателен и не превосходит 1), т.е 0<=(y2-yl)<=(x2-xl). Уравнение отрезка имеет вид y =k*(x-xl)+yl, где k = (y2-y1)/(x2-x1).

В 1965 г. Брезенхейм (Bresenham) предложил простой целочисленный алгоритм растрового построения отрезка. Сначала он использовался в графопостроителях. Алгоритм основан на том, что при построении всегда берется ближайший по вертикали пиксел, т.е. точка, ближайшая к исходной прямой. Очевидная оценка близости: если отклонение исходной прямой по оси ординат от текущего значения превышает 0.5, увеличиваем координату у на 1, корректируем текущее значение отклонения. Чтобы перейти к целочисленным расчетам, изменяют масштаб, умножая отклонение и приращение по оси у  d =(y2-y1)/(x2-x1) на некоторое целое 2*n . В качестве n естественно выбирается величина х2-х1, т.е.  отклонение вычисляется как d =(х2-х1)*(b-а). Если d>0, значение у увеличивается на 1, иначе – не изменяется. d при этом уменьшается на "масштабированную" единицу, (вместо у=у-1 пишем у=y+2*((y2-yl)-(x2-xl))) или увеличиваетcя на величину "масштабированного" приращения (вместо у=у+ ((y2-yl)/(x2-xl)) пишем у = y+2*(y2-yl)).

До сих пор рассматривался случай 0<k<1 в уравнении прямой у = k*х+b . Для случая |k|>1 переменные х и у меняются местами.


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

Многоугольник плоская фигура, ограниченная не самопересекающейся замкнутой ломаной линией. Пусть эта ломаная задается набором вершин. Задача состоит в различении внутренних и внешних точек мной многоугольника. Решение достаточно просто. Выпустим из тестируемой точки произвольный и найдем количество его пересечений с границей прямоугольника. Если это количество нечетно, точка лежит внутри, в противном случае – вне многоугольника. Прохождение луча через некоторую вершину не рассматривается, так как его можно обойти. Но обход вершин связан с определенными трудностями, требуется много проверок. Проверка пересечения с произвольным лучом также неудобна. Поэтому лучше принять соглашение о направлении пересекающего луча. Приняли горизонтальное направление. Это позволило также исключить из рассмотрения все горизонтальные отрезки многоугольника. Что делать при попадании тестирующего луча на вершину? Пересечение не засчитывается, если вершина является верхней для отрезка и засчитывается в любом другом случае. Следовательно, для точек максимума пересечение игнорируется, для точек минимума считается дважды. Для прочих вершин засчитывается единичное пересечение. Зная аналитическое уравнение прямой и вышеизложенный алгоритм, можно написать программу.


22. Алгоритмы заполнения (закраски) замкнутой области.

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

Некоторые алгоритмы заполнения областей

Задачи заполнения некоторой замкнутой области также называются задачами закраски. Требуется заполнить внутреннюю часть области пикселями определенного цвета. Рассмотрим 2 класса таких задач: заполнение многоугольников и заполнение области с затравкой.

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

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

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

 Для выпуклых многоугольников алгоритм ещё проще, т.к. есть всего 2 точки пересечения на каждой растровой прямой (рис. в). Генерируя с помощью алгоритма Брезенхема растровое представление 2 противолежащих ребер для одной и той же ординаты, получаем пикселы, лежащие на границах интервала заполнения.

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

 Простейший алгоритм выполняет перебор всех точек и анализ их окрестностей. Возможен анализ в рамках 4- и 8-связности. Для хранения координат точек используется стек. Сначала туда заносятся координаты затравочной точки. Извлечем из стека очередную точку, закрасим ее и исследуем ее 4- или 8-вязную окрестность. Если исследуемая точка не лежит на границе фигуры и уже не закрашена, поместим ее в стек. По окончании исследования выберем из стека  очередной пиксел, повторим алгоритм. Алгоритм заполняет области любой формы. Но он неэффективен, т.к. один пиксел обрабатывается многократно, стек может неконтролируемо расти

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


23. Отсечение отрезка. Алгоритм Сазерленда-Кохена.

Задачу отсечения иногда называют задачей клиппирования (от английского clip -отрезать, отсекать). Она возникает довольно часто. Пример – размещение изобращения в окнах, в том числе занимающих весь экран, при различном разрешении (640*480, 800*600 и тд). Требуется знать пикселы, лежащие за пределами окна и не работать с ними. Решение «в лоб» – сравнивать с границами каждый выводимый пиксел. Но это долго, т.к. сравнение должно быть встроено в цикл в алгоритме Брезенхейма. К тому же границы должны или где-то храниться в виде набора адресов пикселов, или вычисляться путем 4-х кратного (для каждой стороны прямо угольника) решения уравнения прямой для каждой точки. Придется также учитывать специальные случаи горизонтальной и вертикальной прямой, а также вырождение прямой в точку.

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

№бита

Положение точки при бит= 1

0

Слева от прямоугольника

1

Выше прямоугольника

2

Справа от прямоугольника

3

Ниже прямоугольника

0011

0010

0110

0001

0000

0100

1001

1000

1100

 Соотношение конечных точек и прямоугольника вычисляется с помощью поразрядных логических операции: над кодами. Они выполняются очень быстро, т.к. в процессорах 80х86 есть машинные команды AND и OR.


24. Растровое представление эллипса.

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

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

Как формируется эллипс? Решение "в лоб" - использовать алгебраическое уравнение. Пусть эллипс имеет координаты центра (Xс,Yс). размеры полуосей а и b, полуоси параллельны осям х и у. Вид уравнения ((X-Xc)2/ а2)+((Y-Yc) 2)/ b2)=0

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

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

Уравнение простейшего эллипса с центром в начале координат и полуосями b (по оси у) и а (по оси х):  b2*x2 + а2 * y2 - а2 * b2 =0.

Используется так называемый "алгоритм средней точки". Он выбирает, какой из соседних пикселов ближе к эллипсу, вычисляя, находится ли средняя между пикселями точка вне или внутри эллипса. Подставим координаты средней точки (p,q) в уравнение эллипса: d = b2 * р2 + а2 * q2 - а2 * b2. d = 0, если точка лежит на эллипсе, d<0, если точка находится внутри эллипса, d>0, если точка находится вне эллипса. Следовательно, по знаку функции можно определить ближайший пиксел.

Средняя точка М лежит внутри эллипса. выбирается ближайшая точка А.

Средняя точка М лежит вне эллипса, выбирается ближайшая точка В.

 

Возникает вопрос: какую пару соседних пикселов исследовать на близость? Выбор зависит от наклона касательной к эллипсу. Пусть dу = (у2 - yl), dx = (х2 - xl). Наклон вычисляется как dy/dx.

Если dy/dx > -1, выбираются соседние вертикальные пикселы.

Если dy/dx < -1, выбираются соседние горизонтальные пикселы.

Очередной пиксел выбирается итеративно по отношению к предыдущему пикселу. Если dy/dx>-1   х=х+1, у =у-0.5. Если dy/dx<-1,   х=х+0.5, у = у -1. Сравнивая d для двух соседних точек, можно вывести итерационные формулы для d.

При   dy/dx>-1

d новое=dстарое +2* b2*x старое+ b2

При dy/dx<-1

dновое=dстарое +2* a2*y старое+ a2

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

Формулы для подсчета d определяются точкой, где dy/dx = -1. Как ее найти? Можно продифференцировать уравнение эллипса и приравнять результат к -1:

 

Обычно алгоритм начинается в точке (0,b) и заканчивается в точке (а,0). Движение идет по часовой стрелке. Первоначально dy/dx > -1. Следовательно, выбор осуществляется между пикселями по вертикали. Затем пикселы выбираются по горизонтали до достижения оси x. Для dy/dx = -1 производится замена вертикального нахождения новой средней точки на горизонтальное.

Инкремент для d можно вычислить:

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

В изображении эллипса имеются некоторые проблемы. Когда эллипс мал и для его изображения требуется сравнительно мало пикселов, аппроксимация выглядит как многоугольник (вместо плавной кривой - ломаная). Аналогична ситуация для "тонких" эллипсов с большой разницей между а и b. Выход состоит в переходе к более высокому разрешению (может быть на том же адаптере путем сокращения количества цветов). Друга проблема - вырожденные в прямую эллипсы (а = 0 или b = 0). Здесь или dy = 0, или dx = 0 , следовательно итерация правильно не заканчивается. В программе перед циклом нужна проверка на вырождение.


25. Исходные эвристики, используемые при удалении невидимых линий  и поверхностей.

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

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

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

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

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

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


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

Алгоритм удаления невидимых поверхностей можно определить следующим образом:

 AУHЛиП = (O,S,I,f,st), где О - множество объектов в трехмерном пространстве;

S  - множество видимых отрезков в двумерном пространстве;

I  - множество "промежуточных представлений";

f - множество "функций перехода",  f={PM,IS,CT,DT,VT}

 st - "функция стратегии".

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

РМ - функция преобразования проецирования. Она строит проекции (чаще перспективные), т.е. преобразует трехмерное пространство в двумерное

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

1. Найти точку отрезка прямой, в которой происходит изменение видимости;

2. Определить, имеется ли непустое пересечение проекций 2 многоугольников на картинную плоскость (см. 3ю эвристику: при пустом пересечении возможна независимая обработка непересекающихся фрагментов);

3. Найти точки пересечения объектов со сканирующей прямой (см. растровые алгоритмы);

4. Использовать результат в тесте принадлежности (см. далее);

5. Найти точку пересечения граней объекта и прямой, соединяющей точку наблюдения со специальной тесто вой точкой в объектном пространстве. Пересекающиеся прямые описываются системой линейных уравнений:

A1*x+B1*y+c1=0     Если    |A1 B1| =0, прямые параллельны.

A2*x+B2*y+c2=0  |A2 B2|

Если a1/a2=b1/b2=c1/c2, прямые совпадают. Иначе точка пересечения имеет координаты

x=(b1*c2-b2*c1)/(a1*b2-a2*b1)   y=(c1*a2-c2*a1)/(a1*b2-a2*b1)

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

СТ - функция, выполняющая в двумерном пространстве "тест принадлежности", т.е. проверяющая, лежит ли некоторая точка внутри многоугольника. Результат - булева переменная ИСТИНА или ЛОЖЬ. Проверку на принадлежность методом подсчета числа пересечений рассматривали ранее. Есть еще один тест, известный из элементарной геометрии. Соединим прямыми исследуемую точку с каждой из вершин многоугольника. Каждая пара соседних прямых образует угол. Точка находится вне многоугольника, если сумма углов равна 0, и внутри, если эта сумма равна 2*.

 DT - функция, выполняющая "тест глубины", т.е. сравнивающая 2 точки и определяющая, какая из них расположена дальше/ближе от точки наблюдения. Одна или обе сравниваемые точки могут принадлежать некоторой грани. Следовательно, сравниваются точка - точка, точка - грань, грань - грань. Под глубиной понимается расстояние между элементом и картинной плоскостью или между элементом и точкой наблюдения. Т.е. глубина относится к z-координате элемента, тест глубины заключается в сравнении z-координат двух элементов. Имеются 3 теста глубины:

Тест DT1  применяется для объектного пространства.

Тест DT2  предназначен для параллельной проекции

Тест DT3  применяется в растровых алгоритмах при проверке видимости проекции граней на картинную плоскость вдоль сканирующей прямой


27. Тесты глубины, используемые при удалении невидимых поверхностей.

1. Тест DT1 применяется для объектного пространства. Он сопоставляет грань и точку и определяет, заслоняет ли грань точку Для этого ищется точка пересечения грани с так называемой "линией визирования", т.е линией, проходящей через проверяемую точку и точку наблюдения. Если пересечения нет, проверяемая точка видима. В противном случае вычисляется расстояние от точки наблюдения до точки пересечения dp и до проверяемой точки dt. Если dp > dt, проверяемая точка видима, в противном случае - невидима.

2. Тест DT2 предназначен для параллельной проекции и оперирует элементами как в объектном пространстве так и в картинной плоскости. Проверяются либо 2 грани, либо точка и грань. Для двух граней берется некоторая точка плоскости, которая является общей для проекций на эту плоскость обеих граней. Затем находятся точки на гранях, которые проецируются в выбранную точку. Для этого координаты выбранной точки подставляются в уравнения плоскостей, содержащих грани, и эти уравнения решаются относительно координаты z (параллельная проекция, точка наблюдения находится в бесконечности и лежит на линии, расположенной перпендикулярно или под некоторым углом к плоскости проектирования). Точка плоскости выбирается так. чтобы было zlz2 Считается, что грань f1 имеет приоритет над гранью f2, если zl<z2. Поэтому тест DT2 называют также приоритетным тестом. В тесте точка - поверхность пропускается шаг определения общей точки. Координаты тестируемой точки сразу подставляются в уравнение плоскости, найденная z-координата грани сравнивается с z-координатой точки, в результате решается вопрос о приоритете поверхности над точкой или наоборот.

Для проникающих граней и циклического перекрытия тест "в лоб" не работает. Поэтому грани разбивают (штриховая линия на рисунке).

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

VT - функция, выполняющая "тест видимости" для данной поверхности. Она выдает значение ИСТИНА, если поверхность видима и ЛОЖЬ в противном случае. Применяется только к телам. Определяет, являете ли некоторая грань тела "передней", т.е. потенциально видимой, или "задней". Очевидно, что тест может при меняться только к структурированным объектам в объектном пространстве. К гладким поверхностям тест не применим. Если имеется несколько объектов, то тест видимости не решает вопросы загораживания. Он выявляет только заведомо невидимые элементы каждого тела. Они не участвуют в последующих вычислениях.

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

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

Функция стратегии st определяет порядок применения функций из множества f для получения требуемого результата. Возможны 2 подхода к решению задачи и соответственно 2 типа алгоритмов: объектные и кар тинные. Объектный подход рассматривает видимость в объектном пространстве. При этом сначала выполняете. тест видимости, потом - преобразование проецирования. Временные характеристики таких алгоритмов обычно обладают квадратичной зависимостью от числа объектов сцены. Картинный подход рассматривает видимость ] пространстве отображения. Определяется видимость каждого элемента картинной плоскости (т.е. каждого пик села). При этом сначала выполняется преобразование проецирования, потом - тест видимости. Временные характеристики таких алгоритмов оцениваются как линейные функции от произведения числа объектов на число точек растра. Существуют и смешанные алгоритмы, использующие как первый, так и второй подход.


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

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

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

 Наиболее простыми и часто используемыми фигурами являются выпуклые многогранники. Их грани представляют собой выпуклые многоугольники. ВЫПУКЛЫЙ МНОГОУГОЛЬНИК - это плоский много угольник, обладающий следующим свойством: через каждое его ребро можно провести прямую такую, что ВСЕ вершины многоугольника, не наводящиеся на прямой, оказываются в одной полуплоскости (т.е. лежат с одной стороны от прямой). Для выпуклых многоугольников любая грань либо полностью видима, либо полностью невидима.


29. Алгоритм Робертса, алгоритм Z-буфера, метод построчного сканирования: суть, область применения, сравнительный анализ.

Алгоритм Робертса

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

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

•грань полностью или частично закрывает ребро:

• грань и ребро пересекаются

Первый случай наблюдается в 2 вариантах:

•ребро находится в том же

полупространстве относительно грани, что и наблюдатель

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

Во втором случае ребро полностью расположено в полупространстве, не содержащем наблюдателя. Проекция ребра полностью лежит внутри проекции грани. Если ребро полностью закрыто, оно исключается из дальнейшего рассмотрения. Для частично закрытых ребер производится разбиение, получаем видимых подребра, которые включаются в список для дальнейшего рассмотрения. В третьем случае ребро пересекается с плоскостью, содержащей грань - рис. д). Аналогично второму случаю ребро разбивается на части, из которых видимы не более 2, далее рассматриваем только видимые под ребра. Разбиение делается на 2 части по точке пересечения, рассматриваем отдельно обе части, т.е. сводим к предыдущим случаям.

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

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

Метод Z-буфера

Метод весьма прост, что делает его удобным для аппаратной реализации. Время работы не зависит с числа граней, но линейно зависит от количества точек растра и "глубины сцены", т.е. от числа граней, взаимно закрывающих друг друга. Как правило, метод используется для ортогональных проекций. Его реализация осуществляется с помощью 2 буферов: буфера глубины (Z-буфера) и буфера кадра. Буфер глубины хранит z координаты пикселов экрана (отражено в названии метода). Буфер кадра хранит информацию о состоянии пикселов экрана (интенсивность, цвет). Изначально буфер глубины инициализируется значением +бесконечность. Буфер кадра - атрибутами фона. В ходе работы проекция очередной грани объекта разлагается в растр для каждого пиксела выполняется сравнение его глубины с глубиной, ранее занесенной для этого пиксела в Z буфер. Если для нового пиксела z-координата меньше значения буфера, то он ближе к наблюдателю и, следовательно, видим. Его характеристики заносятся в буфер кадра и Z-буфер.

Алгоритм легко модифицируется для получения сечений поверхности параллельными плоскостями. Для этого на экран выводятся только проекции точек с z-координатой в требуемом интервале.

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

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

Рассмотренный прием используется в играх DOOM и Wolfenstein3d. В Wolfenstein 3d для лабиринта используется не горизонтальное, а вертикальное разбиение, т.к. это в большей степени отвечает задаче..


30. Подсчет количественной невидимости с помощью алгоритма Аппеля.

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

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

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

Работа алгоритма начинается с выбора какой-либо вершины многогранника и определения ее количественной невидимости. Для этого через эту точку и точку наблюдения проводится отрезок прямой и находятся пересечения этого отрезка со всеми гранями (как в тесте глубины DT1). Число найденных граней - количественная невидимость начальной точки. Далее прослеживается изменение количественной невидимости вдоль каждого из ребер, выходящих из этой вершины Эти ребра проверяются на прохождение позади контурной линии, что изменяет количественную невидимость. Части отрезка с нулевой количественной невидимостью сразу рисуются Далее выбирается вершина, образуемая одним из рассмотренных ребер. Для нее количественная невидимость подсчитана, процесс повторяется. Как определить пересечение рассматриваемого ребра с контурным? Аппель предлагает следующее. Образуется треугольник, вершинами которого являются точка наблюдения и концы исследуемого ребра. Контурное ребро изменяет количественную невидимость ребра q, если оно протыкает треугольник, т.е. точка пересечения контурного ребра с плоскостью треугольника лежит внутри  треугольника. Если пересечение существует, количественная невидимость q увеличивается на 1 при положительном знаке векторного произведения контурного и рассматриваемого ребер и уменьшается на 1 в противном случае.

По сравнению с алгоритмом Робертса алгоритм Аппеля более быстр, т.к. число ребер, входящих в контурную линию, намного меньше общего числа ребер.

Подсчет количественной невидимости можно применять и для гладких поверхностей. Здесь контурные линии являются гладкими кривыми. Количественная невидимость точки изменяется, если точка поверхности проектируется на проекцию контурных линий (это происходит при наличии складок в теле). Складка изменяет невидимость на 2.


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

Идея состоит в попытке упорядочить элементы сцены по некоторому признаку. Обычно в качестве критерия упорядочения выступает глубина элементов сцены. Тест глубины рассматривался ранее. Вывод проекций граней на картинную плоскость выполняется, начиная с самых дальних от точки наблюдения граней в порядке приближения к точке наблюдения. Возможны случаи, когда сортировка по расстоянию до картинной плоскости не обеспечивает правильного упорядочения граней из-за пересечения объектов. Перед выводом грани Р следует убедиться, что никакая другая грань Q, проекция которой пересекается с проекцией грани Р, не закрывается гранью Р. Тогда грань Р выводится раньше Q. Требуются дополнительные проверки для установления порядка вывода граней. Рассмотрим эти проверки для наиболее простого случая параллельного проектирования вдоль оси Z. Тесты в порядке возрастания сложности проверки:

 1. Накладываются ли друг на друга отрезки при проектировании проекций граней в плоскости XY на ось X.

 2. Накладываются ли друг на друга отрезки при проектировании проекций граней в плоскости XY на ось Y.

 3. Находится ли грань Р по отношению к плоскости, проходящей через грань Q, по другую сторону, чем наблюдатель.

 4. Находится ли грань Q по отношению к плоскости, проходящей через грань Р, по ту же сторону, что наблюдатель.

 5. Пересекаются ли проекции граней Р и Q на картинную плоскость.

Если хотя бы на один из вопросов получен отрицательный ответ, считается, что грани Р и Q упорядочены верно, грань Р сравнивается со следующей гранью. В противном случае проверяется возможность поменять грани местами. Для этого выполняются следующие тесты:

3а. Находятся ли грань Q и наблюдатель по разные стороны плоскости, проходящей через грань Р.

4а. Находится ли грань Р и наблюдатель по одну сторону плоскости, проходящей через грань Q.

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


32. Триангуляция.

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

По сравнению с прямоугольной сеткой триангуляция имеет преимущества:

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

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

В настоящее время в большинстве приложений используется триангуляция Делоне. Она строится однзначно и соединяет исходные точки в сеть наиболее правильных треугольников. Это удобнее в расчетах.

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

1. треугольник и плоскость не пересекаются, т.е. все вершины лежат по одну сторону плоскости;

2. треугольник касается плоскости одной вершиной, все вершины лежат по одну сторону плоскости;

3. треугольник пересекается с плоскостью по ребру, две вершины лежат на плоскости, все вершины лежат п одну сторону плоскости;

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

5. треугольник лежит в плоскости, т.е. все вершины лежат в плоскости.

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


33. Закраска методами Гуро и Фонга.

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

Метод основан на определении освещенности грани в ее вершинах с последующей билинейной (би=2) интерполяцией результатов на всю грань. Пусть проекция некоторой грани на экран является выпуклым 4-угольником Пусть интенсивности вершин определены и равны I1,I2,I3,I4. Пусть W - произвольная точка грани. Проведем через нее горизонталь. Пусть Р и Q - точки пересечения горизонтали с границами проекции грани. Будем считать, что интенсивность на отрезке PQ меняется линейно, те.

Для определения интенсивности в точках Р и Q снова применяется линейная интерполяция (отсюда термин билинейная). Считаем, что вдоль каждого из ребер границы интенсивность меняется линейно. Тогда интенсивность в точках Р и Q:          

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

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

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

Для каждой точки строится вектор, играющий роль внешней нормали. Далее применяется формула. Схема интерполяции аналогична методу Гуро. Для определения псевдонормали в некоторой точке (точке V через эту точку проводится горизонтальная прямая. Она пересекается с ребрами в точках Р и Q. Пусть вектор псевдонормалей в этих точках соответственно Np и Nq . Тогда

Nw= ((1-t)*Np+t*Nq)/ |((1-t)*Np+t*Nq)   t= |PW|/|PQ|

Нормирование вектора Nw необходимо, т.к. в формулы входит единичный вектор нормали.

Векторы внешних нормалей (псеводнормалей) в точках Р и Q находятся также линейной интерполяцией, но по векторам нормалей концов соответствующих ребер.

Np= (1-u)*Nv4+u*Nv1  Nq=(1-v)*Nv1+u*Nv2    u= |V4P|/|V4V1|  v= |V1Q|/|V1V2|

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

Методы Гуро и Фонга сравнительно просты. Но они не всегда обеспечивают приемлемое качество.


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

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

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

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

Процесс отслеживания всех лучей, выпущенных из каждого источника, с учетом отражения и преломления - ПРЯМАЯ ТРАССИРОВКА ЛУЧЕЙ. Она неэффективна, т.к. изображение формируется лишь небольшой частью лучей, возникают лишние вычисления. Чтобы использовать только существенные лучи. применяется ОБРАТНАЯ ТРАССИРОВКА, где прослеживаются лучи от гл;п;1 наблюдателя до пересечения с объектами сцены и далее в направлении к источнику. В компьютерной графике применяется обратная трассировка.

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

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

Расчет освещенности и распространения света основан на законах физики Свет имеет волновую природу и рассматривается как поток частиц или электромагнитная волна. Интенсивность определяется амплитудой волны, цвет — частотой или длиной волны. Распространение света описывается уравнениями Максвелла.

Произвольный луч света практически не бывает монохромным.. Он состоит, из волн различной длинны. Интенсивность различных волн показывает спектральный анализ. Но поскольку основная цветовая палитра состоит из трех базовых цветов, при исследовании обычно берут только длины волн красного, зеленого и синего цветов. Остальные цвета - их комбинация.

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

Для вторичных источников учитывается зеркальное отражение, диффузное отражение и преломление. При зеркальном отражении луч строго направлен. При диффузном отражении падающий свет рассеивается е все стороны с одинаковой интенсивностью. Поэтому однозначно определить направление нельзя, все направления равноправны. Идеальное диффузное отражение описывается законом Ламберта (п.6.6.1, формула (1)). При идеальном преломлении луч уходит внутрь тела в виде сосредоточенного пучка. При диффузном преломлении луч распространяется в теле одинаково по всем направлениям. Для всех этих случаев существуют формулы.

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

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

• освещенность от каждого из источников света;

• интенсивность (освещенность) фонового освещения;

• освещенность от каждого из отраженных лучей;

• освещенность, приносимая преломленным лучом.

Для освещенности от каждого из источников имеются коэффициенты, отражающие "вклад" источника:

• коэффициент фонового освещения;

• коэффициент диффузного освещения;

• коэффициент зеркального освещения;

• вклад преломленного луча.

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

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

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


35. Понятие текстуры и способы моделирования текстур.

Повышение реалистичности изображения требует учета различных видов поверхностей, т.е. моделирования текстур. Например, для изображения мрамора с прожилками требуется менять цвет поверхности в зависимости от положения точки на ней. Возможны два основных варианта; проективные и процедурные (сплошные - solid) текстуры. В первом случае изображение реальной раскрашенной (мраморной) поверхности проецируется на поверхность объекта, т.е. учитывается искажение рисунка для изогнутых или стоящих под углом к наблюдателю поверхностей. В итоге трехмерные координаты точки сводятся к двумерным, которые затем используются для индексации цвета. Этот вариант прост понятийно, т.к. методы получения проекции известны, но не экономичен по памяти, так как хранятся дополнительные индексы цвета. К тому же проецирование объектов сложной формы – не простая задача. Во втором случае строится функция, определяющая цвет каждой точки в соответствии с исходным рисунком. Здесь затраты памяти невелики, сложность формы объекта на работу не влияет. Но создать такую функцию сложно, поэтому продают библиотеки текстур аналогично библиотекам шрифтов.

Простейшие текстуры моделируют клетчатую поверхность (шахматная доска) и кирпичную кладку. Кроме цветовых текстур моделируют текстуры с меняющимися коэффициентами вторичной освещенности (например, коэффициентом преломления), меняющимся вектором нормали к точке (меняющийся рельеф местности - рябь, волны на воде). Для внесения неправильностей используют шумовые текстуры. Пример - моделирование текстуры дерева с учетом того, что годовые кольца не носят строго правильный характер. Обычно на шумовую функцию накладываются требования непрерывности, выдачи значений из диапазона [0,1], распределение значений близко к равномерному.  Способы построения таких функций известны. Шумовая функция применяется и при моделировании текстуры мрамора. Шум можно наложить не только на цвет, но и на вектор нормали.


36. Распределенная трассировка лучей, оптимизация трассировки лучей.

Распределенная трассировка лучей

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

Выходом является распределенная трассировка (Distributed Ray Tracing). Для вычисления соответствующего интеграла используется метод Монте-Карло. В области пиксела выбирается по равномерному закону распределения случайная точка и трассируется луч, проходящий через эту точку. Освещенность, привносимая этим лучом - случайная величина. Поэтому для вычисления цвета пиксела достаточно оттрассировать несколько равномерно распределенных случайных лучей, и взять среднее значение. Способы выбора тестовых точек различны. Наиболее распространен метод "шевеления" регулярной решетки. Область пиксела разбивается на n1 * n2 одинаковых частей, в каждой из них выбирается равномерно распределенная случайная точка для проведения луча. "Шевеление", т.к. узел решетки, где находится пиксел, как бы шевелится, "плывет" в некоторой области. Рассмотренный метод устраняет погрешность, связанную с неучетом размера пиксела, но вносит свою - высокочастотный шум, который для глаза менее заметен.

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

При неточечных источниках света возможно трассирование нескольких лучей из одной точки объекта в разные СЛУЧАЙНЫЕ точки источника света. Неточечные источники света вместо резких теней дают мягкие полутени. Можно реализовать сферический, цилиндрический ц другой формы источники.

Микрофасетная поверхность (от франц. facette - грань, шершавая поверхность с упорядоченным рисунком) дает нечеткое отражение, когда лучи, идущие из разных точек объекта, попадают в одну точку поверхности и отражаются в одном и том же направлении. Поэтому вместо одного отраженного или преломленного луча можно выпустить несколько СЛУЧАЙНЫХ лучей и определить приносимую ими энергию с учетом их весовых коэффициентов, зависящих от направления (для учета направления рисунка поверхности). Вместо равномерного распределения лучей можно использовать их веса для выбора предпочтительного направления. Тогда приносимые ими значения усредняются. Веса не используются.

Распределенная трассировка лучей позволяет также моделировать неидеальную камеру. В идеальной камере все объекты находятся в фокусе, поэтому нет размывов из-за отсутствия резкости в некоторой части изображения. До сих пор наблюдатель (камера) трактовался как точки. Считалось, что каждая точка экрана освещается одним лучом, проходящим через точку наблюдения. В реальной камере точка освещается бесконечным множеством лучей, проходящих через линзу. Для учета этого используются известные законы оптики. Размытость моделируется выбором СЛУЧАЙНОЙ точки на линзе и исследованием преломленного от нее луча. Количество таких случайных точек ограничивается специальными методами (не рассматриваем, т.к. сложно, узко).

Оптимизации трассировки лучей

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

    Особенно долго ищется пересечение с объектами сложной формы. Объект можно поместить внутрь простой фигуры (например, сферы). Если луч не пересекает эту фигуру, то он не пересекает и обьект, который исследовать не надо. Пересечение со сферой определить просто, можно использовать, например, аналитический метод (уравнение). Вспомогательную фигуру пересечет небольшая часть рассматриваемых лучей. Эти лучи проверяются на пересечение со сложной фигурой. Здесь очевиден выигрыш за счет уменьшения количества лучей. Можно описать фигуру вокруг нескольких объектов. При пересечении - аналогичное разбиение группы на подгруппы и т.д. Строится дерево разбиений. Начальная простая фигура содержит всю сцену (аналог дихотомии). Количество проверок на пересечение для данного метода пропорционально O (log n), где n - общее количество объектов.

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


37. Метод излучательности.

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

Пусть все объекты являются чисто диффузными, т.е. отражают (рассеивают) все равномерно по всем направлениям. Тогда для i-того фрагмента уравнение имеет вид:

 Bi=Ei+piFi,j*Bj  i=1..n

где   Bi - энергия, отбрасываемая i-тым фрагментом сцены,

Ei - собственная излучательность фрагмента,

Fi,j - доля энергии j-того фрагмента, попадающая на i-тый фрагмент (коэффициент формы),

рi - коэффициент отражения.

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

Из закона сохранения энергии следует, что Fi,j <1 для всех i.

Система уравнений имеет так называемое сильное диагональное преобладание, для ее решения можно использовать эффективные итерационные методы (типа Гаусса-Зейделя). При этом за небольшое число итераций достигается приемлемое решение.

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

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

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


38. Системы цветов.

До сих пор цвет рассматривался в так называемой аддитивной форме как композиция в некоторой пропорции 3 базовых цветов RGB. Соединение всех трех цветов в равной пропорции образует белый цвет, отсутствие всех цветов черный (фон). Система RGB естественна для компьютера.

Существует и другой подход к формированию цвета субтрактивный. Он характерен для полиграфии и учитывает поглощение и отражение света от белой поверхности (бумага). Подход основан на вычитании цветов. Здесь белый цвет (фон) отсутствие всех цветов, черный соединение в равной пропорции голубого (cyan), пурпурного (magenta) и желтого (yellow). На практике только сочетанием 3 базовых цветов достигается не черный, а темно-коричневый цвет из-за неполного поглощения света типографскими красками. Поэтому для представления истинно черного делают 4-цветную печать с добавлением черного, система цветов называется CMYK (чтобы не путать с Blue  синий, взята последняя буква слова blacK черный). Происходит как бы вычитание цвета из белого. Данная система была разработана давно и применялась в полиграфии. Для цветоделения (разделения цветов на основные цвета CMYK) применялись фотомеханические методы.

Существует проблема перевода изображений, разработанных в системе RGB, в систему CMYK. Система RGB работает с излучаемым светом, а CMYK с отраженным. У них разная природа получения цветов и то, что видно на экране монитора, нельзя точно повторить при печати. Преобразование усложняется и тем, что приходится корректировать несовершенство типографских красок подмешиванием черного. Имеются специальные системы предпечатной обработки изображений, которые учитывают не только цвета, но и сорт бумаги и показывают на экране, как будет выглядеть напечатанный рисунок. Существуют программы, которые позволяют создавать рисунок сразу в цветах CMYK. Это учитывается в графических форматах. Но возникают проблемы преобразования файлов, проблемы преобразования и интерпретации цветовых пространств.

Системы цветов RGB и CMYK базируются на ограничениях, накладываемых аппаратурой (дисплей, типографское оборудование), и основаны на смешении красок. Существует другой подход, учитывающий яркость (насыщенность) цветов. Его реализация системы HSI(HSL) и YcbCr.

Аббревиатура HSI (HSL) означает Hue  цвет, оттенок, Saturation  насыщенность, Intensity или Luminosity  яркость. Насыщенность трактуется как количество белого, подмешанного к основному цвету (темно-синий/голубой), яркость может отражать, например, освещенность (апельсин в солнечном свете или в сумерках). HSI  более интуитивный способ определения цветов, не зависящий от схемы смешения. В этой системе работают некоторые пакеты программ, имеются графические адаптеры, которые “понимают” HSI и преобразуют ее в RGB. HSI больше соответствует природе света.

Аббревиатура YcbCr происходит от Y(luminositY, яркость), Cb (chrominance blue, цветность исходного синего), Cr (chrominance red, цветность исходного красного). Зеленый комбинация этих трех значений. Отделение яркости от цветности позволяет более эффективное сжимать изображения (см. п. 7.3), т.к. глаз человека больше реагирует на интенсивность, чем на разрешение цвета. Представление YcbCr все шире используется для настольных видеосистем.

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

Монохромные изображения (градации серого) выводятся на дисплей или лазерный принтер. Используются точки одного цвета. Их густота дает оттенок. Изображение называется полутоновым, если обеспечивается непрерывность оттенка. При редактировании на дисплее используют биты интенсивности. При печати это не подходит. Используется добавочный псевдослучайный сигнал, который позволяет регулировать количество черных точек. Он накладывается на основной рисунок, что создает эффект “размытости”. При этом разрешение устройства уменьшается, т.к. часть битов используется для изображения, часть – для дополнительного сигнала. Аналог увеличение цветности за счет уменьшения разрешения видеоадаптера. Таким образом, печать выполняется с псевдослучайным сигналом, редактирование с битами интенсивности, т.к. большинство графических приложений не различает точки для основного рисунка и точки для оттенения.

При переносе изображений между носителями возникает также проблема точности цветов и для цветных, и для полутоновых изображений. Например, на разных дисплеях различны оттенки красного, белая точка имеет не совсем белый цвет, хотя значения R, G и B равны. Требуется калибровка входных и выходных устройств, например, цветного сканера и монитора, на который идет изображение. Используют различные колориметрические стандарты. Наиболее известные из них: CIE (Commitee International de l’Eclairage), NTSC (National Television System Commitee), SMPTE (Society of Motion Picture and Television Engineers), ISO (International Standards Organization). В каждом стандарте устанавливается комплект чисел, используемых для определения объективно измеренного цвета. Цвет, который входным и выходным устройством определен как белый, может быть измерен поставщиком устройства и выражен комплектом чисел. Этот результат называется белой точкой устройства. Следовательно, для точной передачи цвета графический файл должен содержать описание в некотором стандарте белой точки передатчика. Пока это реализуется весьма редко, не поддерживается форматами графических файлов. В большинстве устройств также отсутствует автоматическая подстройка цветности.


39. Основные методы сжатия изображений.

Сжатие изображений

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

1. Групповое кодирование

Один из самых простых методов сжатия групповое кодирование или групповое сжатие. Другое название "сжатие методом RLE" (run-length encoding). Идея состоит в том, что вместо повторяющихся пикселов хранится информация о цвете точки и количестве повторений. Представление данных имеет варианты: может сначала идти запись о цвете, потом о количестве, может наоборот. Это порождает проблемы воспроизведения. Для большинства растровых файлов, особенно для фотореалистических сжатие RLE не эффективно, т.к. мало повторяющихся пикселов. Возникает даже лишняя трата ресурсов.

2. Кодирование методом Хаффмана

Кодирование методом Хаффмана (Huffman) общая схема сжатия. Подход создан в 1952 г. для текстовых файлов. Имеется множество вариантов. Основная идея присвоение двоичного кода каждому уникальному элементу, причем длина этих кодов различна. Для наиболее часто повторяющихся элементов используются более короткие коды. Присвоения хранятся в таблице перекодировки, которая загружается в декодирующую программу перед самими кодами. Существуют различные алгоритмы построения кодов. Степень сжатия оценивается как 8 : 1. Для файлов с длинными последовательностями схема Хаффмана работает не очень хорошо. Здесь лучше групповое сжатие. Т.к. для построения кодов нужна статистика, обычно используют 2 прохода. Сначала создается статистическая модель, затем выполняется собственно сжатие (кодирование). Т.к. работа с кодами переменной длины требует много времени, кодирование и декодирование длительны.

3. Схема сжатия LZW

Метод назван по первым буквам фамилий разработчиков: Lempel, Ziv, Welch. Разработка 1984 г. Сначала метод предназначался для аппаратной реализации. Как и алгоритм Хаффмана, алгоритм LZW имеет несколько вариантов. Идея поиск повторяющихся пиксельных узоров и их кодирование. Кодовая таблица создается не перед кодированием, а в процессе кодирования, что делает алгоритм адаптивным. Рассмотрим последовательность "ababaaacaaaad". Пусть каждая буква кодируется в изображении 2-битной величиной. Начальная кодовая таблица кодирует каждый атомарный объект: a 00, b 01, c 10, d 11. Затем алгоритм переходит к поиску последовательностей. Он может распознать только 1-буквенные последовательности. Первая 2-буквенной  последовательности не распознается и подлежит кодированию. Т.к. длина кода исчерпана, ее увеличивают на 1: a 000, b 001, c 010, d 011, ab 100. Следующее 2-буквенное сочетание распознается. Для каждой буквы было 2-битное описание. На последовательность требуется 2 * 2 = 4 бита. При замене последовательности 3-битным кодом экономим 1 бит на каждом появлении последовательности. Типичный коэффициент сжатия для метода 3 : 1. Изображения с повторяющимися цветными узорами сжимаются до 10 : 1. Отсканированные фотографии и изображения, не содержащие узоров, сжимаются плохо.

4. Арифметическое сжатие

Подобно алгоритму Хаффмана при арифметическом сжатии используются короткие коды для часто повторяющихся участков, более длинные коды для редко повторяющихся. Подобно LZW сжимаются последовательности. Идея: состоит в том, что каждая последовательность пикселов отображается в диапазон чисел между 0 и 1. Эта область затем представляется как двоичная дробь переменной точности. Учитываются вероятностные характеристики изображения. Существует несколько алгоритмов арифметического сжатия. В зависимости от характеристик исходного файла и точности используемой статистической модели можно достичь сжатия 100:1.

5. Сжатие с потерями

Сжатие с потерями используется в телевизионной рекламе, компьютерных играх, анимации. Здесь некоторый аспект исходных данных теряется (отбрасывается). Отбрасывается то, что, например, по телевидению не воспринимается глазом. В основном отбрасывается информация о цветовых оттенках. В критичных приложениях, например, в медицине, метод не используется. Наиболее распространен алгоритм сжатия JPEG. Этот формат придуман Объединенной группой экспертов по фотографии (Joint Photographic Experts Group), файлы в DOS имеют расширение .jpg. Метод лучше всего работает с изображениями фотографического качества. Алгоритм начинается с разделения информации на цвет и яркость. Анализируются группы пикселов (например, квадраты 9х9 пикселов) и определяется разница между ними. Фиксируется информация не о пикселах как единицах изображения, а о динамике изменения их цвета и яркости. Для получения этой информации используется специальный математический аппарат. Сжатие с потерями приводит к тому, что резкие линии выглядят слегка размытыми, в областях однотонной окраски появляются переливы. Т.к. эти эффекты присутствуют и на реальных фотографиях, указанный эффект не заметен. Размеры сжатого файла могут составлять менее 5% исходного.


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

Можно насчитать около 50 различных графических форматов. Рассмотрим только наиболее известные.

1. PCX

Формат растровый, один из самых старых и распространенных, хотя и не признанный в качестве официального стандарта. Первоначально использовался в программе Paintbrush фирмы Zsoft. Расширение в DOS *.pcx. Поддерживается почти всеми программами растровой графики. Имеет много версий (около 5). Поэтому современная версия для 24-разрядного цветового режима не воспринимается старыми программами. Существуют версии для 1-2-4-8-24-битового цвета. Изображения могут быть монохромными, с палитрами цветов или с полными 24-битовыми цветами RGB. Оттенки серого не воспроизводятся, шкалы для отображения оттенков серого в формате нет. Формат аппаратно зависим (EGA, VGA). В основном новые версии выпускались в связи с появлением новых адаптеров. Используется сжатие методом RLE (групповое сжатие). За счет этого размер файла уменьшается на 40-70% для 16 и менее цветов, на 10-30% для 256 цветов. Сжатие используется всегда.

Файл формата PCX содержит 3 части: заголовок, растровые данные и (в более поздних версиях) палитру с количеством цветов до 256. В заголовке 128 байт. Там записаны номер версии, информация о разрешении (в dpi) отпечатанного или отсканированного изображения, информация о размерах (в пикселах), числе байтов на строку развертки, количестве битов на пиксел и количестве цветовых плоскостей. В заголовке может быть информация о наличии палитры и код, указывающий на то, какая палитра используется. В ранних версиях для 4-и 16-цветных изображений информация о палитре была в заголовке. Это порождает несовместимость.

Формат целесообразно применять для нефотореалистических изображений (фотореалистические изображения плохо сжимаются). Основное достоинство широкая распространенность. Ограничения и недостатки:

  •  цветовая палитра до 256 цветов;
  •  не поддерживаются изображения с оттенками серого;
  •  не поддерживаются цвета CMYK и другие системы цветов, отличные от RGB;
  •  размер изображения до 64000  64000 пикселов;
  •  многообразие вариантов порождает проблемы считывания (воспроизведения);
  •  групповое сжатие неэффективно для изображений, полученных при помощи сканера или видео, размер файла может даже увеличиться;
  •  формат поддерживается только на PC-платформе, не поддерживается на Macintosh и в UNIX. Это самый распространенный PC-формат.

2. GIF

Формат растровый. GIF Graphics Image Format. Он был предложен для сети Compuserve, по которой обмениваются различной информацией, в том числе в большом объеме графическими файлами. Расширение для DOS *.gif. Понимается почти всеми растровыми редакторами, большинством издательских пакетов, векторными редакторами, поддерживающими растровые объекты. Для сжатия используется алгоритм LZW.

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

Файл формата GIF состоит из последовательности блоков. Блок заголовка (6 байт) хранит тип файла (GIF) и версию (87а или 89а). Блок дескриптора логического экрана (LSD logical screen device) описывает область устройства (дисплей или принтер) для вывода следующего за ним изображения (или изображений файлы GIF могут хранить несколько изображений, идущих последовательно как слайды). Указывается в пикселах ширина и высота логического экрана для вывода изображений, цвет фона (цвет логического экрана), будет ли для вывода изображения использована глобальная (единая для всех изображений) таблица цветов, коэффициент прямоугольности (ширина и высота) пикселов начального изображения. Блок дескриптора изображения задает размеры изображения и его позицию на логическом экране (относительно левого верхнего угла) и информирует, будет ли использоваться локальная таблица цветов. Таких блоков может быть 1 или более. Файл содержит по крайней мере 1 таблицу цветов. Она может быть глобальной (единственной) и/или локальной (несколько таблиц). После всей служебной информации следует сжатый методом LZW блок данных изображения. Завершает файл блок концевика, который носит только индикаторный характер. Последняя версия (89а) имеет расширения, позволяющие добавлять к рисунку текст аннотации. Причем можно сделать аннотацию как отображаемую на экране, так и не отображаемую. Этот блок размещается (если он есть) перед данными.

Файлы GIF компактны. Их достоинство многоплатформность, свободное распространение, возможность хранения множественных изображений, сочетания изображений и текста. Ограничения и недостатки:

  •  24-битный цвет поддерживает только до 256 цветов;
  •  отсутствует возможность сохранения градаций серого;
  •  не поддерживается система цветов CMYK;
  •  размер изображения до 64К  64К пикселов.

3. TIFF

Формат растровый. TIFF (Tagged Image File Format) дословно переводится как формат файла помеченного изображения. Формат является результатом объединения усилий компаний Aldus и Microsoft, направленных на преодоление трудностей переноса графических файлов между IBM-совместимыми компьютерами и Macintosh. Формат работает также в UNIX-системах. Появление TIFF положило также конец некоторому беспорядку в области программного обеспечения для сканеров.

Существует 5 типов TIFF-файлов: B  черно-белые иллюстрации, F  изображения для факсов, G  полутоновые изображения (каждая точка может быть любой степени серого от 0% белый цвет, до 100% черный), P цветные изображения, использующие собственную цветовую палитру, R  фотореалистические изображения в RGB-представлении. Имеются "диалекты" формата, что создает трудности его понимания различными программами. Сейчас используются версии 5.0 и 6.0. Расширение для DOS *.tif.

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

Формат очень удобен, но файлы велики. Например, файл формата А4 в цветовой модели CMYK (собственная цветовая палитра!) с разрешением 300 dpi занимает около 40 М. А это обычные параметры высококачественной печати. Достоинством являются надежность, большие возможности. Это лучший растровый формат обмена между Macintosh и PC. С той или иной степенью детализации он "понимается" множеством программ. Можно использовать различные методы сжатия. Метод сжатия указывается в одном из полей. Можно работать с оттенками серого. Универсальность формата порождает его основной недостаток: неупорядоченность структуры и вытекающую из этого несовместимость.

4. JPEG

Joint Photographic Expert Group (JPEG) формат объединенной группы экспертов по фотографии. Это объединение действует под эгидой ISO (ведущей международной организации стандартов) и CCITT (организации стандартов в области телефонии, радио, телевидения и т.д.). Формат дает наилучшее сжатие для фотографических (растровых) изображений. Расширение для DOS *.jpg или *.jif (JPEG+TIFF). Последняя версия 1991 г. Формат еще не устоялся, есть ранние, не совместимые с другими реализации. JPEG “понимается” рядом графических редакторов. Это не столько формат, сколько метод сжатия. Он реализован программно на PC, Macintosh и аппаратно (это наиболее эффективно, есть специальные чипы). Программное сжатие работает гораздо медленнее аппаратного. Возможно сжатие до десятых долей исходного файла (до 100:1). Такой результат получается за счет сжатия с потерями. Но теряется то, что для глаза незаметно. Существует формат JPEG+TIFF (TIFF 6.0), допускающий сжатие JPEG. Имеется также формат JFIF. Это вариации JPEG.

Рассмотрим основные этапы сжатия. Большинство реализаций JPEG сначала преобразуют систему цветов RGB в YUV (Y яркость, U и V характеристики цвета). Т.к. человеческий глаз больше воспринимает изменение яркости, нежели изменение цвета, программа сжатия больше внимания уделяет данным о яркости. На одну выборку цвета делается от 2 до 4 выборок яркости. Это источник экономии. Далее выполняется дискретное преобразование массива данных об интенсивности в массив данных о частоте изменения интенсивности. После ряда частотных преобразований используется модифицированное кодирование методом Хаффмана.

5. DXF

DXF Drawing Interchange Format. Это формат обмена рисунками AutoCAD фирмы AutoDesk. Формат векторный. “Понимается” большинством САПР, Corel Draw, издательскими системами. Стандарт "де факто" для обмена чертежами. Позволяет отобразить от черно-белого до 16 млн. цветов. В основном для PC, есть реализации на Macintosh, UNIX. Основа язык графических метафайлов. Это означает, что хранится не само изображение, а его описание. AutoCAD использует плавающую арифметику. Это позволяет выполнять очень точные вычисления. Но большинство векторных редакторов применяет только целочисленную арифметику. Это порождает потерю информации, искажение рисунка. Степень искажения зависит от вида работы.

Формат имеет 2 формы: ASCII и бинарную. Бинарная форма появилась в версии 10. Цифровые коды и данные хранятся не в ASCII, а в двоичном виде. При этом размер файла уменьшается примерно на 25%, скорость чтения увеличивается в 5 раз, но теряется возможность визуальной расшифровки формата.

Объекты в файле DXF задаются парами величин: кодами групп и следующими за ними значениями групп. Коды указывают цель использования значений. Данные внутри файла разделены на 4 секции. Секция заголовка содержит общую информацию: цвет, толщина линий по умолчанию, размеры рисунка и т.д. Эти сведения обычно игнорируются системами, отличными от САПР (векторными редакторами, издательскими системами и др.). Секция таблиц содержит данные о координатных системах и слоях объектов. Они тоже, в основном, используются САПР. В секции блоков векторные объекты группируются по именам. Секция элементов содержит описания всех геометрических объектов. Это самая большая часть файла. Примеры элементов: POINT, LINE, CIRCLE, 3DFACE, TEXT и др. Описываются объекты числовыми и ASCII или двоичными кодами. Сначала указывается код элемента, потом код слоя, цвет и др. характеристики, затем параметры элемента.

Достоинства: распространенность, широкая цветовая палитра, возможность описания трехмерных изображений. Недостатки: неэффективность хранения данных, ASCII-форма медленно читается. Полная реализация стандарта очень сложна, особенно для трехмерных изображений.

6. Базовая графика PostScript

Это стандарт de facto для настольных издательских систем. Изначально формат предназначался для компьютеров Macintosh и их периферии (принтеров и других устройств вывода). Сейчас он используется на PC- и UNIX-платформах как для вывода, так и для хранения и передачи изображений, особенно в формате инкапсулированного PostScript (Encapsulated PostScript  EPS). Тип изображения векторное и bitmap (векторное и растровое). По типу формата PostScript относится к языкам описания страниц. EPS  подмножество языка Adobe PostScript, владельцем которого является Adobe Systemc Inc. Файлы в DOS имеют расширение *.eps.

 Базовая графика PostScript имеет 4 варианта: Level 1, Level 2, Encapsulated PostScript, Display PostScript. Level 1 исходное подмножество языка. Используется, в основном, для черно-белой графики до 8 бит глубиной. Может также работать в RGB и CMYK. Level 2 включает Level 1 и ряд усовершенствований. Используются различные методы сжатия, колориметрия. Глубина цвета до 32 бит. Вместо ASCII-кода можно использовать бинарный код. EPS описывает одну страницу, которая без модификации включается в большие PostScript-документы. В основном используется для обмена. Допускает 24-битные RGB и HSB, 32-битный CMYK, индексирование палитры цветов. EPS “понимается” большинством издательских систем. Интерпретаторы Display PostScript являются аппаратно-независимыми интерфейсами для мониторов в режиме реального времени. Они поддерживают многозадачность, окна и т.д.

 PostScript по сути является языком программирования. Он похож на язык программирования FORT. PostScript очень детализирован, из-за чего интерпретатор занимает большой объем памяти. Руководство по 2 редакции языка содержит более 700 страниц. PostScript позволяет описать документы в сотни страниц с включением в текст рисунков и установок для печати. Имеются средства эскизного просмотра, линейого преобразования изображений (в том числе векторных шрифтов). Можно получить до 12 разрядов глубины серого, 36-битовый RGB. Язык имеет большие возможности, прекрасно служит для согласования различных платформ при цветных и черно-белых изображениях. Для bitmap-изображений он обычно неэффективен. К недостаткам следует отнести жесткую ориентацию языка на принтеры PostScript. Для других принтеров на месте изображения печатается пустая рамка.


Разбиение картинной плоскости

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

Оценим выгоду. При прямом переборе оценка количества операций O(N2), при разбиении - O(N). Однако, требуется память для хранения информации о клетках, в которые попадает проекция ребра.

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

•  область пуста (в нее не попадает ни одной проекции), следовательно она закрашивается цветом фона;

•  область целиком занята проекцией одной грани, следовательно она закрашивается цветом грани;

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

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

МЕТОДОД ДВОИЧНОГО РАЗБИЕНИЯ ПРОСТРАНСТВА 

В основе - известный прием дихотомии (половинного деления). Пространство делится плоскостью на два полупространства. Далее используется исходная эвристика №2 (п. 6.5.1). Внутри каждого полупространства разбиение повторяется. Можно также секущую плоскость провес через произвольно выбранную грань (модификация алгоритма). Фактически строится двоичное дерево, узла! которого являются грани. Древовидные структуры достаточно легко программируются с помощью списков объектно-ориентированного подхода. Объект - грань, методы - различные виды прохода по дереву (получить следующий выше/нижележащий элемент, получить следующий элемент на том же уровне соседней ветви и т.д

Как выбрать грани для разбиения? Существует два основных критерия:

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

• минимизировать количество разбиений.

Эти критерии обычно являются взаимно исключающими, требуется компромисс.

Алгоритм работает в объектном пространстве. Его сильная сторона - независимость от положения центра проектирования (точки наблюдения). Одну и ту же сцену можно перерисовывать для разных точек наблюдение

К методам упорядочения относится также МЕТОД ПЛАВАЮЩЕГО ГОРИЗОНТА. В отличие от вышеизложенных, в этом методе сначала выводятся ближние к наблюдателю фрагменты. Пусть требуется получи каркасное изображение гладкой поверхности. Для изображения проекции ребра на картинную плоскость и пользуется растровый алгоритм, например, алгоритм Брезенхейма. При выводе очередной точки проекции видимость анализируется с учетом нижней и верхней границ уже полученной части изображения. Эти границы и зывают соответственно нижним и верхним плавающим горизонтом, т.к. в процессе работы алгоритма их пол жение меняется. Горизонты можно представить как 2 целочисленных массива. В процессе работы изображения достраивается вне области, где оно уже построено.

 


НАИБОЛЕЕ РАСПРОСТРАНЕННЫЕ ГРАФИЧЕСКИЕ ФОРМАТЫ

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

Растровый способ используется обычно в программном обеспечении сканеров и в программах редактирования фотореалистических изображений. Растровый файл состоит из точек, число которых определяется разрешением. Разрешение измеряется в количестве точек на дюйм (dpi) или на сантиметр (dpc). Эта метрика используется как для дисплея, так и для других устройств вывода, например, принтеров. Очень важным фактором, влияющим на качество изображения, является глубина цвета, т.е. число разрядов, отводимых для хранения информации об оттенках (градациях) 3 основных цветов (RGB). Так, глубина 24 разряда дает 16777216 цветов (24=3*4=2**24). Для полутонового нецветного изображения хранятся оттенки черного.

Плата за высокую глубину - большой размер файлов растровой графики. Размер файла сильно зависит от выбранного формата хранения. При прочих равных условиях (размеры изображения и битовая глубина) рисунок формата TIFF может быть в 2 раза меньше формата EPS или в 2 раза больше PCX. В некоторых форматах применяются особые схемы сжатия, сильно уменьшающие размер файла. Файлы могут содержать дополнительную информацию, обеспечивающую предварительный просмотр изображения. Достоинство растровой графики - реалистичность изображения, соответствие устройствам вывода (принтеры). Недостаток - большие затраты дисковой памяти, хотя дисковая память экономится за счет сжатия. Но т.к. алгоритмы сжатия у разных пакетов разные, возникает проблема ''непонимания" изображений другими программами.

Векторный способ записи изображений применяется обычно в системах автоматизированного проектирования и пакетах для построения графических изображений (рисовалках). Изображение состоит из простейших элементов (прямая, ломаная, кривая Безье, эллипс, прямоугольник' и т.д.), называемых графическими примитивами. В графической библиотеке BGI реализован векторный способ. Для каждого из примитивов определен ряд атрибутов (например, для многоугольников задаются координаты вершин, толщина и цвет контурной линии, тип и цвет заливки и т.д.). Записывают также место объектов на странице и их взаимное расположение. Векторный формат - доказательство идеи древнегреческих математиков, что любую существующую в природе форму можно описать с помощью геометрических примитивов и компаса. Векторная графика использует математические формулы описания объекта и комбинацию команд манипулирования объектами. Местоположение точек ВЫЧИСЛЯЕТСЯ. Векторную графику часто называют объектно-ориентированной или чертежной. Некоторые векторные форматы очень просты, содержат несколько десятков команд. В других форматах число команд сотни и тысячи. Команды могут представляться в коде ASCII, в двоичном коде, и др.

Достоинство векторного представления - экономичность по памяти, т.к. не нужно запоминать каждую точку. Хранится АЛГОРИТМ получения изображения, а не само изображение. В растровых форматах хранится цвет каждого пиксела, что ведет к трате памяти. В векторных форматах хранится цвет объекта в целом. При редактировании векторных изображений манипулируют объектами (примитивами или их совокупностью, выделенной по некоторому критерию). Это позволяет работать с частями рисунка, выводить его по частям, просматривать послойно. Последнее реализовано, например, в системе автоматизации проектирования многослойных печатных плат PCAD, приложениях, написанных в среде AutoCAD для архитектурно-стоительного проектирования и др. Самая сильная сторона векторной графики - максимальное использование разрешающей способности устройства вывода без изменения рисунка. Векторные команды просто требуют нарисовать объект заданного размера. Количество точек, использованное при этом. определяется устройством. В растровом формате рисование ведется по точкам и если точек мало, то на хорошем принтере получается плохой рисунок. По той же причине изменение размеров не воняет на качество вывода векторного изображения. Для растрового изображения при увеличении появляется зернистость, т.к. точек не хватает. Недостаток векторной графики - сложность изображения больших многообъектных сцен. Возникают трудности получения сложных изображений (например, кривых), т.к. набор исходных примитивов может быть недостаточным. Тогда приходится создавать стилизованные изображения. Не все устройства могут реализовать и все требуемые векторные команды.

Т.к. точка - тоже графический примитив, векторные рисунки мог\т содержать растровые вставки. Но возможности их редактирования в большинстве программных пакетов ограничены. Растровые рисунки воспринимаются как объект, поэтому исполняются только команды, относящиеся к рисунку в целом (уменьшить/увеличить яркость, изменить размер рисунка - каждый пиксел представляется несколькими точками). Яркий пример такого подхода - вставка рисунков в текст, подготовленный в редакторе Microsoft Word. Есть программы (в основном на Macintosh), позволяющие работать с обоими типами рисунков. Они создают 2 разных слоя. Некоторые векторные форматы позволяют создавать растровый эскиз изображения, который за счет увеличения размера файла хранится вместе с векторным описанием. За счет этого, например, в издательских пакетах типа PageMaker можно выполнить эскизный просмотр рисунка или страницы, куда вставлен рисунок.

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

* * *

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

  •  линейные изображения (растровые образы линий);
  •  сплошные объекты (растровые области двумерных областей);
  •  шрифты;
  •  изображения (прямоугольные матрицы пикселов).

Любой современный компилятор имеет графическую библиотеку, поддерживающую указанные объекты. Такая библиотека должна обеспечивать работу с основными типами видеоадаптеров. Этого можно достичь несколькими путями. Во-первых, можно написать версии библиотеки для всех основных типов адаптеров. Кроме трудоемкости такой работы и громоздкости полученного компилятора использование конкретной библиотеки привяжет программу к определенному типу видеоадаптера, т.е. сузит ее независимость. Принцип совместимости видеоадаптеров здесь помогает мало, т.к. программа, написанная, например, для CGA, будет работать на VGA, но без полного использования всех его возможностей Эта программа так и останется CGA-шной. Другой путь -включить в библиотеку версии процедур для всех основных типов видеоадаптеров. Это увеличивает машино-независимость. Но нельзя исключить наличия у пользователя видеоадаптера, не поддерживаемого библиотекой. Самым главным недостатком такого подходя является очень большой размер исполняемого файла

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


Закрашивание. Световые эффекты. Общие сведения

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

•  форма и направление источника света;

• ориентация освещаемой поверхности;

• свойства (материал) поверхности;

• рассеянный (отраженный) от других объектов свет.

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

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

I=I1*kd *cos , 0<=<=/2 (1)

где  I1  - интенсивность точечного источника;

       I  - интенсивность отраженного света;

       kd  - коэффициент диффузного отражения

 - угол между направлением источника света и внешней нормалью к поверхности.

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

I=Ia*ka*kd*cos (2)

I  - интенсивность рассеянного света;

ka  - коэффициент диффузного отражения рассеянного света

Имеется также не очень сложная формула для учета расстояния между объектом и источником света:

I=Ia*ka+I1*kd/(d+K)*cos  (3), где 

d  - расстояние;

K  - произвольная постоянная, ее определение в литературе не описано.

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

Is =I1 * ks * cosp a (4), где     

k  - экспериментальная постоянная;

а  - угол между отраженным лучом и вектором наблюдения;

р - степень, аппроксимирующая пространственное распределение света.

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

I=Ia•ka+(I1/d+K)*(kd+cos +ks*cos pa) (5)

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

I=Ia•ka+(I1/d+K)*(kd+cos j+ks*cos pjaj) (6) j=1¸m

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

Для гладких k-многогранных фигур используются разные приемы построения векторов и отыскания углов. А как рассчитать освещенность в вершине многогранника? Здесь при отыскании углов возникает проблема выбора нормали.

Часто в качестве нормали используется нормированная сумма нормалей прилегающих граней:

 a1*n1 + ... +ai*ni

    n     =         —————————

|  a1*n1 + ... +ai*ni |

где    ai - произвольные весовые коэффициенты.

Для ребра используется сумма нормалей двух прилегающих граней.

Как применить формулы на практике? Известно, что cos 0 = 1. Следовательно, непосредственно под точечным источником располагается светлое пятно. В пределе оно белое, добавляется поправка на влияние другие источников. При увеличении угла косинус уменьшается, окраска становится более интенсивной. Возникает проблема дискретизации по углу и сопоставления каждому значению угла определенного количества пикселов.

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


 

А также другие работы, которые могут Вас заинтересовать

27565. Теория и практика формирования правового государства в России 29.5 KB
  Теория правового государства насчитывает многовековую историю. Многие мыслители начиная с античной древности и вплоть до наших дней занимаются проблемой создания рационального государства которое отвечало бы представлениям людей о свободе и справедливости законности и демократии. В числе ученых философов и правоведов принимавших участие в выработке и обосновании теории правового государства необходимо упомянуть Аристотеля Платона Полибия Ш.
27566. Типология государств (Кельзена, Еллинека) 27.5 KB
  Типология государств Кельзена Еллинека. Типология государства – традиционно рассматривают как теория учение о типах государств когдалибо существовавших в истории человеческого общества или существующих в настоящее время. Типология государства – это процесс систематизации государств с учетом их сущностных свойств для повышения эффективности в теоретической и практической деятельности по изучению государства и правоприменения. Под типом государства понимаются взятые в единстве общие черты различных государств система их важнейших...
27567. Типология государства: формационный подход 31 KB
  Типология государства: формационный подход. Типология государства – традиционно рассматривают как теория учение о типах государств когдалибо существовавших в истории человеческого общества или существующих в настоящее время. Типология государства – это процесс систематизации государств с учетом их сущностных свойств для повышения эффективности в теоретической и практической деятельности по изучению государства и правоприменения. Тип государства и права ставится в зависимость от типа общественноэкономической формации.
27568. Тоталитаризм в системе антидемократических политических режимов 24.5 KB
  Тоталитаризм в системе антидемократических политических режимов. Государственнополитический режим это элемент формы государства характеризующий совокупность приемов методов способов и средств осуществления государственной власти. В научной литературе большинство авторов выделяют два вида политического режима: демократический и антидемократический. Антидемократический политический режим представляет собой противоположность демократическому и характеризуется отсутствием демократических прав и свобод; запретом деятельности политических...
27569. Укажите, какие из перечисленных событий и действий являются юридическими фактами (солнечное затмение, назначение на должность, создание литературного произведения) 26.5 KB
  Юридические факты это конкретные жизненные обстоятельства с которыми норма права связывает возникновение изменение и прекращение правоотношений. Виды ЮФ: По последствиям: правообразующие влекут возникновение правоотношений; правоизменяющие влекут изменение правоотношений; правопрекращающие влекут прекращение правоотношений. По форме проявления: положительные обстоятельства требующие их наличия для возникновения правоотношений; отрицательные обстоятельства требующие их отсутствия для возникновения правоотношений.
27570. Укажите, что является основанием деления права на отрасли 26 KB
  В основе деления права на отрасли лежат предмет и метод правового регулирования. Каждая отрасль права регламентирует свой особый участок сферу общественных отношений однопорядкового характера однородных своеобразие которых позволяет отличать одну отрасль права от другой. Но предмет правового регулирования не может быть единственным критерием деления права на отрасли так как общественные отношения разнообразны и часто одни и те же общественные отношения регулируются различными отраслями и способами.
27571. Федерация как особая форма государственного устройства 23.5 KB
  Федерация как особая форма государственного устройства. Форма государственного устройства – территориальная организация государственной власти или иными словами внутреннее строение государства деление его на составные части. По форме государственного устройства государства могут быть простыми и сложными.
27572. Форма государственного устройства 26 KB
  Форма государственного устройства – территориальная организация государственной власти или иными словами внутреннее строение государства деление его на составные части. По форме государственного устройства государства могут быть простыми и сложными. 1 Простые государства называют унитарными так как его составные части являются простыми административнотерриториальными единицами не обладающими суверенитетом. 2 Сложные государства представляют собой союз государств или состоят из обособленных государственных образований.
27573. Множественность преступлений, понятие и виды. Её отличие от продолжаемых и длящихся преступлений 29.5 KB
  Множественность преступлений понятие и виды. Её отличие от продолжаемых и длящихся преступлений. Множественность преступлений это совершение лицом двух или более преступлений независимо от того осуждалось ли лицо за предыдущие преступления. Признаки множественности: одно лицо совершает два или более преступлений; каждое из деяний должно быть установлено судом в приговоре; преступление не должно быть погашено сроком давности уголовной ответственности ст.