Hlavní navigace

Grafika v UNIXu - základní 3D algoritmy

Stanislav Brabec 18. 3. 2002

3D grafika je stále populárnější nejen ve hrách, ale i v nejrůznějších vizualizačních aplikacích, strojírenstvím počínaje a kadeřnickými salony konče. V našem seriálu se však nebudeme zabývat 3D aplikacemi, ale používanými grafickými algoritmy. Jejich znalost nám pomůže orientovat se v obrovské škále možností vizualizačních programů.

3D na 2D

Každý 3D program musí řešit převod třírozměrné „reality“ do dvourozměrných souřadnic obrazovky. K tomu existuje množství nejrůznějších algoritmů, podle účelu a úhlu záběru. Každý z nich zkresluje, a každý z nich zkresluje jinak.

Pravoúhlé rovnoběžné zobrazení, používané často pro strojírenské výkresy, je velmi jednoduché při vykreslování pravoúhlých objektů orientovaných podle os. Při jiné orientaci však dává paradoxně zkreslené objekty.

Axonometrie je další jednoduché zobrazení, které zachovává přímky. V rovnoběžné axonometrii je definován směr všech tří os a poměr zkrácení délek při vynášení. Pozice se vypočte sečtením hodnot pro jednotlivé souřadnice. Protože toto zobrazení nemá perspektivu, existuje též úběžná axonometrie. V ní jsou navíc definovány tři úběžné body (nekonečné hodnoty na osách) – k nim se sbíhají rovnoběžky ve směrech os. Alespoň dva úběžné body bývají většinou mimo obrázek. Nevýhodou axonometrií je zkreslení při velkém úhlu záběru. Pravoúhlé rovnoběžné zobrazení je tedy speciálním případem rovnoběžné axonometrie.

Další velkou skupinu tvoří systémy sférického mapování. Nejdříve se vypočítají úhlové souřadnice všech objektů z místa pozorovatele – objekty se namapují na povrch jednotkové koule – a z této koule se pak mapují na rovinu. Jejich popisy najdeme v každé učebnici kartografie. Mapování obecně nezachovává přímky.

Nejběžnějším mapováním je azimutální zobrazení. Při něm se mapuje povrch koule na tečnou plochu. Podle zachování určité veličiny se dělí na stejnoploché, stejnoúhlé a se zachováním délky na polednících (při udávání vdálenosti od pólu).

Dalšími zajímavými azimutálními zobrazeními jsou projektivní zobrazení. Nejjednodušším z nich je přímková projekce. V ní se obraz z koule promítá přímkami na rovinu, a proto je omezená na zobrazovací úhly silně pod 180°. Projekce mají velký význam, neboť se jedná o přirozené zobrazovací metody většiny fotoaparátů (různé objektivy mohou používat různé typy projekce). V 3D grafice patří vedle axonometrie mezi nejběžnější.

S méně obvyklými válcovými mapováními se setkáváme většinou pouze u panoramatických obrázků. Z kartografie známe ještě další typy mapování (kuželové, polykonické), ale ty se v 3D grafice prakticky nepoužívají.

Popis tělesa

V 3D grafice potřebujeme znát třírozměrný popis tělesa. Jakákoliv metoda musí poskytnout odpověď na několik důležitých otázek: zda zvolený paprsek těleso protne, v jakém bodě, jaký je zde normálový směr (směr kolmý k rovině povrchu tělesa), případně jakou barvu bude těleso mít v tomto bodě.

Popíšeme si dvě nejčastěji používané metody – analytický popis a triangulaci.

Analytický popis je výhodný pro matematicky snadno popsatelná tělesa (rovina, koule, elipsoid, paraboloid, hyperboloid, grafy funkcí). Těleso je tak určeno parametrickou rovnicí, jejímž řešením zjistíme, zda paprsek světla těleso protne, kde, a jaký je zde normálový směr.

Nejjednodušším objektem pro analytický popis je trojúhelník. Z toho vyšla myšlenka triangulace. Povrch celého tělesa se popíše, jako by byl složen z malých k sobě přisedlých trojúhelníků. To můžeme aplikovat na libovolné těleso. Velikost trojúhelníků zvolíme podle požadované přesnosti.

