# Overview

Atlassian Sourcetree is a free Git and Mercurial client for Windows.

Atlassian Sourcetree is a free Git and Mercurial client for Mac.

# B-Spline noise

B-Spline noise seems to generate less regular patterns than Simplex and Perlin noise, at the cost of using more interpolation points.

I got the idea from playing with NURBS. By placing the knots on the control points and removing the weights I thought it would be a good interpolator for noise. It turned out this is simply B-Splines and hencly "B-Spline Noise" :)

This repository has quadratic and cubic b-spline implementations in 2d. For 2d, quadratic requires 9 control points (3x3) and cubic 16 (4x4). For 3d, quadratic will require 27 and cubic 64. So performance wise it probably doesn't scale very well over dimensions.

## How fast is it?

To give an idea, generating noise for 9000000 random points:

Noise function | time |
---|---|

Perlin (quintic) | 151 ms |

B-Spline Quadratic | 237 ms |

Simplex | 255 ms |

B-Spline Cubic | 393 ms |

## Fast pseudo random generation from a point

Both implementations of Perlin and Simplex noise in the performance test above use table lookups to get "random" gradients. But for fun I examined a bunch of ways to quickly generate a less discrete random number from a position. This is a hash problem, where we want to hash a coordinate with few collisions and good bit distribution. After running a few statistical tests on the distributions generated I found that combining the approach described here and here gave good results.

... private static final long BITS = 62; private static final long BIT_MASK = (1L << BITS) - 1L; private static final double NORMALIZER = 1. / (1L << (BITS - 1)); private static double _n(final long x, final long y) { long c = (x * 73856093L) ^ (y * 83492791L); c ^= (c >>> 23); c *= 0x2127599bf4325c37L; c ^= (c >>> 47); return NORMALIZER * (c & BIT_MASK) - 1.; }

You can find the full source in the repo (where the normalizer is delayed and applied once).

The code above first combines x and y and then applies a bit mixer. The mixer only uses one multiplication. For even better "random" numbers, apply the mixer to x and y first and then combine them (this is slower though). If I recall correctly, applying the Murmur3 finalizer (slower with 2 multiplications) gave the best uniform result.

## How does it look?

Cubic B-Spline noise (f=30):

Cubic B-Spline noise (f=10):

Quadratic B-Spline noise (f=30):

Quadratic B-Spline noise (f=10):

## Unsolved possible bit optimization

One pretty cool notation I made is that only using 3 bits for the randomized value produced almost as good results as using the full 64 bits.

This opens up for possible optimizations. What if we could retrieve all control points in one call?

For the cubic (4x4 patch) we could assign 4 bits to each control point, and make one call to the _n method and mask out all all 16 values. The problem is that we need to get continuous bits from multiple patches.

E.g: consider a 2x2 patch with each cell of 3 "random" bits

1,3,7... 2,6,0 ... 1,1,5 ... 2,3,0 ...

so n(0,0) = 1,3,2,6 (easy peasy, just get patch 0,0 as we do now) but n(1,1) = 6,0,1,5 (not so easy? need to get bits from 4 patches)

We can do this by getting 4 neighbor patches and bitting them together into one 64 bit long (but I have a feeling it will be too cluttery for me and the CPU?). So the question is if can we build this efficiently into the hash function somehow?

I've tried to google this, the closest I get is De Bruinji Torus and Z-curves Although I'm not sure if if they are helpful. If I understand De Bruinji Torus it would be possible to generate a table of those and index it to get "continuous" bits, but we want the randomness in there too... Any ideas?