Notice: Undefined index: mode in /home/misc/mst/public_html/common.php on line 63 Notice: Undefined index: mode in /home/misc/mst/public_html/common.php on line 65 Notice: Undefined index: mode in /home/misc/mst/public_html/common.php on line 67 Notice: Undefined index: mode in /home/misc/mst/public_html/common.php on line 69 Notice: Undefined variable: base in /home/misc/mst/public_html/lecture.php on line 36 Grafika komputerowa I – 2. Podstawowe algorytmy grafiki rastrowej – MIM UW

Zagadnienia

2. Podstawowe algorytmy grafiki rastrowej

2.1. Rysowanie odcinka

Rys. 2.1. Odcinek rastrowy.

Współrzędne punktów końcowych odcinka są liczbami całkowitymi; zakładamy, że x_{2}>x_{1}, y_{2}\geq y_{1} oraz y_{2}-y_{1}\leq x_{2}-x_{1}. Chcemy ,,narysować odcinek”, czyli wyznaczyć piksele najbliżej tego odcinka, i nadać im odpowiedni kolor. Pierwsza przymiarka procedury rysowania odcinka, czyli algorytm I, wygląda tak:

$\Delta x$ = $x_2-x_1$;  $\Delta y$ = $y_2-y_1$;
$m$ = $\Delta y/\Delta x$;
for ( $x$ = $x_1$, $y$ = $y_1$; $x$ <= $x_2$; $x$++ ) {
  SetPixel ( $x$, round($y$) );
  $y$ += $m$;
}
Rys. 2.2. Wybór mniejszego błędu.

Zmienne y i m przyjmują wartości ułamkowe, a zatem muszą być typu float; występuje konieczność zaokrąglania współrzędnych, a ponadto błędy zaokrągleń w dodawaniu y+m mogą się kumulować. Zauważmy, że w każdej kolumnie rastra o współrzędnych x między x_{1}x_{2} rysujemy jeden piksel; idziemy zawsze w bok i czasem do góry — wtedy gdy spowoduje to wybranie piksela bliżej odcinka, czyli dającego mniejszy błąd. Algorytm II jawnie wykorzystuje to spostrzeżenie:

$b$ = $0$;
$\Delta x$ = $x_2-x_1$;  $\Delta y$ = $y_2-y_1$;
$m$ = $\Delta y/\Delta x$;
for ( $x$ = $x_1$, $y$ = $y_1$; $x$ <= $x_2$; $x$++ ) {
  SetPixel ( $x$, $y$ );
  $b$ += $m$;
  if ( $b > 1/2$ ) { $y$++;  $b$ -= $1$; }
}

W algorytmie II nadal używamy zmiennych b i m typu real, ale przyjmują one zawsze wartości wymierne, które można sprowadzić do wspólnego mianownika \Delta x (a także 2\Delta x); zatem niech c=2\Delta x\cdot b-\Delta x. Zamiast podstawiać b += m weźmy c += 2\Delta y; zamiast sprawdzać warunek b>1/2 można sprawdzać równoważny warunek c>0. Otrzymujemy w ten sposób algorytm III, w którym wszystkie rachunki są wykonywane na liczbach całkowitych, bez potrzeby zaokrąglania:

$\Delta x$ = $x_2-x_1$;  $\Delta y$ = $y_2-y_1$;
$c$ = $-\Delta x$;
for ( $x$ = $x_1$, $y$ = $y_1$; $x$<=$x_2$; $x$++ ) {
  SetPixel ( $x$, $y$ );
  $c$ += $2\Delta y$;
  if ( $c$ > $0$ ) { $y$++;  $c$ -= $2\Delta x$; }
}

Powyższy algorytm rysowania odcinka nazywa się algorytmem Bresenhama. Obecnie jest on powszechnie implementowany w sprzęcie, tj. procesory stosowane w sterownikach (,,kartach”) graficznych zawierają odpowiednie podukłady, które obliczają kolejne piksele rysowanych odcinków właśnie w ten sposób. Mimo to nieraz zdarza się potrzeba użycia odpowiedniego podprogramu, jeśli zadanie nie polega po prostu na wyświetleniu pikseli.

Aby narysować odcinek, którego końce nie spełniają warunków określonych na początku, trzeba odpowiednio zamienić współrzędne x i y rolami lub zamienić znaki przyrostów współrzędnych. Procedurę rysowania odcinka odpowiednią w każdym przypadku możemy zrealizować tak:

