Simplex Noise

In 2001 Ken Perlin introduced a new type of gradient noise called Simplex Noise.  The document can be found here.  It is essentially his original gradient noise mapped onto a simplex grid.  The term “Simplex” means the simplest possible primitive which can occupy space.  In 2D it is a triangle and in 3D it is a tetrahedron ( 4-sided pyramid ).  A simplex grid is a grid structure made of these primitives.

There are four distinct improvements his new noise had over his classic.

  • A simplex primitive has far fewer verticies than its square/cube equivalent in 2D, 3D and higher dimensions which reduces algorithm complexity.
  • It allows for an easily computable analytic derivative
  • The simplex structure reduces axis-aligned artifacts
  • It lends itself to an efficient hardware implementation

Stefan Gustavson has made some great contributions to Simplex Noise over the years.  Most notably these are…

  • Writing a much clearer description of Simplex Noise in his “Simplex Noise Demystified” document.
  • Along with Ian McEwan providing GLSL implementations of Simplex Noise at WebGLNoise.
  • Providing an implementation of Simplex Noise with analytical derivatives here.

I have been experimenting with implementing this and other noise types over simplex grids.  As a result I have uploaded 3 new noise types to the GitHub repository.

The first is Simplex Perlin Noise in 2D and 3D.  I have made two improvements over what has been supplied by Perlin and Gustavson.  The first is a fix to a bug in the 3D surflet math which would cause discontinuities along the simplex faces, as can be seen here.  The second is providing accurate scaling values to correctly scale the noise to a strict -1.0->1.0 range.

2D+3D sampling of Simplex Perlin Noise  ( simplex gradient noise )

2D+3D sampling of Simplex Perlin Noise ( simplex gradient noise )

The second is Simplex PolkaDot Noise in 2D and 3D.  The simplex grid packs the dots more tightly than the square/cube version which gives the noise a slightly different look.

2D+3D sampling of Simplex PolkaDot Noise

2D+3D sampling of Simplex PolkaDot Noise

The final is Simplex Cellular Noise in 2D and 3D.  I’ve used some optimization ideas as described in a previous post on Cellular Noise so it runs very efficiently.  And given the reduced complexity in higher dimensions it could run a lot faster than its cube grid alternative.  The problem is a simplex grid packs the points much more tightly in space than a cube grid which reduces area for the verticies to move.  This reduces variance leading to a repetitive looking noise.  Nonetheless it is still visually pleasing and well defined so I have included it into the code repository.

One final note is that I experimented with taking additional points into account ( other than the immediate corner verticies of the simplex ) to allow for more variance.  The results were positive ( as can be seen here ) but costly and would only be of benefit in higher dimensions ( eg 3 or 4 ).

2D+3D sampling of Simplex Cellular Noise

2D+3D sampling of Simplex Cellular Noise

Advertisements

About briansharpe

Computer games and graphics programmer interested in procedural modeling and texturing techniques. Current Work: Weta Digital. Work history: Sidhe Interactive, Sony London (SCEE), Pandromeda,
This entry was posted in Uncategorized. Bookmark the permalink.

