Trojúhelníková síťovina - Triangle mesh

Širší pokrytí tohoto tématu najdete v tématu Polygon mesh .
Příklad trojúhelníkové sítě představující delfína.

Trojúhelníková síť je typ z polygonu ok v počítačové grafice . Obsahuje sadu trojúhelníků (obvykle ve třech rozměrech ), které jsou spojeny společnými hranami nebo rohy.

Mnoho grafických softwarových balíků a hardwarových zařízení může pracovat efektivněji na trojúhelnících, které jsou seskupeny do sítí, než na podobném počtu trojúhelníků, které jsou prezentovány jednotlivě. To je obvykle proto, že počítačová grafika provádí operace na vrcholech v rozích trojúhelníků. U jednotlivých trojúhelníků musí systém pracovat se třemi vrcholy pro každý trojúhelník. Ve velké síti by se mohlo setkat osm nebo více trojúhelníků v jednom vrcholu - zpracováním těchto vrcholů pouze jednou je možné udělat zlomek práce a dosáhnout identického efektu. V mnoha aplikacích počítačové grafiky je nutné spravovat síť trojúhelníků. Složky sítě jsou vrcholy, hrany a trojúhelníky. Aplikace může vyžadovat znalost různých spojení mezi součástmi sítě. Tato připojení lze spravovat nezávisle na skutečných polohách vrcholů. Tento dokument popisuje jednoduchou datovou strukturu, která je vhodná pro správu připojení. Toto není jediná možná datová struktura. Existuje mnoho dalších typů, které podporují různé dotazy týkající se sítí.

Reprezentace

Jsou možné různé způsoby ukládání a práce se sítí v paměti počítače. S API OpenGL a DirectX existují dva hlavní způsoby předávání trojúhelníkové sítě grafickému hardwaru, trojúhelníkové pásy a indexová pole.

Trojúhelníkový proužek

Jedním ze způsobů sdílení dat vrcholů mezi trojúhelníky je pruh trojúhelníku. S proužky trojúhelníků každý trojúhelník sdílí jeden úplný okraj s jedním sousedem a druhý s dalším. Dalším způsobem je trojúhelníkový ventilátor, což je sada spojených trojúhelníků sdílejících jeden centrální vrchol. Pomocí těchto metod jsou vrcholy řešeny efektivně, což vede k potřebě zpracovat pouze N+2 vrcholy, aby bylo možné nakreslit N trojúhelníků.

Trojúhelníkové proužky jsou účinné, ale nevýhodou je, že nemusí být zřejmé, jak nebo výhodné převést libovolnou trojúhelníkovou síť na pásy.

Struktura dat

Datová struktura představující síť poskytuje podporu pro dvě základní operace: vkládání trojúhelníků a odebírání trojúhelníků. Podporuje také operaci sbalení hran, která je užitečná ve schématech decimace trojúhelníku. Struktura neposkytuje žádnou podporu pro polohy vrcholů, ale předpokládá, že každému vrcholu je přiřazen jedinečný celočíselný identifikátor, obvykle index tohoto vrcholu v řadě souvislých poloh vrcholů. Vrchol sítě je definován jediným celým číslem a je označen hvi. Okraj sítě je definován dvojicí celých čísel hv0, v1i, přičemž každé celé číslo odpovídá koncovému bodu okraje. K podpoře okrajových map jsou hrany uloženy tak, že v0 = min (v0, v1). Složka trojúhelníku je definována trojicí celých čísel hv0, v1, v2i, přičemž každé celé číslo odpovídá vrcholu trojúhelníku. Pro podporu trojúhelníkových map jsou trojúhelníky uloženy tak, že v0 = min (v0, v1, v2). Všimněte si, že hv0, v1, v2i a hv0, v2, v1i jsou považovány za různé trojúhelníky. Aplikace vyžadující oboustranné trojúhelníky musí do datové struktury vložit obě trojice. Abychom se vyhnuli neustálým připomínkám o pořadí indexů, ve zbývající části dokumentu informace o páru/trojici neimplikují, že vrcholy jsou jakýmkoli způsobem uspořádány (ačkoli implementace řazení zvládá). Propojitelnost mezi komponentami je zcela určena množinou trojic představujících trojúhelníky. Trojúhelník t = hv0, v1, v2i má vrcholy v0, v1 a v2. Má hrany e0 = hv0, v1i, e1 = hv1, v2i a e2 = hv2, v0i. Rovněž jsou známa inverzní spojení. Vrchol v0 sousedí s hranami e0 a e2 a trojúhelníkem t. Vrchol v1 sousedí s hranami e0 a e1 a trojúhelníkem t. Vrchol v2 sousedí s hranami e1 a e2 a trojúhelníkem t. Všechny tři hrany e0, e1 a e2 sousedí s t. Kolik těchto informací ukládá datová struktura, závisí na potřebách aplikace. Kromě toho může aplikace chtít mít u komponent uloženy další informace. Informace uložené na vrcholu, hraně nebo trojúhelníku se označují jako atribut vrcholu, atribut hrany nebo atribut trojúhelníku. Jejich abstraktní reprezentace zde popsané jednoduché datové struktury jsou 

Vertex = <integer>; // v
Edge = <integer, integer>; // v0, v1
Triangle <integer,integer,integer>; // v0, v1, v2
VData = <application-specific vertex data>;
EData = <application-specific edge data>;
TData = <application-specific triangle data>;
VAttribute = <VData, set<Edge>,set<Triangle>>; // data, eset, tset
EAttribute = <EData, set<Triangle>>; // data, tset
TAttribute = <TData>; // data
VPair = pair<Vertex,VAttribute>;
EPair = pair<Edge,EAttribute>;
TPair = pair<Triangle,TAttribute>;
VMap = map<VPair>;
EMap = map<EPair>;
TMap = map<TPair>;
Mesh = <VMap,EMap,TMap>; // vmap, emap, tmap

Mapy podporují standardní funkce vkládání a odebírání pro hashovací tabulku. K vložení dojde pouze v případě, že položka již neexistuje. Odebrání proběhne pouze v případě, že položka existuje.

Sbalit hranu

Tato operace zahrnuje identifikaci hran hvk, vti, kde vk se nazývá vrchol ponechání a vt se nazývá vrchol vyhození. Trojúhelníky, které sdílejí tento okraj, jsou ze sítě odstraněny. Vrchol vt je také odstraněn ze sítě. Všechny trojúhelníky, které sdílejí vt, mají tento vrchol nahrazen vk. Obrázek 1 ukazuje trojúhelníkovou síť a sekvenci tří sbalených hran aplikovaných na síť.

Indexové pole

Viz také: Čelní vrcholové sítě

U indexových polí je síť reprezentována dvěma oddělenými poli, jedním polem držícím vrcholy a druhým držícím sady tří indexů do tohoto pole, které definují trojúhelník. Grafický systém nejprve zpracuje vrcholy a poté vykreslí trojúhelníky pomocí indexových sad pracujících na transformovaných datech. V OpenGL to podporuje primitivum glDrawElements () při použití Vertex Buffer Object (VBO).

Pomocí této metody lze libovolnou sadu trojúhelníků sdílejících libovolný počet vrcholů ukládat, manipulovat s nimi a předávat je do grafického rozhraní API bez jakéhokoli zprostředkovatelského zpracování.

Viz také


Stub ikona

Tento článek související s počítačovou grafikou je útržek . Wikipedii můžete pomoci jejím rozšířením .