Skip to content

3D engine that AI agents drive

22.0 KB
Raw Blame
import { withPositions } from './mesh-field-edits.js';
import { vertexNormals } from './mesh-normals.js';
import { invalidField } from './field-error.js';
import { editField, editInteger, editBoolean, editAxis, editDefault } from './mesh-edit-field.js';
import { vertexGroupWeights } from './mesh-data.js';

// Modifiers that only move vertices, each from a few numbers: lattice (a coarse grid of moved control points), curve (bend
// along a path), hook (pull the vertices near a point), wave (a travelling ripple), smooth_laplacian (smoothing that keeps
// volume) and warp (carry a point to another with a falloff). Every list is bounded, and the
// errors name the field and the limit.

export const MAX_LATTICE_DIVISIONS = 8;
export const MAX_LATTICE_MOVES = 64;
export const MAX_CURVE_POINTS = 64;
export const HOOK_FALLOFFS = Object.freeze(['smooth', 'linear', 'constant']);
export const MAX_LAPLACIAN_ITERATIONS = 64;
export const WAVE_AXES = Object.freeze(['xy', 'x', 'y']);
const AXIS_NAMES = Object.freeze({ x: 0, y: 1, z: 2 });
const CURVE_SAMPLES_PER_SEGMENT = 16;
const MINIMUM_SPAN = 1e-9;
const GROUP_NAME_PATTERN = /^[A-Za-z0-9][A-Za-z0-9._-]{0,47}$/;
// Taubin's pass band: the shrinking step of size factor is followed by an inflating step that cancels it on smooth shapes.
const TAUBIN_PASS_BAND = 0.1;

function meshBounds(mesh) {
  const low = [Infinity, Infinity, Infinity];
  const high = [-Infinity, -Infinity, -Infinity];
  for (let vertex = 0; vertex < mesh.vertexCount; vertex++) {
    for (let axis = 0; axis < 3; axis++) {
      low[axis] = Math.min(low[axis], mesh.positions[vertex * 3 + axis]);
      high[axis] = Math.max(high[axis], mesh.positions[vertex * 3 + axis]);
    }
  }
  return { low, high };
}

/**
 * A lattice of `divisions` control points per axis spanning the mesh bounds. Each move shifts one control point by an
 * offset, and every vertex follows the trilinear blend of the shifts around it. Blender's default is a B-spline blend,
 * which is smoother between points.
 */
export function latticeDeform(mesh, { divisions, moves }) {
  const [countX, countY, countZ] = divisions;
  const shifts = new Float64Array(countX * countY * countZ * 3);
  const indexOfPoint = (x, y, z) => ((z * countY + y) * countX + x) * 3;
  for (const { point, offset } of moves) {
    for (let axis = 0; axis < 3; axis++) shifts[indexOfPoint(...point) + axis] += offset[axis];
  }
  const { low, high } = meshBounds(mesh);
  const counts = [countX, countY, countZ];
  const positions = new Float32Array(mesh.positions);
  for (let vertex = 0; vertex < mesh.vertexCount; vertex++) {
    const cells = [0, 0, 0];
    const fractions = [0, 0, 0];
    for (let axis = 0; axis < 3; axis++) {
      const span = high[axis] - low[axis];
      const position = span > MINIMUM_SPAN ? (mesh.positions[vertex * 3 + axis] - low[axis]) / span * (counts[axis] - 1) : 0;
      cells[axis] = Math.min(Math.floor(position), counts[axis] - 2);
      fractions[axis] = position - cells[axis];
    }
    for (let corner = 0; corner < 8; corner++) {
      const stepX = corner & 1;
      const stepY = (corner >> 1) & 1;
      const stepZ = (corner >> 2) & 1;
      const weight = (stepX ? fractions[0] : 1 - fractions[0]) * (stepY ? fractions[1] : 1 - fractions[1]) * (stepZ ? fractions[2] : 1 - fractions[2]);
      if (weight === 0) continue;
      const base = indexOfPoint(cells[0] + stepX, cells[1] + stepY, cells[2] + stepZ);
      for (let axis = 0; axis < 3; axis++) positions[vertex * 3 + axis] += shifts[base + axis] * weight;
    }
  }
  return positions;
}

