Changeset 3732


Ignore:
Timestamp:
Dec 28, 2014, 12:47:40 AM (7 years ago)
Author:
sam
Message:

math: optimise Perlin noise by parsing the hypercube using a Gray code pattern.

File:
1 edited

Legend:

Unmodified
Added
Removed
  • trunk/src/lol/math/noise/perlin.h

    r3731 r3732  
    3535    inline float eval(vec_t<float, N> position) const
    3636    {
    37         int const cells = 1 << N;
    38 
    39         /* Retrieve the containing hypercube origin */
     37        /* Compute the containing hypercube origin */
    4038        vec_t<int, N> origin;
    4139        for (int i = 0; i < N; ++i)
     
    4442        vec_t<float, N> delta = position - (vec_t<float, N>)origin;
    4543
     44        /* Apply a smooth step to delta and store it in “t”. */
    4645        vec_t<float, N> t = delta;
     46        t = ((6.f * t - vec_t<float, N>(15.f))
     47                  * t + vec_t<float, N>(10.f)) * (t * t * t);
    4748        /* DEBUG: original Perlin noise polynomial */
    4849        //t = (vec_t<float, N>(3.f) - 2.f * t) * t * t;
    49         /* Improved polynomial (with null second derivative) */
    50         t = ((6.f * t - vec_t<float, N>(15.f))
    51                   * t + vec_t<float, N>(10.f)) * (t * t * t);
    5250
    53         /* Compute all gradient contributions */
    54         array<float> values;
    55         values.Resize(cells);
    56         for (int i = 0; i < cells; ++i)
     51        /* Premultiply and predivide (1-t)/t and t/(1-t) into “u” and “v”. */
     52        vec_t<float, N> u, v;
     53        float multiplier = 1.f;
     54        for (int bit = 0; bit < N; ++bit)
    5755        {
    58             /* FIXME: find another way to travel the hypercube that
    59              * causes fewer bit flips, and compute the return value
    60              * directly without allocating an array value. */
    61             vec_t<float, N> v = delta;
    62             vec_t<int, N> corner = origin;
    63             for (int bit = 0; bit < N; ++bit)
    64                 if ((1 << bit) & i)
    65                 {
    66                     ++corner[bit];
    67                     v[bit] = v[bit] - 1.f;
    68                 }
     56            /* Avoid divisions by zero near the hypercube boundaries. */
     57            float f = clamp(t[bit], 0.001f, 0.999f);
    6958
    70             values[i] = dot(v, this->get_gradient(corner));
     59            multiplier *= (1.f - f);
     60            u[bit] = (1.f - f) / f;
     61            v[bit] = f / (1.f - f);
    7162        }
    7263
    73         /* Interpolate all contributions together */
    74         for (int bit = N; bit--; )
     64        float ret = 0.f;
     65
     66        /* Compute all gradient contributions, for each of the 2^N corners
     67         * of the hypercube. */
     68        for (int i = 0; i < (1 << N); ++i)
    7569        {
    76             for (int i = 0; i < (1 << bit); ++i)
    77                 values[i] = (1.f - t[bit]) * values[i]
    78                                   + t[bit] * values[i + (1 << bit)];
     70            /* Accumulate Perlin noise */
     71            ret += multiplier * dot(delta, this->get_gradient(origin));
     72
     73            /* Don’t use the binary pattern for “i” but use its Gray code
     74             * “j” instead, so we know we only have one component to alter
     75             * in “origin” and in “delta”. We know which bit was flipped by
     76             * looking at “k”, the Gray code for the next value of “i”. */
     77            int j = i ^ (i >> 1);
     78            int k = (i + 1) ^ ((i + 1) >> 1);
     79
     80            int bit = 0;
     81            while ((j ^ k) > (1 << bit))
     82                ++bit;
     83
     84            origin[bit] += j > k ? -1 : 1;
     85            delta[bit] += j > k ? 1.f : -1.f;
     86            multiplier *= (j > k ? u : v)[bit];
    7987        }
    8088
    81         return values[0];
     89        return sqrt(2.f) * ret;
    8290    }
    8391};
Note: See TracChangeset for help on using the changeset viewer.