Génération Organique

William Lidwell, dans son ouvrage Universal Principle of Design, différencie deux types de formes : les formes géométriques et les formes organiques. Les premières sont décrites comme des formes définies par une apparence régulière (angles, lignes, segments…) pouvant être décrites de manière mathématique. On y retrouve les formes classiques de nous avons abordé en cours de géométrie telle que les triangles, carré ou autres ellipses. Les secondes sont décrites comme des formes irrégulières, asymétriques à l’apparence souvent courbe et semblant davantage être issues de la nature. Pour autant ces formes, dites organiques peuvent souvent être décrites par des algorithmes et des nombreux chercheurs, artistes ou développeurs ont travaillé à des modèles mathématiques permettant de décrire ces formes. Pour cette seconde partie du thème sur la génération nous allons aborder 4 de ces modèles :

  1. Le flowfield
  2. Le circle packing
  3. L’agrégation limitée par diffusion
  4. La réaction diffusion de Gray-Scott

Le Flow Field

En mathématiques, un champ de vecteurs (flow field ou vector field) est une fonction associant un vecteur, c’est à un dire une direction et une force, à chaque point d’un espace 2D ou 3D. Nous pourrions simplifier cette définition, pour un espace 2D, comme une grille cartésienne à laquelle, pour chaque cellule nous associons une direction.
Ces champs sont très utiles en physique pour modéliser des vitesses, des frictions ou simuler l’écoulement d’un fluide. On y retrouve souvent un ensemble de direction suivant globalement une ou des forces principales créant ainsi des grilles homogènes de mouvements.
Ces grilles sont également grandement utilisées en production graphique afin de simuler des turbulences et des mouvements de masse pour un lot de particules. Elles peuvent également se révéler être un élément visuel intéressant.

Le principe du flow field réside dans le fait de disposer, sur une grille cartésienne, des directions semblables créant ainsi un effet de masse et de turbulence globale. Si nous savons comment réaliser une grille cartésienne — voir première partie de ce cours —, il nous reste à savoir comment décrire une direction.

Si on symbolise des directions par des points cardinaux nous remarquons que ces derniers correspondent à des coordonnées polaires. Ainsi nous pouvons dire que dans notre espace géométrique polaire nous avons : 

Nous pouvons donc symboliser une direction présente au sein de chacune de nos cellules par un motif utilisant des coordonnées polaires. Nous pourrions donc dire d’’un flow field :

Un flow field est un pavage basé sur un système cartésien représentant un motif polaire de rayon R où, pour chaque motif, l’angle varie de manière aléatoire et uniforme par rapport à ces motifs voisins.

Définir le nombre de répétitions des frises :

Pour un nombre i étant égale à 0;
Ce nombre i étant toujours inférieur au nombre maximum de frises;
Et ce nombre s’incrémentant de 1; 

Définir le nombre de répétitions des motifs :

Pour un nombre j étant égale à 0;
Ce nombre j étant toujours inférieur au nombre maximum de motifs;
Et ce nombre s’incrémentant de 1; 


Pour chacun de ce nombre :
Nous définissons une position x étant égale à la position précédente + un certain écart (ici la largeur d’un rectangle)
À chaque nouvelle frise nous définissons une position y étant égale à la position précédente + un certain écart (ici la hauteur d’un rectangle)
Pour chacun de ces motifs nous définissons un rayon R
Pour chacun motif nous définissons un angle aléatoire et uniforme par rapport à ses voisins
Pour chaque motif nous définissons une direction D étant égale à :
D.x = x + cos(angle) * R
D.y = y + sin(angle) * R

Afin de parfaire notre algorithme il nous reste à trouver la méthode nous permettant d’obtenir une valeur d’angle aléatoire et uniforme par rapport aux voisins du motif.

** Algorithm tips : le bruit Perlin **

Le bruit perlin est bien différent du bruit brownien tant dans sa syntaxe que dans les valeurs qu’il renvoie. Contrairement au bruit brownien le bruit perlin produit une séquence de valeurs où chaque valeur est proche de la valeur précédente. On obtient donc une répartition harmonieuse de valeurs. La structure de bruit perlin est similaire à celle d’un signal audio, en ce qui concerne l’utilisation de la fonction de fréquences. Similaire à la notion d’harmoniques en physique,le  bruit perlin est calculé sur plusieurs octaves qui sont traitées par lot pour le résultat final. On peut illustrer le bruit perlin par ce schéma

Le bruit de perlin a été développé par Ken Perlin en 1985. À cette époque, après avoir travaillé sur les effets spéciaux de Tron pour MAGI en 1981, il cherchait à éviter le look « machinique ». Il commença donc par mettre au point une fonction pseudo-aléatoire de bruit qui remplit les trois dimensions de l’espace, avant d’inventer l’année suivante le premier langage de shading. Ses travaux sur les textures procédurales ont valu à Ken Perlin l’Academy Award for Technical Achievement en 1997.

Source Wikipédia

Ce bruit est très utilisé dans la génération de textures procédurales mais aussi dans les déplacements de particules puisque nous permet d’avoir une harmonie entre les valeurs et donc des sensations d’incrémentation et décrémentation plus douces. Dans sa syntaxe le bruit perlin est bien différent du bruit brownien. Voici comment il se déclare :

noise(valeur);
//ou
noise(valeur, valeur);
//ou
noise(valeur, valeur, valeur);

 

On remarque de prime abord que là où le bruit brownien accueille deux valeurs entre ses parenthèses (minimum et maximum) le bruit perlin peut en accueillir trois. En effet on dit du bruit perlin qu’il peut être uni, bi ou tridimensionnel. Nous nous attarderons sur le bruit perlin unidimensionnel dans cette partie.

