Пугачев А.И

Самара

Курс лекций

ОСНОВЫ КомпьютернОЙ графикИ

А. И. Пугачев

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

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ «САМАРСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ»

Кафедра «Вычислительная техника»

А.И. ПугачЕв

Основы
компьютерной графики

Курс лекций

Самара

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

Печатается по решению редакционно-издательского совета СамГТУ

УДК 681.3

П 88

П 88 Основы компьютерной графики: курс лекций/ А.И. Пугачев. – Самара: Самар. гос. техн. ун-т, 2011. – 104 с.: ил.

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

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

Рецензент: д-р техн. наук В.А. Митрошин

УДК 681.3

П 88

Ó А.И. Пугачев, 2011

Ó Самарский государственный
технический университет, 2011

Введение

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

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

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

Кроме синтеза и визуализации двумерных и трехмерных объектов предметом компьютерной графики также являются оцифровка готовых изображений, полученных в аналоговой форме (печатные, фото– и киноматериалы), а также различные виды обработки цифровых изображений [2]. Типичные операции обработки – трансформация изображений, цветовая коррекция, фильтрация, комбинирование нескольких изображений в одно и т.п. Разрабатываемые в компьютерной графике методы обработки изображений используются в самых разных областях: полиграфии, производстве видеопродукции, в системах распознавания образов.

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

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

Лекция 1. РАСТРОВЫЕ ИЗОБРАЖЕНИЯ И ТЕХНИЧЕСКИЕ средства компьютерной графики

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

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

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

Из сказаного следует, что наиболее важными характеристиками изображения являются:

- разрешающая способность, т.е. количество элементов по горизонтали и вертикали;

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

- цветовая модель, т.е. способ кодирования цветов.

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

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

Типичные значения разрешающей способности современных мониторов 1280x1024, 1920х1080 и выше. Основной цветовой моделью графических устройств служит модель RGB, в которой каждый цвет образуется смешиванием трех основных цветов; красного (red), зеленого (green) и синего (blue). В наиболее популярном формате TrueColor этой модели цвета в изображениях кодируются тремя байтами – по одному байту на каждую составляющую R, G и B.

Для хранения растровых изображений используются файлы различных форматов. Файлы наиболее распространенных форматов имеют расширения BMP, GIF, JPG, TIF, PNG [1].

Формат BMP (BMP – сокращение от bitmap) разработан фирмой Microsoft для операционных систем Windows. В этом формате изображение может храниться без сжатия или со сжатием. Цвета могут кодироваться с помощью 256-цветной палитры, которая в этом случае записывается в файл или в формате TrueColor. Чаще используют BMP-формат без сжатия. В этом формате размер файла значительно больше, чем со сжатием, но зато вывод изображения из него на монитор выполняется с максимальной скоростью, так как не требуется использовать сложные алгоритмы декодирования. Многие системы программирования и приложения Windows имеют функции для записи и вывода BMP-изображений.

Формат GIF (Graphics Interchange Format) разработан в 1987 г. фирмой CompuServe как экономичный вариант хранения изображений со сжатием. Цвета кодируются с помощью 256-цветной палитры. В GIF-файле может храниться несколько кадров изображения. В настоящее время GIF используется практически на всех платформах и стал стандартным форматом изображений в оформлении Web-страниц.

Формат JPG разработан Объединенной группой экспертов по фотографии (Joint Photographic Experts Group – JPEG). В этом формате графические данные записываются со сжатием и потерями. Степень сжатия и соответственно степень потерь можно задавать при записи. Это самый популярный формат для хранения фотографических изображений. В большинстве цифровых фотоаппаратов фотографии сохраняются в формате JPG.

Формат TIF (Tagged Image File Format – TIFF) также использует сжатие. В этом формате оно основано на применении тегов различных видов. В тегах размещается как общая информация, так и данные по отдельным элементам изображения. Количество видов тегов составляет несколько десятков. Сжатие производится без потерь, поэтому TIFF достаточно широко используется, в первую очередь, в издательских системах, требующих изображения наилучшего качества.

Формат PNG (Portable Network Graphics) разработан сравнительно недавно и ориентирован специально на Web в качестве замены GIF-формата. В отличие от GIF поддерживает кодирование цветов до 48 бит на пиксель. Использует сжатие без потерь. Кроме того, данный формат предоставляет ряд новых полезных возможностей, таких, как альфа-каналы (возможность плавно задавать прозрачность пикселей), гамма-коррекция (межплатформенное управление контрастностью изображения), возможность чересстрочной развертки при выводе изображения.

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

1.2. Графические устройства ввода-вывода

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

- мониторы (дисплеи);

- принтеры;

- плоттеры;

- сканеры;

- цифровые фотоаппараты;

- дигитайзеры.

