• Estructura del model

 

 

Una malla de triangles es un conjunt connex de triangles. Si el nombre de triangles és prou gran, les malles poden representar amb suficient aproximació objectes curvats o cilindrics, superficies de Bézier, NURBs, etc.

El model més senzill d'un objecte representat per una malla de triangles és el format per dues llistes, una de triangles i una de vèrtexs:

• Cada triangle consta de tres punters a vèrtexs (a més d'altres informacions com color..)
• Cada vèrtex consta de les seves tres coordenades (x,y,z)


Les malles poden ser obertes o tancades. A les malles tancades, cada triangle té tres triangles adjacents a través de cada una de les seves arestes. En canvi, les malles obertes tenen vores, i les arestes de les vores delimiten només amb un triangle. Les malles tancades, si els triangles no s'intersecten, tanquen un volum i són fronteres de sòlids. En aquest cas, com que el nombre de semiarestes és tres cops el nombre de cares, es cumpleix (C és el nombre de cares, A és el nombre d'arestes i V el nombre de vèrtexs de la malla):

2 A = 3 C

D'altra banda, com que R=0, si suposem que S=1 i F=0, l'equació d'Euler ens diu que,

C + V = A + 2

Agrupant les dues equacions, tenim una relació entre el nombre de vèrtexs i el nombre de cares a tota malla tancada:

2 V = C + 4




• Generació de malles

 

 

Les malles triangulars es poden generar:
 

