Skip to content

Code-first video & image, rendered natively on WebGPU.

10.6 KB
Raw Blame
/**
 * Procedural surface scattering: deterministic points on any mesh (terrain,
 * SDF sculpture, primitive or loaded model), sampled by triangle area,
 * filtered by slope, altitude and exclusion zones, spaced by a Poisson-disk
 * test on a spatial hash, and oriented between world up and the surface.
 */

import { poseNodes, type Quat } from "../loaders/pose.js";
import type { Model3DData } from "../loaders/types.js";
import { type Mat4, Matrix4Math } from "../math3d/matrix4.js";
import { createRandom } from "../math3d/noise.js";

type V3 = [number, number, number];

export interface ScatterExclusion {
	/** Center in the surface's parent space, px. */
	x: number;
	z: number;
	/** Nothing grows inside this radius, px. */
	radius: number;
	/** Density ramps back to full over this many px past `radius`. Default 0. */
	falloff?: number;
}

export interface ScatterOptions {
	/** Points to place (fewer when spacing or filters leave no room). */
	count: number;
	/** Poisson-disk spacing: no two points closer than this, px. */
	minDistance?: number;
	seed?: number;
	/** Allowed slope in degrees from level ground. Default [0, 89]. */
	slopeRange?: [number, number];
	/** Allowed altitude 0..1 across the surface's vertical extent (0 = lowest). Default [0, 1]. */
	elevationRange?: [number, number];
	/** 0 keeps instances upright, 1 stands them on the surface normal. Default 0.3. */
	alignToNormal?: number;
	/** Uniform scale drawn per point. Default [1, 1]. */
	scaleRange?: [number, number];
	/** Random turn around the instance's up axis. Default true. */
	randomYaw?: boolean;
	exclude?: ScatterExclusion[];
}

export interface ScatterPoint {
	/** On the surface, in its parent space. */
	position: V3;
	/** Unit face normal there. */
	normal: V3;
	rotation: Quat;
	scale: number;
	/** Normalized altitude 0..1. */
	elevation: number;
}

export interface ScatterSurface {
	model: Model3DData;
	/** The surface layer's transform (its parent space ← model space). */
	matrix?: Mat4;
}

export interface ScatterResult {
	points: ScatterPoint[];
	/** Share of the surface's area its slope and altitude filters keep, 0..1. */
	acceptedArea: number;
}

const UP: V3 = [0, -1, 0];

function transformPoint(m: Mat4, x: number, y: number, z: number): V3 {
	return [
		m[0] * x + m[4] * y + m[8] * z + m[12],
		m[1] * x + m[5] * y + m[9] * z + m[13],
		m[2] * x + m[6] * y + m[10] * z + m[14],
	];
}

/** Every triangle of the model in the surface's parent space, flat xyz × 3. */
export function surfaceTriangles(surface: ScatterSurface): Float64Array {
	const { model } = surface;
	const root = Matrix4Math.multiply(
		surface.matrix ?? Matrix4Math.identity(),
		model.rootTransform ?? Matrix4Math.identity(),
	);
	const posed = model.nodes ? poseNodes(model, undefined, 0) : undefined;
	const tris: number[] = [];
	for (const mesh of model.meshes) {
		if (mesh.topology && mesh.topology !== "triangle-list") continue;
		const node =
			posed && mesh.node !== undefined && mesh.skin === undefined
				? posed[mesh.node]
				: undefined;
		const m = node ? Matrix4Math.multiply(root, node) : root;
		const p = mesh.positions;
		for (const i of mesh.indices) {
			tris.push(...transformPoint(m, p[i * 3]!, p[i * 3 + 1]!, p[i * 3 + 2]!));
		}
	}
	return new Float64Array(tris);
}

function quatMul(a: Quat, b: Quat): Quat {
	return [
		a[3] * b[0] + a[0] * b[3] + a[1] * b[2] - a[2] * b[1],
		a[3] * b[1] - a[0] * b[2] + a[1] * b[3] + a[2] * b[0],
		a[3] * b[2] + a[0] * b[1] - a[1] * b[0] + a[2] * b[3],
		a[3] * b[3] - a[0] * b[0] - a[1] * b[1] - a[2] * b[2],
	];
}

/** Shortest rotation taking unit `a` onto unit `b`. */
function quatBetween(a: V3, b: V3): Quat {
	const d = a[0] * b[0] + a[1] * b[1] + a[2] * b[2];
	if (d < -0.999999) return [1, 0, 0, 0];
	const c: V3 = [
		a[1] * b[2] - a[2] * b[1],
		a[2] * b[0] - a[0] * b[2],
		a[0] * b[1] - a[1] * b[0],
	];
	const q: Quat = [c[0], c[1], c[2], 1 + d];
	const len = Math.hypot(...q);
	return [q[0] / len, q[1] / len, q[2] / len, q[3] / len];
}

