FastNoise Implementation

clayjohn commented 6 years ago

Now that issue #21569 has been added we can think about adding more noise modules. This will give users the option to select what type of noise they would like to

I suggest we look into adding FastNoise, it is super fast plus it includes many types of noise (cellular, value, simplex, perlin, white). If possible, we could even take advantage of SIMD with FastNoiseSIMD, which is significantly faster than any of the other options out there.

TokisanGames commented 4 years ago

Here is the FastNoiseSIMD referenced above. Note both of these libraries include SimplexNoise which might need to be cut out until the patent expires on 2022-01-08.

We can also consider New-Simplex-Style-Gradient-Noise from the author of our currently used OpenSimplexNoise, which includes optimized versions and other variations, some of which appear to be 3-4x faster than even FastNoise Simplex according to benchmarks in the readme (but not FastNoiseSIMD).

Here's a reddit thread from the author describing the new algorithms.

Maybe we can use a mix of both, as the FastNoise library includes other noise algorithms like cellular/voronoi noise.

TokisanGames commented 4 years ago

@Zylann has already created a FastNoise module for Godot.

Next, I'm currently experimenting with FastNoiseSIMD. This version has some caveats so far:

Though it detects the highest available instruction set at run time, it needs to be compiled with a compiler switch. e.g. /arch:AVX2 for MSVC. The author recommends only certain files have these switches instead of the whole project as this defines the minimum instruction set to use.
Speed gains come from getting a whole block of noise at once, ideally sized in multiples of 8. e.g. You ask the GetNoise function to return a 16x16x16 array of floats.

Zylann commented 4 years ago