La seconde remarque que nous ferons sur le bruit perlin est qu’il ne nous renverra toujours qu’une seule valeur comprise entre 0 et 1 et celle-ci sera toujours identique. En effet la répartition de bruit perlin est définie par la valeur précédente obtenue. Il faudra donc incrémenter notre valeur puis recalculer notre bruit afin d’obtenir une suite de valeurs réparties de façon harmonieuse.

Pour cela nous allons utiliser une valeur que nous appellerons xInc et qui sera égale à 0. Nous calculerons un bruit à partir de cette valeur puis à la fin de chaque boucle nous l’incrémenterons de 0.01 pour calculer un nouveau bruit à partir de la valeur précédente.

float xInc = 0.0;
float x;
x = noise(xInc);
xInc+= 0.01;

 

Nous obtenons donc une suite de valeurs harmonieuses dépendante de la valeur précédente. Cependant nos valeurs restent comprises entre 0 et 1. Pour obtenir nos valeurs entre 0 et 100 il faudra donc effectuer une règle de trois (ou règle de proportionnalité, voir ici) qui nous renverra nos valeurs sur une échelle de 1 à 100.

Pour cela processing nous offre une fonction : map(). Cette fonction va nous permettre de mapper nos valeurs comprises entre 0 et 1 entre 0 et 100 de la manière suivante :

x = map(variable à mapper, valeur Min d'origine, valeur Max, d'Origine, valeur Min Finale, valeur Max Finale);

Ex : valeurs perlin entre 0 et 100
float xInc = 0.0;
float x;
x = noise(xInc);
x = map(x, 0, 1, 0, 100);
xInc+= 0.01;

Dans le cadre de la réalisation du flowfield nous pouvons attribuer notre valeur d’angle à une valeur perlin. Afin d’obtenir un bruit uniforme par rapport aux motifs voisins gauche, droit bas et haut nous pouvons mettre une place un bruit perlin à deux dimensions telles que :

for (int i=0; i<hauteurMax; i++) {
    for (int j=0; j<largeurMax; j++) {
      //definition de la position x,y de chaque point
      float x = j * resolutionLargeur
      float y = ij * resolutionHauteur
        float angle = noise(i * 0.1, j * 0.1) * TWO_PI; //2Dimension, l'aleatoire renvoyé est différent pour chaque ligne et différent pour chaque colonne et n'est pas animé car i et j sont identiques à chaque frame
      float endx = x + cos(angle) * largeur/2;
      float endy = y + sin(angle) * hauteur/2; 
      stroke(255);
      line(x, y, endx, endy);
    }
  }

Nous obtenons alors un flowfield dont l’uniformité dépendra de l’incrément de i, j. En effet plus i, et j seront proches les uns des autres (et donc multipliés par un incrément bas) plus l’aléatoire perlin subira un faible écart.

Animation du flow field

Il est possible d’animer le flowfield, notamment par l’introduction d’une nouvelle dimension à notre aléatoire perlin. En effet, comme nous pouvons le voir dans notre exemple précédent, le bruit perlin est une méthode renvoyant un aléatoire fixe. Ce dernier, étant calculé à partir des valeurs précédentes soumises au bruit, renverra toujours la même valeur pour un nombre X à chaque frame. Afin d’animer notre grille nous pouvons ajouter une dernière dimension au bruit par le biais d’une variable s’incrémentant à chaque frame. Nous obtiendrons alors un bruit évolutif en trois dimensions

for (int i=0; i<hauteurMax; i++) {
    for (int j=0; j<largeurMax; j++) {
      //definition de la position x,y de chaque point
      float x = j * resolutionLargeur
      float y = ij * resolutionHauteur
        float angle = noise(i * 0.1, j * 0.1, frameCount *0.01) * TWO_PI; //3imensions, l'aléatoire renvoyé est différent pour chaque ligne et différent pour chaque colonne et n'est pas animé car i et j sont identiques à chaque frame
      float endx = x + cos(angle) * largeur/2;
      float endy = y + sin(angle) * hauteur/2; 
      stroke(255);
      line(x, y, endx, endy);
    }
  }

Par la suite nous pouvons également ajouter de nombreuses variations telles qu’une variation de la longueur des directions selon un aléatoire brownien ou perlin, un changement de couleur ou encore la mise en place d’un flow field polaire.

** Algorithm tips : le bruit Perlin et courbes **

Le bruit perlin est défini selon un certain nombre de paramètres, parmi ces derniers on peut citer le Niveau de Détails,  ou LoD (Level of Details) et le Décrément ou Falloff. Ces deux valeurs sont globalement responsables du nombre de turbulences présentes dans le bruit perlin. Ces valeurs peuvent être modifiées dans Processing à l’aide de la méthode suivante :

noiseDetail(lod, falloff);
Où lod est un nombre entier et falloff un nombre décimal

La manipulation de ces valeurs peuvent facilement permettre de réaliser un bruit perlin proche de la courbe reproduisant des motifs à base polaire plus connue sous le nom de Curl Noise.

Pour réaliser ce type de motif nous allons utiliser la méthode noiseDetail afin de définir la turbulence de notre bruit mais également déplacer notre point sur scène selon un incrément dépendant de notre noise. Nous pouvons décomposer notre algorithme de la manière suivante :

Soit un point P à une position x,y aléatoire en début de programme.
À chaque frame :
    1- Soit un incrément mx défini selon un bruit perlin à deux dimensions à partir de la position y de notre point
    2- Soit un incrément my défini selon un bruit perlin à deux dimensions à partir de la position x de notre point
   3- soit OF la valeur d’offset séparant nos point à chaque frame
   3- Soit mx et my des incrémentant variant de -OF  à +OF 

