Rasterizace úsečky

Algoritmy Grafické Rasterizace úsečky

Rasterizace úsečky patří k úplným základům počítačové grafiky, ať už jde o vykreslování dvourozměrných tvarů nebo 3D mnohoúhelníků. Tento článek má za úkol osvětlit nejčastější způsoby implementace této operace.

Úsečku v paměti typicky reprezentujeme dvěma koncovými body se souřadnicemi x a y. Při převodu na rastrovou reprezentaci potřebujeme spojit tyto dva body nepřerušovaně a nejkratší cestou. Jak to uděláme? Způsobů je hned několik, avšak všechny zpravidla počítají s tím, že úhel úsečky s osou x je mezi 0 a 45 stupni. Pokud má úsečka jakýkoli jiný sklon, jednoduše daný případ převedeme na ten, kterým se zabýváme. Na následujícím obrázku vidíme všechny možné případy poloh úsečky a informaci o tom, jak transformovat souřadnice, abychom je převedli na náš uvažovaný případ.

transformace úsečky

Transformace úsečky

Jak souřadnice převedeme, je na nás. Nejdřív musíme zjistit polohu úsečky, např. vypočítáním úhlu, porovnáváním velikostí hodnot dx a dy (rozdílů souřadnic bodů v obou osách) nebo podobným způsobem, který můžeme vhodně zapsat jako funkci. Dále si můžeme napsat další, transformační funkci, které sdělíme zjištěnou polohu úsečky, a ona nám souřadnice převede buď tam anebo zpět. Této funkci předáme souřadnice vždycky před tím, než s nimi začneme pracovat, a stejně tak zpracované souřadnice vždycky převedeme před vykreslením zpět. Transformační funkce může vypadat např. takto:

void transformuj(int x, int y, int *nove_x, int *nove_y, int poloha, int smer_prevodu)

  {
    if (smer_prevodu == SMER_TAM)                          // prevod tam
      {
        switch (poloha)
         {
           case 0: *x_nove = x; *y_nove = y; break;        // 0 - 45 stupnu
           case 1: *x_nove = y; *y_nove = x; break;        // 46 - 90 stupnu
           case 2: *x_nove = y; *y_nove = -1 * x; break;   // 91 - 135 stupnu
           //...
         }
      }
    else                                                   // prevod zpet
      {
        switch (poloha)
         {
           case 0: *x_nove = x; *y_nove = y; break;        // 0 - 45 stupnu
           case 1: *x_nove = y; *y_nove = x; break;        // 46 - 90 stupnu
           case 2: *x_nove = -1 * y; *y_nove = * x; break; // 91 - 135 stupnu
           //...
         }
        //...
      }
  }

To je vše, co potřebujeme na úvod vědět a nyní se pojďme podívat na to, co je pro tento článek hlavním tématem - konkrétní algoritmy rasterizace.

DDA algoritmus

Název algoritmu znamená digital diferential analyser. Jde o jednoduchý algoritmus, který by asi vymyslel každý z nás. Byl jednou z prvních implementací, která se objevila a jak to tak bývá, nejjednodušší řešení nepatří k nejefektivnějším. Avšak pokud není rychlost kritickým aspektem naší aplikace, lze jej použít.

Principem algoritmu je pohyb po ose x od prvního bodu k druhému po jednom pixelu, přičemž v každém kroku počítáme hodnotu y přičítáním směrnice úsečky (ta je samozřejmě tangens sklonu úsečky, neboli poměr dy/dx). Tuto hodnotu zaokrouhlujeme a vykreslujeme pixely. Kód algoritmu může vypadat např. takto:

int x, dx, dy;
double y = y1;
dx = x2 - x1;
dy = y2 - y1;
double smernice = dy / (double) dx;

for (x = x1; x <= x2; x++)
  {
    vykresli_bod(x,(int) y);
    y = y1 + smernice;
  }

Připomeňme, že v reálném kódu bychom souřadnice nejspíš obalili transformační funkcí, což by zde ale působilo nepřehlednost.

Error control DDA

Jde o variantu předchozího algoritmu. Princip je podobný s tím rozdílem, že v každém kroku vypočítáváme chybu, které se dopouštíme zaokrouhlováním. Pokud chyba přesáhne hodnotu 0,5 pixelu, posuneme se o řádek výš a od chyby odečteme 1, aby zůstala relativní k danému řádku.

int x, y, dx, dy;
dx = x2 - x1;
dy = y2 - y1;
double smernice = dy / (double) dx;
double chyba = 0;

y = y1;

for (x = x1; x <= x2; x++)
  {
    vykresli_bod(x,(int) y);
    chyba += smernice;

    if (chyba => 0.5)
      {
        y++;             // posun na dalsi radek
        chyba -= 1.0;    // aby chyba zustala relativni k radku
      }
  }

Platí zde to samé, co pro předchozí algoritmus - není příliš efektivní, protože používá výpočty v plovoucí řádové čárce.

Bresenhamův algoritmus

Předchozí algoritmy měly jednu chybu - potřebovaly počítat v plovoucí řádové čárce. Ač nám to nemusí připadat jako nevýhoda, je faktem, že floating point operace jsou mnohem náročnější než celočíselná aritmetika. Pokud má grafická karta vykreslovat stokrát za sekundu složitý 3D drátěný model, jistě to potřebuje dělat efektivně, nemluvě o tom, že jednodušší hardware nemusí floating point operace vůbec podporovat. Tento problém řeší právě Bresenhamův algoritmus, který se dnes používá nejčastěji.

