Add simplex noise [revisit this PR in 2022]#1252
Conversation
|
|
||
| // A lookup table to traverse the simplex around a given point in 4D. | ||
| // Details can be found where this table is used, in the 4D noise method. | ||
| // TODO: This should not be required, backport it from Bill's GLSL code! |
There was a problem hiding this comment.
I actually tried this, but the GLSL code is not faster.
- I tried it in my Go implementation (running on my laptop), where it was actually a bit slower.
- I tried roughly the same code on an ESP32, but it didn't affect the speed (the difference was well within the noise).
For those interested, see: https://gist.github.com/aykevl/dddc20182537f7c00f8b6358de97fc6d
|
Thank you for your work on this -- including the 32-bit-friendly fixed-point implementation! The existing noise functions are overdue for a little careful code review and cleanup; I think we're losing a little precision here and there that we don't need to be. But that's another problem for another day, I think. Anyway, thanks again for all the contributions, and the help with FastLED! |
|
Actually, this was never intentionally made for 32-bit MCUs. I just wanted something that was better than improved Perlin noise and I happened to be using 32-bit MCUs (because I absolutely needed the extra performance for what I was animating: 6144 LEDs at a usable frame rate). It'll probably work on AVRs, it just hasn't been optimized.
Okay, sounds reasonable to me. Note that the patent (from my reading) is only for 3D and up, so the 1D and 2D versions might be safe to merge. Regarding the API: I'm now thinking it might be better to use unsigned integers for the API. That would be a bit more compatible with the existing noise functions, but with the input shifted 4 bits. I used signed integers because I adopted it from a floating point implementation (which are naturally signed), not as a conscious decision. |
|
I'm currently trying to convert the code from signed to unsigned, so it better matches the current simplex noise API (also, I think unsigned integers are easier to work with in this case). |
11b54f9 to
7e2739a
Compare
|
I have updated the PR:
Also, it appears that the patent has expired. The legal status of US6867776B2 is listed as "Expired - Lifetime" so I guess we're in the clear now. Therefore, from my perspective this PR is ready. |
Simplex noise has some benefits over classical (or improved) Perlin noise. It generally has fewer artifacts than previous versions. It still has artifacts, just a lot less noticeable. It is also possible to easily extend the algorithm to higher dimensions without exponentially increasing the computational requirements. One practical advantage is that this implementation also includes a 4D version while the other noise functions only implement 1D, 2D and 3D versions. The implementation has been optimized for 32-bit microcontrollers. I've tried to keep all calculations in 32-bit integers, only going to 64-bit when really necessary.
|
Rebased to fix the merge conflict, and removed the patent warning (because the patent is expired). This PR seems ready to me, is there anything missing? Meanwhile I've found that there were some unintended division instructions in the code (I assumed they would be optimized away). This is fixed here but not yet in this PR. It basically makes the noise functions a lot faster on chips that don't have a hardware divide instruction like Cortex-M0. I might update the PR eventually but I don't currently have an easy way to test FastLED changes. |
|
Patent has expired so no more issues with this being merged in |
|
Thank you for merging! Note that since I made this PR, I've optimized the original code to avoid a division instruction that wasn't optimized as I had expected. This would result in a 3.6x speedup in the 1D case (less so in 2D an up). The change is here: aykevl/ledsgo@f76cfa2 |
|
I've lifted your changes into a new PR. You were tagged so you should see it in your notifications. |
|
Actually I wasn't notified, I don't see you tagged me? |
Simplex noise has some benefits over classical (or improved) Perlin noise. It generally has fewer artifacts than previous versions. It still has artifacts, just a lot less noticeable. It is also possible to easily extend the algorithm to higher dimensions without exponentially increasing the computational requirements. One practical advantage is that this implementation also includes a 4D version while the other noise functions only implement 1D, 2D and 3D versions.
The implementation has been optimized for 32-bit microcontrollers. I've tried to keep all calculations in 32-bit integers, only going to 64-bit when really necessary.
The API is a bit different because I converted to fixed-point separately. I also didn't care about possible benefits for microcontrollers for a 16.16 fixed point format, so I picked what seemed better to me at the time: a 19.12 format (or 20.12 if you count the sign: it's a signed integer).
Note that this is covered by a patent, probably until early 2022: https://patents.google.com/patent/US6867776
However, it might not apply to simple LED animations: https://patents.stackexchange.com/questions/18573
The patent is currently owned by a patent troll so it would be rather risky to bring any products to market that uses this algorithm. If this is a problem, it may be better to just wait with merging this PR until the patent has expired.
Also see #1251.