Question on Higher Dimensional noise

felix91gr commented 6 years ago

Hi Jack,

I'm a fan of procedural noise. I used it for procedural generation when I took the graphics classes.

However, I've always wanted to be able to generate 5D and 6D noise. For example, if you wanted to have noise in a 3D sphere, that changed through time but that also looped back at some point in time, you'd need 5D noise to do it without having an obvious "backwards through time" transition. We managed to make it work with a geometric hack and the 4D noise, but anyway. I digress.

My question: do you know where can I ask about this? Do you know what can I read about it? Everywhere I've looked only has non-generic code for 1D-4D and no explanation on how to proceed upwards.

Do you think it's possible? Or is it that just no-one has bothered to try? I could try to program it, but I'm not versed in the theory behind Noise, so I'd need some kickstart at first.

Sidenote: I know one can implement Perlin Noise that does this. But PN is exponential in the number of dimensions, so that wouldn't really be satisfying (after 6D or 7D you'd be stuck). I'm looking for a more efficient function, like Simplex - or anything that isn't exponential like Perlin is.

Sidenote 2: please tell me if you'd prefer I close this issue, I didn't know where to ask you directly.

jackmott commented 6 years ago

You could try asking here : https://www.reddit.com/r/proceduralgeneration/ Or maybe emailing Stefan Gustavson: http://staffwww.itn.liu.se/~stegu/simplexnoise/simplexnoise.pdf

I personally wouldn't know how to go about it.

felix91gr commented 6 years ago

Jack, thank you so much! That pdf has spurred in me and my friend @Ghoeb the intent of actually implementing it. I think we now understand more or less how it should work.

We're now working step by step on the implementation here. We're starting with Perlin Noise, because we want to get a warm-up on Rust first (we've never programmed in Rust). After we get it working generically for N dimensions, we're going to get started on doing the same for Simplex Noise :)

felix91gr commented 6 years ago

What we now understand of the right implementation of Simplex is that it should be:

Ω(nlogn) and O(n²) in time.
ϴ(1) in code size.
ϴ(n) in memory allocation.

The increased time complexity to Ω(nlogn) is for sorting the coordinates of the point in order to find its corners. There might be a faster method, but for the moment that's what I've come up with to get it started.

The upper bound of O(n²) in time complexity comes from us having to skew the n-D vector to take it to the space where the axis-aligned hypercube that contains its simplex is. We plan to do it with a nxn matrix at the moment, and from there comes the complexity. In the provided implementations, they use a hardcoded method which we might be able to generalize. That method seems to be O(n), but I haven't yet fully cracked it.

ϴ(1) in code size comes from us instantiating the gradients of the corners at runtime instead of using the typically used exponentially-sized static table with all of the nx2^n-1 possible gradients prebuilt.

ϴ(n) in memory allocation is probably unavoidable since you have to have the (n+1) corners of the simplex, and their gradients, stored somewhere.

jackmott commented 6 years ago

Cool! I've heard of people implementing generic-dimension cell noise but not perlin or simplex noise. I don't know if it would make sense to include such a thing in a high performance lib, since the generic-ness of it will hurt performance a bit, but we could maybe use it to come up with a 5d implementation or something.

felix91gr commented 6 years ago

I don't know if it would make sense to include such a thing in a high performance lib, since the generic-ness of it will hurt performance a bit

I think that after generics over constant integers lands, we can work on optimizing most of the generic-ness away at compilation time. If I understood this feature correctly, knowing n at compile time allows you to:

Unroll (and if available, vectorize) all the loops.
Pre-allocate in the stack all of the internal variables.
Precalculate constants such as 1 / sqrt(n - 1), which are used for e.g. making the gradients unitary.

The only thing that can't (or shouldn't, I think) be precalculated are the gradients themselves like in the common 2D, 3D and 4D implementations, since that gives rise to the exponential table that I mentioned before. Without counting that table, I feel that we can probably come up with a very fast, thoroughly statically-known at compile-time function for arbitrary n :)

Edit: I might've skimped on a good explanation. As far as I understood it, this feature would look like this:

pub fn create_gradient<n: usize>(corner: [f32; n]) -> [f32, n] { ... }

This defines of course infinitely many different functions. When you call one for a specific n, however, only then they get instantiated and specialized. This should allow us to work on very generic terms, but having the generic-ness be specialized away at compile-time.

Edit 2: I didn't acknowledge your point. Sorry about that!

I think you're right. There's a very high chance that a generic method can't be as fast as a hardcoded-dimension one would be. I think we might be able to get close, though. We'll see! :)

, but we could maybe use it to come up with a 5d implementation or something.

I'd love to help with that! (and I think Vicho - @Ghoeb - would as well <3). I'm certain we can do this as efficiently as possible, after understanding the algorithm.

amaranth commented 6 years ago

http://kaba.hilvi.org/pastel-1.4.0/pastel/gfx/noise/simplex_noise_notes.htm should be useful for figuring out how to make 5D (or higher) simplex noise. It may not be all that useful though as I've heard simplex noise doesn't work well past 4D due to visible surflets. This is the main improvement of OpenSimplex outside of the avoiding the patent situation but it makes OpenSimplex much more complicated and slower.

For gradients, I came up with https://gist.github.com/amaranth/a9ed8fff9a3c029aa743 some time ago (in Python for prototyping) that should generate the appropriate non-normalized gradients for any dimension.

Edit: Looks like that page lost its MathJax, here is a wayback link so you can see the math involved too: https://web.archive.org/web/20160529130139/http://kaba.hilvi.org/pastel-1.4.0/pastel/gfx/noise/simplex_noise_notes.htm

verpeteren / rust-simd-noise

Question on Higher Dimensional noise #2