Modèles de Structures Aléatoires de Type Réaction-Diffusion - Thèse de Morphologie Mathématique - Luc Decker, Ecole des Mines de Paris (1999)

2.2 Construction de polyèdres de Voronoï sur une trame

Le milieu aléatoire polycristallin peut être simulé directement dans une image digitale tri-dimensionnelle : il s'agit de développer un algorithme qui attribue à chaque voxel le label (ou numéro) du polyèdre auquel celui-ci appartient [Decker98d]. Le calcul des polyèdres est donc réalisé à un niveau de résolution donné, soit les dimensions de l'image résultante. Pour des dimensions fixées, la précision du contour des grains dépendra de leur volume moyen, donc du nombre de grains.

L'étape initiale réside dans le processus de germination qui va fixer les positions des centres des grains sur la trame.

Une propagation isotrope à partir cet ensemble de points va ensuite déterminer leur fonction distance euclidienne [Gratin92a,Gratin93]. Une telle opération est assimilable à un processus de croissance où chaque centre se comporte comme une source. Le résultat est représenté sous la forme d'une image dont les niveaux de gris indiquent en chaque point la distance à la source la plus proche. L'image de la Figure 1a est obtenue dans le cas d'une source unique. Dans le cas de plusieurs sources, le même algorithme calcule en chaque point de l'image sa distance à la source la plus proche (Figure 1b). Pour optimiser les temps de calcul (cette étape en représente la plus grande partie) , nous faisons appel à la technique très efficace des files d'attentes hierarchiques [Meyer90a,Gratin92b,Gratin93]. L'espace mémoire requis est aussi considérable puisqu'elle nécessite de créer une image intermédiaire de nombres flottants. Par exemple, 63 Mo sont utilisés pour le calcul d'un domaine de $ 180^3$ voxels.

\begin{figure}
\par\centerline {\begin{tabular}{p{5cm}p{5cm}p{5cm}}
\fbox{\epsfx...
... une trame p\'eriodique, exemple à deux dimensions.}}
\end{tabular}}\end{figure}

Enfin, la segmentation de l'image des distances permet de localiser avec précision les frontières entre grains, donc leurs zones d'influence respectives. Il en résulte une image dans laquelle un label différent a été attribué à chaque région (Figure I-7c) : il s'agit du résultat souhaité, qui caractérise la morphologie du matériau simulé. Pour cette dernière étape, l'image des distances est considérée - à deux dimensions - comme un relief topographique sur lequel les frontières entre grains correspondent aux lignes de partage des eaux de différents bassins versants; chaque centre est associé à un bassin dont il est le point le plus bas. Pour détecter efficacement les lignes de partage des eaux, l'algorithme utilisé simule "l'immersion" du relief [Meyer90b,Meyer92]. Le principe reste applicable à trois dimensions, où l'on considère alors des surfaces de partage entre zones d'influences. De telles méthodes sont appliquées bien plus fréquemment en traitement d'image, par exemple pour la reconnaissance de formes. Par ailleurs, cette étape de segmentation peut être évitée si - au cours du calcul de la fonction distance - on associe directement à tout point le label de la source ponctuelle la plus proche.

A présent, si l'on souhaite obtenir une résolution analytique du problème, il reste possible d'utiliser les informations de voisinage entre grains présentes dans l'image discrète du milieu. Lorsque le volume des grains (en nombre de voxels) est suffisant, ces relations de voisinage (graphe de Delaunay) ne comportent aucune erreur. Le calcul des intersections entre plans médiateurs en est alors fortement simplifié et permet par exemple d'obtenir les coordonnées précises des sommets des polyèdres dans le domaine continu. Un maillage peut ensuite être établi à partir de la microstructure.

Les temps d'exécution de l'algorithme proposé sont relativement courts, et négligeables en comparaison avec la durée des calculs par éléments finis qui exploitent ensuite la microstructure générée. De plus, la complexité des calculs dépend presque uniquement du nombre de voxels du domaine à générer, et non du nombre de polyèdres. A titre d'exemple, sur un micro-ordinateur de type PC sous Linux (133 MHz, 64Mo de mémoire), 200 secondes sont nécessaires pour produire un domaine cubique de $ 180^{3}$ voxels contenant aussi bien 1000 que 3000 polyèdres.



Decker, Luc. "Modèles de structures aléatoires de type réaction-diffusion". PhD diss. (191 p.), Paris, ENSMP-CMM, 1999.
Luc Decker   luc@texrd.com   www.texrd.com  -  Mars 1999