Polygon mesh - Polygon mesh

Viz také: Model s drátovým rámem
Příklad sítě s nízkým poly trojúhelníkem představujícím delfína

Ve 3D počítačové grafice a objemovém modelování je polygonová síť kolekce vrcholy ,hrana satvář s, která definuje tvarpolyhedrálníobjektu. Plochy se obvykle skládají ztrojúhelníků(trojúhelníková síť),čtyřúhelníků(čtyřkolky) nebo jiných jednoduchýchkonvexních polygonů(n-gons), protože to zjednodušujevykreslování, ale může být také obecněji složeno zkonkávních polygonůnebo dokonce polygonů s otvory.

Studium polygonových sítí je velkým dílčím polem počítačové grafiky (konkrétně 3D počítačové grafiky) a geometrického modelování . Pro různé aplikace a cíle se používají různé reprezentace polygonových sítí. Různé operace prováděné v sítích mohou zahrnovat: logickou logiku , vyhlazování , zjednodušení a mnoho dalších. Algoritmy také existují pro sledování paprsku , detekci kolizí a dynamiku tuhého těla s polygonovými sítěmi. Pokud jsou namísto ploch vykresleny okraje sítě, stane se model drátovým modelem .

Objemové sítě se liší od polygonových sítí v tom, že explicitně představují povrch i objem struktury, zatímco polygonové sítě představují pouze povrch (objem je implicitní).

Existuje několik metod pro generování sítě , včetně algoritmu pochodových kostek .

Elementy

Prvky modelování polygonálních sítí.

Objekty vytvořené pomocí polygonových sítí musí ukládat různé typy prvků. Patří mezi ně vrcholy, hrany, plochy, mnohoúhelníky a povrchy. V mnoha aplikacích jsou uloženy pouze vrcholy, hrany a plochy nebo polygony. Renderovací modul může podporovat pouze 3stranné plochy, takže polygony musí být vytvořeny z mnoha z nich, jak je uvedeno výše. Mnoho vykreslovačů však buď podporuje čtyřkolky a polygony s vyššími stranami, nebo jsou schopné za běhu převést polygony na trojúhelníky, takže není nutné ukládat síť do trojúhelníkové formy.

vrchol
Pozice (obvykle v 3D prostoru) spolu s dalšími informacemi, jako jsou barevné, normální vektorové a texturové souřadnice.
okraj
Spojení mezi dvěma vrcholy.
tvář
Uzavřená sada hran, ve které má trojúhelníková plocha tři hrany a čtvercová plocha má čtyři hrany. Polygon je v jedné rovině set tváří. V systémech, které podporují vícestranné plochy, jsou polygony a plochy ekvivalentní. Většina vykreslovacího hardwaru však podporuje pouze 3 nebo 4stranné plochy, takže polygony jsou reprezentovány jako více ploch. Matematicky lze polygonální síť považovat za nestrukturovanou mřížku nebo neorientovaný graf s dalšími vlastnostmi geometrie, tvaru a topologie.
povrchy
Častěji nazývané vyhlazovací skupiny jsou užitečné, ale není nutné je seskupovat do vyhlazovaných oblastí. Zvažte válec s uzávěry, například plechovku sody. Pro plynulé stínování stran musí všechny normály povrchu směřovat vodorovně od středu, zatímco normály čepic musí směřovat rovně nahoru a dolů. Vykreslení jako jeden povrch zastíněný Phongem by vrcholy záhybů měly nesprávné normály. Pro seskupení hladkých částí sítě je tedy potřeba určit způsob, jak zastavit vyhlazování, stejně jako polygony seskupují 3stranné plochy. Jako alternativu k poskytování povrchů / vyhlazovacích skupin může síť obsahovat další data pro výpočet stejných dat, například úhel rozdělení (polygony s normály nad touto prahovou hodnotou jsou automaticky považovány za samostatné vyhlazovací skupiny nebo nějakou techniku, jako je rozdělení nebo srážení hran se automaticky aplikuje na hranu mezi nimi). Sítě s velmi vysokým rozlišením navíc méně podléhají problémům, které by vyžadovaly vyhlazovací skupiny, protože jejich polygony jsou tak malé, že činí potřebu irelevantní. Dále existuje další alternativa v možnosti jednoduchého oddělení samotných povrchů od zbytku sítě. Renderery se nepokoušejí vyhladit hrany přes nesouvislé polygony.
skupiny
Některé formáty mřížky obsahují skupiny , které definují samostatné prvky mřížky, a jsou užitečné pro určení samostatných dílčích objektů pro animaci skeletu nebo samostatných aktérů pro animaci bez skeletu.
materiály
Obecně budou definovány materiály umožňující různým částem sítě použít při vykreslení různé shadery .
UV souřadnice
Většina formátů mřížky také podporuje nějakou formu UV souřadnic, které jsou samostatným 2d znázorněním mřížky „rozloženo“, aby se ukázalo, jakou část 2-dimenzionální texturové mapy použít pro různé polygony mřížky. Je také možné, aby sítě obsahovaly další takové informace o atributech vrcholů, jako je barva, vektory tečen, mapy hmotnosti pro ovládání animace atd. (Někdy se také nazývají kanály ).

