Skip to content

A fast 2D and 3D game engine — TypeScript SDK, C++/WebAssembly core, visual editor. Ship one project to web, desktop, WeChat MiniGames, playable ads, and native Android / iOS.

23.9 KB
Raw Blame
// SPDX-License-Identifier: Apache-2.0
// SPDX-FileCopyrightText: Copyright (c) 2024-present ESEngine Team
/**
 * @file  vectorPath.ts
 * @brief Polygons, polylines and strokes as geometry a MeshRenderer draws.
 *
 * A path is a list of points. {@link buildPathGeometry} turns it into the triangles of its fill (ear clipping, holes allowed) and of its
 * stroke (a width, a join at every corner, a cap at each end), with an optional feathered edge standing in for anti-aliasing where the
 * quality level draws without multisampling. The result is a {@link MeshRendererGeometry}: a MeshRenderer draws it, sorts it with every other
 * renderable, batches it, and a scene saves it the way it saves any mesh geometry, so a path costs no renderer of its own.
 *
 * Pure: no engine, no DOM. Curves are flattened here ({@link cubicBezier}, {@link quadraticBezier}, {@link circlePoints}) into the points a
 * stroke and a fill take.
 */
import type { MeshRendererGeometry } from '../ecs/component';
import type { Vec2 } from '../types';

/** Red, green, blue and alpha, each 0 to 1. */
export type PathColor = readonly [number, number, number, number];

/** How two stroked segments meet at a corner. */
export type LineJoin = 'miter' | 'round' | 'bevel';
/** How an open stroke ends. */
export type LineCap = 'butt' | 'round' | 'square';

/** @experimental */
export interface PathFill {
    color: PathColor;
    /** Rings cut out of the fill. Each is a list of points inside the outline. */
    holes?: readonly (readonly Vec2[])[];
}

/** @experimental */
export interface PathStroke {
    color: PathColor;
    /** The full width of the line, in the units of the points. */
    width: number;
    join?: LineJoin;
    cap?: LineCap;
    /** How far a miter may reach, as a multiple of half the width, before the corner is bevelled instead. Default 4. */
    miterLimit?: number;
}

/** @experimental */
export interface PathStyle {
    fill?: PathFill;
    stroke?: PathStroke;
    /** The outline joins its last point back to its first: a stroke has no caps, a fill needs it either way. Default false. */
    closed?: boolean;
    /** Width of a fade to transparent along every outer edge, in the units of the points: anti-aliasing for a surface drawn without multisampling. 0 (default) draws hard edges. */
    feather?: number;
    /** How finely a round join or cap is cut, as the angle one slice may turn through, in radians. Default 0.25. */
    arcStep?: number;
}

const EPS = 1e-6;

interface Builder {
    positions: number[];
    colors: number[];
    indices: number[];
}

const newBuilder = (): Builder => ({ positions: [], colors: [], indices: [] });

function vertex(b: Builder, x: number, y: number, c: PathColor, alpha = 1): number {
    b.positions.push(x, y);
    b.colors.push(c[0], c[1], c[2], c[3] * alpha);
    return b.positions.length / 2 - 1;
}

const tri = (b: Builder, a: number, c: number, d: number): void => { b.indices.push(a, c, d); };

/** Consecutive points nearer than this are one point. */
function dedupe(points: readonly Vec2[], closed: boolean): Vec2[] {
    const out: Vec2[] = [];
    for (const p of points) {
        const last = out[out.length - 1];
        if (!last || Math.hypot(p.x - last.x, p.y - last.y) > EPS) out.push({ x: p.x, y: p.y });
    }
    if (closed && out.length > 1) {
        const first = out[0]!;
        const last = out[out.length - 1]!;
        if (Math.hypot(first.x - last.x, first.y - last.y) <= EPS) out.pop();
    }
    return out;
}

const signedArea = (ring: readonly Vec2[]): number => {
    let sum = 0;
    for (let i = 0; i < ring.length; i++) {
        const a = ring[i]!;
        const b = ring[(i + 1) % ring.length]!;
        sum += a.x * b.y - b.x * a.y;
    }
    return sum / 2;
};

// ---------------------------------------------------------------------------------------------------------------------
// Fill
// ---------------------------------------------------------------------------------------------------------------------

const cross2 = (ax: number, ay: number, bx: number, by: number): number => ax * by - ay * bx;

