Meshlet compression

Triangle Strips

In real-time graphics, a mesh usually consists of triangles. Each triangle consists of three indices to vertex attributes. An index buffer

V=\left[V_0, V_1, V_2, V_3, V_4, V_5, V_6, V_7, V_8 \dots\right]

represents the connectivity of a triangle mesh.
Commonly, a GPU interprets V as a *triangle list*, where triples of indices in V form the triangles:

\left(V_0, V_1, V_2\right), \left(V_3, V_4, V_5\right), \left(V_6, V_7, V_8\right) \dots

Or here in a concrete example:

However, with three indices per triangle, their storage requirement is relatively high.

A less memory intense way to interpret V are triangle strips, where a triangle reuses an edge of the preceding triangle:

\begin{array}{llll} \left(V_0, V_1, V_2\right), & \left(V_3, V_2, V_1\right), & \left(V_2, V_3, V_4\right), & \left(V_5, V_4, V_3\right),\\ \left(V_4, V_5, V_6\right), & \left(V_7, V_6, V_5\right), & \left(V_6, V_7, V_8\right), & \dots \end{array}

Note that we inverted the vertex order in every second triangle to keep the winding order intact.
Now, each triangle in the strip requires only one new index, except for the first one.
Thus, using strips results in a 3:1 compression ratio.

Triangle strips describe a path over the triangles of a mesh. The previous example was of an alternating triangle strip, where the strip alternates between reusing the right and the left edge of the previous triangle. As this is not very flexible, we can introduce another bit flag per triangle that encodes which edge is reused, which we call the L/R flag. This is called a generalized triangle strip or GTS and is what we use for our meshlets. Our previous example encoded as a GTS could look like this:

Note that we also ordered the vertices of the meshlet, so that they appear in incrementing order in the strip. As this way, the first indices \left(0, 1, 2\right) are mandatory, we don’t need to store them.

To entirely represent a mesh, or in our case a meshlet, multiple strips are typically required. To describe multiple strips as a single one, we need a way to encode a strip restart. This can either be done by adding another restart bit per triangle, or by intentionally adding degenerate triangles to the strip.

A degenerate triangle has two or more identical vertex indices, thus its area is zero. As they will not change the result of the rendered image, the rasterizer of a GPU can just ignore them. For example, the index buffer for an alternating strip

\left[V_0, V_1, V_2, V_3, \textcolor{red}{V_3}, \textcolor{red}{V_4}, V_4, V_5, V_6\right]

with the duplicated vertices \textcolor{red}{V_3}, \textcolor{red}{V_4} produces four degenerate triangles:

\begin{array}{llll} \left(V_0, V_1, V_2\right), & \left(V_3, V_2, V_1\right), & \left(V_2, V_3, \textcolor{red}{V_3}\right), & \left(\textcolor{red}{V_4}, \textcolor{red}{V_3}, V_3\right),\\ \left(\textcolor{red}{V_3}, \textcolor{red}{V_4}, V_4\right), &\left(V_5, V_4, \textcolor{red}{V_4}\right), & \left(V_4, V_5, V_6\right). \end{array}

As you can see, we successfully ended a strip on a triangle \left(V_3, V_2, V_1\right) and started a new one with triangle \left(V_4, V_5, V_6\right). Using degenerate triangles instead of bit flags comes with the benefit that no additional logic is required in the decompression stage. The rasterizer will just ignore all degenerate triangles.

When encoding a meshlet in a GTS, the number of triangles grows when requiring a restart. Thus, in very rare cases, the number of triangles can exceed the 256 limit. In such a case, we choose to split the meshlet in two.

Finding good strips through a meshlet that only require a low number of restarts is a non-trivial problem. For a good tradeoff between run-time performance and quality, we recommend to use the enhanced tunneling algorithm. In our paper “Towards Practical Meshlet Decompression”, we describe an optimal algorithm, but that takes some time to compute.

Strip decoding

As established in the previous section, a L/R flag per triangle marks which edge of the previous triangle is reused. As all triangles are decompressed in parallel, a thread cannot access the decompressed previous triangle. Instead, each individual thread must find the correct indices from earlier in the strip. See the next figure for reference: the longer the strip spins around vertex in a fan-like manner, the further back the required index lies.

