Дешко И.П., Ковалев С.Н. и др. Информационные и коммуникационные технологии

Подождите немного. Документ загружается.

111

строчно на поверхности барабана образ будущего печатаемого

изображения в виде участков с пониженным электрическим по-

тенциалом. При вращении барабана эти участки перемещаются

рядом с контейнером, содержащим частички красящего вещества

(тонера), притягивая эти частицы из-за разницы электрических

потенциалов. Продолжая вращение, участки барабана с притяну-

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

Под дейст-

вием электростатики тонер переносится с барабана на бумагу, на-

гревается специальным нагревателем, расплавляется и спекается,

образуя на бумаге однородные равномерные участки текстовых

символов или элементов графического изображения. Чем выше

плотность тонера на фрагменте бумаги, тем темнее выглядит этот

фрагмент. Лазерные принтеры обеспечивают высокое качество

печати при большой скорости (от

нескольких страниц до не-

скольких десятков страниц в минуту). Цветные лазерные принте-

ры работают по схожему принципу с использованием тонеров не-

скольких базовых цветов.

Струйные принтеры. Струйные принтеры являются широ-

ко распространенной альтернативой лазерным принтерам, осо-

бенно в составе домашнего комплекса ПК, обеспечивая качество

печати, в том числе цветной, не

уступающее лазерным принте-

рам, при существенно меньшей стоимости. Многие модели

струйных принтеров обеспечивают качество цветной печати на

уровне фотопечати. Принцип работы струйного принтера осно-

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

головки (точнее, из нескольких резервуаров с красителями раз-

ных цветов) на бумагу или пленку. Печать осуществляется по-

строчно;

капли красителя, расположенные рядом в соседних

строках изображения, сливаются, создавая однородную высоко-

качественную графику. Существует несколько технологий пере-

носа красителя на бумагу, наиболее распространены из которых –

пьезоэлектрическая и пузырьковая. При использовании пьезо-

электрической технологии порции красителя выдавливаются из

капилляров печатающей головки под действием давления, оказы-

