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)

suivant: 2.2 Marcheurs aléatoires   remonter: 2. Modèles de diffusion   précédent: 2. Modèles de diffusion   [Table des matières]

2.1 Systèmes à base de particules

En informatique graphique, une très forte simplification des processus physiques ou biologiques est généralement pratiquée. Au profit de la rapidité des simulations, il s'agit de réduire les mécanismes en jeu à leur signification essentielle : les aspects quantitatifs du problème traité ne sont en général plus pris en compte. De fait, l'objectif final de la modélisation est dans ce cas de produire des images qui ressemblent qualitativement à la réalité. Le test ultime - dit "de Turing" - consiste ainsi à "tromper" un observateur par l'intermédiaire d'images de synthèse qui ne pourraient plus être differenciées d'images réelles, quels que soient les moyens mis en oeuvre. Les applications de ce type de modélisation sont très nombreuses. La production cinématographique représente cependant leur principal débouché, les moyens financiers investis y étant particulièrement importants. La mise au point des simulateurs de vol est également concernée puisque l'aspect temps réel conduit à privilégier des solutions peu couteuses en temps de calcul - du fait de contraintes techniques incontournables. Les logiciels éducatifs ou de vulgarisation scientifique s'appuient aussi sur une telle démarche, parce que leur objectif se restreint à la présentation générale des principes qui gouvernent un phénomène donné. Enfin, une telle approche est envisageable pour la génération de textures aléatoires réalistes.

C'est dans ce contexte que W. Reeves a introduit le concept de système de particules [Reeves83]. De manière très générale, un système de particules représente un objet quelconque sous la forme d'un ensemble de particules en évolution dans un espace continu. Il n'est pas nécessaire que cet objet soit réellement constitué de particules; ce dernier est défini uniquement en terme de relation d'appartenance de ses particules. Le système de particules ne représente qu'une méthode pour modéliser l'objet et ses déformations au cours du temps, dans le cas où les approches géométriques généralement employées échouent. C'est ainsi que les systèmes de particules ont été initialement conçus pour simuler dynamiquement la morphologie irrégulière d'éléments naturels tels que les nuages (Figure II-1), l'eau ou encore le feu. Pour cette catégorie d'objets flous - nous dirions "fluides" -, il n'existe pas de frontière précise entre l'intérieur et l'extérieur de l'objet : il y a diffusion à travers tout l'espace. Il est ainsi impossible de définir - comme à l'ordinaire - leur surface sous la forme d'un maillage de facettes polygonales.

Le champ d'application des systèmes de particules s'est considérablement étendu, notamment au travers de la production d'effets spéciaux pour le cinéma tels que des explosions et autres feux d'artifices. Encore plus récemment, ils ont été utilisés afin de simuler le processus d'évacuation d'une foule dans un stade (chaque particule représentant un individu) ou encore pour reproduire le déploiement de coussins pneumatiques de protection ( airbags) [Bouvier97]. Dans ces exemples, on retrouve toujours la notion de diffusion, de dispersion. La modélisation de végétaux et de leur croissance a également été réalisée à l'aide de systèmes où chaque particule représente "une brique de base" de l'organisme vivant.

Au niveau informatique, un système de particules se présente sous la forme d'une liste de particules, accompagnées de leurs coordonnées dans l'espace et d'un label qui suffira à les caractériser, correspondant à leur classe ou catégorie. D'une part, un système ordinaire peut compter quelques millions de particules. D'autre part, chaque particule est caractérisée par une multitude de propriétés diverses. La création de classes de particules, qui définissent chacune un jeu complet de propriétés, est ainsi à l'origine d'un gain de mémoire très important, même s'il est nécessaire de créer plusieurs milliers de classes.

Un système de particules évolue par itérations, le temps y est discrétisé; son évolution comprend quatre étapes principales:

a -

La création de nouvelles particules, par l'intermédiaire de sources fixes ou en mouvement. Toute particule peut avoir la propriété de générer de nouvelles particules, de façon probabiliste.

b -

Le déplacement des particules en fonction de leur classe. Celle-ci indique notamment leur vecteur vitesse. Pour obtenir une plus grande liberté de mouvement, il est possible d'associer un vecteur vitesse quelconque à chaque particule. Plus précisément, une particule se déplace d'un point vers tout autre point de l'espace, qui n'appartient pas à un voisinage déterminé.

c -

Le changement d'état (de classe) des particules. Cette étape peut faire appel à une chaine de Markov, afin d'introduire des processus aléatoires. On définit ainsi une matrice des probabilités de changement d'état. Pour une particule, un changement d'état se traduit par une mise à jour complète de toutes ses propriétés. L'accélération d'une particule est par exemple prise en compte par un changement d'état. Des lois physiques simplifiées servent généralement à contrôler l'évolution du système.

d -

Les interactions entre particules ou avec d'autres objets (obstacles solides). Dans un système de particules usuel, la notion de voisinage d'un point de l'espace n'est pas explicitement définie. Du point de vue algorithmique, il semble qu'il s'agisse du problème le plus complexe posé par un système de particules. En effet, il faut diposer d'une méthode permettant de situer rapidement les particules entre elles, ou encore par rapport aux autres objets. Un découpage hiérarchique de l'espace en sous-régions permet de réduire les tests de positions à réaliser.

Enfin, citons quelques exemples de caractéristiques participant à la définition d'une classe de particules:

• géométriques : la forme des particules; la forme de leur zone d'influence.
• graphiques : leur couleur et leur texture, leur niveau de tranparence.
• chimiques : leur espèce; la probabilité de génération de nouvelles particules, et l'état initial de ces particules; des réactions chimiques peuvent aussi être simulées en terme de changements d'états.
• physiques : leur masse, leur charge électrique, etc...
• dynamiques : leur mode d'évolution ou de diffusion (vitesse de déplacement, accélération) et leur durée de vie.

Le principal obstacle à l'utilisation des systèmes de particules réside dans la quantité extrêmement importante de particules qui sont nécessaires à la simulation d'un problème complexe à trois dimensions. En pareil cas, les temps de calculs restent prohibitifs, et le recours à des architectures parallèles est fréquent. Par ailleurs, ces modèles sont physiquement inadaptés à de nombreux domaines. Il est par exemple difficile de mesurer correctement une densité en particules - une concentration ou une pression - dans une région d'un espace continu, et à plus forte raison, un gradient de concentration. Pour des applications en hydrodynamique, la densité des particules en interaction est insuffisante; en conséquence, il demeure impossible de reproduire des écoulements non linéaires. Les processus aléatoires sont pris en compte artificiellement, par simple ajout d'un bruit perturbateur, alors qu'ils résultent d'instabilités physiques plus complexes.

suivant: 2.2 Marcheurs aléatoires   remonter: 2. Modèles de diffusion   précédent: 2. Modèles de diffusion   [Table des matières]

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