PV112 Programování grafických aplikací
Jaro 2017
Výukový materiál
3. přednáška: Rasterizace, Homogenní souřadnice, Transformace
Rasterizace
Nejdříve se znovu vrátíme k nejdražší části blokového diagramu OpenGL a to rasterizaci.
Rasterizace je vlastně konverze grafických primitiv do dvoudimenzionálních obrázků.
Proces rasterizace má dvě části. V první zjistíme, které obdélníky (pixely) mřížky okna jsou
obsazeny. Ve druhé části pak každému obdélníku přiřadíme příslušnou hodnotu barvy a
hloubky. Výsledek je poté poslán dále ke zpracování fragment shaderem.
Princip rasterizace
Na tomto obrázku vidíte ilustraci principu rasterizačního procesu, kdy dochází k promítnutí
3D trojúhelníku do rastru framebufferu. Přitom zásadní je pozice pozorovatele vůči
zobrazovanému trojúhelníku.
Veškeré vstupní objekty jsou zpracovány rasterizační jednotkou a vznikají fragmenty.
Než jsou hodnoty skutečně uloženy do framebufferu, je nad fragmenty provedena sada
operací, které mohou změnit vlastnosti nebo i zcela odstranit dané fragmenty z vykreslování.
Tyto změny probíhají ve fragment shaderu, kde probíhá například texturování a výpočet
mlhy. Dále zde mohou probíhat operace jako discard pro výpočet průhlednosti, stencil test,
depth test (odstranění skrytých částí). Pokud některý z „povolených“ (enabled) testů selže,
může to způsobit ukončení další zpracování daného čtverce fragmentu. Pokud testy projdou,
následuje blending (míchání), dithering (roztřesení) a logické operace. Nakonec je
zpracovaný fragment vykreslen do příslušného bufferu.
Fragment
Fragment je vlastně zlomek objektu v mřížce společně s přiřazenými parametry, jako je
například barva nebo hloubka (hodnota Z). Tyto parametry se nazývají „fragment’s
associated data“.
Fragment je definován dolním levým rohem, který leží v mřížce celočíselných souřadnic.
Operace v rasterizačním procesu rovněž pracují se středem fragmentu, který je posunut o ½
od levého dolního rohu.
Rasterizace bodů
Rasterizace bodů produkuje fragment pro každý pixel framebufferu, jehož střed leží uvnitř
čtverce se středem v bodu [xw,yw], jehož délka strany je shodná s aktuální velikostí bodu.
Defaultně je bod rasterizován ořezáním jeho xw a yw souřadnic na hodnoty typu integer.
Rasterizace bodů je řízena funkcí void glPointsize(float size), kde size určuje velikost
vykreslovaného bodu. Defaultní hodnota je 1.0. Hodnota menší nebo rovna nule způsobí
chybu INVALID_VALUE. Velikost bodu lze nastavit alternativně i povolením změny velikosti
bodu pomocí glEnable(GL_PROGRAM_POINT_SIZE) a poté zavoláním gl_Pointsize = size, kde
size je opět požadovaná velikost vykreslovaného bodu.
Při rasterizaci bodu o velikosti větší než 1.0 je skutečná šířka bodu určena zaokrouhlením
zadané šířky na nejbližší hodnotu typu integer a dále uzavřením na maximální možnou
hodnotu šířky bodu (liší se podle dané implementace).
Jestliže je výsledek zaokrouhlení 0, pak se výsledek bere jako hodnota 1. Když je výsledek
lichý, pak je střed fragmentu (x,y) = (⌊xw⌋ + ½ , ⌊yw⌋ + ½) spočten z pozice [xw,yw] vrcholu a
čtvercová mřížka liché šířky se středem [x,y] definuje středy rasterizovaných fragmentů (jinak
řečeno, středy fragmentů leží v tzv. half-integer souřadném systému). Je-li výsledek sudý, je
středový bod definován jako (x,y) = (⌊xw + ½⌋ , ⌊yw + ½⌋).
Na obrázku je znázorněn příklad rasterizace „velkých“ bodů, kde křížky znázorňují středy
fragmentů vytvořené rasterizací pro jakýkoliv bod ležící v tečkované oblasti. Tečkovaná
oblast leží v prostoru half-integer souřadnic.
Rasterizace úseček
Rasterizace úsečky je opět řízena šířkou úsečky. Rasterizace úsečky začíná určením typu
úsečky – jestli je tzv. x-hlavní (x-major) nebo y-hlavní (y-major). Toto rozdělení závisí na
sklonu úsečky. x-hlavní úsečka má sklon v rozmezí uzavřeného intervalu [-1, 1]. Všechny
ostatní úsečky jsou y-hlavní.
OpenGL využívá tzv. „diamond-exit“ pravidlo pro určení fragmentů, které vznikají rasterizací
úsečky. Pro každý fragment f se středem [xf,yf] definujeme region tvaru diamantu, který je
průsečíkem čtyř polorovin:
Rf = {(x,y) | |x – xf| + |y – yf| < ½}
Každá úsečka začínající v bodě pa a končící v bodě pb vytváří takové fragmenty f, pro které
úsečka protíná Rf.
Pro generování úseček je použit Bressenhamův algoritmus s jednou modifikací – takto
vytvořená úsečka je tzv. „polootevřená“, což znamená, že koncový fragment (odpovídající pb)
není vykreslen. To odpovídá situaci, kdy vykreslujeme sadu na sebe navazujících úseček.
Tímto přístupem vykreslíme koncové body pouze jednou (klasický Bressenham vykreslí v
tomto případě koncové body dvakrát).
Určení interpolace barev a hloubky:
aktuální bod na úsečce
počáteční bod
koncový bod
kde je skalární součin
je druhá mocnina vektorové délky
t je v intervalu [0, 1] a t = 0 pro a, t = 1 pro b
Homogenní souřadnice
Homogenní souřadnice mají přirozené aplikace v počítačové grafice. Vytváří základ pro
projektivní geometrii, která je široce použita pro projekci třírozměrných scén do
dvourozměrné roviny obrazu. Homogenní souřadnice také umožňují jednotné použití
běžných grafických transformací a operací.
Homogenní souřadnice umožňují reprezentovat všechny grafické operace pomocí násobení
matic. Rotaci a scaling ve 2D můžeme reprezentovat násobení maticí 2x2, pro translaci
musíme zavést třetí, homogenní souřadnici.
Důvodem jejich použití je skutečnost, že v klasickém Euklidovském nebo Kartézském
prostoru se nemohou dvě rovnoběžky protnout. Pokud se ale dostaneme do prostoru
projektivní roviny (viz obrázek), vidíme, že se zvětšující se vzdáleností od pozorovatele se dvě
 yxp ,
 aa yxa ,
 bb yxb ,
  