Mnoho programů obě metody kombinuje – běžná tělesa se triangulují, ale např. kouli lze zadat analyticky (kvalitní triangulace koule totiž vyžaduje desítky trojúhelníků).

V praxi se setkáme i s dalšími modifikacemi těchto algoritmů – např. pro vizualizaci grafů bude výhodné použít aproximaci čtyřúhelníkovou­ sítí.

Viditelnost objektů

Pokud kreslíme tělesa plnou barvou, musíme řešit problém viditelnosti. Nejjednodušším řešením je malířův algoritmus. Tělesa seřadíme podle vzdálenosti; pak kreslíme vše, od nejvzdálenějších objektů k nejbližším, kterými ty vzdálené prostě překryjeme. Malířův algoritmus selhává, pokud se objekty navzájem protínají.

Existuje i obrácené použití této metody. Při něm postupujeme od nejbližších objektů a na zobrazovanou plochu vyneseme značky „jak daleko je vidět“. Pokud zjistíme, že objekt není vidět, vůbec se jím nezabýváme.

Také odvrácené části tělesa jsou pro nás neviditelné. K tomu, aby bylo možné snadno rozpoznat, který trojúhelník není vidět, se provede drobná úprava – trojúhelníky se orientují – stanoví se pevné pořadí vrcholů, a to zároveň udává orientaci normálového směru ven z tělesa. Pokud normála směřuje směrem od pozorovatele, je jasné, že se trojúhelník nachází na odlehlé straně povrchu.

Metody zobrazování

Největší vliv na výsledek má ovšem metoda zobrazování. V 3D grafice jich máme k dispozici širokou škálu – od těch nejrychlejších až po fotorealistické.

Nejjednodušší metodou zobrazování je zcela jistě drátový model. Vznikne vykreslením všech úseček triangulace.

Jen o trochu složitější je zakrytý drátový model. Vykresluje se podobně jako drátový model, z kreslení jsou ovšem vyřazeny neviditelné části.

Další skupinou metod jsou metody stínování. Tyto metody již dokáží tělesa obarvit. Pro nápodobu skutečnosti používají bodové světelné zdroje, jejichž světlo se na tělesech rozptyluje. Jejich společným kladem je vysoká rychlost zobrazování, záporem pak plastikově matný vzhled všech objektů. Metoda neumí zobrazit zrcadlový obraz a lom světla. Ve své základní verzi neumí pracovat ani se stíny, ale lze je do algoritmu doplnit.

Základní verzí stínování pro triangulované modely je konstantní stínování. V této metodě se každý z trojúhelníků obarví konstantní barvou. Metoda je ze všech nejrychlejší, s výbornou možností hardwarového zrychlení. Při zobrazení oblých předmětů je však velmi nepřesvědčivá (ostrý přechod odstínů na hranách trojúhelníků vnímá oko jako falešnou hranu).

K „zaoblení“ tvarů je proto nutné použít sofistikovanější metody – například Gouraudovo stínování. Normálový vektor (a tím i barvu) ve vrcholech trojúhelníku získáme jako průměr normálových vektorů všech tří sbíhajících se trojúhelníků. Nyní stačí obraz trojúhelníku na obrazovce vyplnit odpovídajícím barevným přechodem, což lze učinit i s významnou pomocí hardwarových akcelerátorů.

Tabulka č. 260

drátový model
Drátový model.

konstantní stínování
Konstantní stínování.

hladké stínování
A po vyhlazení.

koule Naproti tomu Phongovo stínování z normálových vektorů ve vrcholech aproximuje normálové vektory ve všech bodech trojúhelníku, a teprve z nich odvozuje osvětlení daného bodu. Jde o náročnější postup, výsledkem je však hladší vzhled zejména poblíž obrysu tělesa.