void DrawLine ( int x1, int y1, int x2, int y2 )
{
  int deltax, deltay, g, h, c;

  deltax = x2-x1;
  if ( deltax > 0 ) g = +1; else g = -1;
  deltax = abs(deltax);
  deltay = y2-y1;
  if ( deltay > 0 ) h = +1; else h = -1;
  deltay = abs(deltay);
  if ( deltax > deltay ) {
    c = -deltax;
    while ( x1 != x2 ) {
      SetPixel ( x1, y1 );
      c += 2*deltay;
      if ( c > 0 ) { y1 += h; c -= 2*deltax; }
      x1 += g;
    }
  }
  else {
    c = -deltay;
    while ( y1 != y2 ) {
      SetPixel ( x1, y1 );
      c += 2*deltax;
      if ( c > 0 ) { x1 += g; c -= 2*deltay; }
      y1 += h;
    }
  }
} /*DrawLine*/

Zaletą tej procedury jest fakt, że odcinek zawsze jest rysowany od pierwszego podanego końca (którego współrzędne są początkowymi wartościami zmiennych x_{1} i y_{1}) do drugiego. Drugi koniec (tj. ostatni piksel obrazu odcinka) nie jest rysowany, co łatwo jest uzupełnić, dopisując na końcu wywołanie procedury SetPixel ( x2, y2 ), ale jest to zbędne (a nawet niepożądane) jeśli procedura rysująca odcinek jest używana do narysowania łamanej.

Przyjrzyjmy się jeszcze zawartości poszczególnych wierszy, narysowanej przez algorytm III: w wierszu y_{1} mamy \lceil\frac{\Delta x}{2\Delta y}\rceil pikseli, w kolejnych albo \lfloor\frac{\Delta x}{\Delta y}\rfloor pikseli, albo o 1 więcej, a w ostatnim — resztę. W wielu przypadkach narysowanie jednocześnie kilku sąsiednich pikseli można zrealizować sprawniej niż poprzez rysowanie każdego z nich osobno. Jeśli weźmiemy \tilde{x}_{1}=x_{1}, \tilde{y}_{1}=y_{1}, \tilde{x}_{2}=x_{2}-\lfloor\frac{\Delta x}{\Delta y}\rfloor\Delta y\tilde{y}_{2}=y_{2}, to mamy odcinek, dla którego \tilde{y}_{2}>\tilde{y}_{1}, \tilde{x}_{2}\geq\tilde{x}_{1}\tilde{x}_{2}-\tilde{x}_{1}\leq\tilde{y}_{2}-\tilde{y}_{1}. Rasteryzacja tego odcinka wymaga wyznaczenia y_{2}-y_{1}+1 pikseli, czyli na ogół znacznie mniej niż odcinka wyjściowego. Przypuśćmy, że dysponujemy taką procedurą, wywolywaną przez instrukcję SetHLine ( $x_1$, $x_2$, $y$ );, która rysuje x_{2}-x_{1} pikseli w linii poziomej y, zaczynając od x_{1} (czyli bez x_{2}). Możemy jej użyć w algorytmie Bresenhama dla odcinka o końcach (\tilde{x}_{1},\tilde{y}_{1})(\tilde{x}_{2},\tilde{y}_{2}). Odpowiedni fragment programu ma postać:

if ( $y_2=y_1$ ) SetHLine ( $x_1$, $x_2+1$, $y_1$ );
else {
  $\Delta x$ = $x_2-x_1$;  $\Delta y$ = $y_2-y_1$;
  $m$ = $\Delta x$ / $\Delta y$;  $\Delta\tilde{x}$ = $\Delta x-m$*$\Delta y$;
  $c$ = $-\Delta y$;
  $x_3$ = $x_1-m$ / $2$;  $x_4$ = $x_3+m$;
  SetHLine ( $x_1$, $x_4$, $y_1$ );
  for ( $y$ = $y_1+1$; $y<y_2$ ) {
    $c$ = $c+2\Delta\tilde{x}$;
    $x_3$ = $x_4$;
    if ( $c>0$ ) { $x_4$ = $x_4+m+1$;  $c$ := $c-2\Delta y$; }
           else $x_4$ = $x_4+m$;
    SetHLine ( $x_3$, $x_4$, $y$ );
  }
  SetHLine ( $x_3$, $x_2$, $y_2$ );
}

