REPREZENTACE 3D SCÉNY

REPREZENTACE 3D SCÉNY

JANA ŠTANCLOVÁ [email protected] Obrázky (popř. slajdy) převzaty od RNDr. Josef Pelikán, CSc., KSVI MFF UK

Obsah

•

reprezentace 3D scény – objemové reprezentace • výčtové reprezentace – buněčný model – oktantový strom

• CSG reprezentace

– povrchové reprezentace • „drátový model“ • VHS(T) model

•

2/40

předzpracování 3D-dat

Jana Štanclová, [email protected]

Metody reprezentace 3D scény

METODY REPREZENTACE 3D SCÉNY

3/40



•

1. objemové reprezentace – přímé informace o vnitřních objemech těles – snadný test „bod × těleso“ – složitější zobrazování

•

2. povrchové reprezentace – přímé informace o povrchu těles • hrany, stěny, ....

– poměrně snadné zobrazování – obtížnější test „bod × těleso“ • proč??

4/40



•

1. objemové reprezentace – přímé informace o vnitřních objemech těles – snadný test „bod × těleso“ – složitější zobrazování

•

2. povrchové reprezentace – přímé informace o povrchu těles • hrany, stěny, ....

– poměrně snadné zobrazování – obtížnější test „bod × těleso“ • tělesa nemusí mít objem

5/40


1. Objemové reprezentace

•

výčtové reprezentace – přímé vyčíslení obsazeného prostoru – metody • buněčný model • oktantový strom

•

CSG reprezentace – silná a přesná metoda • elementární tělesa • geometrické transformace • množinové operace

– obtížnější zobrazování

6/40


Buněčný model

•

těleso – pole k×l×m voxelů

•

voxel

m

– volume element – jednobitová varianta • 0 ... nic • 1 ... těleso

l

– vícebitová varianta • 0 ... nic • n > 0 ... těleso číslo n

7/40

k


Zobrazení buněčného modelu

•

kreslení odzadu → dopředu – přivrácené stěny voxelů – stěny na povrchu těles • stěna mezi prázdným voxelem (a=0) a voxelem tělesa (a>0)

→ nevýhoda ??

8/40


Zobrazení buněčného modelu

•

kreslení odzadu → dopředu – přivrácené stěny voxelů – stěny na povrchu těles • stěna mezi prázdným voxelem (a=0) a voxelem tělesa (a>0)

→ vícenásobné překreslování scény

9/40


Oktantový strom („octree“)

•

těleso = sjednocení prostorových buněk různé velikosti – 3D analogie kvadrantového stromu

10/40



•

těleso = sjednocení prostorových buněk různé velikosti – 3D analogie kvadrantového stromu – vnitřek krychle nehomogenní → rozdělen na ?? částí

11/40



•

těleso = sjednocení prostorových buněk různé velikosti – 3D analogie kvadrantového stromu – vnitřek krychle nehomogenní → rozdělen na 8 částí • v případě nutnosti dělení až do voxelů

– úspora paměti oproti buněčnému modelu

•

kreslení odzadu → dopředu – přivrácené stěny krychlí – stěny na povrchu těles → vícenásobné překreslování scény

12/40


CSG reprezentace

•

CSG = Constructive Solid Geometry – elementární geometrická tělesa • ??

– množinové operace • ??

– geometrické transformace • ??

13/40


CSG reprezentace

•

CSG = Constructive Solid Geometry – elementární geometrická tělesa • snadno definovatelná a vyčíslitelná • kvádr, poloprostor, hranol, koule, válec, kužel, ...

– množinové operace • vznik složitějších těles z elementárních těles • sjednocení, průnik, rozdíl, ....

– geometrické transformace • modifikace elementárních i složitějších těles • posunutí, otočení, zkosení, zmenšení/zvětšení, ...

– obtížnější zobrazování scény metoda vrhání paprsku

14/40


CSG strom

•

CSG strom – výpočet/vytváření scény z elementárních těles

– listy • tělesa s aplikovanými geometrickými transformacemi (posunutí, otočení, zmenšení/zvětšení, ...)

15/40


CSG strom - příklad

•

16/40

vytvořit CSG strom pro těleso


CSG strom - příklad

•

17/40

vytvořit CSG strom pro těleso


Test „bod × CSG strom“

•

„bod × CSG strom“ – zda bod A leží uvnitř tělesa – ??

18/40



•

„bod × CSG strom“ – zda bod A leží uvnitř tělesa – průchod CSG stromem – 1. testy nad elementárními tělesy v listech • testy „bod × elementární těleso“ snadné

– 2. pomocí množinových operací se zjistí, zda bod i ve výsledném tělese • množinové operace → booleovské ekvivalenty • →  • → 

19/40



20/40


Zobrazování CSG reprezentace

•

