// ─────────────────────────────────────────────────────────────────────────────
// OIT — order-independent transparency via per-pixel fragment linked lists.
// GFX_V2 §3.C. Composed behind `render::gpu::COMMON_WGSL` (it takes `px_to_ndc`
// from the ONE prelude, so the screen mapping cannot drift from the line lanes).
//
// TWO passes over three storage buffers:
//
// GATHER rasterise every translucent fragment and *append* it to its pixel's
// singly-linked list. Writes NO colour (`ColorWrites::empty()`), runs
// with NO depth attachment, and takes its sort key from a **vertex
// attribute** rather than the rasteriser — so nothing about the order
// fragments arrive in can discard one.
// RESOLVE one fullscreen triangle; each pixel walks its list into registers,
// sorts, and composites back-to-front over the background.
//
// WHY THIS IS ORDER-INDEPENDENT, PRECISELY. The list itself is built by
// `atomicExchange` on the head pointer, so its link order IS submission order and
// differs run to run. Order-independence therefore rests on exactly two properties
// of the resolve, and both are deliberate:
//
// 1. **The sort key is a TOTAL order** — `oit_farther` compares depth first and
// breaks ties on the packed colour. A depth-only comparator is a *partial*
// order: two fragments at equal depth would keep whatever relative order the
// list gave them, and equal depths are not exotic (coplanar quads, a shared
// edge between two triangles of one quad). Ties are where a "sorted" OIT
// silently becomes order-dependent, so they are ordered explicitly.
// 2. **Overflow selects, it does not truncate** — past `OIT_LAYERS` the resolve
// keeps the N *nearest* fragments under that same total order, evicting the
// farthest. Keeping "the first N encountered" would be submission-order
// dependent exactly when the buffer is full, which is precisely the case a
// test with few layers never reaches.
//
// Given 1 and 2 the sorted sequence at a pixel is a pure function of the SET of
// fragments covering it, and the composite is a fixed fold over that sequence — so
// the output is bit-identical across submission orders, not merely close.
// ─────────────────────────────────────────────────────────────────────────────
/// How many fragments per pixel the resolve carries in registers.
const OIT_LAYERS: u32 = 16u;
struct OitU {
/// Viewport in physical px, for `px_to_ndc`.
viewport: vec2<f32>,
/// Viewport as integers — `dims.x` is the head-pointer row stride.
dims: vec2<u32>,
/// The (opaque) background the sorted fragments composite over.
background: vec4<f32>,
/// Node-buffer capacity in fragments; allocations past it are dropped.
capacity: u32,
// Tail padding to a 16 B multiple, as THREE SCALARS and deliberately not a
// `vec3<u32>`. A `vec3` has an alignment of 16 in WGSL, not 12, so spelling the
// padding as one would push this struct to 64 B while the Rust mirror stayed 48 —
// which is exactly the validation error ("bound with size 48 where the shader
// expects 64") that writing it that way first produced. Scalars give offsets 36 /
// 40 / 44, matching `[u32; 3]` on the host byte for byte.
_pad0: u32,
_pad1: u32,
_pad2: u32,
}
/// One fragment on a pixel's list. 12 B.
struct OitNode {
/// `pack4x8unorm(rgba)` — straight (NOT premultiplied) alpha.
color: u32,
/// The sort key. A vertex attribute, not the rasterised z.
depth: f32,
/// **1-based** index of the next node; `0` terminates. 1-based so a
/// zero-filled `heads` buffer already means "empty", and the per-frame reset is
/// a `clear_buffer` rather than a clear shader.
next: u32,
}
@group(0) @binding(0) var<uniform> u: OitU;
@group(0) @binding(1) var<storage, read_write> heads: array<atomic<u32>>;
@group(0) @binding(2) var<storage, read_write> nodes: array<OitNode>;
/// Single-element bump allocator over `nodes`. Also read back on the host as the
/// count of fragments the gather actually emitted — device-side evidence that the
/// pass ran, and how much of it ran.
@group(0) @binding(3) var<storage, read_write> alloc: array<atomic<u32>>;
// ── GATHER ───────────────────────────────────────────────────────────────────
struct GatherIn {
@location(0) pos_px: vec2<f32>,
@location(1) depth: f32,
@location(2) color: vec4<f32>,
}
struct GatherOut {
@builtin(position) clip: vec4<f32>,
@location(0) color: vec4<f32>,
@location(1) depth: f32,
}
@vertex
fn oit_gather_vs(v: GatherIn) -> GatherOut {
var o: GatherOut;
// z = 0 and no depth attachment: the rasteriser must not reject anything. The
// depth that matters travels as `o.depth`.
o.clip = vec4<f32>(px_to_ndc(v.pos_px, u.viewport), 0.0, 1.0);
o.color = v.color;
o.depth = v.depth;
return o;
}
@fragment
fn oit_gather_fs(i: GatherOut) -> @location(0) vec4<f32> {
let px = vec2<u32>(u32(i.clip.x), u32(i.clip.y));
if (px.x < u.dims.x && px.y < u.dims.y) {
let n = atomicAdd(&alloc[0], 1u);
if (n < u.capacity) {
let idx = px.y * u.dims.x + px.x;
// Push onto the head: the old head becomes this node's `next`.
let prev = atomicExchange(&heads[idx], n + 1u);
nodes[n].color = pack4x8unorm(i.color);
nodes[n].depth = i.depth;
nodes[n].next = prev;
}
}
// The pipeline's write mask is empty, so this never reaches the attachment. It
// exists because a fragment stage bound to a colour target must declare one.
return vec4<f32>(0.0, 0.0, 0.0, 0.0);
}
// ── RESOLVE ──────────────────────────────────────────────────────────────────
/// **The total order, far → near.** Depth first; the packed colour breaks ties.
///
/// The tie-break is not decoration — see the header. Without it two fragments at
/// equal depth resolve in list order, i.e. in submission order, and the whole
/// order-independence claim fails on any pair of coplanar surfaces.
fn oit_farther(a_depth: f32, a_color: u32, b_depth: f32, b_color: u32) -> bool {
if (a_depth != b_depth) {
return a_depth > b_depth;
}
return a_color > b_color;
}
@vertex
fn oit_resolve_vs(@builtin(vertex_index) vi: u32) -> @builtin(position) vec4<f32> {
// The standard oversized triangle covering clip space: (-1,-1), (-1,3), (3,-1).
let x = f32(i32(vi) / 2) * 4.0 - 1.0;
let y = f32(i32(vi) & 1) * 4.0 - 1.0;
return vec4<f32>(x, y, 0.0, 1.0);
}
@fragment
fn oit_resolve_fs(@builtin(position) fc: vec4<f32>) -> @location(0) vec4<f32> {
let px = vec2<u32>(u32(fc.x), u32(fc.y));
var col: array<u32, OIT_LAYERS>;
var dep: array<f32, OIT_LAYERS>;
var n = 0u;
if (px.x < u.dims.x && px.y < u.dims.y) {
var cur = atomicLoad(&heads[px.y * u.dims.x + px.x]);
loop {
if (cur == 0u) {
break;
}
let node = nodes[cur - 1u];
if (n < OIT_LAYERS) {
col[n] = node.color;
dep[n] = node.depth;
n = n + 1u;
} else {
// FULL — evict the farthest if this one is nearer, so the surviving
// set is "the OIT_LAYERS nearest" and not "the first OIT_LAYERS seen".
var worst = 0u;
for (var k = 1u; k < OIT_LAYERS; k = k + 1u) {
if (oit_farther(dep[k], col[k], dep[worst], col[worst])) {
worst = k;
}
}
if (oit_farther(dep[worst], col[worst], node.depth, node.color)) {
col[worst] = node.color;
dep[worst] = node.depth;
}
}
cur = node.next;
}
}
// Insertion sort, farthest first. n <= 16, so this is a handful of compares.
for (var i = 1u; i < n; i = i + 1u) {
let kd = dep[i];
let kc = col[i];
var j = i;
loop {
if (j == 0u) {
break;
}
if (!oit_farther(kd, kc, dep[j - 1u], col[j - 1u])) {
break;
}
dep[j] = dep[j - 1u];
col[j] = col[j - 1u];
j = j - 1u;
}
dep[j] = kd;
col[j] = kc;
}
// Back-to-front `src OVER dst`, straight alpha.
var rgb = u.background.rgb;
var a = u.background.a;
for (var i = 0u; i < n; i = i + 1u) {
let src = unpack4x8unorm(col[i]);
rgb = src.rgb * src.a + rgb * (1.0 - src.a);
a = src.a + a * (1.0 - src.a);
}
return vec4<f32>(rgb, a);
}