Et polygonnet ( jar. mesh fra det engelske polygon mesh ) er en samling af hjørner, kanter og flader, der definerer formen af et polyhedralt objekt i tredimensionel computergrafik og volumetrisk modellering. Ansigter er normalt trekanter , firkanter eller andre simple konvekse polygoner (polygoner), da dette forenkler gengivelsen , men masker kan også være sammensat af de mest almindelige konkave polygoner .[ ryd op ] eller polygoner med huller.
Læren om polygonale gitter er en stor undersektion af computergrafik og geometrisk modellering. De mange operationer, der udføres på masker, kan omfatte boolsk algebra , udjævning, forenkling og mange andre. Forskellige mesh-repræsentationer bruges til forskellige formål og anvendelser. For at transmittere polygonmasker over netværket bruges netværksrepræsentationer såsom "streaming" og "progressive" masker. Volumenmasker adskiller sig fra polygonmasker ved, at de eksplicit repræsenterer både overfladen og volumen af en struktur, mens polygonmasker eksplicit kun repræsenterer overfladen, ikke volumenet. Da polygonmasker er meget udbredt i computergrafik, er der udviklet algoritmer til strålesporing , kollisionsdetektion og stiv kropsdynamik til dem .
Den matematiske ækvivalent af polygonale masker - ustrukturerede masker - studeres ved metoder til kombinatorisk geometri .
Objekter, der er oprettet med polygonmasker, skal gemme forskellige typer elementer såsom hjørner, kanter, flader, polygoner og overflader. I mange tilfælde gemmes kun hjørner, kanter og enten flader eller polygoner. Renderen kan kun understøtte tresidede flader, så polygoner skal bygges af mange af dem, som vist i fig. 1. Mange renderere understøtter dog polygoner med fire eller flere sider eller er i stand til at triangulere polygoner til trekanter i farten, hvilket gør det unødvendigt at gemme nettet i en trianguleret form. Også i nogle tilfælde, såsom modellering af et hoved, er det ønskeligt at kunne skabe både tre- og firesidede polygoner.
Et toppunkt er en position sammen med anden information såsom farve, normalvektor og teksturkoordinater. En kant er en forbindelse mellem to hjørner. Et ansigt er et lukket sæt kanter, hvor en trekantet flade har tre kanter, og en firkantet flade har fire. En polygon er et sæt koplanære (ligger i samme plan) flader. I systemer, der understøtter flersidede flader, er polygoner og flader ækvivalente. De fleste gengivelseshardware understøtter dog kun flader med tre eller fire sider, så polygoner er repræsenteret som flere flader. Matematisk kan et polygonnet repræsenteres som et ustruktureret net eller en urettet graf med tilføjelse af geometri, form og topologiegenskaber.
Overflader , mere almindeligt omtalt som udjævningsgrupper , er nyttige, men ikke nødvendige til at gruppere glatte områder. Forestil dig en cylinder med låg, såsom en dåse. For jævn sideskygge skal alle normaler pege vandret fra midten, mens lågnormaler skal pege i +/-(0,0,1) retninger. Hvis de gengives som en enkelt, Phong-skygget overflade, ville foldens toppunkter have forkerte normaler. Derfor har vi brug for en måde at bestemme, hvor vi skal stoppe udglatning for at gruppere de glatte dele af nettet, på samme måde som polygoner grupperer 3-sidede flader. Som et alternativ til at give overflader/glatte grupper, kan nettet indeholde anden information til at beregne de samme data, såsom en adskillelsesvinkel (polygoner med normaler over denne grænse behandles enten automatisk som separate blandingsgrupper, eller en eller anden teknik anvendes på kant mellem dem, såsom opdeling eller affasning). Også mesh med meget høj opløsning er mindre tilbøjelige til problemer, der kræver udjævningsgrupper at løse, da deres polygoner er så små, at de ikke er nødvendige. Derudover findes der et alternativ i muligheden for blot at løsne selve overfladerne fra resten af nettet. Renderere forsøger ikke at udglatte kanter mellem ikke-sammenhængende polygoner.
Mesh-formatet kan også definere andre nyttige data. Der kan defineres grupper , der definerer individuelle mesh-elementer og er nyttige til at etablere individuelle underobjekter til skeletanimation eller individuelle emner til ikke-skeletanimation. Materialer er normalt defineret , hvilket gør det muligt for forskellige dele af nettet at bruge forskellige shaders, når de gengives. De fleste mesh-formater antager også UV-koordinater , som er en separat 2D-repræsentation af masken, "udpakket" for at vise, hvor meget af 2D-teksturen, der anvendes på forskellige mesh-polygoner.
Polygonmasker kan repræsenteres på mange måder ved at bruge forskellige måder til at gemme hjørner, kanter og flader. De omfatter:
Hver udsigt har sine egne fordele og ulemper. [en]
Valget af datastruktur bestemmes af applikationen, den nødvendige ydeevne, størrelsen af dataene og de operationer, der skal udføres. For eksempel er det lettere at håndtere trekanter end med generelle polygoner, især i beregningsgeometri . For visse operationer er det nødvendigt at have hurtig adgang til topologisk information såsom kanter eller naboflader; dette kræver mere komplekse strukturer såsom en "vinget" repræsentation. Hardwaregengivelse kræver kompakte, enkle strukturer; derfor inkluderer lav-niveau API'er såsom DirectX og OpenGL normalt en tabel med vinkler (trekant fans).
En toppunktsrepræsentation beskriver et objekt som et sæt af toppunkter forbundet med andre toppunkter. Dette er den enkleste repræsentation, men den er ikke udbredt, fordi ansigts- og kantinformationen ikke udtrykkes eksplicit. Derfor er det nødvendigt at gennemgå alle data for at generere en liste over ansigter til gengivelse. Derudover er operationer på kanter og flader ikke let at udføre.
VI-masker drager dog fordel af lavt hukommelsesforbrug og effektiv transformation. Figur 2 viser et eksempel på en kasse tegnet med et net VI. Hvert toppunkt indekserer dets tilstødende toppunkter. Bemærk, at de sidste to hjørner, 8 og 9 i toppen og bunden af boksen, har fire forbundne hjørner, ikke fem. Hovedsystemet skal håndtere et vilkårligt antal knudepunkter, der er knyttet til et givet knudepunkt.
For en mere detaljeret beskrivelse af VP-masker, se Smith (2006). [en]
Et net, der bruger en liste over ansigter, repræsenterer et objekt som et sæt ansigter og et sæt hjørner. Dette er den mest udbredte repræsentation, idet input typisk accepteres af moderne grafikhardware.
En ansigtsliste er bedre til modellering end en toppunktsrepræsentation, idet den tillader en eksplicit søgning efter hjørnerne af et ansigt og de ansigter, der omgiver et toppunkt. Figur 3 viser et eksempel på en mesh-boks, der bruger en liste over ansigter. Vertex v5 er fremhævet for at vise kanterne, der omgiver den. Bemærk, at i dette eksempel skal hvert ansigt have 3 spidser. Dette betyder dog ikke, at hvert toppunkt har det samme antal omgivende flader.
Til gengivelse sendes ansigtet normalt til GPU'en som et sæt topindekser, og hjørnerne sendes som position/farve/normale strukturer (kun positionen er angivet i figuren). Derfor kan formændringer, men ikke geometriændringer, opdateres dynamisk ved blot at gentransmittere toppunktsdataene uden at opdatere ansigtsforbindelsen.
Modellering kræver let gennemkøring af alle strukturer. Med et net, der bruger en liste over ansigter, er det meget nemt at finde hjørnerne af et ansigt. Toplisten indeholder også en liste over alle ansigter, der er knyttet til hvert toppunkt. I modsætning til toppunktrepræsentationen er både flader og toppunkter eksplicit repræsenteret, så det at finde naboflader og toppunkter er konstant i tid. Kanterne er dog ikke eksplicit specificeret, så en søgning er stadig nødvendig for at finde alle de kanter, der omgiver en given kant. Andre dynamiske handlinger, såsom at rive eller flette et ansigt, er også vanskelige med en liste over ansigter.
Introduceret af Bruce Baumgart i 1975 repræsenterer Winged Representation eksplicit hjørnerne, ansigterne og kanterne af et net. Denne repræsentation bruges i vid udstrækning i modelleringsprogrammer for at give den højeste fleksibilitet i dynamisk ændring af mesh-geometri, fordi rive- og fletteoperationer kan udføres hurtigt. Deres største ulempe er høje hukommelseskrav og øget kompleksitet på grund af indholdet af mange indekser.
Den bevingede repræsentation løser kant-til-kant traverseringsproblemet og giver et ordnet sæt flader rundt om kanten. For enhver given kant kan antallet af udgående kanter være vilkårligt. For at forenkle dette giver den vingede repræsentation kun de fire nærmeste kanter med uret og mod uret i hver ende af kanten. Andre kanter kan omgås gradvist. Derfor ligner informationen om hver kant en sommerfugl, hvorfor repræsentationen kaldes "vinget". Figur 4 viser et eksempel på en boks i en "vinget" repræsentation. De komplette kantdata består af to spidser (endepunkter), to flader (på hver side) og fire kanter ("vinger" af kanten).
Gengivelse af en bevinget repræsentation ved hjælp af grafisk hardware kræver generering af en liste over ansigtsindekser. Dette gøres normalt kun, når geometrien ændres. Bevinget repræsentation er ideel til dynamisk geometri såsom overfladeinddeling og interaktiv modellering, fordi maskeændringer kan forekomme lokalt. At gå rundt i nettet, som kan være nyttigt til kollisionsdetektion, kan gøres effektivt.
Se Baumgart (1975) for detaljer [2]
| Operation | Vertex repræsentation | Ansigtsliste | "vinget" præstation | ||
|---|---|---|---|---|---|
| VV | Alle hjørner omkring toppunktet | Klart | V → f1, f2, f3, … → v1, v2, v3, … | V → e1, e2, e3, … → v1, v2, v3, … | |
| EF | Alle kanter af et ansigt | F(a, b, c) → {a, b}, {b, c}, {a, c} | F → {a, b}, {b, c}, {a, c} | Klart | |
| VF | Alle hjørner af et ansigt | F(a,b,c) → {a,b,c} | Klart | F → e1, e2, e3 → a, b, c | |
| FV | Alle kanter rundt om toppen | Parsøgning | Klart | V → e1, e2, e3 → f1, f2, f3, … | |
| EV | Alle kanter rundt om toppunktet | V → {v, v1}, {v, v2}, {v, v3}, … | V → f1, f2, f3, … → v1, v2, v3, … | Klart | |
| F.E. | Begge kanter af kanten | Liste sammenligning | Liste sammenligning | Klart | |
| VE | Begge spidser af kanten | E(a, b) → {a, b} | E(a, b) → {a, b} | Klart | |
| Flook | Find ansigt med givne hjørner | F(a,b,c) → {a,b,c} | Skæring af sæt v1,v2,v3 | Skæring af sæt v1,v2,v3 | |
| Hukommelsesstørrelse | V*gennemsnit(V,V) | 3F + V*gennemsnit(F,V) | 3F + 8E + V*gennemsnit(E,V) | ||
| Eksempel med 10 hjørner, 16 flader, 24 kanter: | |||||
| 10 * 5 = 50 | 3*16 + 10*5 = 98 | 3*16 + 8*24 + 10*5 = 290 | |||
| Figur 5: Oversigt over Grid View-operationer | |||||
I tabellen ovenfor angiver det eksplicit , at operationen kan udføres i konstant tid, da dataene er lagret direkte; listesammenligning angiver, at to lister skal sammenlignes for at udføre operationen; og parsøgning angiver, at der skal udføres to indekssøgninger. Notationen avg(V,V) betyder det gennemsnitlige antal toppunkter forbundet med et givet toppunkt; avg(E,V) er det gennemsnitlige antal kanter forbundet til et givet toppunkt, og avg(F,V) er det gennemsnitlige antal flader forbundet til et givet toppunkt.
Betegnelsen “V → f1, f2, f3, … → v1, v2, v3, …” viser, at operationen kræver en gennemkørsel omkring flere elementer. For eksempel, for at få "alle hjørner omkring en given toppunkt V" ved hjælp af en liste over ansigter, skal man først finde ansigterne omkring en given toppunkt V ved hjælp af en liste af toppunkter. Derefter, fra disse ansigter, ved hjælp af listen over ansigter, find hjørnerne omkring dem. Bemærk, at den vingede repræsentation lagrer næsten al information eksplicit, og andre operationer krydser altid kanten først for at få mere information. En toppunktsvisning er den eneste visning, der eksplicit lagrer de tilstødende toppunkter af et givet toppunkt.
Efterhånden som kompleksiteten af repræsentationerne øges (fra venstre mod højre i oversigten), øges mængden af lagret information eksplicit. Dette giver mere direkte, tidskonstant adgang til gennemgangen og topologien af de forskellige elementer, men på bekostning af mere hukommelse til at gemme indekserne korrekt.
Som en generel regel bruges ansigtslistemasker, når et objekt skal gengives af hardware, der ikke ændrer geometrien (forbindelser), men kan deformeres eller transformeres (toppositioner), såsom ved gengivelse af statiske eller transformerende objekter i realtid. Den "vingede" repræsentation bruges, når geometrien ændres, for eksempel i interaktive modelleringspakker eller til at beregne underinddelte overflader. Vertex-visning er ideel til effektive, komplekse ændringer af geometri eller topologi, så længe hardwaregengivelse ikke er vigtig.
Stream-masker gemmer ansigter på en velordnet, men uafhængig måde, så nettet kan sendes i bidder. Rækkefølgen af ansigterne kan være rumlig, spektral eller baseret på andre maskeegenskaber. Streaming-masker giver dig mulighed for at gengive meget store masker, selv mens de stadig indlæses.
Progressive mesh giver top- og ansigtsdata med stigende detaljeringsniveauer. I modsætning til flowmasker giver progressive masker den overordnede form af hele objektet, men med et lavt detaljeringsniveau. Yderligere data, nye kanter og flader øger gradvist maskedetaljer.
Normale masker formidler gradvise maskeændringer som et sæt normale forskydninger fra basisnettet. Med denne teknik viser en række teksturer de ønskede trinvise ændringer. Normale gitter er kompakte, fordi kun én skalarværdi er nødvendig for at udtrykke forskydningen. Teknikken kræver dog en række komplekse transformationer for at skabe forskydningsteksturer.
Polygonmasker kan gemmes i en række forskellige filformater :