nordisk/facett

facett-graphview/src/fdeb.wgsl

// FDEB — force-directed edge bundling, the force iteration as a compute kernel.
//
// One invocation per (edge, interior point). Reads the previous iteration's points
// from `src`, writes the next into `dst`; the host ping-pongs the two buffers, so
// the endpoints (i = 0 and i = m + 1), which are never written, stay put in both.
// This is `facett_graphview::fdeb::bundle`'s inner loop, term for term: a spring to
// the wire's own neighbours weighted `kp`, plus inverse-distance attraction to the
// matching point of every compatible wire, weighted by the precomputed compatibility.
// Guarded by `xtask/tests/wgsl_compiles_in_the_browser.rs` (Tint) like every shader.

struct Params { n: u32, m: u32, step: f32, _pad: f32 };
struct EdgeMeta { kp: f32, off: u32, cnt: u32, _pad: u32 };
struct Compat { q: u32, c: f32 };

@group(0) @binding(0) var<uniform> P: Params;
@group(0) @binding(1) var<storage, read> src: array<vec2<f32>>;
@group(0) @binding(2) var<storage, read_write> dst: array<vec2<f32>>;
@group(0) @binding(3) var<storage, read> edge_meta: array<EdgeMeta>;
@group(0) @binding(4) var<storage, read> compat: array<Compat>;

@compute @workgroup_size(64)
fn cs_fdeb(@builtin(global_invocation_id) gid: vec3<u32>) {
    let id = gid.x;
    if (id >= P.n * P.m) { return; }
    let e = id / P.m;
    let i = 1u + (id % P.m);
    let stride = P.m + 2u;
    let base = e * stride;
    let cur = src[base + i];
    let nb = src[base + i - 1u];
    let nf = src[base + i + 1u];
    var force = edge_meta[e].kp * ((nb - cur) + (nf - cur));
    let off = edge_meta[e].off;
    let cnt = edge_meta[e].cnt;
    for (var k = 0u; k < cnt; k = k + 1u) {
        let ce = compat[off + k];
        let d = src[ce.q * stride + i] - cur;
        let dist = max(length(d), 1e-3);
        force = force + d * (ce.c / dist);
    }
    dst[base + i] = cur + P.step * force;
}