Растровое преобразование графических примитивов

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

Алгоритм Брезенхема растровой дискретизации отрезка

При построении растрового образа отрезка необходимо, прежде всего, установить критерии "хорошей" аппроксимации. Первое требование состоит в том, что отрезок должен начинаться и кончаться в заданных точках и при этом выглядеть сплошным и прямым (при достаточно высоком разрешении дисплея этого можно добиться). Кроме того, яркость вдоль отрезка должна быть одинаковой и не зависеть от наклона отрезка и его длины. Это требование выполнить сложнее, поскольку горизонтальные и вертикальные отрезки всегда будут ярче наклонных, а постоянная яркость вдоль отрезка опять же достигается на вертикальных, горизонтальных и наклоненных под углом в 45 $$\deg$$ линиях. И, наконец, алгоритм должен работать быстро. Для этого необходимо по возможности исключить операции с вещественными числами. С целью ускорения работы алгоритма можно также реализовать его на аппаратном уровне.

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

Задача состоит в построении отрезка, соединяющего на экране точки с координатами $$(i_1,j_1),(i_2,j_2)$$ (будем считать, что $$i_1\ne i_2$$ ). Для построения отрезка прямой на плоскости с вещественными координатами можно воспользоваться уравнением прямой, проходящей через две заданные точки, которое имеет вид$$j=j_1+k(i-i_1), \quad k=(j_2-j_1)/(i_2-i_1).$$

Теперь, считая, что $$0\le k\le 1, \; (i,j)$$ - координаты текущей точки растрового образа, а $$y$$ - точное значение координаты точки отрезка, можно построить следующую точку:$$i'=i+1, \quad j'=y+k$$

