ClusterCull.compute

// M3a proved out writing Unity's indirect-draw-args buffer from a compute shader, in isolation
// from any cluster-selection logic. M3b moved root-only selection onto the GPU (no accept/expand -
// always the coarsest LOD). M3c added a real accept/expand test but only one level deep from each
// root (a failed root's children were selected unconditionally, without being tested in turn).
//
// M3d (this step) replaces M3c with a fully recursive top-down traversal that matches
// ClusterLODManager.SelectClusters exactly: starting from the roots, each node is tested, and if
// it fails, its children are queued for testing in the *next* pass - repeated pass after pass until
// every live node has either been selected or bottomed out at a true leaf. Since the fan-out at
// each node is data/camera-dependent (unlike M3c, which sized everything up front from
// camera-independent worst cases), this needs a real atomic-append mechanism instead of fixed
// per-root output slots, and a way to keep dispatching without a CPU readback between passes.
//
// The approach: two ping-pong "frontier" buffers holding this pass's/next pass's node indices, a
// small counters buffer ([0]=current frontier count, [1]=next frontier count being accumulated via
// InterlockedAdd, [2]=cumulative selected count, [3]=overflow count - see below), and a tiny
// Advance kernel that runs between passes to promote next->current, reset next to zero, and write
// GPU-computed thread-group counts into a dispatch-args buffer that the *next* TraverseLevel call
// consumes via ComputeShader.DispatchIndirect - so the number of passes needed is the only thing
// decided on the CPU (a heuristic upper bound based on the bake's LOD count, see
// ClusterLODManager.RenderGpu), never the per-pass node counts themselves.
//
// _NextFrontier/_Selected are sized to meshletsCount plus a small fixed safety pad (M3e - see
// ClusterLODManager.GetOrBuildBuffers), not a generous multiple of it: now that group expansion is
// deduplicated (see _ClaimedGroups below), each real meshlet can enter the frontier or get selected
// at most once per traversal - a root exactly once (roots are already unique), a non-root exactly
// once (it belongs to exactly one ClusterGroup as a child, and that group is only ever expanded
// once) - so meshletsCount is a tight, not just generous, upper bound. Before dedup existed, a
// ClusterGroup with more than one parent meshlet (siblings sharing a group) could be expanded once
// per sibling, doubling the work at every subsequent level and compounding into an exponential
// blowup pass over pass - caught during bring-up (a small bake produced a clean 4x per-pass growth
// in the frontier before saturating every buffer and collapsing the visible result onto whichever
// single leaf happened to dominate the flood of duplicate writes). Writes past the sized capacity
// are still dropped (counted in _Counters[3]) as a last-resort safety net against genuinely
// corrupted data (e.g. a duplicate group-child reference), not the primary defense against blowup.
//
// Dedup mechanism: _ClaimedGroups is a per-group flag, reset to 0 once per frame (per object) by
// ClusterLODManager.RenderGpu before the traversal starts. The first node to fail its test and
// need to expand a given group calls InterlockedCompareExchange to atomically flip that group's
// flag from 0 to 1 - only the thread that performed the actual 0->1 transition proceeds to push
// the group's children; every other node that independently also wanted to expand the same group
// (its siblings) sees the flag already set and does nothing further, exactly like SelectClusters'
// "if (!expandedGroups.Add(...)) continue;".
//
// M3e: parity with SelectClusters' defensive checks (out-of-range meshlet index, out-of-range
// group index) - a corrupted or stale bake (see SelectClusters' own comments for how this can
// happen, e.g. a schema change leaving a new field zero-initialized instead of -1) could otherwise
// cause TraverseLevel to read past the end of a buffer. The CPU aborts the whole traversal the
// instant it sees this, which isn't practical for thousands of parallel GPU threads - instead,
// each thread validates its own indices, silently drops just that one node if they're out of
// range, and counts it in _Counters[4] so ClusterLODManager can warn once per asset (see
// RenderGpu's periodic, throttled health check - deliberately not a readback every frame).

#pragma kernel TraverseLevel
#pragma kernel Advance
#pragma kernel FinalizeArgs

