Noise generation using lattice based value noise and Bezier curves

Edit on 2023/04/13: The final version, extended to any dimension, is available in this article.

In a previous article I have written about pseudo random numbers generation. These random numbers have equal distribution over their range of possible values: they simulate white noise. This property can be useful, or even necessary, depending on the usage. However, different properties are also desirable for different usages. By analogy with "white" noise, there exists also "colored" noises with particular, varying, distribution over the range of possible values. They also have their usefulness, but they still miss one particular property: they are not coherent, the value of one sample doesn't depend on the value of the others.

In procedural generation and computer graphics, coherent noises are generally desirable as they allow to simulate random but continuous variables. Based on the previous incoherent noises, it is possible to generate coherent ones. They are called procedural coherent noises and divided into point based and lattice based, the latter being subdivided into gradient and value noises. Examples of procedural coherent noises are: Worley noise, Perlin noise, simplex noise, open simplex noise, better gradient noise, etc. I wouldn't be myself if I hadn't tried to make my own, which is the subject of this article.

The constraint on the noise I wanted to create was: continuous and differentiable, tilable, simple to implement, quick to compute, visually different from other noises, function of \(\mathbb{R}^2\rightarrow[0,1]\). I started with bilinear interpolation over a 2D array with a pseudo-random number affected at each cell corner. This is basic lattice based value noise, whose non differenciability can be solved by using Perlin's smootherstep function. It is nicely explained on scratchapixel's website. Tiling can be solved by forcing values at one edge of the grid to be equal to values on the opposite edge.

The image above shows one example (without forced coefficients for tiling). It efficiently produces smooth noise, but it is strongly biased toward the underlying grid pattern which give it an unsatisfying "blocky" look.

That look arises from the input coordinates being directly used for the bilinear interpolation: the result of interpolation has a null gradient (due to the smootherstep function) along the border of the cells of the grid, and the direct mapping of inputs does nothing to hide this regularity. I thought a different mapping of input coordinates to grid coordinates should be able to solve the problem, and came up with the idea of using Bezier splines to create paths inside the noise obtained previously, and sample the values along that path.

One spline gives a function of \(\mathbb{R}\) to \(\mathbb{R}\), and we need a function of an input \((x,y)\) (modulo the dimensions of the grid) to a position in the grid \((x_{grid},y_{grid})\). Two splines seem then sufficient: \(\mathcal{C}_x(x)=x_{grid}\) and \(\mathcal{C}_y(y)=y_{grid}\), however it isn't. For a given input value \(x'\) such as \(\nabla G(\mathcal{C}_x(x'),\cdot)=0\) (where \(G(x,y)\) is the noise value in the grid at \((x,y)\)), that gradient is null for any value of \(y\). We have simply scaled/translated the blocks in the result noise.

What we actually need is each of \((x_{grid},y_{grid})\) to depends on both \(x\) and \(y\): \(F(\mathcal{C}_{xx}(x),\mathcal{C}_{xy}(y))=x_{grid}\) and \(F(\mathcal{C}_{yx}(x),\mathcal{C}_{yy}(y))=y_{grid}\). What is \(F\) ? Well almost anything will do, but it must be differentiable (else the result noise won't be anymore). I've tried several functions an in the end nothing gave better results than a simple \(F(x,y)=(x+y)/2\).

Now what about the four splines \(\mathcal{C}\) ? They must be functions of \([0,n]\) to \([0,s]\) where \(n\) is the number of segment in the spline, and \(s\) is the size (in number of cells along one axis) of the grid (assumed to be square for convenience). It means their control values will be chosen randomly in \([0,s]\). For tilable property, we want the spline to draw a loop in the grid such as when mapping the input from \(\mathbb{R}\) to \([0,n]\) we loop on the sampled values in a continuous and differentiable manner. This imposes constraints on the first and last anchors (must be equal for continuity) and all the handles (must be colinears together and with their respective anchor for differentiability). Note also that handles must be non equal to their respective anchor, or we loose differentiability.

I first considered using only one Bezier curve and raise its order as necessary. However this results in two problems: the higher the order the more expensive it is to compute, and the higher the order the more weight anchors have relatively to handles which create artefacts (higher frequency at the edge of the tile). Using a spline of cubic curves avoid these problems. To make things simpler I correlate the number of segment with the grid dimension, which makes sense as they both control the turbulence of the resulting noise: \(n=s=d+1\) where \(d\ge1\) is what I'll call the "order" of the noise. While we are at naming things, I'll call this noise generator "B-Noise" as the key point is to use Bezier splines on a standard value noise.

Everything being defined I can now implement it, first in pseudo-code. (Note that and extra segment, copy of the first one, is added to the spline to simplify the code of the BNoiseGet function).

What about my initial constraints? Continuous and differentiable, yes, it is a composition of differentiable functions. Tilable, yes, thanks to the constraint on the curves. Simple to implement, I guess no one will dare to say that the pseudo-code above looks scary. Function of \(\mathbb{R}^2\rightarrow[0,1]\), yes. Easy to compute ? It boils down to evaluate four cubic bezier curves, average twice two values, smooth two values, and perform one bilinear interpolation. Per se it doesn't look very expensive. Comparing to Perlin's noise in number of elementary instructions for a more objective estimation, I've counted 61 instructions for Perlin and 118 for B-Noise. So, it should be expected to be around twice slower than Perlin's noise.

Last point, how does it look like? The examples above will give you an idea.

The blocky pattern has clearly disappeared but we can still feel directional bias toward horizontal and vertical directions. I tried to get rid of it but couldn't and finally accepted it as it is. The bias isn't obvious neither, and this noise looks to me original enough to be useful, probably.

An article about 2D noise generation wouldn't be complete without some mountain landscapes, right ? Here are some, using B-Noise based fractal noise:

And finally, the implementation in C. Header file:

Body:

Can be used as follow:

Download the source here. Any question or comment is welcome by email.

Edit on 2023/03/17: I've added an implementation in Javascript too. It's available for download here, and an interactive demo is available here.

Edit on 2023/04/02: I have improved the algorithm introduced in this article to remove the directional bias. Check the new version in this article.

2023-03-16

in All, C programming, Computer graphics,

388 views

I'm open for work ! Check my profile and email me.

You've liked this article ? Please consider supporting me:

in All, C programming, Computer graphics,

388 views

I'm open for work ! Check my profile and email me.

You've liked this article ? Please consider supporting me: