====== Zadání ====== Kreslení grafických primitiv, rastrové algoritmy DDA, s rozhodovacím členem. Rasterizace a vyplňování rovinných primitiv. Ořezávací algoritmy. ====== Rasterizace ====== Rasterizace je proces převodu vektorové reprezentace obrazových dat na jejich rastrovou formu s cílem dosáhnout maximální možnou kvalitu a zároveň rychlost výsledného zobrazení. Při zobrazování je rasterizace velmi často opakovaná operace! Realizována v HW grafické karty. {{:mgr-szz:in-gra:rasterizace.jpg|}} Algoritmy pro vykreslení jsou typicky odvozeny pro případ, kdy obrazec leží v prvním kvadrantu, je rostoucí odpočátečního bodu P1 ke koncovému P2 a nejrychleji roste ve směru osy X. Ostatní místa vykreslování je potřeba převést na tento případ (prohození souřadnic, os, apod.). ===== DDA - Digital Differential Analyser ===== Používá floating-point aritmetiku, pro úsečky a kružnice. Nízká efektivita, náročná implementace do HW. **Vykreslujeme po pixelu od bodu P1 k bodu P2. V ose X postupujeme s přírůstkem dx = 1. V ose Y je přírůstek dán velikostí směrnice objektu. Souřadnice Y se zaokrouhluje na nejbližší celé číslo.** ===== Úsečka ===== Definice souřadnicemi dvou koncových bodů nebo rovnicí přímky popisující geometrii. ==== Obecná rovnice úsečky ==== Ax + By + C = 0 A = (y_1 - y_2) B = (x_2 - x_1) ==== Parametrické vyjádření ==== x = x_1 + t (x_2 - x_1) y = y_1 + t (y_2 - y_1) t \in < 0, 1 > ==== Směrnicový tvar ==== y = kx + q k = \frac{\Delta y}{\Delta x} = \frac{y_2 - y_1}{x_2 - x_1} ---- ==== DDA algoritmus pro úsečku ==== {{:mgr-szz:in-gra:ddausecka.png|}} === Error control DDA === Modifikace DDA algoritmu. V ose X postupujeme s přírůstkem dx = 1 , v ose Y vyjádříme relativní odchylku E = k. Pokud je E >= 0.5, posouváme se na další řádek a E = E − 1. ==== Rozhodovací člen – Bresenhamův algoritmus ==== Použití celočíselné aritmetiky. {{:mgr-szz:in-gra:bresenham.png|}} {{:mgr-szz:in-gra:bresenhamvysvetleni.png|}} === Pseudokód === {{:mgr-szz:in-gra:bresenhamalgoritmus.png|}} ===== Kružnice ===== Definice souřadnicemi středu a hodnotou poloměru. ==== Obecná rovnice ==== (x - s_1)^2 + (y - s_2)^2 - R^2 = 0 Symetrická po **půlkvadrantech** – obvykle rasterizujeme polovinu prvního kvadrantu, zbylé body zkopírujeme se změnou (prohozením) souřadnic. ==== Naivní algoritmus ==== Vykreslujeme po bodech ve směru hodinových ručiček od pixelu [0, R]. Postupujeme po jednom bodu v ose x dokud není x = y, potom postupujeme po jednom bodu v ose y. Floating-point aritmetika, složité v HW. {{:mgr-szz:in-gra:kruznicenaivne.png|}} ==== DDA algoritmus pro kružnici ==== Vykresluje kružnice jako n-úhelníky. {{:mgr-szz:in-gra:kruznicedda.png|}} {{:mgr-szz:in-gra:kruzniceddaeq.png|}} ==== Midpoint ==== S rozhodovací členem - variace na Bresenhamův algoritmus. Určování polohy „midpointu“ vůči kružnici – vevnitř nebo vně. Celočíselná aritmetika, snadná implementace v HW. Posouvání po 1 bodě v x-ové souřednici, v y-ové podle znaménka rozhodovacího členu. {{:mgr-szz:in-gra:midpoint.png|}} {{:mgr-szz:in-gra:midpointobr.png|}} {{:mgr-szz:in-gra:midpointeq.png|}} ===== Elipsa ===== Definice souřadnicemi středu, hodnotami hlavní a vedlejší poloosy a úhlem natočení hlavní poloosy. Obecná rovnice: F(x,y) : b^2x^2 + a^2y^2 - a^2b^2 = 0 Symetrie kvadrantů – vykreslíme jeden kvadrant a ostatní zkopírujeme se změnou souřadnic. ==== Midpoint algoritmus ==== Pro oblast I jdeme postupujeme po jednom pixelu v ose x od bodu [0,b], dokud není 2b^2 x = 2a^2 y. Pak pro oblast II až do bodu [a,0] postupujeme po jednom pixelu v ose y. Rozhodovací člen podobně jako pro kružnici. {{:mgr-szz:in-gra:elipsamidpoint.png|}} ====== Vyplňování ====== ===== Semínkové vyplňování ===== Naivní rekurzivní algoritmus. "Zasadíme" semínko do bodu. Algoritmus obarví aktuální bod a otestuje své okolí, zda lze obarvit. Pokud ano, spustí se pro obarvitelné okolní body znova (rekurzivně). Hraniční varianta vyplňuje až dokud nenarazí na zadanou hraniční barvu. {{:mgr-szz:in-gra:seminko1.png|}} Přebarvení jedné barvy naopak vyplňuje, dokud je v okolí stejná barva jako na počátku (možnost přidat toleranci např. pro malé rozdíly). {{:mgr-szz:in-gra:seminko2.png|}} ==== Okolí ==== * **4-okolí** - pro situace, kdy jsou hranice "šišaté" a rasterizovány jen jedním pixelem * **8-okolí** - pro situace, kdy se rasterizované hranice mohou diagonálně dotýkat, přestože ve vektorové reprezentaci byly malé mezery {{:mgr-szz:in-gra:seminkookoli.png|}} ===== Modifikace semínkového vyplňování po řádcích ===== Od semínka obarvujeme pixely vodorovně na obě strany, při nalezení přiléhající oblasti k vyplnění zasadíme jedno semínko na její začátek. {{:mgr-szz:in-gra:seminkaradkove.png|}} ===== Řádkové vyplňování ===== Nalezneme bounding-box objektu. Řádky v něm procházíme z jedné strany. Při průchodu hranou přepneme obarvování – po lichých hranách obarvujeme, po sudých vypínáme obarvování. {{:mgr-szz:in-gra:radkove.png|}} ==== Problém – vnitřní vrcholy ==== Řešení: * V potřebných extrémech generovat **dva průsečíky** (zde se obarvování vypne a hned zapne) {{:mgr-szz:in-gra:radkovedva.png|}} * **Zkrácení** všech hran ve směru Y o **1 px**. Potřeba překreslit obrys {{:mgr-szz:in-gra:radkovezkraceni.png|}} ===== Inverzní řádkové vyplňování ===== V bounding-boxu objektu od každé hrany napravo po řádcích „zinverzníme“ vyplnění (vyplníme tam, kde není vyplněno, zrušíme vyplnění tam, kde je vyplněno). Vynecháme vodorovné hrany (y1 = y2). Nutno překreslit obrys. {{:mgr-szz:in-gra:inverzni.png|}} ===== Optimalizace: Plotové vyplňování ===== Inverze po řádcích jen ke zvolenému plotu (svislice od některého vrcholu). Vždy od strany směrem k plotu. Méně zbytečných operací. {{:mgr-szz:in-gra:plotove.png|}} ===== Pinedův algoritmus ===== Pouze konvexní mnohoúhelníky (typicky trojúhelníky). Rozdělení roviny na oblasti dané polorovinami úseček polygonu. Určíme, které poloroviny jsou vevnitř a které vně. Právě v oblastech, které jsou pouze vnitřní, provedeme vybarvení. Vnitřní a vnější oblast určíme jako vpravo a vlevo (hrany jsou seřazeny podle hodinových ručiček). Snadné v HW. {{:mgr-szz:in-gra:pineda.png|}} ==== Vyplnění ==== * Postupujeme v opsaném obdélníku. Zbytečný průchod 1/2 pixelů {{:mgr-szz:in-gra:pineda1.png|}} * Začneme nejvyšším vrcholem, při nárazu na hranu otáčíme. Algoritmicky složitější {{:mgr-szz:in-gra:pineda2.png|}} * Od „plotu“ ve středu (opsaného obdélníka). Možná paralelizace {{:mgr-szz:in-gra:pineda3.png|}} ===== Problémy vykreslování ===== Možno "odstranit" (spíše zamaskovat) antialiasingem (částečným překrytím). ==== Sdílené nebo překrývající se hrany ==== Záleží na pořadí vykreslení polygonů. {{:mgr-szz:in-gra:sdilenahrana.png|}} ==== Střípek ==== Tenký polygon nemusí zasáhnout žádný z procházejících pixelů takovou mírou, aby se něco vykreslilo. {{:mgr-szz:in-gra:stripek.png|}} ==== Pohyblivé střípky ==== Malá změna polohy = velká změna vykreslení. {{:mgr-szz:in-gra:stripekposun.png|}} ===== Další možnosti vykreslování ===== ==== Šrafování ==== {{:mgr-szz:in-gra:srafovani.png|}} ===== Vyplňování vzorkem ===== {{:mgr-szz:in-gra:vzorovani.png|}} ====== Ořezávání ====== Výběr zobrazovaných objektů vzhledem k aktuální poloze a rozměrům zobrazovacího okna. Objekty mimo okno budou vyloučeny. Objekty, které hranice okna protínají, budou rozděleny (oříznuty). Výsledkem vždy objekt stejného typu (úsečka, polygon, atd.), jako původní. ===== Naivní ořezávání ===== pro každou úsečku pro každou hranu okna nalezni průsečík přímky s přímkou vyber „skutečné“ průsečíky pokud něco zbylo, tak to nakresli Neoptimální. {{:mgr-szz:in-gra:orez.png|}} ===== Algoritmus Cohen-Sutherland (ACS) ===== Optimalizace naivního algoritmu: vyloučíme zbytečný výpočet průsečíků pomocí dělení – mnoho úseček leží vně okna, mnoho úseček uvnitř okna (rovnou je přijmeme nebo zamítneme). {{:mgr-szz:in-gra:acs.png|}} Pokud oba konce úsečky leží uvnitř okna (test oproti všem čtyřem stranám okna), úsečku triviálně přijmeme. Pokud oba konce úsečky leží ve vnější polorovině některé strany, úsečku triviálně odmítneme. Průniky polorovin označujeme binárně: {{:mgr-szz:in-gra:binarne.png|}} Polohu testujeme binárními operacemi podle polohy koncových bodů C_A a C_B: {{:mgr-szz:in-gra:binarne1.png|}} {{:mgr-szz:in-gra:binarne2.png|}} {{:mgr-szz:in-gra:binarne3.png|}} {{:mgr-szz:in-gra:binarne4.png|}} ==== Pseudokód ==== Vypočti binární kódy koncových bodů C_A, C_B. Je-li (CA and CB) != 0, celá úsečka leží vně okna, odmítni. Je-li (CA or CB) = 0, celá úsečka leží uvnitř okna, přijmi. Pro každou jedničku v (C_A or C_B) postupně ořezávej úsečku. např. pro Ymax počítej: X = X_A + (X_B - X_A) * (Y_max - Y_A ) / (Y_B - Y_A) Y = Y_max (A or B) = [X,Y], oprav kód C_A nebo C_B ===== ===== Nalezení průsečíku s oknem půlením intervalu (neefektivní). **Nejlepší algoritmus, pokud většinu úseček triviálně přijmeme / zamítneme** ===== Parametrické ořezávání ===== Reprezentace hran okna a testovaných úseček v parametrickém tvaru. Rozhodnutí o viditelných částech pomocí testu bodu úsečky násobenou normálou hranice okna. Podle znaménka leží bod uvnitř(-)/vně(+)/na hraně(0). {{:mgr-szz:in-gra:parametricky.png|}} ==== Algoritmus Cyrus-Beck (ACB) ==== Pro určení, která část leží kde (ne po pixelech úsečky, ale po částech). {{:mgr-szz:in-gra:acbpseudo.png|}} Výpočet t-průsečíků nenáročný. Výpočet (x,y) ořezaných bodů je proveden jen jednou. Neuvažuje triviální přijetí/odmítnutí => **nejlepší algoritmus, pokud se musí hodně ořezávat**. ==== algoritmus Liang-Barsky ==== Optimalizace Cyrus-Beck pro obdélníkové okno. Zjednodušení výpočtů pro normály: (-1, 0), (1, 0), (0, -1), (0, 1) Výběr konstantních bodů na hranách. Řešení pro t: - (x0 - xleft ) / (x1 - x0 ) (x0 - xright ) / -(x1 - x0 ) - (y0 - ybottom) / (y1 - y0 ) (y0 - ytop ) / -(y1 - y0 ) ===== Problémy ořezávání ===== ==== Posun ==== Úsečky jsou reprezentovány celočíselně – při ořezání se změní (zaokrouhlí se na jiný pixel). {{:mgr-szz:in-gra:problemorezu.png|}} Rozhodovací člen pro interpolátor je třeba vypočíst na základě průsečíku s hranicí, pak teprve rasterizovat. ==== Ořezávání n-úhelníků ==== Jestliže chceme kreslit pouze obrys n-úhelníku, pak stačí ořezávat hrany samostatně jako úsečky chceme-li vybarvovat vnitřek n-úhelníku, musíme oříznout speciálním algoritmem. {{:mgr-szz:in-gra:orezpolygonu.png|}} === Algoritmus Sutherland-Hodgman === Postupné ořezávání jednou hranou místo okna. Prakticky stačí otáčet souřadnice. {{:mgr-szz:in-gra:orezpolygonureseni.png|}} ====== Použité zdroje ====== doc. Ing. Přemysl Kršek, Ph.D., Ing. Michal Španěl : IZG - Základy počítačové grafiky, slajdy. 2008. Ústav počítačové grafiky a multimédií, Fakulta informačních technologií, Vysoké ucení technické. Brno. Josef Pelikán, Jiří Sochor : PB009 - Základy počítačové grafiky, slajdy. 2012. Fakulta informatiky, Masarykova Univerzita. Brno. Počítačová grafika, slajdy. Univerzita Pardubice. http://school.lynn.cz/grafika/prednasky/PG_2006_P04_Vyplnovani_4s.pdf [online].