// Do NOT declare _Args as RWStructuredBuffer<IndirectDrawArgs> (a custom 4-uint struct). This is a
// documented Unity/driver bug: on some AMD GPUs under DirectX, a RWStructuredBuffer<T> for a
// custom struct silently uses a stride of 4 bytes instead of the struct's real size, so writes
// for element N land only 4 bytes after element N-1 instead of sizeof(T) bytes after - every
// element after the first overlaps/smears into its neighbors. That matches exactly what was seen
// dumping this buffer from C# (instanceCount/startInstance reading back as unrelated garbage
// values instead of the 1/0 this kernel always writes). Nvidia isn't affected, which is why this
// slipped through - see
// https://discussions.unity.com/t/do-not-use-unitys-indirectdrawindexedargs-in-a-structuredbuffer/1623092
// The documented fix: only ever declare indirect-args buffers as (RW)StructuredBuffer<uint> (or
// (RW)Buffer<uint>) in a compute shader, and index by hand in units of uint.
static const uint IndirectDrawArgsUintCount = 4; // vertexCountPerInstance, instanceCount, startVertex, startInstance

// Counter layout (single small buffer, shared across all three kernels):
//   [0] currentFrontierCount - how many entries in _CurrentFrontier are valid this pass.
//   [1] nextFrontierCount    - accumulated via InterlockedAdd as this pass's failed nodes expand.
//   [2] selectedCount        - cumulative across every pass so far (never reset mid-traversal).
//   [3] overflowCount        - how many appends were dropped because a buffer was full (see above).
//   [4] corruptionCount      - how many nodes were dropped for referencing an out-of-range meshlet
//                              or group index (M3e - see file header comment).
RWStructuredBuffer<uint> _Counters;

// This pass's input (read-only) and output (accumulated via InterlockedAdd) node-index lists. For
// pass 0, _CurrentFrontier is bound directly to the data asset's root indices buffer; from pass 1
// onward it's one of ClusterLODManager's two per-object ping-pong buffers, alternating with
// _NextFrontier every pass.
StructuredBuffer<uint> _CurrentFrontier;
RWStructuredBuffer<uint> _NextFrontier;
int _NextFrontierCapacity;

// Every node that passes its test lands here (cumulative across all passes), consumed by
// FinalizeArgs at the end of the traversal.
RWStructuredBuffer<uint> _Selected;
int _SelectedCapacity;

// Per meshlet (indexed by any meshlet index, root or child): xyz = object-space bounding sphere
// center, w = error. Per meshlet: the group (if any) whose children refine it further, or -1 if
// this meshlet is a true leaf - matches Meshlet.boundingSphere/error/parentGroupIndex on the CPU.
StructuredBuffer<float4> _MeshletBoundingSphereError;
StructuredBuffer<int> _MeshletParentGroup;
int _MeshletsCount;

// Per group: (childMeshletOffset, childMeshletCount) into _GroupChildMeshletIndices.
StructuredBuffer<uint2> _GroupChildOffsetCount;
StructuredBuffer<uint> _GroupChildMeshletIndices;
int _GroupsCount;

// Per-group claim flag (0 = not yet expanded this traversal, 1 = claimed) - see file header
// comment. Reset to all-zero once per frame by ClusterLODManager.RenderGpu before pass 0.
RWStructuredBuffer<uint> _ClaimedGroups;

// Per-frame view state - same inputs the CPU's IsDetailSufficient/SelectClusters use.
float3 _ObjectWorldPosition;
float3 _CameraWorldPosition;
float _ErrorThreshold;

