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.
TypeScript 2d-game-engine3d3d-game-engineandroidcppecsgame-editorgame-enginegamedeviostypescriptwebassemblywebglwebgpuwechat-minigame
// SPDX-License-Identifier: Apache-2.0
// SPDX-FileCopyrightText: Copyright (c) 2024-present ESEngine Team
/**
* @file modelOps.ts — what a model's steps do to its mesh.
*
* Each operation takes the mesh and answers a new one, and throws a sentence
* when it cannot: the caller is usually a model reading the reply, so "width
* 0.6 overruns an edge 1 long" gets the next attempt right where a clamped
* shape would have passed silently and looked wrong.
*/
import {
add, boundsOf, collectEdges, compact, cross, dot, edgeKey, faceCenter, faceNormal, length, normalize, scale,
selectEdges, selectFaces, sub,
type Edge, type EdgeSelector, type Face, type FaceSelector, type PolyMesh, type Vec3,
} from './polyMesh';
import { freezeFaceUv } from './modelUv';
const EPS = 1e-6;
const DEG = Math.PI / 180;
/** The most faces one model may hold: past this an `array` typo is a hang, not a model. */
export const MAX_FACES = 200000;
function guardSize(faces: number): void {
if (faces > MAX_FACES) throw new Error(`this would make ${faces} faces; a model holds at most ${MAX_FACES}`);
}
/** Selection that found nothing is a mistake worth stopping for: every step below it would be working on the wrong thing. */
function requireFaces(mesh: PolyMesh, selector: FaceSelector, name = 'faces'): number[] {
const hit = selectFaces(mesh, selector);
if (hit.length === 0) {
const tags = [...new Set(mesh.faces.map((f) => f.tag))].filter(Boolean);
throw new Error(`\`${name}\` ${JSON.stringify(selector)} matched no face. Tags here: ${tags.length ? tags.join(', ') : '(none)'}; ${mesh.faces.length} faces in all`);
}
return hit;
}
const usedVertices = (mesh: PolyMesh, faces: readonly number[]): Set<number> => {
const used = new Set<number>();
for (const f of faces) for (const v of mesh.faces[f]!.v) used.add(v);
return used;
};
// ---- Primitives: each appends a shell, leaving what is there alone ------------
export interface Placed { at?: Vec3; tag?: string; color?: readonly number[] }
/** A colour as a face holds it. Refused rather than clamped: past 1 is a sum gone wrong. */
function toColor(c: readonly number[]): NonNullable<Face['color']> {
if ((c.length !== 3 && c.length !== 4) || c.some((v) => v < 0 || v > 1)) {
throw new Error(`color ${JSON.stringify(c)} must be [r, g, b] or [r, g, b, a], each 0..1 (linear)`);
}
return [c[0]!, c[1]!, c[2]!, c[3] ?? 1];
}
export function append(mesh: PolyMesh, positions: readonly Vec3[], loops: readonly number[][], placed: Placed): PolyMesh {
guardSize(mesh.faces.length + loops.length);
const base = mesh.positions.length;
const at = placed.at ?? [0, 0, 0];
const color = placed.color ? toColor(placed.color) : null;
return {
positions: [...mesh.positions, ...positions.map((p) => add(p, at))],
faces: [...mesh.faces, ...loops.map((loop) => ({
v: loop.map((i) => i + base), tag: placed.tag ?? '', ...(color ? { color } : {}),
}))],
};
}
export function box(mesh: PolyMesh, p: Placed & { size: number | Vec3 }): PolyMesh {
const s: Vec3 = typeof p.size === 'number' ? [p.size, p.size, p.size] : p.size;
if (s.some((v) => v <= 0)) throw new Error(`size ${JSON.stringify(p.size)} must be positive on every axis`);
const [x, y, z] = [s[0] / 2, s[1] / 2, s[2] / 2];
const positions: Vec3[] = [
[-x, -y, z], [x, -y, z], [x, y, z], [-x, y, z],
[-x, -y, -z], [x, -y, -z], [x, y, -z], [-x, y, -z],
];
return append(mesh, positions, [
[0, 1, 2, 3], [5, 4, 7, 6], [1, 5, 6, 2], [4, 0, 3, 7], [3, 2, 6, 7], [4, 5, 1, 0],
], p);
}
export function plane(mesh: PolyMesh, p: Placed & { size: number | readonly [number, number] }): PolyMesh {
const s: readonly [number, number] = typeof p.size === 'number' ? [p.size, p.size] : p.size;
if (s.some((v) => v <= 0)) throw new Error(`size ${JSON.stringify(p.size)} must be positive`);
const [x, z] = [s[0] / 2, s[1] / 2];
return append(mesh, [[-x, 0, z], [x, 0, z], [x, 0, -z], [-x, 0, -z]], [[0, 1, 2, 3]], p);
}
/** A cylinder, or with `radiusTop` a tapered one. */
export function cylinder(mesh: PolyMesh, p: Placed & { radius: number; height: number; radiusTop?: number; sides?: number }): PolyMesh {
const sides = p.sides ?? 24;
const top = p.radiusTop ?? p.radius;
if (sides < 3 || !Number.isInteger(sides)) throw new Error(`sides ${sides} must be a whole number of at least 3`);
if (p.radius <= 0 || p.height <= 0 || top < 0) throw new Error('radius and height must be positive, radiusTop at least 0');
if (top === 0) return cone(mesh, { ...p, sides });
const h = p.height / 2;
const positions: Vec3[] = [];
for (let i = 0; i < sides; i++) {
const t = (i / sides) * Math.PI * 2;
const s = Math.sin(t), c = Math.cos(t);
positions.push([s * p.radius, -h, c * p.radius], [s * top, h, c * top]);
}
const loops: number[][] = [];
for (let i = 0; i < sides; i++) {
const j = (i + 1) % sides;
loops.push([i * 2, j * 2, j * 2 + 1, i * 2 + 1]);
}
loops.push(Array.from({ length: sides }, (_, i) => i * 2 + 1));
loops.push(Array.from({ length: sides }, (_, i) => (sides - 1 - i) * 2));
return append(mesh, positions, loops, p);
}
export function cone(mesh: PolyMesh, p: Placed & { radius: number; height: number; sides?: number }): PolyMesh {
const sides = p.sides ?? 24;
if (sides < 3 || !Number.isInteger(sides)) throw new Error(`sides ${sides} must be a whole number of at least 3`);
if (p.radius <= 0 || p.height <= 0) throw new Error('radius and height must be positive');
const h = p.height / 2;
const positions: Vec3[] = [[0, h, 0]];
for (let i = 0; i < sides; i++) {
const t = (i / sides) * Math.PI * 2;
positions.push([Math.sin(t) * p.radius, -h, Math.cos(t) * p.radius]);
}
const loops: number[][] = [];
for (let i = 0; i < sides; i++) loops.push([1 + i, 1 + (i + 1) % sides, 0]);
loops.push(Array.from({ length: sides }, (_, i) => 1 + (sides - 1 - i)));
return append(mesh, positions, loops, p);
}
export function sphere(mesh: PolyMesh, p: Placed & { radius: number; rings?: number; sides?: number }): PolyMesh {
const rings = p.rings ?? 12, sides = p.sides ?? 24;
if (rings < 2 || sides < 3 || !Number.isInteger(rings) || !Number.isInteger(sides)) {
throw new Error(`rings ${rings} must be at least 2 and sides ${sides} at least 3, both whole`);
}
if (p.radius <= 0) throw new Error('radius must be positive');
const positions: Vec3[] = [[0, p.radius, 0], [0, -p.radius, 0]];
for (let r = 1; r < rings; r++) {
const phi = (r / rings) * Math.PI;
for (let i = 0; i < sides; i++) {
const t = (i / sides) * Math.PI * 2;
positions.push([Math.sin(phi) * Math.sin(t) * p.radius, Math.cos(phi) * p.radius, Math.sin(phi) * Math.cos(t) * p.radius]);
}
}
const at = (r: number, i: number): number => 2 + (r - 1) * sides + (i % sides);
const loops: number[][] = [];
for (let i = 0; i < sides; i++) {
loops.push([0, at(1, i), at(1, i + 1)]);
loops.push([1, at(rings - 1, i + 1), at(rings - 1, i)]);
for (let r = 1; r < rings - 1; r++) loops.push([at(r, i), at(r + 1, i), at(r + 1, i + 1), at(r, i + 1)]);
}
return append(mesh, positions, loops, p);
}
/** A floor plan `points` ([x, z], either winding) stood up `height`: an L-shaped room, a gable end laid flat, a star. */
export function prism(mesh: PolyMesh, p: Placed & { points: readonly (readonly [number, number])[]; height: number }): PolyMesh {
if (p.points.length < 3) throw new Error(`a prism needs at least 3 points, not ${p.points.length}`);
if (p.height <= 0) throw new Error('height must be positive');
// Counter-clockwise seen from above, whichever way the caller walked it; in XZ, that is a negative shoelace.
let area = 0;
p.points.forEach((a, i) => {
const b = p.points[(i + 1) % p.points.length]!;
area += a[0] * b[1] - b[0] * a[1];
});
if (Math.abs(area) < EPS) throw new Error('the points enclose no area');
const pts = area > 0 ? [...p.points].reverse() : p.points;
const n = pts.length, h = p.height / 2;
const positions: Vec3[] = [];
for (const q of pts) positions.push([q[0], -h, q[1]], [q[0], h, q[1]]);
const loops: number[][] = [];
for (let i = 0; i < n; i++) {
const j = (i + 1) % n;
loops.push([i * 2, j * 2, j * 2 + 1, i * 2 + 1]);
}
loops.push(Array.from({ length: n }, (_, i) => i * 2 + 1));
loops.push(Array.from({ length: n }, (_, i) => (n - 1 - i) * 2));
return append(mesh, positions, loops, p);
}
// ---- Moving and copying --------------------------------------------------------
function rotateVector(v: Vec3, degrees: Vec3): Vec3 {
const [cx, sx] = [Math.cos(degrees[0] * DEG), Math.sin(degrees[0] * DEG)];
const [cy, sy] = [Math.cos(degrees[1] * DEG), Math.sin(degrees[1] * DEG)];
const [cz, sz] = [Math.cos(degrees[2] * DEG), Math.sin(degrees[2] * DEG)];
// X, then Y, then Z.
const a: Vec3 = [v[0], cx * v[1] - sx * v[2], sx * v[1] + cx * v[2]];
const b: Vec3 = [cy * a[0] + sy * a[2], a[1], -sy * a[0] + cy * a[2]];
return [cz * b[0] - sz * b[1], sz * b[0] + cz * b[1], b[2]];
}
function pivotOf(mesh: PolyMesh, vertices: Iterable<number>, pivot: 'center' | 'base' | Vec3 | undefined): Vec3 {
if (Array.isArray(pivot)) return pivot as Vec3;
const { min, max } = boundsOf(mesh, vertices);
const center: Vec3 = [(min[0] + max[0]) / 2, (min[1] + max[1]) / 2, (min[2] + max[2]) / 2];
return pivot === 'base' ? [center[0], min[1], center[2]] : center;
}
/** Moves the vertices of the chosen faces: a whole shell moves, a top face scaled in makes a roof of the box under it. */
export function transform(mesh: PolyMesh, p: {
faces?: FaceSelector; translate?: Vec3; rotate?: Vec3; scale?: number | Vec3; pivot?: 'center' | 'base' | Vec3;
}): PolyMesh {
if (!p.translate && !p.rotate && p.scale === undefined) throw new Error('give at least one of translate, rotate, scale');
const s: Vec3 = typeof p.scale === 'number' ? [p.scale, p.scale, p.scale] : p.scale ?? [1, 1, 1];
if (s.some((v) => v <= 0)) throw new Error(`scale ${JSON.stringify(p.scale)} must be positive; a negative one turns faces inside out, which is what \`mirror\` is for`);
const vertices = usedVertices(mesh, requireFaces(mesh, p.faces ?? 'all'));
const pivot = pivotOf(mesh, vertices, p.pivot);
const positions = mesh.positions.slice();
for (const i of vertices) {
let q = sub(positions[i]!, pivot);
q = [q[0] * s[0], q[1] * s[1], q[2] * s[2]];
if (p.rotate) q = rotateVector(q, p.rotate);
positions[i] = add(add(q, pivot), p.translate ?? [0, 0, 0]);
}
const faces = mesh.faces.map((f) => f.uv && f.v.some((v) => vertices.has(v)) ? freezeFaceUv(mesh, f) : f);
return { ...mesh, positions, faces };
}
/** A copy of the chosen faces with vertices of their own, each position put through @p move. */
function cloneFaces(mesh: PolyMesh, faces: readonly number[], move: (p: Vec3) => Vec3, flip = false): { positions: Vec3[]; faces: Face[] } {
const remap = new Map<number, number>();
const positions: Vec3[] = [];
const base = mesh.positions.length;
const out = faces.map((f) => {
const face = freezeFaceUv(mesh, mesh.faces[f]!);
const v = face.v.map((i) => {
let to = remap.get(i);
if (to === undefined) {
to = base + positions.length;
remap.set(i, to);
positions.push(move(mesh.positions[i]!));
}
return to;
});
return { ...face, v: flip ? v.reverse() : v,
...(flip && face.cornerUvs ? { cornerUvs: [...face.cornerUvs].reverse() } : {}) };
});
return { positions, faces: out };
}
/** `count` copies in all, the original included: a row of windows, or with `rotate` a ring of columns. */
export function array(mesh: PolyMesh, p: {
faces?: FaceSelector; count: number; offset?: Vec3; rotate?: Vec3; pivot?: 'center' | 'base' | Vec3; tag?: string;
}): PolyMesh {
if (!Number.isInteger(p.count) || p.count < 2) throw new Error(`count ${p.count} must be a whole number of at least 2 (it includes the original)`);
if (!p.offset && !p.rotate) throw new Error('give offset, rotate, or both');
const hit = requireFaces(mesh, p.faces ?? 'all');
guardSize(mesh.faces.length + hit.length * (p.count - 1));
const vertices = usedVertices(mesh, hit);
const pivot = p.rotate ? pivotOf(mesh, vertices, p.pivot) : [0, 0, 0] as Vec3;
let out = mesh;
for (let n = 1; n < p.count; n++) {
const step = scale(p.offset ?? [0, 0, 0], n);
const angle: Vec3 | null = p.rotate ? [p.rotate[0] * n, p.rotate[1] * n, p.rotate[2] * n] : null;
const copy = cloneFaces({ ...mesh, positions: out.positions }, hit, (q) => {
const turned = angle ? add(rotateVector(sub(q, pivot), angle), pivot) : q;
return add(turned, step);
});
out = {
positions: [...out.positions, ...copy.positions],
faces: [...out.faces, ...copy.faces.map((f) => (p.tag ? { ...f, tag: p.tag } : f))],
};
}
return out;
}
/** Mirror across the plane `axis = at`, adding the reflection (or with `keep: false`, replacing the original with it). */
export function mirror(mesh: PolyMesh, p: { faces?: FaceSelector; axis: 'x' | 'y' | 'z'; at?: number; keep?: boolean; tag?: string }): PolyMesh {
const k = { x: 0, y: 1, z: 2 }[p.axis];
const at = p.at ?? 0;
const hit = requireFaces(mesh, p.faces ?? 'all');
guardSize(mesh.faces.length + hit.length);
const copy = cloneFaces(mesh, hit, (q) => {
const r = [q[0], q[1], q[2]] as [number, number, number];
r[k] = 2 * at - r[k];
return r;
}, true);
const gone = p.keep === false ? new Set(hit) : null;
return compact({
positions: [...mesh.positions, ...copy.positions],
faces: [...mesh.faces.filter((_, i) => !gone?.has(i)), ...copy.faces.map((f) => (p.tag ? { ...f, tag: p.tag } : f))],
});
}
// ---- Changing the surface -------------------------------------------------------
/** Each chosen face (`individual`), or each connected run of them, pushed out with walls joining it to where it was. A negative distance recesses. */
export function extrude(mesh: PolyMesh, p: {
faces: FaceSelector; distance: number; direction?: Vec3; individual?: boolean; tag?: string; sideTag?: string;
}): PolyMesh {
if (p.distance === 0) throw new Error('distance must not be 0');
const hit = requireFaces(mesh, p.faces);
const groups = p.individual ? hit.map((f) => [f]) : [hit];
const positions = mesh.positions.slice();
const faces = mesh.faces.slice();
const direction = p.direction ? normalize(p.direction) : null;
if (p.direction && length(direction!) === 0) throw new Error('direction must not be zero');
for (const group of groups) {
const selected = new Set(group);
const normals = new Map<number, Vec3[]>();
for (const f of group) {
const n = faceNormal(mesh, mesh.faces[f]!);
for (const v of mesh.faces[f]!.v) {
const at = normals.get(v) ?? [];
if (!at.some((m) => dot(m, n) > 1 - 1e-9)) at.push(n);
normals.set(v, at);
}
}
const moved = new Map<number, number>();
for (const [v, ns] of normals) {
let offset: Vec3;
if (direction) offset = scale(direction, p.distance);
else {
const mean = normalize(ns.reduce<Vec3>((a, b) => add(a, b), [0, 0, 0]));
// Mitred: the shifted faces stay `distance` from where they were at a corner too.
const lean = Math.max(dot(mean, ns[0]!), 0.25);
offset = scale(mean, p.distance / lean);
}
moved.set(v, positions.length);
positions.push(add(mesh.positions[v]!, offset));
}
const used = new Set<string>();
for (const f of selected) {
for (let i = 0; i < mesh.faces[f]!.v.length; i++) {
used.add(`${mesh.faces[f]!.v[i]}>${mesh.faces[f]!.v[(i + 1) % mesh.faces[f]!.v.length]}`);
}
}
for (const f of selected) {
const face = mesh.faces[f]!;
for (let i = 0; i < face.v.length; i++) {
const a = face.v[i]!, b = face.v[(i + 1) % face.v.length]!;
if (used.has(`${b}>${a}`)) continue; // its other side moved with it: no wall here
faces.push({ ...face, v: [a, b, moved.get(b)!, moved.get(a)!], tag: p.sideTag ?? face.tag });
}
faces[f] = { ...face, v: face.v.map((v) => moved.get(v)!), tag: p.tag ?? face.tag };
}
}
guardSize(faces.length);
return compact({ positions, faces });
}
/** The point in the face's plane `amountNext` inside the edge leaving along @p toNext and `amountPrev` inside the one along @p toPrev. */
function offsetCorner(corner: Vec3, normal: Vec3, toNext: Vec3, toPrev: Vec3, amountNext: number, amountPrev: number): Vec3 {
// Inward in the plane, for a counter-clockwise loop.
const inNext = normalize(cross(normal, toNext));
const inPrev = normalize(cross(toPrev, normal));
const denom = 1 - dot(inNext, inPrev) ** 2;
if (denom < 1e-9) return add(corner, scale(inNext, amountNext));
const d = dot(inNext, inPrev);
const a = (amountNext - amountPrev * d) / denom;
const b = (amountPrev - amountNext * d) / denom;
return add(add(corner, scale(inNext, a)), scale(inPrev, b));
}
/** A smaller copy of each chosen face inside it, tagged `tag`, joined to the old outline by quads tagged as the face was. */
export function inset(mesh: PolyMesh, p: { faces: FaceSelector; amount: number; tag?: string }): PolyMesh {
if (p.amount <= 0) throw new Error(`amount ${p.amount} must be positive`);
const hit = requireFaces(mesh, p.faces);
const positions = mesh.positions.slice();
const faces = mesh.faces.slice();
for (const f of hit) {
const face = mesh.faces[f]!;
const n = faceNormal(mesh, face);
const count = face.v.length;
const ring = face.v.map((v, i) => {
const at = mesh.positions[v]!;
const next = mesh.positions[face.v[(i + 1) % count]!]!;
const prev = mesh.positions[face.v[(i + count - 1) % count]!]!;
return offsetCorner(at, n, normalize(sub(next, at)), normalize(sub(prev, at)), p.amount, p.amount);
});
// Each edge of the new outline must still run the way the old one did; past the face's own width it runs backwards.
for (let i = 0; i < count; i++) {
const was = sub(mesh.positions[face.v[(i + 1) % count]!]!, mesh.positions[face.v[i]!]!);
const now = sub(ring[(i + 1) % count]!, ring[i]!);
if (dot(was, now) <= 0) {
throw new Error(`amount ${p.amount} is more than the face at ${JSON.stringify(roundVec(faceCenter(mesh, face)))} can hold (its edge ${roundNum(length(was))} long collapses)`);
}
}
const base = positions.length;
positions.push(...ring);
for (let i = 0; i < count; i++) {
const j = (i + 1) % count;
faces.push({ ...face, v: [face.v[i]!, face.v[j]!, base + j, base + i] });
}
faces[f] = { ...face, v: ring.map((_, i) => base + i), tag: p.tag ?? face.tag };
}
guardSize(faces.length);
return { positions, faces };
}
const roundNum = (v: number): number => Math.round(v * 1000) / 1000;
const roundVec = (v: Vec3): number[] => v.map(roundNum);
/**
* Cuts faces across planes `axis = at`, so a wall gains the seams a window is placed
* between. Faces outside `faces` are not cut, but take the new vertex on an edge they
* share with one that was, so no crack opens along it.
*/
export function slice(mesh: PolyMesh, p: { faces?: FaceSelector; axis: 'x' | 'y' | 'z'; at: number | readonly number[] }): PolyMesh {
const k = { x: 0, y: 1, z: 2 }[p.axis];
const planes = typeof p.at === 'number' ? [p.at] : p.at;
if (planes.length === 0) throw new Error('`at` names no plane');
let out = mesh;
for (const at of planes) {
let cut = false;
const targets = new Set(requireFaces(out, p.faces ?? 'all'));
const positions = out.positions.slice();
const crossing = new Map<string, number>();
const side = (v: number): number => {
const d = positions[v]![k]! - at;
return Math.abs(d) < EPS ? 0 : d;
};
for (const f of targets) {
const face = out.faces[f]!;
for (let i = 0; i < face.v.length; i++) {
const a = face.v[i]!, b = face.v[(i + 1) % face.v.length]!;
const da = side(a), db = side(b);
if (da * db >= 0) continue;
const key = edgeKey(a, b);
if (crossing.has(key)) continue;
const t = da / (da - db);
crossing.set(key, positions.length);
positions.push(add(positions[a]!, scale(sub(positions[b]!, positions[a]!), t)));
}
}
const faces: Face[] = [];
out.faces.forEach((face, f) => {
const loop: number[] = [];
for (let i = 0; i < face.v.length; i++) {
const a = face.v[i]!, b = face.v[(i + 1) % face.v.length]!;
loop.push(a);
const mid = crossing.get(edgeKey(a, b));
if (mid !== undefined) loop.push(mid);
}
if (!targets.has(f)) { faces.push({ ...face, v: loop }); return; }
const on: number[] = [];
loop.forEach((v, i) => { if (Math.abs(positions[v]![k]! - at) < EPS) on.push(i); });
const hasBothSides = loop.some((v) => positions[v]![k]! - at > EPS) && loop.some((v) => positions[v]![k]! - at < -EPS);
if (!hasBothSides || on.length < 2) { faces.push({ ...face, v: loop }); return; }
if (on.length !== 2) {
throw new Error(`plane ${p.axis} = ${at} crosses the concave face at ${JSON.stringify(roundVec(faceCenter(out, face)))} more than once; slice it somewhere it crosses once, or build it from convex parts`);
}
const [i, j] = on as [number, number];
faces.push({ ...face, v: loop.slice(i, j + 1) });
faces.push({ ...face, v: [...loop.slice(j), ...loop.slice(0, i + 1)] });
cut = true;
});
if (!cut) throw new Error(`no chosen face crosses ${p.axis} = ${at}; the mesh spans ${JSON.stringify(rangeOn(out, k))} on that axis`);
guardSize(faces.length);
out = { positions, faces };
}
return out;
}
const rangeOn = (mesh: PolyMesh, k: number): number[] => {
const { min, max } = boundsOf(mesh);
return [roundNum(min[k]!), roundNum(max[k]!)];
};
export function deleteFaces(mesh: PolyMesh, p: { faces: FaceSelector }): PolyMesh {
const gone = new Set(requireFaces(mesh, p.faces));
return compact({ positions: mesh.positions, faces: mesh.faces.filter((_, i) => !gone.has(i)) });
}
/** Recolours faces: linear RGB or RGBA in 0..1, multiplied into whatever material draws the mesh. */
export function paint(mesh: PolyMesh, p: { faces: FaceSelector; color?: readonly number[]; roughness?: number; metallic?: number }): PolyMesh {
if (p.color === undefined && p.roughness === undefined && p.metallic === undefined) throw new Error('give at least one of color, roughness, metallic');
for (const [name, v] of [['roughness', p.roughness], ['metallic', p.metallic]] as const) {
if (v !== undefined && !(v >= 0 && v <= 1)) throw new Error(`${name} ${v} must be 0..1`);
}
const set = {
...(p.color !== undefined ? { color: toColor(p.color) } : {}),
...(p.roughness !== undefined ? { roughness: p.roughness } : {}),
...(p.metallic !== undefined ? { metallic: p.metallic } : {}),
};
const hit = new Set(requireFaces(mesh, p.faces));
return { ...mesh, faces: mesh.faces.map((f, i) => (hit.has(i) ? { ...f, ...set } : f)) };
}
/** Names faces, so later steps can ask for them by what they are. */
export function tagFaces(mesh: PolyMesh, p: { faces: FaceSelector; tag: string }): PolyMesh {
const hit = new Set(requireFaces(mesh, p.faces));
return { ...mesh, faces: mesh.faces.map((f, i) => (hit.has(i) ? { ...f, tag: p.tag } : f)) };
}
/**
* Merges vertices closer than `distance`, then removes what that leaves meaningless:
* edges of no length, faces of under three corners, and pairs of faces lying back to
* back on each other, which is the wall a mirrored half leaves down its middle.
*/
export function weld(mesh: PolyMesh, p: { distance?: number }): PolyMesh {
const distance = p.distance ?? 1e-4;
if (distance <= 0) throw new Error(`distance ${distance} must be positive`);
const cell = new Map<string, number[]>();
const parent = mesh.positions.map((_, i) => i);
const keyOf = (q: Vec3): number[] => q.map((v) => Math.floor(v / distance));
mesh.positions.forEach((q, i) => {
const [x, y, z] = keyOf(q) as [number, number, number];
for (let dx = -1; dx <= 1 && parent[i] === i; dx++) {
for (let dy = -1; dy <= 1 && parent[i] === i; dy++) {
for (let dz = -1; dz <= 1 && parent[i] === i; dz++) {
for (const j of cell.get(`${x + dx},${y + dy},${z + dz}`) ?? []) {
if (length(sub(q, mesh.positions[j]!)) <= distance) { parent[i] = j; break; }
}
}
}
}
if (parent[i] === i) {
const key = `${x},${y},${z}`;
const at = cell.get(key);
if (at) at.push(i); else cell.set(key, [i]);
}
});
const faces: Face[] = [];
for (const face of mesh.faces) {
const v: number[] = [];
for (const i of face.v) {
const to = parent[i]!;
if (v[v.length - 1] !== to) v.push(to);
}
while (v.length > 1 && v[0] === v[v.length - 1]) v.pop();
if (v.length >= 3 && new Set(v).size === v.length) faces.push({ ...face, v });
}
// Same corners, opposite way round: neither side can ever be seen.
const signature = (v: readonly number[]): string => [...v].sort((a, b) => a - b).join(',');
const bySet = new Map<string, number[]>();
faces.forEach((f, i) => {
const key = signature(f.v);
const at = bySet.get(key);
if (at) at.push(i); else bySet.set(key, [i]);
});
const hidden = new Set<number>();
for (const group of bySet.values()) {
if (group.length < 2) continue;
for (let a = 0; a < group.length; a++) {
for (let b = a + 1; b < group.length; b++) {
if (hidden.has(group[a]!) || hidden.has(group[b]!)) continue;
if (dot(faceNormal(mesh, faces[group[a]!]!), faceNormal(mesh, faces[group[b]!]!)) < -0.99) {
hidden.add(group[a]!);
hidden.add(group[b]!);
}
}
}
}
return compact({ positions: mesh.positions, faces: faces.filter((_, i) => !hidden.has(i)) });
}
// ---- Bevel ----------------------------------------------------------------------
/**
* Chamfers the chosen edges flat, `width` back on each side, mitring where they meet.
* A corner between two chosen edges moves inside its face; one beside a single chosen
* edge slides along the other. Three or more new vertices round a vertex close with a
* cap; two are the edge the strips share, which is the mitre.
*/
export function bevel(mesh: PolyMesh, p: { edges: EdgeSelector | 'all'; width: number; round?: number; tag?: string }): PolyMesh {
if (p.width <= 0) throw new Error(`width ${p.width} must be positive`);
const passes = p.round ?? 0;
if (!Number.isInteger(passes) || passes < 0 || passes > 3) throw new Error(`round ${passes} must be a whole number, 0..3`);
const chosen = selectEdges(mesh, p.edges === 'all' ? {} : p.edges);
if (chosen.length === 0) throw new Error(`\`edges\` ${JSON.stringify(p.edges)} matched no edge between two faces. Open rims cannot be bevelled, and edges closer to flat than \`sharp\` (default 10 degrees) are left out`);
// Rounded by cutting corners again: each pass takes a quarter off both sides of every corner the last one left, which closes on a curve.
let out = chamferEdges(mesh, chosen, p.width, p.tag);
let width = p.width * Math.SQRT2;
const firstNew = mesh.faces.length;
for (let pass = 0; pass < passes; pass++) {
width /= 4;
const corners = cornerEdges(out, firstNew);
const before = out.faces.length;
out = chamferEdges(out, corners, width, p.tag, true);
// Faces keep their order through a pass and its new ones go on the end, so the bevel's own run from the same place.
void before;
width *= 2;
}
return compact(out);
}
/** The edges where a bevel's own faces (those from @p firstNew on) meet anything at an angle: what the next rounding pass cuts. */
function cornerEdges(mesh: PolyMesh, firstNew: number): Edge[] {
const flat = Math.cos((2 * Math.PI) / 180);
return [...collectEdges(mesh).values()].filter((e) => e.faces.length === 2 && e.faces.some((f) => f >= firstNew)
&& dot(faceNormal(mesh, mesh.faces[e.faces[0]!]!), faceNormal(mesh, mesh.faces[e.faces[1]!]!)) < flat);
}
/** How far along an edge a rounding pass may cut: both ends must leave something of it, whatever size of sliver a corner left. */
const ROUND_LIMIT = 0.45;
/** @p fit keeps every cut on its edge instead of refusing one that overruns: a user's width is checked on the first pass, and later ones are the kernel's own. */
function chamferEdges(mesh: PolyMesh, chosen: readonly Edge[], width: number, tag?: string, fit = false): PolyMesh {
const p = { tag };
const edges = collectEdges(mesh);
for (const edge of edges.values()) {
if (edge.faces.length > 2) throw new Error(`an edge at ${JSON.stringify(roundVec(mesh.positions[edge.a]!))} is shared by ${edge.faces.length} faces; weld or separate them first`);
}
const isChosen = new Set(chosen.map((e) => edgeKey(e.a, e.b)));
const positions = mesh.positions.slice();
// How far each end of an edge is eaten, to refuse a bevel wider than the edge. The most any face at that end asks: two faces share it.
const eaten = new Map<string, number>();
const eat = (v: number, far: number, t: number): void => {
const key = `${v}>${far}`;
eaten.set(key, Math.max(eaten.get(key) ?? 0, t));
};
// A corner is (face, position in loop). What it becomes is a run of new vertices.
const corners = new Map<string, number[]>();
const cornerKey = (f: number, i: number): string => `${f}/${i}`;
/** Slid vertices, by (vertex, far end of the edge slid along): both faces beside that edge land on one. */
const slides = new Map<string, number>();
const touched = new Set<number>();
for (const e of chosen) { touched.add(e.a); touched.add(e.b); }
const slideOn = (v: number, far: number, along: Vec3, across: Vec3): number => {
const key = `${v}>${far}`;
const known = slides.get(key);
if (known !== undefined) return known;
const lean = dot(along, across);
// An edge running away from the chamfer, or nearly along it, has no distance that is `width` across: fall back on `width`.
const wanted = lean > 0.05 ? width / lean : width;
const t = fit ? Math.min(wanted, length(sub(mesh.positions[far]!, mesh.positions[v]!)) * ROUND_LIMIT) : wanted;
eat(v, far, t);
const at = positions.length;
positions.push(add(mesh.positions[v]!, scale(along, t)));
slides.set(key, at);
return at;
};
mesh.faces.forEach((face, f) => {
const n = faceNormal(mesh, face);
const count = face.v.length;
face.v.forEach((v, i) => {
if (!touched.has(v)) return;
const next = face.v[(i + 1) % count]!, prev = face.v[(i + count - 1) % count]!;
const nextChosen = isChosen.has(edgeKey(v, next)), prevChosen = isChosen.has(edgeKey(v, prev));
const at = mesh.positions[v]!;
const toNext = normalize(sub(mesh.positions[next]!, at)), toPrev = normalize(sub(mesh.positions[prev]!, at));
const inNext = normalize(cross(n, toNext)), inPrev = normalize(cross(toPrev, n));
let run: number[];
if (nextChosen && prevChosen) {
let q = offsetCorner(at, n, toNext, toPrev, width, width);
if (fit) {
// Shrunk toward the corner until it is within both edges' share.
const room = ROUND_LIMIT * Math.min(length(sub(mesh.positions[next]!, at)), length(sub(mesh.positions[prev]!, at)));
const along = Math.max(dot(sub(q, at), toNext), dot(sub(q, at), toPrev), length(sub(q, at)));
if (along > room) q = add(at, scale(sub(q, at), room / along));
}
eat(v, next, dot(sub(q, at), toNext));
eat(v, prev, dot(sub(q, at), toPrev));
run = [positions.length];
positions.push(q);
} else if (nextChosen) {
run = [slideOn(v, prev, toPrev, inNext)];
} else if (prevChosen) {
run = [slideOn(v, next, toNext, inPrev)];
} else {
run = []; // filled in below, once every chosen-side slide along its edges exists
}
corners.set(cornerKey(f, i), run);
});
});
// Refused before any face is built: an overrun edge is a bow-tie, and it would look like a rendering bug.
if (!fit) for (const [key, t] of eaten) {
const [a, b] = key.split('>').map(Number) as [number, number];
const needs = t + (eaten.get(`${b}>${a}`) ?? 0);
const long = length(sub(mesh.positions[a]!, mesh.positions[b]!));
if (needs >= long - 1e-9) {
throw new Error(`width ${width} overruns the edge ${roundNum(long)} long at ${JSON.stringify(roundVec(mesh.positions[a]!))}; it would need ${roundNum(needs)}`);
}
}
// A corner with no chosen edge beside it, at a vertex that has one elsewhere: take the slides its two edges got, or stay put on an edge that got none.
const stay = new Map<number, number>();
const stayAt = (v: number): number => {
let at = stay.get(v);
if (at === undefined) {
at = positions.length;
positions.push(mesh.positions[v]!);
stay.set(v, at);
}
return at;
};
mesh.faces.forEach((face, f) => {
const count = face.v.length;
face.v.forEach((v, i) => {
if (!touched.has(v)) return;
const key = cornerKey(f, i);
if (corners.get(key)!.length > 0) return;
const next = face.v[(i + 1) % count]!, prev = face.v[(i + count - 1) % count]!;
const a = slides.get(`${v}>${prev}`) ?? stayAt(v);
const b = slides.get(`${v}>${next}`) ?? stayAt(v);
corners.set(key, a === b ? [a] : [a, b]);
});
});
const faces: Face[] = mesh.faces.map((face, f) => ({
...face,
v: face.v.flatMap((v, i) => corners.get(cornerKey(f, i)) ?? [v]),
}));
const tagFor = (face: Face): Pick<Face, 'tag' | 'color'> => ({
tag: p.tag ?? face.tag, ...(face.color ? { color: face.color } : {}),
});
// The strip along each chosen edge, joining what the two faces now leave open beside it. A face runs
// last(corner) -> first(next corner) where the edge was; the strip runs that the other way, so all of it agrees on outside.
const openSide = (face: number, from: number, to: number): { a: number; b: number } | null => {
const v = mesh.faces[face]!.v;
for (let i = 0; i < v.length; i++) {
const j = (i + 1) % v.length;
if (v[i] !== from || v[j] !== to) continue;
const runA = corners.get(cornerKey(face, i))!, runB = corners.get(cornerKey(face, j))!;
return { a: runA[runA.length - 1]!, b: runB[0]! };
}
return null;
};
for (const edge of chosen) {
const [f, g] = edge.faces as [number, number];
const forward = openSide(f, edge.a, edge.b);
const first = forward ?? openSide(f, edge.b, edge.a)!;
const second = forward ? openSide(g, edge.b, edge.a) : openSide(g, edge.a, edge.b);
if (!second) {
throw new Error(`the faces either side of the edge at ${JSON.stringify(roundVec(mesh.positions[edge.a]!))} are wound opposite ways, so one is inside out`);
}
const loop = [first.b, first.a, second.b, second.a].filter((q, i, all) => q !== all[(i + 1) % all.length]);
if (loop.length >= 3) faces.push({ v: loop, ...tagFor(mesh.faces[f]!) });
}
// Round each vertex the strips leave a hole, which three or more new vertices make a face of. The walk
// goes clockwise seen from outside, and a run is in its face's order, which is the same way: the cap is that loop reversed.
for (const v of touched) {
const around = faceFan(mesh, v);
if (!around) continue; // on an open rim there is no hole to close
const loop: number[] = [];
for (const { face, index } of around) {
for (const q of corners.get(cornerKey(face, index))!) {
if (loop[loop.length - 1] !== q) loop.push(q);
}
}
while (loop.length > 1 && loop[0] === loop[loop.length - 1]) loop.pop();
if (loop.length >= 3) faces.push({ v: loop.reverse(), ...tagFor(mesh.faces[around[0]!.face]!) });
}
guardSize(faces.length);
return compact({ positions, faces });
}
/** The faces round a vertex in order, or null when they do not close round it. */
function faceFan(mesh: PolyMesh, v: number): { face: number; index: number }[] | null {
const byIncoming = new Map<number, { face: number; index: number }>();
let total = 0;
mesh.faces.forEach((face, f) => {
const i = face.v.indexOf(v);
if (i < 0) return;
// A corner's face arrives along prev -> v, and leaves along v -> next. The face round the corner uses next -> v.
byIncoming.set(face.v[(i + face.v.length - 1) % face.v.length]!, { face: f, index: i });
total++;
});
if (total === 0) return null;
const out: { face: number; index: number }[] = [];
let at = byIncoming.values().next().value!;
for (let n = 0; n < total; n++) {
out.push(at);
const face = mesh.faces[at.face]!;
const next = face.v[(at.index + 1) % face.v.length]!;
const round = byIncoming.get(next);
if (!round) return null;
at = round;
}
return at === out[0] ? out : null;
}