Prvním krokem je zavedení tzv. prediktoru:

p0 = 2 * dy - dx

Dále opět postupujeme v ose x po jednotlivých pixelech a podle prediktoru se rozhodujeme, co dělat dál:

  • pokud je prediktor větší nebo roven 0: pi + 1 = pi + 2dy - 2dx, a posun o řádek výš
  • v opačném případě: pi + 1 = pi + 2dy

Kód tedy může vypadat takto:

int x, y, dx, dy, p;

dx = x2 - x1;
dy = y2 - y1;
y = y1;
p = 2 * dy - dx;         // prediktor

for (x = x1; x <= x2; x++)
  {
    vykresli_bod(x,(int) y);

    if (p => 0)
      {
        y++;             // presun na dalsi radek
        p = p + 2 * dy - 2 * dx;
      }
    else
      {
        p = p + 2 * dy;
      }
  }

Hodnoty 2 * dy a 2 * dx můžeme pro lepší optimalizaci předpočítat a uložit do zvláštních proměnných, čemuž jsem se zde opět pro účel přehlednosti dovolil vyhnout.

Pokud vás zajímá odvození rovnic pro prediktor, vězte, že jde o jednoduchou úpravu rovnic algoritmu Error control DDA. U něj platí:

error[i] + dy/dx:
  <  0,5   error[i + 1] := error[i] + dy/dx
  >= 0,5   error[i + 1] := error[i] + dy/dx - 1, y++

Vynásobením nerovnic hodnotou 2dx a převedením jednoho členu na levou stranu dostaneme:

2 * dx * error[i] + 2 * dy - dx:
  <  0   error[i + 1] := error[i] + 2 * dy
  >= 0   error[i + 1] := error[i] + 2 * dy - 2 * dx, y++

Pole error přejmenujeme na prediktor a jsme hotovi.

Závěrem

Vidíme, že nejlepší volbou je pro nás Bresenhamův algoritmus, protože využívá pouze celočíselnou aritmetiku a obejde se dokonce bez dělení. Pokud ale nenavrhujeme hardwarovou desku, která musí být co nejvíce optimalizovaná, tak se obejdeme i s ostatními metodami. Tak jako tak je vždy dobré znát alespoň tyto základní algoritmy.


 

  Aktivity (1)

Článek pro vás napsal tastyfish
Avatar
Autor studuje informatiku na FIT VUT v Brně, věnuje se tvorbě svých stránek a vlastního softwaru. Má rád logické hádanky a odpočívá při sportu a hudbě.

Jak se ti líbí článek?
Celkem (3 hlasů) :
55555


 


Miniatura
Předchozí článek
IFS fraktály
Miniatura
Všechny články v sekci
Grafické algoritmy
Miniatura
Následující článek
Plechovka čili Floodfill

 

 

Komentáře

Avatar
Pekky
Člen
Avatar
Pekky:

Zdravim,

chtel bych se zeptat k Bresenhamove algoritmu, proc je prediktor na radku #6 nastaven na hodnotu "2dy-dx"? S tim take souvisi druhy dotaz - podle ceho se pak nastavuje jeho hodnota uvnitr cyklu?

EDIT: Jeste me napadla druha vec - jak se zde resi, zda usecka ma sklon vetsi ci mensi nez 45 stupnu?

Dekuji

Editováno 25.5.2014 13:28
 
Odpovědět 25.5.2014 13:27
Avatar
Odpovídá na Pekky
Libor Šimo (libcosenior):

:o
Sorry, ale prekvapil si ma maximálne.

Editováno 25.5.2014 13:31
Odpovědět 25.5.2014 13:30
Aj tisícmíľová cesta musí začať jednoduchým krokom.
Avatar
tastyfish
Redaktor
Avatar
Odpovídá na Pekky
tastyfish:

Rovnice pro prediktor jsou odvozeny z rovnic DDA algoritmu vynásobením hodnotou 2dx, do článku jsem to doplnil, takže se to tam brzo objeví. Vykreslení v jiném úhlu než 0 - 45 stupňů je tam vysvětleno, transformuješ souřadnice.

Odpovědět 25.5.2014 19:53
škoda mluvit
Avatar
00
Člen
Avatar
00:

K čemu je u posledního algoritmu to přetypování?

vykresli_bod(x,(int) y);
 
Odpovědět 4. října 13:17
Avatar
Odpovídá na 00
Luboš Běhounek (Satik):

copy&paste pozustatek nejspis

Odpovědět 4. října 13:22
:)
Avatar
00
Člen
Avatar
 
Odpovědět 4. října 13:22
Avatar
Odpovídá na 00
Luboš Běhounek (Satik):

J, i tam, v prvnim prikladu je y typu double.

Odpovědět  +2 4. října 13:28
:)
Avatar
Zdeněk Pavlátka
Tým ITnetwork
Avatar
Zdeněk Pavlátka:

V prvním kódu (DDA) máš v cyklu

y = y1 + smernice;

Kde y1 a smernice jsou konstanty, tudíž y bude v každém kroku stejné...
Asi by to mělo být spíše

y += smernice;
// nebo y = y + smernice;
Odpovědět 4. října 13:42
Kolik jazyků umíš, tolikrát jsi programátor.
Děláme co je v našich silách, aby byly zdejší diskuze co nejkvalitnější. Proto do nich také mohou přispívat pouze registrovaní členové. Pro zapojení do diskuze se přihlas. Pokud ještě nemáš účet, zaregistruj se, je to zdarma.

Zobrazeno 8 zpráv z 8.