Oprócz zmniejszenia liczby obliczeń błędów dla odcinków nachylonych pod małymi kątami, do szybkości działania tej procedury przyczynia się fakt, że przypisanie koloru wielu pikselom położonym obok siebie w poziomej linii rastra (przez procedurę SetHLine) może zająć znacznie mniej czasu niż przypisywanie koloru tym pikselom po kolei, m.in. dzięki uproszczeniu obliczania adresów (w pamięci obrazu) sąsiednich pikseli.

2.2. Rysowanie okręgu

Rysując okrąg warto wykorzystać ośmiokrotną symetrię jego obrazu rastrowego; jeśli ma on środek (0,0) i zawiera piksel (x,y), to zawiera on również piksele (-x,y), (-x,-y), (x,-y), (y,x), (-y,x), (-y,-x), (y,-x). Do narysowania wszystkich tych pikseli możemy zastosować procedurę o nazwie np. Set8Pixels, która może też dodać do ich współrzędnych współrzędne środka okręgu. Wystarczy więc wyznaczyć piksele, które tworzą obraz jednej ósmej okręgu. Zasada działania algorytmu Bresenhama rysowania okręgu jest ta sama co w przypadku odcinka: wybieramy kolejne piksele starając się zminimalizować błąd, tj. odległość piksela od przedstawianej na obrazie figury.

Rys. 2.3. Ośmiokrotna symetria okręgu.

Aby wyprowadzić algorytm rysowania okręgu, rozważmy dwie tożsamości:

\displaystyle\sum _{{i=0}}^{x}(2i+1) \displaystyle{}=(x+1)^{2},
\displaystyle\sum _{{i=y}}^{r}(2i-1) \displaystyle{}=r^{2}-(y-1)^{2}.

Wynika z nich, że funkcja

\displaystyle f(x,y)=\sum _{{i=0}}^{x}(2i+1)-\sum _{{i=y}}^{r}(2i-1)\:=:(x+1)^{2}+(y-1)^{2}-r^{2}

ma wartość 0 jeśli punkt (x+1,y-1) leży na okręgu, jest dodatnia jeśli na zewnątrz i ujemna jeśli leży wewnątrz. Przypuśćmy, że ostatnio narysowany piksel to (x,y) i znamy wartość c=f(x,y). Będziemy rysowali od góry, zaczynając w punkcie (0,r). Rysując łuk przesuwamy się zawsze o 1 piksel w prawo i czasem o 1 w dół — wtedy, gdy da to mniejszy błąd, czyli wtedy gdy

\displaystyle|f(x,y)|<|f(x,y+1)|.
Rys. 2.4. Wybór następnego piksela.

Uwaga: To nie zapewnia wyboru piksela bliżej okręgu, tylko piksela, dla którego funkcja f ma mniejszą wartość bezwzględną. Różnica jest tak mała, że w praktyce jest nieistotna.

Mamy f(x,y)=c, f(x,y+1)=c+2y-1, a także (przyda się to za chwilę) f(x+1,y)=c+2x+3 oraz f(x+1,y-1)=f(x+1,y)-2y+3. Ponieważ rysujemy tak, aby zawsze wybierać między dwoma pikselami które leżą po przeciwnych stronach okręgu, więc f(x,y)\leq 0\leq f(x,y+1). Stąd, zamiast porównywać |f(x,y)| i |f(x,y+1)| można sprawdzać, czy -c<c+2y-1, czyli 2c>1-2y. Mamy więc następującą procedurę:

$x$ = $0$;
$y$ = $r$;
$c$ = $2(1-r)$;
while ( $x\leq y$ ) {
  Set8Pixels ( $x$, $y$ );
  if ( $2c > 1-2y$ ) {    /* czasem w dół */
    $y$ --;
    $c$ -= $2y-1$;
  }
  $x$++;                /* zawsze w bok */
  $c$ += $2x+1$;
}

2.3. Rysowanie elips