x = x + mx;
y = y + my;

Soit dans processing, pour une valeur OF = 4, x=random(width), y = random(height) et noiseDetail(500, 0.5);

float mx = map(noise(y * 0.01, y * 0.01), 0, 1, -4, 4);
float my =  map(noise(x * 0.01, x * 0.01), 0, 1, -4, 4);
x = x+ mx;
y = y+ my;

 Circle Packing

En géométrie, le Circle Packing est l’étude de l’arrangement des cercles, de taille identique ou variables, dans un espace sans que ces derniers de ne se superposent. Le packing de forme, qu’il soit circulaire ou d’une autre forme est un motif assez régulier dans le domaine de la création visuelle. Il permet de mettre en place un système de grille plus organique et moins rigide de la grille cartésienne classique — quoique de nombreuses grilles cartésiennes n’ont rien à envier au circle packing; le travail Grid Index de Carsten Nicolai en est un très bon exemple. On retrouve ce type de motif dans la reproduction de comportements cellulaires où chaque cellule cherche à occuper son espace sans pour autant se superposer les unes aux autres.

Le circle packing est un comportement que nous pouvons décrire de la manière suivante :

Soit un espace E 2D défini par une largeur et une hauteur.
Soit un lot L de cercle de taille de 0 et des position x,y aléatoire dans cet espace E.

Pour cet espace nous définissons une position P aléatoire.
S’il n’existe aucun obstacle à cette position P alors nous y créons un cercle que nous ajoutons au lot L.
S’il existe un obstacle à la position P alors nous cherchons une un nouvelle position aléatoire P’
.
Pour chacun des cercles du lot L :
Le rayon R s’incrémente d’une vitesse S
Si le cercle rencontre un obstacle (un autre cercle) alors son incrémentation s’arrête
Si le cercle rencontre les limites de l’espace alors son incrémentation s’arrête.

Afin de mettre en place ce comportement nous aurons donc besoin :

  1. D’un espace (notre scène)
  2. D’un lot de cercle définit par les variables et comportement
    1. Coordonnées x,y
    2. Rayon r
    3. Vitesse de rayon sr
    4. État gowing vrai/faux
    5. Fonction permettant de grossir (growing)
    6. Fonction permettant de savoir si le cercle à dépasser les limites de l’espace E
    7. Fonction permettant de savoir si le cercle rencontrer un obstacle (autre cercle) et arrêtant son grossissement le cas échéant.
  3. Une fonction permettant de définir si une position aléatoire est occupée ou non
  4. Fonction permettant d’ajouter un cercle C au lot L

En analysant notre algorithme nous remarquons que nos cercles disposent à la fois de plusieurs variables mais également des fonctions qui leur sont propres. Nos cercles seront donc des éléments disposant à la fois de variables mais de comportements propres (fonctions), ce que nous appellerons en programmation un Objet.

** Algorithm tips : les objets (Classe) **

La programmation orientée objet est l’une des bases de programmation moderne et se retrouve dans un grand nombre de langages de programmation tel que le C++, C#, Java…
Un objet est directement inspiré du monde réel. En effet nous sommes entourés d’objets et chacun de ces objets à des propriétés propres.

Prenons par exemple deux téléphones, mon téléphone portable et mon téléphone fixe. Ces deux téléphones sont différents, ils ne sont pas de la même marque, de la même taille et n’ont pas les mêmes fonctions. Pourtant ils ont une chose en commun : il s’agit de Téléphone et leur fonction principale est le fait de pouvoir passer des communications vocales par le biais d’un réseau téléphonique. Nous dirons alors que ces téléphones sont des “instance” (objets) de la classe Téléphone.
Une classe est une matrice, un patron, un plan de construction… d’un objet. La classe d’un objet permet de créer et d’instancier les variables communes à tous nos objets, de développer leurs comportements et de créer la méthode de construction de notre objet. D’un point de vue développement, elle est assez proche de la façon dont nous construisons un programme. Là où notre programme dispose de variables, d’une fonction d’initialisation et d’une boucle principale, notre classe suivra le même type de syntaxe à savoir :

Déclaration de la classe : 
Déclaration des variables afférent à la classe
Déclaration du constructeur de la classe et de ses paramètre
Déclaration des fonctions de la classe

Dans processing cela se traduit de la manière suivante

class Telephone{
       //ici déclaration des variables
       float x;
       float y;

      //Déclaration du constructeur. Nous noterons qu’un constructeur est la fonction portant le nom de la class
    Telephone(paramètre){
       //Affectation des variables
    }

   //Functions de la classe
   void run(){
      //instruction
   }

   void appel(){
      //instruction
   }
}

Une fois le patron de la classe écrit nous pourrons alors créer dans notre programme des instances (objets) de cette classe. Pour ce faire nous déclarons un objet du type de la classe nous l’instancierons en appelant son constructeur.

Telephone monTelephonePortable = new Telephone();
Telephone monTelephoneFixe = new Telephone();

Une fois l’objet instancié nous pourrons accéder à ces variable par son nom ou faire effectuer une fonction à une instance par les procédés suivants :

Float positionXduPortable = monTelephonePortable.x;

//Passer un appel avec mon téléphone fixe
monTelephoneFixe.appel();

 