Как уже отмечалось, мониторы – самые распространённые устройства вывода растровых изображений. Изображение в растровых мониторах формируется из строк пикселей, образующих матрицу с координатной адресацией по осям X и Y. Особенность экранной системы координат в том, что ось OY направлена вниз.

По принципу действия мониторы можно разделить на следующие остновные виды:

- с электронно-лучевой трубкой (ЭЛТ, CRT – cathode ray tube);

- плазменные (PDP – Plasma Display Panels);

- жидкокристаллические (ЖК, LCD – Liquid Crystal Display).

Мониторы с ЭЛТ уже становятся прошлым. Плазменные панели, как и жидкокристаллические, широко используются в телевизорах, однако подавляющая часть современных мониторов для персональных компьютеров жидкокрисаллические.

В LCD-дисплеях используются ЖК-панель, имеющая многослойную структуру, в которой главную роль играют две стеклянные подложки и находящийся между ними слой жидких кристаллов с молекулами стержневидной формы. На подложках нанесены параллельные бороздки. Бороздки двух подложек ортогональны друг к другу, и на пересечении бороздок образуются ячейки, соответствующие пикселям. Бороздки создают первначальную ориентацию молекул кристалла, соприкасающихся с ними. При этом продольные оси молекул самого верхнего слоя жидких кристаллов будут расположены под прямым углом по отношению к осям молекул из нижнего слоя. Ориентация молекул между слоями плавно меняется от одного края к другому. В таком состоянии ячейки прозрачны для света ламп подсветки, расположенных за ЖК-панелью. Степенью прозрачности кристаллов можно управлять, меняя плоскость поляризации молекул за счет электрического напряжения, подаваемого на кристаллы. В качестве управляющих элементов используются тонкопленочные транзисторы (TFT – Thin Film Transistor), образующие матрицу из строк и столбцов соответственно ячейкам экрана.

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

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

Количество столбцов и строк в матрице пикселей определяет максимальную разрешающую способность монитора. Как уже говорилось, типичные значения разрешающей способности мониторов составляют 1280x1024, 1920х1080 и выше. Другая характерисика этого же свойства – разрешение монитора [1]. Оно определяет число пикселей на дюйм по горизонтали (или вертикали). Чаще разрешение в обоих направлениях совпадает. Измеряется в единицах, обозначаемых как ppi (pixel per inch). Типичное разрешение современных мониторов при максимальной разрешающей способности развертки достигает 100 ppi.

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

Максимальная яркость изображения на экране монитора в значительной мере определяется подсветкой. Для большинства LCD-мониторов максимальная яркость лежит в пределах 200 – 500 кд/м².

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

Стандартное количество отображаемых цветов составляет 16,7 Млн., что соответствует диапазону значений цветов формата TrueColor.

Максимальный угол обзора определяется как угол, при обзоре с которого контрастность изображения уменьшается в 10 раз. Различают горизонтальный и вертикальный углы обзора. Типовые значения – 170⁰ и 160⁰ соответственно.

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

Хотя в LCD-мониторах используется цифровое управление выводом изображения на дисплей, многие из них имеют аналоговый интерфейс VGA (Video Graphics Array), разработанный еще для мониторов на базе ЭЛТ. В более современных мониторах используются цифровые интерфейсы DVI (Digital Visual Interface) и HDMI (High-Definition Multimedia Interface), обеспечивающие более высокое качество воспроизведения изображения.

Наиболее известными производителями жидкокристаллических мониторов являются фирмы Accer, Samsung, LG, Philips.

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

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

Разрешение принтеров с матричным способом печати указывается в единицах dpi (dot per inch) – точек на дюйм. Обозначает возможность вывода указанного количества мельчайших печатных точек на дюйм. Однако при печати изображений с полутонами каждый пиксель приходится воспроизводить не одной печатной точкой, а квадратной матрицей печатных точек, например матрицей размером 16х16. Типичное разрешение лазерных принтеров составляет от 600х600 до 1200х1200 dpi, струйных – до 4800х1200 dpi и выше.

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

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

Рулонные графопостроители (roll-feed plotter) по принципу действия относятся к растровому типу. В них чертежная головка перемещается в одном направлении, перпендикулярном направлению движения бумаги. Таким образом, изображение строится построчно. Ширина бумаги соответствует формату А1 или А0, а длина рулона может быть несколько десятков метров.

В барабанных плоттерах (drum plotter) носитель изображения закрепляется на вращающемся барабане.

По способу печати растровые плоттеры подразделяются следующим образом:

- электростатические;

- струйные, основанные на принципе струйной печати;

- лазерные;

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

- термические графопостроители (thermal plotter);

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

Разрешение растровых графопостроителей находится в переделах 300 – 2500 dpi.

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

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

