Bruit de Perlin

Le bruit de Perlin est une texture procédurale utilisée comme effet visuel pour augmenter le réalisme apparent dans la synthèse d'image. La fonction a une apparence pseudo-aléatoire, et pourtant tous ses détails visuels sont de taille égale (voir image). Cette propriété permet à cette texture d'être facilement contrôlable. De multiples copies zoomées de bruit de Perlin peuvent être insérées dans des expressions mathématiques pour créer une grande variété de textures procédurales.

Bruit de Perlin en deux dimensions.

Usages

Bruit de Perlin redimensionné et combiné à lui-même pour créer un bruit fractal.

Le bruit de Perlin est une texture procédurale primitive, c'est un bruit de gradient (par opposition aux bruits de valeur) utilisé pour améliorer le réalisme des infographies. La fonction a un aspect pseudo-aléatoire, cependant ses détails sont de la même taille ; cette propriété la rend facilement contrôlable en la combinant à différentes échelles.

Le bruit de Perlin est souvent utilisé dans les images de synthèse pour des éléments tels que le feu, la fumée ou les nuages.

Les démos font couramment usage du bruit de Perlin car il permet de générer des textures en étant très économique en termes d'espace mémoire.

Cette texture procédurale a aussi été utilisée dans des jeux vidéo tel que Minecraft, le jeu appliquait cette texture à la carte, ainsi les endroits plus sombres étaient profonds et les endroits plus clairs étaient hauts par exemple le pic d'une montagne. L'usage de cette texture est ingénieux car il permet la génération d'un monde cohérent dans le jeu .

Feu généré à partir de bruit de Perlin.
Terrain généré à partir de bruit de Perlin.

Développement

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) en 1981, il cherchait à éviter le look « machinique »[1]. Il commença donc par mettre au point une fonction pseudo-aléatoire de bruit qui remplit les trois dimensions de l'espace[2]^,[3], avant d'inventer l'année suivante le premier langage de shading (en)[4]. Ses travaux sur les textures procédurales ont valu à Ken Perlin l'Academy Award for Technical Achievement (en) en 1997[5].

Algorithme

Le bruit Perlin est le plus couramment utilisé à deux, trois, voire quatre dimensions, il peut être défini pour un nombre quelconque de dimensions. L'algorithme se décompose en trois étapes :

définition de la grille avec des vecteurs de gradient aléatoires ;
calcul du produit scalaire entre le vecteur de gradient et le vecteur distance ;
interpolation entre ces valeurs.

Définition de la grille

Définir une grille à n dimensions. À chaque point de la grille (nœud), attribuer un vecteur de gradient aléatoire de longueur unitaire et de dimension n.

Pour une grille à deux dimensions, à chaque nœud sera assigné un vecteur aléatoire du cercle unité, et ainsi de suite pour les dimensions supérieures. Le cas unidimensionnel est une exception : le gradient est un scalaire aléatoire entre -1 et 1.

Le calcul des gradients (pseudo)-aléatoires en une et deux dimensions est trivial en utilisant un générateur de nombres aléatoires. Pour les dimensions supérieures, une approche Monte Carlo peut être utilisée où les coordonnées cartésiennes aléatoires sont choisies dans un cube unité, les points situés en dehors de la sphère unité sont rejetés et les points restants sont normés.

Produit scalaire

Soit un point de l'espace à n-dimensions envoyé à la fonction de bruit, l'étape suivante dans l'algorithme consiste à déterminer dans quelle cellule de grille le point donné tombe. Pour chaque nœud-sommet de cette cellule, calculer le vecteur distance entre le point et le nœud-sommet. Puis calculer le produit scalaire entre le vecteur de gradient au nœud et le vecteur de distance.

Pour un point dans une grille bidimensionnelle, cela nécessitera le calcul de 4 vecteurs de distance et de 4 produits scalaires, tandis que dans les trois dimensions, 8 vecteurs de distance et 8 produits scalaires sont nécessaires. Cela conduit à l'échelle de complexité $O(2^{n})$ .

Interpolation

La dernière étape est l'interpolation entre les $2^{n}$ produits scalaires calculés aux nœuds de la cellule contenant le point d'argument. Cela a pour conséquence que la fonction de bruit renvoie 0 lorsqu'elle est évaluée sur les nœuds de la grille eux-mêmes.

