Culling Meshlets, and the scene where it did not pay

The frame's draw, and why its cost is index writes

Key idea. Each culling phase builds its draw as one index per triangle corner, in slot order. Once the slots are summed, what the pass pays for is writing those indices: on town, 5,552,214 triangles' worth.

The Frame data lists no draws. The GPU builds its own: the culling pass tests each Instance and appends the ones it draws to the frame's draw, which the main pass draws with one draw_indexed_indirect per pipeline and phase (ADR 0019). The draw is two buffers:

• Meshlet records, one per Meshlet of each drawn Instance: the Instance's slot, the Meshlet and the Material it is drawn with.
• Packed indices, one per triangle corner: the record in the high bits and the vertex within its Meshlet in the low six. Meshlets hold at most 64 vertices and 124 triangles. The vertex shader unpacks the record, and from it its Instance, Material and vertex.

Both are written in slot order within each phase, never in the order atomics happen to land. On the M4 Pro, which triangles a draw holds before others changes the derivatives some pixels sample their Textures with, so a draw built in landing order would draw a different image from run to run (Instance Culling Explained, chapter 3). Slot order means every Instance must know where its records and indices start before any are written, and that is a prefix sum.

Four dispatches per phase

One compute pass per culling phase, at a531ed2:

1. offset_slots · a workgroup per 256 slots
2. offset_blocks · one workgroup
3. append_records · an invocation per slot
4. append_triangles · indirect, 32 per record

1. offset_slots tests each slot's Instance against the frustum, and in phase two the depth pyramid, and sums the Meshlet records and packed indices of the drawn ones over each block of 256 slots: a Hillis and Steele scan in workgroup memory.
2. offset_blocks, one workgroup, scans the blocks' sums. It also writes how many workgroups step 4 launches, and the phase's range of records, as chapter 2 explains.
3. append_records writes each drawn Instance's Meshlet records from its offset, and counts it drawn or, past the draw's capacity, overflowed.
4. append_triangles takes one workgroup of 32 invocations per record and writes its Meshlet's packed indices, adjacent invocations writing adjacent indices.

What PR #363 replaced

Before it, steps 3 and 4 were one entry point, append_meshlets, with a workgroup of 124 invocations, one per triangle of a Meshlet, for every slot in use. town places 244,256 Instances and 10,000 pigeons, so each phase launched 254,256 workgroups whatever it appended. Phase two appends little, since most of what is visible was drawn in phase one, yet it spent about 0.7 ms on those workgroups. PR #363 measured, on town against main's Baseline:

The draw is byte-identical: the same records and packed indices, in the same order, so no image changed. The two phases went from 2,411 to 1,279 µs, 53% of where they started. The ticket asked for under half.

What remains is the writes

Phase one's 1.1 ms is its packed-index writes: 3 × 5,552,214 = 16,656,642 of them on town, this page's product. PR #363 tried to find another cause and found none. A variant that wrote its indices without reading anything cost the same; so did workgroups 32 to 128 wide, and 1 to 8 records per workgroup. Writing fewer indices is the only lever left, which means drawing fewer triangles: a test of each Meshlet, chapter 3's subject.

Indirect dispatch, and the stand-in buffer

Key idea. The GPU writes how many workgroups append_triangles launches into a buffer, and the dispatch reads them from there; the CPU never learns the number. wgpu checks a dispatch's bindings and its argument buffer together, and a buffer cannot be both, so the dispatch binds a 72-byte stand-in where that buffer would go.

Only offset_blocks knows how many Meshlet records the phase appends, and it knows it on the GPU, mid-frame. Reading it back would stall the frame. An indirect dispatch takes its workgroup counts, x, y and z, from a buffer instead of from the CPU's call, so offset_blocks writes them and append_triangles launches with them, in the same compute pass.

Rows of 65,535