function hookWeight(falloff, distance, radius) {
  if (distance >= radius) return 0;
  const closeness = 1 - distance / radius;
  if (falloff === 'constant') return 1;
  if (falloff === 'linear') return closeness;
  return closeness * closeness * (3 - 2 * closeness);
}

/** Blender's Hook: vertices within `radius` of `center` move by `translation` times `strength` and the falloff weight. */
export function hookDeform(mesh, { center, radius, translation, strength, falloff }) {
  const positions = new Float32Array(mesh.positions);
  for (let vertex = 0; vertex < mesh.vertexCount; vertex++) {
    const distance = Math.hypot(
      mesh.positions[vertex * 3] - center[0],
      mesh.positions[vertex * 3 + 1] - center[1],
      mesh.positions[vertex * 3 + 2] - center[2],
    );
    const weight = hookWeight(falloff, distance, radius) * strength;
    if (weight === 0) continue;
    for (let axis = 0; axis < 3; axis++) positions[vertex * 3 + axis] += translation[axis] * weight;
  }
  return positions;
}

/**
 * Blender's Wave: a gaussian ripple along z (or the vertex normal) that travels away from `start` in x, y or both. `time` is a
 * frame number, as the scene frame is in Blender; the ripple moves `speed` units per frame after `timeOffset`.
 */
export function waveDeform(mesh, { height, width, narrowness, speed, time, timeOffset, start, cyclic, axes, normal }) {
  const positions = new Float32Array(mesh.positions);
  const normals = normal ? vertexNormals(mesh) : null;
  const floor = 1 / Math.exp(width * narrowness * width * narrowness);
  for (let vertex = 0; vertex < mesh.vertexCount; vertex++) {
    const x = mesh.positions[vertex * 3] - start[0];
    const y = mesh.positions[vertex * 3 + 1] - start[1];
    let phase = axes === 'xy' ? Math.hypot(x, y) : axes === 'x' ? x : y;
    phase -= (time - timeOffset) * speed;
    if (cyclic) phase = (phase - width) % (width * 2) + width;
    if (!(phase > -width && phase < width)) continue;
    const scaled = phase * narrowness;
    const displacement = height * (1 / Math.exp(scaled * scaled) - floor);
    if (normals) {
      for (let axis = 0; axis < 3; axis++) positions[vertex * 3 + axis] += normals[vertex * 3 + axis] * displacement;
    } else {
      positions[vertex * 3 + 2] += displacement;
    }
  }
  return positions;
}

/** Vertices on an edge that only one face uses: the rim of an open mesh. */
function boundaryVertices(mesh) {
  const faceCounts = new Map();
  for (let face = 0; face < mesh.faceCount; face++) {
    const start = mesh.faceOffsets[face];
    const end = mesh.faceOffsets[face + 1];
    for (let corner = start; corner < end; corner++) {
      const first = mesh.cornerVertices[corner];
      const second = mesh.cornerVertices[corner + 1 < end ? corner + 1 : start];
      const key = Math.min(first, second) * mesh.vertexCount + Math.max(first, second);
      faceCounts.set(key, (faceCounts.get(key) ?? 0) + 1);
    }
  }
  const pinned = new Uint8Array(mesh.vertexCount);
  for (const [key, count] of faceCounts) {
    if (count !== 1) continue;
    pinned[Math.floor(key / mesh.vertexCount)] = 1;
    pinned[key % mesh.vertexCount] = 1;
  }
  return pinned;
}

function laplacianStep(mesh, positions, sums, counts, stepSizes) {
  sums.fill(0);
  counts.fill(0);
  for (let edge = 0; edge < mesh.edgeCount; edge++) {
    const first = mesh.edgeVertices[edge * 2];
    const second = mesh.edgeVertices[edge * 2 + 1];
    for (let axis = 0; axis < 3; axis++) {
      sums[first * 3 + axis] += positions[second * 3 + axis];
      sums[second * 3 + axis] += positions[first * 3 + axis];
    }
    counts[first]++;
    counts[second]++;
  }
  for (let vertex = 0; vertex < mesh.vertexCount; vertex++) {
    if (counts[vertex] === 0 || stepSizes[vertex] === 0) continue;
    for (let axis = 0; axis < 3; axis++) {
      const index = vertex * 3 + axis;
      positions[index] += stepSizes[vertex] * (sums[index] / counts[vertex] - positions[index]);
    }
  }
}

