Skip to content

3D engine that AI agents drive

21.2 KB
Raw Blame
import { createMeshData, deriveEdges, DOMAINS, meshBounds, TAG_PREFIX } from './mesh-data.js';
import { faceNormals } from './mesh-normals.js';
import { cornerCycles, cornerFaces, edgeCornerTable } from './mesh-topology.js';
import { requireFiniteInRange } from './modeling-limits.js';

const NORMAL_SPLIT_TOLERANCE = 1e-4;
const AXIS_TAGS = Object.freeze([
  { name: 'right', axis: 0, sign: 1, side: true },
  { name: 'left', axis: 0, sign: -1, side: true },
  { name: 'top', axis: 1, sign: 1, side: false },
  { name: 'bottom', axis: 1, sign: -1, side: false },
  { name: 'front', axis: 2, sign: 1, side: true },
  { name: 'back', axis: 2, sign: -1, side: true },
]);

function spatialHash(cellX, cellY, cellZ, mask) {
  return (Math.imul(cellX, 73856093) ^ Math.imul(cellY, 19349663) ^ Math.imul(cellZ, 83492791)) & mask;
}

/**
 * Map each input vertex to a welded vertex. Vertices closer than `tolerance` merge into the first one seen.
 * Uses a hashed uniform grid with cell size equal to the tolerance, so each lookup checks 27 cells.
 */
export function weldVertices(positions, tolerance) {
  const count = positions.length / 3;
  const weldMap = new Uint32Array(count);
  const representatives = [];
  let tableSize = 1;
  while (tableSize < count * 2) tableSize *= 2;
  const mask = tableSize - 1;
  const bucketHead = new Int32Array(tableSize).fill(-1);
  const bucketNext = new Int32Array(count).fill(-1);
  const cellSize = tolerance > 0 ? tolerance : 1;
  const squaredTolerance = tolerance * tolerance;
  const searchRadius = tolerance > 0 ? 1 : 0;
  for (let vertex = 0; vertex < count; vertex++) {
    const x = positions[vertex * 3];
    const y = positions[vertex * 3 + 1];
    const z = positions[vertex * 3 + 2];
    const cellX = Math.floor(x / cellSize);
    const cellY = Math.floor(y / cellSize);
    const cellZ = Math.floor(z / cellSize);
    let match = -1;
    for (let offsetX = -searchRadius; offsetX <= searchRadius && match === -1; offsetX++) {
      for (let offsetY = -searchRadius; offsetY <= searchRadius && match === -1; offsetY++) {
        for (let offsetZ = -searchRadius; offsetZ <= searchRadius && match === -1; offsetZ++) {
          let candidate = bucketHead[spatialHash(cellX + offsetX, cellY + offsetY, cellZ + offsetZ, mask)];
          while (candidate !== -1) {
            const source = representatives[candidate];
            const deltaX = positions[source * 3] - x;
            const deltaY = positions[source * 3 + 1] - y;
            const deltaZ = positions[source * 3 + 2] - z;
            if (deltaX * deltaX + deltaY * deltaY + deltaZ * deltaZ <= squaredTolerance) {
              match = candidate;
              break;
            }
            candidate = bucketNext[candidate];
          }
        }
      }
    }
    if (match === -1) {
      match = representatives.length;
      representatives.push(vertex);
      const bucket = spatialHash(cellX, cellY, cellZ, mask);
      bucketNext[match] = bucketHead[bucket];
      bucketHead[bucket] = match;
    }
    weldMap[vertex] = match;
  }
  return { weldMap, representatives };
}

/**
 * Rebuild a mesh from faces described by source corners. Corner attributes follow their source corner, face
 * attributes their source face, and edge attributes are kept for edges that join the same vertex pair as before.
 */
