Лекция 2,3

Построение растровых примитивов

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

1. Прямоугольник (x1,y1,x2,y2,color)

Строится с помощью двух вложенных циклов по x и по y.

for(y=y1;y<=y2;y++) for(x=x1;x<=x2;x++) writePixel(x,y,color);

2. Отрезок (x1,y1,x2,y2,color)

Если это горизонтальный (y1==y2) или вертикальный (x1==x2) отрезок, то его можно построить с помощью одного цикла.

for(x=x1;x<=x2;x++) writePixel(x,y1,color);

Для построения произвольного отрезка пользуются следующими алгоритмами.

2.1. DDA (digital differential analyzer) цифровой дифференциальный анализатор. Из уравнения y=a+bx

Фактически требуется высветить те точки, которые ближе всего к отрезку.

(0,1)-(5,3)

dx=5, dy=2, d=dy/dx=0.4

(0,1.5), (1,1.9), (2,2.3),

(3,2.7), (4,3.1), (5,3.5)

Выбирается ось, вдоль которой отрезок имеет максимальный размер (например, ось x, при |dx|>|dy|)

Рассчитывается производная как d=dy/dx (|d|<=1)

y=y1+0.5;

for(x=x1;x<=x2;x++) { writePixel(x,floor(y),color); y+=d; }

Нужно ввести понятие 4-х и 8-ми связных линий.

По такому алгоритму можно построить и 4-х связный отрезок.

for(x=x1;x<x2;x++){ writePixel(x,floor(y),color); y+=d; writePixel(x,floor(y),color);}

Еще одно понятие – sub-пиксельная точность, когда координаты точек задаются не целыми числами. Более точное представление примитивов на экране.

(0.75, 1.75)-(5.5, 3.5)

Требует лишь незначительной модификации алгоритма.

writePixel(x1,floor(y1),color);

y=y1+(floor(x1)+0.5-x1)*d;