/**
 * Laplacian smoothing that keeps volume. Plain smoothing pulls every vertex toward the mean of its neighbours and so shrinks a
 * closed mesh; with preserveVolume each iteration is a shrinking step of size factor followed by an inflating step (Taubin's
 * lambda and mu), which cancels the shrink for a smooth shape. Group weights scale each vertex's step, and the rim of an open
 * mesh stays where it is unless pinBoundary is false.
 */
export function smoothLaplacianDeform(mesh, { factor, iterations, preserveVolume, pinBoundary, group }) {
  const weights = group === undefined ? null : vertexGroupWeights(mesh, group);
  const pinned = pinBoundary ? boundaryVertices(mesh) : null;
  const shrinkSizes = new Float64Array(mesh.vertexCount);
  const inflateSizes = new Float64Array(mesh.vertexCount);
  const inflateFactor = 1 / (TAUBIN_PASS_BAND - 1 / factor);
  for (let vertex = 0; vertex < mesh.vertexCount; vertex++) {
    const weight = (weights ? weights[vertex] : 1) * (pinned && pinned[vertex] ? 0 : 1);
    shrinkSizes[vertex] = factor * weight;
    inflateSizes[vertex] = preserveVolume ? inflateFactor * weight : 0;
  }
  const positions = Float64Array.from(mesh.positions);
  const sums = new Float64Array(positions.length);
  const counts = new Uint32Array(mesh.vertexCount);
  for (let iteration = 0; iteration < iterations; iteration++) {
    laplacianStep(mesh, positions, sums, counts, shrinkSizes);
    if (preserveVolume) laplacianStep(mesh, positions, sums, counts, inflateSizes);
  }
  return Float32Array.from(positions);
}

function rotateAbout(offset, axis, angle) {
  const cosine = Math.cos(angle);
  const sine = Math.sin(angle);
  const along = dotProduct(axis, offset);
  const across = crossProduct(axis, offset);
  return offset.map((value, component) => value * cosine + across[component] * sine + axis[component] * along * (1 - cosine));
}

/**
 * Carry the mesh from point `from` to point `to`: a vertex within `radius` of `from` moves by (to - from) times the curve
 * weight, so the vertex at `from` lands on `to` and vertices beyond the radius stay. A twist turns each vertex about the
 * axis from `from` toward `to` by that many degrees times the same weight.
 */
export function warpDeform(mesh, { from, to, radius, curve, twist }) {
  const shift = to.map((value, axis) => value - from[axis]);
  const shiftLength = Math.hypot(...shift);
  const direction = shiftLength > MINIMUM_SPAN ? shift.map(component => component / shiftLength) : null;
  const positions = new Float32Array(mesh.positions);
  for (let vertex = 0; vertex < mesh.vertexCount; vertex++) {
    const offset = [0, 1, 2].map(axis => mesh.positions[vertex * 3 + axis] - from[axis]);
    const weight = hookWeight(curve, Math.hypot(...offset), radius);
    if (weight === 0) continue;
    const turned = twist !== 0 && direction ? rotateAbout(offset, direction, twist * Math.PI / 180 * weight) : offset;
    for (let axis = 0; axis < 3; axis++) positions[vertex * 3 + axis] = from[axis] + turned[axis] + shift[axis] * weight;
  }
  return positions;
}

function catmullRom(before, from, to, after, fraction) {
  const squared = fraction * fraction;
  const cubed = squared * fraction;
  return from.map((value, axis) => 0.5 * (
    2 * value + (to[axis] - before[axis]) * fraction
    + (2 * before[axis] - 5 * value + 4 * to[axis] - after[axis]) * squared
    + (3 * value - before[axis] - 3 * to[axis] + after[axis]) * cubed));
}

function normalizedVector(vector) {
  const length = Math.hypot(...vector);
  return vector.map(component => component / length);
}

function dotProduct(first, second) {
  return first[0] * second[0] + first[1] * second[1] + first[2] * second[2];
}