[numthreads(64, 1, 1)]
void TraverseLevel(uint3 id : SV_DispatchThreadID)
{
    uint currentCount = _Counters[0];
    if (id.x >= currentCount)
    {
        return;
    }

    uint meshletIndex = _CurrentFrontier[id.x];

    // M3e: mirrors SelectClusters' out-of-range meshlet index check - a corrupted/stale bake could
    // otherwise send this thread reading past the end of every per-meshlet buffer below. Drop just
    // this one node (not the whole dispatch, unlike the CPU) and count it for ClusterLODManager's
    // periodic health-check warning.
    if (meshletIndex >= (uint)_MeshletsCount)
    {
        uint corruptionDummy;
        InterlockedAdd(_Counters[4], 1u, corruptionDummy);
        return;
    }

    float4 sphereError = _MeshletBoundingSphereError[meshletIndex];
    int parentGroupIndex = _MeshletParentGroup[meshletIndex];

    float d = max(0.0, distance(_CameraWorldPosition, _ObjectWorldPosition + sphereError.xyz));
    float e = d * _ErrorThreshold;
    bool sufficient = (parentGroupIndex < 0) || (sphereError.w <= e);

    if (sufficient)
    {
        uint outIndex;
        InterlockedAdd(_Counters[2], 1u, outIndex);

        if (outIndex < (uint)_SelectedCapacity)
        {
            _Selected[outIndex] = meshletIndex;
        }
        else
        {
            uint dummy;
            InterlockedAdd(_Counters[3], 1u, dummy);
        }
    }
    else if (parentGroupIndex >= (int)_GroupsCount)
    {
        // M3e: mirrors SelectClusters' out-of-range group index check (parentGroupIndex >=
        // Groups.Length) - same reasoning as the meshlet-index check above.
        uint corruptionDummy;
        InterlockedAdd(_Counters[4], 1u, corruptionDummy);
    }
    else
    {
        // Claim this group before expanding it: only the thread that actually flips the flag from
        // 0 to 1 proceeds. Any other node (a sibling meshlet sharing the same parentGroupIndex)
        // that also fails its test this pass sees previousClaim == 1 and does nothing further -
        // this is what stops a shared group from being expanded once per sibling, which otherwise
        // compounds exponentially pass over pass (see file header comment).
        uint previousClaim;
        InterlockedCompareExchange(_ClaimedGroups[(uint)parentGroupIndex], 0u, 1u, previousClaim);

        if (previousClaim == 0u)
        {
            uint2 range = _GroupChildOffsetCount[(uint)parentGroupIndex];
            uint childOffset = range.x;
            uint childCount = range.y;

            for (uint c = 0; c < childCount; c++)
            {
                uint childIndex = _GroupChildMeshletIndices[childOffset + c];

                uint outIndex;
                InterlockedAdd(_Counters[1], 1u, outIndex);

                if (outIndex < (uint)_NextFrontierCapacity)
                {
                    _NextFrontier[outIndex] = childIndex;
                }
                else
                {
                    uint dummy;
                    InterlockedAdd(_Counters[3], 1u, dummy);
                }
            }
        }
    }
}

// Runs as a single thread between passes: promotes next->current, resets next to zero, and writes
// GPU-computed thread-group counts for the *following* TraverseLevel dispatch (issued via
// ComputeShader.DispatchIndirect from ClusterLODManager.RenderGpu) so no CPU readback is needed to
// know how many nodes the next pass has to process.
RWStructuredBuffer<uint> _DispatchArgs; // [0]=groupsX, [1]=groupsY, [2]=groupsZ

[numthreads(1, 1, 1)]
void Advance(uint3 id : SV_DispatchThreadID)
{
    uint nextCount = _Counters[1];
    _Counters[0] = nextCount;
    _Counters[1] = 0u;

    _DispatchArgs[0] = (nextCount + 63u) / 64u;
    _DispatchArgs[1] = 1u;
    _DispatchArgs[2] = 1u;
}

// Runs once after every pass is done, with a fixed CPU-known dispatch size (data.MeshletsCount) -
// unlike the traversal passes, this never needs to be camera/data-dependent, since it's just
// converting whatever ended up in _Selected (up to _Counters[2] entries) into IndirectDrawArgs, one
// thread per potential output slot. Slots beyond the real selected count are padded with a
// zero-vertex-count no-op draw, exactly like M3c did.
RWStructuredBuffer<uint> _Args;
StructuredBuffer<uint> _MeshletIndexCounts;
int _ClusterMaxPrimitives;
int _SlotCount;

[numthreads(64, 1, 1)]
void FinalizeArgs(uint3 id : SV_DispatchThreadID)
{
    if ((int)id.x >= _SlotCount)
    {
        return;
    }

    uint selectedCount = _Counters[2];
    uint baseIndex = id.x * IndirectDrawArgsUintCount;

    if (id.x < selectedCount && id.x < (uint)_SelectedCapacity)
    {
        uint meshletIndex = _Selected[id.x];
        uint vertexCountPerInstance = _MeshletIndexCounts[meshletIndex];
        uint startVertex = meshletIndex * (uint)_ClusterMaxPrimitives * 3u;

        _Args[baseIndex + 0] = vertexCountPerInstance;
        _Args[baseIndex + 1] = 1u;
        _Args[baseIndex + 2] = startVertex;
        _Args[baseIndex + 3] = 0u;
    }
    else
    {
        _Args[baseIndex + 0] = 0u;
        _Args[baseIndex + 1] = 0u;
        _Args[baseIndex + 2] = 0u;
        _Args[baseIndex + 3] = 0u;
    }
}