Grafika komputerowa: algorytm Bresenhama

W bibliotece SDL 2 masz do dyspozycji następujące funkcje graficzne związane z pikselami i liniami na teksturze sprzętowej:

SDL_SetRenderDrawColor(r,cr,cg,cb,ca) – ustawia kolor dla operacji graficznej.
r – wskaźnik struktury SDL_Renderer
cr – składowa czerwona
cg – składowa zielona
cb – składowa niebieska
ca – przezroczystość koloru

SDL_RenderDrawPoint(r,x,y) – rysuje punkt w bieżącym kolorze.
r – wskaźnik struktury SDL_Renderer
x,y – współrzędne punktu

SDL_RenderDrawPoints(r,P,n) – rysuje zadaną liczbę punktów z tablicy
r – wskaźnik struktury SDL_Renderer
P – tablica struktur typu SDL_Point, która definiuje współrzędne punktów
n – liczba wierzchołków w tablicy p

SDL_RenderDrawLine(r,x1,y1,x2,y2) – rysuje odcinek
r – wskaźnik struktury SDL_Renderer
x1,y1 – współrzędne punktu początkowego odcinka
x2,y2 – współrzędne punktu końcowego odcinka

SDL_RenderDrawLines(r,P,n) – rysuje łamaną
r – wskaźnik struktury SDL_Renderer
P – tablica struktur typu SDL_Point, która definiuje współrzędne kolejnych wierzchołków łamanej
n – liczba wierzchołków w tablicy p.

Zdarza się jednak, iż chcesz narysować odcinek w sposób specyficzny, np. linią przerywaną lub gradientem. W takim przypadku zastosowanie funkcji bibliotecznych jest kłopotliwe. Do rysowania odcinków na powierzchni rastrowej (tj. zbudowanej z dyskretnych pikseli) wykorzystuje się tzw. algorytm Bresenhama. Algorytm ten zaprojektował w roku 1965 informatyk amerykański Jack Elton Bresenham. Zaletą tego algorytmu jest duża szybkość działania oraz prostota. W poprzednim rozdziale o figurach podaliśmy wersje algorytmu Bresenhama dla okręgów i elips. Tutaj opiszemy podstawowy algorytm Bresenhama, który dotyczy odcinków prostych.

Na początek określmy, co chcemy uzyskać.

Mamy siatkę (raster) pikseli o współrzędnych całkowitych. Oś y skierowana jest w dół, oś x skierowana jest w prawo (tak zbudowane są powierzchnie graficzne tekstur w SDL 2):

Na siatce wybieramy dwa punkty o współrzędnych (x₁,y₁) oraz (x₂,y₂). Współrzędne odnoszą się do środka piksela (przyjmuje się, że piksel jest kwadratem o boku równym 1 i środku w punkcie x,y). 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 w artykule, 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, których środki leżą najbliżej punktu znajdującego się na odcinku i posiadającego tę samą współrzędną x, co piksel. Zwróć uwagę, iż ze względu na nasze założenie, w kierunku X współrzędne kolejnych pikseli są zwiększane zawsze co 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ć:

Przyrównujemy do siebie oba wyrażenia, ponieważ oba są równe y:

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 dodatnich i zera. 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 opisanego wyżej 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

K01:	dx ← x₂ - x₁	; obliczamy odległości dx i dy
K02:	dy ← y₂ - y₁
K03:	e ← dx / 2	; ustalamy wartość początkową wyrażenia błędu
K05:	Rysuj piksel x₁,y₁	; zapalamy pierwszy piksel odcinka
K04:	Wykonuj dx razy kroki K06...K10	; w pętli zapalamy kolejne piksele
K06:	x₁ ← x₁ + 1	; ruch w kierunku szybkim
K07:	e ← e - dy	; modyfikujemy po ruchu wyrażenie błędu
K08:	Jeśli e ≥ 0, to idź do kroku K11	; jeśli e nieujemne, pomijamy ruch w kierunku wolnym
K09:	y₁ ← y₁ + 1	; ruch w kierunku wolnym
K10:	e ← e + dx	; po ruchu wolnym modyfikujemy wyrażenie błędu
K11:	Rysuj piksel x₁,y₁	; zapalamy kolejne piksele odcinka
K12:	Zakończ

Prześledzimy działanie tego algorytmu na prostym przykładzie.

