3D Simplex Noise: Skewing and Grid Traversal in GLSL

This article provides an overview of how 3D Simplex noise transforms continuous 3D space into a computationally efficient tetrahedral grid. It details the coordinate skewing formulas used to map Cartesian coordinates to a skewed simplicial lattice, the branchless GLSL techniques used to identify the enclosing simplex cell, and how unskewing yields the exact displacement vectors necessary to evaluate noise contributions at runtime.

The Purpose of Coordinate Skewing

Standard 3D Perlin noise samples values on a hypercube grid, requiring evaluation at \(2^3 = 8\) surrounding vertices. Simplex noise optimizes this by partitioning \(\mathbb{R}^3\) into simplices—the simplest geometric figures in that dimension. In 3D, a simplex is a tetrahedron, requiring evaluation at only \(3 + 1 = 4\) vertices.

Because regular tetrahedra do not naturally tile Euclidean space along orthogonal axes, the coordinate space is sheared (skewed) along the main diagonal so that a cubic lattice splits neatly into congruent tetrahedra.

The Skew Transformation in GLSL

The transformation from Cartesian coordinates \((x, y, z)\) to skewed simplex grid coordinates \((x', y', z')\) relies on a dimension-dependent skew factor, \(F_3\):

\[F_3 = \frac{1}{3}\]

To find the base coordinate of the containing cell in the skewed grid, you compute a common displacement factor derived from the sum of the input coordinates:

const float F3 = 1.0 / 3.0;
float s = (p.x + p.y + p.z) * F3;
vec3 i = floor(p + s);

Here, i represents the integer lattice coordinate of the base corner of the skewed unit cube enclosing the sample point p.

The Unskew Transformation

To calculate distances from the sample point to the cell vertices, coordinates must be transformed back to Euclidean space. The unskew factor, \(G_3\), scales the integer grid coordinate:

\[G_3 = \frac{F_3}{1.0 + 3.0 \cdot F_3} = \frac{1/3}{2} = \frac{1}{6}\]

The base vertex unskews back to Cartesian space via:

const float G3 = 1.0 / 6.0;
float t = (i.x + i.y + i.z) * G3;
vec3 p0 = i - t;
vec3 v0 = p - p0; // Distance vector from the first vertex to the input point

v0 serves as the relative Cartesian displacement from the origin of the simplex.

Simplex Grid Traversal in GLSL

A skewed unit cube consists of six distinct tetrahedra meeting along the main diagonal from \((0, 0, 0)\) to \((1, 1, 1)\). Traversal requires determining which of these six tetrahedra contains the point v0.

The path taken through the grid edges depends on the descending magnitude of the components of v0 (\(x\), \(y\), and \(z\)):

  • The first vertex is always the cell origin: \((0, 0, 0)\).
  • The second vertex advances by 1 along the axis of the largest component.
  • The third vertex advances by 1 along the axes of both the largest and second-largest components.
  • The fourth vertex is always the opposite corner: \((1, 1, 1)\).

Modern GLSL implementations avoid conditional branching (if/else) by using step functions to determine the step vectors i1 and i2:

// Compare components to determine the relative order
vec3 s_step = step(v0.yzx, v0.xyz);
vec3 s_inv  = 1.0 - s_step;

// Derive the intermediate offsets
vec3 i1 = s_step * s_inv.zxy;
vec3 i2 = 1.0 - s_inv * s_step.zxy;

i1 and i2 represent the relative integer offsets to the second and third vertices inside the skewed grid cell.

Computing Remaining Vertex Offsets

Once the internal traversal paths are established, the remaining three vertices are transformed back to Cartesian space by subtracting the relative steps and applying the \(G_3\) unskew factor:

vec3 v1 = v0 - i1 + 1.0 * G3;
vec3 v2 = v0 - i2 + 2.0 * G3;
vec3 v3 = v0 - 1.0 + 3.0 * G3;

With v0, v1, v2, and v3 computed, the shader has the four relative distance vectors needed to compute radially symmetric kernel weights and gradient dot products, completing the core sampling stage of 3D Simplex noise.