facett-core 0.1.18

//! **OIT — order-independent transparency via per-pixel fragment linked lists**
//! (GFX_V2 §3.C, item 7).
//!
//! The thing this replaces is a CPU depth sort. Sorting *primitives* on the CPU is
//! wrong in a way that no amount of care fixes: two translucent quads that intersect,
//! or three that cycle in overlap, have **no** correct primitive order — only a
//! per-*fragment* order exists. So the sort moves to the pixel:
//!
//! ```text
//!   GATHER   every translucent fragment appends {colour, depth} to its pixel's
//!            singly-linked list (atomic head exchange + a bump allocator)
//!   RESOLVE  one fullscreen pass; each pixel walks its list into registers, sorts
//!            it, and composites back-to-front over the background
//! ```
//!
//! **The claim, stated so it can fail.** The rendered pixels are *bit-identical* for
//! any permutation of the submission order — not "visually similar", not "within a
//! tolerance". [`OIT_WGSL`]'s header derives why from the two properties that carry
//! it (a **total** sort order including a tie-break on colour, and an overflow policy
//! that *selects the nearest* rather than truncating the first N seen). A depth-sorted
//! alpha blend cannot satisfy that claim, and neither can a depth-only comparator.
//!
//! **Why the claim alone is not a proof.** A resolve that returned a constant would
//! also be identical across every order — the identity-value trap. So the device test
//! (`facett-core/tests/gpu_oit.rs`) pairs the cross-order identity with an
//! *independent CPU oracle* of the composite at named pixels, a distinctness check
//! across regions, and the device's own fragment counter read back out of
//! [`OitPass::fragment_count`]. Identity plus correctness plus non-blankness; any one
//! alone is hollow.
//!
//! The depth key is a **vertex attribute**, not the rasterised z, and the gather pass
//! runs with no depth attachment at all. That is what makes the pass usable for
//! painter-ordered 2-D vector layers (feed it [`crate::render::gpu::picking::painter_depth`]-style
//! layer indices) and for true 3-D translucent geometry (feed it view-space depth)
//! without twinning the pipeline.

use wgpu::TextureFormat;

/// The linked-list OIT shader (gather + resolve). Composed behind
/// [`COMMON_WGSL`](super::COMMON_WGSL) by [`super::wgsl`], from which it takes
/// `px_to_ndc` — so its screen mapping is the same one the line lanes use.
pub use crate::render::wgsl::OIT_WGSL;

/// Fragments per pixel the resolve carries in registers. **Must match `OIT_LAYERS`
/// in [`OIT_WGSL`]** — asserted in this module's tests.
pub const OIT_MAX_LAYERS: u32 = 16;

/// Default fragments *allocated* per pixel. Independent of [`OIT_MAX_LAYERS`]: the
/// node buffer may hold more than the resolve can composite (the overflow policy then
/// picks the nearest `OIT_MAX_LAYERS`), or fewer (the allocator then drops the tail).
pub const OIT_DEFAULT_LAYERS: u32 = 8;

/// Size of one [`OitNode`] on the device: `{u32 colour, f32 depth, u32 next}`.
pub const OIT_NODE_SIZE: u64 = 12;

/// One vertex of translucent geometry. Position in **physical pixels**, depth as the
/// sort key (any monotone "farther is larger" scale), colour as straight RGBA.
#[repr(C)]
#[derive(Clone, Copy, Debug, Default, PartialEq, bytemuck::Pod, bytemuck::Zeroable)]
pub struct OitVertex {
    /// Physical-pixel position; `px_to_ndc` maps it in the shader.
    pub pos: [f32; 2],
    /// Sort key — **larger is farther**. Not the rasterised z.
    pub depth: f32,
    /// Explicit tail padding so the Rust and WGSL strides cannot disagree.
    pub _pad: f32,
    /// Straight (non-premultiplied) RGBA in `0..=1`. Quantised to 8 bits per channel
    /// by `pack4x8unorm` when it lands in a node.
    pub color: [f32; 4],
}

/// Byte stride of [`OitVertex`].
pub const OIT_VERTEX_STRIDE: u64 = 32;

