Open Simplex has discontinuity artifacts

[mystise]

Your code currently doesn't handle the "extra vertices" from the original Open Simplex implementation, which will result in discontinuities at simplex boundaries. See here for further discussion: Razaekel/noise-rs#141 (comment)

[tayloraswift]

I know that after finding that issue report in noise-rs, but it sounded like OpenSimplex is very slow when the extra vertices are added, and that it was deprecated by its inventor in a mysterious reddit post which is why I’m trying to replace it with SuperSimplex

[mystise]

I wouldn't say very slow, it's only one extra vertex for 2D, 2 for 3D and 3 for 4D, the branching may be a bit slow, but overall it's more the code complexity than the slowdown that's the issue. (And in 2D it's perfectly manageable.) So overall it's only very slightly slower with the extra vertices, it's just annoying to write and debug.

And yeah, KdotJPG hasn't formally published Super Simplex yet, nor has he formally deprecated Open Simplex (He said he'd be updating it at some point soon, but that was a few months ago so who knows when that'll be), but he definitely has implied that Super Simplex is better. I've finished implementing Super Simplex 2D in https://github.com/adudney/noise-rs/tree/super_simplex so feel free to reference that. Note that I'm still working on understanding exactly why Super Simplex is implemented the way it is, so I can't really help you yet with the questions you asked in the other issue, but hopefully soon :)

[tayloraswift]

@adudney from googling this guy’s trail, he never formally publishes anything, he just leaves snippets of code on Gist and in that Minecraft mod repo. Porting the Java code to swift is straightforward, but I would like to understand what it is the new algorithm does so I can debug easier and optimize it for Swift. Especially this line which is baffling:

let squish_offset = math::fold2(point, Add::add) * squish_constant;
let squished_point = math::map2(point, |v| v + squish_offset);

On my graph pad right now it looks like he is using a sampling space that looks like

//         (0, -1)
//         /  |
//      /     |
//   /        |
// (-1, 0)---(0, 0) ---- (1, 0)
//            |   A     /     |
//            |       /       |     ← (u, v) coordinates
//            |     /     B   |
//            (0, 1) --- (1, 1)--------(2, 1)
//                            |      /
//                            |    /
//                            |  /
//                           (1, 2)

[mystise]

It seems like he reversed the direction of the tessellation, so the actual points taken into account are as follows:

//              (-1,  0)
//                 |    \
//                 |      \
//                 |        \
// ( 0, -1) --- ( 0,  0) --- ( 1,  0)
//         \       |    \       |    \
//           \     |      \     |      \
//             \   |        \   |        \
//              ( 0,  1) --- ( 1,  1) --- ( 2,  1)
//                      \       |
//                        \     |
//                          \   |
//                           ( 1,  2)

In addition, I think I need to change the names of the scale and squish factor, as the squish factor transforms from grid space to simplectic space (so [1, 1], becomes [1 + 2 * 'squish factor', 1 + 2 * 'squish factor'], which is more of a stretch than a squish. shrug), while the stretch factor transforms from simplectic space to grid space.

[tayloraswift]

@adudney That’s essentially the same as OpenSimplex… and if x, y is supposed to be taken from triangular space, don’t we need to transform it to rectangular space (“stretch factor”) in order to index the triangles? That’s what I don’t get.

I also finished porting his Java code into Swift, and either I made a mistake implementing it, or SuperSimplex looks worse than OpenSimplex did…

SuperSimplex:

OpenSimplex:

[tayloraswift]

@adudney PS your super simplex noise-rs branch has a “bug” in it; the kernel r² should be 2/3, not 1.

let attn = one - math::dot2(dpos, dpos);

Curiously, when I introduce this “bug” into noise-swift, the noise looks much better (probably because it is discarding fewer vertices)

[mystise]

Oh, right, that was actually something I put in to test if it scaled better (it didn't) and forgot to take out before pushing to github. Whoops.

x, y is given to us in grid space (image space, real space), and has to be transformed into simplectic space.

And yeah, that does look really regular, not sure what's up with that. I haven't tested fBm on my Super Simplex or Open Simplex yet, so I'm not sure.

[tayloraswift]

@adudney according to this pdf, the binning works by transforming from simplectic space to rectangular space, and then transforming back to get the offsets in simplectic space. The image is in simplectic space. But in the Super Simplex algorithm, the binning seems to be done in simplectic space with a floor function, which should only work in rectangular space…

[mystise]

Well, you have my terminology backwards. When in "real space", the simplex grid is a series of equilateral triangles, while in "simplectic space" the same simplex grid is a series of squares. (So the red diagram on page 6 is "real space" while the black diagram is "simplectic space")

It is binning in simplectic space, as it should, since the simplex grid appears as rectangles.

Also, I left you a comment on the most recent commit about how the hashing function might be causing the regularity you're seeing.

[tayloraswift]

@adudney ah that makes sense, though the reversed order of transformations in the Super Simplex code still doesn’t

[mystise]

I'm not quite certain either, I know the math works out for Super Simplex, but I'm not sure why it also works fine with Open Simplex.

Essentially when you look at the line from (0, 0) to (1, 1) in simplectic space, and transform it into real space it has to get shorter (because the simplex grid is squashed along the (1, 1) axis), so when you do the reverse transformation it has to get longer. I'm going to take a look at Open Simplex now to see why they did it the other way around.

Also, in that Simplex noise PDF you linked, the skew factor is switched around like in Super Simplex.

[tayloraswift]

@adudney actually, working through the calculations, I think it may have to do with the different tessellations. OpenSimplex seems to tessellate the cells so that the triangles “fan-out” along the line u = v, while SuperSimplex (and Perlin–Simplex) tessellates them so that u = v forms the divider between triangles.

Still no word on why my SuperSimplex output has so much regularity…

[mystise]

Fascinating. I had a hunch that was it, but hadn't explored it yet. Edit: With a bit more thought I'm almost certain this is the case.

Did you end up testing with a fixed hashing function yet?

[tayloraswift]

@adudney I am using a 256 entry random table and the following hash function:

let hash:Int = random_index_table[(u ^ random_index_table[v & 255]) & 255] & 24

Noise looks a bit better when I replace the XOR with addition, but the Java Super Simplex implementation uses XOR. There are still discontinuities though.

[mystise]

As per my comment on the commit: "Won't this only pick indices 0, 8, 16, and 24? You really want it to only pick even indices from [0, 24), so perhaps (hash % 12) * 2 instead of hash & 24?"

The & 24 at the end is greatly limiting the amount of gradients you actually end up using. Replace it with (x % 12) * 2

Edit: Relevant lines from SuperSimplex.java https://github.com/EversongMill/Genesis/blob/master/src/main/java/genesis/util/noise/SuperSimplexNoise.java#L52 and https://github.com/EversongMill/Genesis/blob/master/src/main/java/genesis/util/noise/SuperSimplexNoise.java#L93

[tayloraswift]

@adudney oh shit good catch I didn’t see that! Noise looks very good now with the fix. I just wish there was a way to avoid the modulo operation. The problem is we have 12 gradients (why 12?) and that doesn’t divide into any power of 2.

From playing around with the gradient selection, can confirm that hashing makes all the difference in the world. Now why are there only 12 gradients? That doesn’t play very well with fBm where the repetitions add up with one another to create triangular artifacts

Anyway I’ll see if I can make sense of the 3D algorithm tomorrow.

[mystise]

Awesome, that looks much better :)

And yeah, 12 is a strange number. I'd suggest changing to 8 or 16, but the only issue is that changing the gradients changes the scale factor. This is one of the issues I'm running into in the rust version, we use the 4 cardinal directions and the 4 diagonals, so the scaling factor he provides of 18 and a bit doesn't work quite right. I'm attempting to find a symbolic solution for the maximum, but it's a very odd calculation and not easy to figure out.

I wish you luck in figuring out 3D, it doesn't do scaling/outside vertices the way I expect it to. I'll be messing around with that soon as well.

[tayloraswift]

@adudney I thought the gradients were generated by rotating a fixed radial vector 15 degrees a time to make 12 vectors. You could easily scale it up to generate any number of vectors (for 2D noise anyway), though a multiple of 8 is probably best to capture the 4 cardinal directions and diagonals. Of course this doesn’t scale well to higher dimensions unless you want to try Fibonacci mapping.

[mystise]

Yeah, that is how the Super Simplex gradients were calculated. What I'm saying is that the scaling factor he uses (18.518518518518519) is only correct for exactly the gradients he uses. If you change your gradient vectors, you'll have to change the scaling factor to keep the output within [-1, 1]

[tayloraswift]

Closing this as Super Simplex has been implemented for both 2D and 3D, and the extra vertices have been added into the Open Simplex generator.