65

14.Алгоритмы вывода графических примитивов

Вид занятия – лабораторная работа Цель – исследование простейших графических алгоритмов

Продолжительность – 4 часа

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

Например, в Delphi для закрашивания любого пикселя холста (класс TCanvas) применяется свойство:

property Pixels[X, Y: Integer]: TColor;

где X и Y – горизонтальная и вертикальная координата пикселя.

При графическом выводе стоит иметь в виду, что по умолчанию координатное пространство Windows берёт начало в верхнем левом углу окна. Ось X направлена слева направо, ось Y сверху вниз (см. рис. 14.1).

Рисунок 14.1. – Координатное пространство Windows

Рисование отрезка

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

Перед рассмотрением конкретных алгоритмов сформулируем общие требования к изображению отрезка:

1.концы отрезка должны находиться в заданных точках;

2.отрезки должны выглядеть прямыми.

66

Предположим, что заданы координаты концов отрезка (x1,y1) и (x2,y2). Если x1=x2 (вертикальная линия) или y1=y2 (горизонтальная линия), то для вывода отрезка достаточно обращения к подобным строкам кода:

for y:=y1 to y2 do

Form1.Canvas.Pixels[x,y]:=clBlack;

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

Каким образом Windows принимает решение на закрашивание того или иного пикселя при выводе линии? Поверьте, это совсем не праздный вопрос. Судите сами. Если линия строго горизонтальна или вертикальна, то всё ясно. Проводя отрезок из точки (1,10) в точку (1,100) пером единичной толщины Windows не притрагиваясь к координате X, даёт последовательное приращение координате Y. Задействуются точки: (1,10), (1,11), (1,12), …, (1,99). Но какие пиксели потребуются для прорисовки наклонной линии, допустим проходящей из точки (10,10) в точку (140,180)? С стопроцентной точностью можно утверждать только то, что координаты первого используемого пикселя равны (10,10). Определить координаты следующей точки “на глаз” уже сложнее. Ими, с какой-то степенью вероятности, могут оказаться пиксель (11,11) или пиксель (10,11). А о координатах 50-й по счёту точки вообще допустимо говорить лишь приблизительно. Взгляните на рисунок 14.2, на нём показано, что для вывода казалось идентичных линий могут быть задействованы разные группы пикселей.

Рисунок 14.2. – Варианты вывода наклонной линии

Ни одно из требований к изображению отрезка не может быть точно выполнено на растровом дисплее в силу того, что изображение строится из пикселей конечных размеров. Отрезок аппроксимируется набором пикселов и лишь в частных случаях (вертикальный отрезок, горизонтальный отрезок, отрезок под углом 45°) он будет выглядеть прямой, причем гладкой прямой, без ступе-

нек (рис. 14.2).

Прямое вычисление координат

Рассмотрим простейший способ вычисления координат закрашиваемых пикселей. Пусть заданы координаты начальной (x1,y1) и конечной (x2,y2) точек отрезка (см. рис. 14.3).

(0,0) x1 x x2

y1

y y2

Рисунок 14.3. – Отрезок прямой

67

Запишем отношения катетов для подобных треугольников:

x − x1	=	x2		− x1
y − y		y	2	− y	(13.1).
1				1

Тогда расчёт координат точки будет следующим:

x = x	+( y − y )	x2 − x1				y = y	+(x − x )	y2 − y1
1	1	y	2	− y	(14.2),	1	1	x	2	− x	(14.3).
				1						1

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

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

Инкрементный алгоритм Брезенхэма

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

Основная идея алгоритма Брезенхэма состоит в следующем. При черчении виртуальной прямой из точки (x1,y1) в точку (x2, y2) перед принятием решения на закрашивание очередного пикселя мы вычисляем угловой коэффициент прямой. Если угловой коэффициент прямой меньше 0.5, то естественно точку, следующую за точкой (0,0), поставить в позицию (1,0) (рис. 14.4 а), а если угловой коэффициент больше 0.5, то - в позицию (1,1) (рис. 14.4 б).

Рисунок 14.4. – Исследование углового коэффициента прямой

Для принятия решения куда заносить очередной пиксель вводится величина отклонения Е точной позиции от середины между двумя возможными растровыми точками в направлении наименьшей относительной координаты. Знак Е используется как критерий для выбора ближайшей растровой точки.

Для демонстрации вычисления Е положим, что рассматриваемый вектор начинается в точке (x1,y1)=(0,0) и проходит через точку (x2,y2)=(4,1.6), т.е. имеет положительный наклон меньший 1 (см. рис. 14.5).

68

Рисунок 14.5. – Вектор начинается в точке (0,0) и проходит через точку (4, 1.6)

Из

рисунка

видно, отклонение для 1

шага: E1 = Py / Px −1/ 2 < 0 , (где

Py

= y2 − y1

и

Px

= x2 − x1 ) поэтому для занесения пикселя выбирается точка (1,0). Отклонение для 2 шага вы-

числяется

добавлением

приращения

Y-координаты для

следующей

X-позиции.

E2

= E1 + Py / Px > 0 поэтому для занесения пикселя выбирается точка (2,1). Так как отклонение

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

вычисления

последующих

отклонений надо вычесть единицу: E2

= E2 −1.

Отклонение

для

третьего шага: E3 = E2 + Py / Px < 0 поэтому для занесения пикселя выбирается точка (3,1)., и т.д.

Ядро алгоритма Брезенхэма представлено в следующем листинге:

var X1,Y1,X2,Y2,X,Y:integer; py,px,i,e : integer;

begin

X1:=10; Y1:=45; X2:=100; Y2:=80; //значения координат X:=X1; Y:=Y1; Px:=X2 - X1; Py:=Y2 - Y1;

E:= 2*Py - Px;//можно заменить E:= Py+Py - Px; i:= Px;

Form1.Canvas.Pixels[x,y]:=clBlack;		//1-я точка вектора
while i>= 0	DO
begin	0) then
if (E >=
begin

INC(X); INC(Y);

E:= E + 2*(Py - Px);// можно написать так E:= E + (Py - Px)+ (Py - Px); end else

begin

INC(X);

E:= E + 2*Py;//можно написать так E:=E+Py+Py end;

Form1.Canvas.Pixels[x,y]:=clBlack; //очередная точка DEC(I);

end; end;

Этот алгоритм пригоден для случая 0 < dY < dX. Чтобы реализация алгоритма Брезенхема была полной, необходимо обрабатывать отрезки во всех октантах. Модификацию легко сделать, учитывая в алгоритме номер квадранта, в котором лежит отрезок и его угловой коэффициент. Когда абсолютная величина углового коэффициента больше 1, y постоянно изменяется на единицу, а