Lp.	Raster	Opis
1.		Połączymy odcinkiem punkty: (1,1) i (7,5) Zatem: x₁ = 1, y₁ = 1 x₂ = 7, y₂ = 5 dx = x₂ - x₁ = 7 - 1 = 6 dy = y₂ - y₁ = 5 - 1 = 4 e = ^dx/₂ = ⁶/₂ = 3
2.		Rysujemy pierwszy punkt na współrzędnych x₁,y₁, czyli (1,1)
3.		Na osi X przesuwamy się o 1 (kierunek szybki): x₁ = x₁ + 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: y₁ = y₁ + 1 = 1 + 1 = 2 Modyfikujemy wyrażenie błędu: e = e + dx = -1 + 6 = 5 Rysujemy punkt (x₁,y₁), czyli (2,2).
4.		Na osi X przesuwamy się o 1. x₁ = x₁ + 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. Rysujemy punkt (3,2).
5.		Na osi X przesuwamy się o 1 i wyliczamy nowe wyrażenie błędu: x₁ = x₁ + 1 = 3 + 1 = 4 e = e - dy = 1 - 4 = -3. Ponieważ e jest ujemne, wykonujemy ruch w kierunku wolnym Y: y₁ = y₁ + 1 = 2 + 1 = 3 Modyfikujemy wyrażenie błędu: e = e + dx = -3 + 6 = 3 Rysujemy punkt (x₁,y₁), czyli (4,3).
6.		Na osi X przesuwamy się o 1 i wyliczamy e x₁ = x₁ + 1 = 4 + 1 = 5 e = e - dy = 3 - 4 = -1. Ponieważ e jest ujemne, wykonujemy ruch w kierunku wolnym Y: y₁ = y₁ + 1 = 3 + 1 = 4 Modyfikujemy wyrażenie błędu: e = e + dx = -1 + 6 = 5 Rysujemy punkt (x₁,y₁), czyli (5,4).
7.		Na osi X przesuwamy się o 1 i wyliczamy nowe e: x₁ = x₁ + 1 = 5 + 1 = 6 e = e - dy = 5 - 4 = 1 Ponieważ e nie jest ujemne , nie przesuwamy się na osi Y. Rysujemy punkt (6,4).
8.		Ostatni krok algorytmu: x₁ = x₁ + 1 = 6 + 1 = 7 e = e - dy = 1 - 4 = -3. Ponieważ e jest ujemne, wykonujemy ruch w kierunku wolnym Y: y₁ = y₁ + 1 = 4 + 1 = 5 e = e + dx = -3 + 6 = 3 Rysujemy punkt (x₁,y₁), 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°.

Poniższy program wykorzystuje przedstawiony algorytm do narysowania odcinka od lewego górnego narożnika okna do prawego dolnego (szerokość okna nie może być większa o jego wysokości):

C++

// Algorytm Bresenhama 1
//----------------------

#include <SDL.h>
#include <iostream>

using namespace std;

// Rozmiar okienka
const int W_W = 640;
const int W_H = 480;


int main(int argc, char* args[])
{
   // Inicjujemy SDL
  if(SDL_Init(SDL_INIT_VIDEO))
  {
    cout << "SDL_Init Error: " << SDL_GetError() << endl;
    return 1;
  }

  // Tworzymy okno
  SDL_Window * w = SDL_CreateWindow("Bresenham", SDL_WINDOWPOS_CENTERED, SDL_WINDOWPOS_CENTERED, W_W, W_H, 0);
  if(!w)
  {
    cout << "SDL_CreateWindow Error: " << SDL_GetError() << endl;
    SDL_Quit();
    return 2;
  }

  // Tworzymy kontekst graficzny
  SDL_Renderer * r = SDL_CreateRenderer(w,0,SDL_RENDERER_PRESENTVSYNC);
  if(!r)
  {
     cout << "SDL_CreateRenderer Error: " << SDL_GetError() << endl;
     SDL_DestroyWindow(w);
     SDL_Quit();
     return 3;
  }

  // Algorytm Bresenhama
  int x1,y1,x2,y2,dx,dy,e,i;

  // Współrzędne punktów startowego i końcowego
  x1 = y1 = 0;  // Lewy górny narożnik okna
  x2 = W_W - 1;
  y2 = W_H - 1; // Prawy dolny narożnik okna

  SDL_SetRenderDrawColor(r,255,255,255,255); // Białe piksele

  dx = x2 - x1;
  dy = y2 - y1;
  e = dx / 2;

  // Rysujemy pierwszy piksel

  SDL_RenderDrawPoint(r,x1,y1);

  // Pętla rysująca pozostałe piksele
  for(i = 0; i < dx; i++)
  {
    x1++;     // Ruch w kierunku szybkim
    e -= dy;  // Wyrażenie błędu
    if(e < 0)
    {
        y1++; // Ruch w kierunku wolnym
        e += dx;
    }

    // Rysujemy kolejny piksel
    SDL_RenderDrawPoint(r,x1,y1);
  }

  // Uaktualniamy treść okna na ekranie
  SDL_RenderPresent(r);

  // Czekamy na zamknięcie okna graficznego
  SDL_Event event;
  while(1)
  {
    // Sprawdzamy, czy użytkownik zamyka program
    if(SDL_PollEvent(&event) && event.type == SDL_QUIT) break;
  }

  // Usuwamy kontekst graficzny
  SDL_DestroyRenderer(r);

  // Usuwamy okno
  SDL_DestroyWindow(w);

  // Kończymy pracę z SDL2
  SDL_Quit();

  return 0;
}

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

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