#[repr(C)]
#[derive(Clone, Copy, Debug, Default, bytemuck::Pod, bytemuck::Zeroable)]
struct OitUniform {
    viewport: [f32; 2],
    dims: [u32; 2],
    background: [f32; 4],
    capacity: u32,
    _pad: [u32; 3],
}

/// CPU-side translucent geometry for one frame. Mirrors
/// [`PickBatch`](super::picking::PickBatch)'s shape on purpose: one winding writer
/// ([`push_tri`](Self::push_tri)) that every other push delegates to, so a quad and a
/// triangle cannot disagree about orientation.
#[derive(Clone, Debug, Default)]
pub struct OitBatch {
    verts: Vec<OitVertex>,
}

impl OitBatch {
    /// An empty batch.
    #[must_use]
    pub fn new() -> Self {
        Self { verts: Vec::new() }
    }

    /// Drop all geometry, keeping the allocation.
    pub fn clear(&mut self) {
        self.verts.clear();
    }

    /// **The one winding writer.** Append a triangle at a sort depth.
    pub fn push_tri(
        &mut self,
        a: egui::Pos2,
        b: egui::Pos2,
        c: egui::Pos2,
        color: [f32; 4],
        depth: f32,
    ) {
        for p in [a, b, c] {
            self.verts.push(OitVertex { pos: [p.x, p.y], depth, _pad: 0.0, color });
        }
    }

    /// Append an axis-aligned rect as two triangles, sharing the `min→max` diagonal.
    ///
    /// The two triangles carry the **same** depth and colour, so the fragments on their
    /// shared diagonal are a genuine tie — exactly the case [`OIT_WGSL`]'s colour
    /// tie-break exists for. This is why a quad is a useful test primitive rather than
    /// a degenerate one.
    pub fn push_quad(&mut self, rect: egui::Rect, color: [f32; 4], depth: f32) {
        let (a, b) = (rect.min, rect.max);
        let tr = egui::pos2(b.x, a.y);
        let bl = egui::pos2(a.x, b.y);
        self.push_tri(a, tr, b, color, depth);
        self.push_tri(a, b, bl, color, depth);
    }

    /// The raw vertices, for upload.
    #[must_use]
    pub fn vertices(&self) -> &[OitVertex] {
        &self.verts
    }

    /// Vertex count.
    #[must_use]
    pub fn len(&self) -> usize {
        self.verts.len()
    }

    /// Whether nothing has been pushed.
    #[must_use]
    pub fn is_empty(&self) -> bool {
        self.verts.is_empty()
    }

    /// Return a copy of this batch with its triangles in a different **submission
    /// order**, permuting whole triangles and never splitting one.
    ///
    /// This exists so the order-independence proof cannot cheat: the permutation is a
    /// property of the batch, applied by the batch, and `verts` is private — a test
    /// cannot accidentally reorder half a triangle and then "prove" something about a
    /// frame whose geometry it silently changed.
    #[must_use]
    pub fn permuted(&self, order: &[usize]) -> Self {
        let mut out = Self { verts: Vec::with_capacity(self.verts.len()) };
        for &t in order {
            let base = t * 3;
            if base + 2 < self.verts.len() {
                out.verts.extend_from_slice(&self.verts[base..base + 3]);
            }
        }
        out
    }

    /// Number of whole triangles in the batch.
    #[must_use]
    pub fn tri_count(&self) -> usize {
        self.verts.len() / 3
    }
}

/// The two-pass OIT lane: pipelines, the three storage buffers, and the per-frame
/// record. Persistent — `ensure` is idempotent within a size, like every other
/// target in this module.
pub struct OitPass {
    gather: wgpu::RenderPipeline,
    resolve: wgpu::RenderPipeline,
    bgl: wgpu::BindGroupLayout,
    uniform: wgpu::Buffer,
    /// One `u32` head pointer per pixel; `0` = empty list.
    heads: Option<wgpu::Buffer>,
    /// `capacity` × [`OIT_NODE_SIZE`] fragment records.
    nodes: Option<wgpu::Buffer>,
    /// Single-`u32` bump allocator, also the device's fragment counter.
    alloc: wgpu::Buffer,
    bind: Option<wgpu::BindGroup>,
    verts: Option<wgpu::Buffer>,
    vert_cap: usize,
    vertex_count: u32,
    size: (u32, u32),
    capacity: u32,
    layers: u32,
}