- CMOS – Complementary Metal-Oxide-Semiconductor (комплементарный металлооксидный полупроводник (КМОП));

- CCD – Charged Couple Devices (приборы с зарядовой связью (ПЗС)).

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

Основные характеристики фотокамер – емкость матрицы в мегапикселях (10 – 15 МПикс); максимальная разрешающая способность изображения (3648х2736, 4320х3240 и выше).

Сканер – это устройство ввода графической информации главным образом с бумажных носителей. Обычно это бумажные документы и фотографии [1, 7].

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

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

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

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

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

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

1.3. Видеоадаптеры

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

- видеопамять;

- графический процессор (Graphics processing unit, GPU);

- видеоконтроллер;

- цифроаналоговый преобразователь (ЦАП);

- ПЗУ BIOS (Basic Input/Output System) с основными функциями, поддерживающими интерфейс между оборудованием видеоадаптера и программным обеспечением.

Кроме этого, в составе видеоадаптера обычно имеется контроллер внешней шины данных (например, PCI Express x 16), контроллер внутренней шины данных и контроллер видеопамяти. Для повышения производительности графического процессора разрядность внутренней шины и шины видеопамяти расширяют до 64 – 256 разрядов и выше.

Видеопамять необходима для буферизации изображения, формируемого видеоконтроллером. Она представляет собой СОЗУ на базе быстродействующих микросхем статической памяти (SRAM) типов DDR или GDDR емкостью от 0,5 до 2 Гбайт и выше. Каждому пикселю экрана в видеопамяти соответствует ячейка, где хранится код его цвета. В формате TrueColor цвет пикселя кодируется тремя байтами – по одному байту на каждую цветовую составляющую R, G и B. Содержимое видеопамяти периодически с частотой 75 – 100 Гц считывается видеоконтроллером для регенерации изображения на экране монитора.

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

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

Большинство ЦАП видеоадаптеров имеют разрядность 8 бит на каждый основной цвет. Это позволяет воспроизводить до 16,7 млн различных цветов. Разрядность ЦАП более дорогих видеоадаптеров по каждому каналу составляет 10 бит, что дает возможность отображать более 1 млрд цветов.

Быстродействие ЦАП достигает 300 МГц и выше, что позволяет при оптимальных частотах регенерации изображения (75 – 85 Гц и более) поддерживать высокое разрешение на экране монитора. Видеоадаптеры с быстродействием ЦАП от 300 МГц и выше позволяют поддержать разрешающую способность монитора до 1920 х 1200 при частотах регенерации изображения 75 Гц и выше.

Характеристики графической подсистемы компьютера зависят не только от аппаратуры видеоадаптера, но и во многом определяются используемой для него шиной обмена. В настоящее время в персональных компьютерах для обмена с видеоадаптерами обычно используется высокоскоростная шина PCI Express (PCI-E).

Наиболее известными производителями видеоадаптеров являются фирмы ATI и nVidia (США).

Лекция 2. Двумерная компьютерная графика

2.1. Двумерные примитивы

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

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

Точки на плоскости обычно задаются своими координатами (x,y).

Для аналитического задания линий используют алгебраические уравнения или системы функций. Алгебраические линии описываются алгебраическими уравнениями вида F (x, y)=0. Из них на практике чаще используют прямые линии и линии второго порядка (эллипсы, параболы, гиперболы).

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

a ₁ x + a ₂ y + a ₃ = 0. (2.1)

Общее уравнение линии второго порядка имеет следующий вид:

a ₁₁ x ² + a ₂₂ y ² + 2 a ₁₂ x y + 2 a ₁₃ x + 2 a ₂₃ y + a ₃₃ = 0. (2.2)

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

. (2.3)

Матрица-строка P (t)содержит функции x (t), y (t) от общего параметра t, которые определяют значения координат x, y всех точек параметрической кривой. Если дополнительно ограничить область изменения параметра t ₁£ t £ t ₂, то на линии будет выделен отрезок. Например, отрезок параболы между точками (x ₀, y ₀) и (x ₀ + k_x, y ₀ + k_y) задается функциями x (t) = x ₀ + k_x t, y (t) = y ₀ + k_y t ²и ограничением 0£ t £1.

В качестве базисных функций для x (t) и y (t) используют полиномиальные функции, такие, как полиномы Лежандра, Ньютона, Эрмита, Бернштейна. Выбор базиса зависит от постановки задачи и требований к качеству кривой. Полиномиальные параметрические кривые называются сплайнами.

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

Многоугольник общего вида описывается списком его вершин, т.е. списком точек P ₁, P ₂ ,…, P_n на плоскости, которые последовательно соединяются отрезками прямых, причем имеется в виду, что последняя точка соединяется с первой:

Pg =(P ₁, P ₂ ,…, P_n). (2.4)

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

