12 - Transformace, reprezentace a zobrazení 3D objektů

• jsou jedny z nejčetnějších operací v současné počítačové grafice
• můžeme je chápat jako změnu pozice vrcholů v aktuálním souřadnicovém systému nebo jako změnu souřadnicového systému
• lineární transformace - dají se skládat (otočení + posunutí + zkosení + zvětšení je možné provést v různém pořadí se stejným efektem)
• kartézská soustava souřadnic
  • je taková soustava souřadnic, u které jsou souřadné osy vzájemně kolmé a protínají se v jednom bodě - počátku soustavy souřadnic
  1. pravotočivá - normální, co používáme
  2. levotočivá - osa x a y je přehozená
• homogenní souřadnice
  • homogenní souřadnice bodu v 3D s kartézskými souřadnicemi [x,y,z] je uspořádána čtveřice [X,Y,Z,w] pro kterou platí:
    1. x = X/w
    2. y = Y/w
    3. z = Z/w.
    4. w = váha bodu
       • lineární transformace: w = 1
       • vektory v´ = (x,y,z) reprezentujeme trojicí (x,y,z,0)
  • bod je svými homogenními souřadnicemi určen jednoznačně
  • jsou zavedeny kvůli jednotné manipulaci se všemi transformačními maticemi, protože v případě kartézských souřadnic by jsme u posunutí použili sčítání a u ostatních operací zase násobení ⇒ takto všude použijeme násobení matic, tj. jednotný způsob (ulehčí implementaci)
  •  bod, který chceme transformovat, má matici P(x, y, z, w), kde x, y, z jsou jeho souřadnice, w je 1 pokud je to bod, 0 pokud je to vektor.
    
•  transformační matice ve 3D
  • matice 4*4
  • tuto obecnou transformační matici získáme násobením dílčích základních transformačních matic
  • násobení matic musí být z pravé strany a v přesném pořadí provádění jednotlivých transformací

• pro posun v opačném směru budou koeficienty d záporné

• pro zmenšení se místo S použije 1/S.

•  střed otáčení v počátku souřadného systému.

• vynásobení matic

•  základní metody
  1. Konstruktivní geometrie - CSG
  2. Šablonování (translační, rotační, potahování)
  3. Dekompoziční modely
  4. Hraniční reprezentace
  5. Implicitní plochy - potenciální pole elementárních částic
•  požadavky na modely:
  • obecnost (popis co nejrozsáhlejší třídy objektů)
  • úplnost (úplně popisuje daný objekt)
  • jednoznačnost (lze vyhodnotit pouze jedním způsobem)
  • unikátnost, jedinečnost (jednomu tělesu odpovídá jeden model)
  • přesnost (popisu objektu)
  • regulérnost (nemožnost vytvořit nereálnou reprezentaci)
  • konzistence vůči vybraným operacím tělesa stejné třídy
  • kompaktnost (malá paměťová náročnost)
  • možnost efektivního zpracování (možnost efektivní implementace operací s tělesem)
• typy objektů:
  1. manifold - hrana sdílí jen 2 stěny, vyrobitelný
  2. nonmanifold - nevyrobitelný objekt
•  Eulerovy rovnice
  • slouží pro kontrolu topologie objektu ⇒ platí pro manifold (hrana spojuje 2 vrcholy, ve vrcholu maximálně 3 hrany, stěny se neprotínají)
• regularizované množinové operace
  • skládání objektů
  • nesmí měnit topologickou dimenzi objektu
  • výsledek je vždy těleso
  • -*, ∪*, ∩*
• projekce
  • 3D objekty zobrazujeme na 2D výstupu
  • projekční paprsek promítá body na průmětnu
  • dochází ke ztrátě informace
  1. perspektivní (středová)
     • je zvolený střed projekce
     • velikost průmětu nezávisí na vzdálenosti od průmětny
     • užití: virtuální realita, architektura, hry
     • kavalírská projekce - všechny osy mají stejné měřítko
     • kabinetní projekce - osa Z je v měřítku 1/2 vůči ostatním osám
  2. paralelní (rovnoběžná)
     •  zachovává rovnoběžnost hran ⇒ paprsky kolmé na průmětnu ⇒ střed projekce je v nekonečnu
     • čím blíže středu promítání tím menší objekt
     • užití: technická schémata
     • promítání na zakřivenou průmětnu - např.rybí oko (úsečky se projektují na křivky, potřeba projektovat všechny rastrované body)
     •  obrázek: paralelní promítnutí do roviny XY (zanedbáme Z)
       

