Am tot cautat pe net informatii despre smoothing groups dar nu pot sa zic ca m-am lamurit. Ce sunt si cum se calculeaza normalele folosind smoothing groups?

PS. Am sters mesajul vechi dar nu s-a sters "de tot".

Daca te referi la smoothing groups din Max, atunci gasesti in 3ds Max SDK Programmer's Guide, la topicul: Computing Face and Vertex Normals

Smoothing groups e o tehnica prin care generezi normalele vertexilor folosindu-te de normalele fetelor din care face parte. Tehnica e oricum mult spus, e o adunare de normale.



In desenul de mai sus, vertexul X din prima poze are 2 normale, apartinind celor 2 fete pe care le share-uieste. La randare se va vedea ca trecerea intre cele 2 fete, a si b, nu e smooth, din cauza ca normalele interpolate pe toata lungimea fetelor nu-si schimba directia.

In poza 2, cele 2 normale ale vertexului X sint adunate, iar rezultanta lor este noua normala pentru vertexul X. Normala asta va fi interpolata la render time pe toata lungimea fetelor a si b, si cum va avea directia schimbata, va apare efectul de smooth.


Uite la normalele vertexilor din mijloc, fara sg (cea din stinga, cu 2 normale) si cu sg (din dreapta cu 1 normala). Dedesupt ai cum se randeaza top view. Cred ca este evidenta diferenta.

Ugh... am mutat si io mesajul atunci:




Descrierea scurta:
Smoothing Groups sunt o chestie care exista in taramul editoarelor (Max, Maya etc.), si nu ceva in Direct3D/GL. Ele decid cum sunt calculate normalele per vertex. (deci fie ca le folosesti, fie ca nu, iti iese acelasi format de vertex, insa pot iesi un numar diferit de vertecsi) Daca vrei sa ai o tranzitie "smooth" (spre exemplu, corp uman, masina, sfera, o sticla etc.) atunci vrei sa folosesti smoothing groops ca sa-ti iasa normalele frumos. Daca vrei colturi vizible (orice e patratos) nu folosesti smoothing groups.

Majoritatea obiectelor au cateva grupe separate de smoothing. Uite un "cort" facut dintr-un cilindru in Blender in aproximativ 2 secunde :-P



Puh ce colturos e, nu? Ar arata ca dracu in joc. Crede-ma, o singura normala aiurea iti face muci un model intreg cand pui shadere pe el. Hai sa punem un smoothing group pe poligoanele de la baza:



Ah, asa mai merge. Insa "acoperisul" tot e stricat.
Acum, daca nu ar exista smoothing groups, si ar fi doar pe tot modelul, global, ar iesi urmatoarea abominatie... :-P



Normale = stricate. Nu arata a cort.

Insa daca punem o grupa separata pt baza, si o grupa separata pt acoperis, iese in sfarsit ceva care arata "remotely" a cort




Deci, dupa cum ai observat in exemplele de mai sus, fara smoothing groops fiecare triunghi traieste de capu lui, iar modelul arata ca o adunatura de poligoane. Cu smoothing groups, triunghiurile vecine sunt legate intre ele de normale care tin cont de amandoua.



Uite un mic sfat care l-am prins facand Tillian Tribes: fuck triangles. Modeleaza numai din quad-uri (quad-uri in care toti vertecsii sunt coplanari, evident), asa iti ies normalele fara nici o bataie de cap.

In concluzie, sper ca te-am lamurit cu bazele smoothing groups. Daca esti artist, sigur e vre-un text (carte?) care acopera in detaliu. Smoothing groups sunt o chestie vitala si de baza, fara de care nu poti face un obiect obisnuit sa arate obisnuit. Daca esti programator, nu e problema ta. Doar zi-le artistilor sa nu mai masacreze modelele alea cu tranzitii de la quad-uri la triunghiuri; ori numa triunghiuri (bleahh) ori numa quad-uri. Decat daca nu cumva au chef sa aranjeze normalele de mana.. :-P

/LE:

Okay, dar cum anume calculez normalele folosind informatiile despre smoothing groups? Un pseudocod cu ceva explicatii m-ar ajuta...

Presupun ca vrei sa scrii un exportor, nu?

Hm, fura cod din alt exportor? :-p
Problema sigur sa mai rezolvat de o mie de ori.

Oricum o posibilitate e clara ca ziua: pentru fiecare vertex, daca apartine la mai mult de 1 triunghi, atunci, pt fiecare sub-grupa de triunghiuri, separate dupa smoothing group (cele fara sg sunt toate considerate independente), genereaza un vertex cu normala = media (?) dintre normalele triunghiurilor acelei sub-grupe. Incearca si tu...

Smoothing groups sunt pastrate intr-un array de id-uri catre fetele aflate in acel grup. Obtii array-ul de indecsi apoi ptr fiecare fata (triunghi) din acel grup gasesti triunghiurile vecine si vertecsii lor ce se unesc in acelasi punct, aduni normalele si la sfarsit faci media aritmetica...mai poti face si verificari de genul daca unghiul dintre 2 normale e mai mare de 60 de grade nu le mai faci smooth, dar informatiile astea ar trebui sa fie deja setate din model.

Of of, Internetul asta. Ti-au aratat doi oameni care-i smecheria cu smoothing groups. Cu poze. Este banal sa te prinzi singur cum se scrie codul pentru ce s-a desenat mai sus si te-ar ajuta mai tare sa descoperi singur decit sa-ti dea altcineva mura-n gura. Apuca-te de scris cod si trebuie sa-ti iasa in 5 minute. Singurul lucru care s-ar putea spune ca nu-i evident e cum gasesti normala "smoothed" plecind de la normalele fetelor, desi si asta ar trebui sa-ti dai seama cu un pix si o foaie dupa putin scarpinat in cap.