export function rebuildFromCorners(source, faceOffsets, sourceCorners, sourceFaces) {
  const cornerVertices = new Uint32Array(sourceCorners.length);
  for (let corner = 0; corner < sourceCorners.length; corner++) cornerVertices[corner] = source.cornerVertices[sourceCorners[corner]];
  const edges = deriveEdges(source.vertexCount, faceOffsets, cornerVertices);
  const attributes = { point: { ...source.attributes.point }, edge: {}, face: {}, corner: {} };
  for (const [name, attribute] of Object.entries(source.attributes.corner)) {
    attributes.corner[name] = gatherAttribute(attribute, sourceCorners);
  }
  for (const [name, attribute] of Object.entries(source.attributes.face)) {
    attributes.face[name] = gatherAttribute(attribute, sourceFaces);
  }
  const edgeAttributes = Object.entries(source.attributes.edge);
  if (edgeAttributes.length) {
    const sourceEdgeOfNewEdge = new Int32Array(edges.edgeCount).fill(-1);
    const sourceEdges = deriveEdgeLookup(source);
    for (let edge = 0; edge < edges.edgeCount; edge++) {
      sourceEdgeOfNewEdge[edge] = sourceEdges(edges.edgeVertices[edge * 2], edges.edgeVertices[edge * 2 + 1]);
    }
    for (const [name, attribute] of edgeAttributes) {
      const data = new attribute.data.constructor(edges.edgeCount * attribute.size);
      for (let edge = 0; edge < edges.edgeCount; edge++) {
        const sourceEdge = sourceEdgeOfNewEdge[edge];
        if (sourceEdge === -1) continue;
        for (let component = 0; component < attribute.size; component++) {
          data[edge * attribute.size + component] = attribute.data[sourceEdge * attribute.size + component];
        }
      }
      attributes.edge[name] = { data, size: attribute.size };
    }
  }
  return createMeshData({
    positions: source.positions, faceOffsets, cornerVertices,
    edgeVertices: edges.edgeVertices, cornerEdges: edges.cornerEdges, attributes,
  });
}

function gatherAttribute(attribute, sourceIndices) {
  const data = new attribute.data.constructor(sourceIndices.length * attribute.size);
  for (let index = 0; index < sourceIndices.length; index++) {
    for (let component = 0; component < attribute.size; component++) {
      data[index * attribute.size + component] = attribute.data[sourceIndices[index] * attribute.size + component];
    }
  }
  return { data, size: attribute.size };
}

/** Lookup function from a vertex pair to the source edge index, built from per-vertex edge lists. */
function deriveEdgeLookup(mesh) {
  const firstEdge = new Int32Array(mesh.vertexCount).fill(-1);
  const nextEdge = new Int32Array(mesh.edgeCount).fill(-1);
  for (let edge = 0; edge < mesh.edgeCount; edge++) {
    const low = Math.min(mesh.edgeVertices[edge * 2], mesh.edgeVertices[edge * 2 + 1]);
    nextEdge[edge] = firstEdge[low];
    firstEdge[low] = edge;
  }
  return (first, second) => {
    const low = Math.min(first, second);
    const high = Math.max(first, second);
    let edge = firstEdge[low];
    while (edge !== -1) {
      if (Math.max(mesh.edgeVertices[edge * 2], mesh.edgeVertices[edge * 2 + 1]) === high) return edge;
      edge = nextEdge[edge];
    }
    return -1;
  };
}

function attributeList(domainAttributes) {
  return Object.values(domainAttributes);
}

function sameValues(attributes, first, second) {
  for (const attribute of attributes) {
    const size = attribute.size;
    const data = attribute.data;
    for (let component = 0; component < size; component++) {
      if (data[first * size + component] !== data[second * size + component]) return false;
    }
  }
  return true;
}

const cornerScratch = new Float64Array(12);

/**
 * Sum over the four corners of |corner angle - 90 degrees|, or -1 when the quad is not convex
 * (a corner turns against the others). Vertices are firstVertex to fourthVertex in winding order.
 */
