Plan - imagi,j,k sommets de parallèlépipèdes/cubes = pavés Décomposition de chaque pavé en un ensemble de tétraèdres avec une cohérence entre pavés adjacents Nicolas

Visualisation - courbes/surfaces isovaleur Surfaces isovaleur

Plan

5 Visualisation - courbes/surfaces isovaleurPresentationCourbes isovaleurDonnees volumiquesSurfaces isovaleur

Nicolas SZAFRAN (UGA - UFR IM2AG) L3 Info - Image 2016/2017 40 / 68


Principe

Donnees quelconques : Xi = (xi , yi , zi);Fi



Principe

Donnees quelconques : Xi = (xi , yi , zi);FiTrouver une surface isovaleur

Sv = {X ∈ R3,F (X ) = v}

ou F est un interpolant des donnees.



Principe


Sv = {X ∈ R3,F (X ) = v}


Equivalent 3D des courbes isovaleur→ methodes similaires



Principe


Sv = {X ∈ R3,F (X ) = v}


Equivalent 3D des courbes isovaleur→ methodes similairesXi = (xi , yi , zi) ∈ R

3 + Fi ∈ R ≡ Pi = (xi , yi , zi ,Fi) ∈ R4



Principe


Sv = {X ∈ R3,F (X ) = v}


Equivalent 3D des courbes isovaleur→ methodes similairesXi = (xi , yi , zi) ∈ R

3 + Fi ∈ R ≡ Pi = (xi , yi , zi ,Fi) ∈ R4

Sv ≡ {(x , y , z ,w) ∈ R4, F (x , y , z) = w}

︸︷︷︸

hypersurface de R4

∩{(x , y , z ,w) ∈ R4, w = v}

︸︷︷︸

hyperplan de R4



Exemples d’application




representation de surface impliciteexemple de la sphere {(x , y , z),F (x , y , z) = x2 + y2 + z2 − R2 = 0}




representation de surface impliciteexemple de la sphere {(x , y , z),F (x , y , z) = x2 + y2 + z2 − R2 = 0}







image medicale - extraction du volume d’un organe specifique a partir decoupes issues d’un examen radiologiques (IRM, ...)




image medicale - extraction du volume d’un organe specifique a partir decoupes issues d’un examen radiologiques (IRM, ...)



Algorithme de calcul de surfaces isovaleur




Donnees : grille reguliere uniforme– points Pi ,j ,k = (xi = x0 + i∆x , yj = y0 + j∆y , zk = z0 + k∆z)– valeurs associees Fi ,j ,kavec 1 ≤ i ≤ M, 1 ≤ j ≤ N, 1 ≤ k ≤ P





1) Decouper la grille en tetraedres (tetraedrisation prealable)





1) Decouper la grille en tetraedres (tetraedrisation prealable)

2) Traiter la sequence de tetraedres pour obtenir une surface formee detriangles.



Tetraedrisation prealable




donnees Xi ,j ,k = (xi , yj , zk) + Fi ,j ,k,points disposes suivant une grille reguliere uniforme





Xi ,j ,k sommets de parallelepipedes/cubes = paves





Xi ,j ,k sommets de parallelepipedes/cubes = paves

Decomposition de chaque pave en un ensemble de tetraedres avec unecoherence entre paves adjacents



Tetraedrisation prealableLe probleme de decomposition d’un pave

Pave Pi ,j ,k = [xi , xi+1]× [yj , yj+1]× [zk , zk+1]





8 sommets :A = Xi ,j ,k

B = Xi ,j ,k+1

C = Xi ,j+1,k

D = Xi ,j+1,k+1

E = Xi+1,j ,k

F = Xi+1,j ,k+1

G = Xi+1,j+1,k

H = Xi+1,j+1,k+1

C

B

F

G H

A

E

D





8 sommets :A = Xi ,j ,k

B = Xi ,j ,k+1

C = Xi ,j+1,k

D = Xi ,j+1,k+1

E = Xi+1,j ,k

F = Xi+1,j ,k+1

G = Xi+1,j+1,k

H = Xi+1,j+1,k+1

C

B

F

G H

A

E

D

→ plusieurs possibilites pour decouper un hexaedre en tetraedres







Decomposition en 6 tetraedres

C

B

F

G H

A

E

D





C

B

F

G H

A

E

D C

B

F

G H

A

E

D

