Modely prostorových těles

1

2

3 úrovně pohledu na modely svět - fyzikální objekty nemůžeme postihnout jejich složitost a mikroskopické detaily

Modely prostorových těles

matematické objekty vhodná idealizace fyzikálních objektů, intuitivně odpovídá nejvyšší úrovni našeho poznání reálného světa

© 1997 Josef Pelikán, MFF UK Praha © 2007 Jiří Sochor, FI MU Brno

reprezentace (datové modely) přiřazení datové reprezentace pro vybranou třídu matematických objektů, vhodná pro manipulaci (počítačové zpracování)

http://www.fi.muni.cz/~sochor/ PB009: Základy počítačové grafiky, 17.4.2007

© J.Sochor, FI MU Brno

PB009: Základy počítačové grafiky, 17.4.2007

3

Modelování těles (solid modeling)

4

Požadavky na reprezentaci těles

důraz

je kladen na tvorbu úplných reprezentací fyzických prostorových objektů úplná reprezentace umožňuje řešit libovolný geometrický problém algoritmicky (bez zásahu uživatele modelovacího a zobrazovacího systému)




široká

doména jednoznačnost (úplnost) unikátnost přesnost nemožnost vytvořit chybnou reprezentaci snadnost vytvoření platné reprezentace uzavřenost vůči vybraným operacím kompaktnost efektivní algoritmy PB009: Základy počítačové grafiky, 17.4.2007


5

Těleso, plochy, hrany, vrcholy

6

Drátové modely jednoznačná interpretace ?




7

Drátové modely a „modelování“


8

Modelovací postupy primitivní tělesa, transformace a booleovské operace s okamžitým zpracováním dtto s odloženým zpracováním - CSG strom Eulerovy operátory - „úprava beztvarého jádra topologicky korektními operacemi lokální tvarování těles globální deformace těles lokální deformace těles





9

Modely reprezentace 3D scén

Objemové reprezentace

objemové reprezentace – přímé informace o vnitřních objemech těles – snadný test “bod×těleso” (leží daný bod uvnitř tělesa?), zobrazování může být obtížnější – používají se též jako pomocné datové struktury pro rychlé vyhledávání

výčtové reprezentace – přímé vyčíslení obsazeného prostoru (diskrétní reprezentace - omezená přesnost) – používají se hlavně jako pomocné datové struktury pro rychlé vyhledávání – buněčný model, oktalový strom

povrchové reprezentace – přímé informace o povrchu těles (hrany, stěny) – obtížnější test “bod×těleso” (tělesa vůbec nemusí mít vnitřní objem), poměrně snadné zobrazování PB009: Základy počítačové grafiky, 17.4.2007

10


CSG reprezentace – velice silná a přesná metoda (elementární tělesa, geometrické transformace, množinové operace) – obtížnější zobrazování (vrhání paprsku) PB009: Základy počítačové grafiky, 17.4.2007

11

Buněčný model


12

Buněčný model - příklad

voxel “volume element”

pole k×l×m voxelů jednobitová varianta: 0 - nic, 1 - těleso vícebitová varianta: 0 - nic, n > 0 - těleso číslo n PB009: Základy počítačové grafiky, 17.4.2007




13

Buněčný model - příklad

14

Voxelová data – běžné úlohy nastavení přední roviny ořezání (výběr vrstvy dat) pohledové transformace množinové operace nad modelem osvětlení kontrukce izoploch separace oblastí (např. orgánů …)




15

Volume based modeling


16

Visible human project

Aplikace:

visible human project snímky řezů mrtvoly muže – každý řez je pole voxelů – celé tělo je popsáno sadou volumetrických dat





17

Oktantový model

18

Oktantový strom (octree) „oktalový strom“

y 2 66

62

63 67 65

64 4

7

3 3 7

1

x

5 5

z

F 0



F 1

F

F F .... F

F

60

61

F 7 F ....

F 67



19

Oktantový strom

CSG (Constructive Solid Geometry)

3D analogie kvadrantového stromu – je-li vnitřek krychle nehomogenní, rozdělí se na osm částí (dělí se až do úrovně voxelu) – úspora paměti proti buněčnému modelu Î kreslení odzadu-dopředu – pouze přivrácené stěny krychlí – pouze stěny na povrchu těles (stěny mezi 0 a >0) – několikanásobné překreslování některých pixelů PB009: Základy počítačové grafiky, 17.4.2007

20


elementární geometrická tělesa – snadno definovatelná a vyčíslitelná – kvádr, poloprostor, hranol, koule, válec, kužel,... množinové operace – kompozice složitějších těles z elementárních – sjednocení, průnik, rozdíl, .. geometrické transformace – modifikace elementárních i složitějších těles – (homogenní) maticové transformace PB009: Základy počítačové grafiky, 17.4.2007


21