převod do povrchové reprezentace – elementární těleso → převod do povrchové reprezentace • rutina, která převede elementární těleso na mnohostěn

– provedení množinových operací nad mnohostěny • omezená přesnost

•

vykreslení pomocí algoritmu vrhání paprsku – přesné zobrazování v rastrovém prostředí • pixelová přesnost

– výpočetně náročné

21/40


2. Povrchové reprezentace

•

přímé informace o povrchu těles (hrany, stěny, ...) – složitý test „bod uvnitř tělesa?“ – snadnější zobrazování

•

povrchové reprezentace – „drátový model“ • pseudo-povrchová reprezentace • pouze vrcholy a hrany těles • nepoužitelné pro výpočet viditelnosti

– VHS(T) reprezentace • kompletní topologická informace • seznamy vrcholů, hran, stěn (a těles)

22/40


Povrchové reprezentace VHS(T)

•

kompletní topologická informace – seznamy vrcholů, hran, stěn (a těles)

23/40


Okřídlená hrana

•

okřídlená hrana („winged edge“) – redundantní informace – pro rychlé vyhledávání sousedních objektů • test „bod leží na hraně či ne“

– pro přidání okřídlených hran do reprezentace tělesa → těleso musí splňovat podmínku 2-manifold • v žádném bodě (kromě vrcholů tělesa) se nesmí stýkat 3 a více plochy

24/40


Okřídlená hrana

•

záznam pro každou hranu – – – –

25/40

koncové vrcholy stěny, kterým hrana náleží následník a předchůdce hrany v těchto stěnách orientace hrany v těchto stěnách


Eulerovy zákony

•

jednoduchý polyedr (bez děr) ?? kde V ... počet vrcholů H ... počet hran S ... počet stěn

26/40


Eulerovy zákony

•

jednoduchý polyedr (bez děr) V–H+S=2 kde V ... počet vrcholů H ... počet hran S ... počet stěn

27/40


Eulerovy zákony

•

jednoduchý polyedr (bez děr) V–H+S=2 kde V ... počet vrcholů H ... počet hran S ... počet stěn

•

zobecněný vzorec (povoluje díry) V – H + S – D = 2 (T – G) kde D ... počet děr ve stěnách T ... počet těles G ... počet děr procházejících celým tělesem

28/40


Eulerovy zákony

•

příklad 1. ověření platnosti zákonu pro těleso V=? H=? S=? D=? T=? G=?

29/40


Eulerovy zákony

•

příklad 1. ověření platnosti zákonu pro těleso V = 16 H = 24 S = 10 = (6 + 4) D=2 T=1 G=1 V – H + S – D = 2 (T – G) → 16 – 24 + 10 – 2 = 2 (1 – 1)

30/40


Eulerovy zákony

•

příklad 2. ověření platnosti zákonu pro těleso V = 16 H = 24 S = 11 = (6 + 4 + 1) D=1 T=1 G=0 V – H + S – D = 2 (T – G) → 16 – 24 + 11 – 1 = 2 (1 – 0)

31/40


Předzpracování 3D dat

PŘEDZPRACOVÁNÍ 3D DAT

32/40


Předzpracování dat

•

snížení počtu zpracováváných rovinných ploch – vyloučení stěn odvrácených od pozorovatele • vždy zakryty jinýmy plochami • jejich odstranění neovlivní viditelnost dalších objektů

•

klasifikace stěn – odvrácená • ??

– přivrácená • ??

33/40



•

snížení počtu zpracováváných rovinných ploch – vyloučení stěn odvrácených od pozorovatele • vždy zakryty jinýmy plochami • jejich odstranění neovlivní viditelnost dalších objektů

•

klasifikace stěn – odvrácená stěna • ostrý úhel normály odvrácené stěny se směrem pohledu → kladný skalární součin normálového vektoru stěny a směru pohledu pozorovatele

– přivrácená stěna • záporný skalární součin normálového vektoru stěny a směru pohledu pozorovatele

34/40



•

klasifikace hran – zadní hrana • ??

– přední hrana • ??

– obrysová hrana • ??

35/40



•

klasifikace hran – zadní hrana • hrana incidující 2 odvrácenými stěnami → neviditelná hrana

– přední hrana • hrana sdílená 2 přivrácenými stěnami → viditelná hrana

– obrysová hrana • hrana svíraná přivrácenou a odvrácenou stěnou → může značit změnu viditelnosti → může být viditelná

36/40



37/40



•

jediné konvexní těleso – vidět všechny přední a obrysové hrany

•

nekonvexní těleso nebo skupiny těles – nutnost testovat vzájemné zákryty přivrácených stěn

vykresleny všechny hrany

38/40

vykresleny přivrácené stěny



•


•



39/40

vykresleny jen obrysové hrany



•


•



40/40

celková viditelnost


REPREZENTACE 3D SCÉNY

Recommend Documents