Tworzenie grafiki SDL

Poprzednie tematy, które należy przerobić przed przystąpieniem do tej lekcji:

01 - Instalacja biblioteki SDL dla Dev-C++
02 - Powierzchnia graficzna w SDL - stawianie punktów
03 - Tworzenie biblioteki graficznej mylib
04 - Stawianie punktów i rysowanie linii poziomych oraz pionowych
05 - Zabawa z pikselami

Pliki biblioteczne i projektowe do pobrania: Parametry dla konsolidatora
mylib.h
mylib.cpp
main.cpp
-lmingw32
-mwindows
-lSDLmain
-lSDL

Opis funkcji bibliotecznych

Na tej lekcji omawiamy popularny algorytm Bresenhama rysowania odcinków. Jeśli nie interesują cię sprawy techniczne SDL, to przejdź do opisu nowych funkcji oraz do następnej lekcji, gdzie znajdziesz ich praktyczne zastosowania - nie zapomnij pobrać z naszego serwisu plików biblioteki mylib.cpp oraz mylib.h.

Rysowanie odcinków - algorytm Bresenhama

SDL

Idea algorytmu Bresenhama jest następująca:

 

Mamy siatkę (raster) punktów. Każdy punkt posiada odpowiednie współrzędne całkowite (x,y). Oś y jest skierowana w dół ze względów technicznych.

 

 

Na siatce wybieramy dwa punkty o współrzędnych (x1,y1) oraz (x2,y2). Współrzędne odnoszą się do środka piksela. Bez zmniejszania ogólności załóżmy, iż punkty te wybrano tak, aby odcinek (x1,y1)-(x2,y2) tworzył z osią OX kąt w przedziale od 0 do 45°. Inne przypadki, jak zobaczymy dalej, da się prosto sprowadzić do tego przypadku przy pomocy prostych transformacji współrzędnych. Wybrane punkty mają być połączone odcinkiem.

 

Zadanie sprowadza się do pokolorowania kolejnych pikseli (oczek rastra), których środki leżą najbliżej punktu na odcinku o tej samej współrzędnej x, co dany piksel. Zwróć uwagę, iż ze względu na nasze założenie o kącie nachylenia odcinka względem OX, w kierunku X współrzędne kolejnych pikseli są zwiększane zawsze o 1, natomiast w kierunku Y odbywa się to mniej często. Kierunek X nazwiemy szybkim, a kierunek Y wolnym.

 

Algorytm Bresenhama określa, kiedy należy wykonać ruch w kierunku wolnym Y (bo w kierunku szybkim X ruch wykonujemy zawsze!). Rozważmy równanie prostej przechodzącej przez dwa punkty (x1,y1) i (x2,y2):

W powyższym równaniu x oznacza współrzędną środka kolejnego piksela (punkty niebieskie). Współrzędna y natomiast odnosi się do punktu leżącego na prostej zawierającej odcinek (punkty czerwone). Środek piksela jest zwykle w pewnej odległości od odpowiadającego mu punktu na odcinku. Oznaczmy tę odległość przez ddy, a współrzędną y środka piksela przez yp. Zatem możemy zapisać:

Wstawmy to wyrażenie do równania prostej:

Teraz przekształćmy wyrażenie następująco:

Wyrażenie -ddydx jest tzw. wyrażeniem błędu (ang. error term). Zgodnie ze wzorem krok w kierunku szybkim X powoduje zmniejszenie wyrażenia błędu o dy. Jeśli wartość wyrażenia będzie ujemna, to wykonujemy krok w kierunku wolnym Y, czyli zwiększamy je o dx. Ponieważ dxdy, to wyrażenie błędu sprowadzi się znów do wartości dodatniej lub 0. Na tej podstawie algorytm Bresenhama określa kiedy należy wykonać ruch w kierunku Y - stara się zawsze utrzymać wyrażenie błędu w zakresie liczb nieujemnych. Wartości ddy wcale nie musimy obliczać. Bardzo ważna jest wartość początkowa wyrażenia błędu. Zwykle przyjmuje się ją równą dx/2.

