Tomasz Hebisz

Multimedia

i grafika komputerowa

ALGORYTMY RASTROWE

4 listopada 2002 roku

skrypt znajduje się w trakcie tworzenia, i z pewnością nie jest wolny od błędów

Instytut Sterowania i Systemów Informatycznych

Spis treści

1. Algorytmy rastrowe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2

1.1. Rysowanie odcinka . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2

1.1.1. Algorytm DDA (digital diferential analyzis) . . . . . . . . . . . . . . . . .

3

1.1.2. Algorytm Bressenhama

. . . . . . . . . . . . . . . . . . . . . . . . . . . .

4

1.2. Algorytm wypełniania obszaru . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5

1.3. Problem anytaliasingu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6

1.3.1. Techniki antyaliasingu . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7

1.3.2. Supersampling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

9

1.3.3. Postfiltering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

10

1. Algorytmy rastrowe

1.1. Rysowanie odcinka

Rysowanie linii (odcinków) jest problemem bardzo złożonym. Rysowanie linii piono-

wych i poziomych nie przysparza problemów. Warto jednak pamiętać, że jeżeli szybkość
rysowania grafiki jest istotna, to dla rysowania odcinków poziomych i pionowych, powinno
się zastosować inne procedury niż dla rysowania linii skośnych.

Oprócz linii pionowych, poziomych i idelalnie skośnych (nachylonych o kąt α = arctan(dyx),

gdzie dx - szerokość piksela, dy - wyskość piksela), można jeszcze wyróżnić linie strome
i łagodne. Stromymi nazwać można te, których wysokość jest większa niż szerokość.

W układzie współrzędnych pikselowych, wybór pikseli mających stanowić rysunek

krzywej, która nie jest równoległa, ani prostopadła do układu pikseli, stanowi często
problem.

Wyboru pikseli można dokonywać w dwóch trybach:

•

czterokierunkowym,

•

ośmiokierunkowym.

W przypadku monitorów o wielu kolorach (jasnościach) lepsze efekty można uzyskać

stosując wybór czterokierierunkowy. Natomiast na monitorach starego typu, lub przy
zastosowaniu jednobitowego trybu rysowania lepsze efekty daje wybór ośmiokierunkowy.

1. Algorytmy rastrowe

3

Przy rysowaniu takich krzywych powstaje problem tzw. schodkowatości, zwanej alia-

singiem. Wyrównanie skodków realizuje się poprzes wygładzanie krawędzi stosując kolory
pośrednie, pomiędzy tłem a kolorem odcinka.

1.1.1. Algorytm DDA (digital diferential analyzis)

Pierszym i narzucającym się sposobem narysowania odcinka z punktu do punktu jest

wykorzystanie równania prostej y = ax + b lub odwrotnego x = (y − b)ą, zależnie od
stromości.

Algorytm dyskretnej analizy różnicowej jest jednym z prostszych algorytmów wyboru

punktów odcinka. Bazuje on na obiczeniu stałego kroku dla obu współrzędnych, oraz
funkcji zaokronglającej wartości rzeczywiste do całkowitych. Fakt ten sprawia, że daje
on różne wyniki dla różnych funkcji zaokrąglających Integer(). Poza tym wadą tego
algorytmu jest konieczność stosowania arytmetyki zmiennoprzecinkowej.

/* Rysuj odcinek od (x1,y1) do (x2,y2) */ /* Funkcje:

Integer(float x) -

>

Integer (-8.5) = -9

Sign(float x) -

>

-1, 0, 1

<

-

<

0, =0,

>

0

*/

int i;
int x1, x2, y1, y2, Length, color;
float x, y, Dx, Dy;

/* Dugo docinka - przybliona */

Length = (abs(x2-x1) >= abs(y2-y1)) ? abs(x2-x1) : abs(y2-y1);

/* Wyznaczenie kroku w kierunku x i y */

Dx = (double)(x2 - x1) / Length;
Dy = (double)(y2 - y1) / Length;

/* Wartoci pocztkowe x i y */

x = x1+0.5*Sign(Dx);
y = y1+0.5*Sign(Dy);

/* Ptla rysujca odcinek */