•  objekt je popsán stromem ze:
  1. 3D primitiv (listy stromu)
  2. transformací (zvětšení, otočení, atd… 3D primitiv)
  3. booleovských operací (uzly stromu)
• možnost vzniku singularit (regularizované operace)
• pro každé nové operace probíhá regenerace stromu
• možnost parametrizace operací ve stromu - parametrické modelování (CAD/CAM)
• nejsou informace o povrchu ⇒ převod na polygonální model (B-rep)
• oktalový strom
  • rozdělení prostoru CSG modelu oktalovým stromem (octree) ⇒ CSG strom rozdělený (tzv. prořezaný) na podstromy
  • urychlení regenerace stromu při lokálních operacích, urychlení zobrazování CSG modelu
• strojní inženýrství, architektura

• pohyb křivky, plochy nebo tělesa po zvolené trajektorii
• může být součástí CSG operací (primitiva tvořená šablonováním)
• využívá se invariance spline křivek a ploch vůči lineárním transformacím

1. pohyb po přímce (obrázek)
2. potahování s proměnlivou profilovou křivkou
3. posun po obecné křivce
4. rotační - NURBS křivky

• diskrétní popis objektu dekompozicí na elementární objemové jednotky (krychle, hranoly) - voxely (Volumetric Pixel)
• nese informace o hraniční struktuře x hraniční modely
• geologie, medicína, strojírenství
• uložení dat:
  1. 3D pole diskrétních hodnot - rychlý přístup, ale paměťově náročné
  2. oktalový strom - vhodné pro malou hustotu dat - rekurzivní dělení
  3. subvoxely - kombinace dvou předchozích
• vykreslení pomocí Marching cubes
  • nalezení a polygonizace isoplochy procházející objemem

• B-rep (Boundary Representation)
• objekt popsán prostřednictvím svého povrchu - hranice
• objekty definovány pomocí vrcholů (body), hran (úsečky, křivky) a stěn (polygony, spline křivky)

1. drátový model
   •  popis pomocí vrcholů a hran ⇒ málo topologických informací ⇒ nejednoznačnost
   • pro rychlé zobrazení
2. polygonální model
   • objekt definován pomocí vrcholů, hran, stěn (trojúhelníky == polygony)
   • jednoznačný popis objektu, malá přesnost (lineární aproximace povrchu)
   • hw podpora zobrazení
3. okřídlená hrana
   • 3 lineární seznamy - vrcholů, hran, stěn
   • definuje sousední vrcholy, hrany ohraničující stěnu, sousední stěny
   • zpracováním lze získat normály ve vrcholech
     
4. hraniční spline model
   •  jako polygonální ale místo polygonů jsou spline plochy
   • pro zobrazení se často na polygonální převádí
   • LOD - Level of Detail míra přesnosti podle vzdálenosti, eliminace vrcholů nebo hran

• plocha je definována bázovou maticí (polynomy) a sítí řídících bodů (matice)

_ Bikubické plochy - interpolační, analogie Fergusonových křivek, matice 4×4 řídících bodů, spojitost plátů

1. Beziérové plochy - aproximační, analogie Beziérových křivek, matice 4×4 řídících bodů, spojitost plátů
2. NURBS plochy - aproximační, analogie NURBS křivek, matice 4×4 řídících bodů

•  modelování pomocí kostry kolem které je potenciální pole - určuje povrch objektu
• povrch objektu je v místě, kde je intenzita pole rovna nule

•  drátový model - těžko se určuje viditelnost ⇒ nevíme, jak jsou myšleny stěny
• viditelné plochy jsou přivrácené k pozorovateli, přivrácené části mají normálu směrem k pozorovateli
• orientace normály vůči vektoru pohledu:
  • skalární součin
  • hodnota z normály po pohledové transformaci
• viditelnost hran:
  • hrana mezi viditelnými plochami je viditelná
  • hrana mezi neviditelnými plochami je neviditelná
  • hrana mezi viditelnou a neviditelnou plochou je obrysová
• předzpracování scény:
  • vyřazení odvrácených částí
  • vyřazení zakrytých částí

• algoritmy viditelnosti:
  1. vektorové - výsledkem je soubor viditelných a neviditelných hran
     • např. Robertsův algoritmus - dělení potenciálně viditelných hran na úseky kde se mění viditelnost
  2. rastrové - rastrový výsledek - obraz viditelných ploch, stínováni, barva osvětlení
     • např. Malířův algoritmus - vykreslování nejprve vzdálených objektů, pak bližších