Poniższy program wykorzystuje algorytm Bresenhama do rysowania odcinków o losowych współrzędnych:

C++

// Algorytm Bresenhama 2
//----------------------

#include <SDL.h>
#include <iostream>
#include <cstdlib>
#include <ctime>

using namespace std;

// Rozmiar okienka
const int W_W = 640;
const int W_H = 480;


// Funkcja rysuje odcinek algorytmem Bresenhama
//---------------------------------------------
void SDL_RenderBresenhamLine(SDL_Renderer * r, int x1, int y1, int x2, int y2)
{
  int dx,dy,kx,ky,e,i;

  // Przyrosty w osiach x i y
  if(x1 <= x2) kx = 1; else kx = -1;
  if(y1 <= y2) ky = 1; else ky = -1;

  // Odległości pomiędzy punkatami startowym a końcowym wzdłuż osi
  dx = x2 - x1; if(dx < 0) dx = -dx;
  dy = y2 - y1; if(dy < 0) dy = -dy;

  // Rysujemy punkt startowy
  SDL_RenderDrawPoint(r,x1,y1);

  // Wybieramy wersję algorytmu Bresenhama
  if(dx >= dy)
  {
    // Wersja podstawowa

    e = dx / 2;   // Wyrażenie błędu

    for(i = 0; i < dx; i++)
    {
      x1 += kx;   // Ruch w kierunku szybkim
      e -= dy;    // Nowe wyrażenie błędu
      if(e < 0)
      {
        y1 += ky; // Ruch w kierunku wolnym
        e += dx;
      }

      // Rysujemy kolejny piksel
      SDL_RenderDrawPoint(r,x1,y1);
    }
  }
  else
  {
    // Wersja z zamienionymi współrzędnymi

    e = dy / 2;   // Wyrażenie błędu

    for(i = 0; i < dy; i++)
    {
      y1 += ky;   // Ruch w kierunku szybkim
      e -= dx;    // Nowe wyrażenie błędu
      if(e < 0)
      {
        x1 += kx; // Ruch w kierunku wolnym
        e += dy;
      }

      // Rysujemy kolejny piksel
      SDL_RenderDrawPoint(r,x1,y1);
    }
  }
}
int main(int argc, char* args[])
{
   // Inicjujemy SDL
  if(SDL_Init(SDL_INIT_VIDEO))
  {
    cout << "SDL_Init Error: " << SDL_GetError() << endl;
    return 1;
  }

  // Tworzymy okno
  SDL_Window * w = SDL_CreateWindow("Bresenham", SDL_WINDOWPOS_CENTERED, SDL_WINDOWPOS_CENTERED, W_W, W_H, 0);
  if(!w)
  {
    cout << "SDL_CreateWindow Error: " << SDL_GetError() << endl;
    SDL_Quit();
    return 2;
  }

  // Tworzymy kontekst graficzny
  SDL_Renderer * r = SDL_CreateRenderer(w,0,SDL_RENDERER_PRESENTVSYNC);
  if(!r)
  {
     cout << "SDL_CreateRenderer Error: " << SDL_GetError() << endl;
     SDL_DestroyWindow(w);
     SDL_Quit();
     return 3;
  }

  srand(time(NULL));

  // Animacja
  SDL_Event event;
  while(1)
  {
    SDL_SetRenderDrawColor(r,rand() % 256,rand() % 256,rand() % 256,255);
    SDL_RenderBresenhamLine(r,rand() % W_W,rand() % W_H,rand() % W_W,rand() % W_H);

    // Uaktualniamy treść okna na ekranie
    SDL_RenderPresent(r);

    // Sprawdzamy, czy użytkownik zamyka program
    if(SDL_PollEvent(&event) && event.type == SDL_QUIT) break;
  }

  // Usuwamy kontekst graficzny
  SDL_DestroyRenderer(r);

  // Usuwamy okno
  SDL_DestroyWindow(w);

  // Kończymy pracę z SDL2
  SDL_Quit();

  return 0;
}

Na razie nie mamy żadnych korzyści w porównaniu z funkcją biblioteczną SDL_RenderDrawLine(). Dalej pokażemy jednak, jak takie korzyści otrzymać.

Na początek: podrozdziału strony

