Intervallo di uscita del rumore Perlin

Question

Sto studiando alcune delle varie implementazioni per il rumore coerente (so che ci sono librerie, ma questo è principalmente per la mia edificazione e curiosità) e come puoi usarlo, e c'è un problema Ho con la cosa del rumore Perlin originale.

Secondo this frequently linked Math FAQ, l'intervallo di uscita sarà compreso tra -1 e 1, ma non capisco come il valore possa trovarsi in tale intervallo.

Come ho capito, l'algoritmo è fondamentalmente questo: ogni punto della griglia ha un vettore di gradiente casuale associato di lunghezza 1. Quindi, per ciascun punto, per tutti e quattro i punti della griglia circostante, si calcola il prodotto punto del gradiente casuale e il vettore che passa da quel punto della griglia. Quindi utilizzi una curva di facilità di fantasia e un'interpolazione lineare per portarlo a un valore.

Ma, ecco il mio problema: questi prodotti puntini sono, di tanto in tanto, al di fuori dell'intervallo [-1, 1], e poiché si fa l'interpolazione lineare in definitiva tra i prodotti punto, non significa che il valore finale sarà, a volte, essere al di fuori dell'intervallo [-1, 1]?

Diciamo, per esempio, che uno dei vettori casuali è (sqrt(2)/2, sqrt(2)/2) (che ha una lunghezza di 1) e (0.8, 0.8) (che si trova nella piazza unità), si ottiene un risultato di circa 1.131. Se tale valore viene utilizzato nell'interpolazione lineare, è del tutto possibile che il valore generato sia maggiore di 1. E, in effetti, con la mia implementazione diretta, ciò accade abbastanza frequentemente.

Mi manca qualcosa qui?

Per riferimento, ecco il mio codice in Java. Vec è una semplice classe per eseguire semplici aritmetiche vettoriali 2D, fade() è la curva di facilità, lerp() è l'interpolazione lineare e gradient(x, y) fornisce il gradiente per tale punto di griglia come Vec. La variabile gridSize ti dà la dimensione della griglia in pixel (che è di tipo doppio):

public double getPoint(int x, int y) { 
    Vec p = new Vec(x/gridSize, y/gridSize); 
    Vec d = new Vec(Math.floor(p.x), Math.floor(p.y)); 


    int x0 = (int)d.x, 
     y0 = (int)d.x; 


    double d00 = gradient(x0 , y0 ).dot(p.sub(x0 , y0 )), 
      d01 = gradient(x0 , y0 + 1).dot(p.sub(x0 , y0 + 1)), 
      d10 = gradient(x0 + 1, y0 ).dot(p.sub(x0 + 1, y0 )), 
      d11 = gradient(x0 + 1, y0 + 1).dot(p.sub(x0 + 1, y0 + 1)); 

    double fadeX = fade(p.x - d.x), 
      fadeY = fade(p.y - d.y); 

    double i1 = lerp(fadeX, d00, d10), 
      i2 = lerp(fadeX, d01, d11); 

    return lerp(fadeY, i1, i2); 
} 

Edit: ecco il codice per la generazione di gradienti casuali:

double theta = gen.nextDouble() * 2 * Math.PI; 
gradients[i] = new Vec(Math.cos(theta), Math.sin(theta)); 

Dove gen è un java.util.Random.

Answer 1

Hai y0 = (int)d.x;, ma intendi d.y. Questo sicuramente influirà sul tuo intervallo di output, ed è la ragione per cui stai vedendo valori così fuori dall'intervallo.

---

Detto, la gamma di uscita di rumore Perlin è non effettivamente [-1, 1]. Anche se non sono sicuro della matematica (devo essere invecchiante), this rather lengthy discussion indica che l'intervallo effettivo è [-sqrt (n)/2, sqrt (n)/2], dove n è la dimensionalità (2 nel tuo caso). Pertanto la gamma di output della funzione di disturbo Perlin 2D dovrebbe essere [-0.707, 0,707]. Questo è in qualche modo correlato al fatto che sia d sia i parametri di interpolazione sono una funzione di p.Se leggi questa discussione, potresti trovare la spiegazione precisa che stai cercando (in particolare, post #7).

sto testando l'implementazione utilizzando il seguente programma (che ho messo insieme dal vostro esempio, in modo perdono l'uso di strano gridCells e gridSize):

import java.util.Random; 


