ALL

АЛГОРИТМ ПОСТРОЕНИЯ ПРЯМЫХ ЛИНИЙ БРЕЗЕНХЕМА

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

•АЛГОРИТМ БРЕЗЕНХЕМА можно адаптировать для изображения окружностей и другие кривых.

•На рис. 1 и 2 показаны части экрана дисплея, в которые рисуются прямолинейные отрезки.

Рис. 1. начало в пикселе, находящемся в ст. 10 и в стр. 11

Рис. 2 тангенс угла наклона < 0, начало в пикселе в ст. 50 и стр. развертки 50

•По вертикальной оси откладывается номер строки развертки, по горизонтальной — номер столбца пикселей.

•В этих примерах по координате x берется интервал =1, и на каждом шаге выборки определяется, какое из двух возможных положений пикселей ближе к прямой.

•На рис. 1, нужно для каждом последующей точки выборки решают, изображать пиксель с координатами (11, 11) или пиксель с координатами (11, 12).

•Аналогично на рис. 2 показано направление прямолинейного отрезка, левый конец которого находится в пикселе с координатами (50, 50). Здесь нужно выбрать координаты следующего пикселя: (51, 50) или (51, 49).

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

АЛГОРИТМ ПОСТРОЕНИЯ ПРЯМЫХ ЛИНИЙ БРЕЗЕНХЕМА

•Для иллюстрации метода Брезенхема рассмотрим процесс преобразования стандартов развертки для прямой с положительным тангенсом угла наклона, меньше 1,0 (0 <m <1).

•В этом случае положения пикселей на прямой определяются разбиением на единичные интервалы по координате x.

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

•На рис. показан k-й шаг этого процесса. Предположим, определен пиксель с координатами

(хk, уk). Необходимо решить, какой пиксель должен изображаться в столбце хk+1 = хk + 1. Выбор нужно сделать из пикселей с координатами (хk + 1, yk) и (хk + 1, yk + 1).

•

Рис. 3 в столбце xk и строке развертки yk. который будет изображаться в качестве продолжения прямолинейного отрезка с наклоном 0 < m < 1

•Рис.4 Расстояние по вертикали между положениями пикселей и координатой прямой у в точке выборки хk +1

•В точке выборки с координатами хk +1 обозначим расстояния по вертикали от пикселей до математической прямой как dlover и dupper (рис. 4). Координата у математической прямой в столбце пикселей хk +1 находится как

• y = m (хk +1)+b.		(10)
•	Тогда dlover = y – yk = m (хk +1)+b – yk.	(11)
•	и dupper = (yk+1) – y = yk+1 – m (хk +1)+b.	(12)

АЛГОРИТМ ПОСТРОЕНИЯ ПРЯМЫХ ЛИНИЙ БРЕЗЕНХЕМА

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

• dlover – dupper = 2 m (хk +1) – 2yk +2b – 1.

(13)

•Параметр принятия решения pk для k-го шага алгоритма построения прямой линии находится путем такого преобразования уравнения (13), чтобы в него входили только целочисленные расчеты.

•Это можно сделать, проведя замену m = y/ x,

•где y и x – вертикальные и горизонтальные расстояния между концами отрезка

•и вычислить параметр принятия решения как

• pk = x(dlover – dupper) = 2 y xk – 2 x yk + c.

(14)

•Знак параметра pk будет таким же, как и знак dlover – dupper, поскольку в примере x > 0.

•Параметр с – это постоянная со значением 2 y + x (2b – 1), которая не зависит от координат пикселя и находится в ходе рекурсивных вычислений, необходимых для расчета pk .

1.Если пиксель с координатой yk окажется "ближе" к реальному направлению прямой, чем пиксель с координатой yk + 1 (те. dlover < dupper), то параметр принятия решения pk будет отрицательным.

2.В этом случае на график наносится нижний пиксель. В противном случае наносится верхний пиксель.

АЛГОРИТМ ПОСТРОЕНИЯ ПРЯМЫХ ЛИНИЙ БРЕЗЕНХЕМА

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

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

•На шаге k+ 1 параметр принятия решения находится из уравнения (14) как

•pk+1 = 2 y xk+1 – 2 x yk+1 + c

•Вычитая уравнение (14) из предыдущего уравнения, получим

•pk+1 – pk = 2 y (xk+1 – xk)– 2 x (yk+1 – yk)

•однако xk+1 = xk +1, поэтому

• pk+1 = pk + 2 y– 2 x (yk+1 – yk) ,

(15)

•где член yk+1 – yk равен либо 0, либо 1, в зависимости от знака параметра pk.

•Такой рекурсивный расчет параметров принятия решений выполняется в каждой точке с целым значением координаты x, начиная с координаты левого конца отрезка.

•Первый параметр p0 находится из уравнения (14) в начальной точке с координатами (x0, y0) при этом m находится как y / x:

• p0 = 2 y– x,

(16)

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

АЛГОРИТМ ПОСТРОЕНИЯ ПРЯМЫХ ЛИНИЙ БРЕЗЕНХЕМА

•Подытожим метод построения прямой линии Брезенхема для прямой с положительным тангенсом угла наклона, меньше 1, с помощью следующего алгоритма.

•Алгоритм Брезенхема построения прямой пинии для m| < 1, 0

•1. Ввести два конца отрезка и поместить левый конец в точку с координатами (x0, y0).

•2. построить первую точку,

