Geometrie/Geometrické modelování
Model, který představuje navrhovaný reálný objekt (desku plošných spojů, strojnickou součástku,...), obsahuje v různých grafických systémech rozdílné typy údajů (geometrické, technologické,...).
Geometrické modelování zkoumá reálné objekty z hlediska geometrických vlastností. V následujících kapitolách se budeme zabývat právě problematikou geometrického modelování. Provedeme rozbor základních typů modelů, ukážeme si některé datové reprezentace modelů a nakonec popíšeme základní metody geometrického modelování.
Typy modelů
[editovat | editovat zdroj]V této části se zaměříme na základní klasifikaci jednotlivých typů geometrických modelů a provedeme rozbor výhod a nevýhod těchto typů při geometrickém modelování v rovině či prostoru. Zde jsou příklady základních typů modelů pro trojboký hranol:
- Drátěný model (Wireframe model) - je určen seznamem devíti hran.
- Hraniční model (Boundary model) - je určen seznamem pěti stěn.
- Objemový model (Volume, Solid model) - je určen velikostí stran podstavy a výškou.
Drátěné (hranové) modely
[editovat | editovat zdroj]Drátěné (Wireframe) modely jsou reprezentovány hranami objektu a skládají se z bodů, přímek a křivek. První wireframe systémy byly pouze dvou-dimenzionální. Používaly se především na návrhy tištěných spojů. Základními elementy těchto systémů byly body, přímky a oblouky některých kuželoseček. Vnitřní reprezentaci tvořil obvykle seznam úseček a oblouků.
V 70. letech byla wireframe reprezentace použita i pro modelování v prostoru. Zde však vznikaly dost závažné problémy:
- Možnost vytvoření nejednoznačných modelů.
- Možnost vytvoření nesmyslných modelů.
- Problém velkého počtu dat pro "drátěný" popis objektu.
Průmět drátěného modelu může mít více významů. Pokud u modelu vynecháme některé hrany, dostaneme nesmyslný (nonsense) model. U wireframe modelů je právě velice obtížné kontrolovat jejich logickou správnost.
Poslední nevýhodou je značné množství dat, které jsou nutné pro úplný popis objektu. Například obecně pro jednoznačné určení kvádru v prostoru stačí výška, šířka, hloubka a poloha. Wireframe model kvádru musí obsahovat souřadnice osmi vrcholů, musí být určeno dvanáct hran a ještě není model jednoznačný.
Hraniční (stěnové) modely
[editovat | editovat zdroj]Tato reprezentace (boundary reprezentace) patří k nejpoužívanějším typům při geometrickém popisu objektů. Hraniční model je tvořen seznamem stěn, které daný objekt ohraničují.
Například model trojbokého hranolu je určen pěti stěnami F1, F2, F3, F4, F5.
Obecně mohou být stěny rovinné i nerovinné (obecné). Rovinné stěny jsou určeny hraničními hranami stěny (lomenou čarou nebo rovinnými křivkami).
Nerovinné stěny mohou být jednak analytické plochy (známe přímo analytický předpis plochy) nebo plochy, které vzniknou některou interpolační nebo aproximační metodou (viz. modelování ploch).
Dříve se nejčastěji používala boundary reprezentace s rovinnými stěnami, které byly ohraničeny rovinnými n-úhelníky. Tato reprezentace se používala i pro objekt, jehož hranice byla tvořena obecnými (nerovinnými) plochami. Tyto plochy pak byly aproximovány vhodným počtem n-úhelníků a model daného objektu pak byl mnohostěnem.
Dnešní CAD systémy používají i boundary reprezentaci s obecnými plochami.
Objemové modely
[editovat | editovat zdroj]Objemový model (solid model, volume model) je model, který v sobě zahrnuje informace o části prostoru, kterou těleso zaujímá.
Pro popis objemového modelu se používají tyto způsoby:
- B - reprezentace s orientovanými stěnami - objemový model může být určen seznamem orientovaných stěn (B-reprezentace), které dané těleso ohraničují (stěny mohou být rovinné i nerovinné-viz hraniční modely). Stěna je orientována, jestliže můžeme jednoznačně určit, která strana stěny je vnitřní a která je vnější vzhledem k danému tělesu.
- CSG reprezentace - modelované těleso je reprezentováno binárním stromem, jehož vnitřní uzly představují množinové operace nebo geometrické transformace a listy představují elementární tělesa (primitiva). V poslední době se staly oblíbeními hybridní modely, které v sobě uchovávají současně CSG i B reprezentaci.
- Dekompoziční reprezentace - model je určen seznamem objemových elementů (např. krychliček), které dané těleso vyplňují - např. Octree reprezentace.
Datové reprezentace modelů
[editovat | editovat zdroj]Pro popis geometrických modelů používají různé grafické systémy různé datové reprezentace. Datová reprezentace modelu je určena jednak typem modelu (datová reprezentace drátěného modelu se bude lišit od datové reprezentace hraničního modelu) a dále je určena operacemi, které se s modelem provádí.
Datové reprezentace drátěných modelů
[editovat | editovat zdroj]E - reprezentace
[editovat | editovat zdroj]E - reprezentaci tvoří seznam hran, které obsahuje popisovaný objekt. Tuto reprezentaci můžeme použít pro tvorbu rovinného i prostorového modelu. Je výhodná pro rychlé zobrazení rovinného či prostorového modelu, není však vhodná pro řešení geometrických úloh prostorového modelu či řešení viditelnosti. Pro E-model trojbokého hranolu pak platí:
| E1 | x1y1z1 | x2y2z2 |
|---|---|---|
| E2 | x2y2z2 | x3y3z3 |
| E3 | x3y3z3 | x1y1z1 |
| E4 | x1y1z1 | x4y4z4 |
| E5 | x2y2z2 | x5y5z5 |
| E6 | x3y3z3 | x6y6z6 |
| E7 | x4y4z4 | x5y5z5 |
| E8 | x5y5z5 | x6y6z6 |
| E9 | x6y6z6 | x4y4z4 |
Modifikací této reprezentace dostaneme dva seznamy - seznam vrcholů a seznam hran. Touto modifikací oddělíme geometrické vlastnosti modelu (souřadnice vrcholů) od topologických (hrana je určena indexy odpovídajících vrcholů).
|
|
P - reprezentace
[editovat | editovat zdroj]P - reprezentace je tvořena seznamem lomených čar, které jsou určeny vrcholy modelovaného objektu. Danou reprezentaci budeme používat pro popis rovinného i prostorového modelu. Rovinný P-model použijeme pro popis rovinné scény, kterou tvoří rovinné křivky a lomené čáry. Prostorový P-model bude popisovat především drátěný model analytické plochy.
P-model je určen dvěma seznamy - seznamem vrcholů a seznamem polygonů. V seznamu vrcholů jsou uloženy jednotlivé lomené čáry (souřadnicemi vrcholů každé lomené čáry), seznam polygonů obsahuje ukazatel na první vrchol každé lomené čáry a počet vrcholů této čáry.
P - model trojbokého hranolu je tvořen těmito seznamy:
| V1 | V2 | V3 | V1 | V4 | V5 | V6 | V4 | V1 | V4 | V2 | V5 | V3 | V6 |
| P1 | P2 | P3 | P4 | P5 | |||||
| 1 | 4 | 5 | 4 | 9 | 2 | 11 | 2 | 13 | 2 |
Datové reprezentace hraničních modelů
[editovat | editovat zdroj]B - reprezentace
[editovat | editovat zdroj]B - reprezentace je tvořena seznamem stěn, které daný objekt ohraničují. B reprezentací můžeme popisovat nejen mnohostěny, ale i obecné analytické plochy.
V následujícím výkladu se zaměříme na popis datové reprezentace modelu, kterým je mnohostěn.
Ke standardním typům B-reprezentace patří popis objektu pomocí tří seznamů:
- seznam vrcholů,
- seznam hran,
- seznam stěn.
To znamená, že rozšiřuje modifikovanou E-reprezentaci o seznam stěn. Každá stěna je pro tento typ B-reprezentace určena ukazately na hrany v seznamu hran, které tuto stěnu ohraničují.
Trojboký hranol je pak určen těmito seznamy:
|
|
|
Jiný typ B-reprezentace popisuje každou stěnu přímo pomocí vrcholů hraničního polygonu. B-model trojbokého hranolu.
Datové reprezentace objemových modelů
[editovat | editovat zdroj]V této kapitole se zastavíme pouze u těch datových reprezentací, které určují objemový model pomocí B - reprezentace. Jak již bylo řečeno v kapitole Objemové modely, jedna z možností definování objemového modelu je pomocí orientovaných stěn, které ohraničují modelované těleso. U mnohostěnů je orientace stěny určena pořadím vrcholů, které určují hraniční polygon této stěny.
Platí obecná konvence, že pokud se díváme na dané těleso z vnější strany, pak vrcholy každé stěny jsou uspořádány proti směru pohybu hodinových ručiček.
Pro objemové modelování se v poslední době nejvíce používá datová reprezentace okřídlená hrana (Winged Edge).
Winged Edge reprezentace tělesa obsahuje tři seznamy - seznam stěn, seznam hran a seznam vrcholů.
Pro každou stěnu, hranu a vrchol přitom platí:
- Stěna obsahuje ukazatel na jednu z hran, které tuto stěnu ohraničují.
- Hrana nese nejvíce informací o topologii tělesa.
Každá hrana obsahuje ukazatele na:
- Počáteční vrchol hrany (V1),
- Koncový vrchol hrany (V2),
- Levou přilehlou hranu ve vrcholu V1 (E1),
- Pravou přilehlou hranu ve vrcholu V1 (E2),
- Levou přilehlou hranu ve vrcholu V2 (E3),
- Pravou přilehlou hranu ve vrcholu V2 (E4),
- Levou přilehlou stěnu (F1),
- Pravou přilehlou stěnu (F2).
Vrchol je nositelem geometrických informací, obsahuje souřadnice [x,y,z]. Z definice datové reprezentace okřídlené hrany je zřejmé, že má sice veliké nároky na kapacitu paměti, ale právě její topologie nám umožňuje rychle řešit problémy, které se vyskytují při objemovém modelování:
- Je dán vrchol, nalezni incidující stěny.
- Je dána hrana, nalezni koncové vrcholy této hrany.
- Je dána hrana, nalezni přilehlé stěny.
- Je dána stěna, nalezni obvodové vrcholy.
- Je dána stěna, nalezni obvodové hrany.
Eulerovy operace
[editovat | editovat zdroj]Úvod do topologie
[editovat | editovat zdroj]V geometrickém modelování se většina algoritmů omezuje na tělesa typu manifold.
Tento pojem se definuje pomocí algebraické topologie a to pomocí topologické ekvivalence, kterou rozumíme spojité zobrazení euklidovských prostorů, pro které existuje i inverzní zobrazení.
Manifold: Řekneme, že těleso v E3 je manifold, jestliže každý jeho bod má okolí topologicky ekvivalentní s otevřeným okruhem v E3.
K tělesu lze vytvořit rovinný model - graf s možností přidělení orientace k hranám a i s možností jeho ohodnocení. Rovinné oblasti v grafické reprezentaci grafu odpovídají stěnám (plochám) popisovaného tělesa.
Pomocí rovinného modelu lze rozhodnout o orientovatelnosti povrchu tělesa.
Orientovatelný model: Rovinný model tělesa je orientovatelný, jestliže pro stejné hrany, které se v modelu vyskytují vícekrát, neexistuje posloupnost hran rovinného modelu, v níž by stejně ohodnocená hrana byla v několika výskytech ve shodné orientaci.
Eulerova charakteristika modelu
[editovat | editovat zdroj]Eulerovy operace jsou elementární operace, které umožňují vytváření a modifikace modelů v B reprezentaci. Pomocí Eulerových operací můžeme postupně přidávat nebo odebírat vrcholy, hrany a stěny tělesa tak, aby byla neustále splněna Eulerova formule.
Pro jednoduché mnohostěny (uzavřené mnohostěny bez otvorů) platí následující Eulerova rovnost:
- V + F - E = 2
kde:
- V (Vertex) je počet vrcholů
- F (Face) je počet stěn
- E (Edge) je počet hran
Pro mnohostěny s otvory platí zobecněná Eulerova formule:
- V + F - E = H + 2(B - P)
kde:
- B (Body) je počet disjunktních částí tělesa
- H (Hole) je počet otvorů ve stěnách a
- P (Passage) je počet děr v tělese.
Množinu Eulerových operací můžeme sestavit různými způsoby. Pro vytváření a modifikaci mnohostěnů bez otvorů stačí následující tři operace:
- MBFV - vytvoří degenerované těleso o jedné stěně a jednom vrcholu.
- MEV - vytvoří vrchol a hranu.
- MFE - vytvoří hranu a stěnu.
Ke všem Eulerovým operacím existují operace inverzní, které získáme tak, že v názvu zaměníme M (Make) za K (Kill), což znamená zrušit danou entitu.
Například po šesti operacích pro počty vrcholů, hran a stěn platí:
- V=5, E=5, F=2.
Dosazením do Eulerovy formule snadno ověříme topologickou správnost vytvořené části modelu. Tímto způsobem můžeme ověřit správnost modelu po každé operaci.
Metody geometrického modelování
[editovat | editovat zdroj]Metody používané pro tvorbu geometrických modelů můžeme rozdělit do následujících skupin:
Matematické modelování
[editovat | editovat zdroj]Objekt je v tomto případě popsán matematickými vztahy. Například kružnice v rovině se středem v počátku a poloměrem r je určena parametrickými rovnicemi. Tato metoda se používá především při modelování křivek a ploch.
Šablonování
[editovat | editovat zdroj]V tomto případě je model vytvořen šablonováním (pohybem) křivky, plochy nebo tělesa po zvolené trajektorii. Nejčastěji se používá modelování translačních modelů (model vznikne translací šablony) a modelování rotačních modelů (model vznikne rotací šablony).
Rozkladové modely
[editovat | editovat zdroj]Modelovaný objekt je rozložen na objemové elementy, které pak umíme matematicky popsat.
Konstruktivní geometrie těles
[editovat | editovat zdroj]Model reálného objektu můžeme vytvořit kombinací z jednoduchých vzorových těles (primitiv). Pod pojmem kombinace budeme rozumět prostorové transformace (změna měřítka, posunutí a otočení) a množinové operace (sjednocení, průnik a rozdíl).
Vzorování
[editovat | editovat zdroj]Tato metoda patří mezi nejjednodušší metody geometrického modelování. Metoda vychází ze zadání vzorů reálných objektů, které jsou parametrizovány. Modely pak vytváříme s použitím transformací nebo modifikací určujících parametrů.
Autoři
[editovat | editovat zdroj]Tento text vypracovali studenti Univerzity Palackého v Olomouci katedry Matematické informatiky jako zápočtový úkol do předmětu Počítačová geometrie.