I'll put the emphasis on area generation as well. This opens huge performance gains, as many use cases are down to generating a 2D or 3D area at once, not just individual values. This is even more relevant if the function is virtual on top of that. Such thing could be added to the API, however it's unclear which kind of "area" data structure to expose. Could be Image, PoolRealArray, Array... (in any case I'd use something custom in C++ because none of those data structures fit my performance requirements).

TokisanGames commented 4 years ago

I'm working on a PR for FastNoise, and experimenting with FastNoiseSIMD for a second one. I'd like some guidance on topics below, but so far so good.

fastnoise-cellular

Class structure

Currently we have OpenSimplexNoise : Resource and NoiseTexture : Texture.

NoiseTexture specifically refers to OSN for calls like noise->get_seamless_image() and noise->get_image(). I've made an abstract class Noise : Resource so OSN and FN can inherit from it. Is this the right way to go?

File Organization

The current file structure looks like this:

modules/opensimplex
- OpenSimplexNoise godot class
- NoiseTexture godot class (creates a 2D texture from a noise module)
thirdparty/misc
- OpenSimplexNoise.c library

We probably want these in their own directories. Can the libraries be included in the modules?

modules/noise
- /noisetexture
- NoiseTexture godot class
- /opensimplexnoise
- /lib/OpenSimplexNoise.c library
- OpenSimplexNoise godot class
- /fastnoise
- /lib/FastNoise.cpp library
- FastNoise godot class
- /fastnoise_simd
- ....

Or:

modules/opensimplexnoise
modules/fastnoise
modules/fastnoise_simd
thirdparty/opensimplexnoise
thirdparty/fastnoise
thirdparty/fastnoise_simd

Or all thirdparty in /thirdparty/misc? But where then should noise_texture go?

Seamless Textures & 4D noise

Our current method to get seamless textures is to use 4D noise.

But not all of the considered noise algorithms provide 4D noise. All performance metrics are compared to OSN.

OpenSimplexNoise (implemented): has 4D
Updated OpenSimplexNoise(15-20% up to 15x faster [4D]): has 4D
SuperSimplexNoise (~2x faster): "4D is coming"
FastSimplexNoise (~3x faster): "4D is coming"
FastNoise (~2x faster): 4D only in White Noise and Simplex
FastNoiseSIMD (10-40x faster): 4D is being explored as of October/2019 for some algs, but some have said this won't be good to do with SIMD

I'm looking at alternative methods, and this to make seamless textures. Edit: also I was informed on Twitter I can use a "periodic hash" to make seamless textures without changing the algorithm, and it's faster. So just need to look that up...

Also why implement FN if the new OSN/SSN/FSN are faster and more likely to fully support 4D? Because FN has cellular and other algorithms.

FN/Simplex noise patent

The patent expires 2022-01-08.

It covers what amounts to seamless textures:

The apparatus includes a mechanism for producing images with texture that do not have visible grid artifacts. FIELD OF THE INVENTION The present invention is related to an improved standard for noise. More specifically, the present invention is related to noise where images have texture but do not have visible grid artifacts and/or are visually isotropic.

I think I should comment out the simplex noise type so users won't inadvertently use it until the patent expires. Also it's not really needed since FN/Perlin is comparable and faster, and OSN can be updated. What do you think?

Implementation Plan

So here's my idea moving forward to give us a good coverage of algorithms:

FastNoise without Simplex for other noise types
FastNoiseSIMD without Simplex
Update OpenSimplexNoise to newest version
Replace OpenSimplexNoise with SuperSimplex and FastSimplex once 4D is available

FastNoiseSIMD really is superior to FN. Playing with the sample app, 3D noise generation is 5 up to 20 times faster than FN depending on the algorithm, and 2x that compared to OSN.

How does this sound?

Calinou commented 4 years ago

FastNoiseSIMD really is superior to FN.

Is the performance at least as good on platforms that can't make use of SIMD? IIRC, not all platforms can do that.

TokisanGames commented 4 years ago

FastNoiseSIMD says it has cpu detection and defaults back to regular ints/floats if SIMD is not supported. So it shouldn't be any different on a non simd system. And maybe I should forget about FN and just do FNsimd.

My results on the bottom were from my i7-8750h which can use the AVX2 instruction set. Older processors can use AVX, SSE4 or SSE2. Also there is support for ARM Neon.

simd support and performance metrics: https://github.com/Auburns/FastNoiseSIMD/wiki/In-depth-SIMD-level

fire commented 4 years ago

I'm still looking an implementation of seamless 3d noise for Godot Engine.

TokisanGames commented 4 years ago

I'm still looking an implementation of seamless 3d noise for Godot Engine.

Open simplex noise already provides us seamless noise. We use it in the voxel terrains. It's just a little slow, which is why I'm spearheading this. Do you mean implementing a 3d texture? Because that's out of scope for me.

Also, to general, I was informed on Twitter that 4d noise isn't the best way to make seamless textures, it's just clever. That I can use a periodic hash and it's much faster. So now to figure out how to do that... But I guess that means 4D isn't as important as I thought. Useful for some, but not required for seamless 2D.

fire commented 4 years ago

I have code for 3d texture, I just can't find a function that can generate the 3d texture full of seamless noise. See https://github.com/Xrayez/godot-anl

Zylann commented 4 years ago

I think @fire refers to tiling noise, is it?

JFonS commented 4 years ago

Hi, I'm the developer that first integrated OpenSimplexNoise into Godot. Feel free to work on improving everything noise related, I just did a basic integration to get things started :)

Class structure

Currently we have OpenSimplexNoise : Resource and NoiseTexture : Texture.

NoiseTexture specifically refers to OSN for calls like noise->get_seamless_image() and noise->get_image(). I've made an abstract class Noise : Resource so OSN and FN can inherit from it. Is this the right way to go?

Yes, that was the original plan but since we only had one noise type we postponed it until somebody wanted to implement a new noise type. That's definitely the way to go.

File Organization

The current file structure looks like this:
* modules/opensimplex

  * OpenSimplexNoise godot class
  * NoiseTexture godot class (creates a 2D texture from a noise module)

* thirdparty/misc

  * OpenSimplexNoise.c library
We probably want these in their own directories. Can the libraries be included in the modules?

Thirdparty libraries need to go in the thirdparty directory, and Godot tends to group related classes in the same directories instead of having a deep separation in directories, so I would propose the following:

modules/opensimplex
- Base Noise godot class
- OpenSimplexNoise godot class
- FastNoise godot class
- Other noise type integrations
- NoiseTexture godot class (creates a 2D texture from a noise module)
thirdparty/noise
- OpenSimplexNoise.c library
- FastNoise.c library
- Other noise type implementations

Seamless Textures & 4D noise

I'm looking at alternative methods, and this to make seamless textures. Edit: also I was informed on Twitter I can use a "periodic hash" to make seamless textures without changing the algorithm, and it's faster. So just need to look that up...

That would be very nice, I didn't spend much time investigating the "proper" way to make seamless noise and I went the easy route instead.

FN/Simplex noise patent

I think I should comment out the simplex noise type so users won't inadvertently use it until the patent expires. Also it's not really needed since FN/Perlin is comparable and faster, and OSN can be updated. What do you think?

We don't want to include any patent violations to Godot, so yes, I would remove Simplex from the FastNoise copy we use.

Implementation Plan

So here's my idea moving forward to give us a good coverage of algorithms:
1. FastNoise without Simplex for other noise types

2. FastNoiseSIMD without Simplex

3. Update OpenSimplexNoise to newest version

4. Replace OpenSimplexNoise with SuperSimplex and FastSimplex once 4D is available
FastNoiseSIMD really is superior to FN. Playing with the sample app, 3D noise generation is 5 up to 20 times faster than FN depending on the algorithm, and 2x that compared to OSN.

How does this sound? Are there any differences between FastNoise and FastNoiseSIMD other that implementation and performance? If not I would just make it transparent to the user, if SIMD is available compile FastNoiseSIMD and use FastNoise otherwise.

I would also keep OpenSimplexNoise for compatibility reasons, does the new version break compatibility with the one we currently use? As in, does the same seed and parameters generate the exact same noise pattern?

So in 4.0 we could just have OpenSimplexNoise and FastNoise. FastNoise seems to be better in every situation so I would set it by default on newly created NoiseTexture and OpenSimplexNoise would just be kept for compatibility with 3.x and in case someone needs 4D noise.

TokisanGames commented 4 years ago

Thanks for the guidance, @JFonS.

modules/opensimplex

If this is going to house all the noise classes, wouldn't the directory be better named modules/noise to match thirdparty/noise?

I would also keep OpenSimplexNoise for compatibility reasons, does the new version break compatibility with the one we currently use? As in, does the same seed and parameters generate the exact same noise pattern?

I don't know yet if the new version of OSN produces an identical result. I'll look at that later. I do know the author's FSN and SSN produce very different results.

JFonS commented 4 years ago

If this is going to house all the noise classes, wouldn't the directory be better named modules/noise to match thirdparty/noise?

Yes, I messed up copy-pasting, I meant modules/noise.

I don't know yet if the new version of OSN produces an identical result. I'll look at that later. I do know the author's FSN and SSN produce very different results.

Ok, feel free to ask any other questions :)