To find out how far exactly we have to go back in the strip, we count (starting with 1) how many steps we have to go back in the L/R bit mask until a change of flag occurs. In our example, triangle 7 requires the index of triangle 4, which is 0. To do this search in linear time, we can use the bit operation firstbithigh (or firstbitlow) in hlsl or findMSB (or findLSB) in glsl. Note that the bit mask has to be shifted and inverted accordingly.

This can be implemented in hlsl like the following:

uint LoadTriangleFanOffset(in int triangleIndex, in bool triangleFlag)
{
    uint lastFlags;
    int fanOffset = 1;    
    do
    {
        // Load last 32 L/R-flags
        lastFlags = LoadLast32TriangleFlags(triangleIndex);
        // Flip L/R-flags, such that
        //  0 = same L/R flag
        //  1 = different L/R flags, i.e. end of triangle fan
        lastFlags = triangleFlag ? ~lastFlags : lastFlags;
        // 31 - firstbithigh counts leading 0 bits, i.e. length of triangle fan
        fanOffset += 31 - firstbithigh(lastFlags);
        // Move to next 32 L/R flags
        triangleIndex -= 32;
    }
    // Continue util
    // - lastFlags contains different L/R flag (end of triangle fan)
    // - start of triangle strip was reached (triangleIndex < 0)
    while ((lastFlags == 0) && (triangleIndex >= 0));
    
    return fanOffset;
}

We have to use a loop here, because a fan-like configuration could be longer than 32 triangles. In most cases, this loop will only run once. In the worst case, the whole strip is actually a fan, so the loop will run 256/32 = 8 times (256, because it is the maximum amount of triangles a mesh shader can output and 32, because we store one bit per triangle in a 32-bit dword). Inside the loop, we load the L/R bits in a way that the most significant bit is the flag of the current triangle, the second most significant bit is the form the previous triangle, and so on:

// 256/32 = 8 dwords for flags and 256 / 4 = 64 dwords for 8 bit indices
groupshared uint IndexBufferCache[8 + 64];

uint LoadLast32TriangleFlags(in int triangleIndex)
{
    // Index of DWORD which contains L/R flag for triangleIndex
    int dwordIndex = triangleIndex / 32;
    // Bit index of L/R flag in DWORD
    int bitIndex   = triangleIndex % 32;
    
    // Shift triangle L/R flags such that lastFlags only contains flag prior to triangleIndex
    uint lastFlags = IndexBufferCache[dwordIndex] << (31 - bitIndex);

    if (dwordIndex != 0 && bitIndex != 31)
    {
        // Fill remaining bits with previous L/R flag DWORD
        lastFlags |= IndexBufferCache[dwordIndex - 1] >> (bitIndex + 1);
    }
    
    return lastFlags;
}

As you can see here, we do something we recommended in the previous posts of this series: make use of the group shared memory. In detail, instead of every thread having its own copy of the whole compressed strip, or loading that data from global memory multiple times, we load the data once and cache it in group shared memory. This improves run-time performance.

Finally, the whole triangle is loaded like this:

uint3 LoadTriangle(in int triangleIndex)
{
    // Triangle strip L/R flag for current triangle
    const bool triangleFlag = LoadTriangleFlag(triangleIndex);
    
    // Offset in triangle fan
    const uint triangleFanOffset = LoadTriangleFanOffset(triangleIndex, triangleFlag);
    
    // New vertex index
    uint i = LoadTriangleIndex(triangleIndex);
    // Previous vertex index
    uint p = LoadTriangleIndex(triangleIndex - 1);
    // Triangle fan offset vertex index
    uint o = LoadTriangleIndex(triangleIndex - triangleFanOffset);
    
    // Left triangle
    // i ----- p
    //  \  t  / \
    //   \   /   \
    //    \ / t-1 \
    //     o ----- *
    // 
    // Right triangle
    //     p ----- i
    //    / \  t  /
    //   /   \   /
    //  / t-1 \ /
    // *------ o
    
    return triangleFlag ?
        // Right triangle
        uint3(p, o, i) :
        // Left triangle
        uint3(o, p, i);
}

Reuse Packing

As you might have noticed by now, many indices in our strip are just increments of the previous index. To make use of this redundancy, we can extend our codec with a concept we call reuse packing. Instead of storing the actual indices, we just store wether an index is incremented (1) or a reused index (0). We call this the inc-flag buffer. An additional index buffer, called the reuse buffer, only stores all reused indices. If a thread unpacks the t-th triangle with a 1 as an increment flag, the resulting index is just the sum of all preceding inc-flags s. Otherwise, if the inc-flag is 0, the reuse buffer is accessed at location t+1-s:

To perform the add scan over the inc-flags, we can again make use of a bit instruction called countbits or bitcount.

As this will only give use the sum of all flags of a 32-bit word, we again make use of the group shared memory to precompute and cache the result of the prefix sum at the beginning of each 32-bit word:

groupshared uint IncrementPrefixCache[7];

uint LoadTriangleIncrementPrefix(in int triangleIndex)
{
    // Index of DWORD which contains L/R flag for triangleIndex
    const uint dwordIndex = triangleIndex / 32;
    // Bit index of L/R flag in DWORD
    const uint bitIndex   = triangleIndex % 32;
    
    // Count active bits (i.e. increments) in all prior triangles
    const uint prefix = countbits(
        IndexBufferCache[TRIANGLE_INCREMENT_FLAG_OFFSET + dwordIndex] << (31 - bitIndex));
    
    if (dwordIndex >= 1)
    {
        // IncrementPrefixCache stores prefix sum of all prior DWORDs
        return 2 + prefix + IncrementPrefixCache[dwordIndex - 1];
    }
    else
    {
        return 2 + prefix;
    }
}

An index is then loaded like the following:

uint LoadTriangleIndex(in int triangleIndex)
{
    if (triangleIndex <= 0)
    {
        return max(triangleIndex + 2, 0);
    }
    else
    {
        const bool increment = LoadTriangleIncrementFlag(triangleIndex);
        const uint prefix    = LoadTriangleIncrementPrefix(triangleIndex);
        
        if (increment)
        {
            return prefix;
        }
        else
        {
            const uint index = triangleIndex + 1 - prefix;
            
            const uint dwordIndex = index / 4;
            const uint byteIndex  = index % 4;

            const uint value = IndexBufferCache[TRIANGLE_INDEX_OFFSET + dwordIndex];

            // Extract 8 bit vertex index
            return (value >> (byteIndex * 8)) & 0xFF;
        }
    }
}

This concludes the index buffer compression. In the next section we discuss attribute compression.

Adding the Amplification Shader

When we add an amplification shader to our pipeline, DispatchMesh changes from launching mesh shader thread groups to launching amplification shader thread groups. In the following code example, we load the culling information relevant to the current meshlet and compute wether the meshlet is visible. Note how we use WavePrefixCountBits to assign new indices to visible meshlets in the thread group. After that WaveActiveCountBits returns the total number of visible meshlets in the group, required for calling DispatchMesh. In our custom payload we specify the instance and meshlet id to be used in the mesh shader.

struct Payload {
    uint2 meshletData[32];
};

groupshared Payload payload;

[NumThreads(32, 1, 1)]
void AmplificationShader(uint2 dtid : SV_DispatchThreadID)
{
    // Amplification is dispatched with DispatchMesh((meshletCount + 31) / 32, instanceCount, 1);
    const uint meshletId = dtid.x;
    const uint instance  = dtid.y;
    
    bool visible = false;
    
    if (instance < RootConst.instanceCount)
    {
        visible = IsMeshletVisible(Meshlets[meshletId], instance);
    }
    
    if (visible)
    {
        const uint index = WavePrefixCountBits(visible);
        payload.meshletData[index] = uint2(meshletId, instance);
    }
    
    const uint meshletCount = WaveActiveCountBits(visible);
    DispatchMesh(meshletCount, 1, 1, payload);
}

Frustum Culling

Frustum culling operates by creating a bounding volume around each meshlet – a simple shape that completely encloses the meshlet’s geometry. The meshlet’s bounding volume is then tested against the six planes that define the camera’s view frustum. If the bounding volume does not intersect with the frustum, the meshlet is considered outside the camera’s view and is culled, meaning it is not sent to the mesh shader.

Cone Culling

Similar to hardware-accelerated back-face culling on a triangle by triangle level, it can be checked if all triangles of a meshlet face away from the camera. To achieve this, a bounding volume is necessary that encompasses all the normals of the faces within a meshlet. A practical choice for this volume is a cone, defined by a central normal vector and an opening angle. This cone represents the range of directions that the meshlet’s faces can be oriented in. While approximating this cone should work fine in most cases, finding the optimal cone is the same problem as the finding the smallest circle around a set of points.