Jeśli współczynnik aspekt rastra, czyli iloraz szerokości i wysokości piksela (tj. odległości środka piksela od środków pikseli sąsiednich z boku i z góry) jest różny od 1, to zamiast okręgu otrzymamy elipsę; wtedy aby otrzymać obraz okręgu trzeba narysować elipsę, której oś pionowa (mierzona liczbą pikseli) jest aspekt razy dłuższa niż oś pozioma (mierzona też w pikselach). Ponadto czasem potrzebujemy narysować elipsę osiach o dowolnych długościach. Oznaczmy długość półosi poziomej literą a, a pionowej — b. Metoda pierwsza polega na narysowaniu (za pomocą algorytmu Bresenhama opisanego w poprzednim punkcie) okręgu o promieniu równym długości dłuższej półosi, z procedurą Set8Pixels zmienioną w ten sposób, aby zamiast SetPixel ( $x$, $y$ ); wywoływała SetPixel ( $(x$*$a)$/$b$, $y$ ); (tu jest założenie, że b>a) itd. Należy przy tym uważać na nadmiar (mógłby on nas zaskoczyć, gdybyśmy używali arytmetyki szesnastobitowej).

Metoda druga, sporo trudniejsza, polega na narysowaniu okręgu o promieniu r=ab, za pomocą algorytmu opartego na tej samej zasadzie co algorytm Bresenhama. W bok należy poruszać się z krokiem b, a w dół z krokiem a pikseli. Rastrowy obraz elipsy ma tylko czterokrotną symetrię, więc dla każdego kolejnego punktu rysujemy tylko 4 piksele, a nie 8; należy przy tym wyznaczyć ćwiartkę elipsy, od pewnego miejsca poruszając się zawsze w dół i czasem w bok. Również ten algorytm wymaga użycia arytmetyki co najmniej 32-bitowej dla uniknięcia nadmiaru.

Opisane wyżej metody mają na celu rysowanie elips, których jedna oś jest pozioma, a druga pionowa. Jeśli elipsa, którą trzeba narysować nie spełnia tego warunku (tj. jest w położeniu ogólnym), to można zastosować metodę odpowiednią dla dowolnej krzywej ciągłej: wyznaczyć dostatecznie dużo punktów i narysować łamaną.

Aby narysować elipsę (lub dowolny inny obiekt), należy mieć jej odpowiednią reprezentację. Wygodne jest użycie średnic sprzężonych. Jak wiadomo, elipsa jest obrazem okręgu w pewnym przekształceniu afinicznym. Średnice sprzężone elipsy są obrazem pary prostopadłych średnic tego okręgu w tym samym przekształceniu afinicznym. Mając taką reprezentację możemy zastosować strategię ,,dziel i zdobywaj”. Mając dwa punkty końcowe łuku elipsy możemy zbadać, czy leżą one dostatecznie blisko. Jeśli tak, to narysujemy odcinek. Jeśli nie, to wyznaczymy punkt ,,środkowy” tego łuku, a następnie dwa łuki otrzymane z podziału łuku danego w wyznaczonym punkcie narysujemy stosując tę procedurę rekurencyjnie.

Rys. 2.5. Średnice sprzężone elipsy i sposób ich użycia do rysowania.

Rozważmy łuk okręgu jednostkowego o środku [0,0]^{T}, którego końce są wyznaczone przez wektory \bm{v}_{1}=[1,0]^{T} i \bm{v}_{2}=[0,1]^{T}. Wektor \bm{v}_{3}, wyznaczający punkt środkowy tego łuku, jest równy (\bm{v}_{1}+\bm{v}_{2})a_{1}, gdzie a_{1}=1/\sqrt{2}. Dalej możemy obliczyć wektory \bm{v}_{4}=(\bm{v}_{1}+\bm{v}_{3})a_{2} oraz \bm{v}_{5}=(\bm{v}_{2}+\bm{v}_{3})a_{2}. Ogólnie, na k-tym poziomie rekurencyjnego podziału łuku okręgu, sumę wektorów wyznaczających końce łuku mnożymy przez a_{k}=1/\bigl(2\cos(\pi/2^{{k+1}})\bigr). ,,Całą” procedurę rysowania elipsy za pomocą rekurencyjnego podziału możemy zapisać tak:

void r_Elipsa ( $k$, $\bm{c}$, $\bm{v}_1$, $\bm{v}_2$ )
{
  if ( dostatecznie blisko ( $\bm{v}_1$, $\bm{v}_2$ ) )
    rysuj_odcinek ( $\bm{c}+\bm{v}_1$, $\bm{c}+\bm{v}_2$ );
  else {
    $\bm{v}_3$ = $a_k$*$(\bm{v}_1+\bm{v}_2)$;
    r_Elipsa ( $k+1$, $\bm{c}$, $\bm{v}_1$, $\bm{v}_3$ );
    r_Elipsa ( $k+1$, $\bm{c}$, $\bm{v}_3$, $\bm{v}_2$ );
  }
} /*r_Elipsa*/