Sformułujmy algorytm Bresenhama dla tego przypadku:

Wejście

x1,y1 - całkowite współrzędne punktu startowego
x2,y2 - całkowite współrzędne punktu końcowego
Założenie: x2 > x1, y2 > y1, x2 - x1 > y2 - y1

Wyjście

Rysunek rastrowy odcinka łączącego punkt x1,y1 z punktem x2,y2.

Zmienne pomocnicze

dx - odległość x2 od x1
dy - odległość y2 od y1
e - wartość wyrażenia błędu

Lista kroków

K01: dxx2 - x1 ; obliczamy odległości dx i dy
K02: dy ← y2 - y1  
K03: edx / 2 ; ustalamy wartość początkową wyrażenia błędu
K05: Zapal piksel x1,y1 ; zapalamy pierwszy piksel odcinka
K04: Wykonuj dx razy kroki K06...K10 ; w pętli zapalamy kolejne piksele
K06:     x1x1 + 1 ; ruch w kierunku szybkim
K07:     ee - dy ; modyfikujemy po ruchu wyrażenie błędu
K08:     Jeśli e ≥ 0, idź do K11 ; jeśli e nieujemne, pomijamy ruch w kierunku wolnym
K09:     y1y1 + 1 ; ruch w kierunku wolnym
K10:     ee + dx ; po ruchu wolnym modyfikujemy wyrażenie błędu
K11:     Zapal piksel x1,y1 ; zapalamy kolejne piksele odcinka
K12: Koniec  

 

Prześledzimy działanie tego algorytmu na prostym przypadku.

Lp. Obrazek Opis
1. Połączymy odcinkiem punkty: (1,1) i (7,5)

Zatem:

x1 = 1, y1 = 1
x2 = 7, y2 = 5
dx = x2 - x1 = 7 - 1 = 6
dy = y2 - y1 = 5 - 1 = 4
e = dx/2 = 6/2 = 3

2. Zapalamy pierwszy punkt na współrzędnych x1,y1, czyli (1,1)
3. Na osi X przesuwamy się o 1 (kierunek szybki):
x1 = x1 + 1 = 1 + 1 = 2
Modyfikujemy wyrażenie błędu:
e = e - dy = 3 - 4 = -1.
Ponieważ e jest ujemne, wykonujemy ruch w kierunku wolnym Y:
y1 = y1 + 1 = 1 + 1 = 2
Modyfikujemy wyrażenie błędu:
e = e + dx = -1 + 6 = 5
Zapalamy punkt (x1,y1), czyli (2,2).
4. Na osi X przesuwamy się o 1.
x1 = x1 + 1 = 2 + 1 = 3
Obliczamy wyrażenie błędu:
e = e - dy = 5 - 4 = 1
Ponieważ e nie jest ujemne , nie przesuwamy się na osi Y. Zapalamy punkt (3,2).
5. Na osi X przesuwamy się o 1 i wyliczamy nowe wyrażenie błędu:
x1 = x1 + 1 = 3 + 1 = 4
e = e - dy = 1 - 4 = -3.
Ponieważ e jest ujemne, wykonujemy ruch w kierunku wolnym Y:
y1 = y1 + 1 = 2 + 1 = 3
Modyfikujemy wyrażenie błędu:
e = e + dx = -3 + 6 = 3
Zapalamy punkt (x1,y1), czyli (4,3).
6. Na osi X przesuwamy się o 1 i wyliczamy e
x1 = x1 + 1 = 4 + 1 = 5
e = e - dy = 3 - 4 = -1.
Ponieważ e jest ujemne, wykonujemy ruch w kierunku wolnym Y:
y1 = y1 + 1 = 3 + 1 = 4
Modyfikujemy wyrażenie błędu:
e = e + dx = -1 + 6 = 5
Zapalamy punkt (x1,y1), czyli (5,4).
7. Na osi X przesuwamy się o 1 i wyliczamy nowe e:
x1 = x1 + 1 = 5 + 1 = 6
e = e - dy = 5 - 4 = 1
Ponieważ e nie jest ujemne , nie przesuwamy się na osi Y. Zapalamy punkt (6,4).
8. Ostatni krok algorytmu:

x1 = x1 + 1 = 6 + 1 = 7
e = e - dy = 1 - 4 = -3.
Ponieważ e jest ujemne, wykonujemy ruch w kierunku wolnym Y:
y1 = y1 + 1 = 4 + 1 = 5
e = e + dx = -3 + 6 = 3
Zapalamy punkt (x1,y1), czyli (7,5). Jest to końcowy punkt odcinka. Zadanie wykonane.

 

Przedstawiony powyżej algorytm Bresenhama działa poprawnie jedynie dla przypadku, gdy odcinek tworzy z osią OX kąt mniejszy lub równy 45°. Pokażemy teraz, jak rozwiązać pozostałe przypadki.

 

Ogólny algorytm Bresenhama

Poniżej przedstawiamy pełny algorytm Bresenhama, który rysuje odcinki pomiędzy dowolnymi punktami na powierzchni graficznej. Inne przypadki nachyleń są sprowadzane do przypadku podstawowego przez odpowiednią podmianę współrzędnych punktów odcinka.

Wejście

x1,y1 - całkowite współrzędne punktu startowego
x2,y2 - całkowite współrzędne punktu końcowego

Wyjście

Rysunek rastrowy odcinka łączącego punkt x1,y1 z punktem x2,y2. Współrzędne są dowolne, całkowite.

Dane pomocnicze

dx - odległość współrzędnych x1 i x2
dy - odległość współrzędnych y1, y2
kx - krok po osi X, 1 lub -1
ky - krok po osi y, 1 lub -1
e - wartość wyrażenia błędu

Lista kroków

K01: Jeżeli x1x2, to kx ← 1, inaczej kx ← -1 ; określamy krok X od x1 do x2
K02: Jeżeli y1y2, to ky ← 1, inaczej ky ← -1 ; określamy krok Y od y1 do y2
K03: dx ← |x2 - x1| ; odległość pomiędzy x1 i x2
K04: dy ← |y2 - y1| ; odległość pomiędzy y1 i y2
K05: Zapal piksel x1,y1 ; pierwszy piksel odcinka
K06: Jeżeli dx < dy, idź do K16 ; dla kątów > 45° wykonujemy wersję algorytmu z przestawionymi współrzędnymi
K07: edx / 2 ; obliczamy wartość początkową wyrażenia błędu
K08: Powtarzaj dx razy kroki K09...K14 ; rysujemy pozostałe piksele w pętli
K09:     x1x1 + kx ; przesuwamy się w odpowiednią stronę w kierunku szybkim
K10:     ee - dy ; obliczamy wyrażenie błędu
K11:     Jeżeli e ≥ 0, idź do K14 ; jeśli wyrażenie błędu jest nieujemne, pomijamy ruch w kierunku wolnym
K12:     y1y1 + ky ; przesuwamy się w odpowiednią stronę w kierunku wolnym
K13:     ee + dx ; obliczamy nowe wyrażenie błędu
K14:     Zapal piksel x1.y1 ; kolejny piksel odcinka
K15: Zakończ  
K16: edy / 2 ; wersja algorytmu Bresenhama ze zamienionymi współrzędnymi x i y
K17: Powtarzaj dy razy kroki K18...K23  
K18:     y1y1 + ky  
K19:     ee - dx  
K20:     Jeżeli e ≥ 0, idź do K23  
K21:     x1x1 + kx  
K22:     ee + dy  
K23:     Zapal piksel x1,y1  
K24: Zakończ  

Na podstawie podanego powyżej algorytmu tworzymy funkcję biblioteczną line() - znajdziesz ją w naszej bibliotece mylib.cpp lub jeśli tworzysz tę bibliotekę samodzielnie, to przepisz do pliku mylib.cpp poniższy kod funkcji line(). Funkcja rysuje dowolny odcinek w obszarze graficznym. Jest już zoptymalizowana w celu przyspieszenia obliczeń adresów pikseli. Jednakże realizuje dokładnie algorytm Bresenhama:

 