for(i=0; i<Length; i++) {

putpixel(Integer(x), Integer(y), color);
x += Dx;
y += Dy;

}

1. Algorytmy rastrowe

4

Przykład: (0, 0) 7→ (5, 3)

putpixel(0,0,color); putpixel(1,1,color); putpixel(2,1,color);
putpixel(3,2,color); putpixel(4,2,color); putpixel(5,3,color);

Rozwiązanie takie ma jednak wadę. Operować należy na liczbach rzeczywistych, dla

każdego punktu mnożąc i wykonując przybliżanie (round).

1.1.2. Algorytm Bressenhama

Metoda Bressenhama opera się na zmiennej decyzyjnej. Zmienna decyzyjna to taka

zmienna naturalna, której znak decyduje o kolejnym kroku algorytmu, a w każdym kroku
zmieniana jest zależnie od obecnego stanu. W tym przypadku zmienna decyzyjna określa
kierunek poziomy, pionowy lub idealnie ukośny. W zależności od jej znaku następuje
przyrost zmiennej zależnej lub nie i rysowany jest kolejny piksel.

T (i + 1) = [x(i) + 1, y(i) + 1]

t

s

P

P (i) = [x(i), y(i)]

S(i + 1) = [x(i) + 1, y(i)]

y = m(x − x

0

) + y

0

Poniższy kod realizuje uogólniony algorytm Bressenhama (dla wszystkich

kierunków). {

parametry poczatkowe

}

x:=x1;
y:=y1;
Dx :=abs(x2-x1);
Dy :=abs(y2-y1);
s1 :=Sign(x2-x1);
s2 :=Sign(y2-y1);

{

Zamiana Dx z Dy w zaleznosci od nachylenia

}

if Dy>Dx then

begin

temp:=Dx;
Dx:=Dy;
Dy:=temp;
Inter:=1

end

1. Algorytmy rastrowe

5

else Inter := 0;

{

poczatkowa wartosc zmiennej decyzyjnej

}

p:=(Dy shl 1)-Dx;

{

petla rysujaca

}

for i := 1 to Dx do

begin

putpixel(x,y,15);
if p>=0 then

begin

if Inter=1 then

x:=x+s1

else

y:=y+s2;

p := p - (Dx shl 1);

end;

if Inter=1 then

y:=y+s2

else

x:=x+s1;

p := p + (Dy shl 1);

end

1.2. Algorytm wypełniania obszaru

Zbiorem spójnym nazywa się zbiór pikseli, gdy dla dowolnego piksela z tego zbioru

można przejś do każdego innego pzrez piksele sąsiednie.

Relacja sąsiedztw:

•

zbiór czterospójny,

•

zbiór ośmiospójny.

1. Algorytmy rastrowe

6

Prosty algorytm wypełniania przez przesianie (seed fill algorithm )

void fill4(int x, int y, int cedge, int col) {

int color = getpixel(x, y);
if ((color != cedge) && (color != col)) {

putpixel(x, y, col);
fill4(x,y-1,cedge,col);
fill4(x,y+1,cedge,col);
fill4(x-1,y,cedge,col);
fill4(x+1,y,cedge,col);

}

}

1.3. Problem anytaliasingu

W trakcie rysowania grafiki rastrowej bardzo często dochodzi do zjawiska powstawa-

nia schodów na krawędziach linii pochyłych. Na rysunku poniższym pokazano przykład
takiego zjawiska.

Czarny prostokąt reprezentuje idealną linię, posiadającą grubość oraz kąt nachylenia.
Zaczernione punkty pokazują reprezentację tej linii na rastrze o określonej rozdzielczości.
Zjawisko takie nosi nazwę aliasingu, a zdefiniowane zostało w teorii próbkowania w prze-
twarzaniu sygnałów. Aby zobrazować charakter pewnego sygnału sinusoidalnego, można
zmierzyć lub spróbkować jego wartość w pewnych stałych odstępach czasu.

1. Algorytmy rastrowe

7




Dzięki temu otrzymuje się próbki sygnału. Jeżeli jednak sygnał zostanie sprówbkowany