Parametry wywołania procedury przez program główny to k=1, środek elipsy \bm{c} i wektory \bm{v}_{1}\bm{v}_{2} określające połówki średnic sprzężonych. W przypadku, gdy są one prostopadłe i mają równą długość, procedura narysuje ćwiartkę okręgu.

Współczynniki a_{k} najlepiej jest zawczasu obliczyć i przechowywać w tablicy. Zauważmy, że ograniczając głębokość rekurencji do 10, możemy narysować przybliżenie elipsy w postaci afinicznego obrazu 4096-kąta foremnego, co jest wystarczające w większości zastosowań.

2.4. Wypełnianie wielokątów

Dany jest n-kąt, reprezentowany przez n par (x,y) liczb całkowitych, określających wierzchołki. Należy zamalować piksele w jego wnętrzu.

W dobrze zaprojektowanych pakietach graficznych jest przyjęta i konsekwentnie przestrzegana umowa dotycząca rozstrzygania, czy piksel, którego środek leży na brzegu wielokąta, należy do niego, czy nie. Na przykład:

Rys. 2.6. Piksele należące do wielokąta.
  1. Jeśli środek piksela leży na krawędzi aktywnej, to piksel jest zamalowywany wtedy, gdy wnętrze wielokąta jest z prawej strony krawędzi;

  2. Piksele leżące na krawędzi poziomej są zamalowywane wtedy gdy wnętrze wielokąta leży poniżej tej krawędzi.

Dzięki takiej umowie, jeśli mamy wielokąty o wspólnych krawędziach, to każdy piksel na takiej krawędzi należy do dokładnie jednego wielokąta. Ma to szczególne znaczenie w rysowaniu z przypisywaniem pikselom wartości zależnej od wartości poprzedniej (np. w trybie xor itd.).

Do wykonania zadania posłuży nam następująca reguła parzystości: punkt leży wewnątrz wielokąta, jeśli dowolna półprosta, która z niego wychodzi przecina brzeg wielokąta nieparzystą liczbę razy.

Algorytm przeglądania liniami poziomymi składa się z następujących kroków:

Utwórz tablicę krawędzi (par kolejnych wierzchołków, w tym $(x_n,y_n)$,$(x_1,y_1)$);
Dla każdej krawędzi, jeśli współrzędna $y$ jej drugiego końca jest mniejsza,
     zamień końce; krawędzie poziome usuń z tablicy;
Posortuj tablicę w kolejności rosnących współrzędnych $y$ pierwszego końca;
Utwórz początkowo pustą tablicę krawędzi aktywnych (t.k.a.), czyli przeciętych kolejną linią poziomą;
$y$ = współrzędna $y$ pierwszej krawędzi w tablicy;
do {
  Wstaw $\mbox{do}$ t.k.a. krawędzie, których pierwszy koniec jest na linii $y$;
  Oblicz dla każdej krawędzi w t.k.a. współrzędną $x$ punktu przecięcia z linią poziomą $y$;
  Posortuj t.k.a. w kolejności rosnących współrzędnych $x$ punktów przecięcia;
  Dla kolejnych par krawędzi aktywnych rysuj odcinek poziomy na linii $y$,
      między ich punktami przecięcia z linią $y$;
  $y$ ++;
  Usuń z t.k.a. krawędzie, których drugi koniec jest na linii $y$;
} while ( t.k.a jest niepusta );

Uwaga: Tablica krawędzi aktywnych po każdym uaktualnieniu zawiera parzystą liczbę elementów.

2.5. Wypełnianie obszaru przez zalewanie

Przypuśćmy, że należy zamalować obszar, którego brzeg został narysowany wcześniej i obszar jest określony przez dany na początku obraz. Mamy tu więc problem z pogranicza grafiki i przetwarzania obrazów. Aby rozwiązać takie zadanie, należy je nieco uściślić, przez wprowadzenie dodatkowych pojęć.

Figura rastrowa jest czterospójna, jeśli za sąsiadów dowolnego piksela uznajemy cztery inne piksele (dwa po bokach i po jednym powyżej i poniżej; innymi słowy, sąsiadami piksela (x,y)(x-1,y), (x+1,y), (x,y-1)(x,y+1)) i dla dowolnych dwóch pikseli należących do tej figury istnieje droga złożona z pikseli należących do niej, z których każde dwa kolejne są sąsiadami w podanym wyżej sensie.

