93 lines
3.1 KiB
TeX
93 lines
3.1 KiB
TeX
L'algorithme du bruit de Perlin se décompose en 3 parties que sont:
|
|
\begin{enumerate}
|
|
\item la définition de la grille.
|
|
\item le calcul du produit scalaire entre le vecteur gradiant et le vecteur
|
|
distance.
|
|
\item l'interpolation entre ces valeurs.
|
|
\end{enumerate}
|
|
|
|
|
|
Pour la définitionde la grille, il faut définir une grille à $n$ dimensions.
|
|
Attribuer pour chaque nœud un vecteur de gradient aléatoire de norme 1 et de
|
|
dimension $n$.
|
|
\newline
|
|
|
|
Pour ce qui concerne le produit scalaire, nous faisons comme suit:
|
|
|
|
Soit un point de l'espace à $n$-dimensions envoyé à la fonction de bruit,
|
|
l'étape consiste à déterminer dans quelle cellule de grille le point donné se
|
|
situe. 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. Cela conduit à l'échelle
|
|
de complexité $O(2^{n})$.
|
|
\newline
|
|
|
|
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é.
|
|
\newline
|
|
|
|
Voici une version C++ de l'implantation du bruit de Perlin à 2 dimensions:
|
|
|
|
\begin{minted}{c++}
|
|
// Function to linearly interpolate between a0 and a1
|
|
// Weight w should be in the range [0.0, 1.0]
|
|
float lerp(float a0, float a1, float w) {
|
|
return (1.0 - w)*a0 + w*a1;
|
|
|
|
// as an alternative, this slightly faster equivalent
|
|
// formula can be used:
|
|
// return a0 + w*(a1 - a0);
|
|
}
|
|
|
|
// Computes the dot product of the distance and gradient
|
|
// vectors.
|
|
float 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
|
|
float perlin(float x, float y) {
|
|
|
|
// Determine grid cell coordinates
|
|
int x0 = int(x);
|
|
int x1 = x0 + 1;
|
|
int y0 = int(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;
|
|
}
|
|
\end{minted}
|