Rasterizace je proces převodu vektorové reprezentace dat na jejich rastrovou formu s cílem dosáhnout maximální možnou kvalitu a zároveň rychlost výsledného zobrazení.

Úsečka je základní geometrická vektorová entita definovaná:

• souřadnicemi dvou koncových bodů
• rovnicí přímky popisující geometrii

Obecná rovnice úsečky

Parametrické vyjádření

Směrnicový tvar

Algoritmy pro vykreslení úsečky
Jsou odvozeny pro případ, kdy:

• úsečka leží v prvním kvadrantu
• je rostoucí od P₁ ke koncovému P₂
• ostatní kvadranty vykreslujeme prohozením souřadnic, výměnou os

• Používá ”floating-point aritmetiku”, pak se zaokrouhluje
• Nízká efektivita, náročná implementace do HW
• V podstate x sa inkrementuje a y sa zväčšuje o smernicu
• Vzorec smernice je vyssie, je to podiel prirastku y a x

LineDDA(int x1, int y1, int x2, int y2)
{
  double k = (y2-y1)/(x2-x1);
  double y = y1;
  for (int x = x1; x <= x2; x++)
  {
    draw_pixel( x, y);
    y += k;
  }
}

• modifikace DDA
• V podstate len používame premennú E kde ukladame smernicu
• Ak je hodnota E aspoň 0.5 a viac inkrementujeme X a odpočítame jedničku

LineEC(int x1, int y1, int x2, int y2)
{
  double k = (y2-y1) / (x2-x1);
  double E = 0;
  int y = y1;
  for (int x = x1; x <= x2; x++)
  {
    draw_pixel( x, y);
    E += k;
    if (E >= 0.5) { y++; E -= 1; }
  }
}

Nejpoužívanější, velmi efektivní, snadná implementace do HW
Používá celočíselnou aritmetiku, sčítání, porovnání
Posun v ose Y podle znaménka prediktoru

• Pokud , potom
  
• Pokud potom
  

Takze po vynásobení rovnic :

• 
• 
• 

V podstate:

• nepracujeme so smernicou ale len s prírastkami
• vytvoríme si tri predikáty
  • Upravovaný predikát:
  • Menší ako nula:
  • Aspoň nula:
• následne upravovaný predikát inkrementujeme o hodnotu P1 alebo P2
• v prípade, že je P aspoň 0 inkrementujeme y

LineBres(int x1, int y1, int x2, int y2)
{
  int dx = x2-x1;
  int dy = y2-y1;
  int P = 2*dy – dx;
  int P1 = 2*dy, P2 = P1 - 2*dx;
  int y = y1;
  for (int x = x1; x <= x2; x++)
  {
    draw_pixel( x, y);
    if (P >= 0)
    { P += P2; y++; }
    else
      P += P1;
  }
}

Kružnice je základní geometrická vektorová entita definovaná:

• souřadnicemi středu
• hodnotou poloměru R
• rovnicí kružnice popisující geometrii:

Kružnice je 8*symetrická⇒výpočet pro polovinu bodů jednoho kvadrantu, zbytek prohozením souřadnic a/nebo znamének souřadnice.
Algoritmy jsou odvozeny pro kružnice se středem v počátku [0,0].

• Používá ”floating-point aritmetiku”
• nízká efektivita, náročná implementace v HW
• vykreslujeme ve smere hodinových ruciciek.
• od bodu [0,R] po pixelech dokud není x=y

• Info
• varianta DDA pro kružnici-floating point
• aplikace rotacní transformace bodu.
• používá „floating-point aritmetiku“.
• nízká efektivita, nárocná implementace do HW.
• rekurentní posun o konstaní přírůstek úhlu
• funkce sin a cos jsou vypocítány pouze jednou!
• souradnice X a Y se zaokrouhlují na nejbližší celé císlo.
• vypoctené souˇradnice spojujeme úseckami.

• Vzorce
• 
• 

• V podstate
• Vypočítame cos jedného uhla
• Vypočítame sin jedného uhla
• Začneme na súradnici R,0
• Pre každý uhol vypočítame nové x a y podľa vzorca

• variace na Bresenhamův
• celočíselná aritmetika
• vysoká efektivita
• snadná implementace
• po pixelu od [0,R] dokud
• startovací hodnota je

Elipsa je základní geometrická vektorová entita definovaná:

• souřadnicemi středu
• hodnotami hlavní a vedlejší poloosy
• úhlem natočení hlavní poloosy
• rovnicí elipsy popisující geometrii:
• je 4x symetrická.
• výpočet pre štvrtinu bodov