Figura jest ośmiospójna, jeśli za sąsiadów piksela uznajemy oprócz podanych wyżej jeszcze cztery piksele, które mają wspólny narożnik z pikselem danym i dla dowolnych dwóch pikseli należących do tej figury istnieje droga złożona z \ldots itd.

Reguły spójności odgrywają dużą rolę w rozpoznawaniu obrazów, które polega na identyfikowaniu linii i innych figur na obrazie; tymczasem zauważmy następującą regułę: brzeg obszaru ośmiospójnego jest czterospójny; brzeg obszaru czterospójnego jest ośmiospójny.

Rys. 2.7. Obszar rastrowy (czterospójny) i jego brzeg.

Mając określone sąsiedztwo pikseli w rastrze, dowolną figurę możemy reprezentować za pomocą grafu sąsiedztwa pikseli; jego wierzchołkami są piksele należące do figury; jego krawędziami są wszystkie krawędzie łączące wierzchołki, które są sąsiednie (w sensie jednej z powyższych definicji).

Algorytm wypełniania przez zalewanie (ang. flood fill) polega na przeszukaniu grafu sąsiedztwa pikseli obszaru, którego reprezentacją jest początkowy obraz rastrowy. Oprócz obrazu należy podać tzw. ziarno, czyli jeden piksel, który należy do obszaru, ale nie do jego brzegu. W wielu książkach jest podana procedura rekurencyjna, która stosuje metodę przeszukiwania grafu w głąb (ang. depth-first search, DFS); w wersji dla obszaru czterospójnego wygląda ona następująco:

void r_FloodFill ( $x$, $y$ )
{
  if ( niezamalowany ( $x$, $y$ ) ) {
    SetPixel ( $x$, $y$ );
    r_FloodFill ( $x+1$, $y$ );
    r_FloodFill ( $x-1$, $y$ );
    r_FloodFill ( $x$, $y+1$ );
    r_FloodFill ( $x$, $y-1$ );
  }
} /*r_FloodFill*/

Wadą przeszukiwania w głąb jest ogromne zapotrzebowanie na pamięć (w tym przypadku stos rekurencyjnych wywołań procedury). Trzeba się liczyć z koniecznością przechowania na nim rekordów aktywacji procedury dla wszystkich pikseli w obszarze (czyli np. rzędu 10^{6}, jeśli obszar jest tak duży jak ekran).

Znacznie lepiej działa przeszukiwanie wszerz (ang. breadth-first search, BFS), które polega na użyciu kolejki. Ziarno wstawiamy do pustej kolejki, a następnie, dopóki kolejka nie jest pusta, wyjmujemy z niej piksel, i jeśli jest niezamalowany, to zamalowujemy go i wstawiamy jego sąsiadów do kolejki. Potrzebna pojemność kolejki jest rzędu liczby pikseli na brzegu obszaru.

Jeszcze sprawniejsza procedura wyznacza graf sąsiedztwa linii; jego wierzchołkami są poziome odcinki (o maksymalnej długości), złożone z pikseli należących do obszaru. Na razie tego tematu nie rozwijam.

2.6. Algorytm z pływającym horyzontem

Jednym z efektownych i użytecznych zastosowań algorytmu Bresenhama jest rysowanie wykresów funkcji dwóch zmiennych, tj. obrazów powierzchni z=f(x,y), z uwzględnieniem widoczności. Właśnie w tym algorytmie potrzebna jest procedura, która obliczy piksele pewnych odcinków i dla każdego z nich wywoła procedury, które rysowanie uzupełniają dodatkowym obliczeniem. W takim zastosowaniu implementacja algorytmu Bresenhama obecna w sprzęcie (w układzie grafiki komputera) jest bezużyteczna.

Rys. 2.8. Wykres funkcji dwóch zmiennych wykonany przy użyciu algorytmu z pływającym horyzontem.

Algorytm rysuje wykres funkcji w danym prostokącie [x_{{\mathrm{min}}},x_{{\mathrm{max}}}]\times[y_{{\mathrm{min}}},y_{{\mathrm{max}}}]. Zakładamy, że funkcja f w tym prostokącie jest ciągła i przyjmuje wartości z pewnego przedziału [z_{{\mathrm{min}}},z_{{\mathrm{max}}}].