function crossProduct(first, second) {
  return [first[1] * second[2] - first[2] * second[1], first[2] * second[0] - first[0] * second[2], first[0] * second[1] - first[1] * second[0]];
}

/** The path as a dense polyline with its distance from the start and a twist-free frame (tangent, normal, binormal) at each sample. */
function sampleCurve(path, upAxis) {
  const points = [];
  for (let segment = 0; segment + 1 < path.length; segment++) {
    const before = path[Math.max(segment - 1, 0)];
    const after = path[Math.min(segment + 2, path.length - 1)];
    for (let sample = 0; sample < CURVE_SAMPLES_PER_SEGMENT; sample++) {
      points.push(catmullRom(before, path[segment], path[segment + 1], after, sample / CURVE_SAMPLES_PER_SEGMENT));
    }
  }
  points.push(path.at(-1));
  const distances = [0];
  for (let index = 1; index < points.length; index++) {
    distances.push(distances[index - 1] + Math.hypot(...points[index].map((value, axis) => value - points[index - 1][axis])));
  }
  if (!(distances.at(-1) > MINIMUM_SPAN)) throw invalidField('path', path, 'points that are apart, such as [[0, 0, 0], [0, 0, 2]]');
  const tangents = points.map((point, index) => {
    const ahead = points[Math.min(index + 1, points.length - 1)];
    const behind = points[Math.max(index - 1, 0)];
    const direction = ahead.map((value, axis) => value - behind[axis]);
    return Math.hypot(...direction) > 0 ? normalizedVector(direction) : [1, 0, 0];
  });
  const up = [0, 0, 0];
  up[upAxis] = 1;
  const frames = [];
  let normal = up;
  tangents.forEach((tangent, index) => {
    let candidate = normal.map((value, axis) => value - dotProduct(normal, tangent) * tangent[axis]);
    if (Math.hypot(...candidate) < 1e-6) {
      const other = [0, 0, 0];
      other[(upAxis + 1) % 3] = 1;
      candidate = other.map((value, axis) => value - dotProduct(other, tangent) * tangent[axis]);
    }
    normal = normalizedVector(candidate);
    frames.push({ tangent, normal, binormal: crossProduct(tangent, normal), point: points[index], distance: distances[index] });
  });
  return frames;
}

function frameAtDistance(frames, distance) {
  const last = frames.length - 1;
  if (distance <= 0) return { ...frames[0], along: distance };
  if (distance >= frames[last].distance) return { ...frames[last], along: distance - frames[last].distance };
  let low = 0;
  let high = last;
  while (high - low > 1) {
    const middle = (low + high) >> 1;
    if (frames[middle].distance <= distance) low = middle;
    else high = middle;
  }
  const span = frames[high].distance - frames[low].distance;
  const fraction = span > 0 ? (distance - frames[low].distance) / span : 0;
  const mix = (first, second) => first.map((value, axis) => value + (second[axis] - value) * fraction);
  const tangent = normalizedVector(mix(frames[low].tangent, frames[high].tangent));
  const normal = normalizedVector(mix(frames[low].normal, frames[high].normal));
  return { tangent, normal, binormal: crossProduct(tangent, normal), point: mix(frames[low].point, frames[high].point), along: 0 };
}

/**
 * Blender's Curve: the coordinate of each vertex along `axis` is a distance from the start of the path, and the other two
 * coordinates become offsets from the path in a twist-free frame. The path is a Catmull-Rom spline through `path`; past
 * either end the mesh continues along the end tangent.
 */
export function curveDeform(mesh, { path, axis }) {
  const axisIndex = AXIS_NAMES[axis];
  const frames = sampleCurve(path, (axisIndex + 1) % 3);
  const positions = new Float32Array(mesh.positions);
  for (let vertex = 0; vertex < mesh.vertexCount; vertex++) {
    const distance = mesh.positions[vertex * 3 + axisIndex];
    const acrossFirst = mesh.positions[vertex * 3 + (axisIndex + 1) % 3];
    const acrossSecond = mesh.positions[vertex * 3 + (axisIndex + 2) % 3];
    const frame = frameAtDistance(frames, distance);
    for (let component = 0; component < 3; component++) {
      positions[vertex * 3 + component] = frame.point[component] + frame.tangent[component] * frame.along
        + frame.normal[component] * acrossFirst + frame.binormal[component] * acrossSecond;
    }
  }
  return positions;
}