function quadCornerAngleError(positions, firstVertex, secondVertex, thirdVertex, fourthVertex) {
  const quad = [firstVertex, secondVertex, thirdVertex, fourthVertex];
  let error = 0;
  for (let index = 0; index < 4; index++) {
    const previous = quad[(index + 3) & 3] * 3;
    const current = quad[index] * 3;
    const next = quad[(index + 1) & 3] * 3;
    const firstX = positions[previous] - positions[current];
    const firstY = positions[previous + 1] - positions[current + 1];
    const firstZ = positions[previous + 2] - positions[current + 2];
    const secondX = positions[next] - positions[current];
    const secondY = positions[next + 1] - positions[current + 1];
    const secondZ = positions[next + 2] - positions[current + 2];
    const crossX = secondY * firstZ - secondZ * firstY;
    const crossY = secondZ * firstX - secondX * firstZ;
    const crossZ = secondX * firstY - secondY * firstX;
    cornerScratch[index * 3] = crossX;
    cornerScratch[index * 3 + 1] = crossY;
    cornerScratch[index * 3 + 2] = crossZ;
    const crossLength = Math.sqrt(crossX * crossX + crossY * crossY + crossZ * crossZ);
    const angle = Math.atan2(crossLength, firstX * secondX + firstY * secondY + firstZ * secondZ);
    error += Math.abs(angle - Math.PI / 2);
  }
  for (let index = 1; index < 4; index++) {
    const dot = cornerScratch[0] * cornerScratch[index * 3] + cornerScratch[1] * cornerScratch[index * 3 + 1] +
      cornerScratch[2] * cornerScratch[index * 3 + 2];
    if (dot <= 0) return -1;
  }
  return error;
}

const SORT_BUCKETS = 65536;
const MAX_QUAD_ERROR = 2 * Math.PI;

/** Candidate order by error, using a counting sort on quantized errors (ties keep edge order). */
function orderByError(errors, count) {
  const bucketOfCandidate = new Uint32Array(count);
  const bucketStart = new Uint32Array(SORT_BUCKETS + 1);
  for (let candidate = 0; candidate < count; candidate++) {
    const bucket = Math.min(SORT_BUCKETS - 1, Math.floor(errors[candidate] / MAX_QUAD_ERROR * SORT_BUCKETS));
    bucketOfCandidate[candidate] = bucket;
    bucketStart[bucket + 1]++;
  }
  for (let bucket = 0; bucket < SORT_BUCKETS; bucket++) bucketStart[bucket + 1] += bucketStart[bucket];
  const order = new Uint32Array(count);
  for (let candidate = 0; candidate < count; candidate++) {
    order[bucketStart[bucketOfCandidate[candidate]]] = candidate;
    bucketStart[bucketOfCandidate[candidate]]++;
  }
  return order;
}

/**
 * Join pairs of triangles into quads, as Blender's "Triangles to Quads": only across smooth, manifold edges whose two
 * triangles are within maxAngle of coplanar, form a convex quad, and agree on every corner and face attribute.
 * Best-shaped pairs (corners closest to right angles) join first.
 */