Zastoupení

Polygonální sítě mohou být reprezentovány různými způsoby, za použití různých metod k ukládání dat vrcholů, hran a ploch. Tyto zahrnují:

Face-vrchol vrcholů
Jednoduchý seznam vrcholů a sada polygonů, které ukazují na vrcholy, které používá.
Okřídlený okraj
ve kterém každá hrana ukazuje na dva vrcholy, dvě tváře a čtyři hrany (ve směru hodinových ručiček a proti směru hodinových ručiček), které se jich dotýkají. Okna s okřídleným okrajem umožňují neustálý časový průchod povrchu, ale s vyššími požadavky na skladování.
Poloviční očka
Podobně jako oka s okřídleným okrajem, kromě toho, že se používá pouze polovina informací o průchodu hranou. (viz OpenMesh )
Sítě se čtyřmi okraji
které ukládají hrany, poloviční hrany a vrcholy bez odkazu na mnohoúhelníky. Polygony jsou v reprezentaci implicitní a lze je najít procházením strukturou. Požadavky na paměť jsou podobné sítím s polovičním okrajem.
Rohové stoly
které ukládají vrcholy v předdefinované tabulce, takže procházení tabulky implicitně definuje polygony. Jedná se v podstatě o trojúhelníkový ventilátor používaný při vykreslování hardwarové grafiky. Reprezentace je kompaktnější a efektivnější při načítání polygonů, ale operace pro změnu polygonů jsou pomalé. Rohové tabulky navíc nepředstavují pletiva úplně. K reprezentaci většiny sítí je potřeba více rohových stolů (trojúhelníkové ventilátory).
Sítě vrchol-vrchol
Síť „ VV “ představuje pouze vrcholy, které směřují k jiným vrcholům. Informace o hraně i ploše jsou v reprezentaci implicitní. Jednoduchost reprezentace však neumožňuje provádět na sítích mnoho efektivních operací.

Každé z výše uvedených zobrazení má zvláštní výhody a nevýhody, o nichž se dále zmiňuje Smith (2006). Volba datové struktury se řídí aplikací, požadovaným výkonem, velikostí dat a prováděnými operacemi. Například je jednodušší vypořádat se s trojúhelníky než s obecnými polygony, zejména ve výpočetní geometrii . Pro určité operace je nutné mít rychlý přístup k topologickým informacím, jako jsou hrany nebo sousední plochy; to vyžaduje složitější struktury, jako je například reprezentace okřídlených hran. Pro hardwarové vykreslování jsou zapotřebí kompaktní a jednoduché struktury; rohový stůl (trojúhelníkový ventilátor) je tedy běžně začleněn do nízkoúrovňových vykreslovacích API, jako jsou DirectX a OpenGL .

Sítě vrchol-vrchol

Obrázek 2. Sítě vrchol-vrchol

