Jana Dannhoferová Ústav informatiky, PEF MZLU

Počítačová grafika

Problém viditelnosti • nalezení těch objektů a jejich částí, které jsou viditelné z určitého místa • algoritmy pro řešení viditelnosti jsou vždy spjaty s konkrétní reprezentací prostorových objektů • metody určování viditelnosti: a) vektorové (liniové) • výstupem je soubor geometrických prvků (např. úseček) představujících viditelné části objektů • vyhodnocená data lze opakovaně vykreslovat v libovolném rozlišení • další výstup: soubor zakrytých částí objektů • technické výkresy (výstup např. na plotrech)

Viditelnost Jana Dannhoferová

([email protected])

HLE (Hidden Line Elimination) – alg., které vracejí pouze úsečky HSE (Hidden Surface Elimination) – alg., které vracejí plochy 2

Ústav informatiky, PEF MZLU

© J. Dannhoferová, Počítačová grafika

Problém viditelnosti

Třídy algoritmů viditelnosti

b) rastrové • pracují pouze v rastru • výsledkem je obraz složený z pixelů, které obsahují barvu odpovídající vybarvení viditelných ploch • v dnešní době převažují • výhody: • umožňují práci s barvou a jejími odstíny • dokáží vykreslit osvětlené a stínované plochy • poskytují přesvědčivý obraz prostorové scény • nevýhody: • pevný rozměr výsledného obrázku


• objektově orientované • rychlost výpočtu závisí na počtu objektů ve scéně • základem je porovnávání vzájemných poloh těles (případně jejich částí jako jsou plochy a hrany)

• „pro každý objekt zjisti, která jeho část je vidět“ • obrazově orientované • doba výpočtu závisí na počtu objektů a počtu pixelů rastru • základem jsou testy určující pro každý pixel obrazovky, která část promítnutého objektu je v tomto pixelu nejblíže pozorovateli (viditelná) • „pro každý pixel zjisti, který objekt je v něm vidět“ 3

Vlastnosti zobrazovaných dat

4


Určování viditelnosti

drátový model

přivrácené stěny

obrysové hrany

viditelné hrany

•počet ploch lze snížit vyloučením odvrácených stěn © J. Dannhoferová, Počítačová grafika

5


6

1

Liniové algoritmy viditelnosti 1. Rozděl hrany na zadní, obrysové a přední (zadními se nezabývej) 2. Vytvoř prázdný seznam V potenciálně viditelných hran 3. Pro všechny obrysové a přední hrany Hi dělej: a. Přidej hranu Hi do seznamu V potenciálně viditelných hran b. Pro vš. mnohostěny Mj dělej: I.

Pro A. B. C.

vš. Hrany Hk ze seznamu V dělej: Vyjmi hranu Hk ze seznamu V Testuj hranu Hk na zakrytí mnohostěnem Mj Pokud jsou na hraně nalezeny jeden nebo dva nezakryté úseky, zařaď úseky do seznamu V D. Pokud mnohostěn celou hranu zakrývá, dále se jí nezbývej

c. Vykresli všechny hrany ze seznamu V a vyprázdni jej 7


Rastrové algoritmy viditelnosti • rasterizace ploch je prováděna současně s řešením viditelnosti (na rozdíl od liniových algoritmů)

• paměť hloubky (z-buffer, depth-buffer) • nejznámější a nejefektivnější metoda • vyšší nároky na paměť, ale vysoká rychlost zpracování • standardní prostředek pro řešení viditelnosti u většiny grafických procesorů • tvoří dvourozměrné pole s rozměry totožnými s velikostí obrazu (obrazovkou) • každá položka paměti hloubky obsahuje souřadnici z toho bodu, který leží nejblíže pozorovateli a jehož průmět leží v odpovídajícím pixelu v rastru

Z-buffer

Z-buffer

• kreslení do bufferu – kreslení do video-RAM

1. inicializace • vyplň obrazovou paměť barvou pozadí • vyplň Z-buffer hodnotou - („nekonečno“) 2. zápis všech objektů do Z-bufferu • každou plochu rozlož na pixely a pro každý její pixel o souřadnicích [xi,yi] stanov hloubku zi • má-li zi větší hodnotu než položka [xi,yi] v Z-bufferu, pak: • obarvi pixel [xi,yi] v obrazové paměti barvou této plochy • položku [xi,yi] v paměti hloubky aktualizuj hodnotou zi

(rastrová tiskárna s bufferem)

• výhody: • každá plocha je zpracovávána pouze jednou • správné vykreslování nestandardních situací • není třeba třídit • vyplňování • jednoduchost výpočtů • pro každý pixel ukládám: • souřadnici z (paměť hloubky) • barvu (obrazová paměť – video-RAM) 9


Řádkový rozklad


10

Malířův algoritmus

• paměť hloubky je rozdělena na pruhy (řádky) • každá plocha je zpracovávána několikrát (nižší rychlost alg.) 1. Vyplň daný řádek v obrazové paměti barvou pozadí 2. Vyplň řádek hloubky hodnotou - 3. Každou plochu, která je protínána daným řádkem, rozlož na pixely a pro každý její pixel o souřadnici xi stanov hloubku zi 4. Je-li zi větší než položka xi v řádku hloubky, pak: a. obarvi pixel o souřadnici xi na odpovídajícím řádku v obrazové paměti barvou této plochy b. položku xi v řádku hloubky aktualizuj hodnotou zi © J. Dannhoferová, Počítačová grafika

