RASTERIZACIA (SCAN CONVERSION)
 --------------------------------

  Rasterizacia usecky - Prirastkovy algoritmus
 ----------------------------------------------

  DDA - digital differential analyzer

  y = mx + b ... rovnica usecky, kde 
    (x1,y1) (x2,y2) su koncove body
    m = (y2-y1) / (x2-x1)
    m = \delta y / \delta x  pre lub podusecku

  pre "oktant" so sklonom m, 0 <= m <= 1:
    \delta x = 1
    \delta y = m \delta x = m
    cize x_{k+1} = x_k + 1
         y_{k+1} = y_k + m

  pre "oktant" so sklonom m > 1:
    \delta y = 1
    \delta x = \delta y / m
    cize y_{k+1} = y_k + 1
         x_{k+1} = x_k + 1/m
  
  ak kreslime sprava dolava: 
    \delta x = -1
    \delta y = -m
  ak kreslime zhora nadol:
    \delta y = -1
    \delta x = -1/m
  pripadne urobit najprv swap

  vykreslia sa zaokruhlene suradnice


  Rasterizacia usecky - Bresenhamov algoritmus
 ----------------------------------------------

  efektivnejsi nez prirastkovy
  vyuziva len celociselnu aritmetiku

  y = mx + b, nech 0 < m < 1, nech x2 > x1

  \delta x = x2 - x1
  \delta y = y2 - y1
  t.j. m = \delta y / \delta x

  ak (x_k, y_k) je bod v rastri, ktory parti usecke, nasledujuci
  vysvieteny bude bud (x_k + 1, y_k) alebo (x_k + 1, y_k + 1)

  y = m(x_k + 1) + b  - skutocny bod na usecke so suradnicou x = x_k + 1
  odchylky dvoch kandidatov v rastri:
    d_{dolna} = y - y_k      = m(x_k + 1) + b - y_k
    d_{horna} = y_k + 1 - y  = y_k + 1 - m(x_k + 1) - b

    nech \delta x = x2-x1 > 0
    d_{dolna} - d_{horna} = 2m(x_k + 1) - 2y_k + 2b - 1   | .\delta x (= x2-x1)
    p_k = \delta x (d_{dolna} - d_{horna}) = 
        = 2\delta y (x_k + 1) - 2\delta x y_k + 2\delta x b - \delta x
        = 2\delta y x_k - 2\delta x y_k + 2\delta y - \delta x + 2\delta x b
        = 2\delta y x_k - 2\delta x y_k + C 
            kde C = 2\delta y + \delta x (2b - 1) - konst pre celu usecku

    ak p_k < 0 (d_{dolna} < d_{horna}), y_{k+1} = y_k
    inak y_{k+1} = y_k + 1 

    p_{k+1} - p_k = 2\delta y (x_{k+1} - x_k) - 2\delta x (y_{k+1} - y_k)
    p_{k+1} = p_k + 2\delta y - 2\delta x (y_{k+1} - y_k)
                                                  |.......... = 0 alebo 1
    este prva hodnota:
    p_0 = 2\delta y x_0 - 2\delta x y_0 + 2\delta y + \delta x (2b - 1)
        = 2\delta x(y_0 - b) - 2\delta x y_0 + 2\delta y + \delta x (2b - 1)
        = 2\delta y - \delta x

  zhrnutie: 
    predvypocet: 2\delta y, 2\delta y - 2\delta x
    p_0 = 2\delta y - \delta x
    p_{k+1} = | p_k + 2\delta y,              ak y_{k+1} = y_k
              | p_k + 2\delta y - 2\delta x,  ak y_{k+1} = y_k + 1
    ... same celociselne operacie


  Rasterizacia kruznice
 -----------------------

  f(x,y) = x^2 + y^2 - r^2
  f(a,b) > 0 ... vonku, = 0 na kruznici, < 0 vnutri

  rasterizuje sa po okrantoch, oktant z (0,r) doprava:

  (x_k, y_k) na kruznici -> nasledujuci je bud (x_k + 1, y_k)
    alebo (x_k + 1, y_k - 1)

  p_k := f(x_k+1, y_k - 1/2) - rozhodujuca hodnota
    p_k >= 0 tak y_{k+1} = y_k - 1
    inak         y_{k+1} = y_k

  p_{k+1} = p_k + 2x_k + 3 + (y_{k+1}^2 - y_k^2) - (y_{k+1} - y_k)

  p_k >= 0 tak 
    y_{k+1} = y_k - 1
    p_{k+1} = p_k + 2x_k - 2y_k + 5
  inak 
    y_{k+1} = y_k
    p_{k+1} = p_k + 2x_k + 3
  
  inicializacia: p_0 = f(1, r-1/2) = 5/4 - r
    ak r je cele cislo, moze byt p_0 = 1 - r


  Uloha: rasterizacia elipsy, inej kuzelosecky


  Rasterizacia mnohouholnika
 ----------------------------

  rasterizovat tak, aby sa kazdy bod vykreslil (podla moznosti) 
  len jedenkrat, aj ked sa bude rasterizovat cela siet:

  k mnohouholniku partia: vnutorne body
                          lava a spodna hranica (horna a prava patria uz inam)

  skenovacia priamka: y = konst,
    vykresluju sa vsetky body pozdlz priamky patriace polygonu

  problemy, ulohy:
    test parity na vnutro, 
    specialne pripady priesecniku testovacej/skenovacej priamky vo vrchole, 
    vodorovne prianky
    ...
  vsetko sa vyriesi algoritmom:

  1. vyrad vsetky vodorovne hrany hranice mnohouholnika 
     z dalsieho uvazovania
  2. skrat vsetky zvysne hrany zhora o 1 bod, 
     t.j. kazdy bod hranice uz patri len jednej hrane (ak vobec)
  3. zametaj skenovacou priankou oddola:
     a) pre kazde y obnov tabulku aktivnych hran (TAH)
        - TAH obsahuje vsetky hrany, s ktorymi sa priamka pretina,
        - usporiadane podla x-suradnice priesecnika
        - pre kazdu hranu tam je:
           - y_max = y-suradnica najvyssieho bodu na hrane
           - x = x-suradnica priesecnika
           - \delta x = prirastok x-suradnice zodpovedajuci \delta y = 1
        - obnova TAH :
           - vyhod hrany, pre ktore aktualne y = y_max
           - pre ostatne hrany x := x + \delta x
           - spravne zarad (usporiadane podla x) hrany, 
               ktore zacinaju v tomto y
     b) vykresli body pozdlz skenovacej priamky:
        prechadzaj priamkou zlava doprava a vzdy na priesecniku s hranou
          prepri stav pera (mod kresli/nekresli)


  Vyplnanie oblasti
 -------------------

  pre urcenie spojitosti oblasti si treba najprv vyjasnit, ci uvazujeme
  4-susednost alebo 8-susednost

  vnutro a hranica - doplnkove susednosti:
    pre 4-susedne vnutro staci 8-susedne spojita hranica
    pre 8-susedne vnutro treba 4-susedne spojitu hranicu

  1) vyplnanie oblasti urcenej (starou, povodnou) farbou vnutra:
     treba len prepisovat staru farbu novou:

     premenne: staraf, novaf
     fction floodfill(x,y)
       ak farba(x,y) = stara farba   // treba prekreslit
         farba(x,y) := novaf;
         //  spusti alg pre vsetkych susedov, tu: 4-susedne spojite vnutro
         floodfill(x+1,y);
         floodfill(x,y+1);
         floodfill(x-1,y);
         floodfill(x,y-1);

  2) vypnanie oblasti urcenej hranicou (farbou hranice)

     premenne: novaf, fhranice
     fction boundfill(x,y)
       ak farba(x,y) <> fhranice a tiez farba(x,y) <> novaf 
         farba(x,y) := novaf;
         //  spusti alg pre vsetkych susedov, tu: 8-susedne spojite vnutro
         boundfill(x+1,y);
         boundfill(x+1,y+1);
         boundfill(x,y+1);
         boundfill(x-1,y+1);
         boundfill(x-1,y);
         boundfill(x-1,y-1);
         boundfill(x,y-1);
         boundfill(x+1,y-1);

  problemy:
  - pri bound fill sa oblast nemusi vyplnit cela, ak sa uz vnutri 
    nachadzaju nejake body vyplnene novou farbou 
    - nova farba funguje aj ako farba hranice

    -> riesenie: prekreslit najprv tie body vnutri, ktore maju novu farbu,
       docasne nejakou inou (treba dako preskenovat vnutro)

  - velmi hlboka rekurzia, casto sa preplni zasobnik

    -> riesenie: neukladat do zasobnika vsetkych susedov, ale:
       - vyplnit cely riadok (od hranice po hranicu)
       - ulozit do zasobnika len jeden bod nad a jeden pod riadkom:
         pozor na diery, niekedy treba ulozit viac bodov nad/pod, 
         ked su oddelene farbou hranice