Sítě vrchol-vrchol představují objekt jako sadu vrcholů připojených k jiným vrcholům. Toto je nejjednodušší znázornění, ale není široce používáno, protože informace o obličeji a okraji jsou implicitní. Proto je nutné data procházet, aby bylo možné vygenerovat seznam ploch pro vykreslení. Navíc operace s hranami a plochami nelze snadno provést.

Sítě VV však těží z malého úložného prostoru a efektivního tvarování. Výše uvedený obrázek ukazuje čtyřstranný rámeček znázorněný sítí VV. Každý vrchol indexuje své sousední vrcholy. Všimněte si, že poslední dva vrcholy, 8 a 9 v horním a dolním středu "box-cylindru", mají spíše čtyři spojené vrcholy než pět. Obecný systém musí být schopen zvládnout libovolný počet vrcholů připojených k danému vrcholu.

Úplný popis sítí VV viz Smith (2006).

Face-vrchol vrcholů

Obrázek 3. Sítě tváře-vrchol

Plochy vrchol-vrchol představují objekt jako sadu ploch a sadu vrcholů. Toto je nejpoužívanější síťová reprezentace, což je vstup, který moderní grafický hardware obvykle přijímá.

Plochy vrchol-vrchol se zlepšují na VV-mesh pro modelování v tom, že umožňují explicitní vyhledávání vrcholů plochy a ploch obklopujících vrchol. Výše uvedený obrázek ukazuje příklad „skříňový válec“ jako síť FV. Vertex v5 je zvýrazněn, aby se zobrazily tváře, které jej obklopují. Všimněte si, že v tomto příkladu musí mít každá plocha přesně 3 vrcholy. To však neznamená, že každý vrchol má stejný počet okolních ploch.

Pro vykreslování se seznam tváří obvykle přenáší do GPU jako sada indexů na vrcholy a vrcholy se odesílají jako pozice / barva / normální struktury (na obrázku je uvedena pouze poloha). To má tu výhodu, že změny tvaru, ale ne geometrie, lze dynamicky aktualizovat jednoduchým opětovným odesláním dat vrcholů bez aktualizace připojení plochy.

Modelování vyžaduje snadné procházení všemi strukturami. S oky obličeje a vrcholu lze snadno najít vrcholy obličeje. Seznam vrcholů také obsahuje seznam ploch připojených ke každému vrcholu. Na rozdíl od sítí VV jsou plochy i vrcholy explicitní, takže umístění sousedních ploch a vrcholů je konstantní čas. Okraje jsou však implicitní, takže je stále potřeba hledat všechny tváře obklopující danou tvář. Jiné dynamické operace, jako je rozdělení nebo sloučení obličeje, jsou také obtížné se sítěmi vrchol-vrchol.

Oka s okřídleným okrajem

Obrázek 4. Sítě s křídly

Sítě s okřídlenými hranami, které zavedl Baumgart v roce 1975, výslovně představují vrcholy, plochy a hrany sítě. Tato reprezentace je široce používána v modelových programech, aby poskytla maximální flexibilitu při dynamické změně geometrie sítě, protože operace rozdělení a sloučení lze provádět rychle. Jejich primární nevýhodou jsou velké požadavky na úložiště a zvýšená složitost kvůli udržování mnoha indexů. Dobrou diskusi o otázkách implementace okřídlených ok lze najít v knize Graphics Gems II .

Okna s okřídleným okrajem řeší problém přechodu z okraje na okraj a poskytnutí uspořádané sady ploch kolem okraje. Pro každou danou hranu může být počet odchozích hran libovolný. Abychom to zjednodušili, oka s okřídlenými okraji poskytují pouze čtyři, nejbližší okraje ve směru hodinových ručiček a proti směru hodinových ručiček na každém konci. Ostatní hrany lze procházet přírůstkově. Informace pro každý okraj proto připomínají motýla, a proto jsou oka typu „okřídlený okraj“. Výše uvedený obrázek ukazuje „skříňový válec“ jako síť s křídly. Celková data pro hranu se skládají ze 2 vrcholů (koncových bodů), 2 ploch (na každé straně) a 4 hran (okřídlená hrana).