function checkedVector(value, index, label, finiteNumber) {
  if (!Array.isArray(value) || value.length !== 3) throw editField(index, label, value, 'an array of three numbers, such as [0, 1, 0]');
  return value.map(component => finiteNumber(component, index, label));
}

function normalizeLattice(edit, normalized, index, { finiteNumber }) {
  const divisions = editDefault(edit.divisions, [2, 2, 2]);
  if (!Array.isArray(divisions) || divisions.length !== 3) throw editField(index, 'divisions', divisions, `an array of three whole numbers from 2 to ${MAX_LATTICE_DIVISIONS}, such as [2, 2, 2]`);
  normalized.divisions = divisions.map(count => editInteger(count, index, 'divisions', 2, MAX_LATTICE_DIVISIONS));
  const moves = editDefault(edit.moves, []);
  if (!Array.isArray(moves) || moves.length > MAX_LATTICE_MOVES) throw editField(index, 'moves', moves, `a list of at most ${MAX_LATTICE_MOVES} moves, such as [{ "point": [0, 0, 0], "offset": [0, 0, 1] }]`, RangeError);
  normalized.moves = moves.map((move, moveIndex) => {
    if (!move || typeof move !== 'object' || Array.isArray(move)) throw editField(index, `moves[${moveIndex}]`, move, 'an object such as { "point": [0, 0, 0], "offset": [0, 0, 1] }');
    if (!Array.isArray(move.point) || move.point.length !== 3) throw editField(index, `moves[${moveIndex}].point`, move.point, 'three grid indices, such as [0, 1, 0]');
    const point = move.point.map((cell, axis) => editInteger(cell, index, `moves[${moveIndex}].point`, 0, normalized.divisions[axis] - 1));
    return { point, offset: checkedVector(move.offset, index, `moves[${moveIndex}].offset`, finiteNumber) };
  });
}

function normalizeCurve(edit, normalized, index, { finiteNumber }) {
  if (!Array.isArray(edit.path) || edit.path.length < 2 || edit.path.length > MAX_CURVE_POINTS) {
    throw editField(index, 'path', edit.path, `an array of 2 to ${MAX_CURVE_POINTS} points of three numbers, such as [[0, 0, 0], [0, 0, 2]]`);
  }
  normalized.path = edit.path.map(point => checkedVector(point, index, 'path', finiteNumber));
  normalized.axis = editDefault(edit.axis, 'x');
  editAxis(normalized.axis, index);
}

function normalizeHook(edit, normalized, index, { finiteNumber }) {
  normalized.center = checkedVector(editDefault(edit.center, [0, 0, 0]), index, 'center', finiteNumber);
  normalized.radius = edit.radius === undefined ? 1 : finiteNumber(edit.radius, index, 'radius', { minimum: 0, maximum: 1e4, exclusiveMinimum: true });
  normalized.translation = checkedVector(editDefault(edit.translation, [0, 0, 0]), index, 'translation', finiteNumber);
  normalized.strength = edit.strength === undefined ? 1 : finiteNumber(edit.strength, index, 'strength', { minimum: 0, maximum: 1 });
  normalized.falloff = editDefault(edit.falloff, 'smooth');
  if (!HOOK_FALLOFFS.includes(normalized.falloff)) throw editField(index, 'falloff', normalized.falloff, `one of ${HOOK_FALLOFFS.join(', ')}`);
}

