Prezentowane materiały są przeznaczone dla uczniów szkół ponadgimnazjalnych. Autor artykułu: mgr Jerzy Wałaszek,  wersja1.0

©2008 mgr Jerzy Wałaszek I LO w Tarnowie

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

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

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 (x₁,y₁) oraz (x₂,y₂). Współrzędne odnoszą się do środka piksela. Bez zmniejszania ogólności załóżmy, iż punkty te wybrano, tak aby odcinek (x₁,y₁)-(x₂,y₂) 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 (x₁,y₁) i (x₂,y₂):

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 y_p. Zatem możemy zapisać:

Wstawmy to wyrażenie do równania prostej:

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

Wyrażenie -ddy•dx  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ż dx  ≥ dy, 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

x₁,y₁ - całkowite współrzędne punktu startowego
x₂,y₂ - całkowite współrzędne punktu końcowego
Założenie: x₂ > x₁, y₂ > y₁, x₂ - x₁ > y₂ - y₁

Wyjście

Rysunek rastrowy odcinka łączącego punkt x₁,y₁ z punktem x₂,y₂.

Zmienne pomocnicze

dx  - odległość x₂ od x₁
dy  - odległość y₂ od y₁
e  - wartość wyrażenia błędu

Lista kroków

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

x₁,y₁ - całkowite współrzędne punktu startowego
x₂,y₂ - całkowite współrzędne punktu końcowego

Wyjście

Rysunek rastrowy odcinka łączącego punkt x₁,y₁ z punktem x₂,y₂. Współrzędne są dowolne, całkowite.

Dane pomocnicze

dx  - odległość współrzędnych x₁ i x₂
dy  - odległość współrzędnych y₁, y₂
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

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(x₁,y₁,x₂,y₂,color)

Rysuje odcinek w kolorze color od punktu (x₁,y₁) do (x₂,y₂). 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.

---

I Liceum Ogólnokształcące    im. Kazimierza Brodzińskiego w Tarnowie ©2024 mgr Jerzy Wałaszek

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

Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl

W artykułach serwisu są używane cookies. Jeśli nie chcesz ich otrzymywać,
zablokuj je w swojej przeglądarce.
Informacje dodatkowe