Следует заметить, что целочисленная координата $$j$$ изменится только в том случае, если y превысит величину $$j+0.5$$ ( $$j'$$ есть ближайшее к $$y$$ целое число, полученное в результате операции округления). Приведенный пример включает операции с вещественными числами, которые выполняются существенно медленнее, чем соответствующие целочисленные операции, а при построении растрового образа отрезка желателен алгоритм, по возможности обращающийся только к целочисленной арифметике. Кроме того, алгоритм должен работать при любом взаимном расположении концов отрезка.

Алгоритм Брезенхема построения растрового образа отрезка был изначально разработан для графопостроителей, но он полностью подходит и для растровых дисплеев. В процессе работы в зависимости от углового коэффициента отрезка наращивается на единицу либо $$i$$, либо $$j$$, а изменение другой координаты зависит от расстояния между действительным положением точки и ближайшей точкой растра (смещения). Алгоритм построен так, что анализируется лишь знак этого смещения.

На рис. 8.2 это иллюстрируется для отрезка с угловым коэффициентом, лежащим в диапазоне от нуля до единицы. Из рисунка можно заметить, что если угловой коэффициент $$k\ge\frac12$$, то при выходе из точки $$(0,0)$$ пересечение с прямой $$x=1$$ будет ближе к прямой $$y=1$$, чем к прямой $$y=0$$. Следовательно, точка растра $$(1,1)$$ лучше аппроксимирует прохождение отрезка, чем точка $$(1,0)$$. При $$k<\frac12$$ верно обратное.

На рис. 8.3 показано, каким образом строятся точки растра для отрезка с тангенсом угла наклона $$3/8$$, а на рис. 8.4 - график смещения. В начале построения смещение полагается равным $$k-1/2$$, а затем на каждом шаге оно наращивается на величину $$k$$, и если при этом вертикальная координата точки растра увеличивается на единицу, то смещение в свою очередь уменьшается на единицу.

На рис. 8.5 приведена блок-схема алгоритма для случая $$i_2>i_1, \quad j_2> j_1, \quad k>0$$. Нетрудно понять, как от этого алгоритма перейти к целочисленному: достаточно вместо величины смещения $$e$$ перейти к величине $$\widetilde{e}=2\Delta i\cdot e$$.

Приведем общий алгоритм Брезенхема, который учитывает все возможные случаи направления отрезка, рассматриваемого как вектор на координатной плоскости (на рис. 8.6 выделены четыре области и указаны особенности алгоритма в каждой из них).

В описании алгоритма используются следующие функции:

swap (a, b): обмен значений переменных a, b;
abs (a): абсолютное значение a;
sign (a): 0, если a= 0, 1, если a>0, –1, если a<0;
point (i, j) - инициализация точки (i, j).

Предполагается, что концы отрезка $$(i_1,j_1),(i_2,j_2)$$ не совпадают и что все используемые переменные являются целыми.

i=i1;
j=j1;
di=i2-i1;
dj=j2-j1;
s1=sign(i2-i1);
s2=sign(j2-j1);
di=abs(di);
dj=abs(dj);
if (dj>di) 
{
 swap(di,dj); c=1;
} 
else c=0;
e=2*dj-di;	// Инициализация смещения
// Основной цикл
for (l=0; l<di; l++)
{
	point(i,j);
	while (e>=0)
	{ 
		if (c==1) i=i+s1; 
		else j=j+s2;
		e=e-2*di;
	}
	if (c==1) j=j+s2; else i=i+s1;
	e=e+2*dj;
	}

Алгоритмы Брезенхема растровой дискретизации окружности и эллипса

Алгоритм изображения окружности несколько сложнее, чем построение отрезка. Мы рассмотрим его для случая окружности радиуса $$r$$ с центром в начале координат. Перенесение его на случай произвольного центра не составляет труда. При построении растровой развертки окружности можно воспользоваться ее симметрией относительно координатных осей и прямых $$y=\pm x$$. Необходимо сгенерировать лишь одну восьмую часть окружности, а остальные ее части можно получить путем отображений симметрии. За основу можно взять часть окружности от 0 до 45 $$\deg$$ в направлении по часовой стрелке с исходной точкой построения $$(r,0)$$. В этом случае координата окружности $$x$$ является монотонно убывающей функцией координаты $$y$$.

При выбранном направлении движения по окружности имеется только три возможности для расположения ближайшего пикселя: на единицу вправо, на единицу вниз и по диагонали вниз (рис. 8.7). Выбор варианта можно осуществить, вычислив расстояния до этих точек и выбрав минимальное из них:$$\begin{gathered} d_h=|s_h|, \quad d_v=|s_v|, \quad d_d=|s_d|, \\ s_h=(x+1)^2+y^2-r^2, \quad s_v=x^2+(y-1)^2-r^2, \quad\\ s_d=(x+1)^2+(y-1)^2-r^2. \end{gathered}$$

Алгоритм можно упростить, перейдя к анализу знаков величин $$s_h, s_v, s_d$$. При $$s_d<0$$ диагональная точка лежит внутри окружности, поэтому ближайшими точками могут быть только диагональная и правая. Теперь достаточно проанализировать знак выражения $$\Delta=d_v-d_d$$. Если $$\Delta\le 0$$, выбираем горизонтальный шаг, в противном случае - диагональный. Если же $$s_d>0$$, то определяем знак $$\Delta^1=d_d-d_v$$, и если $$\Delta^1\le 0$$, выбираем диагональный шаг, в противном случае - вертикальный. Затем вычисляется новое значение $$s_d$$, причем желательно минимизировать вычисления не только этой величины, но и величин $$\Delta,\Delta^1$$ на каждом шаге алгоритма. Путем несложных преобразований можно получить для первого шага алгоритма, что $$\Delta=2(s_d+y)-1, \quad \Delta^1=2(s_d+x)-1$$.

После перехода в точку $$(x',y'),\:x'=x+1,\:y'=y+1$$ по диагонали новое значение $$s_d$$ вычисляется по формуле $$s'_d=s_d+2x'-2y'+2$$, при горизонтальном переходе $$(x'=x+1,y'=y)\quad s'_d=s_d+2x'+1$$, при вертикальном $$(x'=x,y'=y-1)$$ - $$s'_d=s_d-2y'+1$$.

Таким образом, алгоритм рисования этой части окружности можно считать полностью описанным (блок-схема его приведена на рис. 8.8). Все оставшиеся ее части строятся параллельно: после получения очередной точки $$(x',y')$$ можно инициализировать еще семь точек с координатами $$(-x',y'),\;(-x',-y'),\;(x',-y'),\;(y',x'),\;(y',-x'),\;(-y',-x'),\;(-y',x')$$.

Для построения растровой развертки эллипса с осями, параллельными осям координат, и радиусами $$a,b$$ воспользуемся каноническим уравнением$$\frac{x^2}{a^2}+\frac{y^2}{b^2}=1,$$ которое перепишем в виде$$f(x,y)\equiv b^2 x^2+a^2 y^2 -a^2 b^2 =0.$$

В отличие от окружности, для которой было достаточно построить одну восьмую ее часть, а затем воспользоваться свойствами симметрии, эллипс имеет только две оси симметрии, поэтому придется строить одну четверть всей фигуры. За основу возьмем дугу, лежащую между точками $$(0,b)$$ и $$(a,0)$$ в первом квадранте координатной плоскости.

В каждой точке $$(x,y)$$ эллипса существует вектор нормали, задаваемый градиентом функции $$f$$. Дугу разобьем на две части: первая - с углом между нормалью и горизонтальной осью больше 45 $$\deg$$ (тангенс больше 1) и вторая - с углом, меньшим 45 $$\deg$$ (рис. 8.9). Движение вдоль дуги будем осуществлять в направлении по часовой стрелке, начиная с точки $$(0,b)$$. Вдоль всей дуги координата является монотонно убывающей функцией от $$x$$, но в первой части она убывает медленнее, чем растет аргумент, а во второй - быстрее. Поэтому при построении растрового образа в первой части будем увеличивать $$x$$ на единицу и искать соответствующее значение $$y$$, а во второй - сначала уменьшать значение $$y$$ на единицу и определять соответствующее значение $$x$$.

Направление нормали соответствует вектору$$grad(x,y)= \left( \frac{\partial f}{\partial x},\frac{\partial f}{\partial y} \right) =(2b^2 x, 2a^2 y).$$ Отсюда находим тангенс угла наклона вектора нормали: $$t=a^2 y/b^2 x$$. Приравнивая его единице, получаем, что координаты точки деления дуги на вышеуказанные части удовлетворяют равенству $$b^2 x=a^2 y$$. Поэтому критерием того, что мы переходим ко второй области в целочисленных координатах, будет соотношение $$a^2(y-1/2)\le b^2(x+1)$$, или, переходя к целочисленным операциям, $$a^2(2y-1)\le 2b^2(x+1)$$.

При перемещении вдоль первого участка дуги мы из каждой точки переходим либо по горизонтали, либо по диагонали, и критерий такого перехода напоминает тот, который использовался при построении растрового образа окружности. Находясь в точке $$(x,y)$$, мы будем вычислять значение $$\Delta=f(x+1,y-\frac12)$$. Если это значение меньше нуля, то дополнительная точка $$(x+1,y-\frac12)$$ лежит внутри эллипса, следовательно, ближайшая точка растра есть $$(x+1,y)$$, в противном случае это точка $$(x+1,y-1)$$ (рис. 8.10а).

На втором участке дуги возможен переход либо по диагонали, либо по вертикали, поэтому здесь сначала значение координаты y уменьшается на единицу, затем вычисляется $$\Delta=f(x+\frac12,y-1)$$ и направление перехода выбирается аналогично предыдущему случаю (рис. 8.10б).

Остается оптимизировать вычисление параметра $$\Delta$$, умножив его на 4 и представив в виде функции координат точки. Тогда для первой половины дуги имеем$$\begin{gathered} \widetilde{\Delta}(x,y)\equiv 4\Delta(x,y)=4b^2(x+1)^2+a^2(2y-1)^2-4a^2 b^2, \\ \widetilde{\Delta}(x+1,y)=\widetilde{\Delta}(x,y)+4b^2(2x+3), \\ \widetilde{\Delta}(x+1,y-1)=\widetilde{\Delta}(x,y)+4b^2(2x+3)-8a^2(y-1). \end{gathered}$$ Для второй половины дуги получим$$\begin{gathered} \widetilde{\Delta}(x,y)\equiv 4\Delta(x,y)=b^2(2x+1)^2+4a^2(y-1)^2-4a^2 b^2, \\ \widetilde{\Delta}(x+1,y)=\widetilde{\Delta}(x,y)+8b^2(x+1), \\ \widetilde{\Delta}(x+1,y-1)=\widetilde{\Delta}(x,y)+8b^2(x+1)-4a^2(2y+3). \end{gathered}$$

Все оставшиеся дуги эллипса строятся параллельно: после получения очередной точки $$(x',y')$$, можно инициализировать еще три точки с координатами $$(-x',y'),\;(-x',-y'),\;(x',-y')$$. Блок-схему не приводим ввиду прозрачности алгоритма.

Алгоритмы заполнения областей

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

Методы первого типа исходят из того, что задана некоторая точка (затравка) внутри контура и задан критерий принадлежности точки границе области (например, задан цвет границы). В алгоритмах ищут точки, соседние с затравочной и расположенные внутри контура. Если обнаружена соседняя точка, принадлежащая внутренней области контура, то она становится затравочной и поиск продолжается рекурсивно.

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

Сначала рассмотрим простой алгоритм заполнения с затравкой с использованием стека. Под стеком в данном случае мы будем понимать массив, в который можно последовательно помещать значения и последовательно извлекать, причем извлекаются элементы не в порядке поступления, а наоборот: по принципу "первым пришел - последним ушел" ("first in - last out"). Алгоритм заполнения выглядит следующим образом:

Поместить затравочный пиксель в стек
Пока стек не пуст:
	Извлечь пиксель из стека
	Инициализировать пиксель
	Для каждого из четырех соседних пикселей:
		Проверить, является ли он граничным и был ли он инициализирован
		Если нет, то поместить пиксель в стек

Алгоритм можно модифицировать таким образом, что соседними будут считаться восемь пикселей (добавляются элементы, расположенные в диагональном направлении).

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

В случае, когда многоугольник, ограничивающий область, задан списком вершин и ребер (ребро определяется как пара вершин), можно предложить еще более экономный метод. Для каждой сканирующей строки определяются точки пересечения с ребрами многогранника, которые затем упорядочиваются по координате $$x$$. Определение того, какой интервал между парами пересечений есть внутренний для многогранника, а какой нет, является достаточно простой логической задачей. При этом если сканирующая строка проходит через вершину многогранника, то это пересечение должно быть учтено дважды в случае, когда вершина является точкой локального минимума или максимума. Для поиска пересечений сканирующей строки с ребрами можно использовать алгоритм Брезенхема построения растрового образа отрезка.

В заключение в качестве примера приведем алгоритм закраски внутренней области треугольника, основанный на составлении полного упорядоченного списка всех отрезков, составляющих этот треугольник. Для записи горизонтальных координат концов этих отрезков будем использовать два массива $$X_{min}$$ и $$X_{max}$$ размерностью, равной числу пикселей растра по вертикали (рис. 8.11).

Построение начинается с инициализации массивов $$X_{min}$$ и $$X_{max}$$: массив $$X_{max}$$ заполняется нулями, а массив $$X_{min}$$ - числом $$N$$, равным числу пикселей растра по горизонтали. Затем определяем значения $$j_{min},J_{max}$$, ограничивающие треугольник в вертикальном направлении. Теперь, используя модифицированный алгоритм Брезенхема, занесем границы отрезков в массивы $$X_{min}$$ и $$X_{max}$$. Для этого всякий раз при переходе к очередному пикселю при формировании отрезка вместо его инициализации будем сравнивать его координату $$i$$ с содержимым $$j$$ -й ячейки массивов. Если $$X_{min}[j]> i$$, то записываем координату $$i$$ в массив $$X_{min}$$. Аналогично при условии $$X_{max}[j]< i$$ координату $$i$$ записываем в массив $$X_{max}$$.

Если теперь последовательно применить алгоритм Брезенхема ко всем трем сторонам треугольника, то мы получим нужным образом заполненные массивы границ. Остается только проинициализировать пиксели внутри отрезков $$\{(X_{min[j],j}),\;(X_{max}[j],j)\}$$.

Этот алгоритм можно легко распространить на случай произвольного выпуклого многоугольника.

Вопросы и упражнения