Skip to content

3D engine that AI agents drive

15.9 KB
Raw Blame
import { placeCellVertices, quadsAroundEdges, splitSaddleVertices } from './surface-nets.js';

// The sdf geometry: a tree of signed-distance primitives and operations, sampled on a bounded grid and meshed by surface
// nets. Distances are negative inside. Everything is plain arithmetic in a fixed order, so the same recipe gives the same bytes.

export const SDF_LIMITS = Object.freeze({ minResolution: 4, maxResolution: 128, defaultResolution: 32, maxNodes: 64, maxDepth: 8, maxChildren: 16 });
const PADDING_VOXELS = 2;
const SADDLE_FIX_HINT = 'Pass a different resolution, or move the parts so they overlap instead of touching at an edge.';
const PRIMITIVE_FIELDS = {
  sphere: ['radius'],
  box: ['size'],
  roundBox: ['size', 'radius'],
  capsule: ['radius', 'height'],
  cylinder: ['radius', 'height'],
  torus: ['radius', 'tubeRadius'],
};
const OPERATIONS = ['union', 'subtract', 'intersect', 'offset'];
const PLACEMENT_FIELDS = ['position', 'rotation', 'scale'];

function fail(path, value, expected) {
  const shown = typeof value === 'object' ? JSON.stringify(value) : String(value);
  return new RangeError(`${path} is ${shown}; pass ${expected}.`);
}

function positiveNumber(node, field, fallback, path) {
  const value = node[field] ?? fallback;
  if (!Number.isFinite(value) || value <= 0) throw fail(`${path}.${field}`, value, 'a positive number');
  return value;
}

function vectorOf(value, fallback, path, { positive = false } = {}) {
  const vector = value ?? fallback;
  const valid = Array.isArray(vector) && vector.length === 3 && [...vector].every(component => Number.isFinite(component) && (!positive || component > 0));
  if (!valid) throw fail(path, vector, positive ? 'three positive numbers, such as [1, 1, 1]' : 'three numbers, such as [0, 0, 0]');
  return vector;
}

function checkKeys(node, allowed, path) {
  for (const key of Object.keys(node)) {
    if (!allowed.includes(key)) throw fail(`${path}.${key}`, node[key], `one of ${allowed.join(', ')}; remove "${key}"`);
  }
}

// Rotation by Euler angles in radians: about X first, then Y, then Z. Stored as the 3x3 matrix, row by row.
function rotationMatrix([x, y, z]) {
  const cosX = Math.cos(x);
  const sinX = Math.sin(x);
  const cosY = Math.cos(y);
  const sinY = Math.sin(y);
  const cosZ = Math.cos(z);
  const sinZ = Math.sin(z);
  return [
    cosZ * cosY, cosZ * sinY * sinX - sinZ * cosX, cosZ * sinY * cosX + sinZ * sinX,
    sinZ * cosY, sinZ * sinY * sinX + cosZ * cosX, sinZ * sinY * cosX - cosZ * sinX,
    -sinY, cosY * sinX, cosY * cosX,
  ];
}

function length2(first, second) {
  return Math.sqrt(first * first + second * second);
}

function length3(first, second, third) {
  return Math.sqrt(first * first + second * second + third * third);
}

function boxDistance(x, y, z, half) {
  const qx = Math.abs(x) - half[0];
  const qy = Math.abs(y) - half[1];
  const qz = Math.abs(z) - half[2];
  return length3(Math.max(qx, 0), Math.max(qy, 0), Math.max(qz, 0)) + Math.min(Math.max(qx, qy, qz), 0);
}