Wykres funkcji mieści się więc w kostce [x_{{\mathrm{min}}},x_{{\mathrm{max}}}]\times[y_{{\mathrm{min}}},y_{{\mathrm{max}}}]\times[z_{{\mathrm{min}}},z_{{\mathrm{max}}}], której obraz powinien być wpisany w prostokąt o szerokości w i wysokości h pikseli. Aby jednoznacznie określić odwzorowanie przestrzeni trójwymiarowej na płaszczyznę ekranu, trzeba jeszcze podać wymiary w_{x}, h_{x}h_{z}, zaznaczone na rysunku 2.8. Punktowi (x,y,z) w przestrzeni trójwymiarowej odpowiada na obrazie punkt (\xi,\eta), którego współrzędne są równe

\displaystyle\xi= \displaystyle ax+by+cz+d,
\displaystyle\eta= \displaystyle ex+fy+gz+h.

Współczynniki a,\ldots{,h}, określone na podstawie podanych wymiarów obrazu dla przedstawionej na rysunku orientacji osi układu współrzędnych na ekranie, można obliczyć na podstawie wzorów

\displaystyle a= \displaystyle\frac{w_{x}}{x_{{\mathrm{min}}}-x_{{\mathrm{max}}}}, \displaystyle\quad b= \displaystyle\frac{w-w_{x}}{y_{{\mathrm{max}}}-y_{{\mathrm{min}}}}, \displaystyle\quad c= \displaystyle 0, \displaystyle\quad d= \displaystyle-ax_{{\mathrm{max}}}-by_{{\mathrm{min}}},
\displaystyle e= \displaystyle\frac{h_{x}}{x_{{\mathrm{max}}}-x_{{\mathrm{min}}}}, \displaystyle\quad f= \displaystyle\frac{h-h_{x}-h_{z}}{y_{{\mathrm{max}}}-y_{{\mathrm{min}}}}, \displaystyle\quad g= \displaystyle\frac{h_{z}}{z_{{\mathrm{min}}}-z_{{\mathrm{max}}}}, \displaystyle\quad h= \displaystyle-ex_{{\mathrm{min}}}-fy_{{\mathrm{min}}}-gz_{{\mathrm{max}}}.

Istotne w określeniu tego przekształcenia dla algorytmu z pływającym horyzontem jest to, że obrazy punktów, które mają identyczne współrzędne x i y, mają tę samą współrzędną \xi. Jest to zapewnione przez przyjęcie współczynnika c=0.

Rysowanie wykresu następuje ,,od przodu do tyłu”, przy czym wcześniej narysowane odcinki ograniczają obszar ,,zasłonięty”, w którym nie wolno rysować. W każdej kolumnie pikseli obszar ten jest odcinkiem, którego końcami są najwyższy i najniższy piksel narysowany wcześniej w tej kolumnie. Dla każdej kolumny pikseli potrzebujemy zatem dwóch zmiennych całkowitych do zapamiętania współrzędych \eta tych pikseli. Zmienne te są elementami dwóch tablic, zwanych horyzontami. Horyzont dolny, który ogranicza obszar zasłonięty od dołu, w trakcie rysowania ,,obniża się” (tj. wartości każdego elementu tej tablicy rosną). Podobnie horyzont górny ,,podwyższa się”, przy czym początkową wartością wszystkich elementów tych dwóch tablic jest odpowiednio -1h.

Aby wykonać wykres obliczamy wartości funkcji f w węzłach regularnej siatki wypełniającej prostokąt [x_{{\mathrm{min}}},x_{{\mathrm{max}}}]\times[y_{{\mathrm{min}}},y_{{\mathrm{max}}}], obliczamy (i wpisujemy do tablicy) obrazy punktów (x,y,f(x,y)) (po zaokrągleniu współrzędnych do liczb całkowitych), inicjalizujemy horyzonty i rysujemy odpowiednie odcinki za pomocą algorytmu Bresenhama. Dla każdego piksela wyznaczonego przez ten algorytm sprawdzamy, czy jest on powyżej górnego lub poniżej dolnego horyzontu i jeśli tak, to przypisujemy mu odpowiedni kolor. Następnie uaktualniamy horyzonty, jako że narysowanie piksela w danej kolumnie oznacza rozszerzenie obszaru zasłoniętego. Ale zrobienie tego natychmiast prowadzi do błędów. Następne piksele rysowanego odcinka znajdujące się w tej samej kolumnie też powinny zostać narysowane, a uaktualnienie horyzontu po narysowaniu poprzedniego piksela może spowodować ich pominięcie.