w zbyt dużych odstępach czasu, to otrzymany sygnał nie będzie wiernie oddawał charak-
teru sygnału wyjściowego. W grafice występuje również zjawisko aliasingu. Próbkami są
tu wartości barwy w punktach rastrowych.

W jaki sposób zatem można poradziś sobie z problemem aliasingu generowanego zbyt

niedokładnym próbkowaniem? Wyświetlanie większej rozdzielczości może polepszyć sytu-
ację, gdyż podnosi częstotliwość próbkowania. Jeżeli jednak chodzi o zastosowanie grafiki
na ekranie monitora, gdzie rozdzielczość jest ustalona, to wówczas trzeba szukać innych
rozwiązań

1.3.1. Techniki antyaliasingu

Techniki antyaliasingu opierają się głównie na sposobie rozmywania krawędzi, pod-

noszącego gładkość krzywych. W przypadku czarnego prostokąta na białym tle, ostre
przejście z czerni do bieli może być wygładzone poprzez zastosowanie szarych pikseli na
krawędzi prostokąta. Taka reprezentacja krawędzi obserwowana z pewnej odległości, przez
oko ludzkie, jako płynne przejście pomiędzy kolorem tła i prostokąta, przez co wygląd
krawędzi staje się gładki.

Istnieją trzy główne podejścia do problemu antyaliasingu:

❏ prefiltering,
❏ supersampling,
❏ postfiltering.

Prefiltering — metoda Pitteway’a-Watkinsona

Metoda prefilteringu oblicza poziom szarości piksela, ana podstawie tego, jak duża

powierzchnia piksela zajęta jest przez obiekt.

Załóżmy, że na czarnej powierzchni ma zostać narysowany biały wielokąt, tak jak na

rysunku:

1. Algorytmy rastrowe

8













































"!

#$

%&

'

(

)

*

+

,

-

.

/

0

1

Intensywność koloru określona jest w przedziale od 0 dla czerni do 1 dla bieli. Wielokąt

jest położony na siatce kwadratów, reprezentujących piksele, gdzie środek każdego kwa-
dratu oznacza środek piksela. Jeżeli zatem piksel przykryty jest w połowie przez wielokąt,
to powinien mieć kolor reprezentowany przez wartość 1/2, jeżeli jest on przykryty na 1/3,
to przyjmuje kolor 1/3 itd. Jeśli kolor piksela opisywany jest wartością 4-bitową, tak że
kolor biały reprezentowany jest liczbą 0, a kolor czarny wartością 15, to w przypadku
pokrycia piksela przez wielokąt w 1/4, należy nadać mu kolor o wartości (1/4)15, która
po zaokrągleniu wynosi 4. Na rysunku ??? pokazano wartości barw poszczególnych pikseli
reprezentujących wielokąt na siatce rastra.

Niestety wadą tego rozwiązania jest duża złożoność obliczeniowa, związana z oblicze-

niem powierzchni piksela zajmowanej przez obiekt. Wady te można częściowo poprawić
stosując modyfikację algorytmu Bresenhamma, służącego do kreślenia linii, która została
opracowana przez Pittewayą i Watkinsona. Dla każdej krawędzi wielokątu, oprócz obli-
czenia położenia piksela, który najlepiej przybliża linię, obliczany jest również stopień
jego przykrycia przez wielokąt. Wnętrze wielomianu jest potem wypełnione odpowiednim
kolorem. Zgodnie z założeniami algorytmu Brassenhama, wszystkich obliczeń dokonuje
się na liczbach całkowitych.

Zasadę działania tego algorytmu najlepiej przedstawić na przykładzie pokazanym na

poniższym rysunku:





























"!#

$%&

'()

*+,

-./

0"12

3

Rysowana krawędź wielokąta pocholona jest ze współczynnikiem 4/10. Wnętrze wie-

lokąta znajduje się poniżej wyszarzonych punktów. Piksele wyznaczone za pomocą stan-
dardowego algorytmu Brassenhama oznaczono kropkami, natomiast wyszarzone części
każdego z nich, to powierzchnia pikseli, należąca do wielokątu. Wartość numeryczna re-
prezentująca tą powierzchnię, przedstawiona jest na górze rysunku.