export function joinTriangles(mesh, { maxAngle = Math.PI / 180 } = {}) {
  requireFiniteInRange('joinTriangles', 'maxAngle', maxAngle, 0, Math.PI);
  const { normals } = faceNormals(mesh);
  const table = edgeCornerTable(mesh);
  const { nextCorner } = cornerCycles(mesh);
  const facesOfCorners = cornerFaces(mesh);
  const sharp = mesh.attributes.edge.sharp?.data;
  const cornerAttributes = attributeList(mesh.attributes.corner);
  const faceAttributes = attributeList(mesh.attributes.face);
  const cosineLimit = Math.cos(maxAngle);
  const vertices = mesh.cornerVertices;
  // Each candidate stores its error and its first corner; the other three corners follow from the topology.
  const candidateErrors = new Float64Array(mesh.edgeCount);
  const candidateFirstCorner = new Uint32Array(mesh.edgeCount);
  const candidateSecondCorner = new Uint32Array(mesh.edgeCount);
  let candidateCount = 0;
  for (let edge = 0; edge < mesh.edgeCount; edge++) {
    const offset = table.edgeOffsets[edge];
    if (table.edgeOffsets[edge + 1] - offset !== 2) continue;
    if (sharp && sharp[edge]) continue;
    const first = table.edgeCorners[offset];
    const second = table.edgeCorners[offset + 1];
    const firstFace = facesOfCorners[first];
    const secondFace = facesOfCorners[second];
    if (mesh.faceOffsets[firstFace + 1] - mesh.faceOffsets[firstFace] !== 3) continue;
    if (mesh.faceOffsets[secondFace + 1] - mesh.faceOffsets[secondFace] !== 3) continue;
    if (vertices[first] === vertices[second]) continue;
    const cosine = normals[firstFace * 3] * normals[secondFace * 3] + normals[firstFace * 3 + 1] * normals[secondFace * 3 + 1] +
      normals[firstFace * 3 + 2] * normals[secondFace * 3 + 2];
    if (cosine < cosineLimit) continue;
    if (!sameValues(faceAttributes, firstFace, secondFace)) continue;
    // first runs a->b in its face, second runs b->a. The quad is a, (second's opposite), b, (first's opposite).
    const firstNext = nextCorner[first];
    const firstOpposite = nextCorner[firstNext];
    const secondNext = nextCorner[second];
    const secondOpposite = nextCorner[secondNext];
    if (!sameValues(cornerAttributes, first, secondNext) || !sameValues(cornerAttributes, firstNext, second)) continue;
    if (vertices[firstOpposite] === vertices[secondOpposite]) continue;
    const error = quadCornerAngleError(mesh.positions, vertices[first], vertices[secondOpposite], vertices[firstNext], vertices[firstOpposite]);
    if (error < 0) continue;
    candidateErrors[candidateCount] = error;
    candidateFirstCorner[candidateCount] = first;
    candidateSecondCorner[candidateCount] = second;
    candidateCount++;
  }
  if (!candidateCount) return mesh;
  const order = orderByError(candidateErrors, candidateCount);
  const joined = new Uint8Array(mesh.faceCount);
  // For the lower-numbered face of each joined pair: the first corner of its quad; the partner face is skipped.
  const quadFirstCorner = new Int32Array(mesh.faceCount).fill(-1);
  const quadSecondCorner = new Uint32Array(mesh.faceCount);
  let joinedPairs = 0;
  for (let index = 0; index < candidateCount; index++) {
    const candidate = order[index];
    const first = candidateFirstCorner[candidate];
    const second = candidateSecondCorner[candidate];
    const firstFace = facesOfCorners[first];
    const secondFace = facesOfCorners[second];
    if (joined[firstFace] || joined[secondFace]) continue;
    joined[firstFace] = 1;
    joined[secondFace] = 1;
    const keeper = Math.min(firstFace, secondFace);
    quadFirstCorner[keeper] = first;
    quadSecondCorner[keeper] = second;
    joinedPairs++;
  }
  const faceCount = mesh.faceCount - joinedPairs;
  const faceOffsets = new Uint32Array(faceCount + 1);
  const sourceCorners = new Uint32Array(mesh.cornerCount - joinedPairs * 2);
  const sourceFaces = new Uint32Array(faceCount);
  let outputFace = 0;
  let outputCorner = 0;
  for (let face = 0; face < mesh.faceCount; face++) {
    const first = quadFirstCorner[face];
    if (joined[face] && first === -1) continue;
    if (first !== -1) {
      const firstNext = nextCorner[first];
      sourceCorners[outputCorner] = first;
      sourceCorners[outputCorner + 1] = nextCorner[nextCorner[quadSecondCorner[face]]];
      sourceCorners[outputCorner + 2] = firstNext;
      sourceCorners[outputCorner + 3] = nextCorner[firstNext];
      outputCorner += 4;
    } else {
      for (let corner = mesh.faceOffsets[face]; corner < mesh.faceOffsets[face + 1]; corner++) {
        sourceCorners[outputCorner] = corner;
        outputCorner++;
      }
    }
    sourceFaces[outputFace] = face;
    outputFace++;
    faceOffsets[outputFace] = outputCorner;
  }
  return rebuildFromCorners(mesh, faceOffsets, sourceCorners, sourceFaces);
}