// Local distance function and half extents of each primitive; capsule, cylinder and torus stand along Y.
function primitiveShape(node, path) {
  switch (node.shape) {
    case 'sphere': {
      const radius = positiveNumber(node, 'radius', 0.5, path);
      return { half: [radius, radius, radius], distance: (x, y, z) => length3(x, y, z) - radius };
    }
    case 'box': {
      const size = vectorOf(node.size, [1, 1, 1], `${path}.size`, { positive: true });
      const half = size.map(value => value / 2);
      return { half, distance: (x, y, z) => boxDistance(x, y, z, half) };
    }
    case 'roundBox': {
      const size = vectorOf(node.size, [1, 1, 1], `${path}.size`, { positive: true });
      const radius = node.radius ?? 0.1;
      if (!Number.isFinite(radius) || radius < 0 || radius > Math.min(...size) / 2) {
        throw fail(`${path}.radius`, radius, `a number from 0 to half the smallest size, ${Math.min(...size) / 2}`);
      }
      const half = size.map(value => value / 2);
      const inner = half.map(value => value - radius);
      return { half, distance: (x, y, z) => boxDistance(x, y, z, inner) - radius };
    }
    case 'capsule': {
      const radius = positiveNumber(node, 'radius', 0.25, path);
      const halfSegment = positiveNumber(node, 'height', 0.5, path) / 2;
      return {
        half: [radius, halfSegment + radius, radius],
        distance: (x, y, z) => length3(x, y - Math.max(-halfSegment, Math.min(halfSegment, y)), z) - radius,
      };
    }
    case 'cylinder': {
      const radius = positiveNumber(node, 'radius', 0.5, path);
      const halfHeight = positiveNumber(node, 'height', 1, path) / 2;
      return {
        half: [radius, halfHeight, radius],
        distance: (x, y, z) => {
          const radial = length2(x, z) - radius;
          const vertical = Math.abs(y) - halfHeight;
          return Math.min(Math.max(radial, vertical), 0) + length2(Math.max(radial, 0), Math.max(vertical, 0));
        },
      };
    }
    case 'torus': {
      const radius = positiveNumber(node, 'radius', 0.5, path);
      const tubeRadius = positiveNumber(node, 'tubeRadius', 0.15, path);
      return {
        half: [radius + tubeRadius, tubeRadius, radius + tubeRadius],
        distance: (x, y, z) => length2(length2(x, z) - radius, y) - tubeRadius,
      };
    }
    default:
      throw fail(`${path}.shape`, node.shape, `one of ${Object.keys(PRIMITIVE_FIELDS).join(', ')}`);
  }
}

function placedPrimitive(node, path) {
  checkKeys(node, ['shape', ...PRIMITIVE_FIELDS[node.shape] ?? [], ...PLACEMENT_FIELDS], path);
  const shape = primitiveShape(node, path);
  const position = vectorOf(node.position, [0, 0, 0], `${path}.position`);
  const rotation = vectorOf(node.rotation, [0, 0, 0], `${path}.rotation`);
  const scale = node.scale ?? 1;
  if (!Number.isFinite(scale) || scale <= 0) throw fail(`${path}.scale`, scale, 'one positive number; scale is uniform');
  const matrix = rotationMatrix(rotation);
  const inverseScale = 1 / scale;
  // The point goes into the shape's frame with the transpose of the rotation; the distance comes back multiplied by the scale.
  const distance = (x, y, z) => {
    const dx = x - position[0];
    const dy = y - position[1];
    const dz = z - position[2];
    const localX = (matrix[0] * dx + matrix[3] * dy + matrix[6] * dz) * inverseScale;
    const localY = (matrix[1] * dx + matrix[4] * dy + matrix[7] * dz) * inverseScale;
    const localZ = (matrix[2] * dx + matrix[5] * dy + matrix[8] * dz) * inverseScale;
    return shape.distance(localX, localY, localZ) * scale;
  };
  const reach = [0, 1, 2].map(row => scale * (Math.abs(matrix[row * 3]) * shape.half[0] + Math.abs(matrix[row * 3 + 1]) * shape.half[1] + Math.abs(matrix[row * 3 + 2]) * shape.half[2]));
  return {
    distance,
    bounds: { min: reach.map((value, axis) => position[axis] - value), max: reach.map((value, axis) => position[axis] + value) },
  };
}

// Polynomial smooth minimum: it lowers the plain minimum by at most smooth / 4, and equals it when smooth is 0.
function smoothMinimum(first, second, smooth) {
  if (smooth === 0) return Math.min(first, second);
  const blend = Math.max(smooth - Math.abs(first - second), 0) / smooth;
  return Math.min(first, second) - blend * blend * smooth / 4;
}

function combine(operation, smooth) {
  switch (operation) {
    case 'union': return (first, second) => smoothMinimum(first, second, smooth);
    case 'intersect': return (first, second) => -smoothMinimum(-first, -second, smooth);
    default: return (first, second) => -smoothMinimum(-first, second, smooth);
  }
}

function expandedBounds(bounds, amount) {
  return { min: bounds.min.map(value => value - amount), max: bounds.max.map(value => value + amount) };
}