A dispatch may launch at most 65,535 workgroups in each dimension, wgpu's default max_compute_workgroups_per_dimension, which the Capability floor takes as its own (ADR 0021); CullingPass::new asserts the device allows it. The frame's draw holds 2²⁰ = 1,048,576 records, so the records are laid out in rows:

// culling.wgsl at a531ed2, the end of offset_blocks
let records = appended.y - appended.x;
// At least one row, so no records dispatch no workgroups.
let rows = max((records + MAX_WORKGROUPS_PER_DIMENSION - 1u) / MAX_WORKGROUPS_PER_DIMENSION, 1u);
frame_draw.append_dispatch = DispatchIndirect((records + rows - 1u) / rows, rows, 1u);

Each workgroup finds its record as appended.x + workgroup.y * workgroups.x + workgroup.x, and returns at once past the last, since x × y can exceed the count. The max(…, 1) matters at zero: without it, rows would be 0 and x would compute (0 + 0 − 1) / 0, which PR #363's review caught wrapping x to 0xFFFFFFFF. With it, zero records give x = 0, y = 1: no workgroups.

One usage scope per dispatch

The dispatch's arguments live in frame_draw, which group 3 binds read-write: the culling entry points add to its counts and offset_blocks writes the arguments there. wgpu tracks how each dispatch uses every buffer, in a usage scope. In wgpu-core 30, flush_bindings merges every active bind group into the dispatch's scope, then the indirect buffer, as INDIRECT. In wgpu-types, INDIRECT is one of the uses a buffer may hold at the same time as others, and STORAGE_READ_WRITE one it must hold alone. So a dispatch whose arguments are in a buffer that a bound group writes fails validation.

Group 3 holds more than frame_draw: the offsets, records, packed indices, visibility bits and the depth pyramid. append_triangles needs most of them. So it runs with a second copy of group 3, built beside the first in frame_draw_bind_groups, whose frame_draw binding is a 72-byte stand-in it never reads. It reads the phase's record range from instance_offsets[APPENDED_RECORDS], where offset_blocks put a copy, past every slot's and block's offsets. One layout, one pipeline layout, two groups.

• The road not taken. The first attempt copied the arguments out between two compute passes. It cost about 50 heap allocations a frame, and was dropped.
• What it costs. 192 bytes of GPU memory on every scene, among them the stand-in's 72 and FrameDraw's growth from 56 to 72 bytes; and 3 heap allocations a frame on Metal, 2 on lavapipe. A test build with direct dispatches allocated fewer, so those are wgpu's work for indirect ones.
• Why 32 wide. 32 is an Apple SIMD-group. On crowd, phase one read 142 µs with a workgroup of 124 invocations, one per triangle, as before, and 93 with 32 per index. town read 1,112 µs either way.
• Why records stay one per slot. Spreading each block's records over a workgroup read 55 µs on helmet but cost town about 180 µs.

What a Meshlet test is

Key idea. A drawn Instance's Meshlet can be dropped whole when its box lies outside the view frustum, when in phase two the depth pyramid hides its box, or when its normal cone shows the camera sees all of its triangles from behind. The cone test needs only a sphere that holds the triangles, so the sphere round the Meshlet's box will do.

The prototype tests each Meshlet of an Instance that has already passed the Instance tests. A Meshlet is kept or dropped whole, never triangle by triangle: its record stays, and its indices are written or not.

The box tests, again

The frustum and occlusion tests are the Instance's, given a smaller box. clip_space_bounds takes the box's corners instead of a Mesh, and in_view_frustum and occluded run unchanged (Instance Culling Explained, chapter 4; Depth Pyramid Explained). The frustum has five planes, four sides and the near one, since with reverse-Z and no far plane there is no sixth (ADR 0015). Phase one has no depth pyramid yet, so it keeps Meshlets that are hidden behind others. The prototype's GPU test shows it: an Instance entering view in its second frame has phase two drop a Meshlet behind a nearer quad, and in its third, phase one keeps it.

The normal cone