•3. Вычислить постоянные x, y, 2 y и 2 y– x и найти начальное значение параметра принятия решения:

•p0 = 2 y– x.

•4. Для каждого xk вдоль прямой, начиная с k = 0, провести следующую проверку.

–Если pk < 0, то следующая точка следует – пиксель с координатами (xk + 1, уk) и pk+1= pk + 2 y.

–В противном случае следующая точка следует – пиксель с координатами (xk + 1, уk+ 1) и pk+1= pk + 2 y – 2 x .

–Построить точку

•5. Выполнить этап 4 x – 1 раз.

•

Построение прямой линии методом Брезенхема

•Пример

•Дан отрезок прямой с концами (20, 10) и (30, 18).

•Тангенс угла наклона этого отрезка m = 0,8 при

•x =10, y = 8

•Исходное значение параметра принятия решения:

•p0 = 2 y– x = 6,

•приращения для вычисления последующих параметров принятия решения равны

•2 y =16, 2 y – 2 x = – 4.

•Откладываем начальную точку (x0, y0) = (20, 10) и с помощью параметра принятия решения определяем последующие положения пикселей по направлению прямой.

Положения пикселей прямолинейного отрезка с концами (20, 10) и (30, 18), по алгоритму Брезенхема

k	pk	(xk + 1, уk+ 1)
0	6	(21,11)
1	2	(22,12)
2	-2	(23,12)
3	14	(24,13)
4	10	(25,14)
5	6	(26,15)
6	2	(27,16)
7	-2	(28,16)
8	14	(29,17)
9	10	(30,18)

Инкрементные алгоритмы

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

•Инкрементные алгоритмы выполняются как последовательное вычисление координат соседних пикселей путем добавления приращений координат. Приращения рассчитываются на основе анализа функции погрешности. В цикле выполняются только целочисленные операции сравнения и сложения/вычитания. Достигается повышение быстродействия для вычислений каждого пикселя по сравнению с прямым способом. Один из вариантов алгоритма Брезенхэма:

•xerr = 0, yerr = 0;

•dx = x2 – x1, dy = y2 – y1;

•Если dх > 0, то incX = 1;

•dх = 0, то incX = 0;

•dх < 0, то incX = -1;

•Если dу > О, то incY = 1;

•dу =0, то incY = 0;

•dу <0, то incY = -1;

•dх = |dх|, dу = |dу| ;

•Если dх > dу, то d = dх;

•	иначе d = dу;

•х = х1, у = у1;

•Пиксел (х, у)

•Выполнить цикл d раз:

•{

•хегг = хегг + dх;

•уeгг = уегг + dу;

•Если хегг > d, то хегг = хегг – d

•	х = х + incX

•Если уегг > d, то уегг = уегг – d

•	у == у + incY

•Пиксел (х, у)

•}

Инкрементные алгоритмы

•Пример работы приведенного алгоритма Брезенхэма для отрезка (х1у1 - х2у2) = (2,3 - 8,6). Этот алгоритм восьмисвязный, то есть при вычислении приращений координат для перехода к соседнему пикселю возможны восемь случаев (рис.).

•

•

•Рис.. Восьмисвязность

•Известны также четырехсвязные алгоритмы (рис. 3.4).

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

•Рис. 3.4. Четырехсвязность

АЛГОРИТМ ПОСТРОЕНИЯ ПРЯМЫХ ЛИНИЙ БРЕЗЕНХЕМА

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

•Для прямой с положительным тангенсом угла наклона, превышающим 1,0, роли координат

xи y меняются местами. Т.е. единичные шаги делаются по y , а значения координаты x, ближайшие к направлению прямой, вычисляются .

•Построение прямой с другого конца. Если в качестве исходной точки прямой с положительным тангенсом угла наклона берется правый конец, то x и y уменьшаются при каждом шаге справа налево.

•При отрицательном тангенсе угла наклона процедура аналогична, только на этот раз одна координата увеличиваемся при уменьшении другой.

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

•ИЗОБРАЖЕНИЕ ЛОМАНЫХ ЛИНИЙ

•Для процедуры построения ломаных линий следует m – 1 раз вызвать процедуру построения прямой линии, в результате чего изображаются прямые линий, соединенные в

mточках.

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

АЛГОРИТМЫ ПОСТРОЕНИЯ ОКРУЖНОСТЕЙ

•СВОЙСТВА ОКРУЖНОСТЕЙ (напоминаем)

•Окружность (рис.) определяется как геометрическое место точек,

•удаленных на заданное расстояние r от центра с координатам (xc, yc).

•Для любой точки окружности (x, у) через теорему Пифагора

• (x – x )2	+ (y – y )2	= r2.	(26)
c	c

1.По этому уравнению можно найти положение точек на окружности, перемещаясь по оси x с единичным шагом от xc – r до xc + r вычисляя в каждой точке соответствующие значения y

• . y y				(27)
		r 2 x	x 2
c		c

•Однако, одна из проблем, возникающих при таком подходе

•– это то, что на каждом шаг необходим значительный объев вычислений

•Более того, промежутки между положениями изображаемых пикселей

•будут неравномерными, что проиллюстрировано на рис..

•Можно было бы регулировать величину этого промежутка меняя местами координаты x и y (делая шаг по оси y; и вычисляя соответствующие значения x), когда абсолютное значение тангенса угла наклона окружности больше 1.

•Однако это увеличит объем операций в алгоритме и время, необходимое для обработки данных.