function combinedBounds(operation, childBounds, slack, path) {
  if (operation === 'subtract') return childBounds[0];
  const pick = operation === 'union' ? [Math.min, Math.max] : [Math.max, Math.min];
  const bounds = {
    min: [0, 1, 2].map(axis => pick[0](...childBounds.map(child => child.min[axis]))),
    max: [0, 1, 2].map(axis => pick[1](...childBounds.map(child => child.max[axis]))),
  };
  if (operation === 'intersect' && bounds.min.some((value, axis) => value >= bounds.max[axis])) {
    throw fail(path, 'children that do not overlap', 'children whose shapes overlap, or use union');
  }
  return operation === 'union' ? expandedBounds(bounds, slack) : bounds;
}

function compileNode(node, path, depth, counter) {
  if (!node || typeof node !== 'object' || Array.isArray(node)) throw fail(path, node, `a primitive such as { "shape": "sphere", "radius": 0.5 } or an operation such as { "op": "union", "children": [...] }`);
  counter.count += 1;
  if (counter.count > SDF_LIMITS.maxNodes) throw fail(path, `more than ${SDF_LIMITS.maxNodes} nodes`, `at most ${SDF_LIMITS.maxNodes} primitives and operations in all`);
  if (depth > SDF_LIMITS.maxDepth) throw fail(path, `nesting deeper than ${SDF_LIMITS.maxDepth}`, `at most ${SDF_LIMITS.maxDepth} levels of operations`);
  if (node.shape !== undefined) {
    if (node.op !== undefined) throw fail(`${path}.op`, node.op, 'either shape or op, not both');
    return placedPrimitive(node, path);
  }
  if (!OPERATIONS.includes(node.op)) throw fail(`${path}.op`, node.op, `shape (${Object.keys(PRIMITIVE_FIELDS).join(', ')}) or op (${OPERATIONS.join(', ')})`);
  if (node.op === 'offset') return compileOffset(node, path, depth, counter);
  checkKeys(node, ['op', 'smooth', 'children'], path);
  const smooth = node.smooth ?? 0;
  if (!Number.isFinite(smooth) || smooth < 0) throw fail(`${path}.smooth`, smooth, 'a blend radius of 0 or more, in the units of the shapes');
  const children = node.children;
  if (!Array.isArray(children) || children.length < 2 || children.length > SDF_LIMITS.maxChildren) {
    throw fail(`${path}.children`, Array.isArray(children) ? `${children.length} children` : children, `2 to ${SDF_LIMITS.maxChildren} nodes`);
  }
  const compiled = Array.from(children, (child, index) => compileNode(child, `${path}.children[${index}]`, depth + 1, counter));
  const join = combine(node.op, smooth);
  const distance = (x, y, z) => {
    let result = compiled[0].distance(x, y, z);
    for (let index = 1; index < compiled.length; index++) result = join(result, compiled[index].distance(x, y, z));
    return result;
  };
  const slack = smooth / 4 * (compiled.length - 1);
  return { distance, bounds: combinedBounds(node.op, compiled.map(child => child.bounds), slack, path) };
}

function compileOffset(node, path, depth, counter) {
  checkKeys(node, ['op', 'distance', 'child'], path);
  if (!Number.isFinite(node.distance)) throw fail(`${path}.distance`, node.distance, 'a number: positive grows the shape, negative shrinks it');
  const child = compileNode(node.child, `${path}.child`, depth + 1, counter);
  const bounds = node.distance > 0 ? expandedBounds(child.bounds, node.distance) : child.bounds;
  return { distance: (x, y, z) => child.distance(x, y, z) - node.distance, bounds };
}

/** Validates an sdf geometry and returns its grid, without sampling it. */
export function planSdf(value) {
  const unknown = Object.keys(value).filter(key => !['id', 'type', 'root', 'resolution'].includes(key));
  if (unknown.length) throw fail(`sdf.${unknown[0]}`, value[unknown[0]], 'only root and resolution; remove it');
  const resolution = value.resolution ?? SDF_LIMITS.defaultResolution;
  if (!Number.isInteger(resolution) || resolution < SDF_LIMITS.minResolution || resolution > SDF_LIMITS.maxResolution) {
    throw fail('sdf.resolution', resolution, `a whole number of cells along the longest side, ${SDF_LIMITS.minResolution} to ${SDF_LIMITS.maxResolution}; the grid is capped at ${SDF_LIMITS.maxResolution ** 3} cells`);
  }
  return planDistanceField(compileNode(value.root, 'sdf.root', 0, { count: 0 }), resolution);
}

// Bounds past Float32 range or NaN make positions NaN, so the grid is refused instead.
function checkReach({ min, max }) {
  const reach = Math.max(...[...min, ...max].map(Math.abs));
  if (!(reach <= 1e38)) throw fail('sdf.root bounds', reach, 'values that keep the shape within 1e38');
}

