Rozdíly

Zde můžete vidět rozdíly mezi vybranou verzí a aktuální verzí dané stránky.

@@ Řádek 1: / Řádek 1: @@
+====== Metody rasterizace 2D vektorových objektů ======
+===== Úsečky =====
+==== Digital differential analyser (DDA) ====
+Používá floaty, což je pomalé.
+Princip stejný jako ECDDA, akorát nevyužívá error, ale zaokrouhluje y na nejbližší celé číslo.
+==== Error Control DDA (ECDDA) ====
+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.
+<note>V praxi se to vždy počítá v tom směru kde X roste rychleji než Y a pro jinak orientované úsečky se otáčejí a prohazují souřadnice.</note>
+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.
+==== Bresenhamův algoritmus ====
+[[http://www.cs.helsinki.fi/group/goa/mallinnus/lines/bresenh.html|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.
+<code c>
+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;
+    }
+  }
+}
+</code>
+===== Kružnice =====
+  * [[wp>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.
+==== Prediktor ====
+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<sub>i</sub>+1 a Y<sub>i</sub>−½ 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.
+===== Křivky =====
+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((Takže když budou mít všechny řídící body maximální váhu, bude to jen lomená čára.))
+  * 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ů
+<note>Všechny ty vzorce a matice bych si nezapamatoval ani omylem, tak je sem ani nepíšu.</note>
+==== Fergusonova kubika ====
+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 ====
+[[wp>Kochanek–Bartels spline]]
+Interpolační spline křivka. Pro interpolaci využívá Fergusonových kubik. Určeno množinou N interpolovaných bodů P<sub>i</sub> a odpovídajícími koeficienty a<sub>i</sub>, b<sub>i</sub> a c<sub>i</sub>.
+Význam koeficientů:
+  * a<sub>i</sub> -- tenze (jak ostře příléhá křivka v bodě P<sub>i</sub>)
+  * b<sub>i</sub> -- šikmost křivky
+  * c<sub>i</sub> -- spojitost křivky
+==== Catmull–Rom spline ====
+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.
+==== Beziérovy křivky ====
+[[wp>Bézier curve]]
+Aproximační křivka. Používá Bernsteinovy polynomy, křivku stupně //n// určuje //n// + 1 bodů.
+=== Algoritmus de Casteljau ===
+Obrázek vydá za tisíc slov:\\
+{{http://upload.wikimedia.org/wikipedia/commons/f/ff/Bezier_3_big.gif}}{{http://upload.wikimedia.org/wikipedia/commons/7/7d/Bezier_4_big.gif}}
+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.
+=== Beziérovy křivky ===
+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.
+=== Racionální Beziérovy křivky ===
+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érovy kubiky ===
+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).
+==== Coonsovy křivky ====
+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 ====
+[[wp>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á [[wp>De Boor's algorithm|algoritmem de Boor]], což je obdoba [[#Algoritmus de Casteljau|de Casteljau]]. Uzlový vektor představuje hodnoty parametru //t// v uzlech, čímž umožňuje lokální změnu tvaru křivky.
+FIXME V praxi se používá, asi by bylo dobrý o něm něco víc napsat. (pořád je to docela málo)
+==== NURBS ====
+[[wp>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.
+===== Shrnutí =====
+  * 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
+  * [[http://www.fit.vutbr.cz/~krivka/|křivka]] se dá rasterizovat ještě foťákem :-P

Kalábovi

Uživatelské nástroje

Nástroje pro tento web

Rozdíly

Nástroje pro stránku