/**
 * Tag faces by the axis their normal points along (within 45 degrees): top, bottom, right (+X), left (-X),
 * front (+Z), back (-Z); the four horizontal directions also get "side". Existing tags are kept.
 */
export function tagFacesByAxis(mesh) {
  const { normals } = faceNormals(mesh);
  const tagData = new Map();
  const ensure = name => {
    if (!tagData.has(name)) tagData.set(name, mesh.attributes.face[TAG_PREFIX + name]?.data.slice() ?? new Uint8Array(mesh.faceCount));
    return tagData.get(name);
  };
  const threshold = Math.SQRT1_2;
  for (let face = 0; face < mesh.faceCount; face++) {
    for (const tag of AXIS_TAGS) {
      if (normals[face * 3 + tag.axis] * tag.sign < threshold) continue;
      ensure(tag.name)[face] = 1;
      if (tag.side) ensure('side')[face] = 1;
    }
  }
  return withFaceAttributes(mesh, Object.fromEntries([...tagData].map(([name, data]) => [TAG_PREFIX + name, { data, size: 1 }])));
}

/** Copy of a mesh with face attributes added or replaced; topology and other arrays are shared. */
export function withFaceAttributes(mesh, faceAttributes) {
  const attributes = {};
  for (const domain of DOMAINS) attributes[domain] = { ...mesh.attributes[domain] };
  Object.assign(attributes.face, faceAttributes);
  return createMeshData({
    positions: mesh.positions, faceOffsets: mesh.faceOffsets, cornerVertices: mesh.cornerVertices,
    edgeVertices: mesh.edgeVertices, cornerEdges: mesh.cornerEdges, attributes,
  });
}

function differentNormals(normals, first, second) {
  return Math.abs(normals[first * 3] - normals[second * 3]) > NORMAL_SPLIT_TOLERANCE ||
    Math.abs(normals[first * 3 + 1] - normals[second * 3 + 1]) > NORMAL_SPLIT_TOLERANCE ||
    Math.abs(normals[first * 3 + 2] - normals[second * 3 + 2]) > NORMAL_SPLIT_TOLERANCE;
}

/** Whether the geometry carries a per-vertex array; throws when it does but its length does not fit the vertices. */
function hasVertexAttribute(geometry, field, expectedLength) {
  const data = geometry[field];
  if (data === undefined || data === null) return false;
  if (!(data instanceof Float32Array) || data.length !== expectedLength) {
    throw new RangeError(`Geometry ${field} must be a Float32Array of ${expectedLength} values (one entry per position), not ${data?.length ?? typeof data}. Fix the array or remove ${field}.`);
  }
  return true;
}

/**
 * Convert renderer geometry (indexed triangles with seam-split vertices) into a polygon mesh.
 * Coincident vertices weld within `weld` (default: 1e-6 of the bounds diagonal); UVs and colours become corner
 * attributes; edges where the input normals were split become "sharp" edges so extraction keeps the hard edges.
 * With `quads` (default true), flat triangle pairs join into quads. With `tags: 'axis'` (default), faces are tagged
 * top, bottom, side, right, left, front and back.
 */
