Algorithme Diamant-Carré

L'algorithme diamant-carré (ou Diamond-Square) est une méthode utilisée pour la réalisation de terrains fractals pour la synthèse d'image. Il a d'abord été énoncé par Gavin S. P. Miller.

Fonctionnement

L'algorithme utilise une matrice carrée de taille 2ⁿ + 1. Les quatre coins sont initialisés avec une valeur aléatoire. La matrice est alors parcourue en effectuant alternativement les phases du diamant puis du carré, en divisant à chaque itération le pas par 2 :

Diamant : le centre de chaque carré prend pour valeur la moyenne des 4 points formant ce carré ajoutée d'une valeur aléatoire.
Carré : le centre de chaque diamant (ou losange) prend pour valeur la moyenne des 4 points formant ce diamant ajoutée d'une valeur aléatoire.
Le pas est divisé par deux et le processus est répété.

L'algorithme s’arrête quand toutes les valeurs de la matrice ont été remplies.

La valeur aléatoire ajoutée à chaque phase doit être de plus en plus petite lorsque l'itération augmente, afin de garder une cohérence dans la texture produite.

Les images ci-dessous montrent l'exécution de algorithme diamant-carré pour une matrice de taille 5.

Pseudo-code

Ci-dessous un exemple d'implémentation en pseudo-code de l'algorithme diamant-carré pour un tableau t de côté 2ⁿ + 1

 fonction diamant-carré (tableau t)
    h = t.coté()
    t[0, 0] = rand(-h, h)  /* initialisation des coins */
    t[0, h-1] = rand(-h, h)
    t[h-1, h-1] = rand(-h, h)
    t[h-1, 0] = rand(-h, h)
    i = h-1
    tant_que i > 1
        id = i/2
        pour x allant de id à h avec un pas de i  /* début de la phase du diamant */
            pour y allant de id à h avec un pas de i
                moyenne = (t[x - id, y - id] + t[x - id, y + id] + t[x + id, y + id] + t[x + id, y - id]) / 4
                t[x, y] = moyenne + rand(-id, id)    
            fin pour
        fin pour
        décalage = 0
        pour x allant de 0 à h avec un pas de id  /* début de la phase du carré */
            si décalage = 0 alors
                décalage = id
            sinon
                décalage = 0
            fin si
            pour y allant de décalage à h avec un pas de i
                somme = 0
                n = 0
                si x >= id alors
                    somme = somme + t[x - id, y]
                    n = n+1
                fin si
                si x + id < h alors
                    somme = somme + t[x + id, y]
                    n = n+1
                fin si
                si y >= id alors
                    somme = somme + t[x, y - id]
                    n = n+1
                fin si
                si y + id < h alors
                    somme = somme + t[x, y + id]
                    n = n+1
                fin si
                t[x, y] = somme / n + rand(-id, id)
            fin pour
        fin pour
        i = id
    fin tant_que
fin fonction

Application

Cet algorithme est largement utilisé pour la création de champs de hauteur (permettant ensuite la génération de paysage en 3D réalistes) ou de textures procédurales (bois, nuages...). Certains logiciels générateurs de paysages comme Terragen utilisent ce type d'algorithmes.

Texture procédurale créée avec l'algorithme diamant-carré

Champ de hauteur correspondant

Exemple de paysage en 3D créé avec le freeware Terragen

Par extension, il est facile de boucler les valeurs, pour créer des textures jointives, de partir d'un rectangle formé d'un ensemble de carrés de forme 1+(2^n), par exemple 6*(1+(2^4)) par 7*(1+(2^4)). Il est également possible de faire des approximations lorsqu'on "coupe en 2" les valeurs pour prendre la coordonnée au milieu du segment, si le carré n'est pas en 1+ 2^n, mais il est plus facile de changer la taille de la texture après.

Annexes

Liens externes