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.

13.4 KB
Raw Blame
// SPDX-License-Identifier: Apache-2.0
// SPDX-FileCopyrightText: Copyright (c) 2024-present ESEngine Team
/**
 * @file  fracture.ts — the `fracture` step: a solid cut into the pieces it breaks into.
 *
 *        A thing that breaks in a game is not broken when it is hit. It was cut beforehand into pieces that fit
 *        together with no gap, drawn as one until the blow, and let go as many after it. This is the cutting.
 *
 *        The pieces are the cells of points scattered through the solid: each piece is what lies nearer its own
 *        point than any other, so the cuts are flat, every piece is convex where the solid is, and the pieces fill
 *        the solid exactly. Points crowded toward a place make small pieces there and large ones far off, which is
 *        how a pane breaks round a stone. Each cut is made by Manifold, as a boolean is, so a piece is a closed
 *        solid with no slivers; its new faces, the inside of the thing, are tagged apart from its skin.
 */
import { PREFAB_FORMAT_VERSION } from 'esengine';
import { loadedEngine, notSolid, toSolid, type ManifoldEngine, type ManifoldSolid } from './booleans';
import { triangulateFace } from './triangulate';
import { boundsOf, compact, cross, dot, normalize, selectFaces, sub, type Face, type FaceSelector, type PolyMesh, type Vec3 } from './polyMesh';

export interface FractureParams {
    /** The closed solid to break. Default every face. */
    faces?: FaceSelector;
    /** How many pieces to aim for, 2..64. A point that falls where its cell misses the solid makes none, so there may be fewer. */
    pieces: number;
    seed?: number;
    /** Where it is struck: the pieces are smaller round here. */
    at?: Vec3;
    /** How much smaller, 0..1. Default 0.6 where `at` is given. */
    focus?: number;
    /** The tag of the faces a cut makes: the inside of the thing. Default "inside". */
    tag?: string;
    /** Their colour. Default the colour of the face nearest, a little darker. */
    color?: readonly number[];
}

/**
 * Faces a cut made carry this in place of the face they came from. Above any face index a model has, and below two
 * to the thirty-first: Manifold keeps an id as a signed number, and one past that comes back as something else.
 */
const INSIDE = 1_000_000_000;

function randomOf(seed: number): () => number {
    let s = (seed * 2654435761 + 0x9e3779b9) >>> 0;
    return () => {
        s = (s + 0x6d2b79f5) >>> 0;
        let t = s;
        t = Math.imul(t ^ (t >>> 15), t | 1);
        t ^= t + Math.imul(t ^ (t >>> 7), t | 61);
        return ((t ^ (t >>> 14)) >>> 0) / 4294967296;
    };
}

/** Everything on the near side of the plane through @p point that faces along @p normal: a box with that plane as one side, larger than the solid. */
function halfSpace(e: ManifoldEngine, point: Vec3, normal: Vec3, reach: number): ManifoldSolid {
    const n = normalize(normal);
    const u = normalize(cross(n, Math.abs(n[1]) < 0.9 ? [0, 1, 0] : [1, 0, 0]));
    const v = cross(n, u);
    const props: number[] = [];
    for (let i = 0; i < 8; i++) {
        const [x, y, z] = [i & 1 ? 0 : -2 * reach, i & 2 ? 2 * reach : -2 * reach, i & 4 ? 2 * reach : -2 * reach];
        props.push(point[0] + n[0] * x + u[0] * y + v[0] * z, point[1] + n[1] * x + u[1] * y + v[1] * z, point[2] + n[2] * x + u[2] * y + v[2] * z);
    }
    // Each side as two triangles, counter-clockwise from outside.
    const quads = [[0, 4, 6, 2], [1, 3, 7, 5], [0, 1, 5, 4], [2, 6, 7, 3], [0, 2, 3, 1], [4, 5, 7, 6]];
    const tris = quads.flatMap(([a, b, c, d]) => [a!, b!, c!, a!, c!, d!]);
    return new e.Manifold(new e.Mesh({ numProp: 3, vertProperties: new Float32Array(props), triVerts: new Uint32Array(tris), faceID: new Uint32Array(12).fill(INSIDE) }));
}

