The animation engine for agents: blazingly fast math and 3D videos with Manim's Python API, on a Rust GPU core.
Python
// A view's paths, drawn exactly: every pixel's coverage is the area of the object inside it, computed
// from the control points; no tessellation, no stencil, no multisampling. A path in a 3D view is the
// same path seen through the camera's projective map (lines stay lines: its exact area on screen is
// still its edges' trapezoids), lying at a depth plane over the view.
//
// Per frame, one compute pass flattens every curve of every path object into exactly as many
// segments as its size on screen needs (Wang's bound at 1/32 px; a curve wholly off the object's
// box as its chord, which casts the same winding into the box), each record in a slot its object
// reserves for it, a function of the slot alone (no counters: the same function runs wherever
// slots are filled). One raster pass adds each record's exact area into its object's rectangles of
// a float atlas (additive, in steps f32 adds exactly: the order is free): a fill edge its signed
// trapezoid down to the object's line y = r (the terms of the line cancel around a closed path, so
// the sum is the winding area); a stroke its pieces, which abut along their shared edges (their
// union: the sum, clamped): rectangles along the curve's exact normals, cut at its dashes' ends; a
// joint where it turns (a miter's kite, a bevel's triangle, a round's fan); a cap at each end of
// what it shows (a square's rectangle, a round's fan). One compute pass composites each 16×16 tile
// of the view over the objects whose boxes reach it, in depth order (the draw order among equal
// depths: all of a 2D view's), keeping each pixel as two regions split by a line: a partial layer is
// the half-plane with its coverage as area and its coverage gradient as normal, so shared and
// coincident edges do not leak what lies under them. A 2D view's points and meshes arrive as
// premultiplied layers drawn by the raster pipeline (`blend.wgsl`); a 3D view's raster base (its
// meshes and points, z-buffered) as one more layer, at its depth per pixel.
struct Frame {
size: vec4<f32>, // view width, height (pixels); atlas width, height
tiles: vec4<u32>, // tiles across, down; record slots (fill, stroke)
counts: vec4<u32>, // objects; 1: what lies under is the texture `base` (else the background); a 3D view's
// raster base: 0 none, 1 a layer (`base`, `base_depth`), 2 laid (what lies behind it is
// hidden); bit 1: what lies under carries light (`base_light`), bit 2: the group's pixels
// carry theirs to the next group or the view's glow (`light_out`), not shown yet
background: vec4<f32>, // premultiplied
depth: vec4<f32>, // how near behind a 3D view's raster base a path still shows (drawn on it): a share of its depth
lists: vec4<u32>, // a 3D view's see-through fragments: listed (1), in rows [y, z) (heads cleared); samples
// a 3D view's light, for its paths with a material (`light.wgsl`): clip -> world; the unit vector toward the
// viewer; where it sees from (w = 1: in perspective); its lights, the exposure, the tone mapping, its bloom
// (`bloom.rs`); the lights
inverse: mat4x4<f32>,
toward: vec4<f32>,
eye: vec4<f32>,
lighting: vec4<f32>,
lights: array<Light, 8>,
harmonics: array<vec4<f32>, 9>, // its environment's diffuse light (`environment.rs`)
occlusion: vec4<f32>, // its ambient occlusion: how much (0: none), how far (`occlusion.rs`)
};
struct Object {
t1x: vec4<f32>, t1y: vec4<f32>, // term 1: canonical point -> local pixel (rows x, y)
t2x: vec4<f32>, t2y: vec4<f32>, // term 2 (a morph's); zero otherwise
t1w: vec4<f32>, t2w: vec4<f32>, // rows w of the projective map (a 2D view's: (0, 0, 0, 1) and 0): pixel = (x, y) / w
rect: vec4<f32>, // its box: corner in view pixels (y down), size
atlas: vec4<u32>, // coverage origins (x | y << 16): fill, stroke, background; a raster layer's origin (NONE: absent)
ids: vec4<u32>, // first curve of term 1, of term 2 (NONE), first subpath, subpaths
params: vec4<f32>, // window lo, hi (u); stroke half-width, background half-width (px)
dash: vec4<f32>, // period, duty, phase (u); the fill's reference line r (local y)
scale: vec4<f32>, // pixels per canonical unit of term 1, 2; reach past the box (px); curves
place: vec4<f32>, // depth z = a x + b y + c over view pixels (a 2D view's: 0); CE's light for gradients
flags: vec4<u32>, // its strokes' depth per pixel (x: not planar); reaching behind the near plane (y)
slots: vec4<u32>, // its first fill slot, first stroke slot; segments a curve is cut into at most,
// dash windows a segment meets at most (1: not dashed)
pieces: vec4<u32>, // records a joint takes, a cap; dash windows a subpath meets at most (1: not dashed)
fill: vec4<f32>, // straight RGBA; alpha < 0: gradient rows
stroke: vec4<f32>,
background: vec4<f32>,
gradient: vec4<f32>, // axis in view pixels (y up): origin, direction / |direction|²
brush: vec4<u32>, // fill rows (offset, count), stroke rows (offset, count)
brush2: vec4<u32>, // paint 2's fill rows, stroke rows offsets; how far it is mixed in (f32 bits)
material: vec4<f32>, // metallic, roughness, reflectance; 1 where its fill is lit by the view's lights
normal: vec4<f32>, // which way its plane faces, in the world (a lit fill's)
t1z: vec4<f32>, t2z: vec4<f32>, // rows of terms 1, 2's depth from the far plane (z - w): a stroke's depth z / w
near: vec4<f32>, // a clipped object's shadows on the near plane (`shadow`)
};
const NONE: u32 = 0xffffffffu;
// The rest it reads (the CPU's arrays, the records, the lists, a non-planar path's strokes' depths, a 3D view's raster
// base sample by sample) comes through its head's loaders (`vector_buffers.wgsl`); its compute passes' entries are in
// `vector_compute.wgsl`.
@group(0) @binding(0) var<uniform> frame: Frame;
@group(1) @binding(0) var atlas: texture_2d<f32>;
@group(1) @binding(1) var layers: texture_2d<f32>; // points and meshes, premultiplied
@group(1) @binding(2) var base: texture_2d<f32>; // what lies under (counts.y = 1), or the raster base
@group(1) @binding(4) var base_depth: texture_2d<f32>; // a 3D view's raster base's depth (else 1x1 far)
// its lights' shadow maps (`shadow.rs`; 1x1 where none) and their comparison
@group(1) @binding(10) var shadow_maps: texture_depth_2d_array;
@group(1) @binding(11) var shadow_compare: sampler_comparison;
// the DFG table, bilinearly (`light.wgsl`)
@group(1) @binding(12) var dfg_table: texture_2d<f32>;
@group(1) @binding(13) var dfg_linear: sampler;
@group(1) @binding(15) var environment: texture_cube<f32>;
@group(1) @binding(16) var occlusion: texture_2d<f32>; // its ambient occlusion (`occlusion.rs`; 1x1 where it has none)
// where what lies under carries light (`frame.counts.w` bit 1): the raster base's light (`blend.wgsl`'s `Base`), or
// what the group before left; `base` its paint then (1x1 where none)
@group(1) @binding(17) var base_light: texture_2d<f32>;
// a 3D view's see-through points among its layers (`points_before`): the depths of each pixel's nearest layers
// (`bound`), and its slabs, layer j - 1 the points between the j-th and the (j+1)-th of them (else 1x1)
@group(1) @binding(20) var slab_bounds: texture_2d<f32>;
@group(1) @binding(21) var slabs: texture_2d_array<f32>;
// A 3D view's see-through fragments (`blend.wgsl` appends them): per pixel a list, its head's index + 1 (0: none)
struct Node {
depth: f32, // at the pixel's centre
color: u32, // straight RGBA8
key: u32, // record << 11 | samples covered << 3 | winding sign << 2 | kind (0 mesh, 3 stroke)
next: u32, // the next node + 1 (0: none)
};
// A record: a fill edge (a = p0, p1; info.x = object) or a stroke piece (a, b = the quad's
// corners; info.xy = object, layer; info.zw = its depth where it begins and ends (f32 bits; negative: none): a
// non-planar path's).
struct Seg {
a: vec4<f32>,
b: vec4<f32>,
info: vec4<u32>,
};
// The view's lights and shadow maps, as `light.wgsl` reads them.
fn light_count() -> u32 {
return u32(frame.lighting.x);
}
fn light_at(i: u32) -> Light {
return frame.lights[i];
}
fn shadow_compare_at(uv: vec2<f32>, layer: i32, depth: f32) -> f32 {
return textureSampleCompareLevel(shadow_maps, shadow_compare, uv, layer, depth);
}
fn shadow_texel() -> vec2<f32> {
return 1.0 / vec2<f32>(textureDimensions(shadow_maps));
}
fn dfg_at(NoV: f32, perceptual: f32) -> vec2<f32> {
return textureSampleLevel(dfg_table, dfg_linear, vec2<f32>(NoV, perceptual), 0.0).xy;
}
fn environment_at(d: vec3<f32>, level: f32) -> vec3<f32> {
return textureSampleLevel(environment, dfg_linear, d, level).rgb;
}
fn harmonic(i: u32) -> vec3<f32> {
return frame.harmonics[i].xyz;
}
// Straight RGBA8 (a byte a channel, red lowest) as floats.
fn rgba8(c: u32) -> vec4<f32> {
return vec4<f32>(f32(c & 0xffu), f32((c >> 8u) & 0xffu), f32((c >> 16u) & 0xffu), f32(c >> 24u)) / 255.0;
}
// ── curves ────────────────────────────────────────────────────────────────────
fn bernstein(t: f32) -> vec4<f32> {
let s = 1.0 - t;
return vec4<f32>(s * s * s, 3.0 * s * s * t, 3.0 * s * t * t, t * t * t);
}
fn dbernstein(t: f32) -> vec4<f32> {
let s = 1.0 - t;
return vec4<f32>(-3.0 * s * s, 3.0 * s * s - 6.0 * s * t, 6.0 * s * t - 3.0 * t * t, 3.0 * t * t);
}
// The four control points from `first` with weights w (Bernstein or its derivative).
fn weighted(first: u32, w: vec4<f32>) -> vec3<f32> {
var acc = vec3<f32>(0.0);
acc = fma(vec3<f32>(w.x), control(first).xyz, acc);
acc = fma(vec3<f32>(w.y), control(first + 1u).xyz, acc);
acc = fma(vec3<f32>(w.z), control(first + 2u).xyz, acc);
acc = fma(vec3<f32>(w.w), control(first + 3u).xyz, acc);
return acc;
}
// Curve c of object o with weights w (Bernstein or its derivative), homogeneous: (x, y, w) of a point
// (affine = true) or of a direction; local pixels are (x, y) / w. A morph adds its second term, curve
// by curve.
fn curve_h(o: u32, c: u32, w: vec4<f32>, affine: bool) -> vec3<f32> {
let h = vec4<f32>(weighted(4u * (ids_of(o).x + c), w), select(0.0, 1.0, affine));
var p = vec3<f32>(dot(t1x_of(o), h), dot(t1y_of(o), h), dot(t1w_of(o), h));
if (ids_of(o).y != NONE) {
// Bernstein weights sum to 1: term 2's translation (none of the camera's) once
let g = vec4<f32>(weighted(4u * (ids_of(o).y + c), w), select(0.0, 1.0, affine));
p += vec3<f32>(dot(t2x_of(o), g), dot(t2y_of(o), g), dot(t2w_of(o), g));
}
return p;
}
// A point of curve c (weights summing to 1), in local pixels.
fn curve(o: u32, c: u32, w: vec4<f32>, affine: bool) -> vec2<f32> {
let h = curve_h(o, c, w, affine);
return h.xy / h.z;
}
// The derivative of curve c at t on screen (local pixels per unit t): the quotient rule of the
// projective map (a 2D view's w is 1 and its derivative 0: the curve's own derivative).
fn derivative(o: u32, c: u32, t: f32) -> vec2<f32> {
let p = curve_h(o, c, bernstein(t), true);
let d = curve_h(o, c, dbernstein(t), false);
return (d.xy * p.z - p.xy * d.z) / (p.z * p.z);
}
fn at(o: u32, c: u32, t: f32) -> vec2<f32> {
return curve(o, c, bernstein(t), true);
}
// Whether curve c's control points all lie on one side beyond the object's box and its strokes' reach: no pixel of
// the box sees the curve or its stroke.
fn off_box(o: u32, c: u32) -> bool {
var lo = vec2<f32>(1e30);
var hi = vec2<f32>(-1e30);
for (var k = 0u; k < 4u; k++) {
var w = vec4<f32>(0.0);
w[k] = 1.0;
let p = curve(o, c, w, true);
lo = min(lo, p);
hi = max(hi, p);
}
let m = scale_of(o).z;
return hi.x < -m || hi.y < -m || lo.x > rect_of(o).z + m || lo.y > rect_of(o).w + m;
}
// The segments curve c needs this frame: Wang's bound at 1/32 px (at most 256; at most the object's `slots.z`).
fn wang(o: u32, c: u32) -> u32 {
var d = control(4u * (ids_of(o).x + c)).w * scale_of(o).x;
if (ids_of(o).y != NONE) {
d += control(4u * (ids_of(o).y + c)).w * scale_of(o).y;
}
return clamp(u32(ceil(sqrt(24.0 * d))), 1u, 256u);
}
// Whether curve c is off object o's box: its control points tell, unless the object reaches behind the near plane
// (where they do not project).
fn off(o: u32, c: u32) -> bool {
return flags_of(o).y == 0u && off_box(o, c);
}
// A fill's segments of curve c: Wang's; one, the chord, off the box (it casts the same winding into it).
fn segments(o: u32, c: u32) -> u32 {
return select(wang(o, c), 1u, off(o, c));
}
// Whether object o's strokes are dashed: a window over u of period dash.x, showing dash.y of it from dash.z.
fn dashed(o: u32) -> bool {
let d = dash_of(o);
return d.x > 0.0 && d.y < 1.0;
}
// A stroke's segments of curve c: Wang's; a dashed stroke's, as many as its object's most (`slots.z`), so that a
// segment meets a known number of dash windows.
fn stroke_segments(o: u32, c: u32) -> u32 {
return select(wang(o, c), slots_of(o).z, dashed(o));
}
// The visible parameter range [t0, t1] of segment i of n of curve c (window applied); t1 <= t0: hidden.
fn piece(o: u32, c: u32, i: u32, n: u32) -> vec2<f32> {
let w = params_of(o).xy - f32(c);
let t0 = max(f32(i) / f32(n), clamp(w.x, 0.0, 1.0));
let t1 = min(f32(i + 1u) / f32(n), clamp(w.y, 0.0, 1.0));
return vec2<f32>(t0, t1);
}
// The point at parameter u (curve index + t) of object o's shape.
fn at_u(o: u32, u: f32, last_curve: u32) -> vec2<f32> {
let c = min(u32(max(floor(u), 0.0)), last_curve);
return at(o, c, clamp(u - f32(c), 0.0, 1.0));
}
// ── what reaches behind the camera ────────────────────────────────────────────
//
// An object whose box crosses the near plane (`flags.y`) shows what lies in front of it: a fill edge is cut where it
// crosses it, and what lies behind is replaced by its shadow on it (`shadow`), which encloses no point in front, so
// every winding in front is the shape's own; a stroke shows the pieces in front, cut square at the crossing.
// A point of an object's shape before its map: term 1's, term 2's (a morph's; else 0), homogeneous.
struct Spot {
a: vec4<f32>,
b: vec4<f32>,
};
fn spot(o: u32, c: u32, t: f32) -> Spot {
let w = bernstein(t);
var s = Spot(vec4<f32>(weighted(4u * (ids_of(o).x + c), w), 1.0), vec4<f32>(0.0));
if (ids_of(o).y != NONE) {
s.b = vec4<f32>(weighted(4u * (ids_of(o).y + c), w), 1.0);
}
return s;
}
fn spot_u(o: u32, u: f32, last_curve: u32) -> Spot {
let c = min(u32(max(floor(u), 0.0)), last_curve);
return spot(o, c, clamp(u - f32(c), 0.0, 1.0));
}
// Its clip z (its depth from the far plane, plus w): in front of the near plane where it is not negative.
fn spot_z(o: u32, s: Spot) -> f32 {
return dot(t1z_of(o) + t1w_of(o), s.a) + dot(t2z_of(o) + t2w_of(o), s.b);
}
// Where it is on the view (local pixels).
fn spot_xy(o: u32, s: Spot) -> vec2<f32> {
let h = vec3<f32>(dot(t1x_of(o), s.a) + dot(t2x_of(o), s.b), dot(t1y_of(o), s.a) + dot(t2y_of(o), s.b), dot(t1w_of(o), s.a) + dot(t2w_of(o), s.b));
return h.xy / h.z;
}
// Its shadow on the near plane: term 1's point moved along clip z's gradient in its shape's plane, to z = 0.
fn shadow(o: u32, s: Spot) -> Spot {
let n = near_of(o);
return Spot(vec4<f32>(s.a.xyz - spot_z(o, s) * n.w * n.xyz, 1.0), s.b);
}
// The point of the chord from s0 to s1 (straight on the view: the map keeps lines) where it crosses the near plane.
fn crossing(o: u32, s0: Spot, s1: Spot) -> vec2<f32> {
let z0 = spot_z(o, s0);
let f = z0 / (z0 - spot_z(o, s1));
return spot_xy(o, Spot(mix(s0.a, s1.a, f), mix(s0.b, s1.b, f)));
}
// Where a point of a clipped object shows: itself in front of the near plane, else its shadow on it.
fn shown(o: u32, s: Spot, front: bool) -> vec2<f32> {
if (front) {
return spot_xy(o, s);
}
return spot_xy(o, shadow(o, s));
}
// Record `half` of the fill edge from s0 to s1 of a clipped object, its ends where they show: whole (half 0) where
// it does not cross the near plane, else from s0 to the crossing (half 0) and from there to s1 (half 1).
fn clipped_edge(o: u32, s0: Spot, s1: Spot, half: u32) -> Seg {
let front = vec2<bool>(spot_z(o, s0) >= 0.0, spot_z(o, s1) >= 0.0);
let p0 = shown(o, s0, front.x);
let p1 = shown(o, s1, front.y);
if (front.x == front.y) {
if (half == 0u) {
return fill_edge(o, p0, p1);
}
return none();
}
let q = crossing(o, s0, s1);
if (half == 0u) {
return fill_edge(o, p0, q);
}
return fill_edge(o, q, p1);
}
// ── the exact area of an edge in a pixel ──────────────────────────────────────
fn ramp(t: f32) -> f32 {
if (t <= 0.0) {
return 0.0;
}
if (t < 1.0) {
return 0.5 * t * t;
}
return t - 0.5;
}
// The signed area of pixel px (its corner) between the edge p0 -> p1 and the line y = r.
fn edge_area(p0: vec2<f32>, p1: vec2<f32>, px: vec2<f32>, r: f32) -> f32 {
let lo = min(p0.x, p1.x);
let hi = max(p0.x, p1.x);
let xa = max(lo, px.x);
let xb = min(hi, px.x + 1.0);
if (xb <= xa) {
return 0.0;
}
let m = (p1.y - p0.y) / (p1.x - p0.x);
let ya = p0.y + m * (xa - p0.x) - px.y;
let yb = p0.y + m * (xb - p0.x) - px.y;
var mean: f32;
if (abs(yb - ya) < 1e-5) {
mean = clamp(0.5 * (ya + yb), 0.0, 1.0);
} else {
mean = (ramp(yb) - ramp(ya)) / (yb - ya);
}
let s = select(-1.0, 1.0, p0.x > p1.x);
return s * (xb - xa) * (mean - clamp(r - px.y, 0.0, 1.0));
}
// ── pass 0: flatten (compute; a thread per slot) ──────────────────────────────
//
// An object reserves a slot for every record its flattening can write (`vector.rs` counts them): a fill edge per
// segment of each curve (as many as its most, `slots.z`) and a closing edge per subpath; for each stroke layer, a
// body piece per segment and dash window it meets (`slots.w`), a joint's records at each curve's start, and a cap's
// at each end of what each subpath shows in each dash window it meets. A slot's record is a function of the slot
// alone (no counter, no order: the atlas adds records exactly, in any order); a slot whose record is not there this
// frame (a curve cut into fewer segments, a piece hidden, a turn not taken) holds none, which draws nothing.
fn none() -> Seg {
return Seg(vec4<f32>(0.0), vec4<f32>(0.0), vec4<u32>(NONE, 0u, 0u, 0u));
}
fn fill_edge(o: u32, p0: vec2<f32>, p1: vec2<f32>) -> Seg {
if (p0.x == p1.x) {
return none(); // a vertical edge adds no area
}
return Seg(vec4<f32>(p0, p1), vec4<f32>(0.0), vec4<u32>(o, 0u, 0u, 0u));
}
fn stroke_piece(o: u32, layer: u32, q0: vec2<f32>, q1: vec2<f32>, q2: vec2<f32>, q3: vec2<f32>, depth: vec2<f32>) -> Seg {
return Seg(vec4<f32>(q0, q1), vec4<f32>(q2, q3), vec4<u32>(o, layer, bitcast<u32>(depth.x), bitcast<u32>(depth.y)));
}
// The depth at parameter t of curve c, where object o's strokes keep their depth per pixel (else NO_DEPTH).
fn curve_depth(o: u32, c: u32, t: f32) -> f32 {
if (flags_of(o).x == 0u) {
return NO_DEPTH;
}
let h = vec4<f32>(weighted(4u * (ids_of(o).x + c), bernstein(t)), 1.0);
var zw = vec2<f32>(dot(t1z_of(o), h), dot(t1w_of(o), h));
if (ids_of(o).y != NONE) {
let g = vec4<f32>(weighted(4u * (ids_of(o).y + c), bernstein(t)), 1.0);
zw += vec2<f32>(dot(t2z_of(o), g), dot(t2w_of(o), g));
}
return clamp(zw.x / zw.y, -1.0, 0.0);
}
// A direction's unit normal; none for a direction shorter than a thousandth of a pixel (below
// the rounding of the points it comes from: no direction at all).
fn perp(d: vec2<f32>) -> vec2<f32> {
let l = length(d);
return select(vec2<f32>(0.0), vec2<f32>(-d.y, d.x) / l, l > 1e-3);
}
// The unit normal of curve c at t (the chord's where the derivative vanishes).
fn normal_at(o: u32, c: u32, t: f32, chord: vec2<f32>) -> vec2<f32> {
let d = derivative(o, c, t);
return select(perp(chord), perp(d), dot(d, d) > 1e-6);
}
// The normal the stroke's body has at t of curve c (`normal_at` with the chord of its piece that
// begins there (ahead) or ends there).
fn body_normal(o: u32, c: u32, t: f32, ahead: bool) -> vec2<f32> {
let d = derivative(o, c, t);
if (dot(d, d) > 1e-6) {
return perp(d);
}
let n = stroke_segments(o, c);
let x = t * f32(n);
let p = piece(o, c, min(u32(select(max(ceil(x) - 1.0, 0.0), floor(x), ahead)), n - 1u), n);
return perp(at(o, c, p.y) - at(o, c, p.x));
}
// Whether curve c is a point on screen (its control points within a thousandth of a pixel): it has
// no direction, and a joint joins the curves on either side of it.
fn degenerate(o: u32, c: u32) -> bool {
let p = at(o, c, 0.0);
var spread = 0.0;
for (var k = 1u; k < 4u; k++) {
var w = vec4<f32>(0.0);
w[k] = 1.0;
spread = max(spread, length(curve(o, c, w, true) - p));
}
return spread <= 1e-3;
}
// A stroke's style (`Paint.brush2.w`): its cap | its joint << 2; 0 is a butt cap and a miter joint.
const ROUND: u32 = 1u; // a cap's or a joint's
const SQUARE: u32 = 2u; // a cap's
const BEVEL: u32 = 2u; // a joint's
const PI: f32 = 3.14159265358979;
// A piece of the stroke's body: from p0 to p1, across their normals, `half` to each side.
fn body(o: u32, layer: u32, half: f32, p0: vec2<f32>, n0: vec2<f32>, p1: vec2<f32>, n1: vec2<f32>, depth: vec2<f32>) -> Seg {
return stroke_piece(o, layer, p0 - n0 * half, p0 + n0 * half, p1 + n1 * half, p1 - n1 * half, depth);
}
// The triangles of a round piece's fan over `angle` at radius `half`: its chords within 1/32 px of
// the arc (`vector.rs` reserves records for half a turn).
fn fan(angle: f32, half: f32) -> u32 {
let step = 2.0 * acos(max(1.0 - 0.03125 / half, -1.0));
return clamp(u32(ceil(angle / step)), 1u, 128u);
}
// Record r of a round piece: the sector of the disk of radius `half` at p from direction a to
// direction b, over `angle`, turning toward w (a ⟂ w); a fan, two triangles to a record.
fn fan_record(o: u32, layer: u32, p: vec2<f32>, a: vec2<f32>, w: vec2<f32>, b: vec2<f32>, angle: f32, half: f32, depth: f32, r: u32) -> Seg {
let k = fan(angle, half);
let i = 2u * r;
if (i >= k) {
return none();
}
let step = angle / f32(k);
let e = step * f32(i);
let f = step * f32(i + 1u);
let g = step * f32(i + 2u);
let first = select(p + half * (cos(e) * a + sin(e) * w), p + half * a, i == 0u);
let q = select(p + half * (cos(f) * a + sin(f) * w), p + half * b, i + 1u >= k);
let s = select(p + half * (cos(g) * a + sin(g) * w), p + half * b, i + 2u >= k);
return stroke_piece(o, layer, p, first, q, s, vec2<f32>(depth));
}
// Record r of the joint at j where a curve arriving with normal m meets one leaving with normal
// nn, turning: the outer side between the bodies' square ends — a miter's kite (past the miter
// limit, 10: a miter ten widths long, a bevel), a bevel's triangle, a round's sector.
fn joint_record(o: u32, layer: u32, j: vec2<f32>, m: vec2<f32>, nn: vec2<f32>, half: f32, style: u32, depth: f32, r: u32) -> Seg {
let cross = nn.x * m.y - nn.y * m.x;
let side = select(-1.0, 1.0, cross > 0.0); // a right turn: the outer side is +n
let u0 = side * m;
let u1 = side * nn;
if (style == ROUND) {
// turning as the path does, from its heading (a reversal's lies ahead of it)
return fan_record(o, layer, j, u0, vec2<f32>(m.y, -m.x), u1, atan2(abs(cross), dot(m, nn)), half, depth, r);
}
if (r > 0u) {
return none();
}
let s = u1 + u0;
let l = length(s);
var tip = j + 0.5 * half * s; // the bevel's middle
if (style != BEVEL && l >= 1e-6) {
let dir = s / l;
let sine = dot(dir, u1); // of half the angle between the pieces: the miter is 1 / sine widths long
if (sine >= 0.1) {
tip = j + dir * (half / sine);
}
}
return stroke_piece(o, layer, j, j + side * half * m, tip, j + side * half * nn, vec2<f32>(depth));
}
// Record r of a cap at an end p of the stroke, whose body has normal n there and lies toward −e:
// a square's rectangle or a round's half-disk.
fn cap_record(o: u32, layer: u32, p: vec2<f32>, n: vec2<f32>, e: vec2<f32>, half: f32, style: u32, depth: f32, r: u32) -> Seg {
if (style == ROUND) {
return fan_record(o, layer, p, n, e, -n, PI, half, depth, r);
}
if (style != SQUARE || r > 0u) {
return none();
}
return stroke_piece(o, layer, p - half * n, p + half * n, p + half * (n + e), p + half * (e - n), vec2<f32>(depth));
}
// Record r of the cap at the start (or end) of a shown stretch [lo, hi] of a subpath, where the
// stroke is drawn from, stepping in past curves that are a point. A stretch that is all one point
// has no direction: its caps face along x (a round pair is a dot).
fn end_cap(o: u32, layer: u32, half: f32, lo: f32, hi: f32, start: bool, style: u32, r: u32) -> Seg {
var c = u32(select(ceil(hi) - 1.0, floor(lo), start));
var t = select(hi - f32(c), lo - f32(c), start);
var drawn = !degenerate(o, c);
for (var k = 0u; k < 64u && !drawn; k++) {
if (start && f32(c + 1u) < hi) {
c += 1u;
t = 0.0;
} else if (!start && f32(c) > lo) {
c -= 1u;
t = 1.0;
} else {
break;
}
drawn = !degenerate(o, c);
}
if (flags_of(o).y != 0u && spot_z(o, spot(o, c, t)) < 0.0) {
return none(); // behind the near plane: the stroke ends at its cut
}
let p = at(o, c, t);
let out = select(1.0, -1.0, start);
var n = vec2<f32>(0.0, 1.0);
var toward = vec2<f32>(out, 0.0);
if (drawn) {
n = body_normal(o, c, t, start);
toward = out * vec2<f32>(n.y, -n.x);
}
return cap_record(o, layer, p, n, toward, half, style, curve_depth(o, c, t), r);
}
// The curve the stroke continues into across the start (next = false) or end (next = true) of
// curve c; NONE where it ends there: an open end, or the reveal window's edge (a closed subpath's
// seam joins only when the whole loop shows).
fn neighbour(o: u32, c: u32, next: bool) -> u32 {
let w = params_of(o).xy;
for (var s = 0u; s < ids_of(o).w; s++) {
let sub = subpath(ids_of(o).z + s);
if (c >= sub.x && c < sub.y) {
let whole = w.x <= f32(sub.x) && w.y >= f32(sub.y);
if (next) {
if (c + 1u < sub.y) {
return select(NONE, c + 1u, w.x < f32(c + 1u) && w.y > f32(c + 1u));
}
return select(NONE, sub.x, sub.z != 0u && whole);
}
if (c > sub.x) {
return select(NONE, c - 1u, w.x < f32(c) && w.y > f32(c));
}
return select(NONE, sub.y - 1u, sub.z != 0u && whole);
}
}
return NONE;
}
// Whether the dashes show the stroke on both sides of where one curve ends (u = end) and the next
// begins (u = start), and between: a joint is drawn only inside a dash (end > start: across a
// closed subpath's seam).
fn dashes_join(o: u32, end: f32, start: f32) -> bool {
let d = dash_of(o);
if (d.x <= 0.0 || d.y >= 1.0) {
return true;
}
let a = (end - d.z) / d.x;
let b = (start - d.z) / d.x;
return fract(a) > 0.0 && fract(a) <= d.y && fract(b) < d.y && (end > start || floor(a) == floor(b));
}
// Whether a subpath of object o goes on across its seam: closed, shown whole, its dashes showing
// on both sides; one that is all one point has no seam to go on across (its caps make it a dot).
fn seam(o: u32, sub: vec4<u32>) -> bool {
let w = params_of(o).xy;
if (!(sub.z != 0u && w.x <= f32(sub.x) && w.y >= f32(sub.y) && dashes_join(o, f32(sub.y), f32(sub.x)))) {
return false;
}
var c = sub.x;
for (var k = 0u; k < 64u && c < sub.y && degenerate(o, c); k++) {
c += 1u;
}
return c < sub.y;
}
// The object whose slots (k = 0: fill, 1: stroke) hold slot q: the last whose first is at most q.
fn owner(q: u32, k: u32) -> u32 {
var lo = 0u;
var hi = frame.counts.x;
while (hi - lo > 1u) {
let mid = (lo + hi) / 2u;
if (slots_of(mid)[k] <= q) {
lo = mid;
} else {
hi = mid;
}
}
return lo;
}
// Fill slot q: segment i of curve c (a curve cut into fewer has none past them), or a subpath's
// closing edge, from where its window ends back to where it starts.
fn fill_slot(q: u32) -> Seg {
let o = owner(q, 0u);
let clipped = flags_of(o).y != 0u;
var l = q - slots_of(o).x;
let half = l % 2u;
if (clipped) {
l /= 2u;
}
let n = slots_of(o).z;
let edges = u32(scale_of(o).w) * n;
if (l < edges) {
let c = l / n;
let i = l % n;
let m = segments(o, c);
let t = piece(o, c, i, m);
if (i >= m || t.y <= t.x) {
return none();
}
if (clipped) {
return clipped_edge(o, spot(o, c, t.x), spot(o, c, t.y), half);
}
return fill_edge(o, at(o, c, t.x), at(o, c, t.y));
}
let sub = subpath(ids_of(o).z + l - edges);
let w = params_of(o).xy;
let a = max(f32(sub.x), w.x);
let b = min(f32(sub.y), w.y);
if (a >= b) {
return none();
}
if (clipped) {
return clipped_edge(o, spot_u(o, b, sub.y - 1u), spot_u(o, a, sub.y - 1u), half);
}
return fill_edge(o, at_u(o, b, sub.y - 1u), at_u(o, a, sub.y - 1u));
}
// Body piece j of segment i of curve c: the segment's body (a dashed stroke's part of it in the
// j-th dash window it meets). A curve off the box has none: no pixel of the box sees it.
fn body_slot(o: u32, layer: u32, half: f32, c: u32, i: u32, j: u32) -> Seg {
let m = stroke_segments(o, c);
let t = piece(o, c, i, m);
if (i >= m || t.y <= t.x || off(o, c)) {
return none();
}
// the piece's ends (a dashed stroke's: of its j-th dash window's part of it; the depth taken where the window
// starts and ends)
var ta = t.x;
var tb = t.y;
var dt = t;
if (dashed(o)) {
let d = dash_of(o);
let u0 = f32(c) + t.x;
let u1 = f32(c) + t.y;
let s = d.z + (floor((u0 - d.z) / d.x) + f32(j)) * d.x;
let a = max(u0, s);
let b = min(u1, s + d.y * d.x);
if (s >= u1 || a >= b) {
return none();
}
ta = select(t.x, a - f32(c), a > u0);
tb = select(t.y, b - f32(c), b < u1);
dt = vec2<f32>(a, b) - f32(c);
}
let chord = at(o, c, t.y) - at(o, c, t.x);
var pa = at(o, c, ta);
var pb = at(o, c, tb);
var na = normal_at(o, c, ta, chord);
var nb = normal_at(o, c, tb, chord);
var depth = vec2<f32>(curve_depth(o, c, dt.x), curve_depth(o, c, dt.y));
if (flags_of(o).y != 0u) {
// a clipped object's piece: its part in front of the near plane, cut square where it crosses it (depth 0)
let sa = spot(o, c, ta);
let sb = spot(o, c, tb);
let front = vec2<bool>(spot_z(o, sa) >= 0.0, spot_z(o, sb) >= 0.0);
if (!any(front)) {
return none();
}
if (!all(front)) {
let q = crossing(o, sa, sb);
let cut = select(NO_DEPTH, -1.0, flags_of(o).x != 0u); // the near plane's depth
if (front.x) {
pb = q;
nb = perp(q - pa);
depth.y = cut;
} else {
pa = q;
na = perp(pb - q);
depth.x = cut;
}
}
}
return body(o, layer, half, pa, na, pb, nb, depth);
}
// Record r of the joint where curve c begins, with the drawn curve before it (past curves that are
// a point), where the stroke turns.
fn joint_slot(o: u32, layer: u32, half: f32, c: u32, r: u32) -> Seg {
if (piece(o, c, 0u, 1u).x != 0.0 || (flags_of(o).y != 0u && spot_z(o, spot(o, c, 0.0)) < 0.0)) {
return none();
}
let nn = body_normal(o, c, 0.0, true);
if (dot(nn, nn) < 0.5) {
return none(); // a point
}
var prev = neighbour(o, c, false);
for (var k = 0u; k < 64u && prev != NONE && prev != c && degenerate(o, prev); k++) {
prev = neighbour(o, prev, false);
}
if (prev == NONE || !dashes_join(o, f32(prev + 1u), f32(c))) {
return none();
}
let m = body_normal(o, prev, 1.0, false);
let cross = nn.x * m.y - nn.y * m.x;
if (!(dot(m, m) > 0.5 && (abs(cross) > 1e-6 || dot(nn, m) < 0.0))) {
return none();
}
return joint_record(o, layer, at(o, c, 0.0), m, nn, half, (brush2_of(o).w >> 2u) & 3u, curve_depth(o, c, 0.0), r);
}
// Record r of a cap at end e of what a subpath shows in one of the dash windows it meets (e / 2:
// the subpath, then the window, from the one over where it shows from; not dashed, the one
// stretch it shows; e % 2: the stretch's start or end). A dash's ends inside a subpath are always
// the stroke's; the subpath's own, unless it goes on across its seam.
fn cap_slot(o: u32, layer: u32, half: f32, e: u32, r: u32) -> Seg {
let windows = pieces_of(o).z;
let sub = subpath(ids_of(o).z + e / 2u / windows);
let start = e % 2u == 0u;
let w = params_of(o).xy;
let a = max(f32(sub.x), w.x);
let b = min(f32(sub.y), w.y);
let joined = seam(o, sub);
var lo = a;
var hi = b;
if (dashed(o)) {
let d = dash_of(o);
let s = d.z + (floor((a - d.z) / d.x) + f32(e / 2u % windows)) * d.x;
lo = max(a, s);
hi = min(b, s + d.y * d.x);
if (s >= b) {
return none();
}
} else if (joined) {
return none();
}
let inside = (start && lo > f32(sub.x)) || (!start && hi < f32(sub.y)); // a dash's end, not the subpath's
if (lo >= hi || !(inside || !joined)) {
return none();
}
return end_cap(o, layer, half, lo, hi, start, brush2_of(o).w & 3u, r);
}
// Stroke slot q: in its layer's slots (the stroke's, then the background stroke's), a body piece,
// a joint's record or a cap's.
fn stroke_slot(q: u32) -> Seg {
let o = owner(q, 1u);
var l = q - slots_of(o).y;
let curves = u32(scale_of(o).w);
let n = slots_of(o).z;
let k = slots_of(o).w;
let joint = pieces_of(o).x;
let cap = pieces_of(o).y;
let bodies = curves * n * k;
let joints = curves * joint;
let per_layer = bodies + joints + 2u * ids_of(o).w * pieces_of(o).z * cap;
var layer = 1u;
if (atlas_of(o).y == NONE) {
layer = 2u;
} else if (l >= per_layer) {
layer = 2u;
l -= per_layer;
}
let half = select(params_of(o).z, params_of(o).w, layer == 2u);
if (l < bodies) {
return body_slot(o, layer, half, l / (n * k), l / k % n, l % k);
}
if (l < bodies + joints) {
return joint_slot(o, layer, half, (l - bodies) / joint, (l - bodies) % joint);
}
return cap_slot(o, layer, half, (l - bodies - joints) / cap, (l - bodies - joints) % cap);
}
// ── pass 1: accumulate (raster, additive, into the atlas) ──────────────────────
fn corner(k: u32) -> vec2<f32> {
let c = array<vec2<f32>, 6>(vec2(0.0, 0.0), vec2(1.0, 0.0), vec2(1.0, 1.0), vec2(0.0, 0.0), vec2(1.0, 1.0), vec2(0.0, 1.0));
return c[k];
}
fn to_atlas(o: u32, layer: u32, local: vec2<f32>) -> vec4<f32> {
let packed = atlas_of(o)[layer];
let at = vec2<f32>(f32(packed & 0xffffu), f32(packed >> 16u)) + local;
return vec4<f32>(at.x / frame.size.z * 2.0 - 1.0, 1.0 - at.y / frame.size.w * 2.0, 0.0, 1.0);
}
struct Piece {
@builtin(position) position: vec4<f32>,
@location(0) @interpolate(flat) a: vec4<f32>, // fill: the edge; stroke: corners 0, 1
@location(1) @interpolate(flat) b: vec4<f32>, // fill: (r, 0, 0, 0); stroke: corners 2, 3
@location(2) @interpolate(flat) o: vec4<u32>, // object, layer, box size (f32 bits)
@location(3) @interpolate(flat) depth: vec2<f32>, // a stroke piece's depth where it begins and ends (or NO_DEPTH)
};
fn nothing() -> Piece {
var out: Piece;
out.position = vec4<f32>(2.0, 2.0, 0.0, 1.0);
return out;
}
// A fill edge's trapezoid down to r: the pixels of its columns between it and r, in the box.
@vertex
fn vs_fill(@builtin(vertex_index) v: u32, @builtin(instance_index) i: u32) -> Piece {
if (i >= frame.tiles.z) {
return nothing();
}
let seg = fill_record(i);
let o = seg.info.x;
if (o == NONE) {
return nothing(); // an empty slot
}
let p0 = seg.a.xy;
let p1 = seg.a.zw;
let r = dash_of(o).w;
let size = rect_of(o).zw;
let lo = floor(vec2<f32>(min(p0.x, p1.x), min(min(p0.y, p1.y), r)));
let hi = ceil(vec2<f32>(max(p0.x, p1.x), max(max(p0.y, p1.y), r)));
var out: Piece;
out.position = to_atlas(o, 0u, clamp(mix(lo, hi, corner(v)), vec2<f32>(0.0), size));
out.a = seg.a;
out.b = vec4<f32>(r, 0.0, 0.0, 0.0);
out.o = vec4<u32>(o, 0u, 0u, 0u);
out.depth = vec2<f32>(NO_DEPTH);
return out;
}
// An area as the atlas adds it: in 1/65536ths, whose sums (below 256) f32 adds exactly, so a
// pixel's sum does not depend on the order the records were written in (it varies from run to run).
fn exact(a: f32) -> vec4<f32> {
return vec4<f32>(round(a * 65536.0) / 65536.0, 0.0, 0.0, 0.0);
}
@fragment
fn fs_fill(in: Piece) -> @location(0) vec4<f32> {
let packed = atlas_of(in.o.x)[0];
let px = floor(in.position.xy) - vec2<f32>(f32(packed & 0xffffu), f32(packed >> 16u));
return exact(edge_area(in.a.xy, in.a.zw, px, in.b.x));
}
// A stroke piece's quad, rasterized as its box oriented along it, grown by a pixel: every pixel
// the quad touches, however sharp or folded its corners (a miter's).
@vertex
fn vs_stroke(@builtin(vertex_index) v: u32, @builtin(instance_index) i: u32) -> Piece {
if (i >= frame.tiles.w) {
return nothing();
}
let seg = stroke_record(i);
let o = seg.info.x;
if (o == NONE) {
return nothing(); // an empty slot
}
let layer = seg.info.y;
let q = array<vec2<f32>, 4>(seg.a.xy, seg.a.zw, seg.b.xy, seg.b.zw);
var along = 0.5 * (q[2] + q[3] - q[0] - q[1]);
if (dot(along, along) < 1e-12) {
along = q[1] - q[0];
}
let axis = select(vec2<f32>(1.0, 0.0), normalize(along), dot(along, along) > 1e-12);
let across = vec2<f32>(-axis.y, axis.x);
var lo = vec2<f32>(1e30);
var hi = vec2<f32>(-1e30);
for (var k = 0u; k < 4u; k++) {
let p = vec2<f32>(dot(q[k], axis), dot(q[k], across));
lo = min(lo, p);
hi = max(hi, p);
}
let at = mix(lo - 1.0, hi + 1.0, corner(v));
let size = rect_of(o).zw;
var out: Piece;
out.position = to_atlas(o, layer, at.x * axis + at.y * across);
out.a = seg.a;
out.b = seg.b;
out.o = vec4<u32>(o, layer, bitcast<u32>(size.x), bitcast<u32>(size.y));
out.depth = vec2<f32>(bitcast<f32>(seg.info.z), bitcast<f32>(seg.info.w));
return out;
}
// Whether point p lies in the triangle a b c (either winding).
fn inside(p: vec2<f32>, a: vec2<f32>, b: vec2<f32>, c: vec2<f32>) -> bool {
let d = vec3<f32>((b.x - a.x) * (p.y - a.y) - (b.y - a.y) * (p.x - a.x), (c.x - b.x) * (p.y - b.y) - (c.y - b.y) * (p.x - b.x), (a.x - c.x) * (p.y - c.y) - (a.y - c.y) * (p.x - c.x));
return all(d >= vec3<f32>(0.0)) || all(d <= vec3<f32>(0.0));
}
@fragment
fn fs_stroke(in: Piece) -> @location(0) vec4<f32> {
let o = in.o.x;
let packed = atlas_of(o)[in.o.y];
let px = floor(in.position.xy) - vec2<f32>(f32(packed & 0xffffu), f32(packed >> 16u));
let size = vec2<f32>(bitcast<f32>(in.o.z), bitcast<f32>(in.o.w));
if (px.x < 0.0 || px.y < 0.0 || px.x >= size.x || px.y >= size.y) {
discard;
}
let far = -1e30;
// the quad as two triangles (0 1 2) and (0 2 3), each counted whole: a quad folded by a sharp
// miter covers the union of its triangles
let diagonal = edge_area(in.a.xy, in.b.xy, px, far);
let a = abs(edge_area(in.a.xy, in.a.zw, px, far) + edge_area(in.a.zw, in.b.xy, px, far) - diagonal)
+ abs(diagonal + edge_area(in.b.xy, in.b.zw, px, far) + edge_area(in.b.zw, in.a.xy, px, far));
if (in.depth.x <= 0.0 && a > 0.0) {
// its depth at the pixel's center: z / w is affine along the piece on screen (lines stay lines, and z and w
// are affine along them)
let c = px + 0.5;
let m0 = 0.5 * (in.a.xy + in.a.zw);
let m1 = 0.5 * (in.b.xy + in.b.zw);
let along = m1 - m0;
let t = clamp(dot(c - m0, along) / max(dot(along, along), 1e-12), 0.0, 1.0);
let z = clamp(mix(in.depth.x, in.depth.y, t), -1.0, 0.0);
let through = inside(c, in.a.xy, in.a.zw, in.b.xy) || inside(c, in.a.xy, in.b.xy, in.b.zw);
// the nearer the larger: a depth's magnitude's bits
keep_stroke_depth(u32(in.position.y) * u32(frame.size.z) + u32(in.position.x), select(0u, 0x80000000u, through) | ((bitcast<u32>(z) & 0x7fffffffu) >> 1u));
}
return exact(a);
}
// ── pass 2: composite (compute) ───────────────────────────────────────────────
// A layer's paint at the pixel centred at `up` (view pixels, y up), premultiplied: a solid color,
// or the object's gradient there (`stops`).
fn paint(o: u32, color: vec4<f32>, first: u32, second: u32, count: u32, up: vec2<f32>) -> vec4<f32> {
if (color.a >= 0.0) {
return premultiplied(color);
}
let g = gradient_of(o);
var c = stops(first, second, count, bitcast<f32>(brush2_of(o).z), dot(up - g.xy, g.zw));
let light = place_of(o).w;
if (light != 0.0) {
c = vec4<f32>(clamp(c.rgb + light, vec3<f32>(0.0), vec3<f32>(1.0)), c.a);
}
return premultiplied(c);
}
// A layer's coverage at a local pixel as its tile's entry has it (`mask`: per layer, the fill where its edges run 1,
// inside them 2, the stroke 4, the background stroke 8): the atlas's where its edges or strokes run, 1 inside the fill
// (no read), else 0.
fn covered(mask: u32, layer: u32, origin: vec2<u32>, local: vec2<i32>, size: vec2<i32>) -> f32 {
if ((mask & array<u32, 3>(1u, 4u, 8u)[layer]) != 0u) {
return cover(origin, local, size);
}
return select(0.0, 1.0, layer == 0u && (mask & 2u) != 0u);
}
// A layer's coverage at a local pixel (0 outside the object's box).
fn cover(origin: vec2<u32>, local: vec2<i32>, size: vec2<i32>) -> f32 {
if (local.x < 0 || local.y < 0 || local.x >= size.x || local.y >= size.y) {
return 0.0;
}
return min(abs(textureLoad(atlas, origin + vec2<u32>(local), 0).r), 1.0);
}
// The area of the unit pixel (centred at 0) on the side n of the line p.n = d: its projection on
// n is the sum of two uniform variables, so the area is a piecewise quadratic of d.
fn side_area(n: vec2<f32>, d: f32) -> f32 {
let a = max(abs(n.x), abs(n.y));
let b = min(abs(n.x), abs(n.y));
let t = -d; // the area of {p.n >= d} = P(projection <= -d), by symmetry
if (t <= -0.5 * (a + b)) {
return 0.0;
}
if (t >= 0.5 * (a + b)) {
return 1.0;
}
if (b < 1e-6) {
return clamp(t / a + 0.5, 0.0, 1.0);
}
if (t <= -0.5 * (a - b)) {
let s = t + 0.5 * (a + b);
return s * s / (2.0 * a * b);
}
if (t <= 0.5 * (a - b)) {
return b / (2.0 * a) + (t + 0.5 * (a - b)) / a;
}
let s = 0.5 * (a + b) - t;
return 1.0 - s * s / (2.0 * a * b);
}
// The offset d with side_area(n, d) = c (its inverse).
fn offset_for(n: vec2<f32>, c: f32) -> f32 {
let a = max(abs(n.x), abs(n.y));
let b = min(abs(n.x), abs(n.y));
var t: f32;
if (b < 1e-6) {
t = a * (c - 0.5);
} else if (c <= b / (2.0 * a)) {
t = -0.5 * (a + b) + sqrt(2.0 * a * b * c);
} else if (c <= 1.0 - b / (2.0 * a)) {
t = -0.5 * (a - b) + a * (c - b / (2.0 * a));
} else {
t = 0.5 * (a + b) - sqrt(2.0 * a * b * (1.0 - c));
}
return -t;
}
// The area of the unit pixel (centred at 0) inside both half-planes p.n1 >= d1 and p.n2 >= d2.
fn both_area(n1: vec2<f32>, d1: f32, n2: vec2<f32>, d2: f32) -> f32 {
var poly: array<vec2<f32>, 8>;
var count = 4u;
poly[0] = vec2<f32>(-0.5, -0.5);
poly[1] = vec2<f32>(0.5, -0.5);
poly[2] = vec2<f32>(0.5, 0.5);
poly[3] = vec2<f32>(-0.5, 0.5);
for (var h = 0u; h < 2u; h++) {
let n = select(n2, n1, h == 0u);
let d = select(d2, d1, h == 0u);
var next: array<vec2<f32>, 8>;
var m = 0u;
for (var i = 0u; i < count; i++) {
let p = poly[i];
let q = poly[(i + 1u) % count];
let sp = dot(p, n) - d;
let sq = dot(q, n) - d;
if (sp >= 0.0 && m < 8u) {
next[m] = p;
m++;
}
if ((sp >= 0.0) != (sq >= 0.0) && m < 8u) {
next[m] = p + (q - p) * (sp / (sp - sq));
m++;
}
}
poly = next;
count = m;
}
var area = 0.0;
for (var i = 0u; i < count; i++) {
let p = poly[i];
let q = poly[(i + 1u) % count];
area += p.x * q.y - q.x * p.y;
}
return 0.5 * abs(area);
}
// What covers a pixel, or a part of it, as the composite mixes it: the raster base's two targets in one value
// (`blend.wgsl`'s `Base`): display paint (premultiplied; its alpha how much of it is lit) and the light of what is lit
// (exposed, premultiplied; its alpha how much is covered). Every way the composite mixes is linear in it (a layer over
// another, a split pixel's regions, a pixel's samples), so lit content's light is averaged as a camera averages it,
// and shown once (`seen`).
alias Mix = mat2x4<f32>;
// Display paint c (premultiplied) as a mix: nothing of it lit.
fn painted_mix(c: vec4<f32>) -> Mix {
return Mix(vec4<f32>(c.rgb, 0.0), vec4<f32>(0.0, 0.0, 0.0, c.a));
}
// The light l of lit content (exposed, premultiplied; its alpha the coverage) as a mix, the light kept within what a
// half float holds (as the raster base keeps it).
fn light_mix(l: vec4<f32>) -> Mix {
return Mix(vec4<f32>(0.0, 0.0, 0.0, l.a), vec4<f32>(min(l.rgb, vec3<f32>(LIGHT_MOST * l.a)), l.a));
}
// A mix divided by k (each column: as a vector is).
fn divided(m: Mix, k: f32) -> Mix {
return Mix(m[0] / k, m[1] / k);
}
// p over what lies below it: below covered as much as p covers.
fn over(p: Mix, below: Mix) -> Mix {
return p + below * (1.0 - p[1].a);
}
// A mix as the view shows it: its paint, and its light tone mapped once, the light of what is lit in it averaged
// first (a view with no lit content has none: `lighting`).
fn seen(m: Mix) -> vec4<f32> {
if (!lighting || m[0].a <= 0.0) {
return vec4<f32>(m[0].rgb, m[1].a);
}
return vec4<f32>(m[0].rgb + toned(m[1].rgb / m[0].a, u32(frame.lighting.z + 0.5)) * m[0].a, m[1].a);
}
// The pixel as two regions split by the line p.n = d (inside: p.n >= d, of area a).
struct Split {
n: vec2<f32>,
d: f32,
a: f32,
inside: Mix,
outside: Mix,
};
// The half-plane (normal, offset) of a partial layer: area c, normal the coverage gradient; z > 1.5
// when it has no direction.
fn half_plane(origin: vec2<u32>, local: vec2<i32>, size: vec2<i32>, c: f32) -> vec3<f32> {
let g = vec2<f32>(
cover(origin, local + vec2<i32>(1, 0), size) - cover(origin, local - vec2<i32>(1, 0), size),
cover(origin, local - vec2<i32>(0, 1), size) - cover(origin, local + vec2<i32>(0, 1), size),
);
return line_of(g, c);
}
// The half-plane of a partial layer of area c whose coverage changes by g across the pixel (x right, y up): its normal
// g's direction, its offset its area's (`offset_for`); z > 1.5 where g has no direction.
fn line_of(g: vec2<f32>, c: f32) -> vec3<f32> {
if (dot(g, g) < 1e-8) {
return vec3<f32>(0.0, 0.0, 2.0);
}
let n = normalize(g);
return vec3<f32>(n, offset_for(n, c));
}
// A pixel as the composite lays its layers: two regions (`Split`). Mode 0: uniform (inside = outside); 1: one
// partial layer pending, its half-plane found only if another partial layer comes (where its coverage lies: `origin`,
// `local`, `size`); 2: split by a line.
struct Pixel {
s: Split,
mode: u32,
origin: vec2<u32>,
local: vec2<i32>,
size: vec2<i32>,
};
// The pixel with paint p (a mix, where the layer covers) of coverage c laid over it: the layer's coverage lies at
// `local` of a box of `size` at `origin` in the atlas (`cover`).
fn lay(px: Pixel, p: Mix, c: f32, origin: vec2<u32>, local: vec2<i32>, size: vec2<i32>) -> Pixel {
var out = px;
if (c >= 1.0 - 1e-5) {
let q = p * c;
out.s.inside = over(q, px.s.inside);
out.s.outside = over(q, px.s.outside);
return out;
}
if (px.mode == 0u) {
// the first partial layer: exact as it is, unless another partial layer comes
out.mode = 1u;
out.s.a = c;
out.s.inside = over(p, px.s.inside);
out.origin = origin;
out.local = local;
out.size = size;
return out;
}
return lay_line(lined(px), p, c, half_plane(origin, local, size, c));
}
// The pixel with its pending partial layer's line found (mode 1 to 2), from its coverage's gradient; one without a
// direction settled as plain coverage.
fn lined(px: Pixel) -> Pixel {
if (px.mode != 1u) {
return px;
}
var out = px;
let h = half_plane(px.origin, px.local, px.size, px.s.a);
if (h.z > 1.5) {
// the pending layer has no direction: settle it as plain coverage
let settled = px.s.a * px.s.inside + (1.0 - px.s.a) * px.s.outside;
out.s.inside = settled;
out.s.outside = settled;
out.s.a = 0.0;
out.s.n = vec2<f32>(1.0, 0.0);
out.s.d = 1.0;
} else {
out.s.n = h.xy;
out.s.d = h.z;
}
out.mode = 2u;
return out;
}
// The pixel with paint p (a mix, where the layer covers) of coverage c laid over it in the half-plane `line` (p.n >= d),
// a line known as it is laid (z > 1.5: none, the paint laid as plain coverage).
fn lay_line(px: Pixel, p: Mix, c: f32, line: vec3<f32>) -> Pixel {
var out = px;
if (line.z > 1.5) {
let q = p * c;
out.s.inside = over(q, px.s.inside);
out.s.outside = over(q, px.s.outside);
return out;
}
if (px.mode == 0u) {
out.mode = 2u;
out.s.n = line.xy;
out.s.d = line.z;
out.s.a = c;
out.s.inside = over(p, px.s.inside);
return out;
}
return split_by(lined(px), p, line, c);
}
// The pixel (split by a line: mode 2) with paint p laid over it in the half-plane h (p.n >= d), of area c: the new
// line splits the pixel again, its inside the layer over what each old region leaves in it.
fn split_by(px: Pixel, p: Mix, hl: vec3<f32>, c: f32) -> Pixel {
var out = px;
let s = out.s;
let overlap = both_area(s.n, s.d, hl.xy, hl.z);
let in_l = divided(overlap * s.inside + (c - overlap) * s.outside, c);
let out_l = divided((s.a - overlap) * s.inside + (1.0 - s.a - c + overlap) * s.outside, max(1.0 - c, 1e-6));
out.s.n = hl.xy;
out.s.d = hl.z;
out.s.a = c;
out.s.inside = over(p, in_l);
out.s.outside = out_l;
return out;
}
// Where layer l is nearer than `last`, the layer laid just before it, both planar: the half-plane of the unit pixel
// (centred at 0, y up, as `half_plane`'s) where their planes put l in front, if they cross inside the pixel (Duff's
// test: their depths' difference changes sign over it); else none (z > 1.5): l is in front all over it.
fn nearer_part(l: Layer, last: Layer) -> vec3<f32> {
let none = vec3<f32>(0.0, 0.0, 2.0);
if (l.key == 0u || l.key == NONE || last.key == 0u || last.key == NONE) {
return none;
}
let ol = (l.key >> 2u) - 1u;
let om = (last.key >> 2u) - 1u;
if ((flags_of(ol).x != 0u && (l.key & 3u) != 1u) || (flags_of(om).x != 0u && (last.key & 3u) != 1u)) {
return none; // (a stroke's own depths, a pixel's)
}
// their depths' difference: at the centre, and its gradient over view pixels (y down); a difference that stays
// within the depths' own precision over the pixel (`frame.depth.x` of them: 8 f32 steps) is no crossing, a tie
let g = place_of(ol).xy - place_of(om).xy;
let dc = l.z - last.z;
let reach = 0.5 * (abs(g.x) + abs(g.y));
if (abs(dc) >= reach || reach <= frame.depth.x * max(abs(l.z), abs(last.z))) {
return none;
}
// l nearer: dc + g.p < 0 (p from the centre, y down); y up, q = (p.x, -p.y): q.(-g.x, g.y) > dc
let length = sqrt(dot(g, g));
return vec3<f32>(-g.x, g.y, dc) / length;
}
// The pixel with layer l laid over it only where it is nearer than the whole layer laid just before it (half-plane h,
// `nearer_part`): exact for a whole layer; a partial one keeps its coverage's share there (`both_area`), along the
// line that cuts it more.
fn lay_nearer(px: Pixel, l: Layer, h: vec3<f32>, gid: vec2<u32>, up: vec2<f32>) -> Pixel {
let o = (l.key >> 2u) - 1u;
let local = vec2<i32>(vec2<f32>(gid) - rect_of(o).xy);
let size = vec2<i32>(rect_of(o).zw);
let layer = array<u32, 3>(2u, 0u, 1u)[l.key & 3u];
let packed = atlas_of(o)[layer];
let p = paint_of(o, layer, up);
var line = h;
var area = side_area(h.xy, h.z);
if (l.c < 1.0 - 1e-5) {
let hc = half_plane(vec2<u32>(packed & 0xffffu, packed >> 16u), local, size, l.c);
if (hc.z <= 1.5) {
area = both_area(h.xy, h.z, hc.xy, hc.z);
let n = select(h.xy, hc.xy, l.c < side_area(h.xy, h.z));
line = vec3<f32>(n, offset_for(n, area));
} else {
area *= l.c;
line = vec3<f32>(h.xy, offset_for(h.xy, area));
}
}
if (area <= 1e-6) {
return px;
}
return lay_line(px, p, area, line);
}
// A layer's place in a pixel's order: key = (object + 1) << 2 | step (an object's layers in their order: background
// stroke, fill, stroke; a raster's: 1), 0 the raster base; its depth there; its coverage.
struct Layer {
key: u32,
z: f32,
c: f32,
};
// Whether layer a is laid before b: farther, or as far and earlier in the order (a 2D view's order alone).
fn before(a: Layer, b: Layer) -> bool {
return a.z > b.z || (a.z == b.z && a.key < b.key);
}
// A layer's paint at the pixel centred at `up` (view pixels, y up; for gradients): object o's background stroke,
// fill or stroke (`layer`, as its atlas origins are numbered), as its colors give it.
fn painted(o: u32, layer: u32, up: vec2<f32>) -> vec4<f32> {
if (layer == 2u) {
return paint(o, background_of(o), 0u, 0u, 0u, up);
}
if (layer == 0u) {
return paint(o, fill_of(o), brush_of(o).x, brush2_of(o).x, brush_of(o).y, up);
}
return paint(o, stroke_of(o), brush_of(o).z, brush2_of(o).y, brush_of(o).w, up);
}
// Whether the view has lit content (paths or meshes with a material): a view with none composites by a pipeline
// without the light's code and a mix's light (whose registers it would pay for unused).
override lighting: bool = false;
// Whether the view lays rasters (a 2D view's points and meshes, a 3D view's raster base), see-through fragments'
// lists and see-through points' slabs: a view without them composites by a pipeline without their code, whose
// registers (as many as the pixel's longest path through the composite needs) every pixel of the view would pay for
// unused.
override rasters: bool = true;
override lists: bool = true;
override points: bool = false;
// A layer's paint as a mix: a fill with a material lit.
fn paint_of(o: u32, layer: u32, up: vec2<f32>) -> Mix {
let p = painted(o, layer, up);
if (lighting && layer == 0u && material_of(o).w > 0.5) {
return lit(o, p, up);
}
return painted_mix(p);
}
// A fill with a material at the pixel centred at `up`: its paint (premultiplied) the base color of a surface lit by
// the view's lights where its plane passes through the pixel, its light exposed (`light.wgsl`). Where it is opaque,
// the light from all around reaches it as the view's ambient occlusion says (what is seen through is not in the depth
// that is found from).
fn lit(o: u32, p: vec4<f32>, up: vec2<f32>) -> Mix {
if (p.a <= 0.0) {
return light_mix(p);
}
let pixel = vec2<f32>(up.x, frame.size.y - up.y);
let z = -plane_depth(o, pixel); // (z / w: its depth from the far plane, negated: reversed Z)
let h = frame.inverse * vec4<f32>(pixel.x / frame.size.x * 2.0 - 1.0, 1.0 - pixel.y / frame.size.y * 2.0, z, 1.0);
let world = h.xyz / h.w;
let v = select(frame.toward.xyz, normalize(frame.eye.xyz - world), frame.eye.w > 0.5);
let m = material_of(o);
var ao = 1.0;
if (frame.occlusion.x > 0.0 && p.a >= 1.0 - 1e-5) {
ao = textureLoad(occlusion, vec2<i32>(pixel), 0).x;
}
let radiance = reflected(linear(p.rgb / p.a), m.x, m.y, m.z, normal_of(o).xyz, world, v, ao);
return light_mix(vec4<f32>(radiance * frame.lighting.y * p.a, p.a));
}
// Object o's plane's depth at `at` (view pixels): from its reference point (its flat's, shared to the bit), where its
// plane keeps its depth's digits.
fn plane_depth(o: u32, at: vec2<f32>) -> f32 {
return dot(place_of(o).xy, at - vec2<f32>(flags_of(o).zw)) + place_of(o).z;
}
// Object o's depth at the pixel `centre`: its plane's; its strokes', where it is not planar, as they cover the pixel
// (`origin`: the layer's atlas; `local`: the pixel in its box).
fn depth_at(o: u32, step: u32, origin: vec2<u32>, local: vec2<i32>, centre: vec2<f32>) -> f32 {
let z = plane_depth(o, centre);
if (flags_of(o).x == 0u || step == 1u) {
return z;
}
let at = origin + vec2<u32>(local);
let v = stroke_depth(at.y * u32(frame.size.z) + at.x);
return select(z, -bitcast<f32>(v << 1u), v != 0u);
}
// Object o's layer `step` at the pixel `centre` (view pixels), `local` in its box: its place in the order and its
// coverage (0: none; `mask`: its tile entry's, see `covered`).
fn layer_at(o: u32, mask: u32, step: u32, local: vec2<i32>, centre: vec2<f32>) -> Layer {
let key = ((o + 1u) << 2u) | step;
if (atlas_of(o).w != NONE) {
return Layer(key, plane_depth(o, centre), select(0.0, 1.0, step == 1u));
}
let packed = atlas_of(o)[array<u32, 3>(2u, 0u, 1u)[step]];
if (packed == NONE) {
return Layer(key, 0.0, 0.0);
}
let origin = vec2<u32>(packed & 0xffffu, packed >> 16u);
return Layer(key, depth_at(o, step, origin, local, centre), covered(mask, array<u32, 3>(2u, 0u, 1u)[step], origin, local, vec2<i32>(rect_of(o).zw)));
}
// What lies under the group (`frame.counts.y`), or a 3D view's raster base, at pixel `gid`, as a mix: display paint,
// or (where it carries light: `frame.counts.w` bit 1) its paint and its light, as the raster base's two targets or the
// group before left them.
fn base_at(gid: vec2<u32>) -> Mix {
let p = textureLoad(base, gid, 0);
if ((frame.counts.w & 1u) == 0u) {
return painted_mix(p);
}
return Mix(p, textureLoad(base_light, gid, 0));
}
// The pixel `gid` (centred at `up`) with layer l laid over it.
fn settle(px: Pixel, l: Layer, gid: vec2<u32>, up: vec2<f32>) -> Pixel {
if (l.key == 0u) {
return lay_raster(px, base_at(gid), true, vec2<u32>(0u), vec2<i32>(gid), vec2<i32>(frame.size.xy));
}
let o = (l.key >> 2u) - 1u;
let local = vec2<i32>(vec2<f32>(gid) - rect_of(o).xy);
let size = vec2<i32>(rect_of(o).zw);
let raster = atlas_of(o).w;
if (raster != NONE) {
let origin = vec2<u32>(raster & 0xffffu, raster >> 16u);
return lay_raster(px, painted_mix(textureLoad(layers, origin + vec2<u32>(local), 0)), false, origin, local, size);
}
let layer = array<u32, 3>(2u, 0u, 1u)[l.key & 3u];
let packed = atlas_of(o)[layer];
return lay(px, paint_of(o, layer, up), l.c, vec2<u32>(packed & 0xffffu, packed >> 16u), local, size);
}
// A raster's coverage (its alpha) at a pixel, 0 outside its box: the raster base's (`base_layer`; `local` the view
// pixel, `size` the view's) or a raster layer's (`local` in its box of `size` at `origin` in the raster atlas).
fn raster_cover(base_layer: bool, origin: vec2<u32>, local: vec2<i32>, size: vec2<i32>) -> f32 {
if (local.x < 0 || local.y < 0 || local.x >= size.x || local.y >= size.y) {
return 0.0;
}
let at = origin + vec2<u32>(local);
if (base_layer) {
return base_at(at)[1].a;
}
return textureLoad(layers, at, 0).a;
}
// The pixel with a raster's pixel r (a mix, premultiplied: its coverage its alpha, its samples') laid over it as a
// path's layer is, where it covers: a partial one in the half-plane its alpha's gradient gives, found as it is laid (a
// raster's coverage lies in no atlas), so that where its edge and a path's share the pixel, each covers its own part.
fn lay_raster(px: Pixel, r: Mix, base_layer: bool, origin: vec2<u32>, local: vec2<i32>, size: vec2<i32>) -> Pixel {
let c = r[1].a;
if (!rasters || c <= 0.0) {
return px;
}
var line = vec3<f32>(0.0, 0.0, 2.0);
if (c < 1.0 - 1e-5) {
let g = vec2<f32>(
raster_cover(base_layer, origin, local + vec2<i32>(1, 0), size) - raster_cover(base_layer, origin, local - vec2<i32>(1, 0), size),
raster_cover(base_layer, origin, local - vec2<i32>(0, 1), size) - raster_cover(base_layer, origin, local + vec2<i32>(0, 1), size),
);
line = line_of(g, c);
}
return lay_line(px, divided(r, c), c, line);
}
// A see-through fragment found in a pixel's list: its node, and its index + 1 (0: none found).
struct Found {
node: Node,
at: u32,
};
// Whether fragment a comes before b in their order: farther first, then by key and color, then by index (what a
// pixel shows does not depend on the order the GPU appended its fragments in: only identical ones swap).
fn node_before(a: Found, b: Found) -> bool {
let x = a.node;
let y = b.node;
return x.depth > y.depth || (x.depth == y.depth && (x.key < y.key || (x.key == y.key && (x.color < y.color || (x.color == y.color && a.at < b.at)))));
}
// The first of a pixel's fragments (its list from `head`) after `after` (at 0: the first of all).
fn next_node(head: u32, after: Found) -> Found {
var best = Found(Node(0.0, 0u, 0u, 0u), 0u);
var at = head;
loop {
if (at == 0u) {
break;
}
let here = Found(list_node(at - 1u), at);
if ((after.at == 0u || node_before(after, here)) && (best.at == 0u || node_before(here, best))) {
best = here;
}
at = here.node.next;
}
return best;
}
// A fragment's place among the layers: at its depth pushed back as the base's is (a path drawn on it shows), after
// the base among equals.
fn node_layer(f: Found) -> Layer {
return Layer(1u, f.node.depth * (1.0 - frame.depth.x), 1.0);
}
const SAME_LAYER: f32 = 1e-5; // a stroke's own fragments this close are one layer (its joints)
const FEW: u32 = 8u; // layers a pixel where depths cross sorts at once
const SLABS: u32 = 4u; // a pixel's nearest layers its see-through points are laid among (`bound`)
const NO_LAYER: f32 = -3.0e38; // nearer than every layer: where a pixel has fewer than SLABS (`bound`)
// A pixel's see-through points that come before a layer at depth z, from slab `first` on, composited in their order,
// and the first slab still to come. Slab j holds its points between the j-th and the (j+1)-th of its nearest layers
// (`bound`), blended in their order (`blend_lists.wgsl`): it comes before the (j+1)-th, wherever the composite meets
// that depth (a layer it hides, it never meets: the slab comes before the next it lays); the last, after everything.
struct Points {
mix: Mix,
next: u32,
};
fn points_before(first: u32, z: f32, gid: vec2<u32>) -> Points {
var out = Points(Mix(), first);
if (!points || first > SLABS) {
return out;
}
let bounds = textureLoad(slab_bounds, gid, 0);
for (var j = first; j <= SLABS; j++) {
if (j < SLABS && z > bounds[j]) {
break; // farther than the layer after slab j
}
if (bounds[j - 1u] > NO_LAYER) {
out.mix = over(painted_mix(textureLoad(slabs, gid, i32(j - 1u), 0)), out.mix);
}
out.next = j + 1u;
}
return out;
}
// The pixel with what comes before `until` of its fragments from `u.next` on, of its base's `u.samples` (a bit each:
// not laid yet) and of its points laid over it as one layer: composited sample by sample (a base sample under its
// fragments, nearest last; a stroke's overlapping pieces once; points over every sample), then the samples' mean, so
// no seam shows where a mesh's triangles meet inside the pixel, nor where the base and the fragments share it.
fn slab(u: Under, head: u32, until: Layer, gid: vec2<u32>) -> Under {
if (!lists || ((u.next.at == 0u || !before(node_layer(u.next), until)) && u.samples == 0u)) {
return u;
}
var out = u;
var acc: array<Mix, 8>;
var kept: array<vec2<u32>, 8>; // per sample, the last fragment laid: its layer (record and kind), its depth
var laid = false;
for (var s = 0u; s < 8u; s++) {
acc[s] = Mix();
kept[s] = vec2<u32>(NONE, 0u);
if ((u.samples & (1u << s)) != 0u && before(Layer(0u, base_sample_depth(gid, s) * (1.0 - frame.depth.x), 1.0), until)) {
acc[s] = base_sample(gid, s);
out.samples &= ~(1u << s);
laid = true;
}
}
var f = u.next;
loop {
if (f.at == 0u || !before(node_layer(f), until)) {
break;
}
let farther = points_before(out.slab, node_layer(f).z, gid);
out.slab = farther.next;
if (farther.mix[1].a > 0.0) {
for (var s = 0u; s < frame.lists.w; s++) {
acc[s] = over(farther.mix, acc[s]);
}
out.shown += 1u;
}
let c = rgba8(f.node.color);
let p = painted_mix(vec4<f32>(c.rgb * c.a, c.a));
let mask = (f.node.key >> 3u) & 0xffu;
let layer = f.node.key & 0xfffff803u;
for (var s = 0u; s < 8u; s++) {
let again = (f.node.key & 3u) == 3u && kept[s].x == layer && bitcast<f32>(kept[s].y) - f.node.depth <= SAME_LAYER;
if ((mask & (1u << s)) != 0u && !again) {
acc[s] = over(p, acc[s]);
kept[s] = vec2<u32>(layer, bitcast<u32>(f.node.depth));
}
}
laid = true;
f = next_node(head, f);
}
out.next = f;
if (laid) {
var sum = Mix();
for (var s = 0u; s < 8u; s++) {
sum += acc[s];
}
out.px = lay(out.px, divided(sum, f32(frame.lists.w)), 1.0, vec2<u32>(0u), vec2<i32>(0), vec2<i32>(0));
}
return out;
}
// What lies under the layers from `until` on: the base, the see-through fragments and points.
struct Under {
px: Pixel,
next: Found, // the first fragment not laid
base_left: bool, // the base (as one layer) not laid
samples: u32, // where the pixel has fragments, the base's samples not laid (instead)
slab: u32, // the first of its points' slabs not laid (`points_before`)
shown: u32, // how many times points were laid
};
// The pixel with the base, the see-through fragments (its list from `head`) and points that come before `until` laid
// over it, in their order: the points once the base is (they lie in front of its opaque samples).
fn under(u: Under, head: u32, base: Layer, until: Layer, gid: vec2<u32>, up: vec2<f32>) -> Under {
var out = u;
if (u.base_left && before(base, until)) {
out.px = settle(out.px, base, gid, up);
out.base_left = false;
}
out = slab(out, head, until, gid);
if (!out.base_left) {
let farther = points_before(out.slab, until.z, gid);
out.slab = farther.next;
if (farther.mix[1].a > 0.0) {
out.px = lay(out.px, farther.mix, 1.0, vec2<u32>(0u), vec2<i32>(0), vec2<i32>(0));
out.shown += 1u;
}
}
return out;
}
// Each pixel of the view: the layers of its tile's objects laid in depth order, farthest first (the draw order among
// equal depths: a 2D view's draw order), with a 3D view's raster base and see-through fragments in their places. Its
// tile's list comes in the order its objects' depths suggest (a 2D view's: the draw order), so a pixel lays the
// layers as they come and checks only that each comes after the last (`laid`); where one does not (where depths
// cross), the pixel takes them again in their order (`crossed`): in the compute form, a second pass over the pixels
// the first lists, so that the few where depths cross keep the rest from waiting.
// What a pixel's composite starts from: what lies under its layers (the background, or what the groups before laid),
// a 3D view's raster base as a layer and the depth past which it hides everything, its see-through fragments' list,
// its tile's list, and where it is.
struct Begun {
fresh: Under,
base_layer: Layer,
hidden: f32,
head: u32,
first: u32,
end: u32,
entries: u32,
pixel: vec2<f32>,
centre: vec2<f32>,
up: vec2<f32>,
};
// Pixel gid's see-through fragments' list (only in the listed rows are the heads this frame's): its head (0: none).
fn head_at(gid: vec2<u32>) -> u32 {
if (lists && frame.lists.x == 1u && gid.y >= frame.lists.y && gid.y < frame.lists.z) {
return list_head(gid.y * u32(frame.size.x) + gid.x);
}
return 0u;
}
fn begin(gid: vec2<u32>) -> Begun {
let tile = (gid.y / TILE) * frame.tiles.x + gid.x / TILE;
let pixel = vec2<f32>(gid);
let centre = pixel + 0.5;
let up = vec2<f32>(pixel.x + 0.5, frame.size.y - pixel.y - 0.5);
var start: Pixel;
start.mode = 0u;
start.s.n = vec2<f32>(1.0, 0.0);
start.s.d = 1.0;
start.s.a = 0.0;
start.s.inside = painted_mix(frame.background);
if (frame.counts.y == 1u) {
start.s.inside = base_at(gid);
}
start.s.outside = start.s.inside;
// a 3D view's raster base: a layer at its depth (a path drawn on it, a little nearer than it, shows), or (laid
// already) hiding what lies behind it; nothing shows behind it where it is opaque
let base_layer = Layer(0u, textureLoad(base_depth, min(gid, textureDimensions(base_depth) - 1u), 0).r * (1.0 - frame.depth.x), 1.0);
var hidden = 3.0;
if ((frame.counts.z == 1u && base_at(gid)[1].a >= 1.0) || frame.counts.z == 2u) {
hidden = base_layer.z;
}
// its see-through fragments: where it has some, its base sample by sample among them; elsewhere one layer
let head = head_at(gid);
let none = Found(Node(0.0, 0u, 0u, 0u), 0u);
let all = (1u << frame.lists.w) - 1u;
let fresh = Under(start, next_node(head, none), frame.counts.z == 1u && head == 0u, select(0u, all, frame.counts.z == 1u && head != 0u), 1u, 0u);
let first = tile_entry(tile);
let end = tile_entry(tile + 1u);
let entries = frame.tiles.x * frame.tiles.y + 1u; // where the tiles' entries begin
return Begun(fresh, base_layer, hidden, head, first, end, entries, pixel, centre, up);
}
// The pixel's mix once what lies under nothing more (the base, the fragments and points left) is laid.
fn finish(u0: Under, b: Begun, gid: vec2<u32>) -> Mix {
let u = under(u0, b.head, b.base_layer, Layer(NONE, NO_LAYER, 0.0), gid, b.up);
return u.px.s.a * u.px.s.inside + (1.0 - u.px.s.a) * u.px.s.outside;
}
// The pixel's layers laid as they come: its mix, where each comes after the last (else, ordered false).
struct Laid {
ordered: bool,
mix: Mix,
};
fn laid(gid: vec2<u32>, b: Begun) -> Laid {
let base_layer = b.base_layer;
let hidden = b.hidden;
let head = b.head;
let first = b.first;
let end = b.end;
let entries = b.entries;
let pixel = b.pixel;
let centre = b.centre;
let up = b.up;
var u = b.fresh;
var last = Layer(0u, 3.0e38, 0.0); // nothing laid yet: before everything
var ordered = true;
for (var k = first; k < end && ordered; k++) {
let e = tile_entry(entries + k);
let o = e & 0xffffffu;
let mask = e >> 24u;
let local = vec2<i32>(pixel - rect_of(o).xy);
let bsize = vec2<i32>(rect_of(o).zw);
if (local.x < 0 || local.y < 0 || local.x >= bsize.x || local.y >= bsize.y) {
continue;
}
let z = plane_depth(o, centre);
let key = (o + 1u) << 2u;
let raster = atlas_of(o).w;
for (var step = 0u; step < 3u; step++) {
var l = Layer(key | step, z, 1.0);
var p: Mix;
var origin = vec2<u32>(0u);
if (raster != NONE) {
if (!rasters || step != 1u) {
continue;
}
origin = vec2<u32>(raster & 0xffffu, raster >> 16u);
p = painted_mix(textureLoad(layers, origin + vec2<u32>(local), 0));
} else {
let layer = array<u32, 3>(2u, 0u, 1u)[step];
let packed = atlas_of(o)[layer];
if (packed == NONE) {
continue;
}
origin = vec2<u32>(packed & 0xffffu, packed >> 16u);
l.c = covered(mask, layer, origin, local, bsize);
if (l.c <= 1e-5) {
continue;
}
if (flags_of(o).x != 0u && step != 1u) {
l.z = depth_at(o, step, origin, local, centre);
}
p = paint_of(o, layer, up);
}
if (l.z > hidden) {
continue;
}
if (before(l, last) || (frame.depth.x > 0.0 && nearer_part(l, last).z <= 1.5)) {
ordered = false;
break;
}
u = under(u, head, base_layer, l, gid, up);
if (raster != NONE) {
u.px = lay_raster(u.px, p, false, origin, local, bsize);
} else {
u.px = lay(u.px, p, l.c, origin, local, bsize);
}
last = l;
}
}
if (!ordered) {
return Laid(false, Mix());
}
return Laid(true, finish(u, b, gid));
}
// The pixel where depths cross: every layer again, in their order.
fn crossed(gid: vec2<u32>, b: Begun) -> Mix {
let base_layer = b.base_layer;
let hidden = b.hidden;
let head = b.head;
let first = b.first;
let end = b.end;
let entries = b.entries;
let pixel = b.pixel;
let centre = b.centre;
let up = b.up;
var u = b.fresh;
// its layers in their order, FEW at a time: one pass over its tile's list keeps the FEW first after the last laid,
// sorted as they come (a pixel where n layers cross costs n / FEW passes, not n)
var last = Layer(0u, 3.0e38, 0.0); // nothing laid yet: before everything
// the last laid, if a whole path layer and nothing since: its paint, and the pixel before it
var prev = Layer(NONE, 0.0, 0.0);
var prev_paint = Mix();
var prev_under = u.px;
loop {
var few: array<Layer, FEW>;
var n = 0u;
for (var k = first; k < end; k++) {
let e = tile_entry(entries + k);
let o = e & 0xffffffu;
let mask = e >> 24u;
let local = vec2<i32>(pixel - rect_of(o).xy);
let bsize = vec2<i32>(rect_of(o).zw);
if (local.x < 0 || local.y < 0 || local.x >= bsize.x || local.y >= bsize.y) {
continue;
}
for (var step = 0u; step < 3u; step++) {
let l = layer_at(o, mask, step, local, centre);
if (l.c <= 1e-5 || l.z > hidden || !before(last, l) || (n == FEW && !before(l, few[FEW - 1u]))) {
continue;
}
var j = min(n, FEW - 1u);
for (; j > 0u && before(l, few[j - 1u]); j--) {
few[j] = few[j - 1u];
}
few[j] = l;
n = min(n + 1u, FEW);
}
}
for (var i = 0u; i < n; i++) {
let before_under = u.base_left;
let next_before = u.next.at;
let shown_before = u.shown;
u = under(u, head, base_layer, few[i], gid, up);
if (u.base_left != before_under || u.next.at != next_before || u.shown != shown_before) {
prev = Layer(NONE, 0.0, 0.0);
}
let path = few[i].key != 0u && atlas_of((few[i].key >> 2u) - 1u).w == NONE;
var paint = Mix();
if (path) {
let o = (few[i].key >> 2u) - 1u;
paint = paint_of(o, array<u32, 3>(2u, 0u, 1u)[few[i].key & 3u], up);
}
let h = nearer_part(few[i], prev);
let whole = few[i].c >= 1.0 - 1e-5;
let laid_before = u.px;
if (h.z <= 1.5 && path && prev_paint[1].a >= 1.0 - 1e-5) {
// over an opaque layer: only where it is nearer (behind it, it is hidden)
u.px = lay_nearer(u.px, few[i], h, gid, up);
} else if (h.z <= 1.5 && path && whole && prev_under.mode == 0u) {
// over a see-through one, both whole, on what is one colour: each over the other where it is nearer
u.px.mode = 2u;
u.px.s.n = h.xy;
u.px.s.d = h.z;
u.px.s.a = side_area(h.xy, h.z);
u.px.s.inside = over(paint, laid_before.s.inside);
u.px.s.outside = over(prev_paint, over(paint, prev_under.s.inside));
} else {
u.px = settle(u.px, few[i], gid, up);
}
prev = Layer(NONE, 0.0, 0.0);
if (path && whole) {
prev = few[i];
prev_paint = paint;
prev_under = laid_before;
}
}
if (n < FEW) {
break;
}
last = few[FEW - 1u];
}
return finish(u, b, gid);
}
// A pixel's nearest layers' depths met so far, far to near (NO_LAYER past the last), with a layer at depth z among them:
// where all SLABS are met, only if it is nearer than the farthest, which makes room.
fn nearer(k: vec4<f32>, z: f32) -> vec4<f32> {
// A boundary is a depth, not a fragment: triangles and per-sample invocations can
// contribute several nodes at one depth without creating another slab for points.
if (any(k == vec4<f32>(z))) {
return k;
}
var out = k;
if (out.w > NO_LAYER) {
if (z >= out.x) {
return out;
}
out = vec4<f32>(out.yzw, NO_LAYER);
}
var j = SLABS - 1u;
for (; j > 0u && out[j - 1u] < z; j--) {
out[j] = out[j - 1u];
}
out[j] = z;
return out;
}
// A 3D view's slab bounds: the depths of pixel gid's SLABS nearest layers, far to near (NO_LAYER where it has fewer),
// its paths' and its see-through fragments', as the composite takes them (`layer_at`, `node_layer`), but what is fixed
// in the frame (in front of everything, it parts no points). A see-through point counts those farther than it
// (`blend_lists.wgsl`'s `slab_of`): with none, it is blended into the base; else into the slab between two of them,
// which the composite lays between them (`points_before`). A point behind SLABS layers is behind them all: the base.
fn bound(gid: vec2<u32>) -> vec4<f32> {
let tile = (gid.y / TILE) * frame.tiles.x + gid.x / TILE;
let entries = frame.tiles.x * frame.tiles.y + 1u;
let pixel = vec2<f32>(gid);
var k = vec4<f32>(NO_LAYER);
for (var i = tile_entry(tile); i < tile_entry(tile + 1u); i++) {
let e = tile_entry(entries + i);
let o = e & 0xffffffu;
let local = vec2<i32>(pixel - rect_of(o).xy);
let size = vec2<i32>(rect_of(o).zw);
if (local.x < 0 || local.y < 0 || local.x >= size.x || local.y >= size.y) {
continue;
}
for (var step = 0u; step < 3u; step++) {
let l = layer_at(o, e >> 24u, step, local, pixel + 0.5);
if (l.c > 1e-5 && l.z > -1.0) {
k = nearer(k, l.z);
}
}
}
var at = head_at(gid);
loop {
if (at == 0u) {
break;
}
let f = Found(list_node(at - 1u), at);
k = nearer(k, node_layer(f).z);
at = f.node.next;
}
return k;
}
const TILE: u32 = 16u;
// A depth no layer has (a 3D view's depths run from the near plane, -1, to the far plane, 0: z / w - 1).
const NO_DEPTH: f32 = 2.0;
// ── the composite's depth entry: a light's shadow map ─────────────────────────
// A triangle over the whole target: a fragment per pixel.
@vertex
fn vs_cover(@builtin(vertex_index) v: u32) -> @builtin(position) vec4<f32> {
let p = vec2<f32>(f32((v << 1u) & 2u), f32(v & 2u));
return vec4<f32>(p * 2.0 - 1.0, 0.0, 1.0);
}
// Whose depth a pass of nearest layers draws: a light's map (standard Z; what is half opaque or more casts a shadow),
// or (`view_depth`) a view's opaque depth, for its ambient occlusion (reversed Z; what is opaque, as its raster base's
// opaque meshes are).
override view_depth: bool = false;
// What casts a shadow at texel `gid` of a light's map (the view, seen from the light), or shuts out light at a pixel
// of a view: the nearest of its tile's objects' layers that cover half the texel or more where their paint is at least
// `opacity`; its depth (3: none).
fn nearest(gid: vec2<u32>, opacity: f32) -> f32 {
let tile = (gid.y / TILE) * frame.tiles.x + gid.x / TILE;
let pixel = vec2<f32>(gid);
let centre = pixel + 0.5;
let up = vec2<f32>(pixel.x + 0.5, frame.size.y - pixel.y - 0.5);
let entries = frame.tiles.x * frame.tiles.y + 1u;
var z = 3.0;
for (var k = tile_entry(tile); k < tile_entry(tile + 1u); k++) {
let e = tile_entry(entries + k);
let o = e & 0xffffffu;
let mask = e >> 24u;
let local = vec2<i32>(pixel - rect_of(o).xy);
if (any(local < vec2<i32>(0)) || any(local >= vec2<i32>(rect_of(o).zw))) {
continue;
}
for (var step = 0u; step < 3u; step++) {
let l = layer_at(o, mask, step, local, centre);
if (l.c >= 0.5 && l.z < z && painted(o, array<u32, 3>(2u, 0u, 1u)[step], up).a >= opacity) {
z = l.z;
}
}
}
return z;
}
// A light's map, or a view's opaque depth: its paths' nearest depth where it is nearer than its meshes' (the depth
// test's).
@fragment
fn fs_nearest(@builtin(position) at: vec4<f32>) -> @builtin(frag_depth) f32 {
let z = nearest(vec2<u32>(at.xy), select(0.5, 1.0 - 1e-5, view_depth));
if (z > 0.5) {
discard;
}
return select(z + 1.0, -z, view_depth); // (z / w, as its meshes write it: a light's from the near plane, a view's reversed)
}