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

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

… směrnice

• modifikace DDA

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

se porovná s 0.5 a buď se y zvýší(, ) nebo zůstane stejné(
Takze po vynásobení rovnic :

LineBres(int x1, int y1, int x2, int y2)
{
  int dx = x2-x1, 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
• od bodu [0,R] po pixelech dokud není x=y
• 

• varianta DDA pro kružnici-floating point, nízka efektivita, vysoká náročnost implementace v HW
• rekurentní posun o konstaní přírůstek úhlu(sin a cos se počítají pouze jednou)
• 
• 

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

CircleMid(int s1, int s2, int R)
{ int x = 0, y = R;
  int P = 1-R, X2 = 3, Y2 = 2*R-2;
  while (x < y)
  {
    draw_pixel_circle(x, y);
    if (P >= 0)
    { P += -Y2; Y2 -= 2; y--; }
    P += X2;
    X2 += 2;
    x++;
  }
}

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:

• 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