Afin de réaliser notre motif de Circle Packing nous allons décomposer notre programme de la manière suivante :

  1. Création d’une classe Cercle simple aux variables et fonctions suivantes :
    1. Coordonnées x,y
    2. Rayon r
    3. Vitesse de rayon sr
    4. État growing vrai/faux
    5. Fonction permettant de grossir (growing)
  2. Création d’une liste dynamique d’objets Cercle à laquelle nous ajoutons, à chaque frame, un nouveau cercle à une position aléatoire non occupée par un cercle précédent
  3. Comportement d’expansion pour chacun de ces cercles en fonction de la vitesse et limitation lorsqu’ils atteignent les limites de la scène
  4. Limitation de l’expansion des cercles lorsqu’ils atteignent un obstacle (overlapping avec un autre cercle)

Création de la classe Cercle

Nous allons dans un premier temps créer la classe Cercle avec les principales variables à savoir la position, le rayon, la vitesse du rayon, l’état du cercle et son constructeur prenant comme argument une position x,y qui seront passé à la création de l’instance.

class Circle {
  float x, y;
  float radius;
  float speedRadius;
  boolean growing = true;

  Circle(float x_, float y_) {
    x = x_;
    y = y_;
   speedRadius = random(1, 5);
    radius = 0;
  }
}

Nous ajoutons ensuite les différentes fonctions nécessaires à savoir son expansion et son dessin.
La première est une fonction assez simple définie de la manière suivante

Si le cercle est en expansion alors le rayon s’incrémente de sa vitesse

Soit dans processing :
void grow() {
    if (growing == true) {
      radius += speedRadius ;
    }
  }

La seconde est une méthode de dessin simple à savoir

void display() {
    stroke(255);
    noFill();
    ellipse(x, y, radius * 2, radius * 2);
  }

Nous obtenons alors la classe suivante :

class Circle {
  float x, y;
  float radius;
  float speedRadius;
  boolean growing = true;

  Circle(float x_, float y_) {
    x = x_;
    y = y_;
   speedRadius = random(1, 5);
    radius = 0;
  }

void grow() {
    if (growing == true) {
      radius += speedRadius ;
    }
  }

 void display() {
    stroke(255);
    noFill();
    ellipse(x, y, radius * 2, radius * 2);
  }
}

Ajout d’objets Cercle à des positions non occupées

La seconde partie de notre programme concerne la génération des cercles. Nous savons qu’à chaque frame nous souhaitons rajouter un cercle dans une liste d’objets de type Cercle à une position non occupée. Pour ce faire nous avons besoin de mettre en place deux éléments :

  1. Une liste dynamique contenant des objets et pouvant s’agrandir
  2. Un algorithme capable de créer un objet de type Cercle à une position aléatoire non occupée par les cercles présents dans la liste

Afin de réaliser notre liste dynamique nous utiliserons l’objet ArrayList<Type>  présent dans processing.

Un ArrayList<Type> est une liste dynamique d’objets, c’est-à-dire un tableau sans fin dans lequel nous pourrons stocker nos objets afin de les appeler aux frames suivantes. Dans Processing — et en Java — les ArrayList<Type>   s’utilisent de la manière suivante :

//Création d’une liste d’objet de class Type :
ArrayList<Type> list;

//initialisation de la liste, généralement dans la méthode setup 
list = new ArrayList<Type>();

//ajout d’un objet/variable dans la liste
list.add(new Type());

//Récupération de l’objet à l’index i dans la liste
list.get(i);

//Suppression d’un élément à l’index i dans la liste
liste.remove(i);

//taille de la litse
liste.size();

Dans notre cas nous créons notre liste de la manière suivante :

ArrayList<Cercle> listeDeCercle;

//Nous initialisons notre liste à la création du programme dans la fonction setup();
listeDeCercle = new ArrayList<Cercle>();

La seconde étape consiste à créer, pour chaque frame, un cercle à une position aléatoire non occupée par un cercle précédent. Pour ce faire nous allons créer une fonction de type Cercle — c’est-à-dire qui nous renvoie un objet de type cercle — se décomposant de la manière suivante :

//fonction renvoyant un objet de type cercle 
Soit une position aléatoire x,y dans les limite de la scène
Pour l’ensemble des cercles présent sur scène
Nous calculons la distance séparant les position du cercle
Si cette position est inférieur au rayon du cercle alors la position n’est pas disponible et nous devons définir une nouvelle position aléatoire
Si les distance est supérieur aux rayons des cercles alors cette position est disponible et nous pouvons créer un cercle à cette position

 

Dans processing nous traduisons cela par la méthode suivante :

//Création du fonction de type Cercle, cad qui renvoie un objet de type Cercle
Circle getNewCircle() {
   //définition d’une position aléatoire
  float x_ = random(width);
  float y_= random(height);

  //Check si la position est disponible
  boolean validCircle = true;

   //Pour chaque cercle de la liste
  for (int i=0; i<circleList.size(); i++) {
   // Nous récupérons le cercle à l’index i
    Circle circle = circleList.get(i);
    
    //nous calculons la distance entre le point et le cercle
    float distance = dist(x_, y_, circle.x, circle.y);

    //Si cette distance est inférieur au rayon du cercle alors nous arrêtons la fonction et cherchons une nouvelle position.
    if (distance < circle.radius) {
      validCircle = false;
      break;
    }
  }

//Sinon nous envoyons un cercle à la position xy
  if (validCircle == true) {
    return new Circle(x_, y_);
  } else {
    return null;
  }
}

Une fois cette méthode créée nous pouvons alors l’ajouter à la boucle principale de notre programme (le draw() dans processing)

void draw() {
  background(20);
  Circle newCircle = getNewCircle();
  if(newCircle != null){
    listeDeCercle .add(newCirlce);
  }
}

Comportement d’expansion dans la limite de la scène

