Worley noise has incomplete kernels

[tayloraswift]

Sampling worley noise at half-kernels requires a minimum of eight generating points to be samples. Your library only wanders the control points around a disk of radius 0.5 instead of filling out the whole grid cell though, so it may be possible to only consider 6 points though I haven’t worked out the math.

    //          O ------- far
    //          |    |    |
    //          |----+----|
    //          |  * |    |
    //       near ------- O

    //               xb   xb + 1
    //          +------------------+
    //          |     |      |     |
    //       yb X---- O//////O ----|
    //          |     |//////|     |
    //   yb + 1 X---- O//////O ----|
    //          |     |      |     |
    //          +-----X------X-----+

The generating points marked with an X are missing from the kernel.

Here is an example of an artifact caused by this:

[Razaekel]

Thank you for pointing this out. Could you provide the settings that you used when you discovered this error?

The way a basic implementation of Worley noise is supposed to work is that it divides the sampled space into squares with a size of 1/frequency, and then places a point in a random location within each square. It then takes the point you're asking for, finds the square that it's located in, and tests the surrounding squares for the nearest points. This means that it should be checking 25 squares in 2d. This means in 2d, at least 9 squares need to be tested, if the point is exactly at the middle of the square, and up to 12 squares if the point is at the corner.

Thinking about it, the radius for 2d should be sqrt(2) (diagonal of a square), not 0.5. And 3d should be the diagonal of the cube, sqrt(3). And so on.

The Worley noise was a direct conversion of the older functional implementation. It wasn't checked for correctness.

[tayloraswift]

Actually I discovered you need to consider exactly twelve points for 2D. See noise-swift:CellNoise2D for an explanation.

The screenshot I attached was given as an example of “correct” output in issue #175 (worley-linear-range_2d). It’s in the center-left of the image there.

3D forces us to expand the kernel to two layers in some cases, I haven’t worked it out. It is probably on the order of ~40 or so points…

[tayloraswift]

Did the math. Exactly 90 cells must be considered for 3D worley noise. Early exit is possible if the cells are checked in groups in a certain order.

Working implementation: noise-swift:CellNoise3D › evaluate(:::)