Delaunay-Splitter — Triangulation, jede Kachel leicht gedreht

// Delaunay shatter — pick the four image corners + N random interior
// points, triangulate them with a hand-rolled Bowyer-Watson Delaunay,
// then affine-warp every triangle of the source onto the output with
// a small random rotation around its own centroid.
//
// Two interlocking pieces this demo proves out:
//   1. Real computational geometry inside the embedded QuickJS — pure
//      JS Bowyer-Watson, no native helper.
//   2. Per-triangle affine warp via Matrix.Mat3.estimateAffine + the
//      engine's warpPerspective, masked through a triangle-shaped
//      Canvas path. Same mask/blend pattern as demo_shatter_cuts, but
//      with affine reprojection layered on top so the imagery inside
//      each tile rotates with the tile rather than staying axis-aligned.

//!INPUT: SRC
//!OUTPUT: OUT
//!PARAM: POINTS:integer=20,min=4,max=200
//!PARAM: MAX_ROT_DEG:number=8,min=0,max=45,step=0.5
//!PARAM: SHADOW_OFFSET:integer=6,min=0,max=40
//!PARAM: SHADOW_BLUR:number=10,min=0,max=40,step=0.5
//!PARAM: SHADOW_OPACITY:number=0.45,min=0,max=1,step=0.05
//!PARAM: TILE_ALPHA:number=1.0,min=0.1,max=1,step=0.05
//!PARAM: SEED:integer=42,min=0,max=1000000

// ── Seeded LCG (same shape as demo_shatter_cuts) ───────────────────
let state = SEED === 0 ? Math.floor(Math.random() * 1000000) : SEED;
const rand = () => {
    state = (state * 1103515245 + 12345) % 2147483648;
    return state / 2147483648;
};

// ── Bowyer-Watson Delaunay triangulation ───────────────────────────
// Returns: array of [i, j, k] index triples into `pts` (CCW).
// Algorithm: start with one huge enclosing super-triangle; insert each
// point one at a time, removing every triangle whose circumcircle
// contains the new point and re-triangulating the resulting hole by
// connecting the point to every boundary edge. After all points are
// in, drop the triangles that still touch a super-triangle vertex.
function delaunayBW(pts) {
    const n = pts.length;

    // Super-triangle large enough to enclose everything.
    let minX = Infinity, minY = Infinity, maxX = -Infinity, maxY = -Infinity;
    for (const p of pts) {
        if (p[0] < minX) minX = p[0]; if (p[0] > maxX) maxX = p[0];
        if (p[1] < minY) minY = p[1]; if (p[1] > maxY) maxY = p[1];
    }
    const span = Math.max(maxX - minX, maxY - minY) * 20;
    const midX = (minX + maxX) / 2, midY = (minY + maxY) / 2;
    const all = pts.slice();
    all.push([midX - span, midY - span]); // n
    all.push([midX + span, midY - span]); // n+1
    all.push([midX,        midY + span]); // n+2

    // In-circumcircle test: positive determinant ⇔ p inside circle
    // through (a, b, c) when (a, b, c) wound CCW.
    function inCircumcircle(p, a, b, c) {
        const ax = a[0] - p[0], ay = a[1] - p[1];
        const bx = b[0] - p[0], by = b[1] - p[1];
        const cx = c[0] - p[0], cy = c[1] - p[1];
        const aSq = ax * ax + ay * ay;
        const bSq = bx * bx + by * by;
        const cSq = cx * cx + cy * cy;
        return (
            ax * (by * cSq - cy * bSq) -
            ay * (bx * cSq - cx * bSq) +
            aSq * (bx * cy - by * cx)
        ) > 0;
    }

    // Force CCW winding so the in-circle test signs out correctly.
    function ccw(i, j, k) {
        const a = all[i], b = all[j], c = all[k];
        const cross = (b[0] - a[0]) * (c[1] - a[1]) - (b[1] - a[1]) * (c[0] - a[0]);
        return cross > 0 ? [i, j, k] : [i, k, j];
    }

    let tris = [ccw(n, n + 1, n + 2)];

    for (let p = 0; p < n; p++) {
        const point = all[p];
        const survivors = [];
        const edgeCount = new Map();
        const bump = (a, b) => {
            const key = a < b ? a * 100000 + b : b * 100000 + a;
            edgeCount.set(key, (edgeCount.get(key) || 0) + 1);
        };
        for (const t of tris) {
            if (inCircumcircle(point, all[t[0]], all[t[1]], all[t[2]])) {
                bump(t[0], t[1]); bump(t[1], t[2]); bump(t[2], t[0]);
            } else {
                survivors.push(t);
            }
        }
        // Each boundary edge of the hole is one that appeared exactly
        // once; shared edges between bad triangles got counted twice
        // and are interior.
        tris = survivors;
        for (const [key, count] of edgeCount) {
            if (count !== 1) continue;
            const a = Math.floor(key / 100000), b = key % 100000;
            tris.push(ccw(a, b, p));
        }
    }

    // Drop triangles that still reference a super-triangle vertex.
    return tris.filter(t => t[0] < n && t[1] < n && t[2] < n);
}