Une fois nos cercles ajoutés à notre liste nous devons activer leurs expansions, la limiter aux bords de la scène et les afficher sur scène. Afin de limiter nos cercles sur la scène nous allons devoir comparer sa position, en incluant son rayon, afin de définir si le cercle dépasse ou non de l’espace.

Nous ajouterons alors la méthode suivante à notre classe Cercle :

// fonction vérifiant si le cercle sort de la scène. Si ce dernier sort de la scène alors nous changeons son état “growing” en faux
Si la position x du cercle est inférieur à la limite min de la scène + le rayon
Alors le cercle sort de la scène
Ou si la position x du cercle est supérieur à la limite max de la scène - le rayon
Alors le cercle sort de la scène
Ou si la position y du cercle est inférieur à la limite max de la scène + le rayon
Alors le cercle sort de la scène
Ou si la position y du cercle est supérieur à la limite max de la scène +- le rayon
Alors le cercle sort de la scène

Dans processing nous traduisons par la méthode suivante : 
Void checkEdges() {
    if (x + radius > width || x - radius < 0 || y + radius > height || y - radius < 0) {
      Growing = false;
    } else {
      Growing = true;
    }
  }

Nous pouvons alors appeler nos cercles dans la boucle principale de notre programme de la manière suivante :

Pour chaque cercle de la liste :
Nous vérifions si le cercle est sortie de la scène
Nous lançons sa méthode d’expansion
Nous affichons le cercle

Soit dans processing 
 for (int i=0; i<listeDeCercle .size(); i++) {
    Circle circle = listeDeCercle .get(i);
   
    circle.checkEdges();
    circle.grow();
    circle.display();
}

Comportement d’arrêt de l’expansion lorsqu’un cercle rencontre un obstacle

Le dernier comportement à ajouter est le suivant : Pour chacun des cercles, si ce dernier rencontre un obstacle (un autre cercle) alors ce dernier arrête son expansion. Si nous savons comment arrêter l’expansion du cercle par la variable growing (true/false) il nous reste à définir quand un cercle rencontre un autre cercle.

En observant le schéma ci-dessus nous remarquons que deux cercles se superposent quand la distance les séparant est inférieure à la somme de leurs rayons.  Nous pouvons donc définir que la limite de l’expansion de nos cercles est définie de la manière suivante dans la boucle principale de notre programme :

Pour chaque cercle de la liste :
Pour chaque autre cercle de la liste
Nous comparant la distance entre les deux cercles
Si cette distance est inférieur à la sommes des rayons
Nous arrêtons l’expansion
Sinon nous continuons l’expansion

Cela se traduira dans processing de la manière suivante 

for(int i=0; i<listeDeCercle.size(); i++){
   Circle c = listeDeCercle.get(i);
  for(int j=0; j<listeDeCercle.size(); j++){ 
   Circle other = listeDeCercle.get(j);
    //si le cercle c est différent du cercle other
    if( c!= other){
       float distance = dist(c.x, c.y, other.x, other.y);
       if(distance <= c.rayon + other.rayon){
          c.growing = false;
       }
    }
  } 
}

Nous obtenons alors  un ensemble de cercles en expansion dont aucuns se superposent dessinant alors notre motif de circle packing.

Diffusion Limited Aggregation

L’agrégation limitée par diffusion est un modèle inventé par Tom Witten et Leonard Sander en 1980 décrivant un processus de collage de particules sur un amas. Le motif très organique en résultant rappel généralement la manière dont évolue l’électricité sur une surface où encore dont se développe un corail.

Le principe d’agrégation limitée par diffusion est assez simple à décrire et consiste en un espace 2D, 3D ou plus dans lequel nous allons introduire une particule P à la création. Nous allons ensuite introduire une seconde particule P’ dans cet espace, cette dernière se déplacera de manière “chaotique” selon un bruit brownien. Lorsque la particule en mouvement P’ rencontre la particule P, c’est-à-dire que les deux particules se touchent, alors la particule P’ se fige et nous introduisons une nouvelle particule en mouvement dans cet espace.

Afin de mettre en place ce comportement nous aurons donc besoin :

  1. D’un espace (notre scène)
  2. D’un lot de particules définit par les variables et comportements suivants :
    1. Coordonnées x,y
    2. Rayon r
    3. État figé vrai/faux
    4. Fonction permettant de se déplacer de manière aléatoire selon un bruit brownien
    5. Fonction permettant de savoir si la particule a rencontré un obstacle ou non

On remarque à la description de notre modèle que nous ce dernier est relativement proche du modèle précédent à savoir le Circle Packing. En effet comme pour ce dernier nous aurons besoin :

  1. Un classe de type Cercle permettant de contenir l’ensemble des variables et fonctions de nos particules
  2. Une liste dynamique de particules
  3. Une fonction permettant de définir si deux particules se touchent en comparant leurs distances avec la somme de leurs rayons.

Les deux modèles étant relativement proches nous pouvons donc reprendre des éléments du circle packing.

Création de la classe Particule