function segmentsCross(a: Vec2, b: Vec2, c: Vec2, d: Vec2): boolean {
    const d1 = cross2(b.x - a.x, b.y - a.y, c.x - a.x, c.y - a.y);
    const d2 = cross2(b.x - a.x, b.y - a.y, d.x - a.x, d.y - a.y);
    const d3 = cross2(d.x - c.x, d.y - c.y, a.x - c.x, a.y - c.y);
    const d4 = cross2(d.x - c.x, d.y - c.y, b.x - c.x, b.y - c.y);
    return ((d1 > EPS && d2 < -EPS) || (d1 < -EPS && d2 > EPS)) && ((d3 > EPS && d4 < -EPS) || (d3 < -EPS && d4 > EPS));
}

/**
 * Joins each hole to the outline by a bridge (the shortest segment from a hole's point to the ring that crosses no edge), so the ring and its
 * holes are one ring that visits the bridge twice. Both are made counter-clockwise (outline) and clockwise (holes) first.
 */
function bridgeHoles(outline: Vec2[], holes: readonly (readonly Vec2[])[]): Vec2[] {
    let ring = outline.slice();
    const rings = holes
        .map((h) => dedupe(h, true))
        .filter((h) => h.length >= 3)
        .map((h) => (signedArea(h) > 0 ? h.slice().reverse() : h))
        // The hole furthest right first: it cannot be hidden behind another that is joined already.
        .sort((a, b) => Math.max(...b.map((p) => p.x)) - Math.max(...a.map((p) => p.x)));
    for (const hole of rings) {
        let best: { r: number; h: number; d: number } | null = null;
        for (let h = 0; h < hole.length; h++) {
            for (let r = 0; r < ring.length; r++) {
                const d = Math.hypot(hole[h]!.x - ring[r]!.x, hole[h]!.y - ring[r]!.y);
                if (best && d >= best.d) continue;
                if (blocked(ring, rings, hole[h]!, ring[r]!)) continue;
                best = { r, h, d };
            }
        }
        if (!best) continue;
        const spliced: Vec2[] = [];
        for (let i = 0; i <= best.r; i++) spliced.push(ring[i]!);
        for (let k = 0; k <= hole.length; k++) spliced.push(hole[(best.h + k) % hole.length]!);
        spliced.push(ring[best.r]!);
        for (let i = best.r + 1; i < ring.length; i++) spliced.push(ring[i]!);
        ring = spliced;
    }
    return ring;
}

function blocked(ring: readonly Vec2[], holes: readonly (readonly Vec2[])[], a: Vec2, b: Vec2): boolean {
    const crossesRing = (pts: readonly Vec2[]): boolean => {
        for (let i = 0; i < pts.length; i++) if (segmentsCross(a, b, pts[i]!, pts[(i + 1) % pts.length]!)) return true;
        return false;
    };
    if (crossesRing(ring)) return true;
    for (const h of holes) if (crossesRing(h)) return true;
    return false;
}

function pointInTriangle(p: Vec2, a: Vec2, b: Vec2, c: Vec2): boolean {
    const d1 = cross2(b.x - a.x, b.y - a.y, p.x - a.x, p.y - a.y);
    const d2 = cross2(c.x - b.x, c.y - b.y, p.x - b.x, p.y - b.y);
    const d3 = cross2(a.x - c.x, a.y - c.y, p.x - c.x, p.y - c.y);
    return d1 >= -EPS && d2 >= -EPS && d3 >= -EPS;
}

/** Triangles (as indices into `ring`) covering a counter-clockwise ring, which may visit a point twice (a bridge). */
function earClip(ring: readonly Vec2[]): number[] {
    const n = ring.length;
    const next: number[] = [];
    const prev: number[] = [];
    for (let i = 0; i < n; i++) { next.push((i + 1) % n); prev.push((i + n - 1) % n); }
    const out: number[] = [];
    let remaining = n;
    let i = 0;
    let guard = 0;
    const same = (p: Vec2, q: Vec2): boolean => Math.abs(p.x - q.x) <= EPS && Math.abs(p.y - q.y) <= EPS;
    while (remaining > 3 && guard++ < n * n) {
        const a = prev[i]!;
        const c = next[i]!;
        const pa = ring[a]!, pb = ring[i]!, pc = ring[c]!;
        let ear = cross2(pb.x - pa.x, pb.y - pa.y, pc.x - pb.x, pc.y - pb.y) > EPS;
        if (ear) {
            for (let k = next[c]!; k !== a; k = next[k]!) {
                const q = ring[k]!;
                // A point shared with the triangle is a bridge's other end, not something in the way.
                if (same(q, pa) || same(q, pb) || same(q, pc)) continue;
                if (pointInTriangle(q, pa, pb, pc)) { ear = false; break; }
            }
        }
        if (ear) {
            out.push(a, i, c);
            next[a] = c;
            prev[c] = a;
            --remaining;
            i = c;
            guard = 0;
        } else {
            i = next[i]!;
        }
    }
    if (remaining === 3) {
        const a = prev[i]!;
        out.push(a, i, next[i]!);
    } else if (remaining > 3) {
        // No ear was found (a ring that crosses itself): fan what is left rather than lose the shape.
        for (let k = next[i]!; next[k]! !== i; k = next[k]!) out.push(i, k, next[k]!);
    }
    return out;
}