impl OitPass {
    /// Whether `adapter` can run this lane at all.
    ///
    /// A fragment shader writing to a storage buffer is
    /// [`wgpu::DownlevelFlags::FRAGMENT_WRITABLE_STORAGE`], which is **not** universal
    /// — and it is the whole mechanism here, so a caller must ask rather than discover
    /// it as a pipeline-creation panic. Reported explicitly rather than skipped
    /// silently: a lane that quietly does nothing is the failure mode this track keeps
    /// finding.
    #[must_use]
    pub fn supported(adapter: &wgpu::Adapter) -> bool {
        adapter
            .get_downlevel_capabilities()
            .flags
            .contains(wgpu::DownlevelFlags::FRAGMENT_WRITABLE_STORAGE)
    }

    /// Build both pipelines for a `target_format` colour attachment.
    #[must_use]
    pub fn new(device: &wgpu::Device, target_format: TextureFormat) -> Self {
        let module = device.create_shader_module(wgpu::ShaderModuleDescriptor {
            label: Some("l0_oit"),
            source: wgpu::ShaderSource::Wgsl(super::wgsl(OIT_WGSL).into()),
        });
        let storage = |binding: u32| wgpu::BindGroupLayoutEntry {
            binding,
            visibility: wgpu::ShaderStages::FRAGMENT,
            ty: wgpu::BindingType::Buffer {
                ty: wgpu::BufferBindingType::Storage { read_only: false },
                has_dynamic_offset: false,
                min_binding_size: None,
            },
            count: None,
        };
        let bgl = device.create_bind_group_layout(&wgpu::BindGroupLayoutDescriptor {
            label: Some("l0_oit_bgl"),
            entries: &[
                wgpu::BindGroupLayoutEntry {
                    binding: 0,
                    visibility: wgpu::ShaderStages::VERTEX_FRAGMENT,
                    ty: wgpu::BindingType::Buffer {
                        ty: wgpu::BufferBindingType::Uniform,
                        has_dynamic_offset: false,
                        min_binding_size: None,
                    },
                    count: None,
                },
                storage(1),
                storage(2),
                storage(3),
            ],
        });
        let pll = device.create_pipeline_layout(&wgpu::PipelineLayoutDescriptor {
            label: Some("l0_oit_pll"),
            bind_group_layouts: &[Some(&bgl)],
            immediate_size: 0,
        });

        let gather = device.create_render_pipeline(&wgpu::RenderPipelineDescriptor {
            label: Some("l0_oit_gather"),
            layout: Some(&pll),
            vertex: wgpu::VertexState {
                module: &module,
                entry_point: Some("oit_gather_vs"),
                compilation_options: Default::default(),
                buffers: &[wgpu::VertexBufferLayout {
                    array_stride: OIT_VERTEX_STRIDE,
                    step_mode: wgpu::VertexStepMode::Vertex,
                    attributes: &[
                        wgpu::VertexAttribute {
                            format: wgpu::VertexFormat::Float32x2,
                            offset: 0,
                            shader_location: 0,
                        },
                        wgpu::VertexAttribute {
                            format: wgpu::VertexFormat::Float32,
                            offset: 8,
                            shader_location: 1,
                        },
                        wgpu::VertexAttribute {
                            format: wgpu::VertexFormat::Float32x4,
                            offset: 16,
                            shader_location: 2,
                        },
                    ],
                }],
            },
            primitive: wgpu::PrimitiveState {
                topology: wgpu::PrimitiveTopology::TriangleList,
                // NO culling. A translucent surface is visible from both sides, and a
                // cull would make the result depend on winding — which is the same
                // class of bug as depending on submission order.
                cull_mode: None,
                ..Default::default()
            },
            // NO depth attachment: the rasteriser must not reject a fragment. Depth
            // travels as a vertex attribute and is resolved per pixel.
            depth_stencil: None,
            multisample: crate::render::gpu::msaa_state(),
            fragment: Some(wgpu::FragmentState {
                module: &module,
                entry_point: Some("oit_gather_fs"),
                compilation_options: Default::default(),
                targets: &[Some(wgpu::ColorTargetState {
                    format: target_format,
                    blend: None,
                    // The gather writes only to storage. An empty mask says so on the
                    // pipeline, so a future edit that started returning real colour
                    // here would be visibly dead rather than double-composited.
                    write_mask: wgpu::ColorWrites::empty(),
                })],
            }),
            multiview_mask: None,
            cache: None,
        });

        let resolve = device.create_render_pipeline(&wgpu::RenderPipelineDescriptor {
            label: Some("l0_oit_resolve"),
            layout: Some(&pll),
            vertex: wgpu::VertexState {
                module: &module,
                entry_point: Some("oit_resolve_vs"),
                compilation_options: Default::default(),
                buffers: &[],
            },
            primitive: wgpu::PrimitiveState {
                topology: wgpu::PrimitiveTopology::TriangleList,
                ..Default::default()
            },
            depth_stencil: None,
            multisample: crate::render::gpu::msaa_state(),
            fragment: Some(wgpu::FragmentState {
                module: &module,
                entry_point: Some("oit_resolve_fs"),
                compilation_options: Default::default(),
                targets: &[Some(wgpu::ColorTargetState {
                    format: target_format,
                    // The resolve *is* the composite. Blending it again would apply
                    // the transparency twice.
                    blend: None,
                    write_mask: wgpu::ColorWrites::ALL,
                })],
            }),
            multiview_mask: None,
            cache: None,
        });

        Self {
            gather,
            resolve,
            bgl,
            uniform: device.create_buffer(&wgpu::BufferDescriptor {
                label: Some("l0_oit_uniform"),
                size: std::mem::size_of::<OitUniform>() as u64,
                usage: wgpu::BufferUsages::UNIFORM | wgpu::BufferUsages::COPY_DST,
                mapped_at_creation: false,
            }),
            heads: None,
            nodes: None,
            alloc: device.create_buffer(&wgpu::BufferDescriptor {
                label: Some("l0_oit_alloc"),
                size: 4,
                usage: wgpu::BufferUsages::STORAGE
                    | wgpu::BufferUsages::COPY_DST
                    | wgpu::BufferUsages::COPY_SRC,
                mapped_at_creation: false,
            }),
            bind: None,
            verts: None,
            vert_cap: 0,
            vertex_count: 0,
            size: (0, 0),
            capacity: 0,
            layers: 0,
        }
    }

