Interrogació de Malles de Triangles

Orientabilitat de la malla

Una malla és orientable si tots els triangles estan orientats cap a la mateixa banda; en altres paraules, els vectors normals calculats a cada triangle en base a la orientació de les seves tres arestes han d'apuntar de forma coherent cap a la mateixa banda de la malla.

Una malla és orientable si, per tota semi-aresta que tingui una sola semi-aresta veina, les dues tenen sentits contraris (dues semi-arestes veines són les que comparteixen les mateixes dues cares). L'algorisme ha de recorrer tots els triangles, i per cada triangle les seves tres semi-arestes. Ara cal cercar la semi-aresta actual dins dels altres triangles de la malla. La malla és orientable si, per tota semi-aresta a la qual s'ha trobat una veina, les dues tenen sentits contraris.

Indirectament, el que estem fent és ampliar la informació topològica que guardem de la malla. Per a la malla inicial només guardavem la relació C:{V} i ara estem usant les relacions C:{A} i A:{C} ja que necessitem les semi-arestes. Per altres càlculs que presentarem més avall podem necessitar altres relacions com ara les A:{V} i V:{C}. Totes elles es calculen fàcilment amb un recorregut per les llistes de la malla de triangles.

Càlcul de vores i de zones no dos-varietat

Una malla té vores si té semi-arestes que no tenen veines. Una malla té arestes que no són dos-varietat si trobem alguna semi-aresta amb més d'una veina.

L'algorisme és el seguent:

Per cada triangle t de la malla fer

BuscarComptar (t.V1, t.V2) ; Si ni=0 i nd=0 llavors AfegirLlistaVora (t.V1, t.V2 ) fisi
BuscarComptar (t.V2, t.V3) ; Si ni=0 i nd=0 llavors AfegirLlistaVora (t.V2, t.V3 ) fisi
BuscarComptar (t.V3, t.V1) ; Si ni=0 i nd=0 llavors AfegirLlistaVora (t.V3, t.V1 ) fisi

fiPer

El procediment BuscarComptar (V,W) busca i va comptant el nombre de vegades que la semi-aresta (V,W) es troba a la resta de triangles de la malla (exceptuant t). Al final,

nd és el nombre de vegades que hem trobat la semi-aresta (V,W)
ni és el nombre de vegades que hem trobat la semi-aresta (W,V)

Després del procediment BuscarComptar, tenim diverses possibilitats:

En el cas que tant nd com ni siguin nuls, l'aresta pertany a una vora de la superficie
Si nd=0 i ni=1, la semi-aresta és correcta
Si nd=1 i ni=0, tenim un cas localment no orientable
En tots els demés cassos, s'ha detectat una situació de no dos-varietat

A l'algorisme anterior es guarden les arestes de la vora a una llista, pero podriem tenir altres llistes i guardar-hi altres tipus de semi-arestes: zones no orientables, zones no dos-varietat

Un cop acabat l'algorisme i detectades les vores, podem pintar les semi-arestes de la llista en un altre color per resaltar les vores, trobar cicles a la llista i pintar els diferents cicles de colors diferents, etc.

Qualitat de la malla

La qualitat d'una malla es medeix per la qualitat dels seus triangles. La qualitat d'un triangle es pot mesurar en base als seus angles:

Q = AngleMinim / SumaAngles (on SumaAngles=180)

O bé en base a la longitut de les seves arestes:

Q = LongitutArestaMinima / Perimetre

La qualitat Q d'un triangle com podeu veure és un valor entre cero i 1/3. Un valor Q=1/3 vol dir que el triangle és equilater. Valors molt petits de Q estan relacionats amb triangles degenerats. La mesura en base als angles és en general més bona, perque detecta la degeneració dels triangles isòscels amb dos angles molt petits (podeu comprovar que en aquest cas, la qualitat en base a la longitut de les arestes no baixa de 1/4).

En una malla podem buscar i detectar el triangle de més baixa qualitat, detectar i/o pintar les zones amb triangles de qualitat més baixa que un cert llindar, etc. Els triangles de baixa qualitat (molt degenerats) poden donar problemes en els algorismes geomètrics i en el seu rendering.

Detecció d'auto-interseccions

