Rozdíly

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

--- temata:11-rasterizace:main [2011/03/16 14:55]
george opravy linků
+++ temata:11-rasterizace:main [2016/05/27 11:41] (aktuální)
xpavel27 [Bresenhamův algoritmus]
@@ Řádek 1: / Řádek 1: @@
+~~ODT~~
 ====== 11 - Metody rasterizace 2D vektorových objektů ======
-====== Definice ======
+<box left round blue 70%|**Definice**>
+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í.
+</box>
-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 =====
-====== Úsečka ======
+<box left round blue 70%|**Popis**>
 {{:temata:11-rasterizace:usecka.png?300|Úsečka}}
 Ú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 ====
-<m>Ax + By + C = 0, A = y_2 − y_1), B = (x_2 − x_1)</m>
+** Obecná rovnice úsečky **
-==== Parametrické vyjdření ====
+|<m>Ax + By + C = 0, A = y_2 − y_1, B = x_2 − x_1</m>|
-<m>x = x_1 + t (x_2 − x_1), y = y_1 + t (y_2 − y_1) , t\in <0, 1></m>
+** Parametrické vyjádření **
-==== Směrnicový tvar ====
+|<m>x = x_1 + t (x_2 − x_1), y = y_1 + t (y_2 − y_1) , t\in <0, 1></m>|
-<m>y = kx + q, k = {\Delta y}/{\Delta x} = (y_2 − y_1)/(x_2 − x_1)</m>
+** Směrnicový tvar **
-==== Algoritmy pro vykreslení úsečky ====
+|<m>y = kx + q, k = {\Delta y}/{\Delta x} = (y_2 − y_1)/(x_2 − x_1)</m>|
+**Algoritmy pro vykreslení úsečky**\\
 Jsou odvozeny pro případ, kdy:
   * úsečka leží v prvním kvadrantu
   * je rostoucí od P<sub>1</sub> ke koncovému P<sub>2</sub>
   * ostatní kvadranty vykreslujeme prohozením souřadnic, výměnou os
-=== DDA - Digital Differential Analyser ===
+</box>
+==== DDA - Digital Differential Analyser ====
+<box left round blue 90%|**Popis**>
   * Používá ”floating-point aritmetiku”, pak se zaokrouhluje
   * Nízká efektivita, náročná implementace do HW
-<m>x_{n + 1} = x_n + 1</m>
+  * V podstate **x** sa inkrementuje a **y** sa zväčšuje o smernicu
+  * Vzorec smernice je vyssie, je to podiel prirastku y a x
-<m>y_{n + 1} = y_n + k, k = (y_2 − y_1)/(x_2 − x_1)</m> ... směrnice
+|<m>x_{n + 1} = x_n + 1</m>|
-=== Error control DDA ===
+|<m>y_{n + 1} = y_n + k, k = (y_2 − y_1)/(x_2 − x_1)</m> ... směrnice|
+<code>
+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;
+  }
+}
+</code>
+</box>
+==== Error control DDA ====
+<box left round blue 90%|**Popis**>
   * 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**
 <code>
 LineEC(int x1, int y1, int x2, int y2)
@@ Řádek 45: / Řádek 76: @@
 }
 </code>
-===Bresenhamův algoritmus ===
+</box>
-  * 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**
-<m>E_i + k</m> se porovná s 0.5 a buď se y zvýší(<m>E_i + k \ge 0.5</m>, <m>E_{i + 1} = E_i + k</m>) nebo zůstane stejné(<m>E_i + k < 0.5, E_{i + 1} = E_i + k - 1)</m>\\
+==== Bresenhamův algoritmus ====
-Takze po vynásobení rovnic <m>2\Delta x</m>:\\
-<m>P_0 = 2\Delta y - \Delta x</m> \\
+<box left round blue 90%|**Popis**>
-<m>P_i < 0 \doubleright P_{i + 1} = P_i + 2\Delta y</m>\\
+Nejpoužívanější, velmi efektivní, snadná implementace do HW\\
-<m>P_i \ge 0 \doubleright P_{i + 1} = P_i + 2 \Delta y - 2 \Delta x</m>
+Používá celočíselnou aritmetiku, sčítání, porovnání\\
+Posun v ose Y podle znaménka **prediktoru**\\ \\
+  * Pokud <m>E_i + k \ge 0.5</m>, potom <m>E_{i + 1} = E_i + k - 1</m>\\
+  * Pokud <m>E_i + k < 0.5</m> potom <m>E_{i + 1} = E_i + k</m>\\
+Takze po vynásobení rovnic <m>2\Delta x</m>:
+  * <m>P_0 = 2\Delta y - \Delta x</m>
+  * <m>P_i < 0 \doubleright P_{i + 1} = P_i + 2\Delta y</m>
+  * <m>P_i \ge 0 \doubleright P_{i + 1} = P_i + 2 \Delta y - 2 \Delta x</m>
+V podstate:
+  * nepracujeme so smernicou ale len s prírastkami
+  * vytvoríme si tri predikáty
+    * Upravovaný predikát: <m>P_0 = 2\Delta y - \Delta x</m>
+    * Menší ako nula: <m>P_1 = 2\Delta y</m>
+    * Aspoň nula: <m>P_2 = P_1 - 2\Delta x</m>
+  * následne upravovaný predikát inkrementujeme o hodnotu P1 alebo P2
+  * v prípade, že je P aspoň 0 inkrementujeme y
 <code>
 LineBres(int x1, int y1, int x2, int y2)
 {
-  int dx = x2-x1, dy = y2-y1;
+  int dx = x2-x1;
+  int dy = y2-y1;
   int P = 2*dy – dx;
   int P1 = 2*dy, P2 = P1 - 2*dx;
@@ Řádek 72: / Řádek 118: @@
 }
 </code>