The third test asks whether the camera sees every triangle of the Meshlet from behind, as the rasterizer would cull each of them. A normal cone answers it without visiting the triangles: an axis a, and a half-angle α within which every triangle's normal lies. meshoptimizer 0.25's meshopt_computeMeshletBounds computes it, which the Mesh pool calls through the meshopt crate. It sets the cone's axis from the triangles' normals and finds the smallest dot product of any normal with it, cos α. Its cutoff is s = √(1 − cos² α) = sin α.

• Wide cones accept everything. Where cos α ≤ 0.1, so the cone is about 168° wide or more, meshoptimizer calls it degenerate and sets the cutoff to 1, which culls nothing.
• Eight bits, rounded up. The axis and cutoff are also given as Snorm8, each x/127. meshoptimizer adds the quantised axis's error to the cutoff and rounds up, so the 8-bit test never culls a Meshlet the exact cone keeps. The prototype stores those four bytes, and tests cone.w < 1.0 first: a cutoff of 127 culls nothing.

The test without an apex

meshoptimizer's header gives two perspective tests. One needs the cone's apex. The other, which the prototype uses, needs only a bounding sphere, centre c and radius r, and the camera e: the Meshlet faces away where

dot(c − e, a)  ≥  s · |c − e|  +  r

The header cites Real-Time Rendering, 4th edition, section 19.3, for its derivation. The prototype uses the sphere round the Meshlet's box, centred on the box with half its diagonal as radius, since the box is there already. meshoptimizer's own sphere would be tighter, but the test holds for any sphere that holds the triangles. Here is why, in this page's words. Write L = |c − e| and u = cos θ for the angle θ between c − e and the axis:

the test says        u  ≥  s + r/L
any normal n is within α of a, so the angle from c − e to n is at most θ + α
any triangle point p is within r of c, so
  dot(p − e, n)  =  dot(c − e, n) + dot(p − c, n)  ≥  L·cos(θ + α) − r
cos(θ + α)  =  u·√(1 − s²) − s·√(1 − u²)  =  f(u),   and f(s) = 0
f′(u)  =  √(1 − s²) + s·u/√(1 − u²)  ≥  1/√(1 − s²)  ≥  1   for u ≥ s
so  L·cos(θ + α)  ≥  L·(u − s)  ≥  r,   and dot(p − e, n) ≥ 0

The last line says the camera lies behind the plane of every triangle the cone covers, which is what the rasterizer would cull. The sphere enters only through dot(p − c, n) ≥ −r, which every sphere that holds p gives. A larger sphere is still sound; it only culls less.

In mesh space

The cone is computed from the Mesh's own vertices, so the prototype tests it in mesh space. It moves the camera there instead of the cone: by the inverse of the Instance's rotation-scale, computed as its cofactors' transpose over its determinant. That is sound because whether a point lies behind a triangle's plane is the sign of a determinant of the triangle's corners and the point, and an affine map multiplies that by its own determinant. Where the determinant is not positive, a mirroring transform that flips winding, the cone test is skipped. It is also skipped unless the camera is a perspective one at the camera-relative origin, which the view-projection maps to clip x = y = w = 0; tests that draw with an identity view-projection are orthographic and keep every Meshlet.

Where the bounds come from

Each Meshlet's box and cone are computed when the Mesh pool loads a Mesh, not cooked into its Blob. SciFiHelmet's Mesh Blob reads 13.822 bytes per triangle against its 13.83 ceiling, which leaves no room for them. A Mesh the GPU bends, as crowd's figures are, gets its whole Mesh's box for every Meshlet and the no-cull cone, since its cooked triangles bound none of the shapes it is bent into.

Test each Meshlet once

Key idea. Metal compiles shaders with fast math by default, which allows the compiler to reassociate arithmetic, so two entry points that test the same Meshlet may disagree at the boundary. The prototype tests each Meshlet in one place, writes down the answer, and every later step reads it.

Part A's offsets are counted in one dispatch and used in another. A test of each Meshlet would naturally go in both: offset_slots testing to count the kept indices, and append_triangles testing again to know whether to write them. That relies on both computing the same answer from the same numbers.

