Pages

Wednesday, January 14, 2015

Simplectic Noise, Part 2: Not so great after all

So over the past two weeks, since I first published the article on simplectic noise, a number of people have ported it to other languages, and I've continued to work on and tweak it. Many people have pointed out flaws in the algorithm, and I've discovered a number of my own. All together, I'm left to conclude that simplectic noise doesn't actually have much value.

Surflet Size


The major problem is the surflet size. A surflet is a single gradient (hyper)sphere in a gradient noise
2D simplectic noise, without the corrected surflet
size, zoomed in with increased contrast to
reveal the subtle discontinuities
function. When implementing simplectic noise, I made a mistake with the gradient equation that determines the falloff of the surflet. I made it:

(sqrt(0.5) - range^2)^4

When it should have been:

(0.5 - range^2)^4

Basically, I failed to account for the fact that the range was squared, and thus the value it's being subtracted from also needed to be squared. The surflets in 2D needed to have a radius of sqrt(0.5), so I need to subtract the range^2 from sqrt(0.5)^2, or 0.5. This resulting in the surflets having a radius of sqrt(sqrt(0.5)), or ~0.84089641525, which is larger than a simplex.

4D simplectic noise with corrected surflet sizes
This created discontinuities at the borders of the 2D simplexes. The gradient falloff function happens to go near zero at about 60% of the radius of the surflet, so these discontinuities were very subtle. In most cases, they were impossible to see with the naked eye, which is why I didn't notice them. However, at very low frequencies, or when used as a heightmap, the discontinuities can become very apparent.

So, easy enough to fix, right? Well, first of all, when you fix the math the surflets become just a little bit too small. It becomes easy to visually pick out individual surflets. Now, it turns out this problem exists in simplex noise as well, so it can't be that bad, right? Well, in simplectic noise, the problem is exacerbated in higher dimensions. It's not that bad in 2D, but it's horrible in 4D.

I've also gained a deeper understanding of OpenSimplex noise. The reason it's so complicated is because it's solving this exact problem. It samples a few extra surflets, from outside it's immediate shape, in order to allow the surflets to have a larger size. While this adds a lot to code complexity, and significantly hampers performance, it makes the quality of the noise actually higher than simplex, and much higher than simplectic.

Performance


Travis Watkins has continued to do amazing work optimizing the noise-rs library, in which I implemented simplectic noise. With every pass he's made, Perlin noise has benefited more than anything else. At this point, our Perlin implementation is incredibly fast. OpenSimplex has fallen behind, and simplectic even more so. Simplectic noise has also resisted all our attempts to significantly optimize it. Further, we've improved the quality of our benchmarks, and the more accurate results have not been kind to simplectic noise. Thus, I can no longer make any significant performance claims. The current numbers on my machine look like this:

     Perlin  Simplectic
2D   21 ns   36 ns
3D   48 ns   100 ns
4D   76 ns   211 ns

So in all dimensions, it's quite a bit slower than Perlin noise. And in 3D and 4D, it's also much lower quality. So there's really not much left to recommend it.

I'm sorry for publishing my results to this blog prematurely. Perhaps the concepts behind simplectic noise will inspire some other innovations, but for now I hope people haven't wasted too much time on it.

Reference Implementation


Since I no longer believe simplectic noise to be valuable, I'm pulling it out of the noise-rs library I'd originally written it in. To save the reference implementation for posterity, I've created a new github repo for it here.

Update:
One of the optimizations that Travis had made to Perlin noise had to be rolled back, which caused the 2D Perlin to get a bit slower, but otherwise had a minimal effect. I've updated the benchmarks above.

4 comments:

  1. Well I got to learn more about noise while porting it and reading this analysis was interesting!

    ReplyDelete
  2. As my uncle, who publishes many scientific papers on mathematical methods which do not work, says, "A negative result is still a valuable result."

    ReplyDelete
  3. Too sad that your simpletic noise lacks quality and performance. I tried out the OpenSimplex too (I use OpenCL) and it ended up to be 30% slower than the old perlin noise.
    Like you, I can't tell if it's caused by unoptimized implementation or just a slower algorithm.

    Do you work on something new or will you just stay with the old perlin? When I figure out a way to boost OpenSimplex I will let you know :D

    ReplyDelete
    Replies
    1. At this point, the Perlin implementation we have is so incredibly fast, it even beats our simplex noise, in 2D, 3D and 4D. I'd guess that we have the most optimized implementation of Perlin noise out there.

      Mind you, I can't claim much credit for that. I wrote the initial implementation, but then Travis Watkins dove in, read all the papers and posts people have made on the subject over the years on Perlin noise, and tried out every combination of optimizations that made sense. The result blows away every other noise function in terms of performance, at least up to 4D.

      So, this comparison is really not fair to OpenSimplex. It hasn't undergone anywhere the same level of rigorous optimization. And given how much of the Perlin optimization was the result of just combining the work others had done in the past over the 30+ years since Perlin noise was invented, it's unlikely we'll be able to bring the same level of optimization to bear on OpenSimplex for some time.

      Delete