ваемого на стенки капилляра пьезоэлементом (кристаллическое

вещество, изменяющее свои размеры под действием электриче-

112

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

капилляре, выталкивающее порции красителя на бумагу, создает-

ся путем быстрого нагрева красителя в капилляре специальными

микронагревателями при пропускании через них электрического

тока. Термин «пузырьковая» связан с тем, что в некоторых вари-

антах этой технологии краситель в процессе работы нагревается

до температуры кипения.

ЛИТЕРАТУРА

Колесниченко О.В., Шишигин И.В. Аппаратные средства

PC. Энциклопедия аппаратных ресурсов персонального компью-

тера. Наиболее полное руководство в подлиннике. – 5-е изд., пе-

рераб. и доп. – СПб: BHV, 2004. 1152с.

ОСНОВЫ КОМПЬЮТЕРНОЙ ГРАФИКИ

В.Н.Цыпкин, к.т.н., доцент

1. Введение в компьютерную графику

Принято выделять три основных направления, связанные с

компьютерной обработкой графической информации: распозна-

вание образов, обработка изображений и компьютерная (или

машинная) графика. Основная задача распознавания образов

(или системы технического зрения – computer vision) состоит в

преобразовании изображения или реального физического объекта

в описание на формально понятном

языке символов (сканирова-

ние, цифровая фото- и видеосъемка). Обработка изображений

(image processing) – направление, связанное с преобразованием

одного вида изображения в другое (контрастирование снимков,

синтезирование имеющихся изображений в новые). Задачи ком-

пьютерной графики (computer graphics) – в настоящее время

достаточно развитой и многосторонней отрасли знания – состоят

в обработке формальных (символьных) описаний объектов и ви-

зуализации изображения.

Спектр использования компьютерной графики чрезвычайно

широк: реклама и различного рода презентации, компьютерные

113

игры и мультипликация, малые и монументальные формы дизай-

на, компьютерная живопись, архитектура, медицина, образова-

ние, наука, проектно-конструкторские разработки, администра-

тивное управление и т.д.

При реализации компьютерной графики используются фай-

лы данных, содержащие информацию об объектах, а также обра-

батывающие эту информацию программы. Исходная информация

поступает в центральный процессор компьютера

, обрабатывается

в нем (зачастую в интерактивном режиме), проходит через ряд

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

временное хранение информации, и затем, уже в аналоговом ви-

де, подается на исполнительные органы графовыводящего уст-

ройства. Выводимое изображение формируется путем поворота,

переноса, масштабирования и вычисления различных проекций

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

матричных операций с данными [1] (математический аппарат та-

ких преобразований достаточно сложен, и его анализ выходит за

рамки настоящей темы). Кроме того, до визуализации изображе-

ния часто требуется осуществить удаление невидимых линий и

поверхностей, закраску поверхностей, двумерное или трехмерное

отсечение (см. ниже). Для таких действий применяются про-

граммные средства, реализующие базовые алгоритмы

компью-

терной графики [2] (ознакомлению с некоторыми из этих алго-

ритмов посвящен второй раздел настоящей темы).

Для вывода непосредственно изображения используются

графовыводящие устройства: дисплеи, принтеры, графопострои-

тели, проекторы и т.п. Практически все современные устройства

такого рода являются точечно-рисующими (растровыми) или

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

наиболее

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

компьютерной графики воплощены в растровых дисплеях.

С точки зрения возможностей формирования изображения

экран растрового дисплея (при конкретных настройках свойств

экрана) представляет собой прямоугольную матрицу дискретных

точек – пикселей (picture elements). В цветном дисплее каждый

пиксель состоит из трех субпикселей, отвечающих за интенсив-

114

ность свечения соответственно трех основных цветов (красного,

зеленого и синего). Варианты аддитивного смешения этих цве-

тов, различающиеся уровнями интенсивности составляющих,

воспринимаются человеком как множество цветовых оттенков.

Положение пикселя в координатной плоскости экрана определя-

ется целочисленными координатами по горизонтали (x) и верти-

кали (

y) его адресуемой точки, расположенной в левом нижнем

углу пикселя. Совокупность пикселей экрана образует растр.

Число пикселей, содержащихся в одной горизонтальной строке

растра, и число таких строк по вертикали определяют разреше-

ние экрана. Преобразование цифровых видеоданных в аналого-

вый сигнал, формирующий изображение на экране, обеспечивает

видеоадаптер. Он, с одной стороны,

хранит в буфере кадра (под

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

бражении (при этом на каждый пиксель отводится фиксирован-

ное количество бит памяти), а с другой – обеспечивает регуляр-

ное отображение содержимого видеопамяти на экране. Частота

вывода изображения на экран называется частотой регенерации

изображения. Буфер кадра и, соответственно, содержание изо-

бражения

обновляются в два раза реже. Частоту, с которой это

происходит, называют частотой воспроизведения кадра (или

частотой кадровой развертки).

Приведем пример специфики формирования изображения в

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

экран не идеально точных фигур, а только лишь более-менее точ-

ных их аппроксимаций, представляющих собой выбранные по

каким

-либо соображениям наборы пикселей. Так, например, в

изображении отрезка прямой во многих случаях появляются сту-

пеньки (лестничный эффект), кривые превращаются, по сути де-

ла, в ломаные линии, замкнутые кривые – в многоугольники

(этим, отчасти, обусловлено введение понятия компьютерной

геометрии). Данное обстоятельство приводит к необходимости

применения методов (алгоритмов), позволяющих формализовать

процесс поиска

пикселей, аппроксимирующих ту или иную фи-

гуру (этот процесс называется разложением в растр).

Алгоритмы компьютерной графики принято разделять на

115

группы, в каждой из которых решаются близкие по смыслу зада-

чи. Можно выделить пять таких групп:

 генерация простых фигур – алгоритмы, связанные с разложе-

нием в растр отрезков прямых, разомкнутых и замкнутых кри-

вых (парабол, гипербол, окружностей, эллипсов и т.п.);

 заполнение многоугольников (или заполнение контуров) –

группа алгоритмов, осуществляющих генерацию

(закраску)

сплошных областей;

 отсечение, в том числе двумерное и трехмерное – решаются

задачи визуализации той части соответственно плоской и объ-

емной сцены, которая находится внутри (внутреннее отсече-

ние) или вне (внешнее отсечение) отсекающей фигуры;

 удаление невидимых линий и поверхностей – алгоритмы оп-

ределяют и удаляют из трехмерной сцены ребра, поверхности,

объемы или их фрагменты, которые заслонены другими объ-

ектами и невидимы наблюдателю, находящемуся в заданной

точке пространства;

 построение реалистических изображений – группа наибо-

лее сложных алгоритмов, реализующих закраску участвую-

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

физических, в том числе оптических свойств, а также распо-

ложения и характеристик

источников света

В соответствующих разделах алгоритмических основ ком-

пьютерной графики рассматриваются теоретические положения,

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

ином виде их формальные описания.

2. Алгоритмы компьютерной графики

В настоящем разделе темы представлены краткие сведения о

теоретических основах построения некоторых базовых

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

Алгоритм Брезенхема для генерации окружности

116

Данный алгоритм является целочисленным. В соответст-

вии с ним полагается, что генерируется окружность с целочис-

ленным радиусом R и центром в точке (x = 0, y = 0) (что всегда

можно сделать, связав координаты x и y с координатной сеткой

растра простым преобразованием координат). Изначально по-

шагово (переходя от пикселя к

пикселю) строится четверть

окружности в первом квадран-

те. Причем ее построение на-

чинается в точке (x = 0, y = R)

и осуществляется в направле-

нии по часовой стрелке. При

таких условиях и нахождении

в некоторой текущей точке

растра с координатами адре-

суемой точки (x

, y

) есть толь-

ко три варианта выбора оче-

редного пикселя (рис.1): по

горизонтали вправо (направ-

ление H

), по диагонали вниз и вправо (направление D) и по

вертикали вниз (направление V

В качестве критериев перехода используются следующие вели-

чины:

()

(

)

R1y1x −−++=

;

(

)

1y2

−

;

(

)

1x2

−

′

Согласно алгоритму Брезенхема:

 если

< 0:

при

≤

выбираем направление H

, т.е. пиксель (x

+ 1, y

);

при

выбираем направление D

, т.е. пиксель (x

+ 1, y

–1);

 если

> 0:

при

δ′

≤

выбираем направление D

, т.е. пиксель (x

+ 1, y

– 1);

Рис.1. К выбору очередного

пикселя

()

y,x

()

y,1x +

()

1y,1x

−

()

1y,x

−

117

при

δ′

выбираем направление V

, т.е. пиксель (x

, y

– 1);

 если

= 0 выбираем направление D

, т.е. пиксель (x

+ 1, y

– 1).

При переходе к очередному текущему пикселю можно ис-

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

 при шаге в горизонтальном направлении H:

1xx

i1i

;

i1i

; ;1x2

1ii1i

 при шаге в диаметральном направлении D:

1xx

i1i

;

1yy

i1i

−

;

2y2x2

1i1ii1i

+−

+++

;

 при шаге в вертикальном направлении

i1i

; 1yy

i1i

−

; 1y2

1ii1i

−

Для построения полной окружности полученную в первом

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

относительно осей

x и y, а также относительно начала координат,

т.е. активизировать не только выбранные пиксели (

, y

), но и

симметричные им пиксели (

, – y

), (– x

, y

) и (– x

, – y

Построчный алгоритм заполнения с затравкой

для гранично-определенной четырехсвязной области

В алгоритмах, относящихся к группе методов «затравочного

заполнения», один пиксель внутри закрашиваемого контура –

затравка – должен быть заранее известен. Начиная с этого пик-

селя, алгоритмы находят и закрашивают все другие пиксели об-

ласти, ограниченной контуром, до обнаружения границ. В про-

цессе работы в качестве новой затравки назначаются, по тем или

иным соображениям, другие пиксели области.

Гранично-определенная область характеризуется тем, что

все пиксели на ее

границе имеют определенный цвет, причем ни

один пиксель самой области не может иметь этот цвет. Четырех-

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

от пикселя к пикселю в четырех направлениях: влево, вправо,

вверх и вниз.

118

0 1

2 3 4 5 6 7 8

Извле-

каемый

из стека

пиксель

лев

пр

(3, 5) 1 5

(5, 4) 4 6

(6, 3) 5 6

(6, 2) 1 6

(6, 1) 5 6

(2, 1) 1 2

(2, 3) 1 2

(2, 4) 1 2

(2, 4) – –

(4, 6) 1 4

Рис.2. Последовательность действий при работе

построчного алгоритма заполнения с затравкой

Работу рассматриваемого алгоритма схематично можно

описать так:

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

в стек;

 пока стек не пуст:

извлечь данные о пикселе из стека; если ему уже присвоено тре-

буемое значение цвета – проигнорировать, если нет, тогда:

присвоить

пикселю требуемое значение цвета; заполнить интер-

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

щей строки до обнаружения границ;

переменным

лев

и х

пр

присвоить значения горизонтальных коор-

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

него правого пикселей интервала;

в диапазоне

лев

≤

пр

проверить строки, расположение непо-

средственно над и под текущей строкой; если в них есть еще не

заполненные интервалы (т.е. не все пиксели граничные или уже

119

заполненные), то в указанном диапазоне данные о крайнем пра-

вом пикселе на каждом интервале поместить в стек.

Рис.2 иллюстрирует последовательность действий при рабо-

те такого алгоритма по заполнению конкретной гранично-

определенной четырехсвязной области. В качестве исходной за-

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

(

3, 5). На рисунке обозначены также уровни стека, на которые

помещаются данные о соответствующих пикселях.

Алгоритм двумерного отсечения Сазерленда-Коэна

Данный алгоритм реализует отсечение отрезков координат-

но-ориентированным прямоугольником, границы которого: ле-

вая, правая, нижняя и верхняя – задаются координатами соот-

ветственно

, x

, y

и y

(рис.3). В алгоритме используются

четырехразрядные (битовые) коды, определяющие расположение

концов отрезков относительно границ отсекающего окна. При

формировании кода конца отрезка с координатами (

x, y) в первый

(крайний правый) бит заносится

1, если x < x

, во второй – если

x > x

, в третий – если y < y

, в четвертый – если y > y

. В

остальных случаях в соответствующие биты заносится

0. Таким

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

областей, в каждой из которых концу отрезка присваивается

уникальный код (см. рис.3). При внутреннем отсечении

признаком полной видимости отрезка являются нулевые коды

обоих его концов (как для отрезка

ab на рис.3). Признак

безусловной невидимости отрезка – отличное от нуля побитовое

логическое произведение концевых кодов (так, у отрезка

cd,

расположенного целиком левее отсекающего окна, с кодами

концов

0101 и 0001 такое произведение будет равно 0001).

Вместе с тем, при полностью нулевом побитовом логическом

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

видимым (как отрезки

ef и gh) или полностью невидимым (как

отрезок

ij). Для подобных отрезков при выявлении их возможных

видимых частей используются результаты определения точек

пересечения бесконечной прямой линии, проведенной через

отрезок, с бесконечными прямыми линиями, проведенными через

ребра отсекающего окна.

1001 1000 1010

0001 0000 0010

0101 0100 0110

Рис.3. Коды концов отрезков

120

Для отрезка с началом в точке P

, y

) и концом в точке

, y

), если он не вертикален (

(

)

(

)

∞≠−

−

1212

xxyym ), та-

кие точки пересечения на прямых, проведенных через левое и

правое ребра, будут иметь координаты соответственно:

x = x

()

11л

yxxmy

−

; x = x

()

11п

yxxmy +−

Если отрезок не горизонтален (

≠

), координаты анало-

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

и верхнее ребра, будут равны соответственно:

()

11н

xmyyx +−= , y = y

;

(

)

11в

xmyyx +

−

, y = y

Последовательность действий в алгоритме двумерного

внутреннего отсечения Сазерленда-Коэна следующая. С исполь-

зованием кодов концов отрезок проверяется на полную види-

мость и безусловную невидимость. Если проверка не дает оче-

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

виде бесконечных прямых, проходящих соответственно через ле-

вое, правое, нижнее и верхнее ребра отсекающего

окна. В каждом

случае проверяется, не лежит ли отрезок полностью в той же сто-

роне от отсекающей прямой, что и само окно (очевидно, напри-

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

отрезок полностью лежит правее левой отсекающей прямой). Ес-

ли это так, переходят к следующей отсекающей прямой. В про-

тивном случае проверяют, не лежит ли начало отрезка в той же

стороне, что и окно. Если это подтверждается, начало и конец от-

резка

меняются местами. Начало отрезка в любом случае оказы-

вается по отношению к отсекающей прямой в стороне, противо-

положной той, где находится окно. После определения точки пе-

ресечения прямой, проведенной через отрезок, с текущей отсе-

кающей прямой начало отрезка переносится в эту точку (уда-

ляется часть отрезка). Полученный новый отрезок вновь

проверяется

на полную видимость и безусловную невидимость. В

зависимости от результата переходят к следующей отсекающей

прямой или алгоритм заканчивает работу.

Алгоритм плавающего горизонта