function emitFill(b: Builder, outline: readonly Vec2[], fill: PathFill, feather: number): void {
    let ring = dedupe(outline, true);
    if (ring.length < 3) return;
    if (signedArea(ring) < 0) ring = ring.slice().reverse();
    const holes = (fill.holes ?? []).map((h) => dedupe(h, true)).filter((h) => h.length >= 3);
    const joined = holes.length ? bridgeHoles(ring, holes) : ring;
    const base = b.positions.length / 2;
    for (const p of joined) vertex(b, p.x, p.y, fill.color);
    for (const i of earClip(joined)) b.indices.push(base + i);
    if (feather <= 0) return;
    // A fade outward from the outline and inward from each hole: the edge of the fill is where the colour is a half.
    fringe(b, ring, fill.color, feather, 1);
    for (const h of holes) fringe(b, signedArea(h) > 0 ? h.slice().reverse() : h, fill.color, feather, -1);
}

/** A band of transparent-to-opaque quads along a counter-clockwise ring, `side` 1 outside it and -1 inside. */
function fringe(b: Builder, ring: readonly Vec2[], color: PathColor, width: number, side: 1 | -1): void {
    const n = ring.length;
    const inner: number[] = [];
    const outer: number[] = [];
    for (let i = 0; i < n; i++) {
        const p = ring[i]!, a = ring[(i + n - 1) % n]!, c = ring[(i + 1) % n]!;
        // Outward normals of the two edges at this point (counter-clockwise: outward is to the right of travel).
        const e0x = p.x - a.x, e0y = p.y - a.y, e1x = c.x - p.x, e1y = c.y - p.y;
        const l0 = Math.hypot(e0x, e0y) || 1, l1 = Math.hypot(e1x, e1y) || 1;
        let nx = e0y / l0 + e1y / l1;
        let ny = -(e0x / l0) - e1x / l1;
        const nl = Math.hypot(nx, ny);
        if (nl < EPS) { nx = e0y / l0; ny = -e0x / l0; } else { nx /= nl; ny /= nl; }
        // Where the two edges bend sharply the offset along the bisector grows by 1 / cos(half the turn); bounded so a spike stays a spike.
        const cosHalf = Math.max(nx * (e0y / l0) + ny * (-e0x / l0), 0.3);
        const d = (width / cosHalf) * side;
        inner.push(vertex(b, p.x, p.y, color));
        outer.push(vertex(b, p.x + nx * d, p.y + ny * d, color, 0));
    }
    for (let i = 0; i < n; i++) {
        const j = (i + 1) % n;
        tri(b, inner[i]!, outer[i]!, outer[j]!);
        tri(b, inner[i]!, outer[j]!, inner[j]!);
    }
}

// ---------------------------------------------------------------------------------------------------------------------
// Stroke
// ---------------------------------------------------------------------------------------------------------------------

/** One point of a stroke's outline with the direction that points away from the line there, for the feathered edge. */
interface Edge { index: number; x: number; y: number; ox: number; oy: number }

