Текст
681.327.22(07)
p 85i — № 2150-1
ГОСУДАРСТВЕННЫЙ КОМИТЕТ ПО ВЫСШЕМУ ОБРАЗОВАНИЮ РОССИЙСКОЙ ФЕДЕРАЦИИ
ТАГАНРОГСКИЙ ГОСУДАРСТВЕННЫЙ РАДИОТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ
17
<х X X ш
РАСТРОВАЯ ГРАФИКА
и® РУКОВОДСТВО
а®х к лабораторной работе
и
“о® по курсу
КОМПЬЮТЕРНАЯ ГРАФИКА * щ S
Для студентов специальностей 22.01, 22.04
S
Ю н < г
Таганрог 1995
УДК 681.327,22(076.5)
Составитель В. В. Селянкин
Растровая графика: Руководство к лабораторной работе по курсу «Компьютерная графика». Таганрог: ТРТУ, 1995. 40с.
Данное руководство предназначено для ознакомления с алгоритмами растровой графики по курсу «Компьютерная графика» и содержит сведения об элементах растровой графики при воспроизведении на экране графических примитивов — линии, окружности, дуги, эллипса, круга, растровой развертки многоугольников, заливки областей, а также сведения по работе с фрагментами изображений, полутоновой аппроксимацией и растровыми фонтами.
Кроме того, в руководстве даны варианты заданий к лабораторной работе, определен порядок ее выполнения и приводится пример выполнения задания. Оно предназначено для студентов дневного п заочного обучения специальностей 22.04, 22.01, а также для студентов родственных специальностей, изучающих компьютерную графику.
Табл. 2. Ил. 20. Библиогр.: 14 назв.
Рецензент Н. И. Витиска, д-р техн, наук, профессор кафедры «Информатика» ТГПИ.
ВВЕДЕНИЕ
Среди многообразия возможностей, предоставляемых современными вычислительными средствами, компьютерная графика, ориентированная на пространственно-образное мышление человека, занимает особое место. Мэ-тоды и средства компьютерной графики представляют собой эффективный инструмент при выполнении проектно-конструкторских, научно-исследовательских, оформительских работ, а также всех случаев визуализации различных объектов. При этом наблюдается взаимное повышение возможностей, как человека, ' владеющего эффективным инструментом, так и компьютера, обогащенного новыми возможностями. В этом смысле значительную роль игг рает разработка соотбетстзующих алгоритмов, отличающихся качественными параметрами по быстродействию, объемам используемой памяти и спектру предоставляемых возможностей.
иеновой компьютерной графики являются методы и алгооитмы растровой графики, которые позволяют строить любые изображения на растровых дисплеях, использующих, прямоугольную матрицу точек (пикселов). Каждый пиксел может изображаться некоторым цветом, выбранным из имеющейся палитры цветов. Для реализации любого изображения в компьютере имеется видеоадаптер, хранящий в своей видеопамяти изображение и обеспечивающий регенерацию изображения на экране сс скоростью порядка 50 паз . в секунду. Размер палитры определяется объемом видеопамяти, отводимой под один пиксел, и зависит of1 типа видеоадаптера. Для ПЭвМ типа IBM существует несколько видеоадаптеров, отличающихся возможностями, своич устройством и принципами работы с 'ними: Hercules, CGA, EGA, VGA, SVGA. Почти все указанные адаптеры поддерживают несколько режимов работы, которые отличаются друг от друга размерами матрицы пикселов - разрешающей способностью изображений, и размером палитры. Как правило, развитие видеоадаптеров строится по принципу совместимости с предыдущими
- 4 -
моделями, однако, при этом могут иметь месте некоторые особенности, нарушающие это положение.
Построение изображения строится на работе о отдельными пикселами, однако пользователю может предоставляться достаточно широкий набор библиотечных примитивов, которые позволяют габотять на более высоком уровне за счет операций с графическими объекте®! что значительно повыпеет эффективность работы. Такими объектами
могут выступать линии, дуги, окружности, сложные кривые, сллолиые объекты, шрифты, картинки и другие. Ках правило, каждый язык пр.трзммиюо-вания имеет свою графическую библиотеку, обеспечивающею работу с.элементами и группами графических объектов, которая должна при этом поддерживать работу с основными типами видеоадаптеров. Данное методическое руководство рассматривает работу с одной из популярных графических библиотек - модулем Gragh системы Turbo Pascal.- Следует отметить, что реализация этой библиотеки в системе Turbo -С фирмы Borland практически нс отличается от нее.
Данное руководство рассматривает' растровую графику, оперирующую с отдельной точкой. Это связано с тем, что квалифицированному специалисту необходимо иметь полное представление о "внутренней технологии" построения изображения, что позволяет при необходимости самостоятельно разрабатывать эффективные алгоритмы в нестандартных ситуациях. Кроме того, при работе с такими устройствами как 'принтер, плоттер, мышь, которые тоже являются растровыми, требуется реализация растровой генерации соответствующих геометрических объектов.
Особенности растровой графики связаны с тем, что обычные изображения, с которыми сталкивается человек в своей деятельности (чертежи, графики, карты, художественные картины и т.п.), реализованы на плоскости, состоящей из бесконечного набора точек. Экран же растрового дисплея представляется матрицей дискретных элементов, имеющих конкретные физические размеры. При этом число их существенно ограничено. Поэтому нельзя провести точную линию из одной точки в другую, а можно выполнить только аппроксимацию этой линии с отображением ее на дискретной матрице.
Для большей определенности следует ввести понятие дискретной плоскости, имеющей целочисленные координаты. Такую плоскость также называют целочисленной решеткой, растровой плоскостью или растром. Эта решетка представляется квадратной сеткой с шагом 1 Узлы целочисленной решетки являются центрами соответствующих квадратных ячеек сетки. Та
- 5 -
ким образом, узлы растра окружены "единичными" квадратными окрестностями "радиуса" 1/2. При обращении к точке растра о координатами (1,6) выполняется инициализация единичного квадрата с закрашиванием его соответствующим цветом. / /
Отображение любого объекта на целочисленную решетку называется разложением его з растр или просто растровым представлением. Естественно, это разложение лишь приблизительно представляет изображаемый объект. Отображение является неоднозначным ввиду зависимости .его от алгоритмов аппроксимации, а они, в свою очередь - от критериев определения точек растра. В связи с этим возникает задача выбора оптимального алгоритма по соответствующему, критерию. /
1. РАСТРОВАЯ РАЗВЕРТКА ОТРЕЗКОВ
1.1. Работа с отрезками прямых
При анализе конкретных алгоритмов рисования отрезков необходимо рассмотреть общие требования к таким алгоритмам и определить критерии их оценок. Естественно, ставится задача рисования отрезков таким образом, чтобы они выглядели прямыми и начинались и заканчивались в заданных точках. Важное значение имеет яркость изображения отрезка,1 которая должна быть постоянной вдоль всего отрезка и не зависеть от его наклона. Кроме того, вывод изображения должен быть выполнен с высокой скоростью. Каждый из перечисленных параметров выполним в определенных границах, определяемых параметрами экрана, .быстродействием компьютера, его объемами памяти ь, выбранным алгоритмом. Улучшение перечисленных характеристик приводит к более полному удовлетворению указанных требований.
Постоянная яркость вдоль всего отрезка достигается лишь при проведении горизонтальных и вертикальных линий или под углом 45°. Кроме того, эти отрезки , имея постоянную 'яркость, различаются между собой степенью яркости- два первых имеют наибольшую, а тоетий - наименьшую яркость. Для всех других вариантов расположения отрезки будут иметь неравномерную и ' различную яркость. Обеспечение одинаковой яркости вдоль отрезков разных длин и ориентаций требует извлечения квадратного корня или использования адаптеров, дающих набор полутонсв, что существенно замедляет процесс вычисления. Обычно реализация разложения отрезка в растр вппопняется с выбором некоторого компромисса рассмотрен-
- 6 -
них вариантов, при котором длина отрезка определяется приближенно, вычисления сводятся к некоторому минимуму за счет использования целочисленной арифметики с исключением операций деления и умножения’, реализации алгоритмов на аппаратном или микропрограммном уровне.
1.2. Простой поааговый алгоритм
Пусть концы отрезка MjMz имеют координаты (х1# yj и (хг, уг).Тогда уравнение отрезка прямой будет определяться следующим выражением
у = Vi +. к*(х - act).
где к = (уг - yj/fig ~ xt),
< X < хг.
В простейшем случае предполагается, что коэффициент К неотрицателен и не превосходит единицы. Перебирая значения х в пределах от до лг е определенным шагом, можно вычислить соответствующие значения у, которые будут отвечать условию
У1 < У < Уг-
и прорисовать текущие точки (х, у). Для простоты шаг прорисовки Ах можно принять равным единице.
Процедура генераций растровой развертки отрезка при указанном алгоритме будет иметь следующий вид:
Dx 1; Dy abs(y2 - ylV(x2 - xl);
х : = xl; у : = yl; for 1 : = 0 co L-l do begin
PucPixel (x,round(y));
x : = x + Px; у : = у + Dy;
end.
-ализация этой процедуры сопряжена со следующими проблемами. Если yi.’.f наклона отрезка прямой к оси абсцисс больше 45°. то приращение отр'зка за один шаг по оси ординат превышает соответствующе^ приращение пс оси абсцисс. Это приводит к тому, что при Ах = 1 приращение Ду
- 7 -
> 1 и линия отрезка будет иметь разрывы. Кроме того, реализация операций деления и округления требует обработки вещественных чисел, что приводит к уменьшению быстродействия. Первую проблему можно решить симметричной заменой координат х и у. Вторую - соответствующей корректировкой алгоритма.
1.3. Универсальный простой алгоритм
Рассмотрим реализацию простого алгоритма, работающего при любой ориентации отрезка прямой на плоскости. В этом случае требуется выбирать базовое приращение по одной из осей координат, равное единице, в зависимости от того, какое из них является большим. Для этого следует
Для-1,4,5 и 8 октантов алгоритмы вычисления приращений имеют вид
xltl - Xi + 1;
У1*1 = У1 + Ду;
Ау = (Уг “ У1 )/(хг - xt).
Для 2,3,6 и 7 октантов соответствующие вычисления принимают вид
yi*i = .У1 + 1;
Х£л1 = Xi + ДХ,‘
Ах = (хг - Х1)/(Уг - yt).
В соответствии с приведенными вычислениями реализация алготирма может быть представлена следующим Ъбразом.
var
х1,у1,х2,у2: Integer;
- 8 -
1,1; • ' integer;
x, у, dx, dy; real;
{вычисляем большую из длин 1 отрезка по оси х и у} if abs (х2 - х!) > abs (у2 - у!) then 1 := abs (х2 - xl) else 1 : = abs (у2 - yl);
(определяем приращения по оси х и у, полагая большее из них равным единице) dx ; =. (х2 - х1.)/1;
dy (у2 - у!)/1;
{начинаем с точки (х,у))
х : = xi:
У := У1:
{цикл по большей длине отрезка)
1;-1;
while (1 < 1)
PutPixel (Round(x).Round(y));
х : = х + dx;
у : = у + dy;
1 ;= 1 + 1;
end while
Данный алгоритм, как и предыдущий, содержит операции деления и округления, что, кроме снижения скорости реализации, может приводить к накоплению погрешности, в результате которой последняя точка может отличаться от заданной.
1.4. Алгоритм Брезеихема
Алгоритм Брэзенхема (Bresenham) был разработан для цифровых графопостроителей, а затем стал использоваться для растровых дисплеев. Отличительной его характеристикой является возможность выбора опти-малвных растровых координат, для представления отрезка. Идея алгоритма заключается в тем, что одна координата изменяется на единицу, а другая - либо не изменяется, либо изменяется на единицу в зависимости бт расположения соответствующей точки от ближайшего узла координатной сетки. Расстояние от точки отрезка До ближайшего узла по соответствующей ортогональной координате называется ошибкой. Алгоритм организован таким
- 9 -
образом, что для вычисления второй координаты требуется только определять знак этой ошибки. Для первого октанта это показано на рис.2.
Рис. 2
Величину ошибки & можно определить в соответствии со следующим выражением:
~ Ууз - УоТ'
гДе Ууг “ у-координата ближайшего.узла при х » 1, |
уот - у-координата точки отрезка при х = 1.
Если при х = 1 у-координата точки отрезка равна 1/2, то узлы координатной оетки (1,0) и (1,1) находятся на одинаковом расстоянии от отрезка и в качестве "ближайшего" выбирается узел (1,1). Таким образом, если уот > 1/2, то А > О, в противном случае, при уот < 1/2, - А < 0. Для организации вычислений удобнее пользоваться не величиной Л, а другой, определяемой как величина г
•
d = А - 1/2. '
При изменении координаты х на единицу величина <3 меняется на значение углового коэффициента:
d = d + Ау/Дх. i 1
В соответ—вии о этим можно построить график изменения величины d при изменении к> огцинчты х. как показано на рис.З.
- 10 -
На каждом шаге алгоритма производится вычисление координаты х. величины d и выполняется анализ знака d. При этом, если окажется, что d > О,- то производится увеличение у на единицу, а значение d корректируется путем вычитания из нее единицы. С учетом изложенного алгоритм аппроксимации отрезка в первом октанте можно представить в следующем виде.
х := х1; /
У := У1;
dx := х2 - xl;
dy .'= у2- yl;
d :- -1/2; ' ,
while х 4 х2 do
PutPlxel (х,у);
х : = х + 1;
d : = d + dy/dx;
If d > 0-then begin
У У + i;
d := d - i
end
end while.
- 11 -
Представленный алгоритм использует вещественные числа и операцию деления. Оба недостатка можно исключить заменой величины d на другую, равную
D - 2 ♦ dx *. d.
В соответствии с этим арифметические выражения, в которых участвует d. модифицируются путем умножения обеих частей на величину 2*dx. Тогда алгоритм принимает вид
х :« xl’ у yl: dx х2 - xl;
dy у2 - yl;
D : - -dx: while х < х2 do PutPlxel (х,У); х х + i-J D D + 2*dy; If D > 0 then begin
У У + 1:
D :« D - 2»dx end end while.
Последний вариант алгоритма можно еще улучшить, если операцию умножения на 2 заменить операцией сдвига влево на один,разряд. Кроме того, если вычисление 2*dx и 2*dy выполнить перед циклом, то операцию сдвига потребуется выполнить только два раза. Тогда алгоритм принимает окончательньй вид
к : xl;
У У1;
dx :« х2 - xl;
dy :» У2 - У1;
О -dx;
DX dx shl 1;
BY dy ahi 1;
- 12 -
while x <x2 do PutPlxel (x,y);
x : = x + 1;
D : - D + DY: if D > 0 then begin
у = у + 1;
D : - D - DX end end while.
Оценивая достоинства полученного алгоритма, можно отметить, что он выполняет оптимальную аппроксимацию отрезка, используя при этом целочисленную арифметику и минимальное количество операций сложения и вычитания. Кроме того, алгоритм дозволяет использовать его и в остальных октантах плоскости. Схема использования алгоритма для других октантов показана на рис. 4.
Рис. 4
Р . хьисда с^и от расположения отрезка на плоскости можно скорректировать алгоритм растровой развертки отрезка для первого октанта путем увеличения или уменьшения соответствующих координат на единицу.
При реализации общего алгоритма растровой развертки отрезков следует учитывать .отличие экранной системы координат от декартовой системы. Считается, что координаты отрезка заданы в декартовой системе, начало которой располагается в центре экрана. Для правильной работы алгоритма необходимо предусмотреть программный перевод этих координат в экранную систему.
- 13 -
1.5. Растровая развертка через видеопамять
Эффективность реализации растровой развертки отрезка можно существенно повысить за счет непосредственного обращения в видеопамять компьютера. Вывод пиксела на экран выполняется процедурой PutPlxel, реализация которой требует вычисления по его координатам (х, у) адреса сегмента, смещения байта и месторасположения бита в байте. При этом никак не учитывается тот факт, что одна или другая координата может не изменяться, и. следовательно, имеется принципиальная возможность использовать сегмент, смещение и маску, вычисленные на предыдущем шаге. Кроме того, по алгоритму Брезенхема каждая из координат может изменяться только на единицу. Поэтому здесь может меняться только маска или сегмент и лишь иногда и смещение. В соответствии с этим рассмотрим в качестве примера процедуры увеличения координат х и у на единицу для адаптера Hercules.
Реализация х - х + 1 имеет вид
If Mask - 1 then
Mask := $80
Offset := Offset + 1 else
Mask := Mask shr 1
Реализация у = у + 1 имеет вид
If (Segment and $0600) - $0600 then Segment : = Segment and JF8FF Offset := Offset + 90 else
Segment Segment 4 $o?00
Для вывода на вк^ан требуемого пиксела используется процедура MemtSegment:Offsetl и соответствующий стиль вывода MOV, X0R или NOT.
Если при этом какая-то координата не Изменяет своего значения, то для нее не выполняется каких вычислений. .Аналогично строятся процр-
- 14 -
дуры вычисления адреса сегмента, смещения байта и маски бита при уменьшении этих координат на единицу. В этом случае подбираются другие константы, другое направление смещения маски и знак "плюс" заменяется на знак "минус". Пс этой же методйке строятся процедуры вычисления координат и для других адаптеров - CGA, EGA/VGA. Для правильной организации этих процедур необходимо представлять себе устройство видеопамяти используемых адаптеров и способ регенерации изображения.
2. РАСТРОВАЯ РАЗВЕРТКА ОКРУЖНОСТИ
2.1. Алгоритмы растровой развертки окружности
Наиболее простой способ определения точек окружности можно получить решением уравнения окружности
х2 + у2 = R2
относительно одной координаты. Например, изменяя х от -к до +R можно вычислить у из соотношения
у - ± |/йй - X2 .
При этом, однако, требуется операция вычисления корня квадратного, что приведет к значительному объему вычислений, а также к появлению разрывов окружности по мере приближения к точкам х = -R и х = +R. Несколько более лучший вариант получается при использовании полярных координат
х = R * Cos <р, у = К * Sir. ф.
Здесь изменение угла в пределах от 0° до 360е позволяет вычислять значения координат х и у. Основная трудность использования этого метода заключается в вычислении тригонометрических функций угла. Кроме того, необходимы определенные усилия по выбору шага изменения угла, который должен быть переменным для того, чтобы избежать разрывов или от -оутствиЯ изменения координат.
Возможен еще один способ получения окружности путём аппроксимации ее вписанным многоугольником, при котором.соседние вычисляемые точки соединяются отрезками прямых. В зависимости от , требуемой точности
• 15 -
построения окружности можно выбирать соответствующее числа сторон многоугольника, выбирая компромиссное решение между точностью и сложностью (скоростью) вычислений. Здесь также можно задавать не только число сторон многоугольника, но и таг изменения угла радиуса окружности, концевые точки которого образуют множество точек окружности, подлежащие соединению отрезками прямых. В этом случае решается задача выбора шага изменения угла.
При построении окружности каким-либо'способом можно также использовать различные методы повышения эффективности алгоритма. Например, достаточно вычислять только точки одного октанта, по которым можно по лучить все остальные точки окружности за счет симметричности‘их расположения относительно четырех осей вращения, как показано на рис. 5,-
Рис. 5 I
При этом каждая вычисленная точка (х,у) позволяет получить еще 7 других: (-х.у), (х,-у), (-х,-у), (у,х), (-у,х), (у,-х), (-у,-х),
2.2. Алгоритм Брезенхема для окружности
Этот алгоритм является более эффективным по скорости и оптимальным по точности ' построения точек окружности и основан, на пошаговом методе их вычисления. Базовым алгоритмом является алгоритм построения окружности в первом октанте. В этом случае координаты имеют следующие пределы изменения:
R/|/^2 -< х С R.
О < у < R//2.
16 -
те.
На рис.6 показана часть окружности, расположенная в первом октан-
Рис. 6
В первом октанте координата х монотонно убывает, а координата у монотонно возрастает, Если построение точек окружности начать с точки (R., то движение от предыдущей точки к последующей возможно в двух вариантах, которые можно обозначить как "движение а" и "движение Ь" Рисунок 7 поясняет эти варианты переходов от точки к точка.
В соответствии с этим можно описать указанные движений через изменение их координат
движение 3: Xj, । -- х(;
У,*1 J У1 +
движение b- x1+I = Xj - 1;
У1+, ’ У1 + 1-
При вы&эре того или иного движения руководствуются соображениями
- 17 -
получения наименьшей ошибки Л, которая определяется как разность между вычисляемой точкой (точкой растра) и точкой окружности:
At = xt2 + у/ - R2.
Выполним вычисления этой ошибки для обоих движений. Сначала выполним вычисление для первого движения:
(а)=(х1+1)2 + (у1+1)2 - R2= (xt)2 + (yj + I)2 - R2= Aj + 2*yt + 1.
X
Аналогичное вычисление можно выполнить и для другого движения:
Л1 + 1 (b) = (x1 + 1 )2+(y1 + 1)2-R2= (Xfl)2 + (У! + I)2 - R2= Ai-ZtXi+gtyi +-2
Для анализа погрешности А1 + 1 вычислим разность погрешностей при движении а" и при "движении Ь":
“ lAjii(a)I (Aj+i(б)
Выбор оптимального движения теперь можно выполнить по знаку величины d1+1. Так. если d1+1 < 0, то следует выполнять "движение а”, в противном случае - "движение Ь". Вычисление dltl можно заменить более простым выражением
сохранив логику выбора движения. Для подтверждения справедливости данного утверждения рассмотрим три случая взаимного расположения точек растра и точек окружности (рис.8). \
Рис. 8
- 18 -
Первый случай - точки растра для "движения а" и движения Ь" лежат пс разные стороны окружности: точка "а" - снаружи, а точка "Ь" - внутри. Тогда >
А1М (а) > 0; Д1 + 1 (Ь) < 0..
Если при этом точка "а" лежит ближе к окружности, тогда сумма A14(a) + A1 + I(b) будет меньше нуля, т.к. |Д1 + 1(а)| < |А1+1(Ь)| и меньшая пэгрешность-положительна . а большая-отрицательна. В случае, когда ближе к окружности лежит точка -"Ь", то указанная сумма будет больше нуля по аналогичным соображениям. Таким образом, при dt + 1 < О выбирается "движение а" с выбором узла, наиболее близко расположенного к окружности. В противоположном случае - "движение Ь".
Второй случай - обе точки растра расположены внутри окружности. Следовательно,
А1 + 1 (а) < 0; А1 + 1 (Ь) < 0.
Тогда сумма Д1+1(а) + А1 + 1(Ь) всегда отрицательна и точка "а" всегда ближе к окружности .по определению (см. рис.8). Значит следует выбирать "движение а".
Третий случай - обе точки растра лежат снаружи окружности. Поэтому
Д1 + 1 (а) > 0; А1 + , (Ь) > 0.
Этот случай симметрично противоположен второму - ' сумма положительна, точка "Ь"'ближе к окружности и выбирается "движение Ь".'
С учетом сказанного и ранее'полученных выражений можно записать
О,, , = Aj + 2*yt + 1 + A; - 2*Xj + 2*yt + 2 = 2*At - 2*Xt < 4*У! + 3.
Последнее выражение позволяет построить процедуру выбора опти-мачьных точек растра (х1+1,у1+1), дающих минимальную погрешность, по чэедыяущйм значениям координат точки (x^yj, значению At и знаку <J, +,. Эффективность процедуры можно повысить за счет организации вы- -числения погрешности d1M по предыдущему значению dj. Для этого выберем начальную точку построения окружности, например, с координатами (Р.Э). Тогда
- 19 -
djи - 2*0 - 2*R +4*0+3 = 3 - 2*R.
Имея значение dltl, можно зачислить dlt2 для "движения а” -и "движения Ь".
di*8(a) - 2*А1 + 1(а) - 2*хО1(а) + 4*yltl(a)^+ 3 -
= 2*(At + 2»yj +1) - 2*Xj + 4*(У! + 1) + 3 =
“ d14.f + 4*yj + 6.
d1+2(b) = 2*Altl(b) - 2*X1 + 1(b) + 4*y1 + 1(b) + 3 =
= 2*(Aj - 2*X; + 2*yj + 2) - 2*(Xj - 1) + 4*(yt +1) + 3= <1t>1 - 4*Xt + 4*yt + 10.
Таким образом, находясь в точке 1, можно вычислить d1+1, определить его знак и выбрать соответствующее движение. Затем вычисляется d14.2, а,по его знаку выполняется выбор очередного движения. Вычисление dlt2 и выбор движения производятся в цикле до конечной точки окружности первого октанта.
В соответствии с изложенным можно записать алгоритм
У : = 0;
х := R;
d : = з - 2*R;
tfhlle х > y<do
begin {вывести точки (x.y); С-х, у): (х,-у); (-х,-у);
(у.х); (-у.х); (у.-х); (-у, -х);1
If d < О then {движение а} d = d + 4*у + 6 else {движение b)
begin
d = d + 4* (у - х) + 1С;
X = х - Д end у - у + 1 end
If х = у then {вывести точки (X,у); (-х, у); (х,-у); (-х.-у);}.
Оценивая достоинства данного алгоритма, можно отметить, что здесь используется целочисленная арифметика, операции сложения', вычитания и
- 20 -
сдвиге. Недостатком является невозможность работы непосредственно с видеопамятью, т.к. приходится выводить сразу 8 точек, расположенных в разных местах экрана. Однако, можно построить процедуру пошаговой развертки всей окружности, если внести соответствующие коррективы в вычислении координат и лбки в различных октантах.
По такой же стратегии можно организовать алгоритм растровой развертки эллипса, при которой отклонение выбранной точки узла будет определяться по отношению к точке, принадлежащей эллипсу, вычисляемой по формуле
аг»хг + Ьг*уг = а?«ьг.
Растровая развертка дуги может быть выполнена по алгоритму Бре-зенхема. При этом параметры ее могут задаваться координатами центра окружности, которой принадлежит данная дуга, и координатами ее концов или начальным и конечным углами концов дуги. При построении растровой развертки дуги возможен вариант того, что начальная точка не совпадает с точкой растра и поэтому начальная погрешность отлична ст нуля, что следует учитывать в процедуре реализации. Кроме того, необходимо точно определить момент окончания вывода точек, чтобы не оказалось Лишних или недостающих элементов.
3. ЗАПОЛНЕНИЕ СПЛОШНЫХ ОБЛАСТЕЙ
3.1. Изображение сплошных областей
Сплошные области могут ограничиваться отрезками прямых (многоу гольники) или произвольным контуром. В связи с этим область может задаваться своими вершинами или ребрами для многоугольников или контуром, представленным его растровой разверткой. Генерация1 сплошных областей носит название растровой развертки сплошных областей и многоугольников или заполнением сплошных областей и многоугольников. Заполнение областей может быть выполнено двумя способами - сканированием строк и затравочным заполнением.
Метод сканирования строк решает задачи определения порядка сканирования, принадлежности точки внутренней области многоугольника или контура. При затравочном заполнении предполагается наличие некоторой точки, принадлежащей внутренней области (затравочная точка),/для которой определяют ее соседние точки и включают ее в список, дрчгих затра
-21-
вочных точек. Список этих точек анализируется с точки зрения необходимости их закрашивания.
Методи сканирования пригодны как для растровых, дисплеев, так и для векторных, а методы затравочного заполнения - только для растровых.
Области могут задаваться внутренне определенным и гранично-определенным способом. Внутренне определенная область соотоит из точек только одного цвета или интенсивности. Пикселы, внешние пс отношению к
Гранично-определенные области имеют контур, состоящий из пикселов с выделенным значением цвета или интенсивности. Внутренние пикселы области отличны от них по цвету или интенсивности, а внешние могут с ними совпадать (рис. 10).
Внутренне и гранично-определенные области могут быть четырех- и
- 22 -
восьмисвязными. В четырехсвязных областях любой пиксел достигается движением по четырем взаимно перпендикулярным направлениям, а восьмисвязные - по восьми: горизонтальным, вертикальным и .диагональным. На
На рис.12 представлены внутренне и гранично-определенные восьмисвязные области.
Рис.12
Следует отметить, что алгоритмы рисования восьмисвязных областей применимы и для четырехсвязных. Обратное несправедливо, т. е. алгоритмы четырехсвязных областей неприменимы для восьмисвязных. Кроме того, границы восьмисвязных гранично-определенных областей должны быть четырехсвязны, а границы четырехсвязных гранично-определенных областей/ -восьмисвязны.
3.2. Алгоритм затравочного заполнения областей
Можно сформировать простейший алгоритм затравочного заполнения
- 23 -
четырехсвязной гранично-определенной области й следующем виде.
var х,у: integer; {координаты затравочной точки)
oldcolor: word; {исходное значение цвета) newcolor: word; {новое значение цвета) framcolor: word; {цвет границы)
begin
помещаем пиксел в Stack;
while (Stack не пуст) do begin
извлекаем пиксел из Stack;
PutPixel(х, у, newcolor);
для точек (хт,ут), соседних с (х,у):
(х+1,у); (х,у+1); (х-1,у); (х;у-1), проверяем условие: if GetPlxel(xT,yT) * newcolor and
GetPlxel(xT.yT) * framcolor then Помещаем txT,yT) в Stack; end end.
Аналогично строится алгоритм и для внутренне определенной области. В этом случае меняется только условный оператор, который должен проверять принадлежность соседних точек и наличие неизмененного цвета. Тогда внешний блок описанной процедуры будет иметь вид begin
помещаем пиксел в Stack;
while (Stack не пуст) do begin
извлекаем пиксел из Stack;
PutPixel (х, у, newcolor);
для точек (хт,ут), соседних с (х,у):
(х+1,у); (х.у+1); -(х-1,у); (х;у-1), проверяем условие: if GetPixel(xT,yT) = oldcolor then помещав^ (хт,ут) в Stack;
end end.
- 24 -
Предложенные алгоритмы легко обобщаются на случай вссьмисвязных обмет eft. для которых необходимо выполнять Анализ восьми соседних точек.
Процедура затравочного заполнения областей, описанная выше, обладает двумя недостатками: стек заполняется большим количеством повторяющихся точек, что приводит к существенным временным затратам при их анализе и, как следствие, требуется стек большого объема. Однако эти проблемы легко разрешить изящным методом перестановки местами операций помещения точек в стек и их закраски. Тогда процедура будет записана следующим образом.
begin
PutPlxel(х,у.newcolor);
помещаем пиксел в Stack;
while (Stack не пуст) do begin извлекаем пиксел (х, у) из Stack: для точек (хт.ут)', соседних с (х.у): (х+1,у); (х.у+1); (х-1.у); (х;у-1). проверяем условие: If GetPlxeKXj.yj) * newcolor and
GetPlxeHXj.y.j) * fraincolor then begin
PutPlxel(хт,у^,newcolor);
помещаем (хт,ут) в Stack end
end end.
Другой метод повышения эффективности затравочного .заполнения областей заключается в организации построчного заполнения непрерывного интервала на сканирующей строке с одной затравочной точкой. Непрерывный интервал точек образуется примыкающими друг к другу соседними пикселами и ограничивается либо уже заполненными точками, либо границами области. Алгоритм применим для четырехсвязных гранично-определенных областей, которые могут быт выпуклыми, невыпуклыми, сплошными или содержащими дыры. При это’ должно соблюдаться условие отсутствия во внешней области, примыкав дей к границе, пикселов с цветом заполнения.
- 25 -
Идею алгоритма можно сформулировать следующим образом:
1°. Затравочная точка (х,у) помещается в стек.
г". Если стек не пуст, то извлекается точка из стека, и влево и ‘ вправо от «ае формируется непрерывный интервал до границы области. В противном случае - переход к п. 5".
3*. Запоминается крайняя левая точка интервала хлев и крайняя правая хправ (или xl и хг);
4П. 8 диапазоне интервала xl < х < хг в строках (у + 1) и (у - () отыскиваются незаполненные пикселы, образующие непрерывные интервалы. В каждом интервале крайний правый пиксел считается затравочным и помещается в стек. Переход к п. 2°
5°. Окончание процедуры.
Более подробно и формализовано предложенную идею можно изложить в следующем виде: begin
помещаем затравочную точку (х.у) в стек;
while (стек не пуст) ДО
{извлекаем (х,у) из стека, закрашиваем и заполняем интервалы слева и справа с запоминанием крайних точек)
begin
извлекаем (х, у) и’з стека;
PutPlxel (х, у, newcolor); xt := х;
{заполняем интервал справа) X := х + 1; ' .
while ((х.у) * fram) do begin
PutPlxelXx,у.newcolor); x := x + 1:
end
{запоминаем правый пиксел)
xr : = x - 1;
{восстанавливаем x)
x : = xt;
{заполняем интервал слева)
х : - х “ 1;
while ((X,у) * fram) do
begin
- 26 -
PutPixel(x, у, newcolor); x := x - 1; end {запоминаем левый пиксел} xl := х + 1; {восстанавливаем х} х : = xt:
{обработка строки у = у + 1 с определением затравочной точки)
х : = xl; у у + 1; while х < xr do begin
F : = 0; {флаг} while (((х,у) * fram) arid ((x.y) ? newcolor) and (x < xr)) do
begin If F = 0 then F 1; x := x + 1 end end begin -
If F l4then
If (x = xr and (x,y) * fram and (x.y) * newcolor) then помещаем (x.y) в стек else помещаем (x - l,y) в стек:
F 0; end xO x;
while ((x.y) = fram or (x.y)' = newcolor and x < xr) x :=x + 1;
if x = xO then x . = x + 1; обработка- строки у = у - 1; end end.
Представляет интерес сравнение алгоритмов затравочного заполнения (второй вариант) и затрайочного интервального с точки зрения эффективности.
- 27
3.3. Растровая развертка многоугольников
Алгоритм основан на построчном сканировании многоугольника с верхней его вершины до нижней. При, этом производится заполнение многоугольника по сканируемым строкам. Рассмотрим характер пересечения сканирующей строки с многоугольником (рис. 13).
Сканирующая строка разбивается многоугольником на пять интервалов в точках 1, 4, 7. 10. Необходимо выделить на сканирующей строке точки, принадлежащие внутренней области многоугольника. Из рисунка видно, что внутри многоугольника лежат точки интервалов (х, - х4) и (х7 - х10). Если вычислить - х-координаты точек пересечения сканирующей строки и упорядочить их по возрастанию, то нечетные интервалы будут лежать во внутренней области многоугольника. Тогда процедура сканирования и поиска точек закрашивания может иметь следующий вид:
1°. Находятся х-координаты всех точек пересечения сканирующей строки с ребрами многоугольника.
2°. Х-координаты упорядочиваются по возрастанию.
3°. Закрашиваются точки в нечетных интервалах...
Однако алгоритм требует уточнения для двух частных случаев.
Первый случай - пересечение сканирующей строки с горизонтальным ребром (рис. 14).
Рис. 14
- 23 -
В этом случае имеется бесконечное множество точек пересечения ребра со сканирующей строкой. В связи с этим понятие четных и нечетных интервалов теряет смысл. Для решения задачи следует рассмотреть- пересечение-сканирующей отроки не с ребром а с ребрами и l1 + j. Пересечения этих ребер со онанирующей строкой дают точки Pj и ₽i,i. При этом образуется только,один интервал, он же и нечетный.
Второй случай - пересечение сканирующей строки о вершиной многоугольника (рис.. 15).
В процессе нахождения точек пересечения сканирующей строки с ребрами многоугольника точка Pt будет найдена дважды - как пересечения с ребрами и ii-i Этот Факт нарушает процедуру нахождения интервалов, принадлежащих внутренней области многоугольника. Для устранения этой проблемы необходимо укоротить одно из смежных ребер lt или Ij-j на одну точку - вершину Pt. Однако, возможен случай пересечения сканирующей строки с вершиной многоугольника, при котором выполняются иные действия. Этот случай приведен на рис. 16.
Pi
Рис. 16
Пересечения сканирующей'строки с ребрами и также дают две точки Xpj и хР1. которые образуют интервал хР1 - хР1. состоящий из одной точки. Но в этом случае, не нарушается процедура, изложенная в алгоритме, в связи с чем не требуется никаких дополнительных действий. Таким образом, следует различать случи пересечения сканирующей стро
- 2° -
кой вершины многоугольника, не являющейся локальным экстремумом (первый вариант), и вершины, являющейся лекальным экстремумом (второй вариант) . Выделение локального экстремума можно выполнить сравнением у-координат вершины и двух точек, принадлежащих смежным' ребрам. Если у-координата вершины больше у-координат смежных точек, то имеет место случай локального минимума, в противном случае - локального максимума. Максимум и минимум понимаются здесь с точки зрения, экранной системы координат. Таким образом, необходимо выполнить проверку всех вершин многоугольника и для тех вершин, которые не являются локальными экстремумами, производится укорочение одного из смежных ребер на одну т'очку.
Нахождение х-координат точек пересечения сканирующей строки с ребрами многоугольника можно выполнить по уравнению прямой. Процедуру нахождения этих точек можно организовать итерационным методом, для чего необходимо задать конечные точки ребер. • Тогда вычисления будут выполняться в соответствии со следующими выражениями
I
х1+1 = xi +
, хк - хи m -------------;
Ук - Ун
где хк.ун.хкун - координаты концевых точек ребра.
Для реализации алгоритма вводится понятие активных ребер. Это такие ребра многоугольника, которые пересекаются сканирующей строкой. При последовательном сканировании экрана сверху вниз список активных ребер меняется за.счет добавления новых или удаления некоторых ребер из
этого списка. Изменения списка происходят в моменты прохождения сканирующей строки через вершины ребер, причем прохождение через-максимальную у-координату ребра делает,его активным, а через минимальную у-кс ординату - исключает это ребро'из списка активных ребер.
Активные ребра содержатся в таблице активных ребер (ТАР), которая имеет следующую структуру записей для каждого ребра:
1 - номер ребра, , .
Утах _ максимальное значение у-координаты ребра, х -. текущее значение х-координаты пересечения сканирующей строки с ребром,
ш ' - приращение х-координаты для данного ребра.
- 30 -
С учетом изложенного можно сформировать алгоритм обработки очередной сканирующей строки 1.
'Л. Включить в ТАР ребра, для которых 1 - увах.
2°. Упорядочить записи ТАР по возрастанию значений х-координат.
3°. Закрасить нечетные интервалы между точками пересечений.
4°. Исключить из ТАР ребра, для которых 1 - увах.
5°. Вычислять х = х + го.
6°. Получить новый номер сканирующей строки 1-1 + 1.
Кроме ТАР существует еще таблица ребер (ТР). которая состоит из всех ребер данного многоугольника, она имеет другую структуру записей:
1 - номер ребра,
ув1п - минимальная у-координата ребра.
увах - максимальная у-координата ребра,
х„1п - х-координата ребра, соответствующая координате ув1п, го - приращение х-координаты для данного ребра-
ТР должна быть упорядочена по возрастанию ув1в, а при наличии ребер с одинаковыми ув1г они упорядочиваются по возрастанию Хп1п. Это упорядочивание позволяет при поиске активных ребер сравнить номер 1 сканирующей строки со значением у:п1п первой записи ТР. Если при этом 1 < Ут11>, то добавляем новую запись р ТАР а из ТР удаляем первую запись-. Затем выполняется очередное сравнение о первой записью ТР. Окончательно алгоритм растровой развертки много- ’'ельников будет следующим.
1°. Перебор всех вершин многоугольник;. с укорочением одного из смежных ребер для вершин, не нвляклох.-о локальными экстремумами. .
2°. Поиск и удаление горизонтальных ре>
3°. Построение упорядоченной ТР.
4°. Принимают первоначальное значение 'им.-ра сканирующей отроки
1 равной ув1п первой записи ТР.
, 5°. ^Создается пустая ТАР.
6°. выполняется обработка сканирующей строг;;. .
7°...Пока ТАР или ТР не пусты, выполняется переход к п. 6°..
8°. Окончание процедуры.
Эффективность полученного алгоритма м <но повысить за счет закраски интервалов многоугольника через обра ние к видеопамяти.
- 31 -
3.4. Растровая* развертка круга
Растровую развертку круга можно построить с помощью алгоритма Брезенхема для первого октанта. При этом использование симметричности точек окружности позволяет организовать заполнение четырех интервалов со следующими координатами:
- первый интервал - (-у.х) - (у.х);
- второй интервал - (-х,у) - (х,у);
- третий интервал - (-х,-у) - (х,-у);
- четвертый интервал - (-у,-х) - (-у.х).
На рис.17 показаны полученные интервалы.
Рис. 17
Следует выделить граничные ситуации; когда (х.у) = (R, 0)’ или
(х.у) = (R//7.R//2).
В первом случае интервалы вырождаются в горизонтально расположенный диаметр окружности и в две точки с координатами (0.R) и (0.-R). Во втором случае получается только два интервала:
первый - (-R//2.R// 2) - (R//2, R//J).
второй - (Н?/)Л2.-R//2)Z -R/i/~3).
Кроме того, при реализации алгоритма необходимо учитывать выбор узла растра при "движении а" и "движении Ь", так как в первом случае __ . меняется только координата у, а координата х остается неизменной.• Во ’ втором случае меняются обе координаты. Это приводит к тому, что интервалы, расположенные во 2, 3. 6 и 7 октантах - ((-у.х) - (у.х)) и
- 32 -
((-у.(-У.Х)'), при "движении а" совпадают с предыдущими интервалами по первой координате и большее по оцной- точке с каждого конца-по второй координате. Это приводит к тому, что приходится повторйо заполнять интервал, а при выводе линии в инверсных режимах- (отили XOR или NOT) ранее заполненный интервал будет стерт. С учетом сказанного алгоритм растровой развертки круга можно сформулировать в следующем виде:
У : = 0;
х R;
d :- 3 - 2*R;
while х > у do
begin
заполняем интервалы в 1, 4, 5, 8 октантах:
((-х,у). - (х, у)), ((-х,-у) - (х,-у));' if d < 0 then {движение а)
d : = d + '4*у + 8;
else
begin {движение Ы
заполняем интервалы в 2, 3, 6, 7 октантах: ((-У.X) - (У„Х)), ((-у,-х) - (у.-х));
d :•= d + 4*(у - х) + 10;
х := х - 1 end
У := У + 1;
end
4. ОПЕРАЦИИ С ФРАГМЕНТАМИ ИЗОБРАЖЕНИЙ
Обработка изображений может сопровождаться с необходимостью выполнения операций с отдельными их частями - фрагментами, которые могут сохраняться в памяти, а затем воспроизводиться на экране. Такие задачи возникают при построении динамических изображений, в игровых программах, Мультипликации и в других случаях. Эти операции возможны и с текстовой информацией. Выполнить их можно процедурами Getlmage и Putl-mage. Обычно, для простоты операций, фрагменты выбирают прямоугольной формы и задают их координатами вершин, расположенных по диагонали, как показано на рис. 18.
- 33 -
(Xmln' УлЦп)
(Xna»' Ушах)
РИС.18
Сохранение прямоугольного фрагмента в памяти выполняется путем запоминания его размеров и значения яркости каждой точки фрагмента. При этом структура данных имеет следующий вид:
type
Image - record
W: Integer; {ширина фрагмента)
H: Integer;. {высота фрагмента)
ЙиГ: array [0. .Н-1,0. ,W-1] of O..MaxColor;
end
Такой фрагмент можно запоминать, последовательно считывая значения яркости всех точек с помощью процедуры Getlmage, в массиве Buf:
W xmax - xmln +1;
Н := ymax - ymln + 1;
for 1 := 0 to H-l do
Tor J := 0 to W-l do ,
Bufli.J) := GetPlxel(xmln + J, ymln + 1).
Воспроизведение записанного Фрагмента выполняется аналогично через процедуру PutPlxel. При этом оледует учитывать размеры фрагмента и область вывода так, чтобы он 1не выходил за границы экрана. Описанный метод обработки фрагментов изображения является недостаточно эффективным из-за того, что каждая точка экрана для сохранения требует одного байта памяти, а также из-за выполнения большого числа обращений к процедурам GetPlxel и PutPlxel.. Каждое такое ’обращение к названным процедурам содержит операции вычисления адресов видеопамяти и является достаточно сложным по числу вычислений.
Более эффективным методом является способ сохранения фрагмента
- 34 -
и;, отражения в виде массива строк, каждая из-которых имеет структуру строк видеопамяти, т.е. каждой точке соответствует один бит пц^яти, а игроки записываются в последовательность байт. Для сохранения одной строки черно-белого изображения требуется k-байт памяти;
k = ((xmax -.xmln +1) + 7) div 8 = (xmax - xmln) div 8+1.
В этом случае фрагмент изображения можно описать структурой
type
Image = record
W: integer;
Я; Integer;
Buf: array[0. .H-1,0. .K-l] of byte end
Рассмотрим операцию копирования упакованных строк фрагмента. Вводятся упакованные строки источника и приемника.
LS: array! ] of byte; {строка-источник}
• LD: array! ] of byte; {строка-приемник}
В общем случае требуется скопировать биты строки LS, начиная с номера XS1 и кончая номером XS2, в биты ‘строки LD с номера XD1 (рис.19).
Задача решается эффективно при копировании группами бит, упакованных в байты. Процедура выполняется с использованием операций маскирования и сдвига.
- 35 -
5. ИЗОБРАЖЕНИЕ РАСТРОВЫХ ШРИФТОВ
Хранение и отображение на экране литер может^быть выполнено двумя методами - растровым и векторным. При растровом.методе литеры представляются в виде фрагментов образов фиксированного размера. Вывод этих образов на экран возможж процедурой аналогичной процедуре Putlmage. Полный набор символов хранится обычно в одном файле, в котором литеры расположены последовательно одна за другой. Для выбора необходимого символа по его коду определяется местоположение образа, который выводится в требуемую точку экрана. Размеры литер могут быть стандартными 8x8, 8 х 14, 9 х 16 или произвольного формата. На рис. 20 показан фрагмент Файла, хранящего символы размером 8x8.
Векторный метод формирования символов заключается в построении процедуры вычерчивания отрезков (векторов), составляющих изображение символа. При этом используются процедуры MoveTo, LlneTo и другие.
6. ПОРЯДОК ВЫПОЛНЕНИЯ РАБОТЫ И ВЫРИАНТЫ ЗАДАНИЙ
по выданному преподавателем варианту составляемся программа реализации требуемых алгоритмов растровой графики и выполняется ее отлад
- 36 -
ка. Отчет по работе должен содержать задание, текст программы, ее содержательное краткое описание и качественный анализ преимуществ и недостатков использованных алгоритмов, а также возможные пути повышения их эффективности. Задание включает в себя разработку программы по реализации трех алгоритмов растровой графики. Первый алгоритм предполагает выполнение растровой развертки отрезка по алгоритму Брезенхема с использованием процедуры PutPixel модуля Graph или ее организацией через видеопамять. При этом отрезок строится в заданном октанте из точки начала декартовых координат в произвольную точку в пределах выделенного октанта. Второй алгоритм предусматривает растровую развертку окружности, дуги или круга. Дуга должна начинаться в произвольной точке одного октанта и заканчиваться в' произвольной точке соседнего октанта, как определено заданием. Радиус окружности выбирается произвольно. И, наконец, трзтий алгоритм заключается в растровом заполнении сплошных областей и многоугольников или обработке фрагментов изображений и разработке растровых фонтов. Кроме этого, каждый студент должен добавить по одному из заданных алгоритмов альтернативный алгоритм для выполнения качественного их сравнения по быстродействию и точности решения задачи. Для этого необходимо предусмотреть в программе выполнение процедуры сравнения. В качестве альтернативных алгоритмов можно взять для растровой развертки отрезка простой алгоритм развертки, для растровой развертки окружности или дуги алгоритм развертки по формуле хг + ys = R’ или с помощью построения вписанного многоугольника с достаточным числом сторон, или построение окружности с использованием полярных координат. Для затравочного заполнения сплошных областей сравнение можно выполнить с затравочным алгоритмом по первому варианту. Выбор альтернативного алгоритма выполняется студентом самостоятельно.
Для растровой развертки отрезка предусматриваются следующие варианты, номера-которых располагаются в клетках табл. 1.
Таблица 1
Способ реализации прорисовки точек на экране Номера октантов
2 3 4 5 6 7 ’ 8
Применение PutPixel 0 , 2 4 \6.' 8 10 12
Работа с видеопамятью 1 3 5 7 9 И
- 37 -
Выбор второго алгоритма следует делать по табл; 2.
Таблица 2
Элемент развертки Вариант реализации
Окружность Октант, с к-рого нЧч-ся окр-ть
, 3 4 5 6 7 8
;о - 1 2 4 5 6
Дуга - Октанты
1-2 2”3 3-4 4-5 5-6 6-7 7-8 8-1
'7 8 9 10 11 12 13 14
Круг Части круга
1 2 3 4 5 6 7 8
15 16 17 18 19 20 21 22
Растровая развертка круга предполагает реализацию одной из его частей, пронумерованных в табл.' от 1 до 8, которые образуются делением коуга горизонтальными линиями, с шагом d/8. Первая часть находится вверху, восьмая - внизу. Табл. 2 содержит 23 варианта, из которых варианты 0-6 относятся к окружности, 7 - 14 - к дуге, а 15 - 22 - к кругу.
Для третьего алгоритма предусмотрено восемь следующих вариантов заданий:
’ нулевой - затравочное заполнение 4-связной гранично-определенной области;
первый - то же для внутренне-определенной'области;
второй - затравочное заполнение 8-связной граничнотопределенной области; 1
третий - то же для внутренне определенной области;
-Четвертый - постро"ное заполнение 4-связной гранично-опредзленной области;
пятый - .растровая развертка многоугольника;
шестой. - обработка фрагментов;
седьмой - создание растровых фонтов.
Для первых пяти вариантов необходимо выбирать сплошные области
- 38 -
произвольно. Для.многоугольника предусмотреть наличие всех частных случаев - горизонтальное ребро, вершины с экстремумом и бвз него. Фрагменты выбрать поямоугольной формы, обработка по битам, а в качестве альтернативного варианта можно взять обработку по байтам. .Цля фонтов достаточно организовать файл с несколькими символами, с помощью которых можно выполнять набор текста.
Выбор конкретйого алгоритма студентом выполняется следующим образом. Номер задания, полученный от преподавателя, делится на 14. Остаток от дел_ения дает номер варианта по первому алгоритму. Аналогично делится исходный номер задания на 23. и остаток определяет номер варианта по второму алгоритму. И, наконец, третий алгоритм определяется делением номера, задания на 8, а остаток дает последний вариант.
ЛИТЕРАТУРА
1. . Роджерс Д. Алгоритмические основы машинной графики. М.: Мир, 1989. 504 С
2. Турбо Паскаль. Руководство пользователя. Модуль GRAPH. Документация по программному обеспечению.
3. Павлидис Т. Алгоритмы машинной графики и обработки изображений. ’ М.: Радио и связь, 1986.
4. Фоли Дж., А. вэн Дэм. Основы интерактивной машинной графики. КН. 1. М.: Мир, 1985. ' •
5. -Фоли Дж.. А. вэн Дэм. Основы интерактивной машинной графики. Кн.2. М.: Мир, 1985.
6. Роджерс Д., Адамс Дж. Математические основы машинной графики. И.: ’Мир. 1989.
7. Аммерел Л. Принципы программирования в машинной графике /Пер. с англ. М.: "Сол Систем", 1992.
8. Аммерал Л. Машинная графика на персональных компьютерах /Пер. с англ. М.: "Сол Систем", 1992.
9. Аммерал Л. Интерактивная трехмерная машинная графика / Пер. с англ. М.: "Сеч систем", 1992.
10. Аммерал л. Программирование графики на Турбо Си. /Пер. с англ. М.: "Сол-Систем", 1992. •
11. Фролов А.В..Фролов Г.В. Программирование видеоадаптеров CGA, EGA и VGA. М.: "Диалог-МИФИ", 1992. 287 с.
12. Начала компьютерной графики; Под ред. Шикина Е.В. М.: "Диа
- 39 -
лог-МИФИ", 1993. 138 с.
13. Справочник по видеосистемам IBM PC & IBM PS/2. Адаптеры CGA.EGA и VGA. Руководство программиста. Р.А.Ашинянц и др. М.: КомпьютерГайд, 1993. 127 с.
14. Селянкин В.В.Введение в компьютерную графику:Руководство кла лабораторным работам.Таганрог: ТРТУ,1994.В 2150.
Содержание
Введение 3
1. Растровая развертка отрезков 5
1.1. Работа с отрезками прямых 5
1.2. Простой пошаговый алгоритм 6
1.3. Универсальный простой алгоритм 7
1.4. Алгоритм Брезенхема 8
1.5. Растровая развертка через видеопамять 13
2. Растровая развертка окружности 14
2.1. Алгоритмы растровой развертки окружности 14
2.1. Алгоритм Брезенхема для окружности 15
3. Заполнение сплошных областей 20
3.1. Изображение сплошных областей 20
3.2. Алгоритм затравочного заполнения областей 23
3.3. Растровая развертка многоугольников 27
3.4. Растровая развертка круга 30
4. Операции с фрагментами изображений 33
5. Изображение растровых шрифтов 35
6. Порядок выполнения работы и варианты заданий 36
Ли тература 38