Algorithme Diamant-Carré

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

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[modifier | modifier le code]

L'algorithme utilise une matrice carrée de taille 2n + 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.Exécution de l'algorithme diamant-carré pour une matrice de taille 5.png

Pseudo-code[modifier | modifier le code]

Ci-dessous un exemple d'implémentation en pseudo-code de l'algorithme diamant-carré pour un tableau t de côté 2n + 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
        pour x allant de 0 à h avec un pas de id  /* début de la phase du carré */
            si x % i = 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[modifier | modifier le code]

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

Annexes[modifier | modifier le code]

Articles connexes[modifier | modifier le code]

Liens externes[modifier | modifier le code]