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

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

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

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

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

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

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

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

--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

Рассмотрим задачу построения растрового изображения отрезка, соединяющего точки A(x_a, y_a) и B(x_b, y_b). Для простоты будем считать, что

0 ≤ y_b – y_a ≤ x_b – x_a. Тогда отрезок описывается уравнением:

y = ya +

(x–xa), x Є [ xa, xb ] или y = kx + b.

Отсюда получаем простейший алгоритм растрового представления отрезка:

void line(int xa, int ya, int xb, int yb, int color)

{

double k = ((double)(yb – ya)) / (xb – xa);

double b = ya – k * xa;

for (int x = xa; x <= xb; x++)

putpixel(x, (int)(k * x + b), color);}

Вычислений значений функции y = kx + b можно избежать, используя в цикле рекуррентные соотношения, так как при изменении x на 1 значение y меняется на k:

void line(int xa, int ya, int xb, int yb, int color)

{

double k = ((double)(yb – ya)) / (xb – xa);

double y = ya;

for (int x = xa; x <= xb; x++, y += k)

putpixel(x, (int)y, color);

}

Приведенные простейшие пошаговые алгоритмы построения отрезка имеют ряд недостатков:

1. Выполняют операции над числами с плавающей точкой, а желательно было бы работать с целочисленной арифметикой;

2. На каждом шаге выполняется операция округления, что также снижает быстродействие.

Эти недостатки устранены в следующем алгоритме Брезенхейма.

Как и в предыдущем случае, будем считать, что тангенс угла наклона отрезка принимает значение в диапазоне от 0 до 1. Рассмотрим i -й шаг алгоритма (рис. 2.3). На этом этапе пиксель P_{i- 1} уже найден как ближайший к реальному отрезку. Требуется определить, какой из пикселов (T_i или S_i) будет установлен следующим.

Рис. 2.3. i-й шаг алгоритма Брезенхейма

В алгоритме используется управляющая переменная d_i, которая на каждом шаге пропорциональна разности между S и T. Если S < T, то S_i ближе к отрезку, иначе выбирается T_i.

Пусть изображаемый отрезок проходит из точки (x ₁, y ₁) в точку (x ₂, y ₂). Исходя из начальных условий, точка (x ₁, y ₁) ближе к началу координат. Тогда перенесем оба конца отрезка с помощью преобразования T(– x ₁, –y ₁), так чтобы первый конец отрезка совпал с началом координат. Начальной точкой отрезка стала точка (0, 0), конечной точкой – (dx, dy), где dx = x ₂ – x ₁, dy = y ₂ – y ₁ (рис. 2.4).

Рис. 2.4. Вид отрезка после переноса в начало координат

Уравнение прямой в этом случае будет иметь вид:

y=x

.

Обозначим координаты точки P_{i- 1}после переноса через (r, q). Тогда S_i = (r+ 1, q) и T_i = (r+ 1, q+ 1).

Из подобия треугольников на рис. 2.4 можно записать, что

=

.

Выразим S:

S =

(r + 1) – q.

T можно представить как T = 1 – S. Используем предыдущую формулу

T = 1 – S = 1 –

(r + 1) – q.

Найдем разницу S – T:

S – T =

(r + 1) – q – 1 +

(r + 1) – q = 2

(r + 1) – 2 q – 1.

Помножим левую и правую часть на dx:

dx (S – T) = 2 dy (r + 1) – 2 q dx – dx = 2(r dy – q dx) + 2 dy – dx.

Величина dx положительная, поэтомунеравенство dx (S – T) < 0 можно использовать в качестве проверки при выборе S_i. Обозначим d_i = dx (S – T), тогда

d_i = 2(r dy – q dx) + 2 dy – dx.

Поскольку r = x_{i- 1} и q = y_{i- 1}, то

d_i = 2 x_{i- 1} dy – 2 y_{i- 1} dx + 2 dy – dx.

Прибавляя 1 к каждому индексу найдем d_{i+ 1:}

d_{i+ 1}= 2 x_i dy – 2 y_i dx + 2 dy – dx.

Вычитая d_i из d_{i+ 1}получим

d_{i+ 1} – d_i = 2 dy (x_i – x_{i- 1}) – 2 dx (y_i – y_{i- 1}).

Известно, что x_i – x_{i- 1} = 1, тогда

d_{i+ 1}– d_i = 2 dy – 2 dx (y_i – y_{i- 1}).

Отсюда выразим d_{i+ 1}:

d_{i+ 1} = d_i + 2 dy – 2 dx (y_i – y_{i- 1}).

Таким образом, получили итеративную формулу вычисления управляющего коэффициента d_{i+ 1} по предыдущему значению d_i. С помощью управляющего коэффициента выбирается следующий пиксель – S_i или T_i.

Если d_i ≥ 0, тогда выбирается T_i и y_i = y_{i– 1} + 1, d_{i+ 1} = d_i +2 (dy – dx). Если d_i < 0, тогда выбирается S_i и y_i = y_{i– 1} и d_{i+ 1}= d_i +2 dy.

Начальные значения d ₁ с учетом того, что (x ₀, y ₀) = (0, 0),

d ₁= 2 dy – dx.

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

Реализация этого алгоритма выглядит следующим образом:

void MyLine(int x1, int y1, int x2, int y2, int c)

{

int dx, dy, inc1, inc2, d, x, y, Xend;

dx = abs(x2 - x1);

dy = abs(y2 - y1);

d = dy << 1 - dx;

inc1 = dy << 1;

inc2 = (dy - dx) << 1;

if (x1>x2)

{

x = x2;

y = y2;

Xend = x1;

}

else

{

x = x1;

y = y1;

Xend = x2;

};

putpixel(x, y, c);

while (x < Xend)

{

x++;

if (d < 0) d = d + inc1;

else

{

y++;

d = d + inc2;

};

putpixel(x, y, c);

};

}

Если dy > d x, то необходимо будет использовать этот же алгоритм, но пошагово увеличивая y и на каждом шаге вычислять x.

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------конец пояснения---------------------------------------------------------------------------------------------------------------------------------------------