-====== Kružnice ======
+</box>
+===== Kružnice =====
+<box left round blue 90%|**Popis**>
 Kružnice je základní geometrická vektorová entita definovaná:{{ :temata:11-rasterizace:kruznice.png?300|Kružnice}}
   * souřadnicemi středu <m>[s_1, s_2]</m>
   * hodnotou poloměru R
   * rovnicí kružnice popisující geometrii:
-<m>(x − s_1)^2 + (y − s_2)^2 − R^2 = 0</m>
+\\
+|<m>(x − s_1)^2 + (y − s_2)^2 − R^2 = 0</m>|
+\\
 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].
+</box>
 ==== Vykreslení po bodech ====
+<box left round blue 90%|**Popis**>
   * 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
-  * <m>dx = 1, y = \sqrt(R^2-x^2)</m>
+|<m>dx = 1, y = \sqrt(R^2-x^2)</m>|
+{{ temata:11-rasterizace:obyckruh.png?500 }}
+</box>
 ==== Vykreslení kružnice jako N-úhelník ====
-  * 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)
+<box left round blue 90%|**Popis**>
+  * **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**
   * <m>x_{n + 1} = x_n \cos\alpha  − y_n \sin\alpha</m>
   * <m>y_{n + 1} = x_n \sin\alpha  − y_n \cos\alpha</m>
+  * **V podstate**
+  * Vypočítame cos jedného uhla <m>\cos (2\pi / N)</m>
+  * Vypočítame sin jedného uhla <m>\sin (2\pi / N)</m>
+  * Začneme na súradnici R,0
+  * Pre každý uhol vypočítame nové x a y podľa vzorca
+{{ temata:11-rasterizace:kruhuholnik.png?500 }}
+</box>
 ==== Midpoint algoritmus ====
-  * variace na Bresenhamův =>celočíselná aritmetika, vysoká efektivita, snadná implementace
+<box left round blue 90%|**Popis**>
+  * variace na Bresenhamův
+  * celočíselná aritmetika
+  * vysoká efektivita
+  * snadná implementace
   * po pixelu od [0,R] dokud <m>x = y</m>
-  * <m>p_i = (x_i + 1)^2 + (y_i − 1/2)^2 − R^2</m>
-  * <m>p_i < 0 \doubleright y_{i + 1} = y_i, p_{i+1} = p_i + 2x_i + 3</m>
-  * <m>p_i \ge 0 \doubleright y_{i + 1} = y_i - 1, p_i + 1 = p_i + 2x_i − 2y_i + 5</m>
   * startovací hodnota je <m>p_i = 1 − R</m>
-<code>
-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++;
-  }
-}
-</code>
-====== Elipsa ======
+|<m>p_i = (x_i + 1)^2 + (y_i − 1/2)^2 − R^2</m>|
+|<m>p_i < 0 \doubleright y_{i + 1} = y_i, p_{i+1} = p_i + 2x_i + 3</m>|
+|<m>p_i \ge 0 \doubleright y_{i + 1} = y_i - 1, p_i + 1 = p_i + 2x_i − 2y_i + 5</m>|
+{{ temata:11-rasterizace:basenkruh.png?500 }}
+</box>
+===== Elipsa =====
+<box left round blue 90%|**Popis**>
 Elipsa je základní geometrická vektorová entita definovaná:
   * souřadnicemi středu
@@ Řádek 120: / Řádek 196: @@
   * úhlem natočení hlavní poloosy
   * rovnicí elipsy popisující geometrii: <m>F(x, y) : b^2x^2 + a^2y^2 − a^2b^2 = 0</m>