Частными случаями многоугольников являются правильные многоугольники, т.е. многоугольники, у которых равны все стороны и углы между смежными сторонами. Правильный многоугольник может быть вписан в окружность (рис. 2.2), поэтому правильные многоугольники удобно задавать через параметры описанной окружности (x_c, y_c), R и число сторон n.

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

Рис. 2.1

Рис. 2.2

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

2.2. Визуализация на дискретной области вывода

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

Формально область вывода монитора или другого графического устройства растрового типа представляет собой прямоугольную часть дискретной плоскости, для адресации пикселей в которой используется целочисленная система координат. На рис. 2.3 показана ограниченная область вывода с системой координат, используемой в мониторах. Диапазоны изменения координат по осям OX и OY составляют соответственно [0.. Xemax ] и [0.. Yemax ]. Например, для монитора с разрешающей способностью 1280 х 1024 этими диапазонами будут [0..1279] и [0..1023].

Рис. 2.3

Для определенности будем считать, что всякая пара координат
(x, y) в области вывода задает центр соответствующего пикселя.

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

Рис. 2.4

Первая причина погрешности заключается в том, что на дискретной плоскости точно можно представить лишь центры точек с целыми координатами. Для изображения точек с вещественными координатами их приходится округлять до целых значений. Погрешностью δ в изображении всякой точно заданной точки (x, y) следует считать расстояние между этой точкой и центром пикселя, изображающего данную точку. На рис. 2.4 центры пикселей отмечены точками, однако, говоря о максимальной погрешности визуализации из-за округления, чаще вместо этого способа ее оценки для простоты рассматривают максимальную погрешность от округления координат пикселей. В этом случае максимальная погрешность визуализации будет 0,5 пикселя, что не сильно отличается от точной оценки.

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

При визуализации приходится учитывать и другие особенности. В частности, алгоритмы визуализации линейных объектов (отрезков линий) должны изображать их без разрывов. На дискретной плоскости непрерывность между точками в изображении линий и отрезков основана на понятии связности соседних пикселей. Рассматриваются 2 вида связности – 4– и 8-связность (рис. 2.5) [4].

Для 4-связности соседними с данным пикселем (x, y) считаются 4 ближайших, у которых одна из координат (xn, yn) отличается на 1 от координат этого пикселя (см. рис. 2.5, а), т.е. такие, для которых | x – xn | + | y – yn | = 1. Для 8-связности соседними считаются пиксели, у которых одна или обе координаты отличаются от (x, y) на 1 (см. рис. 2.5, б), т.е. такие, для которых | x – xn | + | y – yn | Î [1, 2].

Рис. 2.5

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

2.3. Визуализация отрезков прямых

Пусть на дискретной области вывода требуется построить отрезок между двумя заданными точками, начальной P ₁ с целыми координатами (x ₁, y ₁) и конечной P ₂ с координатами (x ₂, y ₂), т.е. изобразить его с помощью непрерывной последовательности пикселей с наименьшей погрешностью (рис. 2.6). Очевидно, что все промежуточные точки отрезка также должны иметь целые координаты. Далее для определенности будем считать, что целые координаты области вывода соответствуют центрам пикселей.

Уравнение прямой, проходящей через P ₁ и P ₂, имеет вид

. (2.5)

Рис. 2.6

Обозначив приращения координат x ₂ – x ₁ = ∆x; y ₂ – x ₁ = ∆y, представим уравнение (2.5) следующим образом:

∆y (x – x ₁) – ∆x (y – y ₁) = 0. (2.6)

Функцию F (x, y)= ∆y (x – x ₁) – ∆x (y – y ₁) в левой части уравнения (2.6) будем называть оценочной, поскольку ее значение характеризует степень отклонения всякой точки (x, y) от прямой P ₁ P ₂. Действительно, в соответствии с уравнением (2.6) для всех точек прямой
F (x, y) = 0. При удалении всякой точки (x, y) плоскости OXY от P ₁ P ₂ абсолютная величина F (x, y) возрастает прямо пропорционально расстоянию между (x, y) и прямой, поэтому | F (x, y)| может использоваться в качестве меры отклонения оцениваемых точек от строящегося отрезка. Это свойство оценочной функции позволяет вместо непосредственного расчета координат точек отрезка по уравнению прямой линии последовательно выбирать очередные точки для изображения отрезка из соседних на основе сравнения значений F (x, y).

Начнем построение отрезка, взяв за начальное значение текущей точки P точку P ₁. Будем двигаться от нее по дискретной плоскости к конечной точке P ₂, стремясь отклоняться от прямой P ₁ P ₂ в наименьшей степени. Направление движения и значения элементарных шагов s_x и s_y по осям зависят от знаков приращений ∆x и ∆y. Если ∆x > 0,то s_x = 1. Если же ∆x < 0,то s_x = -1. Следовательно, s_x = sign(∆x). Аналогично элементарным шагом по координате y будет s_y = sign(∆y).

