voronoi
2024-09-30 00:02:18

intro

  • Two of the most common building blocks for procedural pattern generation are Noise, which have many variations (Perlin’s being the first and most relevant), and Voronoi (also known as “celular”) which also has different variations. For Voronoi, the most common of those variations is the one that splits the domain in a regular grid such that there’s one feature point in each of the cells. That means that Voronoi patterns are based on a grid after all just like Noise, the difference being that while in Noise the feature originators are in the vertices of the grid (random values or random gradients), Voronoi has the feature generators jittered somewhere in the grid. That might be a first indicator that, perhaps, the two patterns are not that unrelated, at least from an implementation perspective?

  • Despite this similarity, the fact is that the way the grid is used in both patterns is different. Noise interpolates/averages random values (as in value noise) or gradients (as in gradient noise), while Voronoi computes the distance to the closest feature point. Now, smooth-bilinear interpolation and minimum evaluation are two very different operations, or… are they? Can they perhaps be combined in a more general metric? If that was so, then both Noise and Voronoi patterns could be seen as particular cases of a more general grid-based pattern genereator?

  • This article is about a small effort to find such generalized pattern. Of course, the code implementing such generalization will never be as fast as implementations of the particular cases (rendering this articles with no obvious immediate practical purpose), but at least it might open the window to a bigger picture understanding and perhaps, one day, new findings!

翻译

程序化图案生成的两个最常见的构建块是噪声（Noise），它有许多变体（其中Perlin噪声是第一个也是最相关的），以及Voronoi（也称为“细胞”），它也有不同的变体。对于Voronoi，最常见的变体是将域分割成规则网格，使得每个单元格中有一个特征点。这意味着Voronoi图案最终是基于网格的，就像噪声一样，不同之处在于，在噪声中，特征的起源是在网格的顶点（随机值或随机梯度），而Voronoi则将特征生成器在网格中抖动。这可能是一个初步的指示，表明这两种图案从实现的角度来看，或许并不是那么不相关？

尽管有这种相似性，但事实上，这两种图案中网格的使用方式是不同的。噪声通过插值/平均随机值（如值噪声）或梯度（如梯度噪声），而Voronoi计算到最近特征点的距离。现在，平滑双线性插值和最小值评估是两种非常不同的操作，或者…它们是吗？它们是否可能被组合成一个更一般的度量？如果是这样，那么噪声和Voronoi图案都可以被看作是一个更一般的基于网格的图案生成器的特例？

本文是关于寻找这种一般化图案的一次小尝试。当然，实现这种概括的代码永远不会像特定情况的实现那样快（这使得本文没有明显的直接实际用途），但至少它可能打开一个更广泛理解的窗口，也许有一天，会有新的发现！

The code

  • In order to generalize Voronoi and Noise, we must introduced two parameters: one to control the amount of jittering of the feature points, and one for controling the metric. Let’s call the grid control parameter u, and the metric controler v.

  • The grid parameter is pretty simple to design: u=0 will simply use a Noise-like regular grid, and u=1 will be the Voronoi-like jittered grid. So, the value of u can simply control the amount of jitter. Straightforward.

  • The v parameters will have to blend between a Noise-like bilinear interpolator of values, and a Voronoi-like min operator. The main difficulty here is that the min() operation is a non-continuous function. However, luckily enough for us, there are smooth alternatives such as the Smooth Voronoi . If we apply a power functions to the distance to each feature points in order to highlight the closest one over the rest, then we get a nice side effect: using a power of 1 gives all features the same relevance and therefore we get an equal interpolation of features, which is what we need for Noise-like patterns! So, something like this might do it:

翻译

为了将Voronoi和噪声（Noise）泛化，我们必须引入两个参数：一个用于控制特征点的抖动量，另一个用于控制度量标准。让我们将网格控制参数称为u，度量控制参数称为v。

网格参数的设计相当简单：u=0将简单地使用类似噪声的规则网格，而u=1将是类似Voronoi的抖动网格。因此，u的值可以简单地控制抖动量。这是直接的。

