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

Экзаменационные билеты по предмету «Информатика»
Информация о работе
  • Тема: Вопросы для экзамена по курсу "Компьютерная графика" (1-20 с ответами)
  • Количество скачиваний: 132
  • Тип: Экзаменационные билеты
  • Предмет: Информатика
  • Количество страниц: 38
  • Язык работы: Русский язык
  • Дата загрузки: 2014-09-21 18:30:48
  • Размер файла: 278.47 кб
Помогла работа? Поделись ссылкой
Ссылка на страницу (выберите нужный вариант)
  • Вопросы для экзамена по курсу "Компьютерная графика" (1-20 с ответами) [Электронный ресурс]. – URL: https://www.sesiya.ru/ekzamenacionnye-bilety/informatika/voprosy-dlya-ekzamena-po-kursu-kompyuternaya-grafika-1-20-s-otvetami/ (дата обращения: 03.08.2021).
  • Вопросы для экзамена по курсу "Компьютерная графика" (1-20 с ответами) // https://www.sesiya.ru/ekzamenacionnye-bilety/informatika/voprosy-dlya-ekzamena-po-kursu-kompyuternaya-grafika-1-20-s-otvetami/.
Есть ненужная работа?

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

добавить работу
Обратиться за помощью в подготовке работы

Заполнение формы не обязывает Вас к заказу

Информация о документе

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

Если Вы являетесь автором текста представленного на данной странице и не хотите чтобы он был размешён на нашем сайте напишите об этом перейдя по ссылке: «Правообладателям»

Можно ли скачать документ с работой

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

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

1. Технические средства ввода графической информации.
2. Технические средства получения твердой копии графической информации.
3. Дисплей как техническое средство компьютерной графики.
4. Векторная и растровая графика: суть, отличия, области применения.
5. Мировые координаты, нормированные координаты, координаты устройства,
функция кадрирования.
6. Понятие графического примитива. Наиболее распространенные графические примитивы и
операции над ними.
7. Основные отличия текстового и графического режима видеоадаптера.
8. Чем отличаются с точки зрения машинной графики видеоадаптеры EGA,VGA,SVGA,MGA.
9. Особенности представления цвета в видеоадаптерах EGA и VGA.
10. Как программно осуществляется управление принтером.
11. Основные отличия в подходах MS DOS и WINDOWS при разработке графических приложений.
12. Основные этапы преобразования и модели, используемые при переходе от изображений
реального мира к компьютерным.
13. Основные этапы растр-векторного преобразования графических объектов.
14. Понятие аффинных преобразований и их прикладное значение для задач компьютерной графики.
15. Элементарные аффинные преобразования на плоскости, составляющие базис операций
машинной графики.
16. Понятие и прикладное значение однородных координат.
17. Элементарные аффинные преобразования в пространстве, составляющие базис операций
машинной графики.
18. Основные виды проекций и соответствующие им аффинные преобразования.
19. Геометрические сплайны.
20. Алгоритм Брезенхема.





















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]). Для создания собственного курсора полезна таблица взаимодействия масок:
Следует обратить внимание на рациональную реализацию обработки событий от мыши. Не требуете; все время опрашивать драйвер мыши. Ему передается адрес функции, которую следует вызвать при наступлении заданного события. Первый параметр - указатель на функцию, второй параметр - маска событий. События соединяются побитовой операцией ИЛИ. Функция, которая обрабатывает событие, получает маску вызывающего события, маску состояния кнопок мыши. координаты курсора мыши.

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 Синий, красный, зеленый Высокая Высокая
Средняя
Низкая
68h – Afh Высокая Средняя
Средняя
Низкая
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 раза меньше).
Все это также представимо в матричном виде.



Так, при проектировании на плоскость ху точки с
координатами х=0, у=0, z=l имеем (0 0 1 l) -> (a b 0 l).
Вид матрицы;

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

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


Из школьного курса черчения и курса начертательной геометрии известно, что по нескольким проекци¬ям можно восстановить изображение. Для компьютерной графики это соответствует обратным матричным пре¬образованиям. Т.к. для восстановления изображения используются несколько проекций, преобразования весьма сложны и длительны. Этим объясняется высокая ресурсоемкость подобных задач.
Как все это реализовать (запрограммировать)? Здесь удобно использовать объектно-ориентированный подход. Фактически, мы работаем с векторами, т.к. координаты точки - 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 равенств. Недостающие граничные условия можно получить, задав, например, значения первых производных на концах интервала x0и xm. Могут быть и граничные условия других типов. Таким образом, для определения коэффициентов решается система линейных уравнений.
Для изображений в пространстве нужно построить поверхность, проходящую через данные точки пространства. Используется функция 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 переменные х и у меняются местами.