Любая точка на дискретной плоскости имеет 8 соседних. Если учитывать направление движения от P ₁ к P ₂, то для выбора очередной точки вместо 8 достаточно рассматривать только 3 соседние точки. Чтобы еще сократить выбор, рассмотрим частный случай, когда | ∆x |³ | ∆y |. Ему соответствуют отрезки с углом наклона к оси OX, меньшим или равным 45⁰. Тогда новым значением текущей точки P с координатами (x, y) может быть либо точка (x + s_x, y), либо (x + s_x, y + s_y). Для выбора лучшей из них используем оценочную функцию.

Так как за начальное значение P принята точка P ₁, лежащая на прямой P ₁ P ₂, то начальное значение F (x, y) = 0. Для соседней точки
(x + s_x, y) имеем

F(x + s_x, y) = ∆y(x + s_x – x₁) – ∆x(y – y₁) = F(x, y) + s_x ∆y. (2.7)

Для соседней точки (x + s_x, y + s_y)

F (x + s_x, y + s_y) = ∆y (x + s_x – x ₁)– ∆x (y + s_y – y ₁) =
= F (x + s_x, y)– s_y ∆x. (2.8)

Рекурсивный вид формул (2.7) и (2.8) позволяет заметно сократить вычисления по сравнению с непосредственным вычислением
F (x, y). Поскольку ∆x, ∆y, s_x, s_y – постоянные величины, то расчеты по формулам (2.7), (2.8) можно еще сократить, если заранее вычислить ∆F_x = s_x ∆y и ∆F_y = s_y ∆x. Тогда

F (x + s_x, y) = F (x, y) + ∆F_x; (2.9)

F (x + s_x, y + s_y) = F (x + s_x, y) – ∆F_y. (2.10)

Если ê F (x + s_x, y) ê < ê F (x + s_x, y + s_y) ê, то точка (x + s_x, y) лежит ближе к прямой P ₁ P ₂, чем точка (x + s_x, y + s_y), и ее следует принять за новое положение текущей точки P. Иначе новым значением P должна стать точка (x + s_x, y + s_y). Далее процесс построения надо повторять до тех пор, пока текущая точка P не достигнет конечной P ₂.

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

1. Установить цвет рисования Color.

2. Вычислить:

∆x = x ₂– x ₁; ∆y = y ₂– y ₁;

s_x = sign(∆x); s_y = sign(∆y);

Если s_x > 0, тогда ∆Fx = ∆y, иначе ∆Fx = – ∆y.
Если s_y > 0, тогда ∆Fy = ∆x, иначе ∆Fy = – ∆x.

x = x ₁; y = y ₁; // начальные координаты текущей точки
F = 0. // начальное значение оценочной функции

3. Вывести пиксель с координатами (x, y) цветом Color.

4. Если x = x ₂, то – конец алгоритма.

5. Вычислить:

Fx = F + ∆Fx; F = Fx – ∆Fy; x = x + s_x.

6. Если ê Fx ê < ê F ê, то вычислить F = Fx,

иначе – вычислить y = y + s_y.

7. Перейти к п. 3.

В алгоритме переменная F обозначает текущее значение оценочной функции, а Fx – новое ее значение при шаге по x. Для сокращения вычислений новое значение оценочной функции при одновременном шаге по x и y также обозначается через F.

Вторую часть алгоритма для построения отрезков с наклоном к оси OX более 45⁰ легко разработать по аналогии.

Близким к рассмотренному, но еще более экономичным по объему вычислений на один пиксель, является алгоритм растрового построения отрезка, разработанный Брезенхемом [5, 7] в 1965 г.

2.4. Кубические сплайны

Кубическими сплайнами называются параметрические кривые, для которых в качестве базисной функции используются полиномы
3-й степени вида

a t ³+ b t ² + c t + d. (2.11)

На плоскости кубический сплайн задается следующим образом:

(2.12)

Параметр t изменяется в пределах 0 £ t £ 1. При этом начальной точкой сплайна будет P (0), а конечной– точка P (1).

Для однозначного задания кубического сплайна в форме Эрмита [1] используют следующие начальные условия (рис. 2.7):

- кривая должна проходить через заданные начальную T ₁ и конечную T ₂ точки;

- в начальной и конечной точках должны быть заданы касательные векторы T¢ ₁ и T¢ ₂ к кривой.

Рис. 2.7

Далее для удобства матрицу-строку [ x y ] координат (x, y)какой-либо точки T или вектора T¢ будем обозначать так же, как и саму точку или вектор.

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

