Algorithme Diamant-Carré
# 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^n$ + 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^n$ + 1

## 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.

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.