• ekvivalent midpointu pro kružnici
• efektivní, snadná implementace v HW, celočíselná aritmetika
• oblast I od[0,b] do 2b²x=2a²y. Oblast II do [a,0]
• založen na určování polohy midpointu vůči elipse
• V ose X/Y postupujeme o 1, v Y/X o posunu rozhoduje znaménko prediktoru.

Rovnost přímek a kulatost kružnic je ideál, ve skutečnosti potřebujeme popsat křivé tvary. Parametrické vyjádření není pro grafiku vhodné, používá se maticový zápis.
Další použití:definice modelů, šablonování, definice fontů, určování dráhy objektů v animaci.

Požadované vlastnosti:

• Invariance k lineárním transformacím(rotace řídících bodů nesmí ovlivnit průběh křivky)
• Konvexní obálka - křivka leží v konvexní obálce svých řídících bodů
• Interpolace krajních bodů
• Lokalita změn - pokud posuneme řídící bod, mělo by se změnit jen jeho okolí ne celá křivka

INTERPOLAČNÍ KŘIVKA(prochází body) vs. APROXIMAČNÍ KŘIVKA(neprochází řídícími body)

Racionální křivka - řídící body mají váhové koeficienty (Neracionální - váhové koef.o velikosti 1)

Spojitost:

• C0 - totožnost navazujících koncových bodů
• C1 - totožnost tečných vektorů v navazujících bodech
• C2 - totožnost vektorů 2.derivace v navazujicích bodech

Spline křivky - po částech polynomiální křivka, používá se s cílem minimalizace křivosti křivky(délku, energii)

Přirozený spline - interpoluje své řídící body

• Nejčastější interpolační křivka
• Určena dvěma koncovými body a dvěma tečnými vektory
• Pro navázání segmentů je třeba definovat stejný bod i tečný vektor v obou segmentech (segment=křivka mezi dvěma body)
• Pro definici se používá maticový zápis Hermitových polynomů

• interpolační spline křivka využívající Fergusonových kubik
• určena množinou interpolačních bodů a jejich koeficientů, které určují chování v daném bodě
• použití v animaci pro definici dráhy pohybu objektů

• interpolační spline křivka určená množinou bodů
• Kochanek-Bartels spline s nulovými koeficienty
• vychází z druhého bodu a končí v předposledním⇒k interpolaci okrajových bodů se použije zdvojení
• neleží v konvexní obálce
• tečný vektor je rovnoběžný s přímkou procházející sousedními body

• Aproximační polynomiální křivka stupně n je určena n+1 body
• používá Bernsteinovy polynomy definované rekurentě
• prochází koncové body, leží v konvexní obálce
• možno pro vykreslení použít algoritmus de Casteljau⇒dělení úseků řídícího polynomu na části t a 1 - t, spojování rekurzivně spočtených bodů úsečkami⇒body úsečky jsou rovnoměrně rozprostřené body pro rovné i křivé části.

• jeden segment popsán 4 řídícími body
• při napojovánní segmentů je nutno mít totožné koncové body i tečné vektory v těchto bodech
• invariantní k lineárním transformacím
• vykreslování pomocí de Casteljau s koeficientem t=0.5

• místo neracionálních Bersteinových polynomů se používají racionální polynomy
• křivka leží v konvexní obálce
• nelze použít algoritmus de Casteljau

• aproximační křivka, která neprochází koncovými řídícími body
• polynomiální křivka n-tého stupně určena n+1 řídícími body
• s křivkou se dá pracovat jen po segmentech, nelze přidávat jen samostatné body

• zobecnění Coonsových kubik
• křivka určena n+1 body a má spojitost k+1, kde k je stupněm křivky
• mají nezápornou hodnotu a jednotkový součet⇒leží v konvexním obálce
• vykreslování algoritmem de Boor(obdoba de Casteljau)
• uzlový vektor představuje hodnoty parametru t v uzlech, čímž umožňuje lokální změnu křivky
• uniformní je když je přírůstek t konstantní(např uzlový vektor 0,0.2,0.4,0.6,0.8,1)

• zobecnění B-spline křivek
• přírůstek hodnoty parametru uzlového vektrou nemusí být konstantní(neuniformita)
• každý bod má váhový koeficient(racionální)
• invariantí vůči lineárním transformacím
• umožnuje přesně vyjádřit kuželosečky