CSG strom - modelování

22

CSG strom - transformace množinové operace T3

T1

∪

T3.T1

!!!

−

T2 výsledek

T4

T4.T1

elementární tělesa, primitiva

geometrické transformace PB009: Základy počítačové grafiky, 17.4.2007




23

Transformace v CSG stromu

Transformace v CSG stromu

význam (sémantika) transformace Ti – Ti mohou být uloženy v každé hraně CSG stromu – převod souřadnic ze soustavy podtělesa (podstromu, elementárního tělesa) do soustavy nadtělesa – “podtěleso transformuji pomocí Ti před tím, než ho přidám do nadtělesa” Î snadná transformace libovolného podstromu – změním pouze jednu matici -1

Î inverzní transformace Ti – pro vyčíslovací algoritmy (test bod×CSG, zobrazení) PB009: Základy počítačové grafiky, 17.4.2007

24


Î uložení transformací jen v listech – kumulované součiny (např. T3· T 2· T 1 nebo inverzní T1-1· T 2-1· T 3-1) – urychlení vyčíslovacích algoritmů (pro editaci je výhodnější distribuované uložení transformací) Î úsporné uložení elementárních těles – tělesa jsou uložena v normovaném tvaru, všechny změny se provádí geometrickými transformacemi – krychle (jednotková, vrchol v počátku), koule (jednotková, střed v počátku), válec (vodorovná podstava - jednotkový kruh, svislá osa, výška 1), ... PB009: Základy počítačové grafiky, 17.4.2007


25

Test „bod x CSG strom“

26

Test „bod x CSG strom“ bod A

leží daný bod A uvnitř tělesa? – někdy chceme zjistit i podtělesa obsahující bod A Î testy “bod×elementární těleso” jsou snadné! (především pro normované tvary těles) Î průchod CSG stromem – souřadnice bodu A se převádějí do souřadných soustav elementárních těles (inverzní transformace) – místo množinových operací se provádějí jejich booleovské ekvivalenty (∨ místo ∪, ∧ místo ∩, ...) PB009: Základy počítačové grafiky, 17.4.2007


bod A·

T1-1

T3

T1

−

T2 Uvnitř

∪

T4 bod A· T 2-1 Mimo

-1 -1 bod A· T 1-1· T3-1 bod A· T 1 · T4 Mimo Uvnitř PB009: Základy počítačové grafiky, 17.4.2007


27

Prořezávání CSG stromů úplný CSG strom A

Úprava CSG výrazů -

(A+B)-C B

28

+ A

-

B

C

+

podprostory s prořezanými CSG stromy

směr pohledu

A

A


.

D C

B

not A

C

. not D

not B

C

not D

((A+B)-C)-D=(A-C-D)+(B-C-D)=A.notC.notD+B.notC.notD

+ A

+

C

B

B

C




29

Zobrazování CSG reprezentace

30

CSG operace - záludnosti

Î převedení do povrchové reprezentace – pro každý druh elementárního tělesa: rutina převádějící těleso na mnohostěn – množinové operace nad mnohostěny (omezená přesnost - výsledek nemusí být správně ani v topologickém smyslu) Î vrhání paprsku (“Ray-casting”) – přesné zobrazování v rastrovém prostředí (pixelová přesnost) – výpočetně náročnější metoda PB009: Základy počítačové grafiky, 17.4.2007

Je nutné definovat tzv. „regularizované operace“




31

Povrchové reprezentace

32

Povrchová reprezentace VEFS V5

“drátový model” – pseudo-povrchová reprezentace – pouze vrcholy a hrany těles (nelze použít pro výpočet viditelnosti)

VEF(S) reprezentace – kompletní topologická informace: seznamy vrcholů (Vertex), hran (Edge), stěn (Face) a těles (Solid)

tělesa

E5 F2 E3 V3

F1 E2

E1

F2

F1

těleso S1

hrany E1

vrcholy

– redundantní informace pro rychlé vyhledávání sousedních objektů (hrany incidentní s vrcholem, ..) © J.Sochor, FI MU Brno

stěny

V2

“okřídlená hrana” (“winged-edge”) PB009: Základy počítačové grafiky, 17.4.2007

S1

V4 E 4 V1


E2

E3

E5

E4

x

x

x

x

x

y

y

y

y

y

z

z

z

z

z

V1

V2

V3

V4

V5 © J.Sochor, FI MU Brno

33

Polygonální geometrie - běžné úlohy

34

Nalezení hraničních hran

kreslení - průchod všemi trojúhelníky, pozice vrcholů zjištění vlastností objektů - nalezení všech hraničních hran - nalezení sousedního trojúhelníku změny sítě - vložení/zrušení trojúhelníku - přemístění vrchoku a přilehlých trojúhelníků - kolaps hran/rozdělení vrcholů




35

Přemístění vrcholu