19 Responses to Simplex Noise

  1. Hi Brian,
    Thanks for this nice series of noise articles. I have one question: while playing with simplex noise (and looking to implement a correct 6d noise), I’m wondering how did you calculate analytically the normalization factor? (for example FINAL_NORMALIZATION in SimplexPerlin2D)

  2. briansharpe says:

    Hi Alex

    The way to work out the normalization factor is to think of what the maximum possible value would be generated if given the right conditions. So this would be by taking some sample within the simplex triangle, while having all gradient vectors pointing at that sample. To generate the maximum value it turns out that this sample is halfway along any one of the triangle edges. ( so this means the equal combination of two surflets )

    In 2D, half the edge length of a simplex triangle is…
    x = ( sqrt( 0.5 )/sqrt( 0.75 ) ) * 0.5
    So our 2D normalization factor becomes…
    2DNF = 1.0 / ( x * ( ( 0.5 – x*x ) ^ 4 ) * 2.0 ) = ~99.2043345….

    In 3D, half the edge length of a simplex tetrahedron is…
    x = sqrt( 0.75 ) * 0.5
    So our 3D normalization factor becomes…
    3DNF = 1.0 / ( x * ( ( 0.5 – x*x ) ^ 3 ) * 2.0 ) = ~37.8372272…..

    Something to note: 2D simplex triangles ( as generated by perlins skew/unskew method ) are equilateral. But the 3D simplex tetrahedrons are NOT. They’re slightly skewed…. So the 3D math I’m using here starts to deviate ever so slightly from the actual results. But because it is so minor and to keep math simplicity+sanity, I’ve chosen to ignore this issue.

    So… Wow. 6D noise? Cool! 🙂 Would you mind if I ask why you’d want such a thing?

    One thing to keep in mind. As you go up the dimensions simplex noise starts to break down. The surflets overlap less and less. We start to see this in the reduced visual quality of 4D simplex noise. Not sure what you’ll get when you hit 6D

    Either way, good luck with it all. 🙂
    Brian

    • ruxbin09 says:

      Hi,Brian
      Thanks for your explaination of the normalization factor. What puzzle me most is “To generate the maximum value it turns out that this sample is halfway along any one of the triangle edges”. I tried to derive the 2D occasion myself. I used (x,y) to denote a point inside a triangle and got a really complicate eqation of the noise function. Then I calculated the partical derivatives of x and y. They shoud be 0 when it reaches the maxium value. But after I put 0 at one side of the equation, I gived up to solve them. They are really complicated compared with the simple yet beautiful mid-point answer. Can you tell me the way you find the mid-point as the maxium points? Or are there any resources I can refer to?
      Thanks 🙂

      • briansharpe says:

        Hi ruxbin.
        I must admit I solved that part numerically. I wrote a solver which subdivided space recursively to find the highest value of noise in a single triangle. ( ie, all normalized gradient vectors pointing at the sample position ). In both 2D and 3D it continuously found the highest value to be the midpoint along an edge. It searched to the edge of floating point precision so I’m confident of the result.

      • ruxbin09 says:

        Thanks for the answer. Floating point precision should be good enough to verify the answer and that has solved my puzzle:).

  3. Thanks Brian for your answer! I was close to those formulas, but got probably something wrong around by taking a grad_results of (1,1) instead of (x,x). I noticed also the same bias in Gustavson original paper, that the skewed version was going above 1.0 and needed a sqrt(0.5) factor.

    One thing that is also not clear to me is the choice of the “Spherical Kernel”: (0.5 – x*x)^4 or (0.6 – x*x)^5, literature about “Spherical Kernel” doesn’t look like these formulas. Where does it come from? When you say that in higher dimension, the surflet overlap less, is it not coming from this kernel, that could then be adjusted?

    6D noise is mostly to get a seamless tiling 3D noise (like this one described here http://www.gamedev.net/blog/33/entry-2138456-seamless-noise/), with a frequency that is not necessarily multiple of the permutation table. It is working great for 2D simplex noise. A 8D would be great to have cycling in time 3D noise, but not sure I will get so far! 😀

    • briansharpe says:

      Hi Alex
      The “Spherical Kernel” is simply a falloff function defined in X-squared. It it efficient because it does not need a sqrt() call. The one in simplex noise is a slight modification to what I have mentioned here. [ https://briansharpe.wordpress.com/2011/11/14/two-useful-interpolation-functions-for-noise-development/ ]
      The modification is the 0.5-… part, which reduces the radius of the kernel from 1.0 to sqrt(0.5)
      sqrt(0.5) is the distance from the corner of a 2D triangle to the opposite side, and represents the highest possible radius of a kernel/surflet before it touches a neighboring triangle. This is the problem with higher dimensions. This distance becomes less and less reducing the area for all kernels (or surflets ) to overlap.

  4. Ryan Boghean says:

    Hi, I’ve been working on understand simplex noise and found my way here. I’ve never heard or used GitHub and searching on the website with your name (Brian Sharpe) or noise produced no usable results. Is there any way I can view this code/changes you’ve made? Also, prior to reading about simplex noise I’d never heard of a simplex grid. I’ve searched all over google, wikipedia, ect.. and came up with nothing useful. Any links to reading material on it that you might know of? Thanks for the write-up and for your time.

    • briansharpe says:

      Hi Ryan
      You can get to the GitHub repository via the “code” button at the top of the page, or you can go directly there via this “https://github.com/BrianSharpe/GPU-Noise-Lib/blob/master/gpu_noise_lib.glsl”. Be warned there is quite a bit of code there. These are the 4 functions relating to simplex noise
      SimplexPerlin2D, SimplexPerlin3D, SimplexPerlin2D_Deriv, SimplexPerlin3D_Deriv

      I agree there is not much out there on “simplex grids”. I have gained most of my understanding from Stefan Gustavson’s “Simplex Noise Demystified”, and taken things from there. Sorry I can’t be of more help in that regard. One more thought, here is a forum post which shows the skew/unskew formulation. http://www.opengl.org/discussion_boards/showthread.php/163082-4D-simplex-noise?p=1152055&viewfull=1#post1152055

      • Ryan Boghean says:

        Thank-you. Over the weekend I went over all the math and in the end and was able to come up with nearly everything that you did (not saying I don’t trust your work, rather I find it easier to understand an algorithm if I understand the why and not just the what) except for a few little issues. I can’t wrap my head around the surflet equation. Consider the 2D case, if I wanted to write a linear equation for the surflet, I’d have started with:
        t = (sqrt(0.5) – sqrt(u^2 + v^2)) / sqrt(0.5)
        before adding curvature with whatever power we want to use. Is the equation:
        t = max(0.5 – (u^2 + v^2),0)
        merely an approximation, to avoid sqrt? And why not something like 6t^5 – 15t^4 + 10t^3 to smooth the surflet instead of just t^3 or t^4? Wouldn’t that give better looking noise?

      • briansharpe says:

        The falloff function is designed to work on x-squared. So it can perform a falloff without calculating a sqrt. ( as you say )
        Its a modification of the x-squared falloff functions mentioned here.
        https://briansharpe.wordpress.com/2011/11/14/two-useful-interpolation-functions-for-noise-development/
        The modification is (0.5-x*x) rather than (1.0-x*x). The 0.5 is a crude way to control the radius. (ie radius == sqrt(0.5) ). Play with it in a graphing calculator. you’ll see.

      • Ryan Boghean says:

        I see, and thanks that all makes sense now : )

      • J-Gamer says:

        Related question: why is the falloff(t) squared again in the calculation of n?
        ie: n = t * t * dot(gradient, direction)

      • briansharpe says:

        The dotproduct of a vector with itself gives its squared length. This is where the squared comes from.

        But where I think you’re getting confused is that there are two dot products that happen with the calculation of each “surflet”
        1) dot product of the point with the gradient to get a linear slope in the direction of the gradient. ( this result is linear )
        2) dot product of the point with itself to calculate a radial falloff. ( This result is squared requiring the xsq-falloff function )

        The results of 1 and 2 are then multiplied to get the surflet value. For 2D noise, we then sum all 4 surflet values to get the final noise result.

      • J-Gamer says:

        That fall-off function is (0.5 – distance^2)^2, isn’t it?
        If so, then it is actually squared one more time. ie:
        t = (0.5 – x*x – y*y)
        if(t > 0) {
        t *= t; //squared here, as the equation says it should
        n = t * t * dot(gradient, direction); //squared again? ==> t = (0.5 – distance^2)^4 ???
        }

      • briansharpe says:

        Yes. I’m sorry. You are right. It does get squared again. This is simply to give it a more pleasing shape. You can choose whatever you want. ^2 ^3 ^4 ^5 etc…

        In a way, Perlin makes note of this in his original simplex noise notes. “…the exact radius and amplitude of the hypersphere-shaped kernel centered at each simplex vertex need to be tuned so as to produce the best visual results…”

      • J-Gamer says:

        Ok, so it doesn’t really matter 😀

  5. plasmacel says:

    Hey Brian,
    I’m reading your comments about the normalization factor, but it is still not clear to me.
    First, isn’t the sample location of the possible maximum value at the center of the simplex (instead of the halfway along an edge)?
    Second, how did you derive the normalization formula
    DNF = 1.0 / ( x * ( ( 0.5 – x*x ) ^ 4 ) * 2.0 ). The ( ( 0.5 – x*x ) ^ 4) part comes from the attenuation kernel you apply, but what is that additional x*2.0 part? Thanks in advance!

    • briansharpe says:

      Hi there

      It is halfway across the edge. so in the middle means you’re influenced by three points but you’re further away from those three points. half way along an edge is influenced by two points but you’re closer to those two points. And it turns out being closer to two points along the edge gives a bigger value than in the middle.

      For the second part… that 2.0 is due to that you have two points influencing the value. (because its along an edge)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s