Представим (2.12) в следующей форме:

(2.13)

где L – матрица неизвестных коэффициентов полиномов.

Первое начальное условие дает следующие соотношения:

P (0) = T ₁; P (1) = T ₂. (2.14)

Используя (2.13), запишем их в матричной форме:

P (0) = [0 0 0 1] ´ L = T ₁; (2.15)

P (1) = [1 1 1 1] ´ L = T ₂. (2.16)

Второе начальное условие дает дополнительные соотношения

P¢ (0) = T¢ ₁; P¢ (1) = T¢ ₂. (2.17)

Касательный вектор к кривой P (t)находится как производная P¢ (t).В данном случае

(2.18)

Запишем P¢ (t) в форме, аналогичной (2.13):

(2.19)

Используя (2.19), представим условия (2.17) также в матричной форме:

P¢ (0) = [0 0 1 0] ´ L = T¢ ₁; (2.20)

P¢ (1) = [3 2 1 0] ´ L = T¢ ₂. (2.21)

Теперь все начальные условия (2.15), (2.16), (2.20), (2.21) объединим в единое матричное уравнение с неизвестной матрицей L:

(2.22)

Для нахождения L умножим слева обе части равенства (2.22) на матрицу M_h, обратную матрице с числовыми коэффициентами. В итоге получим

(2.23)

Матрица M_h называется эрмитовой, а вектор G_h с начальными условиями – геометрическим вектором Эрмита. Несмотря на это общепринятое название G_h, следует помнить, что каждый элемент G_h представляет собой строку из двух элементов.

Формула (2.23) позволяет рассчитать коэффициенты матрицы L по заданным начальным условиям, после чего можно построить и сам сплайн P (t), используя формулу (2.12).

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

В 1962 г. французский ученый П. Безье предложил теорию сплайнов, основанную на использовании интерполяционных полиномов Бернштейна. Такой сплайн, получивший название кривой Безье [7], задается списком опорных точек Lp = (T ₀, T ₁,... T_n). Кривая должна проходить только через начальную и конечную точки списка. Остальные точки влияют лишь на форму кривой. При этом векторы T ₀ T ₁ и T_{n -1} T_n являются касательными векторами в начальной и конечной точках кривой (рис. 2.8). Число точек в списке Lp может быть любым, большим 1. При этом степень кривой на 1 меньше числа точек, т.е. равна n – 1.

Математически кривая Безье описывается в виде функции полиномиальной интерполяции между начальной T ₀и конечной T_n точками списка Lp с помощью полиномов Бернштейна. Полином Бернштейна n – ной степени имеет вид

(2.24)

Рис. 2.8

Сама кривая Безье описывается через базисные функции (2.24) и начальные условия следующим образом:

. (2.25)

Здесь T_i = [ x_i y_i ] – координаты i -той точки списка Lp. Отметим, что степень n полиномов в P (t)на единицу меньше числа вершин.

В шрифтах TrueType при определении контуров символов используются квадратичные кривые Безье (n =2). Для задания такой кривой нужны три точки Lp = (T ₀, T ₁, T ₂). В качестве примера рассмотрим кривую подробнее. Сначала запишем для нее все интерполяционные полиномы:

(2.26)

(2.27)

(2.28)

В итоге на основании (2.25) кривая Безье второй степени будет задаваться следующей функцией:

(2.29)

Более детально (2.29) означает следующее:

(2.30)

Кривые Безье применяются во всех популярных графических программах, например в CorelDraw и PhotoShop. Во многих программных продуктах ограничиваются использованием кубических кривых, строящихся по четырем точкам. В частности, кубические кривые Безье используются в API (Application Programming Interface – интерфейс прикладного программирования) Windows. Ограничение кубическими кривыми вызвано разными причинами. Одна из них – глобальное влияние на форму кривой любой из опорных точек, что практически затрудняет ручное сопряжение кривой с другими элементами изображения, поэтому, ограничиваясь кубическими кривыми, более сложные строят путем гладкого сопряжения нескольких кубических кривых.

Ниже в качестве примера приводится алгоритм визуализации кривой Безье n -ной степени с постоянным шагом табуляции по t.

1. Установить цвет рисования Color.

2. Вычислить:

nFact = Factorial (n);

dt = Const; t = dt;

xPred = Lp [0] .x; yPred = Lp [0] .y.

3. Пока t < 1 + dt/ 2выполнитьпп. 3.1 – 3.4.

3.1. Вычислить:

xt = 0; yt = 0;

i = 0.

3.2. Пока i <= n выполнитьп. 3.2.1.

3.2.1. Вычислить

J = t ⁱ * (1 – t) ^n-i * nFact/ (Factorial (i) * Factorial (n-i));

xt = xt + Lp [ i ] .x * J;