→ 6 tetraedres :





C

B

F

G H

A

E

D C

B

F

G H

A

E

D

→ 6 tetraedres : [CDEG ]





C

B

F

G H

A

E

D C

B

F

G H

A

E

D

→ 6 tetraedres : [CDEG ] - [DFGH]





C

B

F

G H

A

E

D C

B

F

G H

A

E

D

→ 6 tetraedres : [CDEG ] - [DFGH] - [DEFG ]





C

B

F

G H

A

E

D C

B

F

G H

A

E

D

→ 6 tetraedres : [CDEG ] - [DFGH] - [DEFG ] - [BCDE ]





C

B

F

G H

A

E

D C

B

F

G H

A

E

D

→ 6 tetraedres : [CDEG ] - [DFGH] - [DEFG ] - [BCDE ] - [BDEF ]





C

B

F

G H

A

E

D C

B

F

G H

A

E

D

→ 6 tetraedres : [CDEG ] - [DFGH] - [DEFG ] - [BCDE ] - [BDEF ] -[ABCE ]





C

B

F

G H

A

E

D

→ 6 tetraedres : [CDEG ] - [DFGH] - [DEFG ] - [BCDE ] - [BDEF ] -[ABCE ]Inconvenient : decomposition non minimale (en nb de tetraedres)





→ 6 tetraedres : [CDEG ] - [DFGH] - [DEFG ] - [BCDE ] - [BDEF ] -[ABCE ]Inconvenient : decomposition non minimale (en nb de tetraedres)Avantage : bon raccord des tetraedres issus d’hexaedres voisins





→ 6 tetraedres : [CDEG ] - [DFGH] - [DEFG ] - [BCDE ] - [BDEF ] -[ABCE ]Inconvenient : decomposition non minimale (en nb de tetraedres)Avantage : bon raccord des tetraedres issus d’hexaedres voisins



Calcul de surfaces isovaleurAlgorithme

Extraction d’une surface isovaleur dans une tetraedrisationMethode similaire a l’algorithme d’extraction de courbe isovaleur dans unetriangulation.





Donnees : Tetraedrisation T avec

sommets Pi = (xi , yi , zi ) et donnees scalaires associees Fi

tetraedres Tk = [k1, k2, k3, k4] (kj indices des sommets)

+ valeur reelle v





Donnees : Tetraedrisation T avec

sommets Pi = (xi , yi , zi ) et donnees scalaires associees Fi

tetraedres Tk = [k1, k2, k3, k4] (kj indices des sommets)

+ valeur reelle v

Resultat : Surface S sous forme d’un ensemble de triangles







1 parcourir l’ensemble des tetraedreset pour chaque tetraedre :





tester s’il intersecte la surface isovaleur (deux sommets de signedifferents)





tester s’il intersecte la surface isovaleur (deux sommets de signedifferents)si oui, calculer l’intersection entre le tetraedre et la surface isovaleursous forme de triangle(s)





tester s’il intersecte la surface isovaleur (deux sommets de signedifferents)si oui, calculer l’intersection entre le tetraedre et la surface isovaleursous forme de triangle(s)

2 → liste de triangles ≡ surface isovaleur



Calcul de surfaces isovaleurAlgorithme - traitement d’un tetraedre




Tetraedre T = [S1,S2,S3,S4] avec valeur Fi associee a Si

S2 S3

S4

S1





S2 S3

S4

S1

chaque sommet Si : si Fi > v si Fi ≤ v





S2 S3

S4

S1

chaque sommet Si : si Fi > v si Fi ≤ v→ 16 configurations possibles



Calcul de surfaces isovaleurAlgorithme - traitement d’un tetraedre - 16 configurations possibles







2 config. avec 4 sommets de meme signe

8 config. avec 1 sommet de signe different des trois autres

6 config. avec 2 sommets d’un signe et 2 sommets de l’autre







sommets de meme signe

C

D

A

B




sommets de meme signe

C

D

A

B

→ pas d’intersection avec la surface isovaleur







sommet A de signe different des sommets B,C et D

C

D

A

B





C

D

A

B

I

K

J

→ intersection des 3 aretes [A,B ], [A,C ] et [A,D] avec la surface isovaleur





C

D

A

B

I

K

J

→ intersection des 3 aretes [A,B ], [A,C ] et [A,D] avec la surface isovaleur→ un triangle [I , J,K ]