Vykreslování ok okřídlených okrajů pro grafický hardware vyžaduje vygenerování seznamu indexů tváře. To se obvykle provádí pouze při změně geometrie. Sítě s okřídlenými hranami jsou ideální pro dynamickou geometrii, jako jsou dělení ploch a interaktivní modelování, protože ke změnám sítě může dojít místně. Traverz přes síť, který může být potřebný pro detekci kolizí, lze provést efektivně.

Další podrobnosti viz Baumgart (1975).

Vykreslení dynamických sítí

Okna s okřídleným okrajem nejsou jediným znázorněním, které umožňuje dynamické změny geometrie. Novou reprezentací, která kombinuje mřížky s okřídlenými hranami a mřížky vrcholů tváří, je dynamická síť vykreslení , která explicitně ukládá jak vrcholy plochy, tak plochy vrcholů (jako FV sítě), a plochy a vrcholy hrany ( jako okřídlený okraj).

Vykreslení dynamických sítí vyžaduje o něco méně úložného prostoru než standardní sítě s křídly a lze je přímo vykreslit grafickým hardwarem, protože seznam tváří obsahuje index vrcholů. Traversal from vertex to face is explicit (constant time), as is from face to vertex. Sítě RD nevyžadují čtyři odchozí hrany, protože je lze najít procházením od hrany k ploše, poté tváří k sousední hraně.

RD sítě těží z funkcí okřídlených okrajů tím, že umožňují dynamickou aktualizaci geometrie.

Další informace viz Tobler & Maierhofer ( WSCG 2006).

Shrnutí reprezentace sítě

Úkon Vrchol-vrchol Face-vrchol Okřídlený okraj Vykreslení dynamické
VV Všechny vrcholy kolem vrcholu Výslovný V → f1, f2, f3, ... → v1, v2, v3, ... V → e1, e2, e3, ... → v1, v2, v3, ... V → e1, e2, e3, ... → v1, v2, v3, ...
EF Všechny hrany obličeje F (a, b, c) → {a, b}, {b, c}, {a, c} F → {a, b}, {b, c}, {a, c} Výslovný Výslovný
VF Všechny vrcholy obličeje F (a, b, c) → {a, b, c} Výslovný F → e1, e2, e3 → a, b, c Výslovný
F V Všechny tváře kolem vrcholu Párové vyhledávání Výslovný V → e1, e2, e3 → f1, f2, f3, ... Výslovný
EV Všechny hrany kolem vrcholu V → {v, v1}, {v, v2}, {v, v3}, ... V → f1, f2, f3, ... → v1, v2, v3, ... Výslovný Výslovný
FE Obě tváře hrany Seznam porovnat Seznam porovnat Výslovný Výslovný
VE Oba vrcholy hrany E (a, b) → {a, b} E (a, b) → {a, b} Výslovný Výslovný
Flook Najděte tvář s danými vrcholy F (a, b, c) → {a, b, c} Nastavit průsečík v1, v2, v3 Nastavit průsečík v1, v2, v3 Nastavit průsečík v1, v2, v3
Velikost úložiště V * avg (V, V) 3F + V * průměr (F, V) 3F + 8E + V * prům. (E, V) 6F + 4E + V * prům. (E, V)
Příklad s 10 vrcholy, 16 plochami, 24 hranami:
10 * 5 = 50 3 * 16 + 10 * 5 = 98 3 * 16 + 8 * 24 + 10 * 5 = 290 6 * 16 + 4 * 24 + 10 * 5 = 242
Obrázek 6: Souhrn operací znázornění sítě

Ve výše uvedené tabulce explicitně označuje, že operaci lze provést v konstantním čase, protože data jsou přímo uložena; porovnání seznamu znamená, že k provedení operace musí být provedeno srovnání seznamu mezi dvěma seznamy; a vyhledávání párů znamená, že je třeba hledat na dvou indexech. Zápis avg (V, V) znamená průměrný počet vrcholů připojených k danému vrcholu; avg (E, V) znamená průměrný počet hran připojených k danému vrcholu a avg (F, V) je průměrný počet ploch připojených k danému vrcholu.