yt = yt + Lp [ i ] .y * J;

i = i + 1.

3.3. Вывести отрезок (xPred, yPred, xt, yt)цветом Color.

3.4. Вычислить:

t = t + dt; xPred = xt; yPred = yt.

В приведенном алгоритме предполагается, что список Lp исходных точек T ₀, T ₁,... T_n организован как массив, а длявычисления факториала используется функция Factorial.

2.6. Закрашивание ограниченных
областей плоскости

Существует большое число различных алгоритмов закрашивания, называемых алгоритмами заливки [5], в которых производится закрашивание в заданный цвет области, ограниченной построенным на экране контуром. Эти алгоритмы имеют ограниченные возможности, связанные с тем, что для правильного закрашивания контур не должен пересекаться другими линиями; так же, как и внутри контура не должно быть пикселей, закрашенных в цвет контура. Здесь мы рассмотрим алгоритмы автоматического закрашивания ограниченных областей, заданных математическим описанием. Для таких алгоритмов безразлично содержимое экрана монитора, оно не влияет на процесс закрашивания.

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

Граничный многоугольник области задается упорядоченным списком вершин Pg = (P ₁ , P ₂ , …, P_n), однако задания границы области еще недостаточно. Для полноты формального описания области необходимо также задать правило, определяющее то, с какой стороны от граничной линии располагаются ближайшие внутренние точки области.

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

Рис. 2.9

Сказанное справедливо и для горизонтальных строк растра, поэтому закрашивание многоугольника можно выполнять построчно в пределах от Ymin до Ymax, где Ymin – координата Y самой нижней вершины многоугольника; Ymax – координата Y самой верхней вершины. Если список точек пересечения сторон многоугольника со строкой Y упорядочить по возрастанию или убыванию координаты x, то каждая очередная пара точек в списке будет определять границы (xl, Y) и (xr, Y)закрашиваемого сегмента строки (см. рис. 2.9).

Расчет границ Ymin и Ymax закрашивания по Y позволяет сократить число рассматриваемых строк. Однако, по разным причинам, например за счет масштабирования, многоугольник может частично или полностью выйти по Y за пределы интервала , где
Yemax – максимальное значение координаты y области вывода. Чтобы исключить безрезультатные вычисления в этих случаях, найденные значения следует скорректировать так:

(2.31)

(2.32)

При реализации метода следует учесть случаи, требующие особой обработки. Во-первых, это вершины многоугольника. В каждой вершине сопрягаются две смежные стороны. Если при закрашивании учитывать все точки пересечения сторон со строками, не исключая начальную и конечную, то каждой вершине будут соответствовать две совпадающие границы сегментов, что во многих случаях может привести к неправильному закрашиванию. Вторым особым случаем закрашивания являются горизонтальные стороны (∆ y = 0) граничного многоугольника, поскольку они не пересекают строки растра, а лежат на них.

На рис. 2.10 приведен пример граничного контура многоугольника, на котором цифрами отмечены особые случаи: 1 – это вершины, которые должны обрабатываться как одна граница сегмента; 2 – вершины, которые следует рассматривать как две совпадающие границы; 3 – граничные вершины горизонтальных сторон.

Рис. 2.10

Если для всякой стороны P_iP_{i +1} приращение по y рассчитывать как

, (2.33)

то случаи 1 и 2 легко различать между собой по знаку ∆y смежных сторон, примыкающих к вершинам. В случае 1 они совпадают, а в случае 2 – противоположны.

Для корректной обработки особых случаев примем следующее правило: если сторона многоугольника направлена вверх (∆y > 0), то из расчета точек пересечения со строками будем исключать ее начальную вершину, и наоборот, если сторона многоугольника направлена вниз (∆y < 0), то из расчета точек пересечения со строками будем исключать ее конечную вершину.

В остальных случаях для каждой стороны нужно установить, пересекается ли она с текущей строкой, и если – да, то вычислить координату x точки пересечения. Пусть для очередной стороны многоугольника y_i – координата y начальной вершины, а y_k – координата y ее конечной вершины. Тогда критерием пересечения стороны со строкой Y будет выполнение следующего условия:

((y _i < Y) и (y _k >= Y)) или ((y _i >= Y) и (y _k < Y)). (2.34)

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

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

1. Последовательно просматривая список вершин (P ₁, P ₂ ,.., P_n),найти границы сканирования Ymin и Ymax.

2. Вычислить Ymin = max(Ymin, 0); Ymax = min(Ymax, Yеmax).

3. Для каждой строки Y из [ Ymin.. Ymax ] выполнить пп. 3.1 – 3.4.

3.1. Очистить список Xb.

3.2. Для всех i из [1 .. n ]выполнить п. 3.2.1 – 3.2.2.

3.2.1. Если i < n, то k = i + 1, иначе k = 1.

