Lisser un maillage irrégulier ?

[ijk-ref]

Bonjour

Je cherche quelques documentations sur les maillages irréguliers (polyèdres généraux) et plus particulièrement comprendre les relations qui relient des sommets quelconques à des faces quelconques entre eux.

Car j'aimerai Lisser ("flouter") un tel maillage...

Comme je "flouterai" un maillage carré régulier avec

Code :

1
2
3
4
5
6
d[i,j] = 
    (          
         s[i-1,j-1]*1 + s[i-0,j-1]*2  s[i+1,j-1]*1 
       + s[i-1,j-0]*2 + s[i-0,j-0]*4  s[i+1,j-0]*2 
       + s[i-1,j+1]*1 + s[i-0,j+1]*2  s[i+1,j+1]*1
     ) / 16

Appliquer à l'infini une telle formule sur un tel maillage fermé converge vers une solution stable où toutes les sommets auront la même valeur.

Quelle formule faut il appliquer sur un maillage irrégulier (par exemple Diagramme de Voronoï) pour justement respecter cette convergence ?

Si vous avez des pistes... merci

[ijk-ref]

Plus de cent visualisations et pas une seule réponse ! :o

P'être que je m'exprime mal... si vous comprenez pas ma demande dites les moi

[magelan]

Bonjour,

ce qui n'est pas très clair pour moi :
je ne comprends pas le notion de "flouter un maillage"? Tu veux pas plutôt dire lisser un maillage?
Que représente s(i,j) par rapport à ton maillage?

[ijk-ref]

Oui : "lisser" un maillage. Désolé :o

Ca vous donne plus d'idées ?

s(i,j) ? en fait j'ai écrit "s" pour source et "d" pour destination.

Autrement s(i,j) représente chaque sommet du maillage... dans le cas présent carré... c'est à dire qu'il peut se traiter ici comme un bitmap (image) classique en deux dimensions.

Comme je tiens à traiter un maillage complet et fermé... dans le cas présent, la partie droite est reliée à la gauche et celle du haut à celle du bas - un tore quoi

C'est la cas le plus simple et je le donne car tout le monde le connait et comprend parfaitement ce qu'est de "lisser/flouter" un tel maillage/image.

Cependant moi j'aimerai "lisser" des cas plus généraux... et je coince un peu sur la formule à appliquer entre les sommets pour que ce maillage converge vers une solution où tous les sommets ont la même "force".

C'est à dire qu'en lissant ce maillage chaque sommet converge vers "la somme des sommets divisée par la le nombre des sommets"

[pseudocode]

Envoyé par ijk-ref

Oui : "lisser" un maillage. Désolé :o

Ca vous donne plus d'idées ?

Méthode 1 : se ramener au cas connu, en transformant chaque polygone quelconque (= une maille du maillage) en un polygone régulier (carré, ...). Les coordonnées des sommets du polygone quelconque ainsi que celles du point courant sont ainsi converties dans un repère où le lissage est facile.

Méthode 2 : Utiliser un repère local pour chaque maille, dans lequel on peut utiliser directement une formule de lissage. Par exemple les coordonnées barycentriques homogènes. (cf ce document, chapitre 3)

[ijk-ref]

Ah ! J'aurai préféré trouvé des solutions directs aux problèmes :o

Edit : en fait, ça fonctionne déjà très bien... il ne faut pas négliger le "poids/valence" de chaque sommet... chose que l'on néglige complètement dans le cas "carré" car les sommets comme les faces ont naturellement le même "poids".

[Alexis.M]

Moi je suis toujours pas sur d'avoir compris ce qu'il faut "lisser". La position des noeuds ? Une fonction s définie pour chaque sommet du maillage ?

Dans tous les cas, je te conseilles de regarder du côté des techniques de lissages sur graphe.

le principe de base c'est que tu as un ensemble de sommet dont certains sont reliés par des arêtes. On dispose d'une fonction réelle f définie sur l'ensemble des sommet (une valeur associée à chaque sommet). peut donc se mettre sous la forme d'un vecteur avec chaque composante correspondant à un sommet.

Tu veux minimiser la fonction suivante:
E = || f - f0 ||^2 + c * f^T L f

le premier terme et "l'attache au données" le deuxième termie fait intervenir le Laplacien du graphe: L = D - W. *W est la matrice d'adjacence pondérée: W[i,j] représente le poids de l'arrête entre les sommets i et j. D est la matrice diagonale dont chaque élément est la somme des éléments de la ligne correspondante de W (D[i,i] = sum_j W[i,j]).

le terme f^t L f mesure la "rugosité" de la fonction f. Et correspond à la notation matricielle de \sum_i \sum_j W[i,j] (f_i - f_j)^2. ce qui correspond à la somme pondéré des différence (quadratiques) de la fonction entre les sommets adjacents. Si cette différence est petite, la fonction est lisse.

Le coefficient mesure c l'importance de l'attache aux données.

L'avantage de tout ça c'est qu'il existe une solution analytique:

f = (I + c*L)^(-1) f0

I est la matrice identité.

Ceci est la version de base mais il existe des versions qui utilisent des p-Laplacien avec une résolution itérative.

Dans ton cas pour construire la matrice d'adjacence, tu peux simplement mettre 1 quand il existe une arrête entre deux sommets et 0 sinon ou alors une valeurs qui dépend de la distance entre les noeuds (exp(-a*d_ij^2). La matrice D aura alors pour chaque sommet le nombre de sommets voisins.

La fonction f peut-être la composante x ou y des positions ou n'importe qu'elle autre fonction.

[souviron34]

Envoyé par Alexis.M

Moi je suis toujours pas sur d'avoir compris ce qu'il faut "lisser". La position des noeuds ? Une fonction s définie pour chaque sommet du maillage ?
.

Parce qu'on peut aussi utiliser par exemple Delaunay, puis interpoler/lisser..

[ijk-ref]

Envoyé par Alexis.M

Moi je suis toujours pas sur d'avoir compris ce qu'il faut "lisser". La position des noeuds ? Une fonction s définie pour chaque sommet du maillage ?

Ce n'est pas forcement une position, cela peut être un simple scalaire. Par exemple une image en noir et blanc... sauf au lieu d'être définie classiquement par un maillage "carré" et avec la "fonction" de flou "classique" montrée plus haut, je tiens à comprendre comment flouter un maillage quelconque.


Autrement merci pour tes précisions ça l'air très bien ce que tu as écrit

[Alexis.M]

Dans ce cas le formalisme que j'ai donné s'applique très bien mais est un peu différent de ce que tu fais dans ton exemple.

Toi ce que tu fais c'est:
f[i](t+1) = (f[i](t) + \sum_j W[i,j] f[j](t))/(1+sum_j W[i,j])

Remplaces tes coefficients par c/16. est tu verras que ça correspond.