Pages

Friday, January 2, 2015

Simplectic Noise

Notice: Since posting this, further work showed that the algorithm described here is not actually particularly useful. See the follow-up blog post for details. This post is preserved, with only slight modification, for posterity.

This post is about a new gradient noise function I've invented which should help to fill a hole that's existed in this space for some time now. I call it simplectic noise. But first, to put this in context, some history.

Perlin Noise


2D Perlin noise
Back in 1983, Ken Perlin published an algorithm known as Perlin noise. It was for creating smooth, continuous, random values over space, which has numerous applications in 3D graphics and elsewhere. Perlin noise, and it's variants, have become one of the primary tools for creating computer-generated random content (also called procedural content), particularly for natural terrain or textures.

Perlin noise works by dividing space up into squares, cubes, tesseracts, or whatever kind of hypercube is appropriate for the number of dimensions you're using. It figures out which cell you're in, and assigns a random gradient to each corner of that cell, then blends those gradients together. Because the given corner's gradient is chosen solely based on the coordinates of the corner, a neighboring cell sharing the same corner will choose the same gradient for it. This means that neighboring cells blend smoothly with each other.

Because of the way it works, Perlin noise and it's variants are collectively known as gradient noise.

Simplex Noise


2D simplex noise
Perlin noise is pretty useful, but it has some flaws. As you can see in the image above, it tends to have subtle directional artifacts. Because of this Ken Perlin in 2001 published an improved version of the algorithm, called simplex noise. The principle is similar, except instead of dividing space into hypercubes, it divides them into simplexes. A simplex is the simplest possible space-filling shape in a given dimension. This is a triangle in 2D, a tetrahedron in 3D, and increasingly hard-to-visualize shapes in higher dimensions. There are two key advantages to simplex noise over Perlin noise:

  • The simplexes aren't axis-aligned, so there aren't any obvious directional artifacts.
  • The number of points that must be considered only increases by 1 for each additional dimension, whereas Perlin noise doubles the number of points with each dimension, so simplex noise is much faster to calculate at higher dimensions.
This is an excellent noise function. By most measures, simplex noise is still the best gradient noise function available.

But there's a problem. Soon after Perlin published simplex noise, he also secured a patent for it. This makes it a non-starter for a lot of smaller, independent developers, who don't want to deal with the potential legal issues of using a patented algorithm.

OpenSimplex Noise


2D OpenSimplex noise
In September of 2014, only a little over 3 months before this blog post, a post was made on Tumblr describing an algorithm they called OpenSimplex noise. The primary intent is to achieve the advantages of simplex noise without hitting the patent restrictions.

This uses yet another kind of spatial tesselation, known as a simplectic honeycomb. In 2D, a simplectic honeycomb is identical to a the triangular tesselation used by 2D simplex noise, but that's okay because the simplex noise patent only covers 3 or more dimensions. In 3D, a simplectic honeycomb is actually a combination of tetrahedrons and octohedrons. This makes the process of figuring out which cell a given point is in actually very complicated, and in 4D it's a great deal more so. In addition, OpenSimplex noise expands the range of the gradients a bit, so they can extend a little bit into neighboring cells. This theoretically makes the noise a little bit smoother, but it also means that extra cells need to be checked.

Despite this, the blog post claims that OpenSimplex noise achieves better performance than Perlin noise, even if it's not as good as simplex noise. My own experiments disagreed, but this is possibly due to not sufficiently optimizing the OpenSimplex port I was working with. This optimization is a difficult prospect, given that the complexity of the algorithm.

Simplectic Noise


2D simplectic noise
And this leads us to my own noise function. I'm working in Rust, which is an experimental new language I've grown very fond of. The OpenSimplex reference implementation is in Java. So I needed to port it over. The 2D OpenSimplex function wasn't so bad. The 3D one, however, was 558 lines of complicated nested if statements. It was nigh impossible to really understand it, so I just did a raw port, pasting it into Rust and chasing down compile errors until it worked. And surprisingly, it did work. Then I looked at the 4D noise function, which is 1311 lines of even deeper and more complicated nested ifs. My resolve broke.

So I started exploring 3D tesselations myself, figuring I had to be able to find something better. And after digging around some, and playing with lattices of toothpicks and play-doh to better visualize what I was doing, I stumbled on the simplectic honeycomb again... Only I was looking at it a bit differently now. My key realization was this:

2D slice of 3D simplectic noise
An N-dimension simplectic honeycomb is composed of layers of (N-1)-dimensional simplectic honeycombs.

This means that in order to get the value for a given point in N-dimension space, I just need to figure out which two layers it's between, and call the (N-1)-dimensional simplectic noise function twice, once for the layer above this point, and once for the layer below it.

This makes the code incredibly clean and easy to understand. While I've only extended this up to 4D, I could very easily write 5D, 6D or 7D versions. Unlike simplex or OpenSimplex noise, the code size increases linearly with the number of dimensions, and I'd argue that the code complexity increases is something like log(n), because the higher-dimensional versions are just simple functions that call into the lower-dimensional versions.
2D slice of 4D simplectic noise

I initially assumed this would be slower than OpenSimplex noise, but once I benchmarked it, this turned out to not be the case. It's actually faster! My benchmark results are as follows:

Note: The benchmarks originally posted were very different, and inaccurate. This has been corrected, but the blog post from this point down has been heavily edited to reflect that change.

Perlin 2D .......  30 ns
Perlin 3D .......  98 ns
Perlin 4D ....... 212 ns
Simplectic 2D ...  39 ns
Simplectic 3D ...  94 ns
Simplectic 4D ... 207 ns
OpenSimplex 2D ..  48 ns
OpenSimplex 3D .. 122 ns

There is no OpenSimplex 4D in this benchmark, because porting it to Rust was a chore I haven't had the will to undertake. There is no simplex noise in this table because it's patent encumbered, so if I implemented it, it would be just for the sake of this benchmark. I'm not going to use it otherwise. That said, 2D simplectic noise is identical to 2D simplex noise, which again, is acceptable because the simplex patent only applies to 3D and above. (The really observant among you may have noticed that my 2D simplex and 2D simplectic images are actually the same image.)

As you can see, in 2D Perlin is the fastest, but in 3D and 4D Perlin and simplectic are almost the same performance. OpenSimplex is the slowest in both 2D and 3D, though again this may be at least partially due to my inability to effectively optimize the 3D OpenSimplex noise, since it's so difficult to understand.

So we can see that simplectic noise provides higher quality output than Perlin noise, with about the same performance characteristics. OpenSimplex noise doesn't SEEM to live up to it's performance claims, but I'm not willing to make that claim too strongly based on the implementation I have.

Anyway, if you're anything like me, you're probably itching to see the implementation. You can find it on GitHub here.

The library is under the Apache license, but unlike Ken Perlin, I'm not going to take any steps to protect the algorithm itself. Port it to whatever languages you want. Innovate and hack on it. Make it better, if you can! All I ask is to let me know if you do anything really cool with it.

Update:
Some new developments are throwing my performance numbers into doubt. The LLVM optimizer may have been aggressively const folding my code. I'll post more here when I have better info.

Update 2:
Travis "Amaranth" Watkins has done some work on fixing up my benchmarks, so with his help I've got better numbers now. I've updated the post above to reflect his information. It's not nearly as flattering to simplectic noise, which has now been shown to have generally comparable performance to Perlin. This is still valuable, however.

Update 3:
Discovered a tragic flaw in the algorithm, and further work showed the performance to be significantly worse than what's reflected in this post, even after the last update. I can no longer recommend anybody use simplectic noise. I've added the notice at the top of this post to that effect. See the follow-up blog post for details.

4 comments:

  1. As somebody who recently found out about, and was worried by, the patents on Simplex Noise: thank you so much for this, and, bookmarked!

    ReplyDelete
  2. Writing these libs in C would make them usable by pretty much every other language right away. Here's my C lib for opensimplex noise: https://github.com/smcameron/open-simplex-noise-in-c License is public domain.

    ReplyDelete
    Replies
    1. There's a lot of movement to port this to numerous other languages on the Reddit thread, including one person intending a C port.

      Mind you, one of the best parts of this algorithm, and the primary reason I chose this approach, is because it's easy to implement. I'm happy to re-write it in whatever language I happen to be using at the time, because it'll typically only be a couple hours of work for all of 2D, 3D and 4D.

      Delete