8 configurations → 4 cas :






sommet S1 de signe different des sommets S2,S3 et S4































sommets A, C d’un signe et sommets B, D de l’autre signe

C

D

A

B C

D

A

B





C

D

A

B

J

I

KL

C

D

A

B

J

I

KL

→ intersection des 4 aretes [A,B ], [A,D], [C ,B ] et [C ,D] avec la surfaceisovaleur





C

D

A

B

J

I

KL

C

D

A

B

J

I

KL

→ intersection des 4 aretes [A,B ], [A,D], [C ,B ] et [C ,D] avec la surfaceisovaleur→ OU deux triangles [I , J,K ] et [L, J,K ]





C

D

A

B

J

I

KL

C

D

A

B

J

I

KL

→ intersection des 4 aretes [A,B ], [A,D], [C ,B ] et [C ,D] avec la surfaceisovaleur→ OU deux triangles [I , J,K ] et [L, J,K ]→ OU deux triangles [I , J, L] et [I ,K , L]















sommets S1, S2 d’un signe et sommets S3, S4 de l’autre signe






















Donnees :

tetraedrisation T avec sommets Sk et valeurs associees Fk

valeur v

fonction I = intersection arete hyperplan(P ,Q,FP,FQ ,v)// calcul du point I, intersection de l’arete [P ,Q]// avec la surface isovaleur Sv// FP : valeur associee au sommet P// FQ : valeur associee au sommet Qλ ← (v − FP)/(FQ − FP)I ← (1− λ) P + λ Q




Donnees :

tetraedrisation T avec sommets Sk et valeurs associees Fk

valeur v

fonction I = intersection arete hyperplan(P ,Q,FP,FQ ,v)// calcul du point I, intersection de l’arete [P ,Q]// avec la surface isovaleur Sv// FP : valeur associee au sommet P// FQ : valeur associee au sommet Qλ ← (v − FP)/(FQ − FP)I ← (1− λ) P + λ Q

Resultat :

surface isovaleur S (sequence de triangles)




fonction m = marque(P ,F ,v)

// calcul de la marque du sommet P de valeur associee Fsi F < v alorsm ← 0

sinonm ← 1

fin si




Calcul de la surface isovaleur S

// Initialisation de SS ← Ø

// Parcours des tetraedrespour tout tetraedre T de T fairetraitement tetraedre(T )

fin pour




procedure traitement tetraedre(T )

// les quatres sommets de T, leurs valeurs et marquesS1 ← sommet1(T ), F1 ← valeur1(T )S2 ← sommet2(T ), F2 ← valeur2(T )S3 ← sommet3(T ), F3 ← valeur3(T )S4 ← sommet4(T ), F4 ← valeur4(T )m1 ← marque(S1,F1,v)m2 ← marque(S2,F2,v)m3 ← marque(S3,F3,v)m4 ← marque(S4,F4,v)




procedure traitement tetraedre(T ) // suite

// cas marque de S1 differente des marques de S2, S3, S4si m1 6= m2 et m1 6= m3 et m1 6= m4 alors// calcul des trois intersectionsI ← intersection arete hyperplan(S1,S2,F1,F2,v)J ← intersection arete hyperplan(S1,S3,F1,F3,v)K ← intersection arete hyperplan(S1,S4,F1,F4,v)

S ← S ∪ {[I , J,K ]} // ajouter [I , J,K ] a Sfin si























// cas marques de S1 et S2 differentes des marques de S3 et S4si m1 = m2 et m2 6= m3 et m3 = m4 alors// calcul des quatre intersectionsI ← intersection arete hyperplan(S1,S3,F1,F3,v)J ← intersection arete hyperplan(S1,S4,F1,F4,v)K ← intersection arete hyperplan(S2,S3,F2,F3,v)L ← intersection arete hyperplan(S2,S4,F2,F4,v)

S ← S ∪ {[I , J,K ]} // ajouter [I , J,K ] a SS ← S ∪ {[L, J,K ]} // ajouter [L, J,K ] a S

fin si




procedure traitement tetraedre(T ) // suite et fin



fin si




Routine traitement tetraedre(T ) // suite et fin



fin si




Documents

Plan - imagi,j,k sommets de parallèlépipèdes/cubes = pavés Décomposition de chaque pavé en un ensemble de tétraèdres avec une cohérence entre pavés adjacents Nicolas