v参数将需要在类似噪声的双线性插值器的值和类似Voronoi的最小操作符之间进行混合。这里的主要困难是min()操作是一个不连续的函数。然而，幸运的是，我们有平滑的替代方案，例如平滑Voronoi。如果我们对每个特征点的距离应用幂函数以突出最近的一个，那么我们会得到一个不错的副作用：使用1的幂将使所有特征具有相同的相关性，因此我们得到了特征的等同插值，这正是我们需要的类似噪声的图案！所以，类似这样的东西可能会奏效：

  1. 首先，定义一个基础的双线性插值函数，用于在网格顶点之间进行平滑的值插值。
  2. 然后，定义一个距离度量函数，用于计算每个特征点到当前评估点的距离。
  3. 接着，应用幂函数到距离度量上，这可以通过$ d_i^v $来表示，其中$ d_i $是距离，v是控制度量的参数。
  4. 最后，将这些加权距离与原始的双线性插值值结合起来，以形成最终的泛化图案。这可以通过某种形式的加权平均来实现，例如：

$$ P(x, y) = \sum_{i=1}^{n} w_i \cdot V_i(x, y) $$

其中，$ P(x, y) $是最终图案在点(x, y)的值，$ V_i(x, y) $是双线性插值函数在网格顶点i的值，$ w_i $是权重，可以根据$ d_i^v $来计算，以确保最近的点具有更大的权重。

通过这种方式，当u接近0时，我们得到一个更接近噪声的图案，而当u接近1时，我们得到一个更接近Voronoi的图案。同样，当v接近1时，我们得到一个等同插值的噪声模式，而v的增加将使模式更接近Voronoi模式。通过调整这些参数，我们可以探索噪声和Voronoi之间的连续过渡，从而可能发现新的图案生成技术。

1
float ww = pow( 1.0-smoothstep(0.0,1.414,sqrt(d)), 64.0 - 63.0*v );
  • However, a bit of experimentation proves that a better perceptually linear interpolation between the Noise-like and the Voronoi-like pattern can be achieved by rising v to some power:
1
float ww = pow( 1.0-smoothstep(0.0,1.414,sqrt(d)), 1.0 + 63.0*pow(1.0-v,4.0) );
  • So, it seems that after all it’s not so difficult to generalize Noise and Vonoroi. Therefore, assuming one has a way to generate random values deterministically as a function of the grid cell id (which you are already doing both in your favourite Voronoi and Noise implementations), which we could call
1
vec3 hash3( in vec2 p )
  • then the code for our new generalized super pattern could be like this:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
float noise( in vec2 x, float u, float v )
{
    vec2 p = floor(x);
    vec2 f = fract(x);

    float k = 1.0 + 63.0*pow(1.0-v,4.0);
    float va = 0.0;
    float wt = 0.0;
    for( int j=-2; j<=2; j++ )
    for( int i=-2; i<=2; i++ )
    {
        vec2  g = vec2( float(i), float(j) );
        vec3  o = hash3( p + g )*vec3(u,u,1.0);
        vec2  r = g - f + o.xy;
        float d = dot(r,r);
        float w = pow( 1.0-smoothstep(0.0,1.414,sqrt(d)), k );
        va += w*o.z;
        wt += w;
    }

    return va/wt;
}
  • The implementation is very similar to the regular Voronoi pattern, the difference being that we now have the weighted average of distance computations happening (the accumulation happens in wa and the counting for later normalization is in wt.

Results

  • The results of the generalization are rather interesting. Of course, we have generalized Noise and Voronoi. Indeed, noise happens when u=0, v=1, ie, regular grid and interpolation of feature distances. Voronoi happens when u=1, v=0, ie, when the grid is jittered and the metric is the minimum distance.

  • However there’s two side effects. The first happens when u=0, v=0, which gives a minimun distance to a non jittered grid of features. This basically gives a patten with a constant value per grid cell, or what normally is called “cell noise”.

  • The second side effect happens for u=1, v=1, which generates a pattern that has an interpolated value of distances to features in a jittered grid. It’s a combination of Voronoi and Noise, or as I am naming it, Voronoise (top right in the image). This pattern can be useful for regular procedural generation where grid artifacts are visible, because the jittering certainly hides the underlaying grid structure of Noise.


Botton Left: u=0, v=0: Cell Noise
Botton Right: u=0, v=1: Noise
Top Left: u=1, v=0: Voronoi
Top Right: u=1, v=1: Voronoise

  • A realtime interactive implementation of the code above can be found here (click in the title to navigate to the source code, or simply move the mouse along the image to vary the u and v parameters.
Prev
Next