function emitStroke(b: Builder, input: readonly Vec2[], stroke: PathStroke, closed: boolean, feather: number, arcStep: number): void {
    const pts = dedupe(input, closed);
    const half = stroke.width / 2;
    if (pts.length < 2 || half <= 0) return;
    const n = pts.length;
    const join = stroke.join ?? 'miter';
    const cap = stroke.cap ?? 'butt';
    const limit = Math.max(stroke.miterLimit ?? 4, 1);
    const color = stroke.color;
    const segs = closed ? n : n - 1;

    // Direction and left normal of each segment.
    const dx: number[] = [], dy: number[] = [], len: number[] = [];
    for (let i = 0; i < segs; i++) {
        const a = pts[i]!, c = pts[(i + 1) % n]!;
        const l = Math.hypot(c.x - a.x, c.y - a.y);
        len.push(l);
        dx.push((c.x - a.x) / l);
        dy.push((c.y - a.y) / l);
    }

    // Per point: the point on the inside of the turn, and what the outside needs. `left`/`right` chains run along the line, in order, and hold
    // each outline point with its outward direction (the feathered edge is made from them).
    const leftIn: number[] = new Array(n).fill(-1), leftOut: number[] = new Array(n).fill(-1);
    const rightIn: number[] = new Array(n).fill(-1), rightOut: number[] = new Array(n).fill(-1);
    const left: Edge[] = [];
    const right: Edge[] = [];

    const push = (chain: Edge[], x: number, y: number, ox: number, oy: number): number => {
        const index = vertex(b, x, y, color);
        chain.push({ index, x, y, ox, oy });
        return index;
    };

    for (let i = 0; i < n; i++) {
        const p = pts[i]!;
        const hasPrev = closed || i > 0;
        const hasNext = closed || i < n - 1;
        const s0 = hasPrev ? (i + segs - 1) % segs : -1;
        const s1 = hasNext ? i % segs : -1;
        if (!hasPrev || !hasNext) {
            // An end: the normal of the one segment, set back by a square cap and fanned by a round one in {@link emitCap}.
            const s = hasNext ? s1 : s0;
            const ndx = dx[s]!, ndy = dy[s]!;
            const lx = -ndy, ly = ndx;
            const back = hasNext ? -1 : 1;
            const push0 = cap === 'square' ? half * back : 0;
            const bx = p.x + ndx * push0, by = p.y + ndy * push0;
            const l = push(left, bx + lx * half, by + ly * half, lx, ly);
            const r = push(right, bx - lx * half, by - ly * half, -lx, -ly);
            leftIn[i] = leftOut[i] = l;
            rightIn[i] = rightOut[i] = r;
            continue;
        }
        const d0x = dx[s0]!, d0y = dy[s0]!, d1x = dx[s1]!, d1y = dy[s1]!;
        const turn = cross2(d0x, d0y, d1x, d1y);
        const l0x = -d0y, l0y = d0x, l1x = -d1y, l1y = d1x;
        let mx = l0x + l1x, my = l0y + l1y;
        const ml = Math.hypot(mx, my);
        if (ml < EPS) { mx = l0x; my = l0y; } else { mx /= ml; my /= ml; }
        const cosHalf = Math.max(mx * l0x + my * l0y, 1e-3);
        // The inside of the turn: one point, where the two inner edges meet, held back so a short segment is not overrun.
        const reach = Math.min(half / cosHalf, Math.max(Math.min(len[s0]!, len[s1]!) / Math.max(Math.sqrt(1 - cosHalf * cosHalf) / cosHalf, 1e-3), half));
        // turn > 0: a left turn, the left side is the inside.
        const insideLeft = turn > 0;
        const straight = Math.abs(turn) < 1e-5 && d0x * d1x + d0y * d1y > 0;
        const miterRatio = 1 / cosHalf;
        const useMiter = straight || (join === 'miter' && miterRatio <= limit);
        const sign = insideLeft ? 1 : -1;     // +1: the left side is the inside
        const insideChain = insideLeft ? left : right;
        const outsideChain = insideLeft ? right : left;
        const insideIdx = insideLeft ? leftIn : rightIn, insideOut = insideLeft ? leftOut : rightOut;
        const outsideIdx = insideLeft ? rightIn : leftIn, outsideOutIdx = insideLeft ? rightOut : leftOut;
        // Inside point.
        const ip = push(insideChain, p.x + sign * mx * reach, p.y + sign * my * reach, sign * mx, sign * my);
        insideIdx[i] = insideOut[i] = ip;
        if (useMiter) {
            const oreach = half / cosHalf;
            const op = push(outsideChain, p.x - sign * mx * oreach, p.y - sign * my * oreach, -sign * mx, -sign * my);
            outsideIdx[i] = outsideOutIdx[i] = op;
            continue;
        }
        // The outside of the turn: the end of the incoming edge, an arc or nothing, the start of the outgoing one.
        const o0x = -sign * l0x, o0y = -sign * l0y, o1x = -sign * l1x, o1y = -sign * l1y;
        const first = push(outsideChain, p.x + o0x * half, p.y + o0y * half, o0x, o0y);
        outsideIdx[i] = first;
        let last = first;
        if (join === 'round') {
            const a0 = Math.atan2(o0y, o0x);
            let a1 = Math.atan2(o1y, o1x);
            let delta = a1 - a0;
            while (delta > Math.PI) delta -= Math.PI * 2;
            while (delta < -Math.PI) delta += Math.PI * 2;
            const steps = Math.max(1, Math.ceil(Math.abs(delta) / arcStep));
            let prevIdx = first;
            for (let k = 1; k < steps; k++) {
                const a = a0 + (delta * k) / steps;
                const ax = Math.cos(a), ay = Math.sin(a);
                const mid = push(outsideChain, p.x + ax * half, p.y + ay * half, ax, ay);
                tri(b, ip, prevIdx, mid);
                prevIdx = mid;
            }
            last = push(outsideChain, p.x + o1x * half, p.y + o1y * half, o1x, o1y);
            tri(b, ip, prevIdx, last);
        } else {
            // Bevel (and a miter past its limit): the two outer corners joined by a straight edge.
            last = push(outsideChain, p.x + o1x * half, p.y + o1y * half, o1x, o1y);
            tri(b, ip, first, last);
        }
        outsideOutIdx[i] = last;
    }

    // The body: a quad per segment, from the end of one point's outline to the start of the next.
    for (let s = 0; s < segs; s++) {
        const i = s, j = (s + 1) % n;
        const lA = leftOut[i]!, rA = rightOut[i]!, lB = leftIn[j]!, rB = rightIn[j]!;
        tri(b, lA, rA, rB);
        tri(b, lA, rB, lB);
    }

    // Caps.
    if (!closed && cap === 'round') {
        emitRoundCap(b, pts[0]!, -dx[0]!, -dy[0]!, half, color, arcStep, leftIn[0]!, rightIn[0]!);
        emitRoundCap(b, pts[n - 1]!, dx[segs - 1]!, dy[segs - 1]!, half, color, arcStep, rightOut[n - 1]!, leftOut[n - 1]!);
    }

    if (feather > 0) {
        // The line's edge fades over `feather` beyond the outline. A closed line has two loops (outer and inner); an open one has one outline.
        const bandEdge = (chain: readonly Edge[]): void => {
            const outs: number[] = [];
            for (const e of chain) outs.push(vertex(b, e.x + e.ox * feather, e.y + e.oy * feather, color, 0));
            for (let k = 0; k + 1 < chain.length; k++) {
                tri(b, chain[k]!.index, outs[k]!, outs[k + 1]!);
                tri(b, chain[k]!.index, outs[k + 1]!, chain[k + 1]!.index);
            }
            if (closed && chain.length > 2) {
                const k = chain.length - 1;
                tri(b, chain[k]!.index, outs[k]!, outs[0]!);
                tri(b, chain[k]!.index, outs[0]!, chain[0]!.index);
            }
        };
        bandEdge(left);
        bandEdge(right);
        if (!closed) {
            // Butt and square ends fade across the end face.
            if (cap !== 'round') {
                for (const [first, second, dirx, diry] of [
                    [left[0]!, right[0]!, -dx[0]!, -dy[0]!],
                    [left[left.length - 1]!, right[right.length - 1]!, dx[segs - 1]!, dy[segs - 1]!],
                ] as const) {
                    const a = vertex(b, first.x + dirx * feather, first.y + diry * feather, color, 0);
                    const c = vertex(b, second.x + dirx * feather, second.y + diry * feather, color, 0);
                    tri(b, first.index, a, c);
                    tri(b, first.index, c, second.index);
                }
            }
        }
    }
}