TokisanGames commented 4 years ago

I've uploaded a nearly complete implementation of FastNoise. I have a couples things I'd like help with.

Cellular noise allows for a recursive lookup by providing an additional FastNoise lookup. It works and provides an interesting result. Here is small cellular noise on top of big cellular noise. On the right you can see both FastNoise objects.

1. Is this the right way to allocate a new object without leaking memory?

This is what I'm doing now: set_cellular_noise_lookup(memnew(FastNoise()));

This doesn't create the object: set_cellular_noise_lookup(Ref<FastNoise>());

Please review FastNoise::set_cellular_return_type() and FastNoise::set_cellular_noise_lookup()

2. How to refresh an editor panel? When Noise Lookup is selected, a secondary FastNoise object is automatically created if one does not exist. However, the editor still displays [empty]. When I click on it, the field updates and shows the new FastNoise object. How do I refresh the editor panel from code?

3. How to update the second FastNoise? On every set function in FastNoise, I emit_changed(), which updates the texture. However, on the secondary FastNoise, no updates refresh the texture. I have to adjust something in the first FN to get the texture to regenerate. How can I push this signal up?

I was thinking FN could have a reference to a "parent", then pass this to the secondary. That way any secondaries can call up the chain to issue an emit_change. Or is there a more Godot way to do this?

