4

Okay, there are a lot of comparisons between Perlin and Simplex noise to be found on the web. But I really couldn't find one where there was a simple processing time comparison between both for three dimensions, which is what I am mostly interested in. I've read that popular PDF (and even understood most of it - yay!) but I cannot answer the simple question: Which one is faster for 3D, assuming an optimal implementation?

This stackoverflow question answer suggests that Simplex is a pretty clear winner for my case. Of course, there are other resources claiming the exact opposite.

However, the general statement seems to be that Perlin noise has a complexity of O(2^N), while Simplex has O(N^2). Which for 3D would mean 8 for Perlin and 9 for Simplex. But, on some site I found the statement that Simplex is actually O(N). So what is true here, and what does that really mean for speed in 3D?

I am at a loss here, I'm really mainly interested in 3D application (for random terrain generation including caves) usage, and I cannot find a good answer to the question which one I should use if I want it to be as fast as possible.

So maybe someone can help me here :)

Community
  • 1
  • 1
TheSHEEEP
  • 2,961
  • 2
  • 31
  • 57
  • 1
    Wiki says that Simplex is n^2, so maybe that answer you refer to mistyped it? – Kromster Oct 05 '12 at 12:29
  • Perfectly possible, yeah. Still, I'm more interested in what that actually means for speed. If you take those 8 and 9 as the only measurement, there wouldn't be so many people claiming that Simplex is faster. – TheSHEEEP Oct 05 '12 at 12:32
  • 3
    N means how well algorithm scales up, but it says nothing about speed of it. – Kromster Oct 05 '12 at 13:13
  • @Kromster What, who upvoted you? N is indeed a mistake as seen by this author sourced here http://webstaff.itn.liu.se/~stegu/simplexnoise/simplexnoise.pdf. Many people copied his code and examples and ended up with the same mistakes before he fixed them in later 2012. – Krupip Jul 15 '17 at 03:05

2 Answers2

9

1) http://www.fundza.com/c4serious/noise/perlin/perlin.html
2) http://www.6by9.net/b/2012/02/03/simplex-noise-for-c-and-python

Execution times in "my laptop" for 8M samples of noise using these two implementation: (g++ -O6)

1) 1.389s i.e. 5.7M ops per second 2) 0.607s i.e. 13.2M ops per second

But...

When really, really going for the optimizations, one should study

  • Higher level optimizations (what really is done in each stage: are there alternatives?)
  • Branches
  • Memory patterns
  • Dependencies
  • LUT sizes
  • Individual arithmetic operations needed, their latencies and throughputs
  • exploitable parallelisms using SIMD
  • number of live variables
Aki Suihkonen
  • 19,144
  • 1
  • 36
  • 57
  • Nice answer, thank you! That really is a lot faster than I expected. So even if your laptop is not representing all the machines out there, this does seem convincing. You are of course right that there are more things to consider than just the algorithm itself. – TheSHEEEP Oct 05 '12 at 14:04
  • Its worth noting that simplex noise was designed by the same person who developed perlin noise and to create noise with the same properties but more efficiently and without artifacts. So if simplex noise was slower that would be pretty shocking – Richard Tingle Jul 03 '13 at 10:16
2

Simplex noise is better looking, but not necessarily faster. It all depends on the implementation. As a rule of thumb, it is "about the same speed", and there shouldn't be a big penalty from using either variant if your code is good.

Note that most of the code I have written that is floating around on the Internet is not optimized for speed, but written for clarity. The GLSL implementations by Ian McEwan and myself from a couple of years ago are reasonably optimized for speed, but they were optimized for hardware which is now outdated, and the versions of GLSL that were current at the time. Important changes to GLSL since then include integer types and bit-wise logical operations, which makes some of the hash functions awkward and unnecessarily complicated,. The need for a permutation polynomial was motivated by the lack of bit-wise logic operators in GLSL. It's still lacking in GLSL for WebGL, but all other platforms now have integer support.

Simplex noise in 4D is mostly faster than classic noise in 4D. All other cases depend on the language, the platform and the amount of code optimization.

Simplex noise has a simple analytic derivative. Classic noise is more tricky in that respect. In many cases, like antialiasing and terrain mapping, an analytic derivative is very useful.

Stefan Gustavson
  • 121
  • 1
  • 1
  • You sure you don't mean perlin noise has a simple derivative? Simplex noise has defined analytical derivatives, but they are much much harder to understand and derive, though not particularly computationally expensive. Or are you equating classic noise to value noise? – Krupip May 10 '19 at 20:56