/** The sampling grid of a compiled field { distance, bounds }: resolution cells along its longest side, plus padding. */
export function planDistanceField(root, resolution) {
  checkReach(root.bounds);
  const extent = root.bounds.max.map((high, axis) => high - root.bounds.min[axis]);
  const edge = Math.max(...extent) / resolution;
  const points = extent.map(length => Math.ceil(length / edge - 1e-9) + 1 + PADDING_VOXELS * 2);
  const origin = root.bounds.min.map(low => low - PADDING_VOXELS * edge);
  return { root, resolution, edge, points, origin, vertexEstimate: 8 * resolution * resolution };
}

/** The vertex count to reserve for an sdf geometry: validated, not sampled. Surfaces with more detail are checked after meshing. */
export function sdfVertexEstimate(value) {
  return planSdf(value).vertexEstimate;
}

function sampleGrid({ root, edge, points, origin }) {
  const [pointsX, pointsY, pointsZ] = points;
  const distances = new Float32Array(pointsX * pointsY * pointsZ);
  let index = 0;
  for (let z = 0; z < pointsZ; z++) {
    for (let y = 0; y < pointsY; y++) {
      for (let x = 0; x < pointsX; x++) {
        distances[index++] = root.distance(origin[0] + x * edge, origin[1] + y * edge, origin[2] + z * edge);
      }
    }
  }
  return distances;
}

function gradientAt(distance, x, y, z, step) {
  return [
    distance(x + step, y, z) - distance(x - step, y, z),
    distance(x, y + step, z) - distance(x, y - step, z),
    distance(x, y, z + step) - distance(x, y, z - step),
  ];
}

// Two triangles per quad, split along the shorter diagonal so thin quads do not fold.
function triangulate(quads, positions) {
  const indices = [];
  const gap = (first, second) => {
    const dx = positions[first * 3] - positions[second * 3];
    const dy = positions[first * 3 + 1] - positions[second * 3 + 1];
    const dz = positions[first * 3 + 2] - positions[second * 3 + 2];
    return dx * dx + dy * dy + dz * dz;
  };
  for (const [first, second, third, fourth] of quads) {
    if (gap(first, third) <= gap(second, fourth)) indices.push(first, second, third, first, third, fourth);
    else indices.push(first, second, fourth, second, third, fourth);
  }
  return Uint32Array.from(indices);
}

/** Mesh an sdf geometry: positions, normals from the field gradient, box-projected UVs and triangle indices. */
export function sdfGeometry(value) {
  return meshDistanceField(planSdf(value));
}

/** Mesh a planned field (planSdf or planDistanceField) with surface nets. */
export function meshDistanceField(plan) {
  const grid = { points: plan.points, edge: plan.edge };
  const distances = sampleGrid(plan);
  const { cellVertex, positions: cellPositions } = placeCellVertices(distances, grid, plan.origin);
  const insidePoints = [];
  const outsidePoints = [];
  const builtQuads = quadsAroundEdges(distances, grid, cellVertex, insidePoints, outsidePoints);
  const { quads, positions: separatedPositions } = splitSaddleVertices(builtQuads, insidePoints, cellPositions, outsidePoints, SADDLE_FIX_HINT);
  if (!quads.length) throw new RangeError('sdf has no surface: the shape is empty or smaller than a cell. Pass a larger resolution or check subtract and intersect children.');
  const positions = Float32Array.from(separatedPositions);
  const normals = new Float32Array(positions.length);
  const uvs = new Float32Array(positions.length / 3 * 2);
  for (let vertex = 0; vertex < positions.length / 3; vertex++) {
    const gradient = gradientAt(plan.root.distance, separatedPositions[vertex * 3], separatedPositions[vertex * 3 + 1], separatedPositions[vertex * 3 + 2], plan.normalStep ?? plan.edge * 0.5);
    normals.set(gradient, vertex * 3);
    const strongest = Math.abs(gradient[0]) >= Math.abs(gradient[1]) && Math.abs(gradient[0]) >= Math.abs(gradient[2]) ? 0 : Math.abs(gradient[1]) >= Math.abs(gradient[2]) ? 1 : 2;
    const [u, v] = [[1, 2], [0, 2], [0, 1]][strongest];
    uvs[vertex * 2] = separatedPositions[vertex * 3 + u];
    uvs[vertex * 2 + 1] = separatedPositions[vertex * 3 + v];
  }
  return { positions, normals, uvs, indices: triangulate(quads, positions) };
}