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ů

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:

1. Drátěný model (Wireframe model) - je určen seznamem devíti hran.
2. Hraniční model (Boundary model) - je určen seznamem pěti stěn.
3. Objemový model (Volume, Solid model) - je určen velikostí stran podstavy a výškou.

Drátěné (hranové) modely

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

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

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ů

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ů

E - reprezentace

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í:

Seznam hran

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ů).

Seznam hran E1 V1 V2 E2 V2 V3 E3 V3 V1 E4 V1 V4 E5 V2 V5 E6 V3 V6 E7 V4 V5 E8 V5 V6 E9 V6 V4

Seznam vrcholů V1 x1y1z1 V2 x2y2z2 V3 x3y3z3 V4 x4y4z4 V5 x5y5z5 V6 x6y6z6

P - reprezentace

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:

Seznam vrcholů

V1

V2

V3

V1

V4

V5

V6

V4

V1

V4

V2

V5

V3

V6

Seznam polygonů

P1		P2		P3		P4		P5
1	4	5	4	9	2	11	2	13	2

Datové reprezentace hraničních modelů

B - reprezentace

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:

Seznam stěn F1 E1 E5 E7 E4 F2 E2 E6 E8 E5 F3 E3 E6 E9 E4 F4 E1 E2 E3 F5 E7 E8 E9

Seznam hran E1 V1 V2 E2 V2 V3 E3 V3 V1 E4 V1 V4 E5 V2 V5 E6 V3 V6 E7 V4 V5 E8 V5 V6 E9 V6 V4

Seznam vrcholů V1 x1y1z1 V2 x2y2z2 V3 x3y3z3 V4 x4y4z4 V5 x5y5z5 V6 x6y6z6

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ů

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í:

1. Je dán vrchol, nalezni incidující stěny.
2. Je dána hrana, nalezni koncové vrcholy této hrany.
3. Je dána hrana, nalezni přilehlé stěny.
4. Je dána stěna, nalezni obvodové vrcholy.
5. Je dána stěna, nalezni obvodové hrany.

Eulerovy operace

Úvod do topologie

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 E₃ je manifold, jestliže každý jeho bod má okolí topologicky ekvivalentní s otevřeným okruhem v E₃.

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

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í

Metody používané pro tvorbu geometrických modelů můžeme rozdělit do následujících skupin:

Matematické modelování

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í

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

Modelovaný objekt je rozložen na objemové elementy, které pak umíme matematicky popsat.

Konstruktivní geometrie těles

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í

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

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.