The Metal Shading Language specification, 4.1, section 1.6.3, says of -fmetal-math-mode: “The default is fast,” which lets the compiler assume no NaNs or infinities, and “allow reassociation, and FP contract to be fast”. In f32, (x + y) + z and x + (y + z) can round to different values, and a fused multiply-add rounds once where a multiply then an add round twice. Two entry points compiled separately can each choose. For a Meshlet whose test lands within a rounding step of its boundary, the count could say kept and the write say dropped. Then an Instance's indices would end short of the next Instance's offset, leaving a gap of indices that nothing wrote, or overrun it.

How the prototype orders it

Six dispatches per phase, on prototype/347-meshlet-culling:

1. offset_slots · records
2. offset_blocks · records
3. append_records · tests each Meshlet
4. offset_index_blocks
5. count_instances
6. append_triangles

1. offset_slots still tests Instances, but sums only their Meshlet records, which do not depend on the Meshlet test.
2. offset_blocks scans the records and sizes the indirect dispatch, as before.
3. append_records tests each Meshlet, once. It writes every record with the offset of its indices within its Instance, or NOT_KEPT, and scans the kept indices over its block of slots.
4. offset_index_blocks, one workgroup, scans the blocks' kept indices.
5. count_instances, an invocation per slot, counts each Instance drawn or overflowed, now that its final index offset is known.
6. append_triangles writes the indices of the records kept, from their Instance's first index plus the record's offset, and returns at once for a NOT_KEPT record.

Records are not compacted: a dropped Meshlet keeps its record, with no indices pointing at it. Each record grew by one u32, its index offset, and the frame's draw by 4 × 2²⁰ = 4,194,304 bytes. Since each answer is written once and read thereafter, the draw stays in slot order and the same from run to run.

What town measured

Key idea. On town, the Meshlet test dropped 4.9% of the triangles drawn. The depth pre-pass and lit pass got about 90 µs cheaper, the culling phases about 130 µs dearer, and the gate stayed at 8.6 ms against its 6 ms limit. Most of town's Instances draw a single Meshlet that faces every way.

The prototype (M) and main at 7525b7d (A), release builds, praxis bench on town, 1,800 measured frames, three rounds of M then A with no other GPU work. Medians per round, in µs:

• Triangles drawn: 5,552,214 to 5,280,720, −271,494, or −4.9%.
• The draw: the depth pre-pass and lit pass together about 90 µs cheaper, over rounds 2 and 3. Round 1's M lit_pass stands apart from the other five, while its gate does not, so the note leaves it out.
• The culling phases: about 130 µs dearer: the Meshlet tests and the two extra dispatches.
• The phases against the ticket: M's median round reads 1,234 + 217 = 1,451 µs, 60% of the 2,411 the ticket started from. It asked for under half. Even if the tests cost nothing, 4.9% fewer index writes could not bring A's roughly 1.3 ms under 1.2.
• The gate: 8.6 ms either way, against 6.

Why so few

Of the 244,256 Instances town places besides its pigeons, 171,649 draw a Mesh of a single Meshlet, among them 109,760 railing posts and 56,932 boxes, and each of the 10,000 pigeons does too: by this page's sum, 181,649 of 254,256 slots, 71%. For those, the Meshlet test can drop nothing the Instance test did not, since the Meshlet's box is the Mesh's box.

Nor can the cone. A box's single Meshlet faces every way: its normals point along all six axes, its cone is degenerate, and its cutoff is 127. Its back faces are still dropped, but by the rasterizer, after the vertex shader has run for them. Choose box, one Meshlet in the demo above and turn the camera: the cone never culls, and the far faces are drawn facing away. The other Meshes hold 2 to 5 Meshlets each, cut in index order rather than by facing, and 33 of their 37 Meshlets have a cone too wide to cull by. Only 4 could be dropped for facing away.