Linie przerywane w algorytmie Bresenhama łatwo uzyskamy wykorzystując wzorzec bitowy. Funkcja rysująca odcinek otrzyma w dodatkowym parametrze liczbę 32-bitową. W trakcie rysowania pikseli odcinka będą badane w kółko kolejne bity tej liczby. Jeśli dany bit będzie miał wartość 1, to zostanie postawiony punkt na powierzchni graficznej, jeśli bit będzie miał wartość 0, punkt nie będzie stawiany. Do badania bitów wykorzystamy maskę bitową oraz operację bitowe and.

Poniższy program pokazuje, jak to zrobić:

C++

// Algorytm Bresenhama 3
//----------------------

#include <SDL.h>
#include <iostream>
#include <cstdlib>
#include <ctime>

using namespace std;

// Rozmiar okienka
const int W_W = 640;
const int W_H = 480;


// Funkcja rysuje odcinek algorytmem Bresenhama
//---------------------------------------------
void SDL_RenderBresenhamLine(SDL_Renderer * r, int x1, int y1, int x2, int y2, unsigned p)
{
  int dx,dy,kx,ky,e,i;
  unsigned mask = 0;

  // Przyrosty w osiach x i y
  if(x1 <= x2) kx = 1; else kx = -1;
  if(y1 <= y2) ky = 1; else ky = -1;

  // Odległości pomiędzy punkatami startowym a końcowym wzdłuż osi
  dx = x2 - x1; if(dx < 0) dx = -dx;
  dy = y2 - y1; if(dy < 0) dy = -dy;

  // Rysujemy punkt startowy
  mask >>= 1; if(!mask) mask = 0x80000000;
  if(p & mask)SDL_RenderDrawPoint(r,x1,y1);

  // Wybieramy wersję algorytmu Bresenhama
  if(dx >= dy)
  {
    // Wersja podstawowa

    e = dx / 2;   // Wyrażenie błędu

    for(i = 0; i < dx; i++)
    {
      x1 += kx;   // Ruch w kierunku szybkim
      e -= dy;    // Nowe wyrażenie błędu
      if(e < 0)
      {
        y1 += ky; // Ruch w kierunku wolnym
        e += dx;
      }

      // Rysujemy kolejny piksel
      mask >>= 1; if(!mask) mask = 0x80000000;
      if(p & mask)SDL_RenderDrawPoint(r,x1,y1);
    }
  }
  else
  {
    // Wersja z zamienionymi współrzędnymi

    e = dy / 2;   // Wyrażenie błędu

    for(i = 0; i < dy; i++)
    {
      y1 += ky;   // Ruch w kierunku szybkim
      e -= dx;    // Nowe wyrażenie błędu
      if(e < 0)
      {
        x1 += kx; // Ruch w kierunku wolnym
        e += dy;
      }

      // Rysujemy kolejny piksel
      mask >>= 1; if(!mask) mask = 0x80000000;
      if(p & mask)SDL_RenderDrawPoint(r,x1,y1);
    }
  }
}
int main(int argc, char* args[])
{
   // Inicjujemy SDL
  if(SDL_Init(SDL_INIT_VIDEO))
  {
    cout << "SDL_Init Error: " << SDL_GetError() << endl;
    return 1;
  }

  // Tworzymy okno
  SDL_Window * w = SDL_CreateWindow("Bresenham", SDL_WINDOWPOS_CENTERED, SDL_WINDOWPOS_CENTERED, W_W, W_H, 0);
  if(!w)
  {
    cout << "SDL_CreateWindow Error: " << SDL_GetError() << endl;
    SDL_Quit();
    return 2;
  }

  // Tworzymy kontekst graficzny
  SDL_Renderer * r = SDL_CreateRenderer(w,0,SDL_RENDERER_PRESENTVSYNC);
  if(!r)
  {
     cout << "SDL_CreateRenderer Error: " << SDL_GetError() << endl;
     SDL_DestroyWindow(w);
     SDL_Quit();
     return 3;
  }

  srand(time(NULL));

  int x1,y1,x2,y2,dx1,dy1,dx2,dy2,cr,cg,cb,dr,dg,db;

  unsigned p = 0xf090f090; // xxxx....x..x....xxxx....x..x....

  x1 = rand() % W_W;
  x2 = rand() % W_W;
  y1 = rand() % W_H;
  y2 = rand() % W_H;

  do dx1 = -3 + rand() % 7; while(!dx1);
  do dx2 = -3 + rand() % 7; while(!dx2);
  do dy1 = -3 + rand() % 7; while(!dy1);
  do dy2 = -3 + rand() % 7; while(!dy2);

  cr = 128 + rand() % 128;
  cg = 128 + rand() % 128;
  cb = 128 + rand() % 128;

  do dr = -3 + rand() % 7; while(!dr);
  do dg = -3 + rand() % 7; while(!dg);
  do db = -3 + rand() % 7; while(!db);

  // Animacja
  SDL_Event event;
  while(1)
  {
    // Usuwamy treść poprzedniego okna
    SDL_SetRenderDrawColor(r,0,0,0,255);
    SDL_RenderClear(r);

    // Rysujemy linię
    SDL_SetRenderDrawColor(r,cr,cg,cb,255);
    SDL_RenderBresenhamLine(r,x1,y1,x2,y2,p);

    // Modyfikujemy współrzędne i kolory
    if((x1 + dx1 < 0) || (x1 + dx1 >= W_W)) dx1 = -dx1;
    if((y1 + dy1 < 0) || (y1 + dy1 >= W_H)) dy1 = -dy1;
    if((x2 + dx2 < 0) || (x2 + dx2 >= W_W)) dx2 = -dx2;
    if((y2 + dy2 < 0) || (y2 + dy2 >= W_H)) dy2 = -dy2;
    x1 += dx1;
    y1 += dy1;
    x2 += dx2;
    y2 += dy2;
    if((cr + dr < 128) || (cr + dr > 255)) dr = - dr;
    if((cg + dg < 128) || (cg + dg > 255)) dg = - dg;
    if((cb + db < 128) || (cb + db > 255)) db = - db;
    cr += dr;
    cg += dg;
    cb += db;

    // Uaktualniamy treść okna na ekranie
    SDL_RenderPresent(r);

    // Sprawdzamy, czy użytkownik zamyka program
    if(SDL_PollEvent(&event) && event.type == SDL_QUIT) break;
  }

  // Usuwamy kontekst graficzny
  SDL_DestroyRenderer(r);

  // Usuwamy okno
  SDL_DestroyWindow(w);

  // Kończymy pracę z SDL2
  SDL_Quit();

  return 0;
}