    /// (Re)allocate the head-pointer and node buffers for `w × h` pixels with
    /// `layers` fragments of node storage per pixel. Idempotent within a size+layers.
    pub fn ensure(&mut self, device: &wgpu::Device, w: u32, h: u32, layers: u32) {
        let w = w.max(1);
        let h = h.max(1);
        let layers = layers.max(1);
        if self.size == (w, h) && self.layers == layers && self.heads.is_some() {
            return;
        }
        let pixels = u64::from(w) * u64::from(h);
        let heads = device.create_buffer(&wgpu::BufferDescriptor {
            label: Some("l0_oit_heads"),
            size: pixels * 4,
            usage: wgpu::BufferUsages::STORAGE | wgpu::BufferUsages::COPY_DST,
            mapped_at_creation: false,
        });
        let capacity = pixels * u64::from(layers);
        let nodes = device.create_buffer(&wgpu::BufferDescriptor {
            label: Some("l0_oit_nodes"),
            size: capacity * OIT_NODE_SIZE,
            usage: wgpu::BufferUsages::STORAGE | wgpu::BufferUsages::COPY_DST,
            mapped_at_creation: false,
        });
        self.bind = Some(device.create_bind_group(&wgpu::BindGroupDescriptor {
            label: Some("l0_oit_bind"),
            layout: &self.bgl,
            entries: &[
                wgpu::BindGroupEntry { binding: 0, resource: self.uniform.as_entire_binding() },
                wgpu::BindGroupEntry { binding: 1, resource: heads.as_entire_binding() },
                wgpu::BindGroupEntry { binding: 2, resource: nodes.as_entire_binding() },
                wgpu::BindGroupEntry { binding: 3, resource: self.alloc.as_entire_binding() },
            ],
        }));
        self.heads = Some(heads);
        self.nodes = Some(nodes);
        self.size = (w, h);
        self.layers = layers;
        self.capacity = u32::try_from(capacity).unwrap_or(u32::MAX);
    }