// Rysuje odcinek linii prostej
//-----------------------------

void line(Uint32 x1, Uint32 y1, Uint32 x2, Uint32 y2, Uint32 color)
{
  Uint32 * p;
  int dx, dy, kx, ky, e;
  
  kx = (x1 <= x2) ? 1 : -1;
  ky = (y1 <= y2) ? screen->w : -screen->w;
  
  dx = x2 - x1; if(dx < 0) dx = -dx;
  dy = y2 - y1; if(dy < 0) dy = -dy;
  
  p = (Uint32 *)screen->pixels + y1 * screen->w + x1;
  * p = color;
  
  if(dx >= dy)
  {
    e = dx >> 1;
    for(int i = 0; i < dx; i++)
    {
      p += kx;  e -= dy;
      if(e < 0)
      {
        p += ky; e += dx;
      }
      * p = color;
    } 
  }
  else
  {
    e = dy >> 1;
    for(int i = 0; i < dy; i++)
    {
      p += ky; e -= dx;
      if(e < 0)
      {
        p += kx; e += dy;
      }
      * p = color;
    }       
  }
}
 

Oprócz funkcji line() zdefiniujemy dodatkowo dwie funkcje, które bardzo przydają się przy rysowaniu łamanych:

 

// współrzędne początku odcinka dla lineto()
//------------------------------------------------------------------

Uint32 gfx_x_coord = 0; 
Uint32 gfx_y_coord = 0;

// Ustawia współrzędne początku odcinka
//------------------------------------------------------------------

void moveto(Uint32 x, Uint32 y)
{
     gfx_x_coord = x; gfx_y_coord = y;
}

// Rysuje odcinek od zapamiętanych współrzędnych
// do nowych współrzędnych, które po operacji są zapamiętywane.
//------------------------------------------------------------------

void lineto(Uint32 x, Uint32 y, Uint32 color)
{
   line(gfx_x_coord, gfx_y_coord, x, y, color);
   gfx_x_coord = x; gfx_y_coord = y;
}

 

W pliku mylib.h znajdziesz prototypy tych funkcji - jeśli tworzysz bibliotekę mylib samodzielnie, to przepisz do pliku mylib.h prototypy zdefiniowanych powyżej funkcji:

 

void line(Uint32 x1, Uint32 y1, Uint32 x2, Uint32 y2, Uint32 color);
void moveto(Uint32 x, Uint32 y);
void lineto(Uint32 x, Uint32 y, Uint32 color);

 

Opis funkcji

line(x1,y1,x2,y2,color)

Rysuje odcinek w kolorze color od punktu (x1,y1) do (x2,y2). Odcinek w całości powinien mieścić się na obszarze graficznym.

moveto(x,y)

Ustala początek odcinka w punkcie (x,y). Punkt ten powinien leżeć w obszarze graficznym.

lineto(x,y,color)

Rysuje odcinek od poprzednio ustawionego punktu przez moveto() lub lineto() do punktu (x,y). Rysowany odcinek powinien mieścić się w obszarze graficznym.

 



List do administratora Serwisu Edukacyjnego Nauczycieli I LO

Twój email: (jeśli chcesz otrzymać odpowiedź)
Temat:
Uwaga: ← tutaj wpisz wyraz  ilo , inaczej list zostanie zignorowany

Poniżej wpisz swoje uwagi lub pytania dotyczące tego rozdziału (max. 2048 znaków).

Liczba znaków do wykorzystania: 2048

 

W związku z dużą liczbą listów do naszego serwisu edukacyjnego nie będziemy udzielać odpowiedzi na prośby rozwiązywania zadań, pisania programów zaliczeniowych, przesyłania materiałów czy też tłumaczenia zagadnień szeroko opisywanych w podręcznikach.



   I Liceum Ogólnokształcące   
im. Kazimierza Brodzińskiego
w Tarnowie

©2017 mgr Jerzy Wałaszek

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.