-====Midpoint algoritmus ====
+  * je 4x symetrická.
+  * výpočet pre štvrtinu bodov
+</box>
+==== Midpoint algoritmus ====
+<box left round blue 90%|**Popis**>
   * ekvivalent midpointu pro kružnici
   * efektivní, snadná implementace v HW, celočíselná aritmetika
@@ Řádek 126: / Řádek 208: @@
   * 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.
-====== Křivky ======
-Rovnost přímek a kulatost kružnic je ideál, ve skutečnosti potřebujeme popsat křivé tvary.
+{{ temata:11-rasterizace:midelipsa.png?500 }}
-Parametrické vyjádření není pro grafiku vhodné, používá se maticový zápis.
+</box>
+===== Křivky =====
+<box left round blue 90%|**Popis**>
+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://
+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)\\
+**INTERPOLAČNÍ KŘIVKA**(prochází body) vs. **APROXIMAČNÍ KŘIVKA**(neprochází řídícími body)
-Spojitost:
+**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
+**Spline křivky** - po částech polynomiální křivka, používá se s cílem minimalizace křivosti křivky(délku, energii)
-==== Fergusonova kubika ====
+**Přirozený spline** - interpoluje své řídící body
+</box>
+==== Interpolační ====
+=== Fergusonova kubika ===
+<box left round blue 90%|**Popis**>
   * Nejčastější interpolační křivka
   * Určena dvěma koncovými body a dvěma tečnými vektory
@@ Řádek 149: / Řádek 246: @@
   * Pro definici se používá maticový zápis Hermitových polynomů
-==== Kochanek Bartels spline ====
+{{:temata:11-rasterizace:ferguson.jpg}}
+</box>
+=== Kochanek Bartels spline ===
+<box left round blue 90%|**Popis**>
   * 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ů
-==== Catmull-Rom spline ====
+{{:temata:11-rasterizace:kochanek_bartels_spline.png|}}
+</box>
+=== Catmull-Rom spline ===
+<box left round blue 90%|**Popis**>
   * interpolační spline křivka určená množinou bodů
   * Kochanek-Bartels spline s nulovými koeficienty
@@ Řádek 159: / Řádek 267: @@
   * neleží v konvexní obálce
   * tečný vektor je rovnoběžný s přímkou procházející sousedními body
-==== Beziérovy křivky ====
+{{:temata:11-rasterizace:catmull-rom.jpg|}}
+</box>
+==== Aproximační ====
+=== Beziérovy křivky ===
+<box left round blue 90%|**Popis**>
   * 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.
-==== Beziérovy kubiky ====
+{{:temata:11-rasterizace:bezier.jpg|}}
+</box>
+=== Beziérovy kubiky ===
+<box left round blue 90%|**Popis**>
   * 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
-==== Racionální beziérové křivky ====
+{{:temata:11-rasterizace:beziercubic.jpg|}}
+</box>
+=== Racionální beziérové křivky ===
+<box left round blue 90%|**Popis**>
   * 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
-==== Coonsova kubika ====
+{{:temata:11-rasterizace:rationalbezier.jpg|}}
+</box>
+=== Coonsova kubika ===
+<box left round blue 90%|**Popis**>
   * 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
-==== B-spline křivky ====
+</box>
+=== B-spline křivky ===
+<box left round blue 90%|**Popis**>
   * zobecnění Coonsových kubik
   * křivka určena n+1 body a má spojitost k+1, kde k je stupněm křivky
@@ Řádek 184: / Řádek 322: @@
   * 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)
-==== NURBS Non Uniform Rational B-Spline ====
+{{:temata:11-rasterizace:bspline.jpg|}}
+</box>
+=== NURBS Non Uniform Rational B-Spline ===
+<box left round blue 90%|**Popis**>
   * zobecnění B-spline křivek
   * přírůstek hodnoty parametru uzlového vektrou nemusí být konstantní(neuniformita)
@@ Řádek 190: / Řádek 334: @@
   * invariantí vůči lineárním transformacím
   * umožnuje přesně vyjádřit kuželosečky
+{{:temata:11-rasterizace:nurbs.jpg|}}
+</box>
 ====== Pro zájemce ======
@@ Řádek 200: / Řádek 347: @@
   * [[http://en.wikipedia.org/wiki/Cubic_Hermite_spline]]
   * [[http://en.wikipedia.org/wiki/Steven_Anson_Coons]]
+  * [[http://en.wikipedia.org/wiki/Kochanek–Bartels_spline]]
 </box>

temata/11-rasterizace/main.1300283756.txt.gz · Poslední úprava: 2011/03/16 14:55 autor: george

Zobrazit stránku Starší verze

Zpětné odkazy Nahoru