Na początek: podrozdziału strony

Wykorzystujemy tutaj tę samą zasadę, co w poprzednim programie. Funkcja rysująca linię otrzymuje bitowy wzorzec oraz dwa zestawy kolorów. Wzorzec jest kolejno skanowany i dla bitu 0 rysowany jest piksel w jednym kolorze, a dla bitu 1 w drugim:

C++

// Algorytm Bresenhama 4
//----------------------

#include <SDL.h>
#include <iostream>
#include <cstdlib>
#include <ctime>

using namespace std;

// Rozmiar okienka
const int W_W = 640;
const int W_H = 480;

// Funkcja rysuje odcinek algorytmem Bresenhama
//---------------------------------------------
void SDL_RenderBresenhamLine(SDL_Renderer * r, int x1, int y1, int x2, int y2, unsigned p,
                             int r1, int g1, int b1, int r2, int g2, int b2)
{
  int dx,dy,kx,ky,e,i;
  unsigned mask = 0;

  // Przyrosty w osiach x i y
  if(x1 <= x2) kx = 1; else kx = -1;
  if(y1 <= y2) ky = 1; else ky = -1;

  // Odległości pomiędzy punkatami startowym a końcowym wzdłuż osi
  dx = x2 - x1; if(dx < 0) dx = -dx;
  dy = y2 - y1; if(dy < 0) dy = -dy;

  // Rysujemy punkt startowy
  mask >>= 1; if(!mask) mask = 0x80000000;
  if(p & mask) SDL_SetRenderDrawColor(r,r2,g2,b2,255);
  else         SDL_SetRenderDrawColor(r,r1,g1,b1,255);
  SDL_RenderDrawPoint(r,x1,y1);

  // Wybieramy wersję algorytmu Bresenhama
  if(dx >= dy)
  {
    // Wersja podstawowa

    e = dx / 2;   // Wyrażenie błędu

    for(i = 0; i < dx; i++)
    {
      x1 += kx;   // Ruch w kierunku szybkim
      e -= dy;    // Nowe wyrażenie błędu
      if(e < 0)
      {
        y1 += ky; // Ruch w kierunku wolnym
        e += dx;
      }

      // Rysujemy kolejny piksel
      mask >>= 1; if(!mask) mask = 0x80000000;
      if(p & mask) SDL_SetRenderDrawColor(r,r2,g2,b2,255);
      else         SDL_SetRenderDrawColor(r,r1,g1,b1,255);
      SDL_RenderDrawPoint(r,x1,y1);
    }
  }
  else
  {
    // Wersja z zamienionymi współrzędnymi

    e = dy / 2;   // Wyrażenie błędu

    for(i = 0; i < dy; i++)
    {
      y1 += ky;   // Ruch w kierunku szybkim
      e -= dx;    // Nowe wyrażenie błędu
      if(e < 0)
      {
        x1 += kx; // Ruch w kierunku wolnym
        e += dy;
      }

      // Rysujemy kolejny piksel
      mask >>= 1; if(!mask) mask = 0x80000000;
      if(p & mask) SDL_SetRenderDrawColor(r,r2,g2,b2,255);
      else         SDL_SetRenderDrawColor(r,r1,g1,b1,255);
      SDL_RenderDrawPoint(r,x1,y1);

    }
  }
}

