Szum Perlina

Witam wszystkich.

Nad zagadnieniem szumu Perlina spędziłem ponad tydzień i przeglądnąłem większość artykułów jakie można na jego temat znaleźć w sieci. Wciąż jednak nie rozumiem wielu rzeczy, dlatego zwracam się do Was z prośbą - czy znajdzie się ktoś obeznany z szumem Perlina, kto wytłumaczy mi łopatologicznie, krok po kroku, jak on działa?

Przede wszystkim nie bardzo rozumiem ideę tablicy gradientów. Po co nam ona, skoro i tak inicjalizowana jest (tak mi się przynajmniej zdaje) losowymi wartościami?

gamedev.net ->Artykul Simple Clouds

tam jest kod na wykorzystanie perlin noise i wszystko dziala jak powinno

Na pierwszy rzut oka wygląda mi to nie na Perlin noise, ale na wygładzony value noise. Jutro to przestudiuję i dam znać, czy było w czymkolwiek pomocne. Tak czy inaczej dzięki.

Edit:

Tak, kod jest analogiczny do rozwiązań z tej strony - http://freespace.virgin.net/hugo.elias/models/m_perlin.htm . Niestety, z tego co wyczytałem na necie, nie jest to prawdziwy szum Perlina. Jeżeli to komuś pomoże, to tutaj mam dobry kod znaleziony na pewnej francuskiej stronie (napisany w C#):

    #region Using Statements

    using System;