/** The solid as its pieces, in its place: together they are the solid it was, and each face says which piece it is of. */
export function fractureOp(mesh: PolyMesh, p: FractureParams): PolyMesh {
    const e = loadedEngine();
    if (!(Number.isInteger(p.pieces) && p.pieces >= 2 && p.pieces <= 64)) throw new Error('pieces must be a whole number, 2..64');
    if (p.focus !== undefined && !(p.focus >= 0 && p.focus <= 1)) throw new Error('focus must be 0..1');
    if (mesh.faces.some((f) => f.piece !== undefined)) throw new Error('this model is already in pieces: fracture once');
    const all = p.faces === undefined ? mesh.faces.map((_, i) => i) : selectFaces(mesh, p.faces);
    if (all.length === 0) throw new Error(`\`faces\` ${JSON.stringify(p.faces)} matched no face`);
    const bad = notSolid(mesh, all);
    if (bad) throw new Error(`what is to be broken is not a closed solid: ${bad}`);

    const used = new Set<number>();
    for (const f of all) for (const v of mesh.faces[f]!.v) used.add(v);
    const { min, max } = boundsOf(mesh, used);
    const size = sub(max, min);
    const reach = Math.hypot(size[0], size[1], size[2]) * 2 + 1e-6;
    const random = randomOf(p.seed ?? 1);
    const focus = p.at ? p.focus ?? 0.6 : 0;
    const triangulate = (face: Face): [number, number, number][] => triangulateFace(mesh, face);

    // Its points are drawn on its skin, by area, and set a hair inside it. A point drawn anywhere in its bounds falls
    // in air as often as not - inside a pot, round a ring - and the cell of a point in air may hold none of it, so a pot
    // asked for eight came out in two. One on the skin always has some of the thing nearest to it.
    const skin: { a: Vec3; b: Vec3; c: Vec3; inward: Vec3 }[] = [];
    const areas: number[] = [];
    let area = 0;
    for (const f of all) {
        for (const [i, j, k] of triangulate(mesh.faces[f]!)) {
            const [a, b, c] = [mesh.positions[i]!, mesh.positions[j]!, mesh.positions[k]!];
            const n = cross(sub(b, a), sub(c, a));
            const twice = Math.hypot(n[0], n[1], n[2]);
            if (twice < 1e-12) continue;
            skin.push({ a, b, c, inward: [-n[0] / twice, -n[1] / twice, -n[2] / twice] });
            area += twice / 2;
            areas.push(area);
        }
    }
    const hair = Math.hypot(size[0], size[1], size[2]) * 1e-3;
    const onSkin = (): Vec3 => {
        const want = random() * area;
        let lo = 0, hi = areas.length - 1;
        while (lo < hi) { const mid = (lo + hi) >> 1; if (areas[mid]! < want) lo = mid + 1; else hi = mid; }
        const t = skin[lo]!;
        let [u, v] = [random(), random()];
        if (u + v > 1) [u, v] = [1 - u, 1 - v];
        return [0, 1, 2].map((i) => t.a[i]! + (t.b[i]! - t.a[i]!) * u + (t.c[i]! - t.a[i]!) * v + t.inward[i]! * hair) as unknown as Vec3;
    };
    // Toward where it is struck: of a few points drawn, the nearest the blow is kept, more of them the more focus.
    const tries = p.at && focus > 0 ? 1 + Math.round(8 * focus) : 1;
    const draw = (): Vec3 => {
        let best = onSkin();
        if (!p.at) return best;
        const far = (q: Vec3): number => Math.hypot(q[0] - p.at![0], q[1] - p.at![1], q[2] - p.at![2]);
        for (let i = 1; i < tries; i++) { const q = onSkin(); if (far(q) < far(best)) best = q; }
        return best;
    };
    const seeds: Vec3[] = Array.from({ length: p.pieces }, draw);
    const whole = toSolid(e, mesh, all, triangulate);
    const allSet = new Set(all);
    let positions: Vec3[] = [];
    let made: Face[] = [];
    let count = 0;
    // A cell that is a sliver is a piece nobody sees and a body that jitters. Its point is taken out and the others
    // worked out again, which gives its share to its neighbours and leaves the solid as exactly filled as before.
    let live = seeds;
    try {
      for (let round = 0; round < 4; round++) {
        const seeds = live;
        positions = [...mesh.positions];
        made = [];
        count = 0;
        const volumes: number[] = [];
        const kept: number[] = [];
        for (let k = 0; k < seeds.length; k++) {
            // What of the solid is nearer this point than each of the others: one flat cut for every other point.
            let cell: ManifoldSolid = whole;
            for (let j = 0; j < seeds.length && !cell.isEmpty(); j++) {
                if (j === k) continue;
                const [a, b] = [seeds[k]!, seeds[j]!];
                const between = sub(b, a);
                if (dot(between, between) < 1e-18) continue;
                const cutter = halfSpace(e, [(a[0] + b[0]) / 2, (a[1] + b[1]) / 2, (a[2] + b[2]) / 2], between, reach);
                const next = cell.intersect(cutter);
                cutter.delete();
                if (cell !== whole) cell.delete();
                cell = next;
            }
            if (!cell.isEmpty()) {
                const out = cell.getMesh();
                const base = positions.length;
                for (let i = 0; i < out.vertProperties.length; i += out.numProp) positions.push([out.vertProperties[i]!, out.vertProperties[i + 1]!, out.vertProperties[i + 2]!]);
                // The colour a cut face takes where none is given: the skin's, darker, as the inside of most things is.
                const skin = mesh.faces[all[0]!]!.color;
                const inner: readonly [number, number, number, number] = p.color
                    ? [p.color[0]!, p.color[1]!, p.color[2]!, p.color[3] ?? 1]
                    : skin ? [skin[0] * 0.6, skin[1] * 0.6, skin[2] * 0.6, skin[3]] : [0.6, 0.6, 0.6, 1];
                for (let t = 0; t * 3 < out.triVerts.length; t++) {
                    const id = out.faceID![t]!;
                    const v = [out.triVerts[t * 3]! + base, out.triVerts[t * 3 + 1]! + base, out.triVerts[t * 3 + 2]! + base];
                    if (id >= INSIDE) made.push({ v, tag: p.tag ?? 'inside', color: inner, piece: count });
                    else {
                        const source = mesh.faces[id];
                        if (!source) throw new Error(`the cut lost track of a face (${id})`);
                        made.push({ ...source, v, piece: count });
                    }
                }
                let volume = 0;
                for (let t = 0; t * 3 < out.triVerts.length; t++) {
                    const [a, b, c] = [positions[out.triVerts[t * 3]! + base]!, positions[out.triVerts[t * 3 + 1]! + base]!, positions[out.triVerts[t * 3 + 2]! + base]!];
                    volume += dot(a, cross(b, c)) / 6;
                }
                volumes.push(Math.abs(volume));
                kept.push(k);
                count++;
            }
            if (cell !== whole) cell.delete();
        }
        const total = volumes.reduce((a, b) => a + b, 0);
        const slivers = new Set(kept.filter((_, i) => volumes[i]! < (total / Math.max(1, count)) * 0.04));
        if (slivers.size === 0 || count - slivers.size < 2) break;
        live = seeds.filter((_, k) => kept.includes(k) && !slivers.has(k));
        // Drawn again in their place while there are rounds to spare, so the count asked for is the count made; the
        // last round only takes them out.
        if (round < 2) while (live.length < p.pieces) live.push(draw());
      }
    } finally {
        whole.delete();
    }
    if (count < 2) throw new Error(`the solid came out as ${count} piece${count === 1 ? '' : 's'}: its points fell too close together; try another seed, or less focus`);
    const kept = mesh.faces.filter((_, i) => !allSet.has(i));
    const result = compact({ positions, faces: [...kept, ...made] });
    // What is drawn until it breaks: the solid as it came in.
    result.whole = { positions: mesh.positions, faces: mesh.faces };
    // Said only where it is not what was asked: a note is read as something to look at.
    if (count < p.pieces) result.notes = [`${count} pieces of the ${p.pieces} asked: the rest of the points fell where their share of the solid was nothing`];
    return result;
}

