Metody rasterizace 2D vektorových objektů

Používá floaty, což je pomalé. Princip stejný jako ECDDA, akorát nevyužívá error, ale zaokrouhluje y na nejbližší celé číslo.

Algoritmus funguje pro jeden směr „rychlejší“, než druhý – vzdálenost bodů na jedné ose je větší nebo stejná než na druhé. Řekněme, že úsečka vede převážně zleva doprava a pomalu stoupá. Pak je rychlejší směr po ose X. To znamená, že v každém kroku algoritmu se posuneme vždy o 1 pixel doprava a zbývá akorát zjistit, jestli se zároveň budeme posouvat i po ose Y.

Vypočítáme si poměr délky úsečky v pomalém směru oproti rychlému (y2−y1)/(x2−x1) a označíme ho delta. Ta vyjadřuje, o kolik se v každém kroku posune skutečná úsečka po pomalejší ose. Protože máme však k dispozici pixely o určite velikosti, musíme počkat, až se úsečka posune o dostatečný kus po rychlejší ose, než se můžeme po pomalejší posunout. Zavedeme si proměnnou error a nastavíme ji na 0. Poté v každém kroku zvyšujeme error o delta. Pokud nastane error > 0.5, odečteme od error jedničku a posuneme se o pixel na ose Y.

The Bresenham Line-Drawing Algorithm, by Colin Flanagan

Jde o výkonný algoritmus, který nepoužívá floating-point aritmetiku. Toho je docíleno, že obě strany nerovnice porovnávající error a 0,5 vynásobíme výrazem 2Δx. Následně převedeme vše na jednu stranu, výsledek označíme jako prediktor a porovnáváme jej s 0. Pokud je prediktor menší než 0, navýšíme ho o 2Δy. Pokud je větší nebo roven 0, zvýšíme y o 1 (posuneme se o pixel) a přičteme k prediktoru 2Δy − 2Δx.

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;
    }
  }
}

• Midpoint circle algorithm

Vychází se z rovnice pro kružnici: x² + y² = r². Každý bod kružnice by se dal počítat klasicky přes dosazaní jedné souřadnice a počítání druhé, jenže tam by se musela počítat odmocnina, což je výpočetně celkem náročné. Proto vznikla iterativní metoda midpoint, která nemusí počítat odmocninu.

Podobně jako u Bresenhama je potřeba definovat „rychlejší“ směr. Taková část kružnice se nachází například v 1. kvadrantu do úhlu 45°. Kružnici proto kreslíme pro tento úsek – zbytek kružnice je získány zrdcadlením tohoto úseku. Začneme v bodě [0, r]. Určíme tedy jako rychlejší osu X, protože kružnice v tomto úseku jde rychleji doprava, než se pohybuje dolů. V každém kroku se tedy posouváme o 1 pixel doprava, o posunu po ose Y rozhoduje prediktor. Končíme, pokud X = Y.

Tohle je trochu zábavnější než úsečka. Vpodstatě vezmeme aktuální X a Y a počítáme pro X+1 a Y−½ hodnotu r². Pokoušímě se tímto posunout se po ose Y o polovinu pixelu (správným směrem). Výsledek je umocněný poloměr kružnice, která tímto bodem prochází. Odečteme r² naší vykreslované kružnice. Pokud byla vypočítaná kružnice větší nebo stejná jako vykreslovaná, vyjde číslo nižší než 0. Znamená to, že naše kružnice je už pro toto X níž nebo stejně vysoko jako půlka pixelu, takže se posuneme o pixel dolů. V opačném případě zůstáváme.

Odvození vzorce pro prediktor je: dosadíme do rovnice kružnice X_i+1 a Y_i−½ a převedeme r² na levou stranu.

Tady to však nekončí - chceme, abychom nemuseli pokaždé prediktor počítat a zároveň nechceme pracovat s floating-point aritmetikou. Proto odvodíme rekurentní prediktor, který tomu bude vyhovovat. Rekurentní prediktor = získání příštího prediktoru z aktuální hodnoty.