/** Rotates `v` by unit quaternion `q`. */
export function rotateByQuat(q: Quat, v: V3): V3 {
	const t: V3 = [
		2 * (q[1] * v[2] - q[2] * v[1]),
		2 * (q[2] * v[0] - q[0] * v[2]),
		2 * (q[0] * v[1] - q[1] * v[0]),
	];
	return [
		v[0] + q[3] * t[0] + (q[1] * t[2] - q[2] * t[1]),
		v[1] + q[3] * t[1] + (q[2] * t[0] - q[0] * t[2]),
		v[2] + q[3] * t[2] + (q[0] * t[1] - q[1] * t[0]),
	];
}

interface Candidates {
	/** Accepted triangle indices and their cumulative areas. */
	tris: Int32Array;
	cumulative: Float64Array;
	normals: Float64Array;
	minY: number;
	maxY: number;
	acceptedArea: number;
}

/** Face normal of triangle `t`, and its area. */
function face(tri: Float64Array, t: number): { n: V3; area: number } {
	const o = t * 9;
	const ex = tri[o + 3]! - tri[o]!;
	const ey = tri[o + 4]! - tri[o + 1]!;
	const ez = tri[o + 5]! - tri[o + 2]!;
	const fx = tri[o + 6]! - tri[o]!;
	const fy = tri[o + 7]! - tri[o + 1]!;
	const fz = tri[o + 8]! - tri[o + 2]!;
	const c: V3 = [ey * fz - ez * fy, ez * fx - ex * fz, ex * fy - ey * fx];
	const len = Math.hypot(...c);
	return {
		n: len > 0 ? [c[0] / len, c[1] / len, c[2] / len] : [0, -1, 0],
		area: len / 2,
	};
}

/** The triangles the slope and altitude filters keep, weighted by area. */
function candidates(tri: Float64Array, o: ScatterOptions): Candidates {
	const count = tri.length / 9;
	let minY = Number.POSITIVE_INFINITY;
	let maxY = Number.NEGATIVE_INFINITY;
	for (let i = 1; i < tri.length; i += 3) {
		minY = Math.min(minY, tri[i]!);
		maxY = Math.max(maxY, tri[i]!);
	}
	const spanY = maxY - minY > 1e-9 ? maxY - minY : 1;
	const [s0, s1] = o.slopeRange ?? [0, 89];
	const [e0, e1] = o.elevationRange ?? [0, 1];
	const keep: number[] = [];
	const cumulative: number[] = [];
	const normals: number[] = [];
	let total = 0;
	let all = 0;
	for (let t = 0; t < count; t++) {
		const { n, area } = face(tri, t);
		all += area;
		if (area <= 0) continue;
		const slope = (Math.acos(Math.max(-1, Math.min(1, -n[1]))) * 180) / Math.PI;
		const cy = (tri[t * 9 + 1]! + tri[t * 9 + 4]! + tri[t * 9 + 7]!) / 3;
		const elevation = (maxY - cy) / spanY;
		if (slope < s0 || slope > s1 || elevation < e0 || elevation > e1) continue;
		total += area;
		keep.push(t);
		cumulative.push(total);
		normals.push(...n);
	}
	return {
		tris: Int32Array.from(keep),
		cumulative: Float64Array.from(cumulative),
		normals: Float64Array.from(normals),
		minY,
		maxY,
		acceptedArea: all > 0 ? total / all : 0,
	};
}

/** Index of the first cumulative area above `x`. */
function pick(cumulative: Float64Array, x: number): number {
	let lo = 0;
	let hi = cumulative.length - 1;
	while (lo < hi) {
		const mid = (lo + hi) >> 1;
		if (cumulative[mid]! > x) hi = mid;
		else lo = mid + 1;
	}
	return lo;
}

/** Whether exclusion zones let a point at (x, z) grow, given a uniform draw `r`. */
function allowed(
	zones: ScatterExclusion[] | undefined,
	x: number,
	z: number,
	r: number,
): boolean {
	for (const e of zones ?? []) {
		const d = Math.hypot(x - e.x, z - e.z) - e.radius;
		if (d < 0) return false;
		const f = e.falloff ?? 0;
		if (f > 0 && d < f && r > d / f) return false;
	}
	return true;
}

/** A spatial hash of accepted points, for the Poisson-disk distance test. */
class PoissonGrid {
	private cells = new Map<string, V3[]>();
	constructor(private spacing: number) {}