2
ab
abap
t



        abaaba yyyyxxxxabap 
   222
abab yyxxab 
rovnoběžné přímky protínají v nekonečnu. Problém definice tohoto jevu byl vyřešen
zavedením homogenních souřadnic.
Homogenní souřadnice umožňují reprezentovat n-dimenzionální bod n+1 hodnotami. Pro
vytvoření 2D homogenních souřadnic stačí k souřadnicím (x, y) přidat třetí proměnnou w.
Tedy bod v kartézských souřadnicích (X,Y) odpovídá bodu (x, y, w) v homogenních
souřadnicích. Převod z homogenních souřadnic na kartézské probíhá následovně:
X = x/w
Y = y/w
Jako příklad si uveďme bod (1, 2), který odpovídá homogenním souřadnicím (1, 2, 1). Pokud
se tento bod pohybuje směrem k nekonečnu, v kartézských souřadnicích bychom dostali
nesmyslné vyjádření (∞, ∞). V homogenních souřadnicích takovýto bod vyjádříme
jednoduše jako (1, 2, 0).
Definice homogenních souřadnic
Nejdříve začneme s příklady v dvourozměrném prostoru a nabyté znalosti využijeme k
vysvětlení homogenních souřadnic ve třech dimenzích.
Definice 1:
Jako první zavedl v projektivní geometrii homogenních souřadnice August Ferdinand Möbius
(1790 - 1868). Mějme pevně daný trojúhelník v rovině. Množina homogenních souřadnic pro
bod p je definována jako hmotnosti přiřazené vrcholům trojúhelníka takové, že p se stane
těžištěm trojúhelníka.
Bod p je spočten jako (waa, wbb, wcc), kde wa, wb a wc se nazývají barycentrické souřadnice a
platí wa + wb + wc = 1.
Definice 2:
Další definici homogenních souřadnic vytvořil německý matematik a fyzik Julius Plücker
(1801 - 1868). Ve své definici pracuje se vzdálenostmi z daného bodu ke hranám pevného
trojúhelníka.
Plückerovy souřadnice:
n+1 souřadnic reprezentuje n-dimenzionální bod.
Jednou z nejdůležitějších vlastností tohoto systému je jeho invariance vůči scalingu (změně
velikosti). Scaling Möbiových vah ani velikosti Plückerových souřadnic nezmění pozici bodu p.
To si ukážeme na následujícím příkladě:
Převod homogenních souřadnic (x, y, w) na kartézské (X, Y) probíhá pomocí již známého
převodu
X = x/w
Y = y/w
Vezmeme-li například souřadnice:
(1, 2, 3) = (1/3, 2/3)
(2, 4, 6) = (2/6, 4/6) = (1/3, 2/3)
(4, 8, 12) = (4/12, 8/12) = (1/3, 2/3)
A obecně tedy
(1a, 2a, 3a) = (1a/3a, 2a/3a) = (1/3, 2/3)
Z toho je vidět, že všechny zmíněné body odpovídají stejnému bodu v euklidovských
souřadnicích. Proto jsou nazývány „homogenní“. Jinak řečeno, homogenní souřadnice jsou
invariantní vůči scalingu.
Projektivní rovina
Plücker si uvědomil tuto invarianci homogenních souřadnic vůči scalingu a dále považoval
homogenní bod s hodnotou w = 0 odpovídající bodu v normální rovině, který je nekonečně
daleko.
Normální rovina doplněná o body v nekonečnu se nazývá projektivní rovina. V projektivní
rovině se libovolné dvě přímky protínají (tedy i ty rovnoběžné).
p =  cba lll
Projektivní rovina nemůže být reprezentována v konečných Euklidovských souřadnicích,
může však být reprezentována v homogenních souřadnicích, což je základní důvod jejího
použití v projektivní geometrii. Projektivní geometrie je ve skutečnosti geometrií "snímání".
Projektivní rovinu můžeme popsat pomocí všech přímek a rovin procházejících skrz daný bod
s, který nazýváme střed projekce. Jestliže jsou tyto přímky a roviny protnuty rovinou P, která
neprochází skrz s, pak každý bod (nebo přímka na P) může být asociován s přímkou (nebo
rovinou) procházející skrz s.
Podle konvence paralelní přímky protínají P v ideálním (nekonečně vzdáleném) bodě.
Pak projektivní rovina ρ2 obsahuje současně ideální body a ideální přímky.
Dvojrozměrný projektivní prostor
Každé z následujících tvrzení definuje dvojrozměrný projektivní prostor ρ2:
1) Množina všech tříd ekvivalence uspořádaných trojic nenulových vektorů v ε3, kde
ekvivalence je vzájemná úměra dvou vektorů.
2) Množina všech přímek procházejících skrz počátek ε3.
3) Množina všech dvojic protilehlých bodů S2 jednotkové koule v ε3.
Prakticky to znamená:
Homogenní souřadnice reprezentují projektivní rovinu ρ2 zobrazením každého Euklidovského
bodu (x’, y’) ∈ ε2 na [x y w] ∈ ε3, w<>0, který je členem třídy ekvivalence bodů v ρ2. Zobrazení
je dosaženo ekvivalencí x’ ≈ x/w, y’ ≈ y/w.
• Skalární násobení vytváří nového člena dané třídy ekvivalence.
• Jestliže jsou vybráni zástupci z průniku s rovinou w=1, pak vektorové sčítání dvou
bodů v ρ2 vypočte zástupce středového bodu mezi těmito dvěma vektory. Například:
[1, 2, 1] + [3, 4, 1] = [4, 6, 2] ≈ (2, 3)
• Protože homogenní body reprezentují projekci, mohou také reprezentovat body
v nekonečnu.
Důležitý a praktický aspekt systému homogenních souřadnic je unifikace translace, scalingu a
rotace geometrických objektů.
Motivace pro transformace
Nyní si na jednoduchém příkladě ukážeme, proč jsou důležité v OpenGL matice a k čemu se
používají. Jsou na nich založeny veškeré transformace s objekty ve scéně. Představme si
situaci, že chceme vykreslit čtyři trojúhelníky jako na obrázku.
Trojúhelníky mají různou pozici a orientaci. Jedním z možných řešení je samozřejmě uložit si
souřadnice vrcholů všech trojúhelníků a použít postup, jaký jsme si ukazovali na minulé
přednášce. Ale co kdybychom měli ve scéně trojúhelníků například 20? V tom případě
bychom museli do našeho pole uložit 60 pozic vrcholů. A obecně objekty bývají mnohem
složitější. Pokud tedy chceme zkopírovat daný objekt na mnoho různých pozic na obrazovce
a v různých orientacích, potřebujeme lepší způsob než zadávání všech vrcholů do pole.
Tento problém lze vyřešit za použití maticové algebry. Místo uložení daného objektů N-krát
jej uložíme pouze jednou a použijeme geometrické transformace posunutí, rotace a
škálování, abychom jej umístili na požadovaným způsobem (na požadovanou pozici, správně
orotovaný a se správnou velikostí). Obrázek znázorňuje prinicip těchto transformací na
jednoduchém příkladě čtverce.
Tyto jednoduché transformace můžeme skládat a tím dosáhneme složitějších efektů (jako
například na obrázku).
Jak tedy dosáhneme těchto transformací v OpenGL? Jako obvykle přesuneme souřadnice
objektu do OpenGL bufferu a ve vertex shaderu vynásobíme tyto souřadnice transformační
maticí.
Výklad teorie maticové algebry je mimo rozsah předmětu, nicméně je nutné ji znát. Zde
uvedeme pouze některé důležité vlastnosti maticového násobení, protože právě násobení
matic nás bude v OpenGL zajímat nejvíc.
• Maticové násobení není komutativní, záleží tedy na pořadí matic při jejich násobení.
• Násobení je asociativní, můžeme tedy operaci provádět po různých částech (ale při
zachování pořadí matic).
• Pokud transponujeme výslednou matici vzniklou vynásobením dvou matic, pak
výsledek je stejný jako kdybychom nejdříve matice transponovali a pak je vynásobili,
ale v opačném pořadí.
• Podobné pravidlo platí i pro inverzní matice.
• Násobení maticí identity nemění původní matici.
Modelovací matice (model matrix)
Jak již bylo řečeno, násobení matic není komutativní, proto je naprosto zásadní pořadí, v
jakém transformace aplikujeme na objekt. Z matematického pohledu se transformace
provádí postupným násobením souřadnic objektu základními transformačními maticemi.
Alternativně se dá proces transformace provést i takovým způsobem, že si nejdříve
připravíme matici složenou ze základních transformací (jejich vynásobením) a poté tuto
finální transformační matici aplikovat na objekt (jeho vrcholy ve formě sloupcového vektoru,
v rovnici označené jako v).
kde
Aby byla transformace korektní, je třeba ji aplikovat na všechny vrcholy objektu.
Matice M, kterou jsme v předchozí rovnici násobili každý vrchol objektu, se v OpenGL nazývá
modelovací matice (model matrix). Místo toho, abychom do pipeline posílali více
transformačních matic, pošleme pouze matici M a tím dojde k zefektivnění.
Základní (affinní) transformace
Mezi základní transformace patří posun, rotace a scaling. Při posunu dojde k vynásobení
vektoru v pozic vrcholu maticí daného tvaru, což způsobí posun v o hodnotu Tx v ose x, Ty v
ose y a Tz v ose z.
Pro rotaci máme tři různé matice lišící se tím, podle které osy rotujeme. Například matice Rz
orotuje vektor v o alpha stupňů okolo osy z proti směru hodinových ručiček.
Matice škálování pak naškáluje vektor v hodnotou Sx ve směru osy x, Sy ve směru osy y a Sz ve
směru osy z.
Všimněte si, že matice jsou o rozměrech 4x4. Vektor v je tedy vyjádřen v homogenních
souřadnicích.
Uveďme si příklad rotace vrcholu na pozici x = 0.5 a y = 0.5 o 90° okolo osy z.
Následně provedeme ještě posun o 0.1 v ose x, -0.2 v ose y a 0.5 v ose z.
Tyto transformace jsme provedli postupným násobením s vektorem reprezentujícím vrchol.
Totéž lze dosáhnout tím, že nejdříve sestavíme modelovací matici složenou z individuálních
transformací, kterou následně v jediném kroku aplikujeme na vrchol.
Jak již bylo řečeno, pořadí prováděných transformací je velmi důležité, protože násobení
matic není obecně komutativní. Transformace můžeme chápat dvěma různými způsoby:
Prvním přístupem je globální souřadný systém (the grand fixed coordinate system), druhý
přístup je použití lokálního souřadného systému (local coordinate systém tied to object).
Pokud máme v globálním souřadném systému matici C=NML a aplikujeme ji na vrchol v,
transformovaný vrchol v’ vypadá následovně: v’ = N(M(Lv)). Vrchol v je tedy nejprve
transformován transformací L! Tedy poslední volaná transformace je ta, která se jako první
aplikuje na vrcholy.
Oproti tomu v lokálním souřadném systému se s operacemi počítá v přirozeném pořadí, jak
jdou za sebou. Tedy v předchozím příkladě se na vrchol v nejdříve aplikuje transformace N.
S tímto konceptem pracuje i OpenGL, tedy v pořadí, v jakém jsou zadány transformační
matice, se aplikují na jednotlivé vrcholy.
Pro porovnání globálního a lokálního přístupu si uvedeme následující obrázek:
Globální
Lokální
Pohledová matice (view matrix)
Pohledová matice (view matrix) v OpenGL kontroluje způsob náhledu na scénu. Pohledová
matice je velikosti 4x4 a je jednoznačně určena třemi parametry a nastavuje se funkcí
LookAt, která je přítomna v některé z nadstavbových knihoven pro zvolený programovací
jazyk (více na cvičeních). Tyto parametry jsou pozice pozorovatele (eye), bod, do kterého se
kamera dívá (center) a směr nahoru pozorovatele (up)(definující orientaci pozorovatele).
V OpenGL je pozorovatel implicitně umístěn na ose z a směr pohledu je k počátku souřadné
soustavy. Vektor definující orientaci pohledu (up vektor) směřuje v kladném směru osy y.
Pohledovou matici V aplikujeme na modelovací matici a tu pak na vektor reprezentující
vrchol. Rovnice tedy definuje aplikování pohledové a modelovací matice na vrchol.
Projekční matice (projection matrix)
V OpenGL má objekt implicitně stále stejnou velikost, bez ohledu na pozici kamery. To ale
odporuje reálnému světu, kdy se objekt blíže pozorovateli (kameře) jeví větší. Dalším
problémem defaultního nastavení OpenGL je skutečnost, že pro vykreslení objektu na
obrazovku je nutné tento objekt umístit dovnitř krychle o rozměrech
[-1,+1] x [-1,+1] x [-1,+1]. Cokoliv mimo tento rozsah bude ořezáno. Tento defaultní ořezávací
objem je možné virtuálně zvětšit nebo zmenšit pomocí projekční matice. Tento objem může
mít podobu komolého jehlanu (v případě perspektivní projekce) nebo kvádru (v případě
ortografické projekce). Ortografická projekce nemění velikost objektu s ohledem na pozici
kamery. Toto chování je vhodné u CAD systémů či 2D her.
Perspektivní projekce
Matice perspektivní projekce je často specifikována čtyřmi parametry. Parametr fov určuje
pohledový úhel, aspect je poměr výšky a šířky pohledového jehlanu a parametry Near a Far
určují pozici přední a zadní ořezávací roviny. Vztah parametrů je následující:
Matice perspektivní projekce vypadá následujícím způsobem. Jednotlivé parametry
představují hranice ořezávacího objemu.
Perspektivní projekce slouží pro přirozeně vypadající promítnutí 3D objektu na 2D
obrazovku. Perspektivní projekce je nezbytná pro zobrazení jednoduchých grafických
primitiv, jako například polygonů či úseček.
Vykreslování objektů v ε3 je prováděno přirozeně použitím jejich projekce do ε2.
Pohled zboku:
Bod obrazu je vypočten z bodu objektu pomocí podobnosti trojúhelníků.
V okamžiku, kdy se D blíží k nekonečnu, se blíží k 0 a transformované body se
stanou nekonečně vzdálenými.
Matice perspektivní projekce
Vzniká násobením matice pro perspektivu a pro projekci.
Projekce Perspektiva Perspektivní projekce
Perspektivní transformace
Díky lineární závislosti třetího a čtvrtého sloupce matice ztrácí perspektivní projekce
hloubkovou informaci.
Zavedením nenulového výrazu, např. -1, do třetího sloupce neovlivní x’a y’, ale z’ bude
Smysl tohoto dalšího výrazu je komprese Euklidovského prostoru na .
      DzzyxzDDzyDzxDzyx /1/,/,/,, '''
 ''
, yx  zyx ,,
zDyy //'

zDxx //'

   zyDzxDyx /,/, ''

     
 

Dzzyx
DzyDzxDDzyDzxDzyx
/
1//,/,/,, '''
Dw /1'

zDD /
  ,1z  Dz ,0'


























10/100
0100
0010
0001
z
y
x
D






































0/100
0100
0010
0001
0/100
1100
0010
0001
1000
000
0010
0001
DD
D

























10/100
0100
0010
0001
)',','(
z
y
x
D
zyx
Ortografická projekce
Matice ortografické projekce vypadá následujícím způsobem. Parametry right, left, far, near,
top, bottom reprezentují pozice ořezávacích rovin, které definují pohledový kvádr.


























10/100
1100
0010
0001
z
y
x
D