Pokud prediktor v kroku i spočítáme jako <m>({x_i + 1})^2 + ({y_i - 1/2})^2 - R^2</m>, jeho další krok je spočítaný úplně stejně, jen s jinými indexy u x a y. Stačí nám tedy najít rozdíl. Pokud je prediktor v aktuálním kroku menší než 0, posouváme se pouze po ose X a další prediktor se tedy mění pouze v části <m>({x_i + 1})^2</m> a to konkrétně o <m>+ 2x_i + 3</m>. Pokud je prediktor větší než 0, mění se i v části s y a to konkrétně o <m>+ 2x_i - 2y_i + 5</m>. Zkuste si to dosadit a uvidíte…

No a protože je počáteční hodnota prediktoru 1-R (dosazením bodu [0, R] do rovnice prediktoru) a rozdíly v prediktoru jsou celočíselné, nemusíme pracovat s floating-point aritmetikou.

Požadované vlastnosti křivek:

• Invariance k lineárním transformacím – když posunu nebo rotuju všechny řídící body, nemění to tvar křivky
• Konvexní obálka – pokud bych do řídících bodů zabodnul špendlíky a přetáhl přes ně gumičku, neměla by křivka přes tuto gumičku vyčnívat
• Interpolace krajních bodů – křivka prochází krajními (prvním a posledním) body
• Lokalita změn – pokud posunu nějaký řídící bod, mělo by to ovlivnit jen nejbližší okolí, a ne celou křivku

Křivky se dají rozdělit na:

• Interpolační – křivka prochází řídícími body (ale většinou pak neleží v konvexní obálce)
• Aproximační – křivka neprochází řídícími body (ale jako by se jim jen přibližuje)

• Racionální – řídící body mají váhu, čím vyšší váha, tím víc se křivka (pokud je aproximační) blíží tomuto bodu¹⁾
• Neracionální – bez váhových koeficientů (respektive všechny řídící body je mají stejné), takže tvar křivky ovlivňuje jen poloha řídících bodů

Je určena dvěma koncovými body a dvěma tečnými vektory. Pokud na sebe chceme tyto segmenty navazovat, musí mít společné koncové body a tečné vektory (samozřejmě ale v opačném směru).

Kochanek–Bartels spline

Interpolační spline křivka. Pro interpolaci využívá Fergusonových kubik. Určeno množinou N interpolovaných bodů P_i a odpovídajícími koeficienty a_i, b_i a c_i.

Význam koeficientů:

• a_i – tenze (jak ostře příléhá křivka v bodě P_i)
• b_i – šikmost křivky
• c_i – spojitost křivky

Interpolační spline, často v praxi používaný. Nesplňuje ale požadavky na konvexní obálku a interpolaci krajních bodů (takže musíme přidat bod před začátek a konec). Tečný vektor řídícího bodu je rovnoběžný s průsečíkem dvou okolních bodů. Je to vlastně Kochanek–Bartels s nulovými koeficienty.

Bézier curve

Aproximační křivka. Používá Bernsteinovy polynomy, křivku stupně n určuje n + 1 bodů.

Obrázek vydá za tisíc slov:

Prvním krokem je postupné spojení kontrolních bodů (první s druhým, druhý se třetím, …). Každou úsečku pomyslně rozdělíme na tolik kroků, kolik bodů má mít výsledná křivka. Podle délky kroku bude výsledná křivka plynulá nebo hranatá. Potom postupně v každém kroku vezmeme další z těchto kroků na každé úsečce a vybrané body spojíme opět popořadě novými úsečkou. Tím nám vznikne polygon, který má o jeden kontrolní bod méně, než původní řídící polygon. Na tomto novém polygonu celý proces opakujeme. Postupujeme rekurzivně tak dlouho, dokud nezbyde jen jeden bod, který vykreslíme. Algoritmus se provádí nad celou křivkou, takže nesplňuje lokalitu změn.

