O plasă poligonală ( jar. ochiuri din poligonul englezesc mesh ) este o colecție de vârfuri, muchii și fețe care definesc forma unui obiect poliedric în grafica computerizată tridimensională și modelarea volumetrică. Fețele sunt, de obicei , triunghiuri , quad -uri sau alte poligoane convexe simple (poligoane), deoarece acest lucru simplifică redarea , dar rețelele pot fi compuse și din cele mai comune poligoane concave .[ clarifica ] , sau poligoane cu găuri.
Doctrina grilelor poligonale este o subsecțiune mare a graficii pe computer și modelării geometrice. Numeroasele operații efectuate pe rețele pot include algebră booleană , netezire, simplificare și multe altele. Diferite reprezentări de plasă sunt utilizate pentru diferite scopuri și aplicații. Pentru a transmite ochiuri poligonale prin rețea, sunt utilizate reprezentări de rețea, cum ar fi rețelele „streaming” și „progresive”. Ochiurile de volum diferă de ochiurile poligonale prin faptul că reprezintă în mod explicit atât suprafața, cât și volumul unei structuri, în timp ce ochiurile poligonale reprezintă în mod explicit doar suprafața, nu volumul. Deoarece rețelele poligonale sunt utilizate pe scară largă în grafica computerizată, pentru ele au fost dezvoltați algoritmi de urmărire a razei , de detectare a coliziunilor și de dinamică a corpului rigid .
Echivalentul matematic al ochiurilor poligonale - ochiurile nestructurate - sunt studiate prin metode de geometrie combinatorie .
Obiectele create cu rețele poligonale trebuie să stocheze diferite tipuri de elemente, cum ar fi vârfuri, muchii, fețe, poligoane și suprafețe. În multe cazuri, sunt stocate doar vârfurile, muchiile și fie fețele, fie poligoane. Rendererul poate suporta doar fețe cu trei fețe, așa că poligoane trebuie construite din multe dintre ele, așa cum se arată în Fig. 1. Cu toate acestea, multe dispozitive de redare acceptă poligoane cu patru sau mai multe laturi sau sunt capabile să triunghiuleze poligoane în triunghiuri din mers, făcând inutilă stocarea rețelei într-o formă triangulată. De asemenea, în unele cazuri, cum ar fi modelarea unui cap, este de dorit să se poată crea atât poligoane cu trei, cât și cu patru laturi.
Un vârf este o poziție împreună cu alte informații precum culoarea, vectorul normal și coordonatele texturii. O muchie este o conexiune între două vârfuri. O față este un set închis de muchii, în care o față triunghiulară are trei muchii, iar o față pătrangulară are patru. Un poligon este un set de fețe coplanare (care se află în același plan). În sistemele care acceptă fețe cu mai multe fețe, poligoanele și fețele sunt echivalente. Cu toate acestea, majoritatea hardware-ului de randare acceptă doar fețe cu trei sau patru laturi, astfel încât poligoanele sunt reprezentate ca mai multe fețe. Din punct de vedere matematic, o plasă de poligon poate fi reprezentată ca o plasă nestructurată sau grafic nedirecționat, cu adăugarea de proprietăți de geometrie, formă și topologie.
Suprafețele , denumite mai frecvent grupuri de netezire , sunt utile, dar nu sunt necesare pentru gruparea zonelor netede. Imaginați-vă un cilindru cu capace, cum ar fi o cutie de tablă. Pentru umbrirea laterală netedă, toate normalele ar trebui să fie îndreptate orizontal din centru, în timp ce normalele capacului ar trebui să îndrepte în direcții +/-(0,0,1). Dacă sunt randate ca o singură suprafață, umbrită Phong , vârfurile cute ar avea normale incorecte. Prin urmare, avem nevoie de o modalitate de a determina unde să oprim netezirea pentru a grupa părțile netede ale rețelei, în același mod în care poligoanele grupează fețele cu 3 laturi. Ca o alternativă la furnizarea de suprafețe/grupuri netede, rețeaua poate conține alte informații pentru a calcula aceleași date, cum ar fi un unghi de separare (poligoane cu valori normale peste această limită sunt fie tratate automat ca grupuri de amestec separate, fie o anumită tehnică este aplicată la marginea dintre ele, cum ar fi despicarea sau teșirea). De asemenea, rețelele cu rezoluție foarte înaltă sunt mai puțin predispuse la probleme care necesită rezolvarea unor grupuri de netezire, deoarece poligoanele lor sunt atât de mici încât nu sunt necesare. În plus, există o alternativă în posibilitatea de a detașa pur și simplu suprafețele de restul plasei. Rendererii nu încearcă să netezească marginile între poligoane necontigue.
Formatul de plasă poate defini și alte date utile. Pot fi definite grupuri care definesc elemente de plasă individuale și sunt utile pentru stabilirea sub-obiectelor individuale pentru animația scheletică sau subiectele individuale pentru animația non-scheletică. Materialele sunt de obicei definite , permițând diferitelor părți ale rețelei să utilizeze diferite umbriri atunci când sunt randate. Majoritatea formatelor de plasă presupun, de asemenea , coordonate UV , care sunt o reprezentare 2D separată a plasei, „desfăcută” pentru a arăta cât de mult din textura 2D este aplicată la diferite poligoane de plasă.
Ochiurile poligonale pot fi reprezentate în mai multe moduri, folosind diferite moduri de a stoca vârfuri, muchii și fețe. Ei includ:
Fiecare vedere are propriile sale avantaje și dezavantaje. [unu]
Alegerea structurii datelor este determinată de aplicație, de performanța necesară, de dimensiunea datelor și de operațiunile care trebuie efectuate. De exemplu, este mai ușor să te ocupi de triunghiuri decât de poligoane generale, în special în geometria computațională . Pentru anumite operații, este necesar să aveți acces rapid la informații topologice precum muchiile sau fețele învecinate; aceasta necesită structuri mai complexe, cum ar fi o reprezentare „înaripată”. Redarea hardware necesită structuri compacte, simple; prin urmare, API-urile de nivel scăzut, cum ar fi DirectX și OpenGL , includ de obicei un tabel de unghiuri (ventilatoare triunghiulare).
O reprezentare de vârf descrie un obiect ca un set de vârfuri conectate la alte vârfuri. Aceasta este cea mai simplă reprezentare, dar nu este utilizată pe scară largă deoarece informațiile față și marginea nu sunt exprimate în mod explicit. Prin urmare, este necesar să parcurgeți toate datele pentru a genera o listă de fețe pentru randare. În plus, operațiile pe margini și fețe nu sunt ușor de efectuat.
Cu toate acestea, rețelele VI beneficiază de utilizarea redusă a memoriei și transformarea eficientă. Figura 2 prezintă un exemplu de casetă desenată folosind o plasă VI. Fiecare vârf își indexează vârfurile învecinate. Rețineți că ultimele două vârfuri, 8 și 9 din partea de sus și de jos a casetei, au patru vârfuri conectate, nu cinci. Sistemul principal trebuie să gestioneze un număr arbitrar de vârfuri asociate cu orice vârf dat.
Pentru o descriere mai detaliată a ochiurilor VP, a se vedea Smith (2006). [unu]
O plasă care utilizează o listă de fețe reprezintă un obiect ca un set de fețe și un set de vârfuri. Aceasta este reprezentarea cea mai utilizată, fiind intrarea acceptată de obicei de hardware-ul grafic modern.
O listă de fețe este mai bună pentru modelare decât o reprezentare a vârfurilor, deoarece permite o căutare explicită a nodurilor unei fețe și a fețelor din jurul unui vârf. Figura 3 prezintă un exemplu de casetă de plasă folosind o listă de fețe. Vertex v5 este evidențiat pentru a afișa marginile care îl înconjoară. Rețineți că în acest exemplu, fiecare față trebuie să aibă 3 vârfuri. Totuși, acest lucru nu înseamnă că fiecare vârf are același număr de fețe înconjurătoare.
Pentru randare, fața este de obicei trimisă la GPU ca un set de indici de vârfuri, iar vârfurile sunt trimise ca poziție/culoare/structuri normale (în figură este dată doar poziția). Prin urmare, modificările de formă, dar nu modificările de geometrie, pot fi actualizate dinamic prin simpla retransmitere a datelor de vârf fără a actualiza conectivitatea feței.
Modelarea necesită parcurgerea ușoară a tuturor structurilor. Cu o plasă care folosește o listă de fețe, este foarte ușor să găsești vârfurile unei fețe. De asemenea, lista de vârfuri conține o listă a tuturor fețelor asociate fiecărui vârf. Spre deosebire de reprezentarea vârfurilor, atât fețele, cât și vârfurile sunt reprezentate în mod explicit, astfel încât găsirea fețelor și a vârfurilor învecinate este constantă în timp. Cu toate acestea, muchiile nu sunt specificate în mod explicit, așa că este încă necesară o căutare pentru a găsi toate muchiile care înconjoară o anumită muchie. Alte operațiuni dinamice, cum ar fi ruperea sau îmbinarea unei fețe, sunt, de asemenea, dificile cu o listă de fețe.
Introdusă de Bruce Baumgart în 1975, Reprezentarea aripată reprezintă în mod explicit vârfurile, fețele și marginile unei rețele. Această reprezentare este utilizată pe scară largă în programele de modelare pentru a oferi cea mai mare flexibilitate în modificarea dinamică a geometriei rețelei, deoarece operațiunile de rupere și îmbinare pot fi efectuate rapid. Principalul lor dezavantaj este cerințele mari de memorie și complexitatea crescută datorită conținutului multor indici.
Reprezentarea înaripată rezolvă problema traversării de la margine la margine și oferă un set ordonat de fețe în jurul marginii. Pentru orice muchie dată, numărul de muchii de ieșire poate fi arbitrar. Pentru a simplifica acest lucru, reprezentarea înaripată oferă doar cele patru margini cele mai apropiate în sensul acelor de ceasornic și în sens invers acelor de ceasornic la fiecare capăt al muchiei. Alte margini pot fi ocolite treptat. Prin urmare, informațiile despre fiecare margine seamănă cu un fluture, motiv pentru care reprezentarea se numește „aripată”. Figura 4 prezintă un exemplu de cutie într-o reprezentare „înaripată”. Datele complete ale muchiei constau din două vârfuri (puncte de capăt), două fețe (pe fiecare parte) și patru muchii ("aripi" ale muchiei).
Redarea unei reprezentări înaripate prin hardware-ul grafic necesită generarea unei liste de indici de fețe. Acest lucru se face de obicei numai atunci când geometria se schimbă. Reprezentarea cu aripi este ideală pentru geometria dinamică, cum ar fi subdiviziunea suprafeței și modelarea interactivă, deoarece modificările de plasă pot avea loc local. Plimbarea în jurul rețelei, care poate fi utilă pentru detectarea coliziunilor, se poate face eficient.
Vezi Baumgart (1975) pentru detalii [2]
| Operațiune | Reprezentarea vârfurilor | Lista de fețe | performanță „înaripată”. | ||
|---|---|---|---|---|---|
| VV | Toate vârfurile din jurul vârfului | Clar | V → f1, f2, f3, … → v1, v2, v3, … | V → e1, e2, e3, … → v1, v2, v3, … | |
| EF | Toate marginile unei fețe | F(a, b, c) → {a, b}, {b, c}, {a, c} | F → {a, b}, {b, c}, {a, c} | Clar | |
| VF | Toate vârfurile unei fețe | F(a,b,c) → {a,b,c} | Clar | F → e1, e2, e3 → a, b, c | |
| FV | Toate marginile din jurul vârfului | Căutare pereche | Clar | V → e1, e2, e3 → f1, f2, f3, … | |
| EV | Toate marginile din jurul vârfului | V → {v, v1}, {v, v2}, {v, v3}, … | V → f1, f2, f3, … → v1, v2, v3, … | Clar | |
| F.E. | Ambele margini ale marginii | Comparație de liste | Comparație de liste | Clar | |
| VE | Ambele vârfuri ale muchiei | E(a, b) → {a, b} | E(a, b) → {a, b} | Clar | |
| Flook | Găsiți fața cu vârfuri date | F(a,b,c) → {a,b,c} | Intersecția mulțimilor v1,v2,v3 | Intersecția mulțimilor v1,v2,v3 | |
| Capacitate de memorie | V*medie(V,V) | 3F + V*medie (F,V) | 3F + 8E + V*medie(E,V) | ||
| Exemplu cu 10 vârfuri, 16 fețe, 24 de muchii: | |||||
| 10 * 5 = 50 | 3*16 + 10*5 = 98 | 3*16 + 8*24 + 10*5 = 290 | |||
| Figura 5: Rezumatul operațiunilor de vizualizare grilă | |||||
În tabelul de mai sus, indică în mod explicit că operația poate fi efectuată în timp constant, deoarece datele sunt stocate direct; compararea listelor indică faptul că două liste trebuie comparate pentru a efectua operația; iar căutarea perechilor indică faptul că urmează să fie efectuate două căutări de index. Notația avg(V,V) înseamnă numărul mediu de vârfuri conectate la un vârf dat; avg(E,V) este numărul mediu de muchii conectate la un anumit vârf, iar avg(F,V) este numărul mediu de fețe conectate la un anumit vârf.
Denumirea „V → f1, f2, f3, … → v1, v2, v3, …” arată că operația necesită o parcurgere în jurul mai multor elemente. De exemplu, pentru a obține „toate nodurile din jurul unui anumit vârf V” folosind o listă de fețe, trebuie mai întâi să găsiți fețele din jurul unui anumit vârf V folosind o listă de vârfuri. Apoi, din aceste fețe, folosind lista de fețe, găsiți vârfurile din jurul lor. Rețineți că reprezentarea înaripată stochează aproape toate informațiile în mod explicit, iar alte operațiuni traversează întotdeauna marginea întâi pentru a obține mai multe informații. O vedere de vârf este singura vizualizare care stochează în mod explicit vârfurile învecinate ale unui punct dat.
Pe măsură ce complexitatea reprezentărilor crește (de la stânga la dreapta în rezumat), cantitatea de informații stocate crește în mod explicit. Acest lucru oferă un acces mai direct, constant în timp, la traversarea și topologia diferitelor elemente, dar cu prețul unei mai multe memorie pentru a stoca în mod corespunzător indicii.
Ca regulă generală, rețelele listei de fețe sunt folosite ori de câte ori un obiect trebuie redat de hardware care nu modifică geometria (conexiunile), dar se poate deforma sau transforma (pozițiile vârfurilor), cum ar fi redarea statică sau transformarea obiectelor în timp real. Reprezentarea „înaripată” este utilizată atunci când geometria se modifică, de exemplu în pachetele de modelare interactivă sau pentru a calcula suprafețe subdivizate. Vizualizarea Vertex este ideală pentru modificări eficiente și complexe ale geometriei sau topologiei, atâta timp cât randarea hardware nu este importantă.
Mesh- urile stream stochează fețele într-un mod ordonat, dar independent, astfel încât plasa să poată fi trimisă în bucăți. Ordinea fețelor poate fi spațială, spectrală sau bazată pe alte proprietăți ale rețelei. Rețelele de difuzare vă permit să redați rețele foarte mari chiar și în timp ce acestea încă se încarcă.
Rețelele progresive oferă date de vârf și față cu niveluri crescânde de detaliu. Spre deosebire de ochiurile de flux , ochiurile progresive dau forma generală a întregului obiect, dar la un nivel scăzut de detaliu. Date suplimentare, margini și fețe noi, măresc progresiv detaliile rețelei.
Rețelele normale transmit modificări treptate ale rețelei ca un set de decalaje normale față de rețeaua de bază. Cu această tehnică, o serie de texturi afișează modificările incrementale dorite. Grilele normale sunt compacte deoarece este necesară o singură valoare scalară pentru a exprima deplasarea. Cu toate acestea, tehnica necesită o serie de transformări complexe pentru a crea texturi de forfecare.
Rețelele poligonale pot fi stocate într-o varietate de formate de fișiere :