/**
 * The pieces of a fractured model as a prefab: one entity for each, where it lies in the model, drawing its own mesh
 * and with a body and a hull of that mesh, so that put down in a scene they are the model again and let go they fall
 * apart. A `Breakable` names it and spawns it where the whole stood.
 */
export function piecesPrefabOf(name: string, pieces: readonly { mesh: string; center: Vec3 }[], extra: { material?: string | null; texture?: string | null; normalMap?: string | null } = {}): Record<string, unknown> {
    const idOf = (i: number): string => `p${i + 1}`;
    return {
        version: PREFAB_FORMAT_VERSION, name: `${name} Pieces`, rootEntityId: 'root',
        entities: [
            { prefabEntityId: 'root', name: `${name} Pieces`, parent: null, children: pieces.map((_, i) => idOf(i)), visible: true, components: [{ type: 'Transform', data: {} }] },
            ...pieces.map((piece, i) => ({
                prefabEntityId: idOf(i), name: `Piece ${i + 1}`, parent: 'root', children: [], visible: true,
                components: [
                    { type: 'Transform', data: { position: { x: piece.center[0], y: piece.center[1], z: piece.center[2] } } },
                    // Both sides drawn: the inside of a broken thing is seen.
                    { type: 'MeshRenderer', data: { mesh: piece.mesh, ...(extra.normalMap ? { normalMap: extra.normalMap } : {}), ...(extra.texture ? { texture: extra.texture } : {}), ...(extra.material ? { material: extra.material } : {}), lit: true, opaque: true, cullBackfaces: true, enabled: true } },
                    { type: 'RigidBody3D', data: { bodyType: 2, enabled: true } },
                    { type: 'ConvexCollider3D', data: { mesh: piece.mesh, friction: 0.6, restitution: 0.05, enabled: true } },
                ],
            })),
        ],
    };
}