int main(int argc, char* args[])
{
   // Inicjujemy SDL
  if(SDL_Init(SDL_INIT_VIDEO))
  {
    cout << "SDL_Init Error: " << SDL_GetError() << endl;
    return 1;
  }

  // Tworzymy okno
  SDL_Window * w = SDL_CreateWindow("Bresenham", SDL_WINDOWPOS_CENTERED, SDL_WINDOWPOS_CENTERED, W_W, W_H, 0);
  if(!w)
  {
    cout << "SDL_CreateWindow Error: " << SDL_GetError() << endl;
    SDL_Quit();
    return 2;
  }

  // Tworzymy kontekst graficzny
  SDL_Renderer * r = SDL_CreateRenderer(w,0,SDL_RENDERER_PRESENTVSYNC);
  if(!r)
  {
     cout << "SDL_CreateRenderer Error: " << SDL_GetError() << endl;
     SDL_DestroyWindow(w);
     SDL_Quit();
     return 3;
  }

  srand(time(NULL));

  int x1,y1,x2,y2,dx1,dy1,dx2,dy2;
  int cr1,cg1,cb1,dr1,dg1,db1;
  int cr2,cg2,cb2,dr2,dg2,db2;

  unsigned p = 0xffff0000; // xxxxxxxxxxxxxxxx................

  x1 = rand() % W_W;
  x2 = rand() % W_W;
  y1 = rand() % W_H;
  y2 = rand() % W_H;

  do dx1 = -3 + rand() % 7; while(!dx1);
  do dx2 = -3 + rand() % 7; while(!dx2);
  do dy1 = -3 + rand() % 7; while(!dy1);
  do dy2 = -3 + rand() % 7; while(!dy2);

  cr1 = 128 + rand() % 128;
  cg1 = 128 + rand() % 128;
  cb1 = 128 + rand() % 128;

  do dr1 = -3 + rand() % 7; while(!dr1);
  do dg1 = -3 + rand() % 7; while(!dg1);
  do db1 = -3 + rand() % 7; while(!db1);

  cr2 = rand() % 128;
  cg2 = rand() % 128;
  cb2 = rand() % 128;

  do dr2 = -3 + rand() % 7; while(!dr2);
  do dg2 = -3 + rand() % 7; while(!dg2);
  do db2 = -3 + rand() % 7; while(!db2);

  // Animacja
  SDL_Event event;
  while(1)
  {
    // Usuwamy treść poprzedniego okna
    SDL_SetRenderDrawColor(r,0,0,0,255);
    SDL_RenderClear(r);

    // Rysujemy linię
    SDL_RenderBresenhamLine(r,x1,y1,x2,y2,p,cr1,cg1,cb1,cr2,cg2,cb2);

    // Modyfikujemy współrzędne i kolory
    if((x1 + dx1 < 0) || (x1 + dx1 >= W_W)) dx1 = -dx1;
    if((y1 + dy1 < 0) || (y1 + dy1 >= W_H)) dy1 = -dy1;
    if((x2 + dx2 < 0) || (x2 + dx2 >= W_W)) dx2 = -dx2;
    if((y2 + dy2 < 0) || (y2 + dy2 >= W_H)) dy2 = -dy2;
    x1 += dx1;
    y1 += dy1;
    x2 += dx2;
    y2 += dy2;
    if((cr1 + dr1 < 128) || (cr1 + dr1 > 255)) dr1 = - dr1;
    if((cg1 + dg1 < 128) || (cg1 + dg1 > 255)) dg1 = - dg1;
    if((cb1 + db1 < 128) || (cb1 + db1 > 255)) db1 = - db1;
    cr1 += dr1;
    cg1 += dg1;
    cb1 += db1;
    if((cr2 + dr2 < 0) || (cr2 + dr2 > 127)) dr2 = - dr2;
    if((cg2 + dg2 < 0) || (cg2 + dg2 > 127)) dg2 = - dg2;
    if((cb2 + db2 < 0) || (cb2 + db2 > 127)) db2 = - db2;
    cr2 += dr2;
    cg2 += dg2;
    cb2 += db2;

    // Uaktualniamy treść okna na ekranie
    SDL_RenderPresent(r);

    // Sprawdzamy, czy użytkownik zamyka program
    if(SDL_PollEvent(&event) && event.type == SDL_QUIT) break;
  }

  // Usuwamy kontekst graficzny
  SDL_DestroyRenderer(r);

  // Usuwamy okno
  SDL_DestroyWindow(w);

  // Kończymy pracę z SDL2
  SDL_Quit();

  return 0;
}

Na początek: podrozdziału strony