Rozwiązaniem tego problemu jest dwukrotne wywołanie algorytmu Bresenhama dla każdego odcinka, z różnymi procedurami wywoływanymi w celu przetworzenia pikseli. Za pierwszym razem wykonujemy test widoczności i rysowanie, a za drugim razem uaktualniamy horyzonty. Procedura DrawLine, realizująca algorytm Bresenhama, otrzymuje procedurę przetwarzającą piksele jako parametr, zatem jej nagłówek musi być taki:

void DrawLine ( int x1, int y1, int x2, int y2, void (*SetPixel)(int x, int y) );

Jako ostatni parametr będziemy przekazywać dwie różne procedury. Procedura SetPixel1 sprawdza widoczność i rysuje (wywołując ,,prawdziwą” procedurę rysowania piksela), zaś SetPixel2 uaktualnia horyzonty.

Zmienne wdthgh opisują wymiary obrazu (w pikselach). W tablicy ftab są przechowywane końce odcinków do narysowania (w tym kodzie jest to tablica jednowymiarowa, o długości (densx+1)*(densy+1), gdzie parametry densxdensy określają gęstość siatki). Tablice fhupfhdn opisują horyzont górny i dolny (rezerwowanie i zwalnianie pamięci na te tablice zostało pominięte). Procedury SetPixel1SetPixel2 są dodatkowo wywoływane poza procedurą DrawLine po to, aby uzupełnić brak ich wywołania dla ostatniego piksela rysowanych odcinków (w całym obrazie trzeba w ten sposób uzupełnić tylko jeden piksel). Podany niżej fragment programu w C rysuje odcinki parami.

short *fhup, *fhdn;

void SetPixel1 ( int x, int y )
{
  if ( y <= fhdn[x] && y >= fhup[x] )
    return;
  SetPixel ( x, y );
} /*SetPixel1*/

void SetPixel2 ( int x, int y )
{
  if ( y > fhdn[x] ) fhdn[x] = y;
  if ( y < fhup[x] ) fhup[x] = y;
} /*SetPixel2*/

...
  for ( i = 0; i < wdt; i++ )
    { fhup[i] = hgh;  fhdn[i] = -1; }
  for ( j = k = 0; j < densy; j++, k++ ) {
    pa = ftab[k];  pb = ftab[k+1];
    DrawLine ( pa.x, pa.y, pb.x, pb.y, &SetPixel1 );
    DrawLine ( pa.x, pa.y, pb.x, pb.y, &SetPixel2 );
  }
  SetPixel1 ( pb.x, pb.y );  SetPixel2 ( pb.x, pb.y );
  for ( i = 1, k = densy+1; i <= densx; i++, k++ ) {
    pa = ftab[k];  pb = ftab[k-densy-1];
    DrawLine ( pa.x, pa.y, pb.x, pb.y, &SetPixel1 );
    DrawLine ( pa.x, pa.y, pb.x, pb.y, &SetPixel2 );
    for ( j = 0; j < densy; j++, k++ ) {
      pb = pa;  pa = ftab[k+1];  pc = ftab[k-densy];
      DrawLine ( pb.x, pb.y, pa.x, pa.y, &SetPixel1 );
      DrawLine ( pa.x, pa.y, pc.x, pc.y, &SetPixel1 );
      DrawLine ( pb.x, pb.y, pa.x, pa.y, &SetPixel2 );
      DrawLine ( pa.x, pa.y, pc.x, pc.y, &SetPixel2 );
    }
  }
...

Pozostaje mi zaproponować uzupełnienie tego kodu do pełnego programu, uruchomienie, eksperymenty i dorabianie bajerów, takich jak obliczanie kolorów pikseli zależnie od wartości funkcji f, albo rozszerzenie algorytmu umożliwiające rysowanie wykresów ,,z dziurami”.

Treść automatycznie generowana z plików źródłowych LaTeXa za pomocą oprogramowania wykorzystującego LaTeXML.

Projekt współfinansowany przez Unię Europejską w ramach Europejskiego Funduszu Społecznego.

Projekt współfinansowany przez Ministerstwo Nauki i Szkolnictwa Wyższego i przez Uniwersytet Warszawski.