Understanding Perlin Noise (2014) | Hacker News Reader

Understanding Perlin Noise (2014)

flafla2.github.io

94 pointsacdanger18 comments

When I first learned about noise (many years later than I should have), I remember finding out that Perlin noise was patented, so I looked into OpenSimplex[1] instead which is Java but has been ported to other languages. It turns out Love2d has love.math.noise built in which does the same thing. Would be great if PICO-8 had it too, although I think this one[2] is free too. But one of the coolest things was realizing that Minecraft landscapes are mostly just multiple applications of noise functions on top of each other, which means it only needs to store changes to the environment, and that it can completely regenerate the same environment using noise functions. Sometimes I envy game developers, until I remember how their working conditions are usually very horrible.

[1] https://gist.github.com/KdotJPG/b1270127455a94ac5d19

[2] http://staffwww.itn.liu.se/~stegu/simplexnoise/Noise.lua

I actually missed the built-in noise function and instead used the same library you linked to. I tried switching to built-in C++ implementation just now and it was actually slower.

The Lua library for simplex does some FFI trickery and avoids crossing Lua/C++ barrier. Mike Pall is credited in comments, so I guess I'm not surprised it's faster.

As far as I know, Perlin noise has never been patented. According to Wikipedia, however (emphasis mine):

> in 2001 he was granted a patent for the use of 3D+ implementations of simplex noise for texture synthesis.

OpenSimplex is a variant of simplex noise developed specifically to work around that patent.

i think that minecraft stores the generated data along with modifications nowadays, instead of the neat little format you describe, because generating this frequently is usually very difficult for the computer. im not completely sure though.

You're correct, Minecraft generates chunks around as players get near them, then they get stored on disk. To reset a chunk you can just delete it IIRC, it gets regenerated to the initial state as soon as a player comes near it.

There would be not much practical use for it I think, but in theory it should be possible to "compress" a Minecraft world by figuring out the delta between the original generated state and the current state, and then for each chunk either saving the delta or the the full chunk, whatever is smaller.

It is still practical in some cases, like moving the world border at will.

Daniel Shiffman also has very approachable explanation of Perlin noise on his Youtube channel Coding Train: https://www.youtube.com/watch?v=Qf4dIN99e2w

The article and this video don't describe the same algorithm. As stated at the end of article, "this is not true perlin noise! Hugo's algorithm is not based on gradients like Perlin Noise is. Instead it is what's known as value noise, which is essentially blurred white noise."

Thank you. He was quite entertaining and clear.

I have implemented Perlin Noise myself and wrote some procedural generation projects. Some experience to share:

- 2D Perlin Noise gives rather significant artifacts. If you look at the examples provided in the article you’ll notice that many of the edges in the examples are along the x and y direction. I use (open) simplex noise to avoid those. (When you are doing terrain generation those artifacts become easily noticeable)

- Gradient noises can be used to control more than just the intensity of something! I have used them to control the orientation of mountain ranges for example. Basically, you can use them to control anything that needs to be smooth and continuous over space.

Perlin noise is great for making pretty patterns, and as shown by this page, surprisingly easy to understand.

The first thing I did when I got an rPi with a sensehat (which includes an 8x8 rgb display) was to make a plasma type display by generating 3 perlin noise maps and crossfading to a new set slowly every second or so.

I still have it running on my desk to this day and get constant comments. People seem to find it endlessly fascinating

Do you have the source handy?

Sure, I've pasted it up here https://pastebin.com/rsVY3JWB

Long time ago I played around with gimp+mathmap[1]. For some reason I needed the second derivative of a Perlin noise layer and I kind of surprised when the underlying grid structure revealed itself. I didn't know anything about the Perlin noise algorithm at the time. AFAIK there are variations of the algorithm that are continuous in the Nth derivative (for various values of N). Maybe the article's implementation is continuous in the 2nd derivative.

[1] https://www.complang.tuwien.ac.at/schani/mathmap/

I couldn't find an explanation in the article for what makes Perlin noise unique (especially given the comments by sephoric here on HN).

Can anyone explain?

Tried going to the background pages linked, but links are broken.

How do you mean "unique"? It's pretty unique in that there exist no other well-known gradient noise algorithms, besides simplex noise which is a) much more recent and b) also devised by Ken Perlin.

I'll take a shot (PLUG -- Here's /my/ explanation of Perlin noise: [1]).

1) It's approximately band-limited. In other words, it goes up and down in a somewhat random looking way that is neither too fast nor to slow. If you evaluate two points close by, they'll have approximately the same value. If you evaluate two points far away they'll have completely unrelated values. This is so because the way it is constructed, every "hill" is paired with a "valley" nearby and vice-versa. Those hills and valleys are of a fairly uniform size and in each pair are a consistent distance from each other. This helps to give it a fairly even appearance and means that we can use it as a building block for other patterns; we can do spectral synthesis (e.g.: [2]) and sum together multiple instances of Perlin noise at different scales and amplitudes to produce a particular look. (Though Gabor noise [3], is even better at this.)

2) It's deterministic. So long as your permutation tables and gradient tables are the same from run to run (either hard-coded into your program or generated from the same RNG seeding), the values that you get out of Perlin noise at a given point will stay the same across different runs of your program. This is nice for things like Minecraft where you can put in the same seed and be dropped into the same world. For movies, we can use it to make pattern on a surface, add detail to a volume, or make things move in interesting swirls [4] and know that they'll stay consistent from frame-to-frame rather than jumping to a completely different pattern.

3) It's random access. You can evaluate any point, anywhere, at any time without having to say, pre-compute a patch and filter it somehow. (Classic Perlin noise uses just a couple of tiny lookup tables initialized at the program start and even these can be traded for pure computation [5].) This makes it ammenable to parallelization.

4) It easily generalizes to arbitrary dimensions. Typical implementations provide functions for evaluating it on a 1D, 2D, 3D, and 4D domains. So if you need a 3D point that varies with time you can use the 4D version. Classic Perlin noise gets exponentially more expensive with higher dimensions, but the closely related Simplex noise [6] scales linearly. There are also vector-valued versions where the range is multidimensional; instead of just getting a scalar value out you can get a vector.

Hope that helps. Let me know if anything is unclear or you have further questions.

----

[1] http://www.eastfarthing.com/blog/2015-04-21-noise/

[2] http://paulbourke.net/fractals/noise/

[3] http://graphics.cs.kuleuven.be/publications/LLDD09PNSGC/

[4] https://www.cs.ubc.ca/~rbridson/docs/bridson-siggraph2007-cu...

[5] https://www.csee.umbc.edu/~olano/papers/GPUTEA.pdf

[6] https://www.csee.umbc.edu/~olano/s2002c36/ch02.pdf#page=18

that's super helpful; thank you! useful links, too.

Reply on news.ycombinator.com