Bresenhamov kružnicový algoritmus (Bresenham's Circle Algorithm)

Princíp algoritmu

Tento algoritmus predstavuje zovšeobecnenie Bresenhamovho algoritmu rasterizácie úsečky na kružnicu. Rozklad zrýchlime tým, že budeme generovať len segment kružnice v jednom oktante. Ostatné časti kružnice dostaneme súmernosťou podľa súradnicových osí $x$, $y$ a priamok $x=y$ a $y=-x$.

Výber pixlov je založený na rovnakom princípe ako pri úsečke, kde z dvoch možných kandidátov na vysvietenie vyberáme toho, ktorého stred je bližšie ku danej kružnici. Využívame parameter $p_i=d_1-d_2$, ktorý sa vyčísľuje rekurentne, kde hodnoty $d_1$ a $d_2$ sú štvorcami rozdielov $y$-ových súradníc.

Pre ilustráciu algoritmu volíme kružnicu so stredom v začiatku súradnicovej sústavy a zobrazíme jej segment, ktorý sa začína v bode $(0,r)$ a končí, v bode $(x_i,y_i)$, kde $x_i \geq y_i$ (Obr. 1). V tomto prípade je jednotkový krok v smere súradnicovej osi $x$. Nachádzame sa v bode $(x_i,y_i)$ a potrebujeme sa rozhodnúť, ktorý z pixlov $E=(x_i+1,y_i)$ alebo $SE=(x_i+1,y_i-1)$ si vyberieme (Obr. 2).

Obr. 1 - Generovaný segment kružnice
Obr. 2 - Bresenhamov algoritmus generovania kružnice

Označíme si $d_1={y_i^2}-y^2$ a $d_2=y^2-(y_i-1)^2$, kde $y$ je hodnota určená rovnicou $y^2=r^2-(x_i+1)^2$ z implicitnej rovnice kruznice. Hodnota $d_1$ vyjadruje vzdialenosť medzi bodmi $E$ a $(x_i+1,y)$ a hodnota $d_2$ medzi $(x_i+1,y)$ a $SE$. Určíme $p_i=d_1-d_2=2(x_i+1)^2+y_i^2+(y_i-1)^2-2r^2$. Zrejme platí

  • Ak $p_i \lt 0 \Leftrightarrow d_1 \lt d_2$, tak bod $E$ je bližšie k bodu na kružnici $(x_i+1,y_i)$ a preto vysvietime pixel $E$.
  • Ak $p_i \geq 0 \Leftrightarrow d_1\geq d_2$, tak je bližšie bod $SE$, ktorý následne vysvietime. Pri rovnosti môžeme vybrať ľubovoľný z bodov $E$, $SE$, no zvyčajne sa vyberá vyššie položený bod.

Teraz vyjadríme parameter $p_{i}$ rekurentne pomocou $p_{i+1}$

$p_{i+1}=2(x_{i+1}+1)^2+y_{i+1}^2+(y_{i+1}-1)^2-2r^2$ a rozdielu $p_{i+1}-p_i=4x_i+6+2(y_{i+1}^2-y_i^2)-2(y_{i+1}-y_i)$.

Možno zapísať rekurentný vzťah $p_{i+1}=p_i+4x_i+6+2(y_{i+1}^2-y_i^2)-2(y_{i+1}-y_i)$ Teda:

  • Ak $p_i \lt 0 \Leftrightarrow d_1 \lt d_2$, nasledujúci bod je $(x_{i+1},y_{i+1})=E=(x_i+1,y_i)$ a $p_{i+1}=p_i+4x_i+6$
  • Ak $p_i \geq 0 \Leftrightarrow d_1\geq d_2$, nasledujúci bod je $(x_{i+1},y_{i+1})=SE=(x_i+1,y_i-1)$, a preto $p_{i+1}=p_i+4x_i+6+2(y_i-y_i^2)$

Potom pre začiatočnú hodnotu $p_0$ v bode $(x_C,y_C)=(0,r)$ dostaneme $p_0=3-2r$. Hoci pri výpočte parametra sa používa násobenie, príslušný násobok je druhou mocninou a je možná implementácia cez logické operácie. Ostatné operácie sú celočíselné sčítanie a odčítanie.

Postup výpočtu

Kroky algoritmu vieme zhrnúť nasledovne:

  1. Zadaj polomer $r$ a stred kružnice $(x_C,y_C)$ a urči prvý bod na kružnici so stredom v začiatku ako $(x_0 ,y_0)=(0, r)$.
  2. Vypočítaj začiatočnú hodnotu rozhodovacieho parametra ako $p_0 =3-2r$
  3. V každej pozícii $x_i$, štartujúc v $i=0$, vykonaj nasledujúci test:
    1. Ak $p_i \lt 0$: nasledujúci bod pozdĺž kružnice so stredom $(0,0)$ bude $(x_{i+1}, y_{i+1})=(x_i+1,y_i)$ a $p_{i+1}=p_i+4x_i+6$.
    2. Inak je nasledujúci bod $(x_{i+1}, y_{i+1})=(x_i+1,y_i-1)$ a $p_{i+1}=p_i+4(x_i-y_i)+10$.
  4. Urči súmerne položené body v ostatných siedmich oktantoch.
  5. Posuň každú vypočítanú pixlovú pozíciu $(x, y)$ na kružnicu so stredom $(x_C ,y_C )$ a zobraz bod so súradnicami: $x=x+x_C$,$y=y+y_C$.
  6. Opakuj kroky 3. až 5. pokiaľ $x_i \geq y_i$.

Príklad

Na ilustráciu algoritmu si ukážeme rasterizáciu kružnice s polomerom $r=8$ a stredom kružnice $(x_C, y_C)=(1, 2)$.

  1. $(x_0,y_0)=(0,r)=(0,8)$
  2. $p_0=3-2r=-13$
    • $i=0:~p_0 \lt 0 \Rightarrow (x_1,y_1)=(x_0+1,y_0)=(1,8)$ a $p_1=p_0+4x_0+6=-7$
    • $i=1:~p_1 \lt 0 \Rightarrow (x_2,y_2)=(x_1+1,y_1)=(2,8)$ a $p_2=p_1+4x_1+6=3$
    • $i=2:~p_2 \gt 0 \Rightarrow (x_3,y_3)=(x_2+1,y_2-1)=(3,7)$ a $p_3=p_2+4(x_2-y_2)+10=-11$
    • $i=3:~p_3 \lt 0 \Rightarrow (x_4,y_4)=(x_3+1,y_3)=(4,7)$ a $p_4=p_3+4x_3+6=7$
    • $i=4:~p_4 \gt 0 \Rightarrow (x_5,y_5)=(x_4+1,y_4-1)=(5,6)$ a $p_5=p_4+4(x_4-y_4)+10=5$
    • $i=5:~p_5 \gt 0 \Rightarrow (x_6,y_6)=(x_5+1,y_5-1)=(6,5)$ a $x_6\geq y_6$ teda algoritmus končí.
  3. Určíme súmerne položené body v ostatných oktantoch (Obr. 3).
  4. Posunieme každú hodnotu pixla do stredu $(1,2)$. Teda body: $(2,10),(3,10),(4,9),(5,9),(6,8), ...$
Obr. 3 - Výsledná kružnica so stredom v bode $(0,0)$

Ďalšie riešené a neriešené príklady.

Interaktívny applet

Bressenhamov algoritmus pre rasterizáciu kružnice

Zobrazený raster sa nachádza v prvom kvadrante, teda v ľavom dolnom rohu sa nachádza bod (0,0).

Urči polomer a kliknutím do rastra vlož stred kružnice.


Polomer kružnice
Vykresli kružnicu

Automaticky
Ukazuj kroky algoritmu
Interval 1sek
Nepodporovany prehliadac.

circleBress(int xC, int yC, int r){
  int x = 0, y = r;
  int p = 3 - (2 * r);
  void vykresliBodKruznice(int, int, int, int);

  vykresliBodKruznice(xC, yC, x, y);
  while(x < y) {
    if(p < 0) p = p + (4 * x) + 6;
    else {
      y--;
      p = p + 4 * (x - y) + 10;
      }
    x++;
    vykresliBodKruznice(xC, yC, x, y);
  }
}

void vykresliBodKruznice(int xC, int yC, int x, int y){
  vykresliPixel(xC + x, yC + y);
  vykresliPixel(xC - x, yC + y);
  vykresliPixel(xC + x, yC - y);
  vykresliPixel(xC - x, yC - y);
  vykresliPixel(xC + y, yC + x);
  vykresliPixel(xC - y, yC + x);
  vykresliPixel(xC + y, yC - x);
  vykresliPixel(xC - y, yC - x);
}

Pseudokód

Implementácia Bresenhamovho kružnicového algoritmu je zhrnutá v nasledujúcom pseudokóde. Na vstupe je stred $(x_C,y_C)$ a polomer kružnice $r$.

circleBres(int $x_C$, int $y_C$, int r) $\lbrace$

  int x = 0, y = r, p = 3 - (2 * r);

  void vykresliBodKruznice(int, int, int, int);

  /* Vykreslí prvý bod kružnice

  vykresliBodKruznice($x_C$, $y_C$, x, y);

  while(x < y) $\lbrace$

    x++;

    if(p < 0) p = p + (4 * x) + 6;

    else $\lbrace$

      y$--$;

      p = p + 4 * (x - y) + 10; $\rbrace$

    vykresliBodKruznice($x_C$, $y_C$, x, y);

  $\rbrace$

$\rbrace$


void vykresliBodKruznice(int $x_C$, int $y_C$, int x, int y); $\lbrace$

  vykresliPixel($x_C$ + x, $y_C$ + y);

  vykresliPixel($x_C$ - x, $y_C$ + y);

  vykresliPixel($x_C$ + x, $y_C$ - y);

  vykresliPixel($x_C$ - x, $y_C$ - y);

  vykresliPixel($x_C$ + y, $y_C$ + x);

  vykresliPixel($x_C$ - y, $y_C$ + x);

  vykresliPixel($x_C$ + y, $y_C$ - x);

  vykresliPixel($x_C$ - y, $y_C$ - x);

$\rbrace$

Literatúra

Bresenhamov kružnicový algoritmus sa nachádza podrobne spracovaný v literatúre [3]. Jeho myšlienka je načrtnutá aj v [1] na strane 62 a taktiež jeho vysvetlenie sa nachádza v [2] od strany 88.