/** A half circle of `radius` at `center` bulging along (dirx, diry), between two outline points already placed. */
function emitRoundCap(b: Builder, center: Vec2, dirx: number, diry: number, radius: number, color: PathColor, arcStep: number, from: number, to: number): void {
    const a0 = Math.atan2(diry, dirx) - Math.PI / 2;
    const steps = Math.max(2, Math.ceil(Math.PI / arcStep));
    const c = vertex(b, center.x, center.y, color);
    let prev = from;
    for (let k = 1; k < steps; k++) {
        const a = a0 + (Math.PI * k) / steps;
        const v = vertex(b, center.x + Math.cos(a) * radius, center.y + Math.sin(a) * radius, color);
        tri(b, c, prev, v);
        prev = v;
    }
    tri(b, c, prev, to);
}

// ---------------------------------------------------------------------------------------------------------------------
// Entry points
// ---------------------------------------------------------------------------------------------------------------------

/**
 * The geometry of a path: its fill, then its stroke on top, as one mesh in the path's own coordinates.
 * An empty result (fewer than the points a shape needs) is a mesh with nothing in it, which draws nothing.
 * @experimental
 */
export function buildPathGeometry(points: readonly Vec2[], style: PathStyle): MeshRendererGeometry {
    const b = newBuilder();
    const feather = Math.max(style.feather ?? 0, 0);
    const arcStep = Math.max(style.arcStep ?? 0.25, 0.05);
    const closed = style.closed ?? false;
    if (style.fill) emitFill(b, points, style.fill, feather);
    if (style.stroke) emitStroke(b, points, style.stroke, closed, feather, arcStep);
    return { positions: b.positions, colors: b.colors, indices: b.indices };
}