export function meshFromGeometry(geometry, { weld, quads = true, tags = 'axis' } = {}) {
  const { positions, normals, indices } = geometry ?? {};
  if (!(positions instanceof Float32Array) || positions.length % 3 !== 0 || positions.length === 0) throw new TypeError('Geometry needs Float32 positions.');
  if (!(indices instanceof Uint32Array) || indices.length % 3 !== 0 || indices.length === 0) throw new TypeError('Geometry needs Uint32 triangle indices.');
  const sourceCount = positions.length / 3;
  for (const index of indices) if (index >= sourceCount) throw new RangeError('Geometry index exceeds the vertex count.');
  if (tags !== 'axis' && tags !== 'none') throw new RangeError('tags must be "axis" or "none".');
  let tolerance = weld;
  if (tolerance === undefined) {
    const sourceBounds = meshBounds({ positions });
    tolerance = Math.hypot(...sourceBounds.max.map((value, axis) => value - sourceBounds.min[axis])) * 1e-6;
  }
  if (!Number.isFinite(tolerance) || tolerance < 0) throw new RangeError('weld must be a nonnegative distance.');
  const { weldMap, representatives } = weldVertices(positions, tolerance);
  const weldedPositions = new Float32Array(representatives.length * 3);
  for (let vertex = 0; vertex < representatives.length; vertex++) {
    weldedPositions.set(positions.subarray(representatives[vertex] * 3, representatives[vertex] * 3 + 3), vertex * 3);
  }
  const keptTriangles = [];
  for (let triangle = 0; triangle < indices.length / 3; triangle++) {
    const first = weldMap[indices[triangle * 3]];
    const second = weldMap[indices[triangle * 3 + 1]];
    const third = weldMap[indices[triangle * 3 + 2]];
    if (first !== second && second !== third && third !== first) keptTriangles.push(triangle);
  }
  if (!keptTriangles.length) throw new RangeError('Every triangle collapses after welding. Reduce weld.');
  const faceCount = keptTriangles.length;
  const faceOffsets = new Uint32Array(faceCount + 1);
  const cornerVertices = new Uint32Array(faceCount * 3);
  const cornerSource = new Uint32Array(faceCount * 3);
  for (let face = 0; face < faceCount; face++) {
    faceOffsets[face + 1] = (face + 1) * 3;
    for (let corner = 0; corner < 3; corner++) {
      const source = indices[keptTriangles[face] * 3 + corner];
      cornerSource[face * 3 + corner] = source;
      cornerVertices[face * 3 + corner] = weldMap[source];
    }
  }
  const edges = deriveEdges(representatives.length, faceOffsets, cornerVertices);
  const cornerAttributes = {};
  if (hasVertexAttribute(geometry, 'uvs', sourceCount * 2)) {
    cornerAttributes.uv = gatherAttribute({ data: geometry.uvs, size: 2 }, cornerSource);
  }
  if (hasVertexAttribute(geometry, 'colors', sourceCount * 3)) {
    cornerAttributes.color = gatherAttribute({ data: geometry.colors, size: 3 }, cornerSource);
  }
  const edgeAttributes = {};
  if (normals instanceof Float32Array && normals.length === positions.length) {
    const sharp = new Uint8Array(edges.edgeCount);
    const probe = createMeshData({ positions: weldedPositions, faceOffsets, cornerVertices, edgeVertices: edges.edgeVertices, cornerEdges: edges.cornerEdges });
    const table = edgeCornerTable(probe);
    const { nextCorner } = cornerCycles(probe);
    for (let edge = 0; edge < edges.edgeCount; edge++) {
      const start = table.edgeOffsets[edge];
      if (table.edgeOffsets[edge + 1] - start !== 2) continue;
      const first = table.edgeCorners[start];
      const second = table.edgeCorners[start + 1];
      // Opposite winding: first's start vertex is second's end vertex.
      const pairs = [[first, nextCorner[second]], [nextCorner[first], second]];
      if (pairs.some(([left, right]) => differentNormals(normals, cornerSource[left], cornerSource[right]))) sharp[edge] = 1;
    }
    edgeAttributes.sharp = { data: sharp, size: 1 };
  }
  let mesh = createMeshData({
    positions: weldedPositions, faceOffsets, cornerVertices,
    edgeVertices: edges.edgeVertices, cornerEdges: edges.cornerEdges,
    attributes: { corner: cornerAttributes, edge: edgeAttributes },
  });
  if (quads) mesh = joinTriangles(mesh);
  if (tags === 'axis') mesh = tagFacesByAxis(mesh);
  return mesh;
}