using System.Drawing;

    #endregion

    /// <summary>
    /// This is a class able to generate pseudo coherent random noise based on Ken Perlin's algorithm
    /// <see cref="http://mrl.nyu.edu/~perlin/noise/"/>
    /// <seealso cref="http://www.siafoo.net/snippet/144"/>
    /// </summary>
    public sealed class PerlinNoise
    {
        #region Constants

        /// <summary>
        /// Stores the size of the random value array
        /// </summary>
        private int RANDOM_SIZE = 256;

        #endregion

        #region Fields

        /// <summary>
        /// Stores the random values used to generate the noise
        /// </summary>
        private readonly int[] values;

        #endregion

        /// <summary>
        /// Initializes a new instance of the PerlinNoise class.
        /// </summary>
        /// <param name="seed">The seed used to generate the random values</param>
        public PerlinNoise(int seed)
        {
            // Initialize the random values array
            this.values = new int[RANDOM_SIZE*2];

            // Initialize the random generator
            Random generator = new Random(seed);

            // Initialize an array for storing 256 random values
            byte[] source = new byte[RANDOM_SIZE];

            // Generate 256 random byte values
            generator.NextBytes(source);

            // Copy the source data twice to the generator array
            for (int i = 0; i < RANDOM_SIZE; i++)
                this.values[i+RANDOM_SIZE] = this.values[i] = source[i];
        }



        /// <summary>
        /// Generates a one-dimensional noise
        /// </summary>
        /// <param name="x">The entry value for the noise</param>
        /// <returns>A value between [-1;1] representing the noise amount</returns>
        public float Noise(float x)
        {
            // Compute the cell coordinates
            int X = (int)Math.Floor(x) & 255;

            // Retrieve the decimal part of the cell
            x -= (float)Math.Floor(x);

            float u = Fade(x);

            return Lerp(u, Grad(this.values[X], x), Grad(this.values[X+1], x - 1));
        }

        /// <summary>
        /// Generates a bi-dimensional noise
        /// </summary>
        /// <param name="x">The X entry value for the noise</param>
        /// <param name="y">The Y entry value for the noise</param>
        /// <returns>A value between [-1;1] representing the noise amount</returns>
        public float Noise(float x, float y)
        {
            // Compute the cell coordinates
            int X = (int)Math.Floor(x) & 255;
            int Y = (int)Math.Floor(y) & 255;

            // Retrieve the decimal part of the cell
            x -= (float)Math.Floor(x);
            y -= (float)Math.Floor(y);

            // Smooth the curve
            float u = Fade(x);
            float v = Fade(y);

            // Fetch some randoms values from the table
            int A = this.values[X] + Y;
            int B = this.values[X + 1] + Y;

            // Interpolate between directions 
            return Lerp(v, Lerp(u, Grad(this.values[A], x, y),
                                   Grad(this.values[B], x - 1, y)),
                           Lerp(u, Grad(this.values[A + 1], x, y - 1),
                                   Grad(this.values[B + 1], x - 1, y - 1)));
        }

        /// <summary>
        /// Generates a tri-dimensional noise
        /// </summary>
        /// <param name="x">The X entry value for the noise</param>
        /// <param name="y">The Y entry value for the noise</param>
        /// <param name="z">The Z entry value for the noise</param>
        /// <returns>A value between [-1;1] representing the noise amount</returns>
        public float Noise(float x, float y, float z)
        {
            // Compute the cell coordinates
            int X = (int)Math.Floor(x) & 255;
            int Y = (int)Math.Floor(y) & 255;
            int Z = (int)Math.Floor(z) & 255;

            // Retrieve the decimal part of the cell
            x -= (float)Math.Floor(x);
            y -= (float)Math.Floor(y);
            z -= (float)Math.Floor(z);

            // Smooth the curve
            float u = Fade(x);
            float v = Fade(y);
            float w = Fade(z);

            // Fetch some randoms values from the table
            int A = this.values[X] + Y;
            int AA = this.values[A] + Z;
            int AB = this.values[A + 1] + Z;
            int B = this.values[X + 1] + Y;
            int BA = this.values[B] + Z;
            int BB = this.values[B + 1] + Z;

            // Interpolate between directions
            return Lerp(w, Lerp(v, Lerp(u, Grad(this.values[AA], x, y, z),
                                           Grad(this.values[BA], x - 1, y, z)),
                                   Lerp(u, Grad(this.values[AB], x, y - 1, z),
                                           Grad(this.values[BB], x - 1, y - 1, z))),
                           Lerp(v, Lerp(u, Grad(this.values[AA + 1], x, y, z - 1),
                                           Grad(this.values[BA + 1], x - 1, y, z - 1)),
                                   Lerp(u, Grad(this.values[AB + 1], x, y - 1, z - 1),
                                           Grad(this.values[BB + 1], x - 1, y - 1, z - 1))));
        }

#if XNA
        #region XNA specific methods
        
        /// <summary>
        /// Generates a bi-dimensional noise
        /// </summary>
        /// <param name="value">The vector coordinates of the entry value for the noise</param>
        /// <returns>A value between [-1;1] representing the noise amount</returns>
        public float Noise(Vector2 value)
        {
            return Noise(value.X, value.Y);
        }

        /// <summary>
        /// Generates a tri-dimensional noise
        /// </summary>
        /// <param name="value">The vector coordinates of the entry value for the noise</param>
        /// <returns>A value between [-1;1] representing the noise amount</returns>
        public float Noise(Vector3 value)
        {
            return Noise(value.X, value.Y, value.Z);
        }

        #endregion
#endif

        #region Private helpers methods

        /// <summary>
        /// Smooth the entry value
        /// </summary>
        /// <param name="t">The entry value</param>
        /// <returns>The smoothed value</returns>
        private static float Fade(float t)
        {
            return t * t * t * (t * (t * 6 - 15) + 10);
        }

        /// <summary>
        /// Interpolate linearly between A and B.
        /// </summary>
        /// <param name="t">The amount of the interpolation</param>
        /// <param name="a">The starting value</param>
        /// <param name="b">The ending value</param>
        /// <returns>The interpolated value between A and B</returns>
        private static float Lerp(float t, float a, float b)
        {
            return a + t * (b - a);
        }

        /// <summary>
        /// Modifies the result by adding a directional bias
        /// </summary>
        /// <param name="hash">The random value telling in which direction the bias will occur</param>
        /// <param name="x">The amount of the bias on the X axis</param>
        /// <returns>The directional bias strength</returns>
        private static float Grad(int hash, float x)
        {
            // Result table
            // ---+------+----
            //  0 | 0000 |  x 
            //  1 | 0001 | -x 

            return (hash & 1) == 0 ? x : -x;
        }

        /// <summary>
        /// Modifies the result by adding a directional bias
        /// </summary>
        /// <param name="hash">The random value telling in which direction the bias will occur</param>
        /// <param name="x">The amount of the bias on the X axis</param>
        /// <param name="y">The amount of the bias on the Y axis</param>
        /// <returns>The directional bias strength</returns>
        private static float Grad(int hash, float x, float y)
        {
            // Fetch the last 3 bits
            int h = hash & 3;

            // Result table for U
            // ---+------+---+------
            //  0 | 0000 | x |  x
            //  1 | 0001 | x |  x
            //  2 | 0010 | x | -x
            //  3 | 0011 | x | -x

            float u = (h & 2) == 0 ? x : -x;

            // Result table for V
            // ---+------+---+------
            //  0 | 0000 | y |  y
            //  1 | 0001 | y | -y
            //  2 | 0010 | y |  y
            //  3 | 0011 | y | -y

            float v = (h & 1) == 0 ? y : -y;

            // Result table for U + V
            // ---+------+----+----+--
            //  0 | 0000 |  x |  y |  x + y
            //  1 | 0001 |  x | -y |  x - y
            //  2 | 0010 | -x |  y | -x + y
            //  3 | 0011 | -x | -y | -x - y

            return u + v;
        }

        /// <summary>
        /// Modifies the result by adding a directional bias
        /// </summary>
        /// <param name="hash">The random value telling in which direction the bias will occur</param>
        /// <param name="x">The amount of the bias on the X axis</param>
        /// <param name="y">The amount of the bias on the Y axis</param>
        /// <param name="z">The amount of the bias on the Z axis</param>
        /// <returns>The directional bias strength</returns>
        private static float Grad(int hash, float x, float y, float z)
        {
            // Fetch the last 4 bits
            int h = hash & 15;

            // Result table for U
            // ---+------+---+------
            //  0 | 0000 | x |  x
            //  1 | 0001 | x | -x
            //  2 | 0010 | x |  x
            //  3 | 0011 | x | -x
            //  4 | 0100 | x |  x
            //  5 | 0101 | x | -x
            //  6 | 0110 | x |  x
            //  7 | 0111 | x | -x
            //  8 | 1000 | y |  y
            //  9 | 1001 | y | -y
            // 10 | 1010 | y |  y
            // 11 | 1011 | y | -y
            // 12 | 1100 | y |  y
            // 13 | 1101 | y | -y
            // 14 | 1110 | y |  y
            // 15 | 1111 | y | -y

            float u = h < 8 ? x : y;

            // Result table for V
            // ---+------+---+------
            //  0 | 0000 | y |  y
            //  1 | 0001 | y |  y
            //  2 | 0010 | y | -y
            //  3 | 0011 | y | -y
            //  4 | 0100 | z |  z
            //  5 | 0101 | z |  z
            //  6 | 0110 | z | -z
            //  7 | 0111 | z | -z
            //  8 | 1000 | z |  z
            //  9 | 1001 | z |  z
            // 10 | 1010 | z | -z
            // 11 | 1011 | z | -z
            // 12 | 1100 | x |  x
            // 13 | 1101 | z |  z
            // 14 | 1110 | x | -x
            // 15 | 1111 | z | -z

            float v = h < 4 ? y : h == 12 || h == 14 ? x : z;

            // Result table for U+V
            // ---+------+----+----+-------
            //  0 | 0000 |  x |  y |  x + y
            //  1 | 0001 | -x |  y | -x + y
            //  2 | 0010 |  x | -y |  x - y
            //  3 | 0011 | -x | -y | -x - y
            //  4 | 0100 |  x |  z |  x + z
            //  5 | 0101 | -x |  z | -x + z
            //  6 | 0110 |  x | -z |  x - z
            //  7 | 0111 | -x | -z | -x - z
            //  8 | 1000 |  y |  z |  y + z
            //  9 | 1001 | -y |  z | -y + z
            // 10 | 1010 |  y | -z |  y - z
            // 11 | 1011 | -y | -z | -y - z

            // The four last results already exists in the table before
            // They are doubled because you must get a result for all
            // 4-bit combinaisons values.

            // 12 | 1100 |  y |  x |  y + x
            // 13 | 1101 | -y |  z | -y + z
            // 14 | 1110 |  y | -x |  y - x
            // 15 | 1111 | -y | -z | -y - z

            return ((h & 1) == 0 ? u : -u) + ((h & 2) == 0 ? v : -v);
        }

        #endregion
    }


 

