Cellular Noise is a noise basis which mimics a voronoi diagram. It was first proposed by Steven Worley in his 1996 paper “A Cellular Texture Basis Function” and has been used extensively by the graphics community ever since.
Stefan Gustavson has been doing some great work with optimized GPU Cellular Noise lately at http://webstaff.itn.liu.se/~stegu/GLSL-cellular/. The usual implementation of 2D Cellular Noise searches over 9 jittered points on a 3×3 grid to find the closest point. Stefan has optimized it to work with 4 jittered points on a 2×2 grid. This reduces the work significantly but can create artifacts which show as discontinuities.
I will be using noise in my procedural modeler to create displaced surfaces as well as for solid texturing which mean discontinuities are unacceptable. So I have decided to continue on from Stefan’s work and create an optimized GPU Cellular Noise which is free from discontinuities.
The artifacts in Stefan’s implementation come from the possibility that closest jittered points may exist outside the 2×2 search region ( which is why Worley uses 3×3 ). We can eliminate this by reducing the jitter size ( eg from +-0.5 to +-0.25 ) so there can be no way a closest point can exist outside the 2×2 search region. I did some calculations and found in 2D this distance is +-0.25 and in 3D it is +-0.16666666. The problem with reducing the jitter distance to such a small amount is the noise has very little variation and the grid structure becomes apparent.
To fix this I use a cubic function to push the randomly placed points outwards to the extremes of the jitter window. The result is an acceptable-looking artifact-free GPU Cellular Noise which runs at an acceptable speed. I have uploaded 2D+3D implementations to the GitHub repository. I have left the original functionality proposed by Stefan in as an option in case the artifacts are acceptable for your own use.
My next step with this is to explore one of Stefan’s other ideas. In 2D this is to sample things in a 2.5D manner where the points are jittered over the 2D grid as normal, but also jittered in a 3rd dimension. A 2D slice is then taken through the center of the 3rd dimension to sample the noise. This would add more variance to the 2D noise. The same can be done in 3D. Jittering would still need to be restricted to ensure a continuous signal but variance may be good enough that cubic weighting is not needed.