Ett polygonnät ( jar. mesh från engelska polygon mesh ) är en samling av hörn, kanter och ytor som definierar formen på ett polyedriskt föremål i tredimensionell datorgrafik och volymetrisk modellering. Ansikter är vanligtvis trianglar , fyrkanter eller andra enkla konvexa polygoner (polygoner) eftersom detta förenklar återgivningen , men maskor kan också bestå av de vanligaste konkava polygonerna .[ clear up ] , eller polygoner med hål.
Läran om polygonala rutnät är en stor underavdelning av datorgrafik och geometrisk modellering. De många operationerna som utförs på maskor kan inkludera boolesk algebra , utjämning, förenkling och många andra. Olika mesh-representationer används för olika ändamål och tillämpningar. För att sända polygonmaskor över nätverket används nätverksrepresentationer såsom "strömmande" och "progressiva" maskor. Volymnät skiljer sig från polygonnät genom att de uttryckligen representerar både ytan och volymen av en struktur, medan polygonnäten uttryckligen endast representerar ytan, inte volymen. Eftersom polygonnät används i stor utsträckning i datorgrafik, har strålspårning , kollisionsdetektering och stela kroppsdynamikalgoritmer utvecklats för dem .
Den matematiska motsvarigheten till polygonala maskor - ostrukturerade maskor - studeras med metoder för kombinatorisk geometri .
Objekt skapade med polygonmaskor måste lagra olika typer av element som hörn, kanter, ytor, polygoner och ytor. I många fall lagras endast hörn, kanter och antingen ytor eller polygoner. Renderaren kan bara stödja tresidiga ytor, så polygoner måste byggas från många av dem, som visas i fig. 1. Många renderare stödjer dock polygoner med fyra eller fler sidor, eller kan triangulera polygoner till trianglar i farten, vilket gör det onödigt att lagra nätet i triangulerad form. Också i vissa fall, som att modellera ett huvud, är det önskvärt att kunna skapa både tre- och fyrsidiga polygoner.
En vertex är en position tillsammans med annan information som färg, normalvektor och texturkoordinater. En kant är en förbindelse mellan två hörn. Ett ansikte är en sluten uppsättning kanter, där ett triangulärt ansikte har tre kanter och ett fyrkantigt ansikte har fyra. En polygon är en uppsättning koplanära (som ligger i samma plan) ytor. I system som stöder flersidiga ytor är polygoner och ytor likvärdiga. Men de flesta renderingshårdvara stöder bara ytor med tre eller fyra sidor, så polygoner representeras som flera ytor. Matematiskt kan ett polygonnät representeras som ett ostrukturerat nät, eller oriktad graf, med tillägg av geometri, form och topologiegenskaper.
Ytor , mer allmänt kallade utjämningsgrupper , är användbara men krävs inte för att gruppera jämna områden. Föreställ dig en cylinder med lock, till exempel en plåtburk. För jämn sidoskuggning bör alla normaler peka horisontellt från mitten, medan locknormaler bör peka i +/-(0,0,1) riktningar. Om de återges som en enda, Phong-skuggad yta, skulle veckpunkten ha felaktiga normaler. Därför behöver vi ett sätt att bestämma var vi ska sluta utjämna för att gruppera de släta delarna av nätet, på samma sätt som polygoner grupperar 3-sidiga ytor. Som ett alternativ till att tillhandahålla ytor/släta grupper, kan nätet innehålla annan information för att beräkna samma data, såsom en separeringsvinkel (polygoner med normaler över denna gräns behandlas antingen automatiskt som separata blandningsgrupper, eller så används någon teknik på kant mellan dem, såsom klyvning eller fasning). Dessutom är maskor med mycket hög upplösning mindre benägna att få problem som kräver utjämningsgrupper för att lösa, eftersom deras polygoner är så små att de inte behövs. Dessutom finns ett alternativ i möjligheten att helt enkelt ta bort själva ytorna från resten av nätet. Renderare försöker inte jämna ut kanter mellan icke sammanhängande polygoner.
Nätformatet kan också definiera andra användbara data. Grupper kan definieras som definierar individuella mesh-element och är användbara för att upprätta individuella delobjekt för skelettanimering eller enskilda motiv för icke-skelettanimering. Material är vanligtvis definierade , vilket gör att olika delar av nätet kan använda olika shaders när de renderas. De flesta nätformat förutsätter också UV-koordinater , som är en separat 2D-representation av nätet, "olindade" för att visa hur mycket av 2D-texturen som appliceras på olika nätpolygoner.
Polygonnät kan representeras på många sätt, med olika sätt att lagra hörn, kanter och ytor. De inkluderar:
Varje syn har sina egna fördelar och nackdelar. [ett]
Valet av datastruktur bestäms av applikationen, den erforderliga prestandan, storleken på datan och de operationer som ska utföras. Till exempel är det lättare att hantera trianglar än med allmänna polygoner, särskilt i beräkningsgeometri . För vissa operationer är det nödvändigt att ha snabb tillgång till topologisk information såsom kanter eller angränsande ytor; detta kräver mer komplexa strukturer såsom en "vingad" representation. Hårdvarurendering kräver kompakta, enkla strukturer; därför inkluderar lågnivå-API:er som DirectX och OpenGL vanligtvis en tabell med vinklar (triangelfläktar).
En vertexrepresentation beskriver ett objekt som en uppsättning av hörn kopplade till andra hörn. Detta är den enklaste representationen, men den används inte i stor utsträckning eftersom informationen om ansikte och kant inte uttrycks explicit. Därför är det nödvändigt att gå igenom all data för att generera en lista över ansikten för rendering. Dessutom är operationer på kanter och ytor inte lätta att utföra.
VI-nät drar dock nytta av låg minnesanvändning och effektiv transformation. Figur 2 visar ett exempel på en låda ritad med ett nät VI. Varje vertex indexerar sina närliggande hörn. Observera att de två sista hörnen, 8 och 9 i toppen och botten av rutan, har fyra sammankopplade hörn, inte fem. Huvudsystemet måste hantera ett godtyckligt antal hörn associerade med en given vertex.
För en mer detaljerad beskrivning av VP-maskor, se Smith (2006). [ett]
Ett nät som använder en lista med ansikten representerar ett objekt som en uppsättning ansikten och en uppsättning hörn. Detta är den mest använda representationen, och är den indata som vanligtvis accepteras av modern grafikhårdvara.
En ansiktslista är bättre för modellering än en vertexrepresentation eftersom den tillåter en explicit sökning efter hörn på ett ansikte och ansikten som omger en vertex. Figur 3 visar ett exempel på en nätlåda som använder en lista med ansikten. Vertex v5 är markerad för att visa kanterna som omger den. Observera att i det här exemplet måste varje ansikte ha 3 hörn. Detta betyder dock inte att varje vertex har samma antal omgivande ytor.
För rendering skickas ansiktet vanligtvis till GPU:n som en uppsättning vertexindex, och hörnen skickas som position/färg/normala strukturer (endast positionen anges i figuren). Därför kan formändringar, men inte geometriändringar, uppdateras dynamiskt genom att helt enkelt återsända vertexdata utan att uppdatera ansiktsanslutningen.
Modellering kräver enkel genomgång av alla strukturer. Med ett nät som använder en lista över ansikten är det väldigt lätt att hitta hörn på ett ansikte. Dessutom innehåller vertexlistan en lista över alla ansikten som är associerade med varje vertex. Till skillnad från vertexrepresentationen är både ytor och hörn explicit representerade, så att hitta angränsande ytor och hörn är konstant i tiden. Kanterna är dock inte explicit specificerade, så en sökning behövs fortfarande för att hitta alla kanter som omger en given kant. Andra dynamiska operationer, som att riva eller slå samman ett ansikte, är också knepigt med en lista med ansikten.
Winged Representation , som introducerades av Bruce Baumgart 1975, representerar explicit topparna, ytorna och kanterna på ett nät. Denna representation används ofta i modelleringsprogram för att ge högsta flexibilitet vid dynamisk modifiering av nätgeometri eftersom riv- och sammanfogningsoperationer kan utföras snabbt. Deras största nackdel är höga minneskrav och ökad komplexitet på grund av innehållet i många index.
Den bevingade representationen löser problemet med korsning från kant till kant och ger en ordnad uppsättning ansikten runt kanten. För varje given kant kan antalet utgående kanter vara godtyckligt. För att förenkla detta ger den bevingade representationen endast de fyra närmaste medurs och moturs kanterna i varje ände av kanten. Andra kanter kan förbigås gradvis. Därför liknar informationen om varje kant en fjäril, varför representationen kallas "vingad". Figur 4 visar ett exempel på en ruta i en "vingad" representation. Den fullständiga kantdatan består av två hörn (ändpunkter), två ytor (på varje sida) och fyra kanter ("vingar" på kanten).
Att rendera en bevingad representation med grafisk hårdvara kräver generering av en lista med ansiktsindex. Detta görs vanligtvis endast när geometrin ändras. Bevingad representation är idealisk för dynamisk geometri som ytuppdelning och interaktiv modellering eftersom nätförändringar kan inträffa lokalt. Att gå runt nätet, vilket kan vara användbart för kollisionsdetektering, kan göras effektivt.
Se Baumgart (1975) för detaljer [2]
| Drift | Vertex representation | Ansiktslista | "vingad" prestation | ||
|---|---|---|---|---|---|
| VV | Alla hörn runt hörnet | Klart | V → f1, f2, f3, … → v1, v2, v3, … | V → e1, e2, e3, … → v1, v2, v3, … | |
| EF | Alla kanter av ett ansikte | F(a, b, c) → {a, b}, {b, c}, {a, c} | F → {a, b}, {b, c}, {a, c} | Klart | |
| VF | Alla hörn av ett ansikte | F(a,b,c) → {a,b,c} | Klart | F → el, e2, e3 → a, b, c | |
| FV | Alla kanter runt toppen | Parsökning | Klart | V → e1, e2, e3 → f1, f2, f3, … | |
| EV | Alla kanter runt spetsen | V → {v, v1}, {v, v2}, {v, v3}, … | V → f1, f2, f3, … → v1, v2, v3, … | Klart | |
| F.E. | Båda kanterna av kanten | Listjämförelse | Listjämförelse | Klart | |
| VE | Båda kanten av kanten | E(a, b) → {a, b} | E(a, b) → {a, b} | Klart | |
| Flook | Hitta ansikte med givna hörn | F(a,b,c) → {a,b,c} | Skärning av set v1,v2,v3 | Skärning av set v1,v2,v3 | |
| Minnesstorlek | V*avg(V,V) | 3F + V*genomsnitt(F,V) | 3F + 8E + V*avg(E,V) | ||
| Exempel med 10 hörn, 16 ytor, 24 kanter: | |||||
| 10 * 5 = 50 | 3*16 + 10*5 = 98 | 3*16 + 8*24 + 10*5 = 290 | |||
| Figur 5: Sammanfattning av Grid View Operations | |||||
I tabellen ovan indikerar uttryckligen att operationen kan utföras i konstant tid, eftersom data lagras direkt; listjämförelse indikerar att två listor måste jämföras för att utföra operationen; och parsökning indikerar att två indexsökningar ska utföras. Notationen avg(V,V) betyder det genomsnittliga antalet hörn kopplade till en given vertex; avg(E,V) är det genomsnittliga antalet kanter anslutna till en given vertex, och avg(F,V) är det genomsnittliga antalet ytor som är anslutna till en given vertex.
Beteckningen “V → f1, f2, f3, … → v1, v2, v3, …” visar att operationen kräver en genomgång runt flera element. Till exempel, för att få "alla hörn runt en given vertex V" med hjälp av en lista med ytor, måste man först hitta ytorna runt en given vertex V med hjälp av en lista med hörn. Sedan, från dessa ansikten, med hjälp av listan över ansikten, hitta hörnen runt dem. Observera att den bevingade representationen lagrar nästan all information explicit, och andra operationer korsar alltid kanten först för att få mer information. En vertexvy är den enda vy som explicit lagrar angränsande hörn av en given vertex.
När komplexiteten i representationerna ökar (från vänster till höger i sammanfattningen), ökar mängden lagrad information explicit. Detta ger mer direkt, tidskonstant tillgång till genomgången och topologin för de olika elementen, men till priset av mer minne för att lagra indexen på rätt sätt.
Som en allmän regel används ansiktslistmaskor närhelst ett objekt behöver renderas av hårdvara som inte ändrar geometrin (anslutningar) men som kan deformeras eller transformeras (vertexpositioner), till exempel vid rendering av statiska eller transformerande objekt i realtid. Den "vingade" representationen används när geometrin ändras, till exempel i interaktiva modelleringspaket eller för att beräkna uppdelade ytor. Vertexvy är idealisk för effektiva, komplexa ändringar av geometri eller topologi, så länge som hårdvaruåtergivning inte är viktigt.
Streammaskor lagrar ansikten på ett ordnat men oberoende sätt så att nätet kan skickas i bitar. Ordningen på ytorna kan vara rumslig, spektral eller baserad på andra meshegenskaper. Med strömmande maskor kan du göra mycket stora maskor även när de fortfarande laddas.
Progressiva mesh ger vertex- och ansiktsdata med ökande detaljnivåer. Till skillnad från flödesmaskor ger progressiva maskor den övergripande formen på hela objektet, men på en låg detaljnivå. Ytterligare data, nya kanter och ytor, ökar successivt maskdetaljer.
Normala maskor förmedlar gradvisa nätförändringar som en uppsättning normala förskjutningar från basnätet. Med denna teknik visar en serie texturer de önskade inkrementella förändringarna. Normala rutnät är kompakta eftersom endast ett skalärt värde behövs för att uttrycka förskjutningen. Tekniken kräver dock en serie komplexa transformationer för att skapa skjuvningstexturer.
Polygonnät kan lagras i en mängd olika filformat :