Le premier élément que nous allons créer est a classe particule en reprenant la classe Cercle précédemment écrite et en y apportant les modifications suivantes :

  1. Définition de son rayon et d’une vitesse selon des nombres aléatoires

    class Particle{
      float x, y;
      float radius;
       float speed;
      boolean stuck = true;
    
      Particle(float x_, float y_) {
        x = x_;
        y = y_;
        radius = random(20, 40);
        speed= random(20, 40);
      }
    
     void display() {
        stroke(255);
        noFill();
        ellipse(x, y, radius * 2, radius * 2);
      }
    }

     

  2. Nous allons également ajouter une fonction de déplacement selon un aléatoire décrite de la manière suivante :
    1. Si cette dernière n’est pas bloquée
      1. Nous définissons un nombre aléatoire randomX entre 0 et 1
      2. Si randomX est supérieur à 0.5 (soit 50% de chance) alors nous incrémentons x de la vitesse
      3. Sinon nous décrémentons x de la vitesse;
      4. Nous définissons un nombre aléatoire randomY entre 0 et 1
      5. Si randomY est supérieur à 0.5 (soit 50% de chance) alors nous incrémentons y de la vitesse
      6. Sinon nous décrémentons y de la vitesse;

        //Movement de la particules
        // 
              
        void move(){
            if(stuck == false){
                 float randomX = random(0, 1);
                 float randomY = random(0, 1);
                
                if(randomX > 0.5){
                   x += speed
               }else{
                  x -= speed;
               }
               if(randomY > 0.5){
                   y += speed
               }else{
                  y -= speed;
               }
           }
        }

Nous obtenons alors la classe suivante :

class Particle{
  float x, y;
  float radius;
   float speed;
  boolean stuck = true;

  Particle(float x_, float y_) {
    x = x_;
    y = y_;
    radius = random(20, 40);
    speed= random(20, 40);
  }

void move(){
    if(stuck == false){
         float randomX = random(0, 1);
         float randomY = random(0, 1);
        
        if(randomX > 0.5){
           x += speed
       }else{
          x -= speed;
       }
       if(randomY > 0.5){
           y += speed
       }else{
          y -= speed;
       }
   }
}

 void display() {
    stroke(255);
    noFill();
    ellipse(x, y, radius * 2, radius * 2);
  }
}

Mise en place de la scène

La seconde étape est la mise en place de la scène. Nous savons que notre modèle dispose de deux éléments principaux à savoir :

  1. Un lot de particules figées possédant 1 particule à la frame 0
  2. Une particule en mouvement

Pour ce faire nous allons donc mettre en place une liste dynamique de type Particule à laquelle nous ajouterons une particule en début de programme. Nous figerons cette première particule en indiquant la valeur de booléenne stuck comme vrai. Nous allons ensuite créer un objet particule à une position aléatoire sur la scène. Enfin pour chaque frame nous allons dessiner nos particules et faire se déplacer la particule en mouvement.

ArrayList<Particle> listDeParticule;
Particule particule;