8


11

• přímé vykreslování ploch na obrazovku v pořadí od nejvzdálenějších k nejbližším vůči pozorovateli • plochy bližší k pozorovateli jsou vykreslovány později (překryjí zadní plochy)

• viditelnost vyřešena přirozeným způsobem • řešení viditelnosti je převedeno na úlohu seřazení ploch podle vzdálenosti od pozorovatele • předpoklad: rovinné plochy se navzájem neprotínají! • fáze: • třídění podle hloubky • odstranění nejasností v pořadí • řádkový rozklad a zobrazení © J. Dannhoferová, Počítačová grafika

12

2



1. Třídění podle hloubky • plochy setřídíme podle minimální souřadnice z vzestupně (tj. odzadu dopředu) • vytvoříme tak vstupní seznam S

2. Kontrola pořadí • ze začátku seznamu S vybereme plochu P (kandidáta na kresbu) • proti P otestujeme ostatní plochy, které s ní mohou kolidovat (právě testovanou plochu označíme Q)

x,y

x,y Q1

2 1

P

3

• P = aktivní plocha

(je podrobována několika testům zakrývání vzhledem k ostatním plochám)

Q2

5 4

z

z 13


Q4

Q3

14




2. A) Minimax test • nejprve provedeme nejjednodušší test – v průmětu porovnáme obdélníky opsané oběma plochám • jestliže nemají společný bod, testování Q končí • jinak pokračujeme dalším testem P a Q

2. B) P versus rovina Q • testujeme, zda plocha P neleží celá za rovinnou danou ploškou Q • v kladném případě testování Q končí • jinak pokračujeme dalším testem P a Q x,y

y

P

P

Q

x 15


Q

z

16




2. C) Q versus rovina P • testujeme, zda plocha Q neleží celá před rovinou danou plochou P • v kladném případě testování Q končí • jinak pokračujeme dalším testem P a Q

2. D) Úplný test v průmětu • pokud předchozí testy neuspěly, musíme provést úplný test ploch P a Q v průmětu • je potřeba zjistit, zda není některá část Q překrytá ploškou P • v takovém případě by nešlo nakreslit P před Q!

x,y

y

P P

Q

Q

x

z © J. Dannhoferová, Počítačová grafika

17


18

3

Malířův algoritmus 2. • • • •


D) Úplný test v průmětu testujeme proti sobě všechny hrany P a Q najdeme-li průsečíky, porovnáme v nich souřadnice z je-li vždy P za Q, test Q končí jinak nelze P nakreslit před Q!

2. D) Úplný test v průmětu • jestliže neexistuje průsečík hran P a Q, je třeba ještě zkontrolovat, zda neleží ploška P celá uvnitř Q nebo naopak • v takovém případě opět porovnáme souřadnice z

y

y Q

zP
P

Q

zP
x 19



20


2. Změna pořadí • jestliže nelze z nějakého důvodu nakreslit P před Q, zkusíme přesunout plošku Q na začátek seznamu S (před P) • pro Q budeme opět provádět všechny testy 2. fáze (jak jsme je popsali s plochou P)

• testy nového kandidáta Q proti P už byly z velké části provedeny, stačí pouze doplnit obrácené testy B a C • kvůli zacyklení se musí každý kandidát označit zvláštním příznakem

2. Zacyklení • jestliže je testován některý kandidát podruhé, došlo k zacyklení • cyklus lze odstranit rozstřižením některé plochy (pořadí A1 B C A2)

3. Vykreslení kandidáta P © J. Dannhoferová, Počítačová grafika

21

Dělení obrazovky


22

Dělení obrazovky

• předpoklad: složitý problém lze rozdělit na řadu menších, snáze řešitelných • jak má být vyplněno dané obdélníkové okno obrazovky? • při vyplňování okna mohou nastat následující možnosti: • pokud do okna nezasahuje žádný objekt, zůstává vyplněné barvou pozadí • pokud do okna zasahuje právě jedna plocha, bude tato plocha uvnitř okna vyplněna, zbytek získá barvu pozadí • pokud do okna zasahuje více ploch, ale plocha nejbližší pozorovateli je zcela překrývá, pak je okno vyplněno barvou této plochy • pokud okno obsahuje komplikovanější část scény, pak je rozděleno na čtyři menší okna a algoritmus je opakován pro každé z nich © J. Dannhoferová, Počítačová grafika

23


24

4

Literatura • Beneš, B., Felkel, P., Sochor, J., Žára, J. Moderní počítačová grafika. Computer Press: Brno, 2004. • Beneš, B., Sochor, J., Žára, J. Algoritmy počítačové grafiky. ČVUT: Praha, 1996. • Sochor, J.: Základy počítačové grafiky. FI MU: Brno, 2001.


25

5

Jana Dannhoferová Ústav informatiky, PEF MZLU

Recommend Documents