Nie chodzi mi jednak, tak jak wspomniałem wcześniej, o sam kod a o wytłumaczenie co, jak i dlaczego.

wiesz co zmienili strone ale

http://www.gamedev.net/page/resources/_/reference/programming/sweet-snippets/simple-clouds-part-1-r2085

o to mi chodzilo jakznalazles cos innego maja tam napisane perlin noise wiecchyba to to

Chodzi o to, że implementacja którą mi podałeś polega na tym, że gość generuje sobie najpierw niespójny szum, po czym wygładza go. Też na początku zaimplementowałem go w ten sposób, ale doczytałem później, że algorytm Perlina generuje spójny szum bez potrzeby wygładzania. I tu właśnie zaczynają się dla mnie problemy. Wiem o co chodzi z oktawami, persistence, dodawaniem na koniec wszystkich szumów. Nie bardzo kojarzę jednak tablicę gradientów, która to właśnie powoduje podobno spójność szumu.

Z racji, że mam zrobić projekt z OpenGLa oraz tego, że proceduralne tworzenie grafiki mnie od dawna interesowało poczytałem co nieco o szumie Perlina.

Na razie niewiele z tego rozumiem, ale gradient dla każdego punktu na siatce jest stały, wcześniej wylosowany. Każdy kierunek musi mieć identyczne prawdopodobieństwo wystąpienia. Szum Perlina różni się tym od Value Noise, że zamiast interpolować wartości interpoluje długości gradientów (o ile dobrze rozumiem) i używa funkcji wygładzającej fade (funkcja ta przyciąga trochę punkt w kierunku siatki, tym bardziej im bliżej jest punktu z siatki).

W sumie to nie wiem jeszcze czemu taka metoda miałaby być lepsza, ale piszą coś o pochodnych drugiego rzędu, które w Value Noise są bardzo skomplikowane (?). Może niedługo zrobię shadera w RenderMonkey i się sam przekonam jak różni się Value Noise od szumu Perlina wizualnie :)

EDIT:
Mam jeszcze jeden wykład z OpenGL'a więc może zapytam o ten szum Perlina. Jak na razie zaimplementowałem szum Perlina w RenderMonkey'u, ale inicjalizacja tablicy haszującej jest tragicznie wolna (w sumie to inicjalizuję ją we Fragment Shaderze, a więc dla każdego piksela od nowa, ale przecież i tak tablica ma może dwa kilobajty).