4. Not that it's ready to merge, but my draft PR failed some checks. Specifically it's trying to build /modules/opensimplex/* even though I changed SCsub, the files don't exist, and the project builds fine. What other files do I need to change to get Travis CI to update its list of modules and files?

5. Library changes

I made a patch to document my changes to the library as the original OSN module did.

I also noticed there were changes to the OSN library to prevent it from allocating memory or something. Are there rules against this?

Next Before finalizing this PR, I'm going to play with FastNoiseSIMD and if I can get it to work in singular mode GetNoise(x,y) as well as a set mode GetNoiseSet(x,y,16,16) without a major performance hit over regular FN, then I'll probably replace it with only FastNoiseSIMD. If not, then I'll look at providing both.

bojidar-bg commented 4 years ago

Is this the right way to allocate a new object without leaking memory?

You should probably use Ref<T>::instance() to instance the object inside the Ref.

How to refresh an editor panel?

There is Object::_change_notify and Object::property_list_changed_notify, which might be useful for that.

How to update the second FastNoise?

Subscribe from the first one to the second one. There is some similar code in theme.cpp.

Not that it's ready to merge, but my draft PR failed some checks.

Your code did not pass clang-format checks. The lines about No such file or directory are not causing the error, you should check the lines below.

Library changes

I cannot say for sure, but, in general, dynamic memory allocations are slow -- slower than allocating beforehand, or not allocating at all. Those can be look in later pull requests, though, as this is no reason to block potentially useful features.

Note that this kind of questions and answers discussion happens relatively slowly on GitHub, especially on GitHub issues. I would suggest asking in various Godot development channels (e.g. #godotengine-devel on freenode IRC) or in the PR itself, so that the discussion is more timely or better scoped.

TokisanGames commented 4 years ago

FastNoise has been implemented in #35144. I have versions for both Godot 3.2 and 4.0. It just needs documentation, which will be coming.

FastNoiseSIMD has also been implemented, but in an external repository since mingw-w64 cannot cross-compile SIMD code. It also has versions for 3.2 and 4.0, and builds and works fine under Windows/msvc and Linux/gcc. I'll be releasing my Godot binaries soon, once I get it working for OSX and Mono.

Although I proposed implementing the updated versions of OpenSimplexNoise, after having worked on this for 2 months, I'm done for a while and will be getting back to my other projects. There are more than enough options for wildly creative, high-performance noise with these two modules now. Also OSN needs to be ported to C++ and 4D+ is not available yet.

The PR is set to close this issue, but I could leave it open as a discussion on these other algorithms if desired. Just let me know.

clayjohn commented 4 years ago

Feature and improvement proposals for the Godot Engine are now being discussed and reviewed in a dedicated Godot Improvement Proposals (GIP) (godotengine/godot-proposals) issue tracker. The GIP tracker has a detailed issue template designed so that proposals include all the relevant information to start a productive discussion and help the community assess the validity of the proposal for the engine.

The main (godotengine/godot) tracker is now solely dedicated to bug reports and Pull Requests, enabling contributors to have a better focus on bug fixing work. Therefore, we are now closing all older feature proposals on the main issue tracker.

If you are interested in this feature proposal, please open a new proposal on the GIP tracker following the given issue template (after checking that it doesn't exist already). Be sure to reference this closed issue if it includes any relevant discussion (which you are also encouraged to summarize in the new proposal). Thanks in advance!

TokisanGames commented 4 years ago

@clayjohn Does this really need a proposal? The PR is already done and just needs to be reviewed and merged.

clayjohn commented 4 years ago

@tinmanjuggernaut I dont think so. Your PR provides a pretty good explanation and this issue has a good amount of discussion.

Calinou commented 2 years ago

For future reference, this was implemented by https://github.com/godotengine/godot/pull/56718 in 4.0.alpha.

godotengine / godot