// ── Demo ───────────────────────────────────────────────────────────
const img = Engine.loadImage(SRC);
const W = img.width, H = img.height;

// 4 corners + N random interior points (kept ≥ 20 px from the edge
// so the triangles around the rim aren't slivers).
const points = [
    [0, 0], [W - 1, 0], [W - 1, H - 1], [0, H - 1],
];
const margin = 20;
for (let i = 0; i < POINTS; i++) {
    points.push([
        Math.floor(rand() * (W - margin * 2)) + margin,
        Math.floor(rand() * (H - margin * 2)) + margin,
    ]);
}

const tris = delaunayBW(points);
const out = Engine.createImage(W, H);

// Precompute each triangle's source + rotated-destination vertices.
// Two-pass rendering (shadows then content) needs the same dst geometry
// in both passes; computing once avoids re-seeding the RNG between
// passes and keeps both visually aligned.
const tileData = [];
for (const [i, j, k] of tris) {
    const a = points[i], b = points[j], c = points[k];
    const cenX = (a[0] + b[0] + c[0]) / 3;
    const cenY = (a[1] + b[1] + c[1]) / 3;
    const angle = (rand() * 2 - 1) * MAX_ROT_DEG * Math.PI / 180;
    const cosA = Math.cos(angle), sinA = Math.sin(angle);
    const rotP = (p) => [
        cenX + (p[0] - cenX) * cosA - (p[1] - cenY) * sinA,
        cenY + (p[0] - cenX) * sinA + (p[1] - cenY) * cosA,
    ];
    tileData.push({ src: [a, b, c], dst: [rotP(a), rotP(b), rotP(c)] });
}

// Helper: rasterise the dst triangle as a white-on-transparent mask.
function buildTriangleMask(dst) {
    const cv = Engine.createCanvas(W, H);
    const path = Engine.createPath();
    path.moveTo(dst[0][0], dst[0][1]);
    path.lineTo(dst[1][0], dst[1][1]);
    path.lineTo(dst[2][0], dst[2][1]);
    path.close();
    cv.fill('#fff').drawPath(path);
    const mask = cv.toImage();
    path.free();
    cv.free();
    return mask;
}

// Pass 1 — shadows. For each tile build the dst-triangle silhouette,
// tint it black, blur the edges, and blend it onto `out` at an offset
// down-right. Tiles drawn later (in pass 2) cover their own shadow
// footprint, so only the offset/blurred fringe survives — giving the
// shards a floating-above-the-canvas look. Skipped entirely when
// SHADOW_OPACITY = 0 so the "no-shadow" path costs nothing.
if (SHADOW_OPACITY > 0) {
    for (const td of tileData) {
        const mask = buildTriangleMask(td.dst);
        const shadow = Engine.createColoredImage(W, H, '#000000');
        shadow.applyMask(mask);
        if (SHADOW_BLUR > 0) shadow.gaussianBlur(SHADOW_BLUR);
        out.blendAt(shadow, px(SHADOW_OFFSET, SHADOW_OFFSET),
                    SHADOW_OPACITY, Blend.Over);
        shadow.free();
        mask.free();
    }
}

// Pass 2 — triangle content. Affine-warp the source through the
// src→dst map, mask to the dst triangle, blend over the shadow pass.
// TILE_ALPHA < 1 mixes shadow + previous tiles through the rendered
// content — useful for a "stained-glass" feel.
for (const td of tileData) {
    const M = Matrix.Mat3.estimateAffine(td.src, td.dst);
    const warped = img.clone().warpPerspective(W, H, M);
    const mask = buildTriangleMask(td.dst);
    warped.applyMask(mask);
    out.blendAt(warped, px(0, 0), TILE_ALPHA, Blend.Over);
    warped.free();
    mask.free();
}

out.save(OUT);
out.free();
img.free();

// © 2026 Michael Lechner · mlc OpticScript · https://mlcgo.eu · Elastic License 2.0