• Per subdivisió a partir de models de sòlids amb cares planes (poliedres). Els algorismes més coneguts són el de Doo & Sabin i el de Loop (veure referències al final d'aquesta pàgina
• Per generació d'isosuperficies a partir d'un model de voxels (veure Cignoni'00)
• Per facetització de superficies. Tot seguit donem un algorisme de facetització d'una superficie on umin <= u <= umax  i vmin <= v <= vmax. Existeixen algorismes más sofisticats, basats en una triangulació adaptativa i de Delaunay (veure Vigo'99)


var
   P:punt3D; V1, V2: PunterAVertex
   Vert:  taula [0..M]  de  PunterAVertex
   Vin:   taula [0..M]  de  PunterAVertex
fvar

CrearObjecteMalla ( Ob )
/* Crea una malla de 2*N*M triangles */
Per j  en  [0..M] fer
    u :=umin
    v := vmin + (vmax-vmin) * j / M
    P := SupBezier (npol,nps,n,TP,u,v)
    Vert[j] := InsertaVertex (P, Ob)
    Vin [j] := Vert [j]
fper
Per i  en  [1..N] fer
    u := umin + (umax-umin) * i / N
    P := SupBezier (npol,nps,n,TP,u,vmin)
    V1 := InsertaVertex (P, Ob)
    Per j  en  [1..M] fer
        v := vmin + (vmax-vmin) * j / M
        P := SupBezier (npol,nps,n,TP,u,v)
        V2 := InsertaVertex (P, Ob)
          InsertaTriangle ( V1, Vert[j-1], Vert[j], Ob )
          InsertaTriangle ( V1, Vert[j], V2, Ob )
        Vert[j-1] := V1
        V1 := V2
    fper
    Vert [M] := V2
fper

/* Aquest darrer bucle només cal si la superficie ha de ser tancada en direcció u */
Per j  en  [1..M] fer
    InsertaTriangle ( Vin[j-1], Vert[j-1], Vert[j], Ob )
    InsertaTriangle (Vin[j-1], Vert[j], Vin[j], Ob )
fper
 
 

• Simplificació

  Existeixen molts algorismes que redueixen el nombre de triangles d'una malla, obtenint una altra malla més simple i propera a la inicial. En alguns d'aquests algorismes es pot especificar una tolerància, i l'algorisme ens assegura que la malla simplificada es mantindrà a una distància sempre menor que la tolerància respecte a la malla inicial. Veure per exemple, El Sana'00. Veure també l'apartat específic del temari sobre simplificació (apartat 3.4).


 

• Tires de triangles (strips)

 

Si una malla de triangles es representa com una tira de triangles contigus, la informació que cal (un cop s'ha codificat el primer triangle de la tira) és simplement un vèrtex i un bit per triangle. Aquesta és una representació molt compacta, admesa per exemple per OpenGL. Existeixen algorismes eficients per a la conversió d'una malla en tires de triangles.Veure El-Sana'00.
 
 

• Compressió i transmissió progressiva

• Relació amb els models de punts i amb els models de volum
  

Tal com hem vist, una malla de triangles es representa habitualment amb dues llistes (o taules): una de triangles i una de vèrtexs. Cada triangle consta de tres punters a vèrtexs (a més d'altres informacions com color..), i cada vèrtex ve representat per les seves tres coordenades (x,y,z).

Un model de núvol de punts és simplement una taula o llista de punts. Cada punt pot tenir informació addicional a part de les seves coordenades, com pot ser el color, el seu vector normal, etc. La diferència bàsica amb una malla de triangles és que aqui no tenim informació sobre la connectivitat entre els punts.

Un model de volum (voxelització) és una taula que conté informació sobre una malla regular de N x N x N cel.les uniformes que divideixen un cub univers a l'espai. Aquesta malla  està formada per cel.les, totes elles del mateix tamany, que estan limitades per arestes i vèrtexs de la malla. Hi ha moltes variants de models de volum (codificació d'un o més objectes a través de la informació dins_objecte_k / fora als vèrtexs de la malla,  codificació d'un o més objectes a través de la informació dins_objecte_k / fora als vèrtexs de la malla i de la informació dels punts de tall i vectors normals entre la superficie dels objectes i les arestes de la malla, etc.). Aquí ens concretarem als models de volum que representen camps escalars i que guarden un valor escalar a cada un dels vèrtexs de la malla: taula [0..N, 0..N, 0..N] de float. Un cas particular dels models de volum que representen camps escalars són els camps de distàncies. En aquest cas, el valor que es guarda a cada vèrtex de la malla es el valor de la distància (amb signe o sense signe) a la superficie de l'objecte que estem representant. En canvi, direm que una voxelització és binaria si la informació a cada vèrtex és del tipus dins/fora.

Podem convertir una malla de triangles en un núvol de punts simplement eliminant la llista de triangles. En el cas de triangles massa grans, pot ser bó fer un mostreig més fí i generar punts dins de cada triangle.

Convertir en canvi un model de punts a una malla de triangles no és tant trivial. Es l'anomenat problema de la reconstrucció. Hi ha diverses solucions, com els algorismes dels Alpha Shapes (i derivats), els algorismes basats en la reducció d'una membrana discreta o els algorismes de Hornung i Kobbelt, basats el el càlcul del tall minimal  del camp de distàncies definit per una crosta discreta. Els núvols de punts es poden operar i visualitzar, vegeu per exemple el projecte PointShop: www.pointshop.com

El càlcul d'un model de volum (camp de distàncies) a partir d'una malla de triangles tampoc és complexe. El que cal és calcular la distància mínima desde cada punt de la malla als triangles de la malla. El càlcul es pot accelerar si es calcula primer la distància a la malla desde els vèrtexs de les cel.les de la malla que contenen triangles de la superficie, i després s'extenen aquests valors als altres vèrtexs de la malla.

Hi ha dos algorismes clàssics per passar d'un model de volum a una malla de triangles: l'algorisme de Marching Cubes i l'algorisme de Dual Contouring. Teniu més informació sobre aquests dos algorismes a l'apartat 2.5 del temari.

Els models de volum moltes vegades tenen interés com a model intermig per a certes operacions:

• reconstrucció de superficies a partir de núvols de punts
• reparació de models de malles de triangles
• simplificació de models de malles de triangles (apartat 3.4 del temari)
  

 

• Operacions booleanes entre malles


 Veiem un algorisme de principi de l'operació booleana entre dues malles triangulars O1, O2. Les malles poden ser obertes o tancades, pero han de ser orientades (els triangles han de tenir una orientació compatible). L'algorisme calcula la malla que conté O1+  i O2+ (la part de O1 externa a O2 i la part de O2 externa a O1), pero els altres algorismes serien idèntics:

Inillista (Ll1); Inillista (Ll2); IniLlista (Ar1); IniLlista (Ar2)
Per cada triangle t de O1 fer
    Si Intersecta (t, O2) llavors
        CalculaSubtriangles (t, O2, Ll)  /* Calcula els subtriangles de t a O2+ i els torna a Ll
        Inserta (Ll, Ll1 )
        InsertaPossibleArestaNoTallada_de_t_si_DinsDeO2Mes (t, Ll, Ar1)
    fsi
fper

mentre no buida ( Ar1) fer
    (a,t) := PrimeraAresta ( Ar1 )
    r := TriangleContigu (t,a,O1)
    Si NoHiEs (r, Ll1) llavors
        Inserta (r, Ll1)
        InsertaArestesRestantsDe_r (r, Ar1)
    fsi
fmentre

Per cada triangle t de O2 fer
    Si Intersecta (t, O1) llavors
        CalculaSubtriangles (t, O1, Ll)  /* Calcula els subtriangles de t a O1+ i els torna a Ll
        Inserta (Ll, Ll2 )
        InsertaPossibleArestaNoTallada_de_t_si_DinsDeO1Mes (t, Ll, Ar2)
    fsi
fper

mentre no buida ( Ar2) fer
    (a,t) := PrimeraAresta ( Ar2 )
    r := TriangleContigu (t,a,O2)
    Si NoHiEs (r, Ll2) llavors
        Inserta (r, Ll2)
        InsertaArestesRestantsDe_r (r, Ar2)
    fsi
fmentre

Observacions:

• La malla final està formada per tots els triangles de Ll1 i per tots els de Ll2.
• El triangle contigu a un triangle t a traves d'una certa aresta és molt fàcil de trobar si ampliem l'estructura de dades afegint a cada vèrtex la seva llista de cares
• La detecció de si un triangle és intersectat per l'altra malla és el punt critic de l'algorisme. Cal fer-ho de forma el més eficient possible. Una de les millors solucions és disposar d'un arbre octal (octree) per cada malla. Cada node terminal del octree conté una llista dels triangles que intersecten el cub corresponent al node. I cada triangle de la malla té informació de la llista de nodes que atravessa ( o bé cada vèrtex de la malla té un punter al node que el conté ).
• Es suposa que un triangle r és a la llista Ll1 si hi és ell o algun dels seus trossos tallats per l'altre malla

 

Cignoni,P., Ganovelli,F., Montani,C., Scopigno,R., "Reconstruction of Topologically Correct and Adaptive Trilinear Isosurfaces", Computers and Graphics Vol. 24, 2000, pp 399-418 (Generació de malles triangulars a partir de models volumètrics de voxels. Es una millora de l'algorisme de Marching Cubes)

 Vigo,M.,  Pla,N., Brunet,P., "Directional Adaptive Surface Triangulation",  Computer-Aided Geometric Design, Vol. 16, 1999, pp 107-126 (Generació de malles triangulars a partir d'una superficie, de forma adaptativa, creant més triangles a les zones més curvades)

Zorin,D., Schroeder,P., Sweldens,W., "Interactive Multiresolution Mesh Editing", ACM Computer Graphics, Proc. of Siggraph 1997, pp 259-268 (Algorisme sofisticat per editar malles de triangles, que incorpora multiresolució per poder editar versions simplificades del model. L'algorisme afegeix  automàticament els detalls al model editat)

Kobbelt,L.P., Bareuther,T., Seidel,H-P., "Multiresolution Shape Deformations for Meshes with Dynamic Vertex Connectivity", Computer Graphics Forum Vol. 19 (3), Proc. of Eurographics'00, 2000, pp 249-259 (Edició molt sofisticada de malles de triangles, amb multiresolució i modificació dinàmica de l'estructura de la malla)

Meek,D.S., Walton,D.J., "On Surface normal and Gaussian curvature approximations given data sampled from a smooth surface", Computer-Aided Geometric Design, Vol. 17, 2000, pp 521-543 (Càlcul del vector normal i de la curvatura gaussiana en superficies aproximades per malles)

Loop,C., "Smooth Subdivision Surfaces Based on Triangles", Master thesis, University of Utah, Dept. of Mathematics, 1987 (Algorisme de subdivisió de malles triangulars). Una millora de l'algorisme es pot trobar als proceedings del ACM Siggraph'1994, pàgines 295-302: Hoppe, DeRose, Duchamp, McDonald, Schweitzer, Stuetzle, "Piecewise Smooth Surface Reconstruction"

Doo,D., and Sabin,M., "Behaviour of Recursive Division Surfaces near Extraordinay Points", Computer-Aided Design, Vol. 10 (6), 1978, pp 256-360 (Algorisme de subdivisió de malles, no necessàriament triangulars)

Taubin,G., "A Signal Processing Approach to fair Surface Design", ACM Computer Graphics, Proc. of Siggraph 1995, pp 351-358 (Suavitzat de malles, per eliminar soroll i petites oscilacions)

El-Sana,J., Evans,F., Kalaiah,A., Varshney,A., Skiena,S., Azanli,E., "Efficient Computing and Updating Triangle Strips for Real-Time Rendering", Computer-Aided Design Vol. 32 (13), 2000, pp 753-772 (Simplificació de malles de triangles i generació eficient de tires - strips - de triangles)

Pajarola,R., Rossignac,J., Szymczak,A., "Implant Sprays: Compression of Progressive Tetrahedral Meshes", Proc. of IEEE Visualization, 1999 (Compressió i transmissió molt eficient de malles de triangles)