	private key(x: number, y: number, z: number): string {
		const s = this.spacing;
		return `${Math.floor(x / s)},${Math.floor(y / s)},${Math.floor(z / s)}`;
	}

	fits(p: V3): boolean {
		const s = this.spacing;
		for (let dx = -1; dx <= 1; dx++)
			for (let dy = -1; dy <= 1; dy++)
				for (let dz = -1; dz <= 1; dz++) {
					const near = this.cells.get(
						this.key(p[0] + dx * s, p[1] + dy * s, p[2] + dz * s),
					);
					for (const q of near ?? []) {
						if (Math.hypot(p[0] - q[0], p[1] - q[1], p[2] - q[2]) < s)
							return false;
					}
				}
		return true;
	}

	add(p: V3): void {
		const k = this.key(...p);
		const list = this.cells.get(k);
		if (list) list.push(p);
		else this.cells.set(k, [p]);
	}
}

function orient(n: V3, o: ScatterOptions, rand: () => number): Quat {
	const a = Math.max(0, Math.min(1, o.alignToNormal ?? 0.3));
	const u: V3 = [
		UP[0] + (n[0] - UP[0]) * a,
		UP[1] + (n[1] - UP[1]) * a,
		UP[2] + (n[2] - UP[2]) * a,
	];
	const len = Math.hypot(...u) || 1;
	const align = quatBetween(UP, [u[0] / len, u[1] / len, u[2] / len]);
	const yaw = (o.randomYaw ?? true) ? rand() * Math.PI * 2 : 0;
	// Turn around the instance's own up (-y) first, then lean onto the surface.
	const spin: Quat = [0, -Math.sin(yaw / 2), 0, Math.cos(yaw / 2)];
	return quatMul(align, spin);
}

/** Scatters points on `surface`. Same inputs, same points. */
export function scatterOnSurface(
	surface: ScatterSurface,
	o: ScatterOptions,
): ScatterResult {
	const tri = surfaceTriangles(surface);
	const c = candidates(tri, o);
	const points: ScatterPoint[] = [];
	const total = c.cumulative[c.cumulative.length - 1] ?? 0;
	const count = Math.max(0, Math.floor(o.count));
	if (total <= 0 || count === 0)
		return { points, acceptedArea: c.acceptedArea };
	const rand = createRandom(o.seed ?? 1);
	const spacing = Math.max(0, o.minDistance ?? 0);
	const poisson = spacing > 0 ? new PoissonGrid(spacing) : undefined;
	const [sc0, sc1] = o.scaleRange ?? [1, 1];
	const spanY = c.maxY - c.minY > 1e-9 ? c.maxY - c.minY : 1;
	const attempts = count * 30;
	for (let a = 0; a < attempts && points.length < count; a++) {
		const k = pick(c.cumulative, rand() * total);
		const t = c.tris[k]! * 9;
		// Uniform on the triangle.
		const r1 = Math.sqrt(rand());
		const r2 = rand();
		const w0 = 1 - r1;
		const w1 = r1 * (1 - r2);
		const w2 = r1 * r2;
		const p: V3 = [0, 1, 2].map(
			(d) => w0 * tri[t + d]! + w1 * tri[t + 3 + d]! + w2 * tri[t + 6 + d]!,
		) as V3;
		const gate = rand();
		const yawDraw = createRandom(Math.floor(rand() * 2 ** 31));
		const scaleDraw = rand();
		if (!allowed(o.exclude, p[0], p[2], gate)) continue;
		if (poisson && !poisson.fits(p)) continue;
		poisson?.add(p);
		const n: V3 = [
			c.normals[k * 3]!,
			c.normals[k * 3 + 1]!,
			c.normals[k * 3 + 2]!,
		];
		points.push({
			position: p,
			normal: n,
			rotation: orient(n, o, yawDraw),
			scale: sc0 + (sc1 - sc0) * scaleDraw,
			elevation: (c.maxY - p[1]) / spanY,
		});
	}
	return { points, acceptedArea: c.acceptedArea };
}

/**
 * Where an instance's origin goes so its lowest point (local max y, as up
 * is -y) rests on the scattered point, sunk `sink` px into the surface.
 */
export function seatOnSurface(
	point: ScatterPoint,
	bottomY: number,
	sink = 0,
): V3 {
	const lift = rotateByQuat(point.rotation, [
		0,
		bottomY * point.scale - sink,
		0,
	]);
	return [
		point.position[0] - lift[0],
		point.position[1] - lift[1],
		point.position[2] - lift[2],
	];
}