Aproximační polynomiální křivka, která prochází koncovými body. Křivka stupně n je určena n + 1 body. Je definována Bernsteinovými polynomy, které se dají definovat i rekurentně, čehož se využívá pro algoritmus de Casteljau. Bernsteinovy polynomy mají vždy nezápornou hodnotu, mají jednotkový součet – křivka leží v konvexní obálce.

Používají racionální polynomy R. Tyto polynomy jsou váženým průměrem Bernsteinových polynomů. Pro jejich vykreslení nelze použít algoritmus de Casteljau (nejsou rekurentně zapsané). Křivka leží v konvexní obálce.

Beziérova kubika je tvořená 4 řídícími body, která vychází z teorie Beziérových křivek. Pro spojování Beziérových kubik je třeba si pamatovat pravidlo, že koncový bod prvního úseku musí být středem úsečky mezi předposledním bodem prvního úseku a druhým bodem druhého úseku. Laicky řečeno – každý oblouk je tvořen čtyřmi body, pokud navazují oblouky za sebou, tak mají vždy 1 bod společný. Pro stejnou křivku jako reprezentuje druhý animovaný obrázek (2 oblouky) je proto třeba 7 řídicích bodů (1 je společný pro obě křivky – je to vlastně inflexní bod).

Aproximační křivka, která neprocházi koncovými řídícími body. Křivka stupně n je určena n + 1 řídícími body. S křivkou pracujeme po segmentech, nelze přidat jeden bod, jen celý segment. Segment je kubika, takže má 4 body.

B-spline

Zobecnění Coonsových křivek. Křivka je určena n + 1 body a má spojitost k + 1, kde k je stupeň křivky. Její polynomy mají nezápornou hodnotu a jednotkový součet – křivka leží v konvexní obálce. Při dělení 0 je výsledek 0. Vykreslování probíhá algoritmem de Boor, což je obdoba de Casteljau. Uzlový vektor představuje hodnoty parametru t v uzlech, čímž umožňuje lokální změnu tvaru křivky.

V praxi se používá, asi by bylo dobrý o něm něco víc napsat. (pořád je to docela málo)

Non-uniform rational B-spline

Zobecnění B-spline. Je racionální, takže uzly mají váhy. Je invariantní vůči lineárním transformacím.

• rasterizace: převod matematicky (vektorově) zadaných objektů do rastru (matice bodů)
• snažíme se rasterizovat útvary tak, abychom co nejméně používali floating-point aritmetiku
• úsečka: DDA (nejhorší, naivní přístup), ECDDA (hodnota chyby v intervalu (-0,5; 0,5), pořád FP počty), Bresenham (prediktor, bez FP aritmetiky, kreslí se v rychlejším směru)
• kružnice: n-úhelník (po úsečkách, nehezké, floating point), midpoint (analogové k bresenhamu u úsečky, kreslí se 1/8, ideálně umět odvodit prediktor)
• elipsa: podobný algoritmus k midpointu, kreslí se 2x 1/8 (není totiž 8x symetrická)
• křívky: umět vlastnosti – aprox vs interpolační, konvexní obálka, invariantnost k posunu/rotaci, racionalita
• kubika: křivka definovaná čtyřmi body, polynom obsahuje třetí stupeň
• Kochanek-Bartels spline: racionální interpolační křivka, používá Fergussonovy kubiky, parametry tenze, šikmost, spojitost, Catmull-Rom je neracionální obdoba. Nesplňuje konvex. obálku
• Beziérova křivka: aproximační, interpoluje krajní body, leží v konvex. obálce, používá Bernsteinovy polynomy, vykreslení: de Casteljau [kastelžó], racionální forma nelze vykreslit pomocí Casteljau
• Coonsovy křivky: jde o kubiky, jedna kubika: segment, B-spline je obecná Coonsova křivka (obecný počet řídících bodů), vykreslení de Boor, uzlový vektor (lokalita změn), NURBS jsou obecné B-spliny: racionální, nesplňuje konvexní obálku, používá se hodně v grafice a všech těch CADech
• umět de Casteljau
• křivka se dá rasterizovat ještě foťákem