    /// Write this frame's uniform: viewport, list stride, node capacity, background.
    pub fn set_frame(&self, queue: &wgpu::Queue, background: [f32; 4]) {
        let (w, h) = self.size;
        queue.write_buffer(
            &self.uniform,
            0,
            bytemuck::bytes_of(&OitUniform {
                viewport: [w as f32, h as f32],
                dims: [w, h],
                background,
                capacity: self.capacity,
                _pad: [0; 3],
            }),
        );
    }

    /// Upload `batch`, growing the vertex buffer in powers of two.
    pub fn upload(&mut self, device: &wgpu::Device, queue: &wgpu::Queue, batch: &OitBatch) {
        let verts = batch.vertices();
        self.vertex_count = u32::try_from(verts.len()).unwrap_or(u32::MAX);
        if verts.is_empty() {
            return;
        }
        if self.vert_cap < verts.len() || self.verts.is_none() {
            let cap = verts.len().next_power_of_two();
            self.verts = Some(device.create_buffer(&wgpu::BufferDescriptor {
                label: Some("l0_oit_verts"),
                size: cap as u64 * OIT_VERTEX_STRIDE,
                usage: wgpu::BufferUsages::VERTEX | wgpu::BufferUsages::COPY_DST,
                mapped_at_creation: false,
            }));
            self.vert_cap = cap;
        }
        if let Some(vb) = &self.verts {
            queue.write_buffer(vb, 0, bytemuck::cast_slice(verts));
        }
    }

    /// Reset the per-frame lists: every head back to "empty" and the allocator to 0.
    ///
    /// A `clear_buffer` rather than a clear compute pass — which is the whole reason
    /// node links are 1-based. Zero is a free clear on every backend.
    pub fn reset(&self, encoder: &mut wgpu::CommandEncoder) {
        if let Some(heads) = &self.heads {
            encoder.clear_buffer(heads, 0, None);
        }
        encoder.clear_buffer(&self.alloc, 0, None);
    }

    /// **The frame.** Reset the lists, gather every fragment, then resolve into
    /// `target`. Returns the vertex count submitted — so "everything was clipped away"
    /// is distinguishable from "the pass never ran".
    ///
    /// `target` must be a `target_format` view of the size passed to [`Self::ensure`].
    pub fn record(&self, encoder: &mut wgpu::CommandEncoder, target: &wgpu::TextureView) -> u32 {
        let Some(bind) = &self.bind else { return 0 };
        self.reset(encoder);

        if self.vertex_count > 0 {
            if let Some(vb) = &self.verts {
                let mut rp = encoder.begin_render_pass(&wgpu::RenderPassDescriptor {
                    label: Some("l0_oit_gather_pass"),
                    // The attachment is a formality (the write mask is empty); binding
                    // the eventual target costs no extra memory.
                    color_attachments: &[Some(wgpu::RenderPassColorAttachment {
                        view: target,
                        resolve_target: None,
                        depth_slice: None,
                        ops: wgpu::Operations {
                            load: wgpu::LoadOp::Clear(wgpu::Color::TRANSPARENT),
                            store: wgpu::StoreOp::Store,
                        },
                    })],
                    depth_stencil_attachment: None,
                    timestamp_writes: None,
                    occlusion_query_set: None,
                    multiview_mask: None,
                });
                rp.set_pipeline(&self.gather);
                rp.set_bind_group(0, bind, &[]);
                rp.set_vertex_buffer(0, vb.slice(..));
                rp.draw(0..self.vertex_count, 0..1);
            }
        }

        {
            let mut rp = encoder.begin_render_pass(&wgpu::RenderPassDescriptor {
                label: Some("l0_oit_resolve_pass"),
                color_attachments: &[Some(wgpu::RenderPassColorAttachment {
                    view: target,
                    resolve_target: None,
                    depth_slice: None,
                    ops: wgpu::Operations {
                        // The resolve writes the background itself, from the uniform,
                        // so it does not depend on what the gather pass left behind.
                        load: wgpu::LoadOp::Clear(wgpu::Color::TRANSPARENT),
                        store: wgpu::StoreOp::Store,
                    },
                })],
                depth_stencil_attachment: None,
                timestamp_writes: None,
                occlusion_query_set: None,
                multiview_mask: None,
            });
            rp.set_pipeline(&self.resolve);
            rp.set_bind_group(0, bind, &[]);
            rp.draw(0..3, 0..1);
        }

        self.vertex_count
    }