L'interpolation est effectuée en utilisant une fonction dont la dérivée première (et éventuellement la dérivée seconde) est nulle aux $2^{n}$ nœuds de la grille . Cela a pour effet que le gradient de la fonction de bruit résultante à chaque nœud de grille coïncide avec le vecteur de gradient aléatoire précalculé. Si $n=1$ , un exemple de fonction qui interpole entre la valeur $a_{0}$ au nœud de grille 0 et la valeur $a_{1}$ au nœud de grille 1 est

f(x)=a_{0}+\operatorname {smoothstep} (x)\cdot (a_{1}-a_{0})\ \ {\text{for }}0\leq x\leq 1

où la fonction smoothstep (en) a été utilisée.

Les fonctions de bruit utilisées dans l'infographie produisent généralement des valeurs comprises dans la plage [-1.0,1.0]. Afin de produire du bruit Perlin dans cette plage, la valeur interpolée peut avoir besoin d'être mise à l'échelle par un facteur d'échelle.

Pseudo-code

Voici le pseudo-code de l'implémentation du bruit de Perlin dans un espace à deux dimensions.

 // Function to linearly interpolate between a0 and a1
 // Weight w should be in the range [0.0, 1.0]
 function lerp(float a0, float a1, float w) {
     return (1.0 - w)*a0 + w*a1;
 }
 
 // Computes the dot product of the distance and gradient vectors.
 function dotGridGradient(int ix, int iy, float x, float y) {
 
     // Precomputed (or otherwise) gradient vectors at each grid node
     extern float Gradient[IYMAX][IXMAX][2];
 
     // Compute the distance vector
     float dx = x - (float)ix;
     float dy = y - (float)iy;
 
     // Compute the dot-product
     return (dx*Gradient[iy][ix][0] + dy*Gradient[iy][ix][1]);
 }
 
 // Compute Perlin noise at coordinates x, y
 function perlin(float x, float y) {
 
     // Determine grid cell coordinates
     int x0 = floor(x);
     int x1 = x0 + 1;
     int y0 = floor(y);
     int y1 = y0 + 1;
 
     // Determine interpolation weights
     // Could also use higher order polynomial/s-curve here
     float sx = x - (float)x0;
     float sy = y - (float)y0;
 
     // Interpolate between grid point gradients
     float n0, n1, ix0, ix1, value;
     n0 = dotGridGradient(x0, y0, x, y);
     n1 = dotGridGradient(x1, y0, x, y);
     ix0 = lerp(n0, n1, sx);
     n0 = dotGridGradient(x0, y1, x, y);
     n1 = dotGridGradient(x1, y1, x, y);
     ix1 = lerp(n0, n1, sx);
     value = lerp(ix0, ix1, sy);
 
     return value;
 }

Annexes

Notes et références

(en) Ken Perlin, « History », sur www.noisemachine.com (consulté le 19 mai 2014).
(en) Ken Perlin, « Controlled random primitive », sur www.noisemachine.com (consulté le 19 mai 2014).
(en) Ken Perlin, « coherent noise function over 1, 2 or 3 dimensions », sur nyu.edu (consulté le 19 mai 2014).
Code (en C) de la première version de la fonction, en 1983.
(en) Ken Perlin, « Rapid adoption », sur www.noisemachine.com (consulté le 19 mai 2014).
(en) Ken Perlin, « Noise and Turbulence », sur nyu.edu (consulté le 19 mai 2014).

Article connexe

Génération procédurale

Liens externes

(en) Présentation par Ken Perlin
(en) Page de Ken Perlin

Portail de l'informatique théorique
Portail de l’imagerie numérique
Portail des mathématiques

Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.

[KP-History-1] (en) Ken Perlin, « History », sur www.noisemachine.com (consulté le 19 mai 2014).

[KP-Crp-2] (en) Ken Perlin, « Controlled random primitive », sur www.noisemachine.com (consulté le 19 mai 2014).

[code1983-3] (en) Ken Perlin, « coherent noise function over 1, 2 or 3 dimensions », sur nyu.edu (consulté le 19 mai 2014).
Code (en C) de la première version de la fonction, en 1983.

[KP-Ra-4] (en) Ken Perlin, « Rapid adoption », sur www.noisemachine.com (consulté le 19 mai 2014).

[KP-oscar-5] (en) Ken Perlin, « Noise and Turbulence », sur nyu.edu (consulté le 19 mai 2014).