Es important detectar si la malla s'auto-intersecta. Aquest és el test més complexe, perque cal comprovar i fer el test d'intersecció entre totes les parelles de triangles de la malla. Com veieu, el test és quadratic. Es pot accelerar amb tècniques de subdivisió espaial, guardant els triangles de la malla en una estructura d'octree o d'arbre BSP.

El test triangle-triangle es redueix a sis tests aresta-triangle (les tres arestes d'un triangle contra l'altre, i al revés). Per tant, el test aresta-triangle és el que cal optimitzar. Normalment es comença comprovant si cada un dels dos extrems de l'aresta és a una banda diferent del pla del triangle. Si és aixi, es pot testejar l'orientació dels tetraedres que es formen a partir dels 5 vèrtexs en joc.

Càlcul de característiques topològiques

Si la malla és correcta i tanca un volum (ho hem pogut detectar amb els tests anteriors, comprovant que és orientable, que no té vores i que no s'auto-intersecta), podem calcular les seves característiques topològiques i comprovar que es cumpleix l'equació d'Euler C+V=A+2(S-H) . En cas que la malla no sigui correcta, molts dels algorismes geomètrics fallaran. La ùnica solució en aquest cas és la de reparar la malla i corretgir-la.

A partir del nombre d'elements de les dues llistes, sabem C i V. Com que sabem que 3*C=2*A, podem calcular el nombre d'arestes A. Amb un algorisme senzill d'inundació de vèrtexs, podem detectar el nombre de components connexes S:

S:=0;
mentre quedin vertexs no marcats fer

Escollir un primer vertex v ; Marcar(v) ; Afegir tots els seus veins (segons la relació V:{V} ) a una pila
mentre quedin vèrtexs a la pila fer

v:=desempilar(Pila)
Marcar (v)
Afegir tots els seus veins no marcats a la pila

fmentre
S:=S+1

fmentre

Finalment, el nombre forats passants H el trobarem despejant a partir de l'equació d'Euler, ja que coneixem tots els altres termes.

Pla tangent i curvatures

El pla tangent a la malla en un vèrtex és el pla perpendicular al vector normal. Com que coneixem un punt de pas (el propi vèrtex), el problema és equivalent al del càlcul del vector normal.

Una possibilitat per calcular el vector normal és calcular el vector normal del poligon "corona" del vèrtex, usant la fòrmula ja coneguda a VIG (veure el capítol de geometria al CD de VIG). El polígon corona d'un vèrtex v de la malla és el poligon format per tots els vèrtexs que es troben a distància d'una aresta respecte v (en altres paraules, és el poligon que formen els vèrtexs de la llista que retorna la relació topològica v:{V} ).

Una segona possibilitat per a calcular el vector normal a un vèrtex v de la malla és calcular el vector ponderat de totes les cares veines a v, segons la seva àrea:

normal := 0
Per cada cara c veina de v fer

normal := normal + c.normal / Area(c)

fiPer
Normalitza(normal)

Si volem estimar la curvatura a un vèrtex v de la malla, podem usar el mètode proposat per Gabriel Taubin: Primer es calcula el vector normal a v i el pla tangent (pi). A continuació, per a cada aresta a que conflueix a v, calculem el pla pi_a com el pla que passa per a i és perpendicular a pi. Aquest pla pi_a és el pla normal a la superficie en v i en la direcció de a. Ara, amb un senzill càlcul geomètric, es calcula el radi de curvatura a la secció normal definida pel pla pi_a: dins del pla pi_a, és el radi R de la circumferència que passa per v i per l'altra extrem de l'aresta a, i que a més és tangent, en el punt v, a la recta intersecció entre els plans pi, pi_a. A aquest radi R li donarem signe positiu si el centre de la circumferència es troba en sentit contrari al vector normal desde el punt v, i signe negatiu en cas contrari. La curvatura normal a v en la direcció de l'aresta a és ara 1/R. Un cop ha calculat aquestes curvatures per a totes les arestes, Taubin calcula una quàdrica aproximant a la superficie en el punt v i el càlcul dels seus valors i vectors propis ens dóna finalment les curvatures i direccions principals.

Superficie i volum tancat per la malla

Si ja hem fet les comprovacions anteriors i hem vist que la malla és correcta, podem aplicar directament els algorismes per models BRep de l'apartat 2.2.3.