3.2.2. Если ((y _i < Y) и (y _k >= Y)) или ((y _i >= Y) и (y _k < Y)), то

вычислить координату x точки пересечения стороны P_i P_k
со строкой Y и записать в Xb.

3.3. Отсортировать список Xb по возрастанию.

3.4. Последовательно беря из списка Xb пары xl, xr, закрасить
соответствующие им сегменты строки Y.

В алгоритме для каждой строки Y сначала очищается список Xb границ сегментов, а затем циклически рассматриваются все стороны P_iP_k многоугольника, i – индекс текущей, а k – индекс последующей вершины. Учитывается, что за вершиной P_n следует вершина P ₁. В цикле производится тестирование сторон P_iP_k многоугольника по критерию (2.34). Для сторон, удовлетворяющих условию (2.34), вычисляется координата x точки пересечения стороны со строкой и записывается в Xb.

Когда обработка списка вершин заканчивается, список Xb сортируется по возрастанию. Сортировка гарантирует, что после этого левые и правые границы сегментов при движении от начала к концу списка будут чередоваться, поэтому на заключительном этапе для закрашивания сегментов строки из Xb последовательно берутся пары элементов.

У данного алгоритма есть некоторые особенности. Во-первых, вершины локального максимума по Y будут всегда закрашиваться, а вершины локального минимума – нет (рис. 2.11). Это следствие принятого критерия (2.34) к обработке сторон. На рис. 2.11 квадратиками отмечены места расположения вершин многоугольника. Вершины заданы в центрах квадратиков.

Во-вторых, как видно из того же рисунка, тонкие слабонаклонные к оси OX выступы многоугольника могут закрашиваться не до конца и с разрывами. Здесь причина в построчном способе закрашивания. Максимальная погрешность в расчете границ сегментов из-за их округления составляет 0,5 пикселя, но погрешность в изображении сторон в таких случаях может стать значительно большей. Чтобы визуально улучшить вид многоугольника и снизить погрешность изображения тонких слабонаклонных выступов, можно после завершения закрашивания обрисовать граничный контур многоугольника тем же цветом, что и цвет закраски.

Рис. 2.11

2.7. Алгоритм закрашивания
ориентированных многоугольников

Для определения внутренних точек закрашиваемой многоугольной области можно применить более формальное и более универсальное правило, основанное на использовании понятия ориентации граничного контура. Если исходить из того, что порядок вершин в списке (P ₁, P ₂ ,.., P_n) определяет и порядок построения сторон многоугольника, то каждую сторону P_iP_{i +1}можно рассматривать как вектор, направленный из P_i в P_{i +1}. Тогда правило определения внутренних точек области сформулируем следующим образом: при движении от начала всякого вектора граничного контура к его концу ближайшие внутренние точки области расположены слева от него (рис. 2.12).

Рис. 2.12

Из принятого правила следует, что при обходе вершин против часовой стрелки внутренние точки области лежат внутри многоугольника, а при обходе по часовой стрелке – вне многоугольника. В последнем случае должна закрашиваться вся область вывода кроме точек внутри граничного многоугольника. В соответствии со сказанным далее многоугольник будем считать ориентированным по часовой стрелке или против в зависимости от заданного в списке (P ₁, P ₂ , …, P_n)направления обхода его вершин. Использование понятия ориентации для границы многоугольника позволяет разрабатывать более универсальные алгоритмы закрашивания, имеющие и более широкие возможности.

Как видно из рис. 2.12, стороны много­угольника, направленные вверх (приращение ∆y > 0), являются правыми границами, а стороны, направленные вниз (∆y < 0), – левыми границами закрашиваемых сегментов строки. Точки пересечения сторон с очередной строкой по знаку ∆y можно сразу классифицировать как левые или правые границы сегментов. В связи с этим вместо общего списка X границ сегментов строки здесь удобнее формировать отдельно список Xl левых и список Xr правых границ. Очевидно, что очередную координату x следует заносить в список Xr, когда ∆y > 0, и в список Xl – в противном случае. Когда все точки пересечения сторон многоугольника со строкой будут найдены, количество элементов в списках Xl и Xr должно быть одинаковым.

Если граничный многоугольник ориентирован так, что должна закра­шиваться внешняя область (по часовой стрелке), то все строки, не имеющие точек пересечения с многоугольником, должны закрашиваться полностью (рис. 2.13). Для остальных строк список Xl не будет содержать левой границы первого закра­шива­емого сегмента, а список Xr не будет содержать правой границы последнего сегмента строки. В этих случаях для закрашивания в пределах области вывода в качестве недостающей левой границы первого сегмента следует взять левую границу области вывода, а в качестве недостающей правой границы последнего сегмента строки – ее правую границу.

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