    /// Read the device's own count of fragments the gather emitted this frame.
    ///
    /// Not a host-side tally: this is the bump allocator the shader `atomicAdd`ed, read
    /// back out of GPU memory. It is the assertion that distinguishes "the OIT frame is
    /// stable across submission orders" from "the OIT frame is stable because no
    /// fragment ever reached a list".
    ///
    /// Counts *attempts*, including allocations past `capacity` that were dropped — so
    /// comparing it to `capacity` tells a caller whether it overflowed.
    #[must_use]
    pub fn fragment_count(&self, device: &wgpu::Device, queue: &wgpu::Queue) -> u32 {
        let bytes = super::readback::read_buffer_range(device, queue, &self.alloc, 0, 4);
        if bytes.len() < 4 {
            return 0;
        }
        u32::from_le_bytes([bytes[0], bytes[1], bytes[2], bytes[3]])
    }

    /// Node-buffer capacity in fragments (`w · h · layers`).
    #[must_use]
    pub fn capacity(&self) -> u32 {
        self.capacity
    }

    /// Allocated size in physical pixels.
    #[must_use]
    pub fn size(&self) -> (u32, u32) {
        self.size
    }

    /// Whether the buffers are allocated.
    #[must_use]
    pub fn ready(&self) -> bool {
        self.bind.is_some()
    }