function normalizeWave(edit, normalized, index, { finiteNumber }) {
  normalized.height = edit.height === undefined ? 0.5 : finiteNumber(edit.height, index, 'height', { minimum: -1e4, maximum: 1e4 });
  normalized.width = edit.width === undefined ? 1.5 : finiteNumber(edit.width, index, 'width', { minimum: 0, maximum: 1e4, exclusiveMinimum: true });
  normalized.narrowness = edit.narrowness === undefined ? 1.5 : finiteNumber(edit.narrowness, index, 'narrowness', { minimum: 0, maximum: 50 });
  normalized.speed = edit.speed === undefined ? 0.25 : finiteNumber(edit.speed, index, 'speed', { minimum: -1e4, maximum: 1e4 });
  normalized.time = edit.time === undefined ? 0 : finiteNumber(edit.time, index, 'time', { minimum: -1e6, maximum: 1e6 });
  normalized.timeOffset = edit.timeOffset === undefined ? 0 : finiteNumber(edit.timeOffset, index, 'timeOffset', { minimum: -1e6, maximum: 1e6 });
  const start = editDefault(edit.start, [0, 0]);
  if (!Array.isArray(start) || start.length !== 2) throw editField(index, 'start', start, 'an array of two numbers, x and y, such as [0, 0]');
  normalized.start = start.map(value => finiteNumber(value, index, 'start'));
  normalized.cyclic = editDefault(edit.cyclic, true);
  normalized.normal = editDefault(edit.normal, false);
  editBoolean(normalized.cyclic, index, 'cyclic');
  editBoolean(normalized.normal, index, 'normal');
  normalized.axes = editDefault(edit.axes, 'xy');
  if (!WAVE_AXES.includes(normalized.axes)) throw editField(index, 'axes', normalized.axes, `one of ${WAVE_AXES.join(', ')}`);
}

function normalizeSmoothLaplacian(edit, normalized, index, { finiteNumber }) {
  normalized.factor = edit.factor === undefined ? 0.5 : finiteNumber(edit.factor, index, 'factor', { minimum: 0, maximum: 1, exclusiveMinimum: true });
  normalized.iterations = edit.iterations === undefined ? 1 : editInteger(edit.iterations, index, 'iterations', 1, MAX_LAPLACIAN_ITERATIONS);
  normalized.preserveVolume = editDefault(edit.preserveVolume, true);
  normalized.pinBoundary = editDefault(edit.pinBoundary, true);
  editBoolean(normalized.preserveVolume, index, 'preserveVolume');
  editBoolean(normalized.pinBoundary, index, 'pinBoundary');
  if (edit.group === undefined) return;
  if (typeof edit.group !== 'string' || !GROUP_NAME_PATTERN.test(edit.group)) {
    throw editField(index, 'group', edit.group, '1 to 48 letters, digits, dots, dashes or underscores naming a vertex group, such as "mask"');
  }
  normalized.group = edit.group;
}

function normalizeWarp(edit, normalized, index, { finiteNumber }) {
  normalized.from = checkedVector(edit.from, index, 'from', finiteNumber);
  normalized.to = checkedVector(edit.to, index, 'to', finiteNumber);
  normalized.radius = edit.radius === undefined ? 1 : finiteNumber(edit.radius, index, 'radius', { minimum: 0, maximum: 1e4, exclusiveMinimum: true });
  normalized.curve = editDefault(edit.curve, 'smooth');
  if (!HOOK_FALLOFFS.includes(normalized.curve)) throw editField(index, 'curve', normalized.curve, `one of ${HOOK_FALLOFFS.join(', ')}`);
  normalized.twist = edit.twist === undefined ? 0 : finiteNumber(edit.twist, index, 'twist', { minimum: -3600, maximum: 3600 });
  const apart = Math.hypot(...normalized.to.map((value, axis) => value - normalized.from[axis])) > MINIMUM_SPAN;
  if (normalized.twist !== 0 && !apart) throw editField(index, 'twist', edit.twist, 'left out, or with "to" apart from "from", because the twist turns about the axis between them');
}

const NORMALIZERS = Object.freeze({ lattice: normalizeLattice, curve: normalizeCurve, hook: normalizeHook, wave: normalizeWave, smooth_laplacian: normalizeSmoothLaplacian, warp: normalizeWarp });
const DEFORMERS = Object.freeze({ lattice: latticeDeform, curve: curveDeform, hook: hookDeform, wave: waveDeform, smooth_laplacian: smoothLaplacianDeform, warp: warpDeform });

export const isDeformModifier = operation => Object.hasOwn(DEFORMERS, operation);

export function normalizeDeformEdit(edit, normalized, index, helpers) {
  NORMALIZERS[edit.op](edit, normalized, index, helpers);
}

export function runDeformEdit(mesh, edit) {
  return { mesh: withPositions(mesh, DEFORMERS[edit.op](mesh, edit)), result: {} };
}