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 organic.ts — a body from its parts: the `organic` step.
*
* Living shapes are what steps on polygons cannot say: a shoulder has no edges
* to select. So this describes volumes instead, the way a person sketching a
* creature does, as a torso, limbs running from a joint to a joint, a skull. Each
* part melts into those before it by `blend`, or carves into them, and the skin
* is found afterwards. Nothing needs its topology thought about, and moving a
* shoulder is one number, which is what makes this something an agent can steer.
*
* The volume is a signed distance field; the skin is Naive Surface Nets over a
* grid of it, with each vertex then settled onto the true surface. The result
* is one more shell of quads, so every later step can act on it. Its faces are
* marked smooth, and each carries the tag and colour of the part nearest it.
*/
import { refine } from './displace';
import { add, type Face, type PolyMesh, type Vec3 } from './polyMesh';
import { curveThrough } from './surfaces';
import { hash3 } from './hash';
export type OrganicShape = 'sphere' | 'ellipsoid' | 'box' | 'torus' | 'chain' | 'outline' | 'limb';
/** One cross-section of a limb: an oval standing square to the line it is on. */
export interface LimbSection {
at: Vec3;
/** Half its width, along `side`. */
across: number;
/** Half its depth, the way it faces; `back` differs where a body does, a calf or a chest. */
front: number;
back?: number;
}
export interface OrganicNoise {
/** How far the surface moves, in and out. */
amplitude: number;
/** Size of the bumps, in world units. */
scale: number;
octaves?: number;
seed?: number;
}
export interface OrganicPart {
shape: OrganicShape;
tag?: string;
at?: Vec3;
/** Degrees, X then Y then Z: for ellipsoid, box and torus. */
rotate?: Vec3;
/** sphere; torus's ring. */
radius?: number;
/** ellipsoid's three half-axes. */
radii?: Vec3;
/** box's whole size. */
size?: Vec3;
/** box's corners. */
rounding?: number;
/** torus's thickness. */
tube?: number;
/** chain: a limb, a tail, a branch, as [x, y, z, radius] along its length. outline: a closed drawing, as [x, y] round it. */
points?: readonly (readonly number[])[];
/** outline: half how thick it stands, along z. */
depth?: number;
/** outline: how far in from its edge it takes to come up to `depth`. Default the whole way to its middle, a dome with no flat on it; small, a slab with soft edges. */
round?: number;
/** outline and limb: this many segments between points, passing through each. A point given twice keeps a corner there. */
curve?: number;
/** limb: its cross-sections, in order along it. */
sections?: readonly LimbSection[];
/** limb: the direction that is across it, kept square to the line. Default +x. */
side?: Vec3;
/** limb: 2 is an oval; higher squares it, as a chest is squarer than a wrist. Default 2. */
power?: number;
/** How far this melts into what is before it; 0 is a hard crease. Defaults to the step's. */
blend?: number;
/** Carves this volume out of what is before it: an eye socket, a mouth. */
subtract?: boolean;
/** Also exists reflected across this axis's zero plane: the other arm. */
mirror?: 'x' | 'y' | 'z';
color?: readonly number[];
noise?: OrganicNoise;
}
export interface OrganicParams {
parts: readonly OrganicPart[];
/** Grid cells along the longest side. More resolves more detail, at the cost of triangles. */
resolution?: number;
/** What `resolution` may go to, where a caller knows the cost: a whole body. */
maxResolution?: number;
/** Around these places the skin is split finer and settled back on the true surface: a face, a hand. No seam, as it stays one skin. */
fine?: readonly { at: Vec3; radius: number; longest: number; mirror?: 'x' }[];
blend?: number;
noise?: OrganicNoise;
at?: Vec3;
tag?: string;
color?: readonly number[];
}
export const ORGANIC_DEFAULT_RESOLUTION = 64;
export const ORGANIC_MAX_RESOLUTION = 160;
const DEG = Math.PI / 180;
type Color = readonly [number, number, number, number];
type Eval = (x: number, y: number, z: number) => number;
// ---- Noise: value noise, seeded and platform-independent, so a bake is the same everywhere ----
const fade = (t: number): number => t * t * t * (t * (t * 6 - 15) + 10);
const mix = (a: number, b: number, t: number): number => a + (b - a) * t;
function valueNoise(x: number, y: number, z: number, seed: number): number {
const [ix, iy, iz] = [Math.floor(x), Math.floor(y), Math.floor(z)];
const [u, v, w] = [fade(x - ix), fade(y - iy), fade(z - iz)];
const at = (dx: number, dy: number, dz: number): number => hash3(ix + dx, iy + dy, iz + dz, seed);
return mix(
mix(mix(at(0, 0, 0), at(1, 0, 0), u), mix(at(0, 1, 0), at(1, 1, 0), u), v),
mix(mix(at(0, 0, 1), at(1, 0, 1), u), mix(at(0, 1, 1), at(1, 1, 1), u), v),
w,
);
}
function noiseField(n: OrganicNoise): Eval {
const octaves = n.octaves ?? 3;
const seed = n.seed ?? 1;
return (x, y, z) => {
let sum = 0, amp = 1, total = 0, f = 1 / n.scale;
for (let o = 0; o < octaves; o++) {
sum += amp * valueNoise(x * f, y * f, z * f, seed + o);
total += amp;
amp *= 0.5;
f *= 2;
}
return (sum / total) * n.amplitude;
};
}
// ---- Shapes ---------------------------------------------------------------------
/** World to part space: the inverse of rotating X, then Y, then Z. */
function inverseRotation(degrees: Vec3): (x: number, y: number, z: number, out: number[]) => void {
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)];
return (x, y, z, out) => {
const ax = cz * x + sz * y, ay = -sz * x + cz * y;
const bx = cy * ax - sy * z, bz = sy * ax + cy * z;
out[0] = bx;
out[1] = cx * ay + sx * bz;
out[2] = -sx * ay + cx * bz;
};
}
/** Part space to world: X, then Y, then Z. */
function rotateForward(degrees: Vec3, p: 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)];
const [y1, z1] = [cx * p[1] - sx * p[2], sx * p[1] + cx * p[2]];
const [x2, z2] = [cy * p[0] + sy * z1, -sy * p[0] + cy * z1];
return [cz * x2 - sz * y1, sz * x2 + cz * y1, z2];
}
/** The part's distance function in its own frame, and how far from `at` it can reach. */
export function shapeField(part: OrganicPart): { field: (x: number, y: number, z: number) => number; reach: number; thinnest: number } {
const need = (name: keyof OrganicPart): void => {
if (part[name] === undefined) throw new Error(`a ${part.shape} part needs \`${name}\``);
};
switch (part.shape) {
case 'sphere': {
need('radius');
const r = part.radius!;
if (r <= 0) throw new Error('radius must be positive');
return { field: (x, y, z) => Math.sqrt(x * x + y * y + z * z) - r, reach: r, thinnest: r };
}
case 'ellipsoid': {
need('radii');
const [a, b, c] = part.radii!;
if (a <= 0 || b <= 0 || c <= 0) throw new Error('radii must be positive');
return {
field: (x, y, z) => {
const k0 = Math.sqrt((x * x) / (a * a) + (y * y) / (b * b) + (z * z) / (c * c));
const k1 = Math.sqrt((x * x) / a ** 4 + (y * y) / b ** 4 + (z * z) / c ** 4);
return k1 > 1e-12 ? (k0 * (k0 - 1)) / k1 : -Math.min(a, b, c);
},
reach: Math.max(a, b, c),
thinnest: Math.min(a, b, c),
};
}
case 'box': {
need('size');
const [hx, hy, hz] = [part.size![0] / 2, part.size![1] / 2, part.size![2] / 2];
if (hx <= 0 || hy <= 0 || hz <= 0) throw new Error('size must be positive');
const r = Math.min(part.rounding ?? 0, hx, hy, hz);
return {
field: (x, y, z) => {
const qx = Math.abs(x) - hx + r, qy = Math.abs(y) - hy + r, qz = Math.abs(z) - hz + r;
const ox = Math.max(qx, 0), oy = Math.max(qy, 0), oz = Math.max(qz, 0);
return Math.sqrt(ox * ox + oy * oy + oz * oz) + Math.min(Math.max(qx, qy, qz), 0) - r;
},
reach: Math.hypot(hx, hy, hz),
thinnest: Math.min(hx, hy, hz),
};
}
case 'torus': {
need('radius');
need('tube');
const [ring, tube] = [part.radius!, part.tube!];
if (ring <= 0 || tube <= 0) throw new Error('radius and tube must be positive');
return {
field: (x, y, z) => {
const q = Math.sqrt(x * x + z * z) - ring;
return Math.sqrt(q * q + y * y) - tube;
},
reach: ring + tube,
thinnest: tube,
};
}
case 'chain': {
need('points');
const pts = part.points!;
if (pts.length < 2) throw new Error(`a chain needs at least 2 points, not ${pts.length}`);
if (pts.some((p) => p.length !== 4 || !(p[3]! > 0))) throw new Error('every chain point is [x, y, z, radius], with a positive radius');
return {
field: (x, y, z) => {
let best = Infinity;
for (let i = 0; i + 1 < pts.length; i++) {
const a = pts[i]!, b = pts[i + 1]!;
const [bx, by, bz] = [b[0]! - a[0]!, b[1]! - a[1]!, b[2]! - a[2]!];
const [px, py, pz] = [x - a[0]!, y - a[1]!, z - a[2]!];
const len2 = bx * bx + by * by + bz * bz;
const t = len2 > 0 ? Math.min(1, Math.max(0, (px * bx + py * by + pz * bz) / len2)) : 0;
const [dx, dy, dz] = [px - bx * t, py - by * t, pz - bz * t];
const d = Math.sqrt(dx * dx + dy * dy + dz * dz) - (a[3]! + (b[3]! - a[3]!) * t);
if (d < best) best = d;
}
return best;
},
reach: Math.max(...pts.map((p) => Math.hypot(p[0]!, p[1]!, p[2]!) + p[3]!)),
// Its widest: a limb tapering to a point past the grid is a limb, and only one wholly under it goes missing.
thinnest: Math.max(...pts.map((p) => p[3]!)),
};
}
case 'outline': {
need('points');
need('depth');
const depth = part.depth!;
if (depth <= 0) throw new Error('depth must be positive');
if (part.round !== undefined && part.round <= 0) throw new Error('round must be positive');
if (part.points!.length < 3) throw new Error(`an outline needs at least 3 points, not ${part.points!.length}`);
if (part.points!.some((p) => p.length !== 2)) throw new Error('every outline point is [x, y]');
const drawn = curveThrough(part.points!, part.curve ?? 1, true);
const pts = drawn.filter((p, i) => { const q = drawn[(i + 1) % drawn.length]!; return p[0] !== q[0] || p[1] !== q[1]; });
const count = pts.length;
const [xs, ys] = [new Float64Array(count), new Float64Array(count)];
pts.forEach((p, i) => { xs[i] = p[0]!; ys[i] = p[1]!; });
// How far in a point is. Not the distance to the nearest edge, which creases along the drawing's middle wherever the nearest edge changes, and those creases
// shade as ridges down a face. The fourth power of the inverse distance, integrated round the outline: smooth everywhere, and exact beside a straight edge.
const within = (x: number, y: number): number => {
let sum = 0;
for (let i = 0, j = count - 1; i < count; j = i, i++) {
const [ax, ay, ex, ey] = [xs[j]!, ys[j]!, xs[i]! - xs[j]!, ys[i]! - ys[j]!];
const len = Math.hypot(ex, ey);
if (len <= 0) continue;
const [px, py] = [x - ax, y - ay];
const a = -(px * ex + py * ey) / len, b = a + len;
const d = Math.abs(px * ey - py * ex) / len;
if (a * b > 0 && d < 0.02 * Math.min(Math.abs(a), Math.abs(b))) {
sum += Math.abs(a ** -3 - b ** -3) / 3;
} else {
const safe = Math.max(d, 1e-9);
const primitive = (s: number): number => s / (2 * safe * safe * (safe * safe + s * s)) + Math.atan(s / safe) / (2 * safe * safe * safe);
sum += primitive(b) - primitive(a);
}
}
return (sum / (Math.PI / 2)) ** (-1 / 3);
};
const isInside = (x: number, y: number): boolean => {
let inside = false;
for (let i = 0, j = count - 1; i < count; j = i, i++) {
const [ax, ay, bx, by] = [xs[j]!, ys[j]!, xs[i]!, ys[i]!];
if ((by > y) !== (ay > y) && x < ax + ((y - ay) * (bx - ax)) / (by - ay)) inside = !inside;
}
return inside;
};
let round = part.round ?? 0;
if (part.round === undefined) {
// The deepest place in the drawing, so that the dome comes up to `depth` only there.
const [lx, hx, ly, hy] = [Math.min(...xs), Math.max(...xs), Math.min(...ys), Math.max(...ys)];
for (let i = 0; i <= 32; i++) {
for (let j = 0; j <= 32; j++) {
const [x, y] = [lx + ((hx - lx) * i) / 32, ly + ((hy - ly) * j) / 32];
if (isInside(x, y)) round = Math.max(round, within(x, y));
}
}
round = Math.max(round * 1.02, depth * 0.01);
}
const r2 = round * round, d2 = depth * depth;
const reach = Math.max(...pts.map((p) => Math.hypot(p[0]!, p[1]!))) + depth;
return {
// The drawing's distance, then an ellipse across its edge: the same estimate as an ellipsoid's, in the plane of edge and depth.
field: (x, y, z) => {
let edge: number;
if (isInside(x, y)) {
edge = -within(x, y);
} else {
let best = Infinity;
for (let i = 0, j = count - 1; i < count; j = i, i++) {
const [ax, ay, ex, ey] = [xs[j]!, ys[j]!, xs[i]! - xs[j]!, ys[i]! - ys[j]!];
const [px, py] = [x - ax, y - ay];
const len = ex * ex + ey * ey;
const t = len > 0 ? Math.min(1, Math.max(0, (px * ex + py * ey) / len)) : 0;
const [qx, qy] = [px - ex * t, py - ey * t];
best = Math.min(best, qx * qx + qy * qy);
}
edge = Math.sqrt(best);
}
const u = edge + round;
if (u <= 0) return Math.abs(z) - depth;
const k0 = Math.sqrt((u * u) / r2 + (z * z) / d2);
const k1 = Math.sqrt((u * u) / (r2 * r2) + (z * z) / (d2 * d2));
return k1 > 1e-12 ? (k0 * (k0 - 1)) / k1 : -Math.min(round, depth);
},
reach,
thinnest: depth,
};
}
case 'limb': {
need('sections');
const sections = part.sections!;
if (sections.length < 2) throw new Error(`a limb needs at least 2 sections, not ${sections.length}`);
if (sections.some((s) => !(s.across > 0) || !(s.front > 0) || (s.back !== undefined && !(s.back > 0)))) throw new Error('every limb section needs a positive across and front');
const power = part.power ?? 2;
if (!(power >= 1)) throw new Error(`power ${power} must be 1 or more`);
const rows = curveThrough(sections.map((s) => [s.at[0], s.at[1], s.at[2], s.across, s.front, s.back ?? s.front]), part.curve ?? 1, false);
const count = rows.length;
const side = part.side ?? [1, 0, 0];
// A frame per segment: along it, across as near `side` as being square to it allows, and which way it faces.
const frames = rows.slice(0, -1).map((row, i) => {
const next = rows[i + 1]!;
const [ex, ey, ez] = [next[0]! - row[0]!, next[1]! - row[1]!, next[2]! - row[2]!];
const len = Math.hypot(ex, ey, ez) || 1;
const t = [ex / len, ey / len, ez / len];
const dotted = side[0] * t[0]! + side[1] * t[1]! + side[2] * t[2]!;
const u = [side[0] - t[0]! * dotted, side[1] - t[1]! * dotted, side[2] - t[2]! * dotted];
const ul = Math.hypot(u[0]!, u[1]!, u[2]!) || 1;
u[0]! /= ul; u[1]! /= ul; u[2]! /= ul;
// Its front: across crossed with the way along, flipped to a limb running up +y having +z in front, and so on down a limb.
const v = [u[1]! * t[2]! - u[2]! * t[1]!, u[2]! * t[0]! - u[0]! * t[2]!, u[0]! * t[1]! - u[1]! * t[0]!];
const toFront = v[2]! !== 0 ? Math.sign(v[2]!) : Math.sign(v[1]!) || 1;
return { t, u, v: [v[0]! * toFront, v[1]! * toFront, v[2]! * toFront], len };
});
const widest = Math.max(...sections.map((s) => Math.max(s.across, s.front, s.back ?? s.front)));
const thinnest = Math.max(...sections.map((s) => Math.min(s.across, s.front, s.back ?? s.front)));
return {
field: (x, y, z) => {
const at = (i: number, raw: number): number => {
const [a, fr] = [rows[i]!, frames[i]!];
const s = Math.max(0, Math.min(1, raw));
// Everything along it runs through a quadratic spline over the rows. Straight between them, the slope would jump at each one.
const [c0, c1, c2, t] = s < 0.5 ? [rows[Math.max(0, i - 1)]!, a, rows[i + 1]!, s + 0.5] : [a, rows[i + 1]!, rows[Math.min(count - 1, i + 2)]!, s - 0.5];
const [w0, w1, w2] = [0.5 * (1 - t) * (1 - t), 0.5 + t * (1 - t), 0.5 * t * t];
const along = (k: number): number => c0[k]! * w0 + c1[k]! * w1 + c2[k]! * w2;
const [qx, qy, qz] = [x - along(0), y - along(1), z - along(2)];
const u = qx * fr.u[0]! + qy * fr.u[1]! + qz * fr.u[2]!;
const v = qx * fr.v[0]! + qy * fr.v[1]! + qz * fr.v[2]!;
const w = qx * fr.t[0]! + qy * fr.t[1]! + qz * fr.t[2]!;
const across = along(3);
// From back to front across the middle, gradually: where the two simply met there would be a seam down each side of a body.
const [front, back] = [along(4), along(5)];
const lean = Math.max(0, Math.min(1, v / (across * 1.2) + 0.5));
const deep = back + (front - back) * lean * lean * (3 - 2 * lean);
const inPlane = power === 2 ? Math.hypot(u / across, v / deep) : (Math.abs(u / across) ** power + Math.abs(v / deep) ** power) ** (1 / power);
// Past an end it rounds off, by the smaller of its two radii.
const radial = Math.min(across, deep);
const k = Math.abs(w) < 1e-12 ? inPlane : Math.hypot(inPlane, w / radial);
return (k - 1) * radial;
};
// Only the section square to the point: a neighbour's rounded end would stand proud of a narrower place, and the surface would be a row of scallops.
let best = Infinity;
const raws = new Float64Array(count - 1);
for (let i = 0; i < count - 1; i++) {
const [a, fr] = [rows[i]!, frames[i]!];
const raw = ((x - a[0]!) * fr.t[0]! + (y - a[1]!) * fr.t[1]! + (z - a[2]!) * fr.t[2]!) / fr.len;
raws[i] = raw;
if ((raw >= 0 || i === 0) && (raw <= 1 || i === count - 2)) best = Math.min(best, at(i, raw));
}
// Outside a bend, square to nothing: the joint it is nearest.
if (best === Infinity) for (let i = 0; i < count - 1; i++) best = Math.min(best, at(i, raws[i]!));
return best;
},
reach: widest,
thinnest,
};
}
default:
throw new Error(`unknown shape ${JSON.stringify(part.shape)}; there are sphere, ellipsoid, box, torus, chain, outline, limb`);
}
}
interface CompiledPart {
distance: Eval;
blend: number;
subtract: boolean;
tag: string;
color: Color | null;
min: Vec3;
max: Vec3;
thinnest: number;
label: string;
/** Worth asking its box first. */
costly: boolean;
}
const toColor = (c: readonly number[] | undefined): Color | null => {
if (!c) return null;
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];
};
function compilePart(part: OrganicPart, index: number, params: OrganicParams): CompiledPart {
const { field, reach, thinnest } = shapeField(part);
const at = part.at ?? [0, 0, 0];
const noise = part.noise ? noiseField(part.noise) : null;
const rotate = part.rotate && part.shape !== 'sphere' && part.shape !== 'chain' && part.shape !== 'limb' ? inverseRotation(part.rotate) : null;
const local = [0, 0, 0];
const axis = part.mirror === undefined ? -1 : { x: 0, y: 1, z: 2 }[part.mirror];
const label = part.tag ? `"${part.tag}"` : `${index}`;
if (part.rotate && !rotate) throw new Error(`part ${label}: rotate means nothing on a ${part.shape}`);
const distance: Eval = (wx, wy, wz) => {
let x = wx, y = wy, z = wz;
// Folded across the plane: both halves of a symmetric pair are one evaluation, and meet without a seam of their own.
if (axis === 0) x = Math.abs(x);
else if (axis === 1) y = Math.abs(y);
else if (axis === 2) z = Math.abs(z);
x -= at[0]; y -= at[1]; z -= at[2];
if (rotate) { rotate(x, y, z, local); x = local[0]!; y = local[1]!; z = local[2]!; }
const d = field(x, y, z);
return noise ? d + noise(wx, wy, wz) : d;
};
const margin = part.noise?.amplitude ?? 0;
const extent = reach + margin;
let min: Vec3, max: Vec3;
if (part.shape === 'chain') {
// A chain's points are already placed by `at`'s offset.
const pts = part.points!;
min = [0, 1, 2].map((k) => Math.min(...pts.map((p) => p[k]! - p[3]!)) + at[k]! - margin) as unknown as Vec3;
max = [0, 1, 2].map((k) => Math.max(...pts.map((p) => p[k]! + p[3]!)) + at[k]! + margin) as unknown as Vec3;
} else if (part.shape === 'limb') {
// A curve can bow past its sections, a little.
const sections = part.sections!;
const radius = (s: LimbSection): number => Math.max(s.across, s.front, s.back ?? s.front) * 1.2;
min = [0, 1, 2].map((k) => Math.min(...sections.map((s) => s.at[k as 0] - radius(s))) + at[k]! - margin) as unknown as Vec3;
max = [0, 1, 2].map((k) => Math.max(...sections.map((s) => s.at[k as 0] + radius(s))) + at[k]! + margin) as unknown as Vec3;
} else if (part.shape === 'outline') {
// Round what is drawn and not round `at`: a drawing is traced where it lies, far from the origin, and a ball about the origin would spend the grid on nothing.
const pts = part.points!;
// A curve can bow past the points it passes through.
const pad = (part.curve ?? 1) > 1 ? 0.25 * Math.max(Math.max(...pts.map((p) => p[0]!)) - Math.min(...pts.map((p) => p[0]!)), Math.max(...pts.map((p) => p[1]!)) - Math.min(...pts.map((p) => p[1]!))) / Math.max(1, pts.length - 2) : 0;
const [lx, hx, ly, hy] = [Math.min(...pts.map((p) => p[0]!)) - pad, Math.max(...pts.map((p) => p[0]!)) + pad, Math.min(...pts.map((p) => p[1]!)) - pad, Math.max(...pts.map((p) => p[1]!)) + pad];
const depth = part.depth!;
const corners: Vec3[] = [];
for (const x of [lx, hx]) for (const y of [ly, hy]) for (const z of [-depth, depth]) corners.push(rotateForward(part.rotate ?? [0, 0, 0], [x, y, z]));
min = [0, 1, 2].map((k) => Math.min(...corners.map((c) => c[k]!)) + at[k]! - margin) as unknown as Vec3;
max = [0, 1, 2].map((k) => Math.max(...corners.map((c) => c[k]!)) + at[k]! + margin) as unknown as Vec3;
} else {
min = [at[0] - extent, at[1] - extent, at[2] - extent];
max = [at[0] + extent, at[1] + extent, at[2] + extent];
}
if (axis >= 0) {
// The reflection is in the bounds too.
const lo = [...min], hi = [...max];
lo[axis] = Math.min(min[axis]!, -max[axis]!);
hi[axis] = Math.max(max[axis]!, -min[axis]!);
min = lo as unknown as Vec3;
max = hi as unknown as Vec3;
}
const blend = part.blend ?? params.blend ?? 0;
if (blend < 0) throw new Error(`part ${label}: blend ${blend} must not be negative`);
return {
distance, blend, subtract: part.subtract === true, tag: part.tag ?? params.tag ?? '',
color: toColor(part.color), min, max, thinnest, label, costly: part.shape === 'limb' || part.shape === 'outline',
};
}
// ---- The whole body ------------------------------------------------------------
/** Folds the parts in order. `h` is how much of the running result survives the part, 0..1: smooth min's own weight. */
function bodyField(parts: readonly CompiledPart[], noise: Eval | null): Eval {
return (x, y, z) => {
let d = Infinity;
for (const part of parts) {
// The dear shapes first ask their box: far enough off to change nothing, and a body has hundreds of grid points for every one near a finger.
if (part.costly && d !== Infinity) {
const gap = Math.hypot(Math.max(part.min[0] - x, 0, x - part.max[0]), Math.max(part.min[1] - y, 0, y - part.max[1]), Math.max(part.min[2] - z, 0, z - part.max[2]));
if (part.subtract ? gap + d > part.blend : gap - d > part.blend) continue;
}
const p = part.distance(x, y, z);
if (part.subtract) {
const k = part.blend;
if (k <= 0) { d = Math.max(d, -p); continue; }
const h = Math.min(1, Math.max(0, 0.5 - (0.5 * (d + p)) / k));
d = mix(d, -p, h) + k * h * (1 - h);
} else {
const k = part.blend;
if (k <= 0 || d === Infinity) { d = Math.min(d, p); continue; }
const h = Math.min(1, Math.max(0, 0.5 + (0.5 * (p - d)) / k));
d = mix(p, d, h) - k * h * (1 - h);
}
}
return noise ? d + noise(x, y, z) : d;
};
}
/** Which part owns a point on the skin, and the colour there: the same fold, tracking what each step's weight kept. */
function paintAt(parts: readonly CompiledPart[], base: Color | null, x: number, y: number, z: number): { tag: string; color: Color | null } {
let d = Infinity;
let tag = '';
let color: Color | null = base;
const take = (part: CompiledPart, weight: number): void => {
// `weight` is how much the part shows here.
if (weight > 0.5) tag = part.tag;
const c = part.color ?? base;
if (c && color && c !== color) color = [0, 1, 2, 3].map((i) => mix(color![i]!, c[i]!, weight)) as unknown as Color;
else if (c && !color && weight > 0.5) color = c;
};
for (const part of parts) {
const p = part.distance(x, y, z);
const k = Math.max(part.blend, 1e-5);
if (part.subtract) {
const h = Math.min(1, Math.max(0, 0.5 - (0.5 * (d + p)) / k));
d = mix(d, -p, h) + k * h * (1 - h);
if (part.color) take(part, h);
} else if (d === Infinity) {
d = p;
tag = part.tag;
color = part.color ?? base;
} else {
const h = Math.min(1, Math.max(0, 0.5 + (0.5 * (p - d)) / k));
d = mix(p, d, h) - k * h * (1 - h);
take(part, 1 - h);
}
}
return { tag, color };
}
/** Under this many quads, a separate piece of skin is the grid losing a thin tip, never a part: a part is refused long before it is this small. */
const SPECK_QUADS = 24;
/** The quads without the specks a taper past the grid's resolution leaves floating off its end. */
function keepLargeIslands(quads: readonly number[][], vertices: number): number[][] {
const parent = Array.from({ length: vertices }, (_, i) => i);
const find = (i: number): number => {
let at = i;
while (parent[at] !== at) { parent[at] = parent[parent[at]!]!; at = parent[at]!; }
return at;
};
for (const q of quads) for (let i = 1; i < 4; i++) parent[find(q[i]!)] = find(q[0]!);
const size = new Map<number, number>();
for (const q of quads) size.set(find(q[0]!), (size.get(find(q[0]!)) ?? 0) + 1);
return quads.filter((q) => size.get(find(q[0]!))! >= SPECK_QUADS);
}
const FINE_BUDGET = 1_200_000;
/** A point moved onto the surface along the field's slope. */
function settleOnto(field: Eval, q: Vec3, size: number): Vec3 {
let [x, y, z] = q;
const e = size * 0.25;
for (let step = 0; step < 3; step++) {
const d = field(x, y, z);
const [gx, gy, gz] = [field(x + e, y, z) - field(x - e, y, z), field(x, y + e, z) - field(x, y - e, z), field(x, y, z + e) - field(x, y, z - e)];
const length = Math.hypot(gx, gy, gz);
if (length < 1e-9) break;
const slope = length / (2 * e);
const s = Math.max(-size * 2, Math.min(size * 2, d / slope));
x -= (s * gx) / length; y -= (s * gy) / length; z -= (s * gz) / length;
}
return [x, y, z];
}
/** One more shell: the skin of @p params' parts, in the steps' usual outward winding. */
export function organic(mesh: PolyMesh, params: OrganicParams): PolyMesh {
if (!params.parts?.length) throw new Error('`parts` names nothing to build');
const resolution = params.resolution ?? ORGANIC_DEFAULT_RESOLUTION;
const most = params.maxResolution ?? ORGANIC_MAX_RESOLUTION;
if (!Number.isInteger(resolution) || resolution < 8 || resolution > most) {
throw new Error(`resolution ${resolution} must be a whole number, 8..${most}`);
}
const parts = params.parts.map((p, i) => {
try {
return compilePart(p, i, params);
} catch (e) {
throw new Error(`part ${p.tag ? `"${p.tag}"` : i}: ${(e as Error).message}`);
}
});
if (parts[0]!.subtract) throw new Error('the first part cannot subtract: there is nothing yet to carve');
const adding = parts.filter((p) => !p.subtract);
const noise = params.noise ? noiseField(params.noise) : null;
const field = bodyField(parts, noise);
const margin = (params.noise?.amplitude ?? 0) + Math.max(...adding.map((p) => p.blend));
const min = [0, 1, 2].map((k) => Math.min(...adding.map((p) => p.min[k]!)) - margin);
const max = [0, 1, 2].map((k) => Math.max(...adding.map((p) => p.max[k]!)) + margin);
const longest = Math.max(max[0]! - min[0]!, max[1]! - min[1]!, max[2]! - min[2]!);
const cell = longest / resolution;
// A part the grid cannot see simply is not in the result, and it reads as a model that ignored the request.
// Inside a region to be split finer, the fine faces are what find it.
const inFine = (part: CompiledPart): boolean => (params.fine ?? []).some((region) => Math.hypot(
Math.max(part.min[0] - region.at[0], 0, region.at[0] - part.max[0]),
Math.max(part.min[1] - region.at[1], 0, region.at[1] - part.max[1]),
Math.max(part.min[2] - region.at[2], 0, region.at[2] - part.max[2]),
) < region.radius);
for (const part of parts) {
if (part.thinnest * 2 < cell * 1.5 && !inFine(part)) {
const needed = Math.ceil((longest * 1.5) / (part.thinnest * 2));
throw new Error(`part ${part.label} is ${(part.thinnest * 2).toFixed(4)} across, too thin for the grid's cell of ${cell.toFixed(4)}, so it would vanish; `
+ (needed <= ORGANIC_MAX_RESOLUTION
? `make it thicker or raise resolution to at least ${needed}`
: `make it at least ${((longest / ORGANIC_MAX_RESOLUTION) * 1.5).toFixed(4)} across, or build this body smaller and separate from its small details`));
}
}
const pad = 2;
const [nx, ny, nz] = [0, 1, 2].map((k) => Math.ceil((max[k]! - min[k]!) / cell) + pad * 2 + 1) as [number, number, number];
const ox = min[0]! - pad * cell, oy = min[1]! - pad * cell, oz = min[2]! - pad * cell;
const values = new Float32Array(nx * ny * nz);
const idx = (i: number, j: number, k: number): number => i + nx * (j + ny * k);
// Most of the grid is nowhere near the skin and only its sign is ever read. A block whose centre is clearly further
// from the surface than the block is wide takes that one value. Doubled, as an ellipsoid's distance is an estimate.
const BLOCK = 4;
const clear = Math.sqrt(3) * BLOCK * cell;
for (let bk = 0; bk < nz; bk += BLOCK) {
for (let bj = 0; bj < ny; bj += BLOCK) {
for (let bi = 0; bi < nx; bi += BLOCK) {
const centre = field(ox + (bi + BLOCK / 2) * cell, oy + (bj + BLOCK / 2) * cell, oz + (bk + BLOCK / 2) * cell);
const far = Math.abs(centre) > clear;
for (let k = bk; k < Math.min(nz, bk + BLOCK); k++) {
for (let j = bj; j < Math.min(ny, bj + BLOCK); j++) {
for (let i = bi; i < Math.min(nx, bi + BLOCK); i++) {
values[idx(i, j, k)] = far ? centre : field(ox + i * cell, oy + j * cell, oz + k * cell);
}
}
}
}
}
}
// Surface Nets: one vertex per cell the surface passes through, at the mean of where it crosses that cell's edges.
const CORNERS = [[0, 0, 0], [1, 0, 0], [0, 1, 0], [1, 1, 0], [0, 0, 1], [1, 0, 1], [0, 1, 1], [1, 1, 1]] as const;
const EDGES = [[0, 1], [2, 3], [4, 5], [6, 7], [0, 2], [1, 3], [4, 6], [5, 7], [0, 4], [1, 5], [2, 6], [3, 7]] as const;
const cellVertex = new Int32Array(nx * ny * nz).fill(-1);
const positions: Vec3[] = [];
const corner = new Float32Array(8);
for (let k = 0; k < nz - 1; k++) {
for (let j = 0; j < ny - 1; j++) {
for (let i = 0; i < nx - 1; i++) {
let inside = 0;
for (let c = 0; c < 8; c++) {
const v = values[idx(i + CORNERS[c]![0], j + CORNERS[c]![1], k + CORNERS[c]![2])]!;
corner[c] = v;
if (v < 0) inside++;
}
if (inside === 0 || inside === 8) continue;
let sx = 0, sy = 0, sz = 0, count = 0;
for (const [a, b] of EDGES) {
const va = corner[a]!, vb = corner[b]!;
if ((va < 0) === (vb < 0)) continue;
const t = va / (va - vb);
const A = CORNERS[a]!, B = CORNERS[b]!;
sx += A[0] + (B[0] - A[0]) * t;
sy += A[1] + (B[1] - A[1]) * t;
sz += A[2] + (B[2] - A[2]) * t;
count++;
}
cellVertex[idx(i, j, k)] = positions.length;
positions.push([ox + (i + sx / count) * cell, oy + (j + sy / count) * cell, oz + (k + sz / count) * cell]);
}
}
}
if (positions.length === 0) throw new Error('these parts leave no surface: everything was carved away');
// Settled onto the true surface: the mean of the crossings is only near it, and that is what makes a grid show through as terracing.
const e = cell * 0.25;
for (let n = 0; n < positions.length; n++) {
let [x, y, z] = positions[n]!;
for (let step = 0; step < 2; step++) {
const d = field(x, y, z);
const gx = field(x + e, y, z) - field(x - e, y, z);
const gy = field(x, y + e, z) - field(x, y - e, z);
const gz = field(x, y, z + e) - field(x, y, z - e);
const g2 = (gx * gx + gy * gy + gz * gz) / (4 * e * e);
if (g2 < 1e-8) break;
// Bounded, so a crease's bad gradient cannot throw a vertex across the cell.
const s = Math.max(-cell * 0.5, Math.min(cell * 0.5, d / Math.sqrt(g2)));
const n2 = Math.sqrt(g2) * 2 * e;
x -= (s * gx) / n2; y -= (s * gy) / n2; z -= (s * gz) / n2;
}
positions[n] = [x, y, z];
}
// A quad across every grid edge the surface crosses, wound by which end is inside.
const quads: number[][] = [];
const quad = (a: number, b: number, c: number, d: number, flip: boolean): void => {
if (a < 0 || b < 0 || c < 0 || d < 0) return;
quads.push(flip ? [d, c, b, a] : [a, b, c, d]);
};
for (let k = 1; k < nz - 1; k++) {
for (let j = 1; j < ny - 1; j++) {
for (let i = 1; i < nx - 1; i++) {
const here = values[idx(i, j, k)]! < 0;
if (here !== (values[idx(i + 1, j, k)]! < 0)) {
quad(cellVertex[idx(i, j - 1, k - 1)]!, cellVertex[idx(i, j, k - 1)]!, cellVertex[idx(i, j, k)]!, cellVertex[idx(i, j - 1, k)]!, !here);
}
if (here !== (values[idx(i, j + 1, k)]! < 0)) {
quad(cellVertex[idx(i - 1, j, k - 1)]!, cellVertex[idx(i - 1, j, k)]!, cellVertex[idx(i, j, k)]!, cellVertex[idx(i, j, k - 1)]!, !here);
}
if (here !== (values[idx(i, j, k + 1)]! < 0)) {
quad(cellVertex[idx(i - 1, j - 1, k)]!, cellVertex[idx(i, j - 1, k)]!, cellVertex[idx(i, j, k)]!, cellVertex[idx(i - 1, j, k)]!, !here);
}
}
}
}
const base = toColor(params.color);
const at = params.at ?? [0, 0, 0];
const start = mesh.positions.length;
const painted = (loop: readonly number[], where: readonly Vec3[]): Face => {
let cx = 0, cy = 0, cz = 0;
for (const v of loop) {
cx += where[v]![0]; cy += where[v]![1]; cz += where[v]![2];
}
const { tag, color } = paintAt(parts, base, cx / loop.length, cy / loop.length, cz / loop.length);
return { v: [...loop], tag: tag || params.tag || '', smooth: true, ...(color ? { color } : {}) };
};
let skin: PolyMesh = { positions, faces: keepLargeIslands(quads, positions.length).map((loop) => painted(loop, positions)) };
for (const region of params.fine ?? []) {
const places: Vec3[] = region.mirror ? [region.at, [-region.at[0], region.at[1], region.at[2]]] : [region.at];
for (const place of places) {
const chosen = new Set<number>();
skin.faces.forEach((face, f) => {
const p = skin.positions[face.v[0]!]!;
if (Math.hypot(p[0] - place[0], p[1] - place[1], p[2] - place[2]) < region.radius) chosen.add(f);
});
if (chosen.size === 0) continue;
const before = skin.positions.length;
const outside = skin.faces.length - chosen.size;
const { mesh: fine } = refine(skin, chosen, region.longest, FINE_BUDGET);
if (fine === skin) continue;
const settled = fine.positions.map((q, n) => (n < before ? q : settleOnto(field, q, region.longest)));
// Painted again where it was split: a lip's edge is finer than the grid that found it.
const faces = fine.faces.map((face, n) => (n < outside ? face : painted(face.v, settled)));
skin = { positions: settled, faces };
}
}
return {
positions: [...mesh.positions, ...skin.positions.map((p) => add(p, at))],
faces: [...mesh.faces, ...skin.faces.map((face) => ({ ...face, v: face.v.map((v) => v + start) }))],
};
}