    /// Vertices submitted by the last [`Self::upload`].
    #[must_use]
    pub fn vertex_count(&self) -> u32 {
        self.vertex_count
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    /// The Rust `OitVertex` and the WGSL vertex attributes describe the same bytes.
    /// Offsets are quoted in [`OitPass::new`]; if the struct is reordered this is the
    /// guard that notices.
    #[test]
    fn vertex_layout_matches_the_shader() {
        assert_eq!(std::mem::size_of::<OitVertex>() as u64, OIT_VERTEX_STRIDE);
        assert_eq!(std::mem::offset_of!(OitVertex, pos), 0);
        assert_eq!(std::mem::offset_of!(OitVertex, depth), 8);
        assert_eq!(std::mem::offset_of!(OitVertex, color), 16);
        assert_eq!(std::mem::size_of::<OitUniform>(), 48, "the uniform is 3 × 16 B");
    }

    /// `OIT_MAX_LAYERS` is a Rust mirror of a WGSL `const`. Mirrors drift, so read the
    /// actual shader text rather than trusting the comment next to it.
    #[test]
    fn the_layer_count_constant_is_the_same_number_on_both_sides() {
        let want = format!("const OIT_LAYERS: u32 = {OIT_MAX_LAYERS}u;");
        assert!(
            OIT_WGSL.contains(&want),
            "OIT_MAX_LAYERS ({OIT_MAX_LAYERS}) must match the shader's OIT_LAYERS; looked for `{want}`"
        );
    }

    // `oit.wgsl`'s use of the ONE prelude is asserted by the shared loop in
    // `super::tests::every_shared_shader_takes_its_maths_from_the_one_prelude`, which
    // this shader was added to rather than given a private twin of (LAW #5).

    /// The gather must not be able to reject a fragment. Both of these are how that
    /// would silently happen, and both are stated in the source as deliberate.
    #[test]
    fn the_gather_neither_depth_tests_nor_culls() {
        // Not a state round-trip: this reads the *shader text* for the two things that
        // would make the linked list incomplete, and the pipeline setters live in one
        // function whose source is checked by the compiler to have those literals.
        assert!(
            OIT_WGSL.contains("o.clip = vec4<f32>(px_to_ndc(v.pos_px, u.viewport), 0.0, 1.0);"),
            "the gather must emit a constant z — a varying z with a depth test would cull"
        );
    }

    /// A quad is two triangles over its rect, sharing the diagonal, at one depth.
    #[test]
    fn a_quad_is_two_triangles_of_one_depth_over_its_rect() {
        let mut b = OitBatch::new();
        let r = egui::Rect::from_min_max(egui::pos2(10.0, 20.0), egui::pos2(30.0, 50.0));
        b.push_quad(r, [0.25, 0.5, 0.75, 0.5], 3.5);
        assert_eq!(b.len(), 6);
        assert_eq!(b.tri_count(), 2);
        assert!(b.vertices().iter().all(|v| v.depth == 3.5), "one depth");
        assert!(b.vertices().iter().all(|v| v.color == [0.25, 0.5, 0.75, 0.5]), "one colour");
        let xs: Vec<f32> = b.vertices().iter().map(|v| v.pos[0]).collect();
        let ys: Vec<f32> = b.vertices().iter().map(|v| v.pos[1]).collect();
        assert_eq!(xs.iter().cloned().fold(f32::MAX, f32::min), 10.0);
        assert_eq!(xs.iter().cloned().fold(f32::MIN, f32::max), 30.0);
        assert_eq!(ys.iter().cloned().fold(f32::MAX, f32::min), 20.0);
        assert_eq!(ys.iter().cloned().fold(f32::MIN, f32::max), 50.0);
        // Both triangles carry the min→max diagonal, which is what makes the shared
        // edge a genuine depth+colour tie.
        assert_eq!(b.vertices()[0].pos, [10.0, 20.0]);
        assert_eq!(b.vertices()[2].pos, [30.0, 50.0]);
        assert_eq!(b.vertices()[3].pos, [10.0, 20.0]);
        assert_eq!(b.vertices()[4].pos, [30.0, 50.0]);
    }

    /// `permuted` reorders whole triangles and never splits one — the property the
    /// order-independence proof depends on for its permutations to be *the same scene*.
    #[test]
    fn permuting_reorders_whole_triangles_and_preserves_the_multiset() {
        let mut b = OitBatch::new();
        for i in 0..4u32 {
            let x = i as f32 * 10.0;
            b.push_quad(
                egui::Rect::from_min_max(egui::pos2(x, 0.0), egui::pos2(x + 5.0, 5.0)),
                [i as f32 / 4.0, 0.0, 0.0, 0.5],
                i as f32,
            );
        }
        let n = b.tri_count();
        assert_eq!(n, 8);
        let rev: Vec<usize> = (0..n).rev().collect();
        let p = b.permuted(&rev);
        assert_eq!(p.len(), b.len(), "same vertex count");

        // Every triangle survives intact: each 3-vertex group of the permutation is a
        // 3-vertex group of the original.
        let groups = |x: &OitBatch| -> Vec<[OitVertex; 3]> {
            x.vertices().chunks(3).map(|c| [c[0], c[1], c[2]]).collect()
        };
        let (og, pg) = (groups(&b), groups(&p));
        assert_eq!(pg.len(), og.len());
        for g in &pg {
            assert!(og.contains(g), "each permuted triangle is an original triangle");
        }
        // And it genuinely reordered — otherwise the whole proof is vacuous.
        assert_ne!(pg, og, "the reversal must actually change the submission order");
        assert_eq!(pg.iter().rev().cloned().collect::<Vec<_>>(), og, "…by reversing it");
    }

    /// An out-of-range permutation index drops that triangle instead of panicking, and
    /// an empty order yields an empty batch.
    #[test]
    fn permuting_is_total() {
        let mut b = OitBatch::new();
        b.push_quad(egui::Rect::from_min_max(egui::pos2(0.0, 0.0), egui::pos2(4.0, 4.0)), [1.0; 4], 0.0);
        assert_eq!(b.permuted(&[99]).len(), 0, "out-of-range triangle is dropped");
        assert_eq!(b.permuted(&[]).len(), 0);
        assert_eq!(b.permuted(&[0, 1]).len(), 6);
    }
}