What is Octahedral Compression of Vertex Arrays?

I'm generating 3d meshes in Godot procedurally. The Mesh class offers:

ARRAY_FLAG_USE_OCTAHEDRAL_COMPRESSION = 2097152 --- Flag used to mark that the array uses an octahedral representation of normal and tangent vectors rather than cartesian.

This flag is set as default when generating a mesh with the ArrayMesh subclass.

The best result I get from google for "octahedral compression" is this shader example, however I don't understand what it does.

Can somebody explain what octahedral compression does and what it's good for?

Solution

What is octahedral representation?

By "octahedral representation" in this context we refer to a way encode normal vector which happens to take less space (in exchange of precision) compared to the usual XYZ encoding. Since it takes less space we can also say it is a kind of (lossy) compression of the vectors.

By XYZ encoding I mean that each vector is represented by three float components XYZ. This is the default.

Thus, the octahedral representation saves memory and memory bandwidth (video memory and vertex memory bandwidth when rendering). In exchange of encoding time (which happens when creating the mesh) and decoding time (which happens when rendering in the GPU), and with some loss of precision. The lose in precision and GPU performance is not as bad as other alternatives (e.g. using spherical coordinates).

How does it work?

The method was published in Survey of Efficient Representations for Independent Unit Vectors back in 2014. it based on Octahedron Environment Maps. That is a way to map an environment texture (so it is al alternative to cube-mapping) based on an octahedron, where the texture is split like this:

As you can see we now have a 2D space (which can be adjusted to the range of the texture UV) where each point corresponds to a point in the surface of an Octahedron, and thus each 2D point corresponds to a direction from the center of the Octahedron. And thus these 2D coordinates are a way to encode directions.

So to encode our normal we interpret it as a point on a unit sphere, then:

Map it to the Octahedron.
Map it to 2D space. I'll get to details below.
If we were doing environment mapping, we would also map the coordinates to UV space.

Map it to the Octahedron

Since we want to preserve the direction what we will do is scale the vector so that it is on the Octahedron.

As you know, the Octahedron is formed a plane on each of the eight quadrants of 3D space. Thus, right away, by making a vector with the absolute values of the components of the input vector, we can work on the first quadrant:

l = vec3(abs(v.x), abs(v.y), abs(v.z))

From line-plane intersection we have that:

d = ((pₒ - lₒ)·n)/(l·n)
p = lₒ + ld

Where lₒ is a point of the line. Which we will place at the origin, leaving us:

p = l * (pₒ·n)/(l·n)

Where n is the normal of the plane… So n = (1, 1, 1) is convenient. And pₒ is a point on the plane… pₒ = (1, 0, 0) is also convenient. Thus:

p = l * 1/(l·n)

Which is the same as:

p = l * 1/((l.x * n.x) + (l.y * n.y) + (l.z * n.z))

And since n = (1, 1, 1) that is the same as:

p = l * 1/(l.x + l.y + l.z)

Ah, but remember we did absolute value because of the symmetry of the Octahedron? We need the sign back:

p = v * 1/(abs(v.x) + abs(v.y) + abs(v.z))

Thus, to go from the Sphere to the Octahedron we divide the vector by the sum of the absolute values of its components.

Map it to 2D space

Then we need to out-fold the normals that have negative z. To clarify: the normals with positive z will be in the center (near the origin), and those with negative z will be in the outer corners. Thus, when the z is positives we can leave the x and y coordinates as they are. But when the z is negative we need to map them to the corresponding corner. Which is like this:

vec2 output = vec2(
    (1.0 - abs(input.x)) * sign(input.x),
    (1.0 - abs(input.y)) * sign(input.y)
);

To understand that, see that the absolute value would fold the numbers in the range [-1, 0] over the range [0, 1] (flipped). Then by doing 1 - x we flip the range [0, 1] so that what was close to 0 is now close to 1 and viceversa. And then we unfold by multiplying by the sign. And since we are doing this to both x and y we are mapping points that are close to the origin to points that are near the corners of our square.

Map to UV space

If we were doing environment mapping, then we would map the coordinates from the range [-1.0, 1.0] to [0.0, 1.0] so we can use them as UV coordinates to query the environment texture map. Which would be input * 0.5 + 0.5.

How does Godot do it?

We can find the functions norm_to_oct in the source code:

// Maps normalized vector to an octahedron projected onto the cartesian plane
// Resulting 2D vector in range [-1, 1]
// See http://jcgt.org/published/0003/02/01/ for details
Vector2 VisualServer::norm_to_oct(const Vector3 v) {
    const float L1Norm = Math::absf(v.x) + Math::absf(v.y) + Math::absf(v.z);

    // NOTE: this will mean it decompresses to 0,0,1
    // Discussed heavily here: https://github.com/godotengine/godot/pull/51268 as to why we did this
    if (Math::is_zero_approx(L1Norm)) {
        WARN_PRINT_ONCE("Octahedral compression cannot be used to compress a zero-length vector, please use normalized normal values or disable octahedral compression");
        return Vector2(0, 0);
    }

    const float invL1Norm = 1.0f / L1Norm;

    Vector2 res;
    if (v.z < 0.0f) {
        res.x = (1.0f - Math::absf(v.y * invL1Norm)) * SGN(v.x);
        res.y = (1.0f - Math::absf(v.x * invL1Norm)) * SGN(v.y);
    } else {
        res.x = v.x * invL1Norm;
        res.y = v.y * invL1Norm;
    }

    return res;
}

Convince yourself this code performs the operations described earlier.

I did dig a bit on the motivation to add this feature to Godot, and as it turns out it is intended to save memory (in particular vertex memory bandwidth) in mobile devices. See Octahedral Normal/Tangent Compression.