MOOR security

Dieser Eintrag ist auf Englisch verfasst.

Triangle fans on a GPU API that has none

Entry 068856 of 956 tests pass

Metal can't draw triangle fans, so mtl12 rewrites each fan into a triangle list on the GPU just before the draw, keeping the vertex that flat shading reads in the right place.

What changed

A triangle fan is a primitive type where every triangle shares the first vertex, the "hub": vertices h, a, b, c draw triangles (h, a, b) and (h, b, c). Direct3D 12 offers fans as an optional feature (TriangleFanSupported), mostly for translation layers that run Direct3D 9 games on top of it. Metal has no fan primitive.

mtl12 already rewrote some index buffers on the GPU just before the draws that use them, for strip cut values Metal lacks. Fans now use the same pre-pass. A fan of n vertices becomes a triangle list of 3(n − 2) 32-bit indices, and triangle t is written as (v[t+1], v[t+2], hub). The rotation matters. A triangle's "provoking vertex" is the one a non-interpolated (flat) attribute comes from. For fans it is v[t+1], while Metal takes the first vertex of a list triangle. Rotating puts v[t+1] first and keeps the winding, so back-face culling still works. A fan that isn't indexed gets generated indices 0, 1, 2….

Fans with a "cut" value (a special index that ends one fan and starts the next) are converted in a single threadgroup per draw. It walks the fan in chunks of 256 triangles and carries the current hub from one chunk to the next. My first version had each GPU thread scan backwards for the last cut. That costs O(n²) for a long fan, and the review after the milestone flagged it as a GPU watchdog risk.

How a fan draw becomes a Metal triangle list.D3D12: DrawIndexedInstanced, topology TRIANGLEFAN indices h a b c CUT h2 d e f → record_draw: count = 3 x (n - 2) mode by index size and strip cut value; D3D12: DrawInstanced, TRIANGLEFAN no index buffer → record_draw: count = 3 x (n - 2) mode by index size and strip cut value (indices 0, 1, 2, ... base vertex = start vertex); record_draw: count = 3 x (n - 2) mode by index size and strip cut value → cut value set?; cut value set? → convert_indices one thread per output index (no); cut value set? → convert_fan_cuts: one threadgroup prefix max of cut positions in chunks of 256 triangles (yes); convert_indices one thread per output index → triangle t = (v[t+1], v[t+2], hub) provoking vertex first, same winding; convert_fan_cuts: one threadgroup prefix max of cut positions in chunks of 256 triangles → triangle t = (v[t+1], v[t+2], hub) provoking vertex first, same winding; triangle t = (v[t+1], v[t+2], hub) provoking vertex first, same winding → triangles touching a cut: three 0xffffffff, nothing drawn; triangle t = (v[t+1], v[t+2], hub) provoking vertex first, same winding → Metal: indexed triangle list of 32-bit converted indices; triangles touching a cut: three 0xffffffff, nothing drawn → Metal: indexed triangle list of 32-bit converted indicesD3D12: DrawIndexedInstanced, topology TRIANGLEFANindices h a b c CUT h2 d e frecord_draw: count = 3 x (n - 2)mode by index size and strip cut valueD3D12: DrawInstanced, TRIANGLEFANno index buffercut value set?convert_indicesone thread per output indexconvert_fan_cuts: one threadgroupprefix max of cut positionsin chunks of 256 trianglestriangle t = (v[t+1], v[t+2], hub)provoking vertex first, same windingtriangles touching a cut:three 0xffffffff, nothing drawnMetal: indexed triangle listof 32-bit converted indicesindices 0, 1, 2, ...base vertex = start vertexnoyes
How a fan draw becomes a Metal triangle list. (Mermaid source)
Scene trianglefan: left, one triangle fan of 26 vertices, a disc of 24 wedges, each coloured by its provoking vertex, so the colours step around the rim in order; right, one indexed draw with the strip cut 0xFFFFFFFF: a hexagon, a square and a pentagon, three fans split by cuts, each around its own hub, with no slivers joining them
Gallery scene trianglefan: left, one triangle fan of 26 vertices, a disc of 24 wedges, each coloured by its provoking vertex, so the colours step around the rim in order; right, one indexed draw with the strip cut 0xFFFFFFFF: a hexagon, a square and a pentagon, three fans split by cuts, each around its own hub, with no slivers joining them. All scenes in the gallery

The interesting part

The new test passed with the hub carry deliberately broken. A broken carry makes a triangle use the cut value 0xffffffff as its hub's index. That index lies past the vertex buffer, and the results fit that vertex being drawn with a position of zeros. In the test every fan's hub sat at (0, 0), so the wrong triangles covered exactly the right pixels. The test now stores positions 0.25 off the origin and the vertex shader subtracts it again. With that change the same mutation fails. The lesson is to break the code once on purpose and watch the new test fail.

Numbers

  • Full run: 856 pass, 27 fail, 73 skip of 956, up from 853.
  • vkd3d-proton test_topology_triangle_fan went from skipped to passing. The new api/triangle_fan test passes all 691 checks, and 561 of them fail without the change.
Tests by suite at the end of this entry: 856 of 956 pass (data as CSV)
  • pass
  • fail
  • skip

suite · share of each row's total

  1. vkd3d-proton (+1)494 pass, 14 fail, 69 skip of 577
  2. vkd3d177 pass, 9 fail, 4 skip of 190
  3. api (+1)85 pass, 0 fail, 0 skip of 85
  4. apps (+1)80 pass, 0 fail, 0 skip of 80
  5. wine-dxgi16 pass, 4 fail, 0 skip of 20
  6. samples4 pass, 0 fail, 0 skip of 4
Zur Eintragsliste