search

love2d / love

LÖVE is an awesome 2D game framework for Lua.
https://love2d.org
Other
4.96k stars 394 forks source link

Noise Function's Implementation may be Patented #1002

Closed slime73 closed 9 years ago

slime73 commented 9 years ago

Original report by Zauber Paracelsus (Bitbucket: zauberparacelsus, GitHub: zauberparacelsus).

The love.math.noise function is an implementation of the Simplex noise algorithm, and generates noise up to 4 dimensions. The problem, however, is that Simplex Noise unfortunately is covered by a patent for 3D and higher implementations.

Is Love using the patented implementation? Or is it using an implementation unaffected by the patent, like what OpenSimplex did?

If Love is using the patented implementation, then perhaps alternatives need to be looked at. There is the aforementioned OpenSimplex implementation, though it is somewhat slower than Simplex (not sure how much). There is also the Wavelet Noise implementation made by Pixar, which like Simplex avoids the artefacts found in Perlin noise.

OpenSimplex: https://github.com/smcameron/open-simplex-noise-in-c Wavelet Noise: http://graphics.pixar.com/library/WaveletNoise/paper.pdf

Footnote 1: Although I set the issue type to Bug, this is more of a general issue than a bug, and I didn't think the other issue types were any more appropriate.

Footnote 2: There are at least a one or two confused claims scattered online that the patent expired in 2005. This is untrue, and 2005 was actually the year that it was published.

slime73 commented 9 years ago

Original comment by Alex Szpakowski (Bitbucket: slime73, GitHub: slime73).

Is Love using the patented implementation? Or is it using an implementation unaffected by the patent, like what OpenSimplex did?

LÖVE uses simplexnoise1234, which unfortunately seems to be an implementation of Ken Perlin's simplex noise rather than its own invention (a software patent of a particular invention covers all implementations of that invention/idea/methodology, unlike copyright.)

Despite the name, OpenSimplex isn't a re-implementation of Ken Perlin's simplex noise, so the patent wouldn't apply to it. Do you know if it has adequate performance (compared to simplex noise implementations)?

slime73 commented 9 years ago

Original comment by Zauber Paracelsus (Bitbucket: zauberparacelsus, GitHub: zauberparacelsus).

I haven't been able to find any benchmarks, but it seems that 2D opensimplex was up to 50% slower than Simplex, with higher dimensional ones being even slower. Although, the author of OpenSimplex did go back and optimize his code to make it a bit faster.

However, his code was in Java and C#, which to my knowledge are more difficult to optimize due to the VM overhead of JVM and .Net, along with garbage collection. The C implementation I linked above may have better performance though.

Either way, OpenSimplex is said to still be faster than Perlin Noise.

As for pixar's Wavelet Noise, I don't know anything about its performance.

slime73 commented 9 years ago

Original comment by Zauber Paracelsus (Bitbucket: zauberparacelsus, GitHub: zauberparacelsus).

On another note, there is the MIT-licensed Hexanoise library, which provides multiple noise algorithms (opensimplex, among others) that are implemented in OpenCL, so they would be able to take advantage of GPU acceleration. That would probably wipe out the performance losses nicely.

https://github.com/Nocte-/hexanoise

EDIT: Actually, not sure that Hexanoise would be a compatible replacement...

slime73 commented 9 years ago

Original comment by Alex Szpakowski (Bitbucket: slime73, GitHub: slime73).

Replaced Simplex noise with Perlin noise for the 3D and 4D variants of love.math.noise, to avoid patent-infringement issues (resolves #1002.)