Przypomnijmy, gradient jest płynnym przejściem koloru jednego w drugi. W przypadku linii rozpoczynamy rysowanie kolorem startowym, który płynnie zmienia się wewnątrz linii w kolor końcowy. W algorytmie Bresenhama zawsze wiemy, z ilu punktów składa się rysowany odcinek. Zadanie zatem sprowadza się do zmiany kolorów składowych koloru startowego w kolory składowe koloru końcowego wzdłuż rysowanych punktów. Ponumerujmy punkty odcinka od 0 do n-1. W punkcie o numerze 0 mamy kolor startowy. W punkcie o numerze n-1 mamy kolor końcowy. Punkty o numerach pośrednich muszą przyjmować kolory pośrednie pomiędzy kolorem startowym a końcowym:

Kolor		kolory pośrednie
Punkt	0	1	2	3	...	...	...	...	...	n-3	n-2	n-1

Problem ten sprowadza się do zmiany składowych kolorów wraz z numerem piksela. W punkcie o numerze 0 mamy składową startową ss. W punkcie o numerze n - 1 powinniśmy otrzymać składową końcową sk. Odpowiedni wzór wyprowadziliśmy w rozdziale poświęconym liniom. Skorzystamy z niego:

s	–	wynikowa składowa koloru
ss	–	składowa koloru piksela startowego
sk	–	składowa koloru piksela końcowego
i	–	numer rysowanego piksela
n	–	liczba pikseli do narysowania

Wzór ten należy zastosować dla każdej składowej koloru piksela. W programie został on nieco zmodyfikowany, aby dostosować go do algorytmu Bresenhama.

C++

// Algorytm Bresenhama 5
//----------------------

#include <SDL.h>
#include <iostream>
#include <cstdlib>
#include <ctime>

using namespace std;

// Rozmiar okienka
const int W_W = 640;
const int W_H = 480;

// Funkcja rysuje odcinek algorytmem Bresenhama
//---------------------------------------------
void SDL_RenderBresenhamLine(SDL_Renderer * r, int x1, int y1, int x2, int y2,
                             int r1, int g1, int b1, int r2, int g2, int b2)
{
  int dx,dy,kx,ky,e,i,cr,cg,cb;

  // Przyrosty w osiach x i y
  if(x1 <= x2) kx = 1; else kx = -1;
  if(y1 <= y2) ky = 1; else ky = -1;

  // Odległości pomiędzy punkatami startowym a końcowym wzdłuż osi
  dx = x2 - x1; if(dx < 0) dx = -dx;
  dy = y2 - y1; if(dy < 0) dy = -dy;

  // Rysujemy punkt startowy
  SDL_SetRenderDrawColor(r,r1,g1,b1,255);

  // Wybieramy wersję algorytmu Bresenhama
  if(dx >= dy)
  {
    // Wersja podstawowa

    e = dx / 2;   // Wyrażenie błędu

    for(i = 1; i <= dx; i++)
    {
      x1 += kx;   // Ruch w kierunku szybkim
      e -= dy;    // Nowe wyrażenie błędu
      if(e < 0)
      {
        y1 += ky; // Ruch w kierunku wolnym
        e += dx;
      }

      // Wyliczamy składowe koloru piksela
      cr = r1 + i * (r2 - r1) / dx;
      cg = g1 + i * (g2 - g1) / dx;
      cb = b1 + i * (b2 - b1) / dx;

      // Ustawiamy kolor piksela
      SDL_SetRenderDrawColor(r,cr,cg,cb,255);

      // Rysujemy kolejny piksel
      SDL_RenderDrawPoint(r,x1,y1);
    }
  }
  else
  {
    // Wersja z zamienionymi współrzędnymi

    e = dy / 2;   // Wyrażenie błędu

    for(i = 1; i <= dy; i++)
    {
      y1 += ky;   // Ruch w kierunku szybkim
      e -= dx;    // Nowe wyrażenie błędu
      if(e < 0)
      {
        x1 += kx; // Ruch w kierunku wolnym
        e += dy;
      }

      // Wyliczamy składowe koloru piksela
      cr = r1 + i * (r2 - r1) / dy;
      cg = g1 + i * (g2 - g1) / dy;
      cb = b1 + i * (b2 - b1) / dy;

      // Ustawiamy kolor piksela
      SDL_SetRenderDrawColor(r,cr,cg,cb,255);

      // Rysujemy kolejny piksel
      SDL_RenderDrawPoint(r,x1,y1);
    }
  }
}

C++