/** The geometry of several paths drawn into one mesh, in order. */
export function mergeGeometry(parts: readonly MeshRendererGeometry[]): MeshRendererGeometry {
    const out: MeshRendererGeometry = { positions: [], colors: [], indices: [] };
    for (const part of parts) {
        const base = out.positions.length / 2;
        for (const v of part.positions) out.positions.push(v);
        for (const c of part.colors ?? []) out.colors!.push(c);
        for (const i of part.indices) out.indices.push(base + i);
    }
    return out;
}

/** A cubic Bezier curve as points, cut finely enough that no point is further than `tolerance` from the curve. @experimental */
export function cubicBezier(p0: Vec2, p1: Vec2, p2: Vec2, p3: Vec2, tolerance = 0.25): Vec2[] {
    // The flatness bound of a Bezier: the control polygon's distance from its chord says how many pieces keep the error under tolerance.
    const ux = 3 * p1.x - 2 * p0.x - p3.x, uy = 3 * p1.y - 2 * p0.y - p3.y;
    const vx = 3 * p2.x - 2 * p3.x - p0.x, vy = 3 * p2.y - 2 * p3.y - p0.y;
    const dev = Math.sqrt(Math.max(ux * ux, vx * vx) + Math.max(uy * uy, vy * vy));
    const steps = Math.min(Math.max(Math.ceil(Math.sqrt(dev / (4 * Math.max(tolerance, 1e-4)))), 1), 256);
    const out: Vec2[] = [];
    for (let i = 0; i <= steps; i++) {
        const t = i / steps, m = 1 - t;
        out.push({
            x: m * m * m * p0.x + 3 * m * m * t * p1.x + 3 * m * t * t * p2.x + t * t * t * p3.x,
            y: m * m * m * p0.y + 3 * m * m * t * p1.y + 3 * m * t * t * p2.y + t * t * t * p3.y,
        });
    }
    return out;
}

/** A quadratic Bezier curve as points. @experimental */
export function quadraticBezier(p0: Vec2, p1: Vec2, p2: Vec2, tolerance = 0.25): Vec2[] {
    // Raised to a cubic: one flattening to keep right.
    const c1 = { x: p0.x + (2 / 3) * (p1.x - p0.x), y: p0.y + (2 / 3) * (p1.y - p0.y) };
    const c2 = { x: p2.x + (2 / 3) * (p1.x - p2.x), y: p2.y + (2 / 3) * (p1.y - p2.y) };
    return cubicBezier(p0, c1, c2, p2, tolerance);
}

/** The points of a circle (or a slice of one: angles in radians, counter-clockwise from +x). @experimental */
export function circlePoints(cx: number, cy: number, radius: number, segments = 0, startAngle = 0, endAngle = Math.PI * 2): Vec2[] {
    const full = Math.abs(endAngle - startAngle) >= Math.PI * 2 - 1e-9;
    const n = segments > 0 ? segments : Math.max(Math.ceil(Math.abs(endAngle - startAngle) / Math.max(Math.acos(1 - 0.25 / Math.max(radius, 0.25)) * 2, 0.05)), 8);
    const out: Vec2[] = [];
    const count = full ? n : n + 1;
    for (let i = 0; i < count; i++) {
        const a = startAngle + ((endAngle - startAngle) * i) / n;
        out.push({ x: cx + Math.cos(a) * radius, y: cy + Math.sin(a) * radius });
    }
    return out;
}

/**
 * The triangles (indices into `ring`) that cover a simple polygon, whichever way round it is given.
 * @experimental
 */
export function triangulateRing(ring: readonly Vec2[]): number[] {
    if (ring.length < 3) return [];
    if (signedArea(ring) >= 0) return earClip(ring);
    // Clockwise: clip the reverse and map the indices back.
    const n = ring.length;
    return earClip(ring.slice().reverse()).map((i) => n - 1 - i);
}