Worley Cellular Noise Nearest-Feature Distance in GLSL

This article details the mathematical procedure for computing Worley cellular noise nearest-feature distances (\(F_1\)) within OpenGL Shading Language (GLSL). Cellular noise divides continuous space into a regular discrete grid, populates each grid cell with one or more pseudo-random feature points, and calculates the minimum distance from an input coordinate to the closest feature point. The following sections outline the coordinate partitioning, pseudo-random point distribution, neighborhood evaluation, distance metric computation, and the corresponding GLSL implementation.

1. Domain Partitioning

The evaluation starts by decomposing any input coordinate vector \(\mathbf{p} \in \mathbb{R}^n\) into an integer lattice coordinate \(\mathbf{i}\) and a fractional offset \(\mathbf{f}\):

\[\mathbf{i} = \lfloor \mathbf{p} \rfloor\] \[\mathbf{f} = \mathbf{p} - \mathbf{i} = \operatorname{fract}(\mathbf{p})\]

In GLSL, this corresponds to the built-in functions floor(p) and fract(p). The vector \(\mathbf{i}\) identifies the specific cell containing the sample point, while \(\mathbf{f} \in [0, 1)^n\) represents the position of the evaluation point relative to the cell's local origin.

2. Feature Point Generation via Deterministic Hashing

To avoid storing explicit geometry in GPU memory, feature points are generated procedurally on the fly using a deterministic pseudo-random hash function \(H(\mathbf{g}): \mathbb{Z}^n \to [0, 1)^n\).

For any integer lattice coordinate \(\mathbf{g}\), the feature point \(\mathbf{P}_{\mathbf{g}}\) inside that cell (in local coordinates relative to the integer lattice origin \(\mathbf{i}\)) is defined as:

\[\mathbf{P}_{\mathbf{g}} = \mathbf{g} - \mathbf{i} + H(\mathbf{g})\]

Letting \(\mathbf{u} = \mathbf{g} - \mathbf{i}\) represent the relative neighbor cell offset, the local coordinate of the feature point relative to the sample point's cell origin becomes:

\[\mathbf{p}_{\text{local}} = \mathbf{u} + H(\mathbf{i} + \mathbf{u})\]

3. Neighbor Traversal

Because a feature point in an adjacent cell may be closer to \(\mathbf{p}\) than the point in cell \(\mathbf{i}\), the algorithm must query neighboring cells. For an \(n\)-dimensional domain, a neighborhood with offset \(\mathbf{u}\) spanning each dimension \(k \in \{1, \dots, n\}\) is evaluated:

\[\mathbf{u} \in \{-1, 0, 1\}^n\]

In 2D, this evaluates \(3^2 = 9\) surrounding cells (\(\Delta x, \Delta y \in \{-1, 0, 1\}\)).
In 3D, this evaluates \(3^3 = 27\) surrounding cells (\(\Delta x, \Delta y, \Delta z \in \{-1, 0, 1\}\)).

Searching beyond immediate neighbors is mathematically unnecessary under the standard assumption of one feature point per unit cell and a maximum displacement within \([0, 1)^n\), as no point outside this boundary can be closer than the points inside the \(3^n\) cluster.

4. Distance Calculation and Minimization

For each neighbor cell offset \(\mathbf{u}\), the displacement vector \(\mathbf{v}_{\mathbf{u}}\) from the evaluation point \(\mathbf{f}\) to the generated feature point is:

\[\mathbf{v}_{\mathbf{u}} = \mathbf{u} + H(\mathbf{i} + \mathbf{u}) - \mathbf{f}\]

The Euclidean distance \(d_{\mathbf{u}}\) to the feature point is the \(\ell_2\)-norm:

\[d_{\mathbf{u}} = \|\mathbf{v}_{\mathbf{u}}\|_2 = \sqrt{\mathbf{v}_{\mathbf{u}} \cdot \mathbf{v}_{\mathbf{u}}}\]

To optimize shader instruction cycles, the squared distance \(d_{\mathbf{u}}^2 = \mathbf{v}_{\mathbf{u}} \cdot \mathbf{v}_{\mathbf{u}}\) is tracked during loop traversal to eliminate redundant square root operations. The nearest-feature distance \(F_1\) is the minimum value over the neighborhood:

\[F_1(\mathbf{p}) = \sqrt{\min_{\mathbf{u} \in \{-1, 0, 1\}^n} (\mathbf{v}_{\mathbf{u}} \cdot \mathbf{v}_{\mathbf{u}})}\]

Other distance metrics, such as Manhattan (\(\ell_1\)) or Chebyshev (\(\ell_\infty\)), can be used by substituting the norm calculation:

Manhattan: \(d_{\mathbf{u}} = \sum_{k=1}^n |v_{\mathbf{u}, k}|\)
Chebyshev: \(d_{\mathbf{u}} = \max_{k=1}^n |v_{\mathbf{u}, k}|\)

5. GLSL Implementation (2D Example)

The following GLSL function computes the normalized \(F_1\) nearest-feature distance for a two-dimensional input coordinate:

// Deterministic 2D hash returning values in [0, 1)
vec2 hash2D(vec2 p) {
    p = vec2(dot(p, vec2(127.1, 311.7)),
             dot(p, vec2(269.5, 183.3)));
    return fract(sin(p) * 43758.5453123);
}

// Computes the nearest Worley distance F1
float worley2D(vec2 p) {
    vec2 i = floor(p);
    vec2 f = fract(p);

    float min_dist_sq = 8.0; // Arbitrary value greater than maximum possible distance squared

    // Iterate through the 3x3 local neighborhood
    for (int y = -1; y <= 1; y++) {
        for (int x = -1; x <= 1; x++) {
            vec2 u = vec2(float(x), float(y));
            vec2 point = hash2D(i + u);
            
            // Vector from evaluation point to the pseudo-random feature point
            vec2 diff = u + point - f;
            
            // Squared Euclidean distance
            float dist_sq = dot(diff, diff);
            
            min_dist_sq = min(min_dist_sq, dist_sq);
        }
    }

    return sqrt(min_dist_sq);
}

The returned scalar represents the distance to the nearest feature center, producing zero at cell centers and scaling linearly toward the Voronoi cell boundaries.