Рисунок 26 – Диагональное расположение ячеек

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

4.3. Алгоритмические основы растровой графики

4.3.1. Поиск оптимального алгоритма рисования прямой

Пусть отрезок прямой задан в плоскости координатами начала(x1 , y1 ) и

конца (x2 , y2 ) (см. рисунок 27).

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

Для вывода линии необходимо закрасить в определённый цвет все пиксели вдоль неё (считаем, что линия бесконечно тонкая). Из отношения катетов для подобных треугольников:

	x - x1	=	x2	- x1	(8)
	y - y1		y2	- y1

Можно выразить текущие координаты x или y .

59

Пусть здесь и далее угол наклона прямой к осиx меньше или равен 45°. При этом можно запустить инкрементный цикл по оси x , и прямая останется 8- связной (т.е. не появятся так называемые «выпадающие пиксели»). Если же тангенс угла наклона больше1, то наоборот, осуществляется цикл с единичным приращением по оси y . Крайние случаи, когда линии являются вертикальными или горизонтальными, не рассматриваем, так как практически любой из алгоритмов их рисования достаточно быстр.

1. Рассмотрим реализацию алгоритма рисования отрезка«из первых принципов»:

for (x=x1; x<=x2; x++)

{

y=y1+((x-x1)*(y2-y1))/(x2-x1); SetPixel(x,y);

}

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

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

float k = (float) (y2-y1) / (float) (x2-x1); for (x=x1; x<=x2; x++)

{

y=y1+ (float) (x-x1) * k; SetPixel(x,y);

}

Так как

y = y1 + (x - x1 ) × k = y1 + xk - x1k = xk + yy ,

(9)

где yy – константа, то перепишем программу следующим образом:

float k = (float) (y2-y1) / (float) (x2-x1); float yy=(float) y1 – (float) x1*k

60

for (x=x1; x<=x2; x++)

{

y=yy+(float) x*k; SetPixel(x,y);

}

В итеративном процессе при постоянном шаге поx равном xi+1 - xi	=1 в
соответствии с (9) разность
yi+1 - yi = y1 + xi+1k - x1 × k - y1 - xi k + x1k = (xi+1 - x)k = k	(10)

Тогда:

float k = (float) (y2-y1) / (float) (x2-x1);

//работаем с вещественными числами float yy = y1;

for (x=x1; x<=x2; x++)

{

yy += k; y = yy

//в цикле осталась только операция сложения

SetPixel(x,y);

}

Недостаток представленного алгоритма в том, что в случае целочислен-

ных значений исходных координат вычисление путём добавления вещественных приращений может привести к накоплению ошибки вычислений координат (т.е. y ¹ y2 на последнем шаге).

4.3.2. Инкрементный алгоритм Брезенхема (Bresenham) для прямой

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

В 1965 году Брезенхемом предложен алгоритм растрового построения отрезка. В алгоритме используется управляющая переменная d1 , которая на каж-

61

дом шаге пропорциональна разности между s и t (см. рисунок 28). На рисунке приведен i –ый шаг, когда пиксель Pi-1 уже найден как ближайший к реальному изображаемому отрезку, и теперь требуется определить, какой из пикселей должен быть установлен следующим: Ti или Si .

Если s < t , то Si ближе к отрезку и необходимо выбрать его; в противном случае ближе будет Ti . Другими словами, если s - t < 0 , то выбирается Si ; в

противном случае выбирается Ti .

Рисунок 28 –

Изображаемый отрезок проводится из точки(x1 , y1 ) в точку (x2 , y2 ) .

Пусть первая точка находится ближе к началу координат, тогда перенесем её в

начало координат, и тогда конечная точка окажется в(Dx, Dy) ,										где Dx = x2 - x1 ,
Dy = y		- y . Уравнение прямой теперь имеет вид y = x × Dy							.
	2	1						Dx
	Из рисунка следует, что
		s =	Dy	(r +1) - q,		t = q +1 -	Dy	(r +1) ,		(11)
			Dx				Dx
поэтому
				s - t = 2	Dy	(r +1) - 2q -1				(12)
					Dx
умножим на Dx :
		Dx(s - t) = 2(Dy ×r - q ×Dx) + 2Dy - Dx ,								(13)

так как Dx > 0 , величину Dx(s - t) можно использовать в качестве критерия для

62

выбора пикселя. Обозначим эту величину di :
	di = 2(Dy × r - q × Dx) + 2Dy - Dx,				(14)
так как r = xi-1 , q = yi-1 (предыдущий шаг итерации), получаем:
di	= 2(Dy × xi-1 - yi-1 × Dx) + 2Dy - Dx,				(15)
а на текущем шаге итерации:
	di-1 = 2(Dy × xi - yi		× Dx) + 2Dy - Dx.		(16)
Введём величину Di следующим образом:
	Di = di+1 - di	= 2Dy(xi		- xi-1 ) - 2Dx( yi - yi-1 ).	(17)
Вспомним, что	xi - xi-1 =1.	Если	di	³ 0 , то выбираем Ti ,	тогда
Di = 2(Dy - Dx). .

Если di < 0 , то выбираем Si , тогда Di = 2Dy.

Таким образом, получена итеративная формула для вычисления критерия di . Начальное значение d1 = 2Dy - Dx.

Можно построить блок-схему алгоритма (см. рисунок 29).

Этот алгоритм пригоден для случая 0 £ Dy £ Dx. Для других случаев алго-

ритм строится сходным образом.

В алгоритме используются только целые числа, сложение, вычитание и

сдвиг.

63

Рисунок 29 – Блок-схема алгоритма

Пример программы, реализующей этот алгоритм: int dx = x2 - x1;

int dy = y2 - y1; int d = 2 * dy - dx; int d1 = 2*dy;

int d2 = 2*(dy - dx); SetPixel(x1, y1, color);

// Первая точка отрезка

for (int x = x1 + 1; int y = y1; x <= x2; x++) { if (d < 0) {

d += d1; } else { d += d2; y += 1;

}

SetPixel( x, y, color);

// Очередная точка отрезка

}

64