for(x=x1+1;x<x2;x++) { //writePixel(x,floor(y),color); y+=d; writePixel(x,floor(y),color); }

//writePixel(x2,floor(y),color);

writePixel(x2,floor(y2),color);

2.2. Алгоритм Брезенхема.

Не требует деления и вычислений с нецелыми числами.

r=-0.5

r+=dy/dx, при пересечении 0-ой границы – r-=1;

если все домножить на 2*dx - получим

r=-dx

r+=2*dy, при пересечении 0-ой границы – r-=2*dx;

r=-(x2-x1); a=2*(y2-y1); b=2*(x2-x1);

for(x=x1, y=y1;x<=x2;x++) { writePixel(x,y,color); r+=a; if (r>0) { y++; r-=b; } }

Для 4-х связных линий

for(x=x1, y=y1;x<x2;x++) { writePixel(x,y,color); r+=a;

if (r>0) { y++; r-=b; writePixel(x,y,color);} }

writePixel(x2,y2,color);

Для работы с sub-пиксельной точностью алгоритм следует модифицировать.

1. Дополнительно умножить все коэффициенты на точность

2. Иначе рассчитать начальный r

r=(2*K*floor(x1)+K-2*K*x1)* (y2-y1); a=2*K*(y2-y1); b=2*K*(x2-x1);

for(x=x1, y=y1;x<=x2;x++) { writePixel(x,y,color); r+=a; if (r>0) { y++; r-=b; } }

Для 4-х связных линий – ничем не отличается от обычного (кроме коэффициентов)

3. Окружность. (x0,y0,R,color)

3.1. DDA – алгоритм.

for(x=0,y=R;x<=y;x++) { writePixel(x0+x,y0-floor(y),color); y-=x/y; }

Для остальных 7 частей меняются местами x,y и направление приращения. Для sub-пиксельной точности алгоритм остается прежним, только все переменные – нецелые. Алгоритм рисует не совсем точную окружность.

3.2. Алгоритм Брезенхема.

Требуется выбрать либо A либо B.

Р асстояние от окружности до A

Расстояние от окружности до B

Если a>=0 – A находится снаружи от окружности,

выбираем A.

Е сли a<0 – определяем, что больше |a| или |b|.

Если эта разность больше нуля – выбираем A, иначе – B.

Р екуррентное соотношение для a в случае, если выбираем A.

Р екуррентное соотношение для a в случае, если выбираем B.

Н ачальное значение.

a=2*(1-R);

for(x=0,y=R;x<=y;x++) { writePixel(x0+x,y0-y,color);

if ((a<0) && (2*(a-y)-1<0)) { a+=2*x+2; }

else { y--; a+=2*(x-y)+4; } }

Для sub-пиксельной точности алгоритм остается прежним, только все коэффициенты умножаются на точность.

4. Треугольник.

(x1,y1,x2,y2,x3,y3,color)

Рисуется с помощью спанов.

Спан - горизонтальный отрезок пикселов.

Спан ограничен двумя отрезками.

Одним слева, а другим справа.

Еще одно понятие – sub-пиксельная точность, когда координаты точек задаются не целыми числами. Более точное представление примитивов на экране.

Координаты s1 и s2 спанов рассчитываются как пересечение ограничивающих отрезков с горизонтальной прямой, проходящей через центры пикселов соответствующей строки.

Сначала точки сортируются вдоль вертикальной оси (по y). A,B,C – отсортированные точки. Рассчитывается номер первой строки Ys=floor(Ay+0.5). Затем, для первых двух отрезков (AB и BC) рассчитываются производные dx/dy {k1=(Bx-Ax)/(By-Ay), k2=(Cx-Ax)/(Cy-Ay)} и значения границ первого спана {s1=Ax+k1*(Ys-Ay), s2=Ax+k2*(Ys-Ay)}. До тех пор, пока Ys<=By в цикле рисуем спан, увеличиваем Ys, пересчитываем s1,s2 для новой строки {s1+=k1; s2+=k2;}. Затем пересчитываем k1,s1 и продолжаем цикл пока Ys<=Sy.

5. Заливка ограниченной области с затравкой. (x1,y1,color1,color2) затравка, цвет контура, цвет заливки.

Реализуется с помощью рекурсивного алгоритма.

Самый простой – поточечный.

FillPoint(x, y,color1, color2)

{

c=GetPixel(x,y);

if ((c ==color1)||(c ==color2)) return;

writePixel(x,y,color2);

FillPoint(x-1,y);

FillPoint(x+1,y);

FillPoint(x,y-1);

FillPoint(x,y+1);

}

Более сложный, но и более быстрый – по спанам.

int FillSpan(int x0,int y0,long color1,long color2,int prev_xl,int prev_xr,int dir,int offset=0)

{

long c;

for(int xl=x0;xl>=0;xl--){c=GetBigPixel(xl,y0);if ((c==color1)||(c==color2)) break;}

xl++;

for(intxr=x0;xr<Width;xr++){c=GetBigPixel(xr,y0);if ((c==color1)||(c==color2)) break;}

xr--;

int x,xnext1,xnext2;

xnext1=xnext2=xl-1;

for(x=xl;x<=xr;x++)

{

bigPixel(x,y0,color1,offset);

if(x>xnext1)

{

c=GetBigPixel(x,y0+dir);

if((c!=color1)&&(c!=color2))

xnext1=FillSpan (x, y0+dir,color1,color2,xl,xr,dir,offset);

}

if ((x<prev_xl) && (x>xnext2))

{

c=GetBigPixel(x,y0-dir);

if((c!=color1)&&(c!=color2))

xnext2=FillSpan (x, y0-dir,color1,color2,xl,xr,-dir,offset);

}

if (x>prev_xr)

{

c=GetBigPixel(x,y0-dir);

if((c!=color1)&&(c!=color2))

prev_xr=FillSpan (x, y0-dir,color1,color2,xl,xr,-dir,offset);

}

}

return xr;

}