36

Kolaps hrany




37

Rozdělení vrcholu

38

Geometrie a topologie Primitiva • vrcholy • hrany • stěny (polygony, často jen trojúhelníky) Topologické vztahy • vrcholy sousedící s hranou • hrany sousedící (připojené) ke stěně • vrcholy připojené ke stěně • …. Geometrie • pozice a tvar vrcholů, hran, stěn Topologie • konektivita/sousednost mezi různými vrcholy, hranami, stěnami




39

Topologicky identické sítě


40

Topologicky odlišné sítě • identická geometrie vrcholů • odlišná topologie a geometrie trojúhelníků/hran





41

Manifoldy

42

Okřídlená hrana (winged edge)

Def: 2-manifold: Pro každý povrchový bod existuje okolí, které je topologicky ekvivalentní s rovinou

V4 E2 F1 V3

E1 E4 V2

V1

E3 F2

V1

E5 V5

hrany

těleso S1

S1

tělesa PB009: Základy počítačové grafiky, 17.4.2007



43

Okřídlená hrana - (F,E,V)

x

x

y

y

y

z

z

z

V2

vrcholy

V3

V1

V2

F1

F2

E2

E5

E4

E3

+

-

E1 stěny

F1

F2 © J.Sochor, FI MU Brno

44

Okřídlená hrana

2    F , E ,V : F → E ⇒(V , F ,2 E )  


x

Příklad: průchod hranami levé stěny




45

46

Okřídlená hrana

Orientovaná okřídlená hrana

problém orientace: význam před/succ se mění podle pořadí procházení

Idea: vytvoření symetrické datové struktury uložení dvou polovičních hran místo jedné hrany poloviční hrany na sebe vzájemně ukazují





47


48

Orientovaná okřídlená hrana Komponenty:

Všechny hrany mají své předchůdce a následníky i v těch případech, že je to okrajová hrana

poloviční hrana

trojúhelník

vrchol





49



Alg: Ověření, zda vrchol je na hranici


50

Alg: Nalezení vrcholu na hranici




51


52

Eulerova rovnost

Alg: Výstup všech hran na okraji

Î pro jednoduchý polyedr (bez děr) platí vzorec

V-E+F=2 V - počet vrcholů, E - počet hran, F - počet stěn Î zobecněný vzorec (dovoluje díry):

V - E + F - L = 2 · (S - H) L - počet děr ve stěnách, S - počet těles, H - počet děr procházejících celým tělesem PB009: Základy počítačové grafiky, 17.4.2007




53

Euler.rovnost - jednoduchá tělesa

54

Eulerovy operátory Î konstrukce 2-manifoldu po krocích – v každém kroku je zajištěna platnost Eulerových vzorců (těleso je topologicky korektní) – ke každému operátoru existuje inverzní (snadná implementace příkazu “undo”) Î příklady Eulerových operátorů: Mvsf - “make vertex, solid, face”, Mev - “make edge, vertex”, Mef - “make edge, face”, Kef - “kill edge, face”, ...




55

Topologicky korektní model


56

Porovnání modelů

mvsf mev mev,mev mef mev,mev,mev,mev mef,mef,mef,mef mev mev,mev,mev,mef kemr mev,mev,mev,mev kfmrh – „kill face make ring hole“ PB009: Základy počítačové grafiky, 17.4.2007

mef,mef,mef,mef, kfmrh © J.Sochor, FI MU Brno



57

Další informace o tělese

Ukázka - formát OBJ

vrchol: – (normálový vektor pro spojité stínování) hrana: – příznak umělé hrany: pro reprezentaci děravých stěn nebo aproximaci křivých ploch sítí polygonů stěna: – barva – normálový vektor (stínování, přivrácená/odvrácená) těleso: – barva PB009: Základy počítačové grafiky, 17.4.2007

58


v v v v v v v v

0.0 0.0 0.0 0.0 1.0 1.0 1.0 1.0

0.0 0.0 1.0 1.0 0.0 0.0 1.0 1.0

0.0 1.0 0.0 1.0 0.0 1.0 0.0 1.0

vn 0.0 0.0 1.0 vn 0.0 0.0 -1.0 vn 0.0 1.0 0.0 vn 0.0 -1.0 0.0 vn 1.0 0.0 0.0 vn -1.0 0.0 0.0

f f f f f f f f f f f f

1//2 1//2 1//6 1//6 3//3 3//3 5//5 5//5 1//4 1//4 2//1 2//1

7//2 3//2 4//6 2//6 8//3 4//3 7//5 8//5 5//4 6//4 6//1 8//1

5//2 7//2 3//6 4//6 7//3 8//3 8//5 6//5 6//4 2//4 8//1 4//1


59

Modely a zobrazování



60

Modely a světlo - realita a iluze




Modely prostorových těles

Recommend Documents