Apropo, vezi ca nu trebuie sa faci media aritmetica. Trebuie doar sa aduni vectorii si la sfirsit sa normalizezi. Impartirea aia la N pentru media aritmetica nu face nimic, deci nu-i nevoie sa o faci. Uneori se vorbeste de un fel de medie ponderata, de genul:

Nv = N1 * A1 + N2 * A2 + ...

unde Nv e normala care rezulta pentru vertex, N1, N2 etc. sint normalele fetelor, iar A1, A2 etc. sint suprafetele fetelor (observi ca impartirea lipseste si aici). Avantajele sint discutabile asa ca in practica nu prea se da nimeni in vint dupa varianta asta.

Cateodata trebuie explicat intr-un anume fel , altfel risti sa nu inteleaga nimic, ramane la matematica lui sa-si dea seama de ce nu trebuie impartit la N, cum de altfel e cazul multor operatii matematice folosite in jocuri.

    Cred ca am inteles. Am implementat si arata bine(folosind un algoritm simplu). Am testat folosind un cub, un torus si un cilindru. Am citit prin mai multe locuri si aveam impresia ca atunci cand se calculeaza normala pentru un vertex(fie V,vertex-ul) se ia in considerare doar normala triunghiului(fie A,triunghiul initial) din care face parte alaturi de normala triunghiului adiacent(fie B,triunghiul adiacent) fata de care are o latura comuna si care are minim un smoothing group comun cu triunghiul A.

    Se pare insa ca trebuie luate in considerare toate triunghiurile cu minim un smoothing group comun cu A care se intersecteaza cu A in V. Deci ar trebui sa gasesc in vectorul de fete(cate 3 indici pentru o fata spre vectorul de vertecsi) toate fetele care au unul din indici egal cu indexul vertexu-ului curent.

Pseudocod:

Liniile 1-3 au complexitatea : O(3*numarul_de_triunghiuri).
Liniile 5-8 pot avea complexitatea O(3*log(numarul_de_triunghiuri) daca se sorteaza in 3 vectori triunghiurile dupa: primul indice, al doilea indice, al treilea indice.(O(numarul_de_triunghiuri*log(numarul_de_triunghiuri) sa zicem ca ia sortarea).
Deci: O(3*numarul_de_triunghiuri)*O(3*log(numarul_de_triunghiuri)) = O(numarul_de_triunghiuri*log(numarul_de_triunghiuri))

Pentru liniile 5-8 se poate folosi si o tabela hash, cred ca ar putea fi mai rapid in unele circumstante dar ar putea consuma mai multa memorie. Voi cum faceti? Am inteles bine, ca rezultatele arata ok so far.

P.S. modficat algoritmul ca era prea ciudat scris

Pentru fiecare smoothing group parcurgi lista de triunghiuri care-i apartin. Pentru fiecare vertex gasit construiesti o lista de triunghiuri care folosesc acel vertex. Calculezi normala fiecarui triunghi si, folosind listele construite la pasul anterior, calculezi normala fiecarui vertex insumind normalele triunghiurilor. Timpul de rulare este aproximativ O(v+t), unde v este numarul de vertecsi si t e numarul de triunghiuri din mesh. De fapt v e inmultit cu un numar mic acolo, ca pentru fiecare vertex trebuie sa faci un numar de pasi egal cu numarul de fete care-l impart, tot timp liniar se cheama ca ai.

In practica pierzi o groaza de timp daca faci cite un array pentru fiecare vertex si te chinui sa le cresti cind ai de adaugat elemente (sau mai rau, o lista inlantuita). Ca sa fie mai usor, intii parcurgi lista de triunghiuri si numeri cite triunghiuri corespund fiecarui vertex. Dupa ce faci asta, poti aloca un array mare in care vei tine toate listele una dupa alta si-ti aranjezi niste indecsi (sau pointeri) spre inceputul fiecarei liste in array-ul mare. Asta duce timpul teoretic O(2*t + v), dar practic merge mai bine decit O(v+t) ala naiv cu jdemii de alocari de memorie.

Ideea este buna dar cat de mult inseamna o groaza de timp?

Probabil vor dura mai mult malloc()-urile decit tot restul codului.

LE: evident, poti sa aloci la inceput un array cu 3*numTriangles elemente din care sa servesti "alocarile" pentru listele de indecsi in loc sa le treci prin malloc(). Ceva de genul asta:

http://pastebin.com/f3f8d06d2

Codul aloca 36 de bytes per face si 16 per vertex (pe 32 de biti), deci pentru un smoothing group cu 100,000 de fete si 200,000 de triunghiuri ai nevoie de vreo 6.5 MB de RAM. De aici rezulta ca e OK sa faci asa pentru orice model de joc. E mult mai simplu decit aia cu sortari si hash-uri si ce vroiai sa faci. Timpul de rulare se deduce usor adunind limitele for-urilor si se observa ca-i liniar. Ultimul for face maxim 3*numVtx pasi din acelasi motiv din care ne permitem sa alocam 3*numVtx elemente in pool si sa stim ca vor fi intotdeauna suficiente (motiv care e tema pentru acasa daca nu te-ai prins deja).

PS: poate intr-o zi forumul nu va mai crede ca cineva incearca sa aduca Apocalipsa cu ajutorul caracterelor "mai mic" si "mai mare" si atunci vom putea scrie cod in post-uri.