A poligonháló ( jar. mesh az angol polygon mesh szóból ) csúcsok, élek és lapok gyűjteménye, amelyek meghatározzák egy poliéder objektum alakját a háromdimenziós számítógépes grafikában és térfogati modellezésben. A lapok általában háromszögek , négyszögek vagy más egyszerű konvex sokszögek (sokszögek), mivel ez leegyszerűsíti a megjelenítést , de a hálók a leggyakoribb konkáv sokszögekből is összeállíthatók.[ tisztítás ] , vagy lyukakkal ellátott sokszögek.
A sokszögrácsok doktrínája a számítógépes grafika és a geometriai modellezés nagy részterülete. A hálókon végrehajtott számos művelet közé tartozik a logikai algebra , a simítás, az egyszerűsítés és sok más. Különböző célokra és alkalmazásokra különböző hálóábrázolásokat használnak. A sokszög hálók hálózaton keresztüli továbbításához olyan hálózati reprezentációkat használnak, mint a "streaming" és a "progresszív" hálók. A térfogathálók abban különböznek a sokszöghálóktól, hogy kifejezetten reprezentálják a szerkezet felületét és térfogatát, míg a sokszöghálók kifejezetten csak a felületet, a térfogatot nem. Mivel a sokszöghálókat széles körben használják a számítógépes grafikában, sugárkövetést , ütközésészlelést és merev testdinamikai algoritmusokat fejlesztettek ki hozzájuk .
A sokszögű hálók matematikai megfelelőjét – a strukturálatlan hálókat – a kombinatorikus geometria módszereivel vizsgáljuk .
A sokszöghálókkal létrehozott objektumoknak különféle típusú elemeket kell tárolniuk, például csúcsokat, éleket, lapokat, sokszögeket és felületeket. Sok esetben csak a csúcsok, élek és lapok vagy sokszögek kerülnek tárolásra. A renderer csak háromoldalas lapokat tud támogatni, ezért sok közül sokszöget kell építeni, ahogy az ábra mutatja. 1. Sok megjelenítő azonban támogatja a négy vagy több oldalú sokszögeket, vagy képes a sokszögeket menet közben háromszögekké alakítani, így szükségtelenné válik a háló háromszögezett formában történő tárolása. Bizonyos esetekben, például egy fej modellezésénél is kívánatos, hogy három- és négyoldalú sokszöget is tudjunk létrehozni.
A csúcs egy pozíció más információkkal, például színekkel, normálvektorokkal és textúra koordinátákkal együtt. Az él két csúcs közötti kapcsolat. A lap az élek zárt halmaza, amelyben a háromszög alakú lapnak három, a négyszögletű lapnak négy éle van. A sokszög egy síkban lévő (ugyanazon síkban fekvő) lapok halmaza. A többoldalú lapokat támogató rendszerekben a sokszögek és a lapok egyenértékűek. A legtöbb renderelő hardver azonban csak a három vagy négy oldalú lapokat támogatja, így a sokszögek több lapként jelennek meg. Matematikailag a sokszögháló ábrázolható strukturálatlan hálóként vagy irányítatlan gráfként, geometriai, alakzati és topológiai tulajdonságok hozzáadásával.
A felületek , amelyeket általában simítócsoportoknak neveznek , hasznosak, de nem szükségesek a sima területek csoportosításához. Képzelj el egy fedelű hengert, például egy bádogdobozt. A sima oldalárnyékolás érdekében az összes normálnak vízszintesen kell mutatnia a közepétől, míg a fedél normáljainak +/-(0,0,1) irányba kell mutatniuk. Ha egyetlen, Phong-árnyékolt felületként jelenítjük meg, a gyűrődési csúcsok normálértékei helytelenek. Ezért szükségünk van egy módszerre annak meghatározására, hogy hol hagyjuk abba a simítást, hogy a háló sima részeit csoportosítsuk, ugyanúgy, ahogy a sokszögek csoportosítják a 3 oldalú lapokat. A felületek/sima csoportok megadásának alternatívájaként a háló más információkat is tartalmazhat ugyanazon adatok kiszámításához, például elválasztó szöget (az e határérték feletti normálértékekkel rendelkező sokszögeket a rendszer vagy automatikusan különálló keverékcsoportként kezeli, vagy valamilyen technikát alkalmaznak a köztük lévő él, például hasadás vagy levágás). Ezenkívül a nagyon nagy felbontású hálók kevésbé hajlamosak olyan problémákra, amelyek megoldásához simítócsoportok szükségesek, mivel sokszögeik olyan kicsik, hogy nincs szükség rájuk. Ezen túlmenően létezik egy alternatíva, hogy egyszerűen leválasztják magukat a felületeket a háló többi részéről. A megjelenítők nem próbálják meg kisimítani az éleket a nem összefüggő sokszögek között.
A mesh formátum más hasznos adatokat is meghatározhat. Csoportok definiálhatók , amelyek egyedi hálóelemeket határoznak meg, és hasznosak egyéni részobjektumok létrehozásához csontváz animációhoz , vagy egyedi témák létrehozásához nem csontváz animációhoz. Az anyagok általában meghatározottak , lehetővé téve, hogy a háló különböző részei különböző árnyékolókat használhassanak rendereléskor. A legtöbb hálóformátum UV-koordinátákat is feltételez , amelyek a háló különálló 2D-s ábrázolásai, „kicsomagolva”, hogy megmutassák, mennyi a 2D-s textúra a különböző háló sokszögekre.
A sokszöghálók sokféleképpen ábrázolhatók, különféle módokon tárolva a csúcsokat, éleket és lapokat. Tartalmazzák:
Mindegyik nézetnek megvannak a maga előnyei és hátrányai. [egy]
Az adatstruktúra megválasztását az alkalmazás, a szükséges teljesítmény, az adatok mérete és az elvégzendő műveletek határozzák meg. Például könnyebb a háromszögekkel foglalkozni, mint az általános sokszögekkel, különösen a számítási geometriában . Bizonyos műveletekhez gyors hozzáférésre van szükség a topológiai információkhoz, például az élekhez vagy a szomszédos lapokhoz; ehhez bonyolultabb struktúrákra van szükség, például "szárnyas" ábrázolásra. A hardveres megjelenítéshez kompakt, egyszerű szerkezetekre van szükség; ezért az alacsony szintű API-k, mint például a DirectX és az OpenGL általában tartalmaznak egy szögtáblázatot (háromszög ventilátorok).
A csúcsábrázolás egy objektumot más csúcsokhoz kapcsolódó csúcsok halmazaként ír le. Ez a legegyszerűbb ábrázolás, de nem használják széles körben, mert az arc- és szélinformáció nincs kifejezve. Ezért az összes adaton át kell menni, hogy létrejöjjön az arcok listája a megjelenítéshez. Ezenkívül a széleken és a felületeken végzett műveletek végrehajtása nem egyszerű.
A VI mesh-ek azonban előnyt kovácsolnak az alacsony memóriahasználatból és a hatékony átalakításból. A 2. ábra egy VI hálóval rajzolt doboz példáját mutatja. Minden csúcs indexeli a szomszédos csúcsait. Ne feledje, hogy az utolsó két csúcsnak, a 8-asnak és a 9-esnek a doboz tetején és alján négy összekapcsolt csúcs van, nem pedig öt. A fő rendszernek tetszőleges számú csúcsot kell kezelnie bármely adott csúcshoz.
A VP hálók részletesebb leírását lásd Smith (2006). [egy]
A lapok listáját használó háló egy objektumot lapok és csúcsok halmazaként ábrázol. Ez a legszélesebb körben használt ábrázolás, a modern grafikus hardverek által jellemzően elfogadott bemenet.
Az arclista jobb modellezéshez, mint a csúcsábrázolás, mivel lehetővé teszi az arc csúcsainak és a csúcsot körülvevő lapok explicit keresését. A 3. ábra egy hálódobozra mutat példát az arcok listájával. A Vertex v5 kiemelve mutatja az azt körülvevő éleket. Vegye figyelembe, hogy ebben a példában minden lapnak 3 csúcsnak kell lennie. Ez azonban nem jelenti azt, hogy minden csúcsnak ugyanannyi környező lapja van.
A rendereléshez az arc általában csúcsindexek halmazaként kerül a GPU-ba, a csúcsok pedig pozíció/szín/normál struktúraként (az ábrán csak a pozíció szerepel). Ezért az alakváltozások, de nem a geometriaváltozások, dinamikusan frissíthetők a csúcsadatok egyszerű újraküldésével az arckapcsolat frissítése nélkül.
A modellezés megköveteli az összes szerkezet könnyű bejárását. Az arcok listáját használó hálóval nagyon könnyű megtalálni az arc csúcsait. Ezenkívül a csúcslista tartalmazza az egyes csúcsokhoz társított összes lap listáját. A csúcsábrázolástól eltérően az oldalak és a csúcsok is explicit módon vannak ábrázolva, így a szomszédos lapok és csúcsok keresése időben állandó. Az élek azonban nincsenek kifejezetten megadva, ezért továbbra is keresésre van szükség az adott élt körülvevő összes él megtalálásához. Más dinamikus műveletek, mint például az arcok eltépése vagy összevonása, szintén trükkösek az arcok listájával.
A Bruce Baumgart által 1975-ben bevezetett szárnyas ábrázolás kifejezetten a háló csúcsait, lapjait és éleit ábrázolja. Ezt az ábrázolást széles körben használják modellező programokban, hogy a legnagyobb rugalmasságot biztosítsák a hálógeometria dinamikus módosításában, mivel a szakítási és egyesítési műveletek gyorsan végrehajthatók. Legfőbb hátrányuk a magas memóriaigény és a sok index tartalma miatt megnövekedett összetettség.
A szárnyas ábrázolás megoldja a szélek közötti átjárás problémáját, és rendezett lapkészletet biztosít a szélek körül. Egy adott élnél a kimenő élek száma tetszőleges lehet. Ennek leegyszerűsítése érdekében a szárnyas ábrázolás csak az óramutató járásával megegyező és az óramutató járásával ellentétes irányú négy legközelebbi élt tartalmazza az él mindkét végén. A többi él fokozatosan megkerülhető. Ezért az egyes élekre vonatkozó információk pillangóhoz hasonlítanak, ezért az ábrázolást "szárnyasnak" nevezik. A 4. ábra egy doboz példáját mutatja "szárnyas" ábrázolásban. A teljes éladatok két csúcsból (végpontokból), két lapból (mindkét oldalon) és négy élből (az él "szárnyaiból") állnak.
A szárnyas ábrázolás grafikus hardverrel történő megjelenítéséhez arcindexek listáját kell létrehozni. Ez általában csak akkor történik meg, ha a geometria megváltozik. A szárnyas ábrázolás ideális dinamikus geometriához, például felületfelosztáshoz és interaktív modellezéshez, mivel lokálisan előfordulhatnak hálóváltozások. A háló körüli séta, ami hasznos lehet az ütközésészlelésnél, hatékonyan végezhető.
Lásd Baumgart (1975) a részletekért [2]
| Művelet | Csúcsábrázolás | Arclista | "szárnyas" előadás | ||
|---|---|---|---|---|---|
| VV | Minden csúcs a csúcs körül | Tisztán | V → f1, f2, f3, … → v1, v2, v3, … | V → e1, e2, e3, … → v1, v2, v3, … | |
| EF | Az arc minden széle | F(a, b, c) → {a, b}, {b, c}, {a, c} | F → {a, b}, {b, c}, {a, c} | Tisztán | |
| V F | Az arc összes csúcsa | F(a,b,c) → {a,b,c} | Tisztán | F → e1, e2, e3 → a, b, c | |
| FV | Minden él a tetején | Párkeresés | Tisztán | V → e1, e2, e3 → f1, f2, f3, … | |
| EV | Minden él a csúcs körül | V → {v, v1}, {v, v2}, {v, v3}, … | V → f1, f2, f3, … → v1, v2, v3, … | Tisztán | |
| F.E. | A szél mindkét széle | Lista összehasonlítása | Lista összehasonlítása | Tisztán | |
| VE | Az él mindkét csúcsa | E(a, b) → {a, b} | E(a, b) → {a, b} | Tisztán | |
| Flook | Találja meg az arcot adott csúcsokkal | F(a,b,c) → {a,b,c} | A v1,v2,v3 halmazok metszéspontja | A v1,v2,v3 halmazok metszéspontja | |
| Memória méret | V*átl.(V,V) | 3F + V*átl.(F,V) | 3F + 8E + V*átl.(E,V) | ||
| Példa 10 csúcsgal, 16 lappal, 24 éllel: | |||||
| 10 * 5 = 50 | 3*16 + 10*5 = 98 | 3*16 + 8*24 + 10*5 = 290 | |||
| 5. ábra: A rácsnézeti műveletek összefoglalása | |||||
A fenti táblázatban kifejezetten azt jelzi, hogy a művelet konstans időben végrehajtható, mivel az adatok közvetlenül tárolódnak; A lista összehasonlítása azt jelzi, hogy a művelet végrehajtásához két listát kell összehasonlítani; és a páros keresés azt jelzi, hogy két indexkeresést kell végrehajtani. Az avg(V,V) jelölés az adott csúcshoz kapcsolódó csúcsok átlagos számát jelenti; avg(E,V) az adott csúcshoz kapcsolódó élek átlagos száma, az avg(F,V) pedig az adott csúcshoz kapcsolódó lapok átlagos száma.
A „V → f1, f2, f3, … → v1, v2, v3, …” jelölés azt mutatja, hogy a művelet több elem körüli bejárást igényel. Például ahhoz, hogy egy adott V csúcs körüli összes csúcsot megkapjuk egy laplistával, először meg kell találni az adott V csúcs körüli lapokat egy csúcslistával. Ezután ezekről az oldalakról az arcok listáját használva keresse meg a körülöttük lévő csúcsokat. Vegye figyelembe, hogy a szárnyas ábrázolás szinte az összes információt explicit módon tárolja, és a többi művelet mindig a szélen halad át, hogy több információt kapjon. A csúcsnézet az egyetlen nézet, amely explicit módon tárolja egy adott csúcs szomszédos csúcsait.
A reprezentációk összetettségének növekedésével (az összefoglalóban balról jobbra), a tárolt információ mennyisége kifejezetten növekszik. Ez közvetlenebb, időben állandóbb hozzáférést biztosít a különböző elemek bejárásához és topológiájához, de több memória árán az indexek megfelelő tárolása érdekében.
Általános szabályként az arclista hálókat akkor használják, amikor egy objektumot olyan hardverrel kell renderelni, amely nem változtatja meg a geometriát (kapcsolatok), de deformálódhat vagy átalakulhat (csúcspozíciók), például statikus vagy valós idejű objektumok átalakítása során. A "szárnyas" ábrázolást akkor használják, amikor a geometria megváltozik, például interaktív modellezési csomagokban vagy felosztott felületek kiszámításához. A Vertex nézet ideális a geometria vagy topológia hatékony, összetett megváltoztatásához, mindaddig, amíg a hardveres megjelenítés nem fontos.
A streamhálók rendezett, de független módon tárolják az arcokat, így a hálót darabokban lehet küldeni. A lapok sorrendje lehet térbeli, spektrális vagy más hálótulajdonságokon alapuló. A streaming hálók lehetővé teszik nagyon nagy hálók megjelenítését még betöltés közben is.
A progresszív hálók egyre részletesebb csúcs- és arcadatokat biztosítanak. Az áramlási hálókkal ellentétben a progresszív hálók az egész objektum általános formáját adják, de alacsony részletességgel. További adatok, új élek és felületek fokozatosan növelik a háló részletességét.
A normál hálók fokozatos hálóváltozásokat közvetítenek az alaphálóhoz képesti normál eltolások halmazaként. Ezzel a technikával egy sor textúra megjeleníti a kívánt növekményes változtatásokat. A normál rácsok kompaktak, mert csak egy skaláris érték szükséges az elmozdulás kifejezéséhez. A technika azonban egy sor összetett átalakítást igényel a nyírási textúrák létrehozásához.
A sokszöghálók többféle fájlformátumban tárolhatók :