Aby jakékoliv stínování fungovalo v náš prospěch, musíme ke každé hraně triangulace přiřadit informaci, zda se jedná o „falešnou“ hranu, kterou je třeba vyhladit, nebo o skutečnou hranu. V tomto případě se trojúhelníky „za hranou“ do hodnot pro vrcholy nezapočítávají.

V příštím dílu si přiblížíme dokonalejší metody pro fotorealistické zobrazování.

Obrázky byly vytvořeny pomocí demonstrančních programů z knihovny GLUT. Š A. K. Peters, Mark Kilgard; David G. Yu.

Našli jste v článku chybu?

22. 3. 2002 22:42

mako (neregistrovaný)

Ano - Moderni pocitacova grafika - (kolega) Zara, Benes, Felkel, Computer Press, 1998, ISBN 80-7226-049-9... Ovsem pokud nechcete utratit ctyri stovky a dostat se k vetsine popsanych algoritmu, podivejte se po skriptech CVUT FEL - Algoritmy pocitacove grafiky a Vizualizace - vetsina textu v knize MPG pochazi z techto skript...

20. 3. 2002 19:30

Stanislav Brabec (neregistrovaný)

V seriálu jsem se snažil o slovní popis algoritmů.
Přesný popis 3D algoritmů vyžaduje znalosti vektorové matematiky, u barev zase maticové algebry.
Velmi zajímavá je:
Václav Skala: Světlo, barvy a barevné systémy v počítačové grafice, Academia, Praha 1993
Algoritmy pro 3D jsou zde popsány matematicky.
Ale v knihkupectví jsem kdysi viděl i další.






DigiZone.cz: ČRo rozšiřuje DAB do Berouna

ČRo rozšiřuje DAB do Berouna

Podnikatel.cz: EET zvládneme, budou horší zákony

EET zvládneme, budou horší zákony

Podnikatel.cz: EET: Totálně nezvládli metodologii projektu

EET: Totálně nezvládli metodologii projektu

Měšec.cz: U levneELEKTRO.cz už reklamaci nevyřídíte

U levneELEKTRO.cz už reklamaci nevyřídíte

Podnikatel.cz: Přehledná titulka, průvodci, responzivita

Přehledná titulka, průvodci, responzivita

120na80.cz: Rakovina oka. Jak ji poznáte?

Rakovina oka. Jak ji poznáte?

Podnikatel.cz: 1. den EET? Problémy s pokladnami

1. den EET? Problémy s pokladnami

Vitalia.cz: Láska na vozíku: Přitažliví jsme pro tzv. pečovatelky

Láska na vozíku: Přitažliví jsme pro tzv. pečovatelky

Vitalia.cz: Tesco: Chudá rodina si koupí levné polské kuře

Tesco: Chudá rodina si koupí levné polské kuře

Lupa.cz: Avast po spojení s AVG propustí 700 lidí

Avast po spojení s AVG propustí 700 lidí

Měšec.cz: Kdy vám stát dá na stěhování 50 000 Kč?

Kdy vám stát dá na stěhování 50 000 Kč?

Měšec.cz: Zdravotní a sociální pojištění 2017: Připlatíte

Zdravotní a sociální pojištění 2017: Připlatíte

Podnikatel.cz: Víme první výsledky doby odezvy #EET

Víme první výsledky doby odezvy #EET

Podnikatel.cz: Prodává přes internet. Kdy platí zdravotko?

Prodává přes internet. Kdy platí zdravotko?

Měšec.cz: Finančním poradcům hrozí vracení provizí

Finančním poradcům hrozí vracení provizí

Podnikatel.cz: Babiše přesvědčila 89letá podnikatelka?!

Babiše přesvědčila 89letá podnikatelka?!

Vitalia.cz: Jsou čajové sáčky toxické?

Jsou čajové sáčky toxické?

Vitalia.cz: To není kašel! Správná diagnóza zachrání život

To není kašel! Správná diagnóza zachrání život

DigiZone.cz: Sony KD-55XD8005 s Android 6.0

Sony KD-55XD8005 s Android 6.0

DigiZone.cz: Recenze Westworld: zavraždit a...

Recenze Westworld: zavraždit a...