public class Perlin { 

    static final int gridSize = 200; 
    static final int gridCells = 20; 
    static final Vec[][] gradients = new Vec[gridCells + 1][gridCells + 1]; 

    static void initializeGradient() { 
     Random rand = new Random(); 
     for (int r = 0; r < gridCells + 1; ++ r) { 
      for (int c = 0; c < gridCells + 1; ++ c) { 
       double theta = rand.nextFloat() * Math.PI; 
       gradients[c][r] = new Vec(Math.cos(theta), Math.sin(theta));     
      } 
     } 
    } 

    static class Vec { 
     double x; 
     double y; 
     Vec (double x, double y) { this.x = x; this.y = y; } 
     double dot (Vec v) { return x * v.x + y * v.y; } 
     Vec sub (double x, double y) { return new Vec(this.x - x, this.y - y); } 
    } 

    static double fade (double v) { 
     // easing doesn't matter for range sample test. 
     // v = 3 * v * v - 2 * v * v * v; 
     return v; 
    } 

    static double lerp (double p, double a, double b) { 
     return (b - a) * p + a; 
    } 

    static Vec gradient (int c, int r) { 
     return gradients[c][r]; 
    } 

    // your function, with y0 fixed. note my gridSize is not a double like yours.  
    public static double getPoint(int x, int y) { 

     Vec p = new Vec(x/(double)gridSize, y/(double)gridSize); 
     Vec d = new Vec(Math.floor(p.x), Math.floor(p.y)); 

     int x0 = (int)d.x, 
      y0 = (int)d.y; 

     double d00 = gradient(x0 , y0 ).dot(p.sub(x0 , y0 )), 
       d01 = gradient(x0 , y0 + 1).dot(p.sub(x0 , y0 + 1)), 
       d10 = gradient(x0 + 1, y0 ).dot(p.sub(x0 + 1, y0 )), 
       d11 = gradient(x0 + 1, y0 + 1).dot(p.sub(x0 + 1, y0 + 1)); 

     double fadeX = fade(p.x - d.x), 
       fadeY = fade(p.y - d.y); 

     double i1 = lerp(fadeX, d00, d10), 
       i2 = lerp(fadeX, d01, d11); 

     return lerp(fadeY, i1, i2); 

    } 

    public static void main (String[] args) { 

     // loop forever, regenerating gradients and resampling for range. 
     while (true) { 

      initializeGradient(); 

      double minz = 0, maxz = 0; 

      for (int x = 0; x < gridSize * gridCells; ++ x) { 
       for (int y = 0; y < gridSize * gridCells; ++ y) { 
        double z = getPoint(x, y); 
        if (z < minz) 
         minz = z; 
        else if (z > maxz) 
         maxz = z; 
       } 
      } 

      System.out.println(minz + " " + maxz); 

     } 

    } 

} 

sto vedendo i valori all'interno della gamma teorica di [-0.707, 0.707], anche se generalmente vedo valori compresi tra -0,6 e 0,6; che potrebbe essere solo una conseguenza della distribuzione del valore e un basso tasso di campionamento.

Answer 2

Quando si calcola il prodotto punto, è possibile ottenere valori al di fuori dell'intervallo -1 +1, tuttavia durante la fase di interpolazione, il valore finale scende nell'intervallo -1 +1. Questo perché i vettori di distanza di prodotti a punti che sono interpolati puntano in direzioni opposte rispetto all'asse interpolato. Durante l'ultima interpolazione, l'output non supera l'intervallo di -1 +1.

L'intervallo di uscita finale per il disturbo Perlin è definito dalla lunghezza dei vettori di gradiente. Se parliamo di rumore 2D e il nostro obiettivo di avere un intervallo di output -1 +1, la lunghezza dei vettori di gradiente deve essere sqrt (2) (~ 1,4142). È un errore comune mescolare questi vettori (1, 1) (-1, 1) (1, -1) (-1, -1) e (1, 0) (0, 1) (-1, 0) (0, -1). In questo caso l'intervallo di output finale sarà ancora -1 intervallo di +1, tuttavia i valori nell'intervallo -0.707 +0.707 saranno più frequenti. Per evitare questo problema (1, 0) (0, 1) (-1, 0) (0, -1) i vettori devono essere sostituiti con (sqrt (2), 0) (0, sqrt (2)) (-sqrt (2), 0) (0, -sqrt (2)).