void setup() {
  size(500, 500);
  listDeParticule = new ArrayList<Particule>();
  Particule premiereParticule = new Particule(random(width), random(height);
  premiereParticule.stuck = true;
  listDeParticule.add(premiereParticule);


  particule = new Particule(random(width), random(height);
} 

void draw(){
  background(0);
  particule.move();
  particule.display();
  
  for(int i=0; i<listDeParticule.size(); i++){
    Particule particulesFigee = listDeParticule.get(i);
    particulesFigee.display();
  }
}

Comportement d’agrégation

La dernière étape de notre modèle consiste à figer la particule en mouvement lorsque celle-ci touche une particule déjà figée. Ce comportement se décrit de la manière suivante :

  1. Si la particule en mouvement touche l’une des particules figées présentes dans le lot de particules
    1. Alors nous figeons la particule en mouvement
    2. Nous l’ajoutons au tableau de particules figées
    3. Nous créons une nouvelle particule en mouvement sur scène

Afin de définir si une particule en touche une autre nous utiliserons la même méthode que celle utilisée dans le modèle du Circle Packing, à savoir la comparaison de distance entre les deux éléments. En effet si la distance séparant les deux particules est inférieure à la somme de leurs rayons alors celles-ci se touchent.

Cette comparaison s’effectuant entre la particule en mouvement et le lot de particules nous la réaliserons dans une boucle for du lot de particules de la manière suivante :

for (int i=0; i<listDeParticule .size(); i++) {
    Particule other = listDeParticule.get(i);
    float distance = dist(particule.x, particule.y, other.x, other.y);
    if (distance  <= other.radius + particule.radius) {
      particule.stuck = true;
      listDeParticule.add(particule);
      particule = new Particule(random(width), random(height);
      break;
    }
  }

Nous obtenons alors notre comportement d’agrégation limitée par diffusion.

Réaction-Diffusion

La réaction-diffusion est un modèle mathématique décrivant l’évolution de substances soumises à deux processus : Un processus chimique d’évolution (ou réaction) et un processus de diffusion provoquant une répartition des substances dans l’espace. L’un des modèles les plus connus de ce type de comportement est la réaction-diffusion de Gray-Scott. Ce modèle est largement utilisé dans le domaine de la création visuelle, notamment dans la réalisation de motifs organiques et naturels.

L’artiste Karl Sim décrit ce modèle de la manière suivante :

  1. Soit un espace 2D (une grille)
  2. Soit cet espace remplit d’un élément A selon une certaine vitesse dite “Feedrate”
  3. Soit l’introduction, de manière aléatoire d’éléments B dans la grille
  4. Deux éléments B convertissent un élément A en B lorsqu’ils sont proche d’un élément A
  5. Les éléments B sont retirés à une certaines vitesse dite “KillRate”

Pour chaque frame, et chaque élément A et B de chacune des cellules, la réaction-diffusion est décrite selon algorithme suivant :

A’ = A + (Da * ∇ 2A – A*B2 + f*(1 – A) );

B’ = B + (Db * ∇ 2B + A*B2 -(k + f)*B );

Où :

  1. A est l’élément chimique A;
  2. B est l’élément chimique B;
  3. Da et Db sont les vitesses de diffusion des éléments A et B
  4. 2A et ∇2B sont les fonctions Laplacienne 2D donnant la valeur moyenne des éléments A et B en fonction de leurs voisins respectifs
  5. A*B2 est la réaction
  6. f est la vitesse d’introduction de A
  7. k est la vitesse de retrait de B

Afin de réaliser ce modèle nous aurons donc besoin de mettre en place :

  1. Une grille (notre espace 2D) contenant pour chaque cellule des éléments nécessaires à la réaction-diffusion
  2. Une classe de type Cellule contenant nos éléments A et B pour chaque cellule de la grille
  3. Une fonction calculant la valeur Laplacienne 2D pour les éléments A et B

Le modèle se déroulant par comparaison — A’ et B’ sont les nouvelles valeurs de A et B après réaction-diffusion — nous aurons besoin de connaître à tout moment la valeur des éléments chimiques à l’instant T et T+1. Pour cela nous mettrons en place deux grilles. La première contiendra nos éléments à l’instant T et la seconde contiendra nos éléments à l’instant T+1. une fois le calcul de réaction diffusion réalisé nous échangerons les grilles entre elles afin de réaliser la réaction à la frame suivante.

Mise en place des variables

La première étape consiste en la mise en place des variables nécessaires à notre algorithme, à savoir :

  1. Da et Db
  2. f et k

Ici nous utiliserons les valeurs suivantes :

float dA = 1.0;
float dB = 0.5;
float feedRate = 0.05;
float killRate = 0.062;

Mise en place de la classe Cellule

La classe Cellule est un modèle simple disposant des variables suivantes :

  1. Position x,y de la cellule
  2. Largeur et hauteur de la cellule
  3. Valeur de l’élément A
  4. Valeur de l’élément B
class Cell {
  float cellWidth, cellHeight;
  float x, y;

  //chemical
  float a, b;

  Cell(float x_, float y_, float w_, float h_) {
    x = x_;
    y = y_;
    cellWidth = w_;
    cellHeight = h_;
  }
}

Mise en place des grilles N et N+1

Nous allons ensuite mettre en place nos deux grilles, chaque grille sera un pavage de paramètres identiques que nous utiliserons sous forme d’un tableau à deux dimensions. Nous remplissons chacune de ces grilles avec l’élément A de valeur 1.0 par Cellule. Enfin nous introduisons l’élément B pour 1.0/100.0 des cellules de la grille N répartit de manière aléatoire entre les cellules

int rows, cols;
int resX, resY;
Cell[][] cellList;
Cell[][] nextCellList;

//initialisation de la grille
resX = 5;
  resY = 5;
  rows = height / resY;
  cols = width / resX;
  cellList = new Cell[rows][cols];
  nextCellList = new Cell[rows][cols];

  //start by creating a grid
  for (int i=0; i<rows; i++) {
    for (int j=0; j<cols; j++) {
      int x = j * resX;
      int y = i * resY;
      cellList[i][j] = new Cell(x, y, resX, resY);
      nextCellList[i][j] = new Cell(x, y, resX, resY);
      //fill the first and next grid with chemical a = 1.0
      cellList[i][j].a = 1.0;
      nextCellList[i][j].a = 1.0;

      //fill the first grid with chemical b for random 1/100 of the grid
      float randomChemicalB = random(1);
      if (randomChemicalB < 1.0/100.0) {
        cellList[i][j].b = 1.0;
      }
    }
  }

Réaction diffusion des éléments

Une fois nos grilles mises en place nous pouvons, dans la boucle principale de notre programme, calculer la réaction-diffusion entre les éléments A et B pour chacune de nos cellules. Pour ce faire nous réaliserons une double boucle for afin de nous adresser à chaque cellule de nos grilles. Nous utiliserons la grille N afin de récupérer la valeur des éléments A et B et la grille N+1 afin de stocker les valeurs A’ et B’ de nos éléments après réaction-diffusion.

La première étape consiste à mettre en place la fonction Laplacienne 2D. Sans entrer dans la définition mathématique, la fonction Laplacienne 2D est la fonction qui, pour une grille donnée, renvoie la valeur moyenne de chaque cellule calculée par rapport aux valeurs adjacentes (voisine). Chaque “voisin” disposera d’une valeur de poids dans le calcul, c’est-à-dire que plus le “voisin” est éloigné de l’élément dont nous calculons la valeur moyenne plus son poids dans l’équation sera faible.

Nous allons donc réaliser une fonction laplacienne 2D pour chacun des éléments A et B. Cette fonction prendra pour arguments l’index i,j de la cellule afin de récupérer ces valeurs d’élément A et B

Float near = 0.2;
Float far = 0.05;

float laplaceA(int i, int jl) {
  float sum = 0;
  sum += cellList[i][j].a * -1;
  //nearest neighbors
  if (i > 1 && i < rows-1 && j > 1 && j < cols-1) {
    sum += cellList[i-1][j].a * near;
    sum += cellList[i+1][j].a * near;
    sum += cellList[i][j-1].a * near;
    sum += cellList[i][j+1].a* near;
    //Farest neighbors
    sum += cellList[i-1][j-1].a * far;
    sum += cellList[i+1][j-1].a * far;
    sum += cellList[i+1][j+1].a * far;
    sum += cellList[i-1][j+1].a * far;
  }

  return sum;
}

float laplaceB(int i, int jl) {
  float sum = 0;
  sum += cellList[i][j].b * -1;
  //nearest neighbors
  if (i > 1 && i < rows-1 && j > 1 && j < cols-1) {
    sum += cellList[i-1][j].b * near;
    sum += cellList[i+1][j].b * near;
    sum += cellList[i][j-1].b * near;
    sum += cellList[i][j+1].b* near;
    //Farest neighbors
    sum += cellList[i-1][j-1].b * far;
    sum += cellList[i+1][j-1].b * far;
    sum += cellList[i+1][j+1].b * far;
    sum += cellList[i-1][j+1].b * far;
  }

  return sum;
}

Une fois cette fonction réalisée nous disposons de tous les éléments nécessaires au calcul de la réaction-diffusion soit :

for (int i=0; i<rows; i++) {
    for (int j=0; j<cols; j++) {
      Cell c = cellList[i][j];
      Cell n = nextCellList[i][j];

      //reaction formula      
      //gray-scott model
      n.a = c.a + (dA * laplaceA(i, j) - (c.a * c.b * c.b) + feedRate * (1.0 - c.a));
      n.b = c.b + (dB * laplaceB(i, j) + (c.a * c.b * c.b) - c.b * (killRate + feedRate));
      //constrain reaction
      n.a = constrain(n.a, 0, 1);
      n.b = constrain(n.b, 0, 1);
    }
  }

À noter que nous avons ici restreint les valeurs des éléments A et B entre 0 et 1. En effet nous utiliserons par la suite ces valeurs comme incrément pour la couleur de notre motif. Ces derniers devront donc toujours être compris entre 0 et 1.

Enfin il nous reste à échanger les grilles de sorte à ce que la grille N+1 contenant les valeurs A’ et B’ deviennent la valeur de base A et B à la frame suivante. Pour ce faire nous utiliserons la méthode suivante :

  1. Nous définissons une grille temporaire T comme une copie de N
  2. Nous définissons N comme égale à N+1
  3. Nous définissons N+1 comme égale à T

Nous réalisons cela dans une fonction que nous appelons à la fin de la boucle principale de notre programme :

void swapGrid() {
  //swap grid
  //Next become actual and actual become next...
  Cell[][] tmpGrid = cellList;
  cellList = nextCellList;
  nextCellList = tmpGrid;
}

Nous pouvons alors dessiner notre motif à partir des valeurs des éléments A et B précédemment calculés. Pour ce faire nous allons calculer l’incrément de la couleur correspondante pour chaque cellule. Cet incrément sera égal à : A – B

for (int i=0; i<rows; i++) {
    for (int j=0; j<cols; j++) {
      Cell c = cellList[i][j];
      float inc = c.a - c.b
       color c = color(255 * inc);
      rect (c.x, c.y, c.cellWidth, c.cellHeight);
    }
  }

Rappel des algorithmes et méthodes

  1. Nous utilisons la méthode noise(x, y, z) afin de définir une valeur aléatoire perlin, c’est-à-dire proche de sa valeur précédente
  2. Nous utilisons la méthode noiseDetail(lod, fallof) afin de définir la précision du bruit perlin
  3. Nous utilisons des classes pour décrire des éléments/objets disposant de leur propre variable et fonctions
  4. Nous utilisons des List dynamique pour stocker un nombre indéfini d’éléménts par le biai de l’objet ArrayList<Type>
  5. Nous comparons la distance entre 2 points et la somme de leurs rayons respectifs pour définir si ces derniers se superposent
  6. La réaction-diffusion entre deux éléments A et B est définie de la manière suivante :
    1. A’ = A + (Da * ∇ 2A – A*B2 + f*(1 – A) );
    2. B’ = B + (Db * ∇ 2B + A*B2 -(k + f)*B );

Pour aller plus loin

Réaliser les exercices suivants :

  1. Réaliser un Flowfield en faisant varier la grille, son dessin ou sa forme (système polaire)
  2. Introduisez de l’aléatoire brownien dans votre motif pour définir un nouveau comportement
  3. Réaliser un motif de circle packing restreint dans une forme (cercle) ou image
  4. Ajouter de nouveaux comportements à la classe Cercle (changement de couleur, forme taille…)
  5. Réaliser différents motifs d’agrégation limitée par diffusion (agrégation centrale, linéaire, mouvement perlin…)
  6. Réaliser différents motifs de Réaction-Diffusions

Annexes :

  1. Circle Packing, julien Leonard : http://julienleonard.com/circle-packing-2×2.html
  2. Circle Packing, Daniel Shiffman : https://www.youtube.com/watch?v=pF0cadg2mg0
  3. Animated Circle Packing, Part.1 Daniel Shiffman : https://www.youtube.com/watch?v=QHEQuoIKgNE
  4. Animated Circle Packing, Part.2 Daniel Shiffman : https://www.youtube.com/watch?v=ERQcYaaZ6F0
  5. Circle Packing Theorem : https://en.wikipedia.org/wiki/Circle_packing_theorem
  6. Circle Packing : https://en.wikipedia.org/wiki/Circle_packing
  7. Circle packing, a mathematical tale : http://www.ams.org/notices/200311/fea-stephenson.pdf
  8. Circle packing maths : http://mathworld.wolfram.com/CirclePacking.html
  9. Random Space filling tiling of a plane : http://paulbourke.net/texture_colour/randomtile/
  10. Agrégation limitée par diffusion : http://www.epm6604b.be/dla/dla_2d.html
  11. Diffusion limited Aggregation : https://en.wikipedia.org/wiki/Diffusion-limited_aggregation
  12. Diffusion Limited Aggregation, Paul Bourke : http://paulbourke.net/fractals/dla/
  13. Réaction Diffusion, Karl Sim : http://karlsims.com/rd.html
  14. Réaction Diffusion, Will Cavanagh & Andrew Finley : https://sdm.scad.edu/faculty/mkesson/vsfx419/wip/best/spring15/william_cavanagh/index.html