• algoritmy viditelnosti (jiné dělení):
  • objektové - pro každý objekt scény hledá viditelné části - složitost n²
  • obrazové - pro každý pixel obrazu hledá viditelný objekt - složitost n*p
  • komplexní - scéna je zpracovávána celá najednou. Měkké stíny. Komplexní řešení.

•  klasický vektorový algoritmus
• dělení potenciálně viditelných hran na úseky, kde se mění viditelnost
• uděláme průsečíky s obrysovými hranami a testujeme viditelnost jejich úseků podle vzdálenosti průsečíků a zakrytí

•  vizualizace 3D funkcí v grafu
• vykreslení řezů v rovině XZ a YZ od předu dozadu (ve směru pohledu)
• vykreslení úseků řezu, které jsou mimo oblast horního a dolního horizontu

•  rastrový algoritmus
• vykreslování objektů odzadu dopředu ⇒ seřazení podle vzdálenosti

•  rastrový objektový algoritmus
• dělení okna na čtvrtiny, dokud není vyplněn jedním objektem
  1. žádný objekt v okně ⇒ pozadí
  2. jeden objekt v okně ⇒ vykreslit
  3. více objektů v okně, ale nejbližší překrývá ostatní ⇒ vykreslit
  4. jinak ⇒ dělit

• rastrový obrazový algoritmus
• ukládá informace o hloubce objektu (Z souřadnice nejbližších bodů)
• rychlý algoritmus, snadná implementace v HW
• každá plocha je zpracovávána pouze jednou ⇒ fronta
• využívá předzpracování scény
• využívá color buffer

• sledování paprsků - z kamery se vypouštějí paprsky, sleduje se jejich pohyb, zlom a odraz
• výpočetně hodně náročné - použití u statických scén, filmu ne u her, kdy je potřeba rychlost vykreslování
• je nereálné sledovat všechny paprsky ⇒ Backtracking ⇒ zpětné sledování ⇒ procházíme rekurzivně postupně, jak se paprsek odráží

• rastrový obrazový algoritmus řešení viditelnosti
• Ray tracing prvního stupně
• vrhání paprsků z místa pozorovatele, pozorují se jen primární paprsky, bez odrazů
• urychlení oproti Ray tracingu (snížíme počet paprsků, urychlíme výpočet průsečíků, používáme svazky paprsků, rozdělíme na více částí)
• použití: přímé zobrazování CSG modelů, vizualizace voxel modelů
• nevýhody:
  • ostré stíny
  • bodové zdroje světla
  • zrcadla (lesklé plochy) sice odrážejí okolí, ale neodráží světlo do okolí ⇒ nejsou sekundárními zdroji světla

• vystřelování „radiozity“ z plošek, které mají nejvíce energie
• ozářené plošky se stávají sekundárními zdroji světla
• rekurzivní opakování dokud se energie neutlumí
• nejkomplexnější řešení viditelnosti
• trvá nejdéle ⇒ je třeba respektovat fyzikální vlastnosti světla

• Empirický model
• Počítá pouze s difuzí
• Ideální difuze, půlkulový odraz do všech směrů
• Intenzita difuze závisí na úhlu dopadu paprsku na povrch (kosínové pravidlo)

• Empirický model
• K difuzi přidává reflexi
• Ideální reflexe, odraz je symetrický podle normály
• Intenzita reflexe závisí na směru odrazu a směru k pozorovateli
• Ambientní složka světla IA, světelný šum, rozptýlené světelné pozadí

• Fyzikálně založený model
• Realistické zobrazení (Ray-tracing)
• Specializace na jednotlivé efekty nebo materiály
• Výpočetně náročnější

• Pro každý polygon se osvětlovacím modelem vyhodnotí středový pixel
• Celý polygon má pak konstantní barvu
• Nezohledňuje se zakřivení povrchu objektů

• Pro polygony se osvětlovacím modelem vyhodnotí pixely ve vrcholech
• Při rasterizaci polygonu probíhá interpolace barvy
• Zohledňuje se zakřivení povrchu objektů

• Při rasterizaci probíhá interpolace normál z vrcholů
• Osvětlovací model se počítá pro každý pixel
• Zohledňuje se zakřivení povrchu objektů
• Velmi kvalitní výsledky, realistické zobrazení

12
Celé jméno	OK	!!!
Jirka Hynek
	1