1. Algorytmy rastrowe

9

1.3.2. Supersampling

Problem rasteryzacji obiektów można sprowadzić do problemu dyskretyzacji funkcji

opisujących obiekt, z częstotliwością rastra. Jeżeli na linię, stanowiącą krawędź obiektu,
popatrzy się, jako funkcję liniową, to rastryzacja polega na dyskretnym spróbkowaniu,
czyli obliczeniu wartości tej funkcji, z częstotliwością odpowiadającą gęstości rastra.

Technika supersamplingu, zwana też nadsamplingiem lub oversamplingiem, polega naj-

ogólniej na zwiększeniu liczby próbkowania, podczas dopasowywania analowego kształtu
obiektu do siatki rastra. Odwzorowanie obiektu na siatkę rastra można przedstawić jako
próbkowanie sygnału analogowego z częstotliwością rastra. Niestety często jakości tego
próbkowania nie można poprawić poprzez zwiększenie częstości próbkowania, gdyż gę-
stość rastra jest uzależniona od urządzenia wyjściowego (np. rozdzielczość ekranowa).
Technika supersamplingu realizowana jest poprzez zwiększenie próbkowania, a następnie
poprzez uśrednienie próbek do wartości odpowiadających poszczególnym pikselom. Zatem,
aby obliczyć barwę piksela znajdującego się na krawędzi obiektu, należy zdyskretyzować
obiekt, tak, jakby gęstość rastra była większa od wyjściowej, a następnie, dla każdego
wyjściowego punktu rastrowego, oblicza się uśrednioną barwę, na podstawie zabarwienia
poszczególnych próbek w obrębie tego piksela.

Poniższy rysunek przedstawia przykład realizacji nadsamplingu.

3/4

3/4

3/4

3/4

1/4

1/4

1/4

1/4

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

Realizacja metody supersamplingu

Należy zwrócić uwagę na fakt, że jeżeli liczba próbek na wyjściowy punkt rastrowy,

zmierzać będzie do nieskończoności, to metoda ta sprowadza się wówczas do obliczenia
rzeczywistej powierzchni piksela, jaka należy do obiektu. Najczęściej stosuje się jednak
nadsampling, w którym liczba próbek na wyjściowy punkt rastrowy jest stosunkowo nie-
wielka.

1. Algorytmy rastrowe

10

1.3.3. Postfiltering

Ostatnią z opisanych metod jest metoda postfilteringu. Polega ona na uśrednieniu

wartości barwy każdego piksela w oparciu o barwę jego i barwy pikseli sąsiadujących z
nim. Najczęściej stosowana jest tu średnia ważona, w której waga piksela, którego barwa
jest obliczana, jest największa. W algorytmie tym definiuje się pewne otoczenie piksela,
nadając wagi każdemu elementowi takiego otoczenia.

Następnie dla każdego piksela w obrazie oblicza się nową wartość, w oparciu o barwę

jego i jego otoczenia. Metoda ta wymaga zatem znajomości barw wszystkich pikseli. Dla-
tego wygładzanie krawędzi metodą postfilteringu realizuje się najczęściej po narysowaniu
wszystkich obiektów na bitmapie, która nie jest bezpośrednio wyświetlana na ekranie
monitora, a następnie kopiuje się tą bitmapę na ekran.

Ważną rolę, w metodzie postfilteringu, odgrywa dobór sąsiedztwa piksela, oraz wagi,

jakie odgrywają poszczególne piksele. Poniżej przedstawiono kilka przykładów sąsiedztw.

1/16 1/16 1/16

1/16 1/2 1/16

1/16 1/16 1/16

1/16 1/8 1/16

1/8 1/4 1/8

1/16 1/8 1/16

1/8

1/8 1/2 1/8

1/8

4/81 6/81 4/81

6/81 9/81 6/81

4/81 6/81 4/81

2/81

3/81

2/81

2/81

3/81

2/81

2/81 3/81 2/81

1/81

1/81

2/81 3/81 2/81

1/81

1/81

Przykłady ssiedztw w metodzie postfilteringu