*

x - x - T Sin 0,

0 *

y - x tg +T

Последние три равенства будем называть формулой Бьюнемана.

Алгоритмы растровой графики

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

4-Ф-

Рис. 28. Растеризация отрезка прямой линии.

Термин "пиксел" образован от английского pixel (picture element -элемент изображения) - то есть точка на экране. Будем считать, что пикселы имеют целочисленные координаты. На первый взгляд кажется, что эта задача имеет простое решение. Пусть конечные точки отрезка имеют целочисленные координаты, и уравнение прямой, содержащей отрезок: y - kx + b. Не

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

достаточно для всех целых x, принадлежащих отрезку, выводить на экран точки с координатами (x, Round(y)). Однако в этом методе присутствует

операция умножения kx. Хотелось бы иметь алгоритм без частого использования операции умножения вещественных чисел. Избавиться от

операции умножения можно следующим образом. Поскольку k = AyAx, то

один шаг по целочисленной сетке на оси x будет соответствовать Ax = 1. Отсюда получаем, что y будет увеличиваться на величину k . Итерационная

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

xi+1 = xi + yi+1 = yi + k

Когда k > 1, то шаг по x будет приводить к шагу по y > 1, поэтому x и

y следует поменять ролями, придавая y единичное приращение, а x будет

увеличиваться на Ax = Ayk = /k единиц. Этот алгоритм все же не свободен

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

Для вывода формул алгоритма Брезенхема рассмотрим рис. 29.

Pi-i=(r,q) Ti=(r+i,q)

Рис. 29. Рисование отрезков прямых по методу Брезенхема.

Пусть начало отрезка имеет координаты (x1, y1), а конец (x2, y2). Обозначим dx = (x2 - x1), dy = (y2 - y1). Не нарушая общности, будем считать, что начало отрезка совпадает с началом координат, и прямая имеет

вид y = -x, где - е [0,1]. Считаем что начальная точка находится слева.

Пусть на (i - 1)-м шаге текущей точкой отрезка является Pi-1 - (r, q). Выбор следующей точки Si или Ti зависит от знака разности (s -1). Если (s -1) < 0, то Pi - Ti - (r +1, q) и тогда xi+1 - xi +1, yi+1 - yi, если же (s - t) > 0, то

Pi - Si -(r +1 q +1) и тогда xi +1 - xi +1, yi+1 - yi +1.

s - (r + 1)-q, t - q + 1 - d-(r + 1), ==

OL/vOL/v

s -1 - 2 - (r + 1)-2q -1 => <x

dx(s - t) - 2(r • dy - q dx) + 2dy - dx.

Поскольку знак dx(s -1) совпадает со знаком разности (s -1), то будем проверять знак выражения di - dx(s -1). Так как r - xi-1 и q - yi-1, то di+1 - di + 2dy - 2dx(yt - yt-1).

Пусть на предыдущем шаге di < 0, тогда (yi - yi-1) - 0 и di+1 - di + 2dy. Если же на предыдущем шаге di > 0, то (yi - yi-1)-1 и di+1 - di + 2(dy - dx).

Осталось узнать как вычислить d1. Так как при i -1:

(x0,y0 )-(0,0), = d1 - 2dy - dx .

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

Procedure Bresenham(x1,y1,x2,y2,Color: integer); var

dx,dy,incr1,incr2,d,x,y,xend: integer;

begin

dx:= ABS(x2-x1); dy:= Abs(y2-y1);

d:=2*dy-dx;{начальное значение для d}

incr1:=2*dy;{приращение для d<0}

incr2:=2*(dy-dx); {приращение для d>=0} if x1>x2 then {начинаем с точки с меньшим знач. x} begin x:=x2;

y:=y2;

xend:=x1;

end