The ticket's hope came from option B's prototype, which found about 2.9 ms of the lit pass was vertex work on Meshlets no sample shows (Visibility Pre-pass Explained, chapter 4). A sample-exact pass sees that; a test of bounds sees only what a box and a cone can prove.

Correct, but not merged

The prototype passed its checks: a new GPU test that drops a Meshlet outside the frustum, one facing away and, in phase two, one behind the pyramid; every Golden but one; and culling on and off drawing the same image at town's eight frames. The exception was helmet, whose culled and unculled images differed by 23 pixels with shadow rays on, and by none with them off. That is a bug of its own, #369, about which triangle a sample on a shared edge shows. PR #373 has since fixed it, and with the fix the prototype's helmet images match at 0 pixels; it is MSAA Fragment Merging Explained's subject.

The owner chose to record the prototype rather than merge it. It stays on its branch at d242a68. docs/performance.md holds the measurement, and ADR 0019's line that culling tests Instances, with tests per Meshlet waiting for a profile that shows the pass raster-bound, now cites it as evidence.

What would make it pay

Key idea. A Meshlet test pays where Meshlets have narrow cones and are each a small part of what an Instance draws. Either cut Meshes so their Meshlets face one way, at the cost of more records, or draw denser Meshes. Neither is ticketed; the next step on the gate is option D.

• Cut by facing. A box cut into its six faces has six Meshlets, each with a cone of zero width, and from most viewpoints the cone test drops the faces turned away before their vertex work. Choose box as its faces in the demo. The price is records: six per box instead of one, each written by append_records and each a workgroup of append_triangles. Notice too that the apex-free test is conservative: a face is dropped only once the camera is behind its plane by at least the sphere's radius.
• Denser Meshes. The demo's ring, 16 is a Mesh whose Meshlets each turn only a little: from outside, roughly half of them fail the cone test, and a close camera drops more by the frustum. A Mesh of many Meshlets, each a small part of the Instance, is where a test of each pays for itself. town's Meshes are not that.

docs/performance.md names both and tickets neither. With the gate still past 6 ms under option A after #363 and this, ADR 0019's reopen clause sends the next prototype to option D, a visibility buffer, ticket #297 (Frame Timing Explained, chapter 3).

Check yourself

Why does append_triangles run with a second copy of group 3, whose frame_draw binding is a stand-in it never reads?

Its dispatch takes its arguments from frame_draw, as an indirect buffer. wgpu merges every bind group active at a dispatch and its indirect buffer into one usage scope, and a buffer may not be used as INDIRECT and as read-write storage in one scope. The first copy of group 3 binds frame_draw read-write, so append_triangles binds a copy with a 72-byte stand-in in its place, and reads the phase's record range from instance_offsets instead.

The prototype could have tested each Meshlet in offset_slots, to count its indices, and again in append_triangles, to write them. Why does it test each once, in append_records?

Metal compiles with fast math by default, which lets the compiler reassociate and contract arithmetic differently in each entry point. Near the test's boundary the two could disagree: the count says kept and the write says dropped, or the reverse, and an Instance's indices would then leave a gap of unwritten indices or overrun the next Instance's. Testing once and recording the answer, an index offset or NOT_KEPT, gives every later step the same answer.

Why did the cone test drop nothing from town's 56,932 boxes, and what would let it?

Each box draws a Mesh of one Meshlet whose normals point every way, so its normal cone is wider than about 168°: meshoptimizer gives it the cutoff 127, which culls nothing. The rasterizer still drops the back faces, after their vertex work. Cutting the box into Meshlets by face would give each a zero-width cone, which the test can drop once the camera is behind the face's plane by the sphere's radius, at the cost of six records per box instead of one.

Reading list

Grouped by source, each with what it is good for here. Links into the code are pinned to a531ed2, or to d242a68 for the prototype.

Glossary

Meshlet, Instance, Frame data and Capability floor are CONTEXT.md's definitions at a531ed2. The rest are this guide's own.