int main(int argc, char* args[])
{
   // Inicjujemy SDL
  if(SDL_Init(SDL_INIT_VIDEO))
  {
    cout << "SDL_Init Error: " << SDL_GetError() << endl;
    return 1;
  }

  // Tworzymy okno
  SDL_Window * w = SDL_CreateWindow("Bresenham", SDL_WINDOWPOS_CENTERED, SDL_WINDOWPOS_CENTERED, W_W, W_H, 0);
  if(!w)
  {
    cout << "SDL_CreateWindow Error: " << SDL_GetError() << endl;
    SDL_Quit();
    return 2;
  }

  // Tworzymy kontekst graficzny
  SDL_Renderer * r = SDL_CreateRenderer(w,0,SDL_RENDERER_PRESENTVSYNC);
  if(!r)
  {
     cout << "SDL_CreateRenderer Error: " << SDL_GetError() << endl;
     SDL_DestroyWindow(w);
     SDL_Quit();
     return 3;
  }

  srand(time(NULL));

  int x1,y1,x2,y2,dx1,dy1,dx2,dy2;
  int cr1,cg1,cb1,dr1,dg1,db1;
  int cr2,cg2,cb2,dr2,dg2,db2;

  x1 = rand() % W_W;
  x2 = rand() % W_W;
  y1 = rand() % W_H;
  y2 = rand() % W_H;

  do dx1 = -3 + rand() % 7; while(!dx1);
  do dx2 = -3 + rand() % 7; while(!dx2);
  do dy1 = -3 + rand() % 7; while(!dy1);
  do dy2 = -3 + rand() % 7; while(!dy2);

  cr1 = 128 + rand() % 128;
  cg1 = 128 + rand() % 128;
  cb1 = 128 + rand() % 128;

  do dr1 = -3 + rand() % 7; while(!dr1);
  do dg1 = -3 + rand() % 7; while(!dg1);
  do db1 = -3 + rand() % 7; while(!db1);

  cr2 = rand() % 128;
  cg2 = rand() % 128;
  cb2 = rand() % 128;

  do dr2 = -3 + rand() % 7; while(!dr2);
  do dg2 = -3 + rand() % 7; while(!dg2);
  do db2 = -3 + rand() % 7; while(!db2);

  // Animacja
  SDL_Event event;
  while(1)
  {
    // Usuwamy treść poprzedniego okna
    SDL_SetRenderDrawColor(r,0,0,0,255);
    SDL_RenderClear(r);

    // Rysujemy linię
    SDL_RenderBresenhamLine(r,x1,y1,x2,y2,cr1,cg1,cb1,cr2,cg2,cb2);

    // Modyfikujemy współrzędne i kolory
    if((x1 + dx1 < 0) || (x1 + dx1 >= W_W)) dx1 = -dx1;
    if((y1 + dy1 < 0) || (y1 + dy1 >= W_H)) dy1 = -dy1;
    if((x2 + dx2 < 0) || (x2 + dx2 >= W_W)) dx2 = -dx2;
    if((y2 + dy2 < 0) || (y2 + dy2 >= W_H)) dy2 = -dy2;
    x1 += dx1;
    y1 += dy1;
    x2 += dx2;
    y2 += dy2;
    if((cr1 + dr1 < 128) || (cr1 + dr1 > 255)) dr1 = - dr1;
    if((cg1 + dg1 < 128) || (cg1 + dg1 > 255)) dg1 = - dg1;
    if((cb1 + db1 < 128) || (cb1 + db1 > 255)) db1 = - db1;
    cr1 += dr1;
    cg1 += dg1;
    cb1 += db1;
    if((cr2 + dr2 < 0) || (cr2 + dr2 > 127)) dr2 = - dr2;
    if((cg2 + dg2 < 0) || (cg2 + dg2 > 127)) dg2 = - dg2;
    if((cb2 + db2 < 0) || (cb2 + db2 > 127)) db2 = - db2;
    cr2 += dr2;
    cg2 += dg2;
    cb2 += db2;

    // Uaktualniamy treść okna na ekranie
    SDL_RenderPresent(r);

    // Sprawdzamy, czy użytkownik zamyka program
    if(SDL_PollEvent(&event) && event.type == SDL_QUIT) break;
  }

  // Usuwamy kontekst graficzny
  SDL_DestroyRenderer(r);

  // Usuwamy okno
  SDL_DestroyWindow(w);

  // Kończymy pracę z SDL2
  SDL_Quit();

  return 0;
}

Poeksperymentuj z podanymi tutaj programami: ciekawe efekty powstają, jeśli usunie się w nich wymazywanie treści poprzedniego okna.

Na początek: podrozdziału strony

Materiały tylko do użytku dydaktycznego. Ich kopiowanie i powielanie jest dozwolone
pod warunkiem podania źródła oraz niepobierania za to pieniędzy.

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

Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.

Informacje dodatkowe.

Algorytm Bresenhama

Rysowanie odcinka

Wejście

Wyjście

Zmienne pomocnicze

Lista kroków

Wejście

Wyjście

Dane pomocnicze

Lista kroków

Linie przerywane

Linie dwukolorowe

Linie gradientowe