Zápis „V → f1, f2, f3, ... → v1, v2, v3, ...“ popisuje, že k provedení operace je nutný průchod více prvky. Například pro získání „všech vrcholů kolem daného vrcholu V“ pomocí sítě plocha-vrchol je nutné nejprve najít plochy kolem daného vrcholu V pomocí seznamu vrcholů. Potom z těchto obličejů použijte seznam obličejů k vyhledání vrcholů kolem nich. Všimněte si, že mřížky s okřídleným okrajem výslovně ukládají téměř všechny informace a další operace vždy přejdou k okraji jako první, aby získaly další informace. Sítě vrchol-vrchol jsou jedinou reprezentací, která explicitně ukládá sousední vrcholy daného vrcholu.

Jak se reprezentace sítí stávají složitějšími (v souhrnu zleva doprava), zvyšuje se množství explicitně uložených informací. To poskytuje přímější a konstantní čas, přístup k procházení a topologii různých prvků, ale za cenu zvýšené režie a prostoru při správném udržování indexů.

Obrázek 7 ukazuje informace o připojení pro každou ze čtyř technik popsaných v tomto článku. Existují také další reprezentace, například tabulky s poloviční hranou a rohové tabulky. To jsou všechny varianty toho, jak se vrcholy, plochy a hrany navzájem indexují.

Obecným pravidlem je, že sítě typu líc-vrchol se používají vždy, když musí být objekt vykreslen na grafickém hardwaru, který nemění geometrii (konektivitu), ale může deformovat nebo měnit tvar (polohy vrcholů), jako je vykreslování statických nebo morfujících objektů v reálném čase. . Okřídlené hrany nebo vykreslení dynamických sítí se používají při změnách geometrie, například v balíčcích interaktivního modelování nebo pro výpočet dělících ploch. Sítě vrchol-vrchol jsou ideální pro efektivní a komplexní změny v geometrii nebo topologii, pokud vykreslování hardwaru není důležité.

Další zastoupení

Streamování sítí
ukládat tváře uspořádaným, ale nezávislým způsobem, aby bylo možné síť přenášet po částech. Pořadí ploch může být prostorové, spektrální nebo založené na jiných vlastnostech sítě. Streamovací sítě umožňují vykreslení velmi velké sítě, i když se stále načítá.
Progresivní sítě
přenášet data vrcholů a tváří se zvyšující se úrovní podrobností. Na rozdíl od streamovacích sítí poskytují progresivní sítě celkový tvar celého objektu, ale s nízkou úrovní detailů. Další data, nové hrany a plochy, postupně zvyšují detail sítě.
Normální oka
přenášet progresivní změny do sítě jako sadu normálních posunů ze základní sítě. S touto technikou představuje řada textur požadované přírůstkové úpravy. Normální sítě jsou kompaktní, protože k vyjádření posunutí je potřeba pouze jedna skalární hodnota. Tato technika však k vytvoření textur posunutí vyžaduje složitou řadu transformací.

Formáty souborů

Existuje mnoho různých formátů souborů pro ukládání dat polygonových sítí. Každý formát je nejúčinnější, pokud je použit pro účely určené jeho tvůrcem. Některé z těchto formátů jsou uvedeny níže:

Přípona souboru Název formátu Organizace Program (y) Popis
.drsný Syrové pletivo Neznámý Rozličný Otevřený, pouze formát ASCII. Každý řádek obsahuje 3 vrcholy oddělené mezerami, které tvoří trojúhelník, například takto: X1 Y1 Z1 X2 Y2 Z2 X3 Y3 Z3
.směs Formát souboru mixéru Blender Foundation Mixér 3D Open source, pouze binární formát
.fbx Formát Autodesk FBX Autodesk Rozličný Proprietární. Existují binární a ASCII specifikace.
.3ds Soubor 3ds Max Autodesk 3ds Max Běžný, ale zastaralý formát s tvrdými 16bitovými limity počtu vrcholů a ploch. Ani standardizovaný, ani dobře zdokumentovaný, ale býval „de facto standardem“ pro výměnu dat.
.dae Výměna digitálních aktiv (COLLADA) Sony Computer Entertainment , Khronos Group N / A Je zkratka pro " Colla borative D eSign A ctivity". Univerzální formát určený k zabránění nekompatibilitě.
.dgn Soubor MicroStation Bentley Systems MicroStation Existují dva formáty souborů dgn: pre-verze 8 a verze 8 (V8)
.3dm Soubor Rhino Robert McNeel & Associates Nosorožec 3D
.dxf , .dwg Formát výměny výkresů Autodesk AutoCAD
.obj Wavefront OBJ Technologie Wavefront Rozličný Formát ASCII popisující 3D geometrii. Vrcholy všech ploch jsou uspořádány proti směru hodinových ručiček, čímž jsou normály fazet implicitní. Hladké normály jsou specifikovány na vrchol.
.vrstva Polygonový formát souboru Stanfordská Univerzita Rozličný Binární a ASCII
.pmd Data Polygon Movie Maker Yu Higuchi MikuMikuDance Proprietární formát binárního souboru pro ukládání geometrie humanoidního modelu s podrobnostmi, materiálem a fyzikálními informacemi.
.stl Stereolitografický formát 3D systémy Mnoho Binární a ASCII formát původně navržený pro pomoc v CNC .
.amf Formát souboru aditivní výroby ASTM International N / A Stejně jako formát STL, ale s přidanou podporou nativní barvy, materiálu a konstelace.
.wrl Modelingový jazyk pro virtuální realitu Konsorcium Web3D Internetové prohlížeče Norma ISO 14772-1: 1997
.wrz VRML komprimováno Konsorcium Web3D Internetové prohlížeče
.x3d, .x3db, .x3dv Rozšiřitelný 3D Konsorcium Web3D Internetové prohlížeče XML, otevřený zdroj, bez licenčních poplatků, rozšiřitelný a interoperabilní; také podporuje informace o barvě, struktuře a scéně. Norma ISO 19775/19776/19777
.x3dz, .x3dbz, .x3dvz X3D komprimovaný binární Konsorcium Web3D Internetové prohlížeče
.c4d Soubor Cinema 4D MAXON KINO 4D
. dvě LightWave 3D objekt Soubor NewTek LightWave 3D
.smb SCOREC apf RPI SCOREC PUMI Otevřené paralelní adaptivní nestrukturované 3D sítě pro pracovní postupy simulace založené na PDE.
.msh Gmsh Mesh Vývojáři GMsh Projekt GMsh Otevřený zdroj poskytující popis sítě ASCII pro lineární a polynomiálně interpolované prvky v 1 až 3 rozměrech.
.pletivo OGRE XML OGRE vývojový tým OGRE, čistě základní Otevřený zdroj. K dispozici je binární formát (.mesh) a ASCII (.mesh.xml). Zahrnuje data pro vertexovou animaci a cílovou animaci Morph (blendshape). Data skeletální animace v samostatném souboru (.skeleton).
.veg Vega FEM čtyřboká síť Jernej Barbič Vega FEM Otevřený zdroj. Ukládá čtyřstěnnou síť a její materiálové vlastnosti pro simulaci MKP. K dispozici jsou formáty ASCII (.veg) a binární (.vegb).
. z3d Z3d Oleg Melashenko Zanoza Modeler -
.vtk VTK síť VTK , Kitware VTK , Paraview Otevřený, ASCII nebo binární formát, který obsahuje mnoho různých datových polí, včetně dat bodů, dat buněk a dat polí.
.14d LAI4D kresba Laboratoř umělé inteligence pro design LAI4D Datový formát ASCII, který popisuje hierarchický strom entit.

Viz také

Reference

externí odkazy