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
modifierL'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.
Pseudo-code
modifierCi-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
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
modifierCet 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.
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.
