Skip to content

3D engine that AI agents drive

32.9 KB
Raw Blame
import { mat4, vec3 } from 'gl-matrix';
import { buildTriangleBvh, pointBoxDistance, rayBoxDistance, traverseBvhPairs, traverseTriangleBvh } from './triangle-bvh.js';
import { barycentricWeights, closestPointOnTriangle, intersectRayTriangle, readTriangle, triangleNormal, trianglesIntersect } from './triangle-math.js';

const records = new WeakMap();
const EPSILON = 1e-9;
const MINIMUM_ALTITUDE = 1e-8;
const INDEX_OPTIONS = new Set(['maxTriangles', 'maxVertices', 'memoryBudgetMiB', 'solid', 'maxValidationPairs']);
const PAIR_OPTIONS = new Set(['mode', 'maxTriangleTests']);
const NEAREST_OPTIONS = new Set(['maxDistance', 'maxTriangleTests']);
const PROJECT_OPTIONS = new Set(['origin', 'direction', 'maxDistance', 'maxTriangleTests']);
const DIRECTIONS = [[0, 0, 1], [1, 0.41421356237, 0.73205080757], [0.61803398875, 1, 0.27182818285], [0.17320508075, 0.44721359550, 1], [-1, 0.31622776602, 0.14142135624], [0.22360679775, -1, 0.70710678118]];

function createVector(x = 0, y = 0, z = 0) {
  return Float64Array.of(x, y, z);
}

// gl-matrix allocates Float32Array unless the caller supplies the output, which would lose precision here.
function createMatrix() {
  return mat4.identity(new Float64Array(16));
}

function optionsObject(options, fields) {
  if (!options || typeof options !== 'object' || Array.isArray(options)) throw new TypeError('Query options require an object.');
  for (const field of Object.keys(options)) if (!fields.has(field)) throw new TypeError(`Unsupported query option ${field}.`);
}

function integer(value, maximum, label) {
  if (!Number.isSafeInteger(value) || value < 1 || value > maximum) throw new RangeError(`${label} requires an integer within one and ${maximum}.`);
  return value;
}

function budget(maximum, label) {
  let tests = 0;
  return {
    charge() {
      tests++;
      if (tests > maximum) throw new RangeError(`${label} exhausted. Raise the query budget or reduce geometry detail.`);
    },
    get tests() { return tests; },
  };
}

function live(index) {
  const record = records.get(index);
  if (!record) throw new TypeError('Use an index from createMeshQueryIndex().');
  if (record.disposed) throw new Error('Mesh query index was disposed. Create a new index.');
  return record;
}

function isFloat32Triple(input) {
  return (Array.isArray(input) || ArrayBuffer.isView(input)) && input.length === 3 &&
    Array.from(input).every(value => typeof value === 'number' && Number.isFinite(value) && Number.isFinite(Math.fround(value)));
}

function transformPositions(positions, matrix) {
  const moved = new Float64Array(positions.length);
  const point = createVector();
  for (let offset = 0; offset < positions.length; offset += 3) {
    point[0] = positions[offset];
    point[1] = positions[offset + 1];
    point[2] = positions[offset + 2];
    vec3.transformMat4(point, point, matrix);
    moved.set(point, offset);
  }
  return moved;
}

function transformBounds(bounds, matrix) {
  const moved = Float64Array.of(Infinity, Infinity, Infinity, -Infinity, -Infinity, -Infinity);
  const corner = createVector();
  for (let mask = 0; mask < 8; mask++) {
    corner[0] = bounds[mask & 1 ? 3 : 0];
    corner[1] = bounds[mask & 2 ? 4 : 1];
    corner[2] = bounds[mask & 4 ? 5 : 2];
    vec3.transformMat4(corner, corner, matrix);
    for (let axis = 0; axis < 3; axis++) {
      moved[axis] = Math.min(moved[axis], corner[axis]);
      moved[3 + axis] = Math.max(moved[3 + axis], corner[axis]);
    }
  }
  return moved;
}

function boundsContainPoint(bounds, point) {
  for (let axis = 0; axis < 3; axis++) if (point[axis] < bounds[axis] || point[axis] > bounds[3 + axis]) return false;
  return true;
}

function boundsOverlap(first, second) {
  for (let axis = 0; axis < 3; axis++) if (first[axis] > second[3 + axis] || second[axis] > first[3 + axis]) return false;
  return true;
}

function transformDirection(direction, matrix) {
  return createVector(
    matrix[0] * direction[0] + matrix[4] * direction[1] + matrix[8] * direction[2],
    matrix[1] * direction[0] + matrix[5] * direction[1] + matrix[9] * direction[2],
    matrix[2] * direction[0] + matrix[6] * direction[1] + matrix[10] * direction[2],
  );
}

function rotationScaleNorm(matrix) {
  return Math.hypot(...[0, 1, 2, 4, 5, 6, 8, 9, 10].map(index => matrix[index]));
}

function maximumAbsolute(values) {
  return Math.max(...Array.from(values, Math.abs));
}

function castTriangles(first, second, secondToFirst, counter, visitor) {
  const secondPositions = transformPositions(second.positions, secondToFirst);
  const firstTriangle = new Float64Array(9);
  const secondTriangle = new Float64Array(9);
  return traverseBvhPairs(first.bvh, second.bvh, secondPositions, (firstId, secondId) => {
    counter.charge();
    readTriangle(first.positions, first.bvh.indices, firstId, firstTriangle);
    readTriangle(secondPositions, second.bvh.indices, secondId, secondTriangle);
    return visitor(firstTriangle, secondTriangle, firstId, secondId);
  });
}

function validateGeometry(geometry, maxVertices, maxTriangles) {
  if (!geometry || typeof geometry !== 'object') throw new TypeError('Mesh queries require geometry.');
  if (geometry.skinIndices !== undefined || geometry.skinWeights !== undefined || geometry.morphTargets !== undefined) {
    throw new RangeError('Mesh queries require static geometry without skinning or morph targets.');
  }
  const positions = geometry.positions;
  const indices = geometry.indices;
  if (!(positions instanceof Float32Array) || positions.length === 0 || positions.length % 3 !== 0) throw new TypeError('Query positions require nonempty Float32 XYZ vertices.');
  if (!(indices instanceof Uint32Array) || indices.length === 0 || indices.length % 3 !== 0) throw new TypeError('Query indices require nonempty Uint32 triangles.');
  if (positions.length / 3 > maxVertices || indices.length / 3 > maxTriangles) throw new RangeError('Geometry exceeds maxVertices or maxTriangles.');
  const low = [Infinity, Infinity, Infinity];
  const high = [-Infinity, -Infinity, -Infinity];
  for (let offset = 0; offset < positions.length; offset += 3) {
    for (let axis = 0; axis < 3; axis++) {
      const value = positions[offset + axis];
      if (!Number.isFinite(value)) throw new RangeError('Query positions must remain finite.');
      low[axis] = Math.min(low[axis], value);
      high[axis] = Math.max(high[axis], value);
    }
  }
  for (const index of indices) if (index >= positions.length / 3) throw new RangeError('Query index exceeds the vertex count.');
  const center = createVector(...low.map((value, axis) => (value + high[axis]) / 2));
  const scale = Math.max(...high.map((value, axis) => value - low[axis]));
  if (scale === 0) throw new RangeError('Query geometry has no drawable extent.');
  return { center, scale, minimumAltitude: minimumNormalizedAltitude(positions, indices, scale), vertexCount: positions.length / 3, triangleCount: indices.length / 3 };
}

// Shortest altitude of the triangle at indices[offset..offset + 3), in units of the geometry scale.
function normalizedAltitude(positions, indices, offset, scale) {
  const second = createVector();
  const third = createVector();
  const between = createVector();
  const cross = createVector();
  const firstOffset = indices[offset] * 3;
  for (let axis = 0; axis < 3; axis++) {
    second[axis] = (positions[indices[offset + 1] * 3 + axis] - positions[firstOffset + axis]) / scale;
    third[axis] = (positions[indices[offset + 2] * 3 + axis] - positions[firstOffset + axis]) / scale;
  }
  vec3.subtract(between, second, third);
  const longest = Math.max(vec3.length(second), vec3.length(third), vec3.length(between));
  vec3.cross(cross, second, third);
  return vec3.length(cross) / longest;
}

function minimumNormalizedAltitude(positions, indices, scale) {
  let minimumAltitude = Infinity;
  for (let offset = 0; offset < indices.length; offset += 3) {
    const altitude = normalizedAltitude(positions, indices, offset, scale);
    if (!Number.isFinite(altitude) || altitude <= MINIMUM_ALTITUDE) throw new RangeError('Query triangle is degenerate or below the normalized precision domain.');
    minimumAltitude = Math.min(minimumAltitude, altitude);
  }
  return minimumAltitude;
}

/**
 * The triangles a query index accepts: zero-area and sliver triangles make createMeshQueryIndex throw, and they cannot
 * be hit by a ray anyway.
 */
export function withoutDegenerateTriangles({ positions, indices }) {
  const low = [Infinity, Infinity, Infinity];
  const high = [-Infinity, -Infinity, -Infinity];
  for (let offset = 0; offset < positions.length; offset += 3) {
    for (let axis = 0; axis < 3; axis++) {
      low[axis] = Math.min(low[axis], positions[offset + axis]);
      high[axis] = Math.max(high[axis], positions[offset + axis]);
    }
  }
  const scale = Math.max(...high.map((value, axis) => value - low[axis]));
  const kept = [];
  for (let offset = 0; offset < indices.length; offset += 3) {
    const altitude = normalizedAltitude(positions, indices, offset, scale);
    if (Number.isFinite(altitude) && altitude > MINIMUM_ALTITUDE) kept.push(indices[offset], indices[offset + 1], indices[offset + 2]);
  }
  return { positions, indices: Uint32Array.from(kept) };
}

function topology(geometry) {
  const vertexIds = new Uint32Array(geometry.positions.length / 3);
  const vertices = new Map();
  for (let vertex = 0; vertex < vertexIds.length; vertex++) {
    const offset = vertex * 3;
    const key = Array.from(geometry.positions.subarray(offset, offset + 3), value => value === 0 ? 0 : value).join(',');
    if (!vertices.has(key)) vertices.set(key, vertices.size);
    vertexIds[vertex] = vertices.get(key);
  }
  const triangles = Uint32Array.from(geometry.indices, index => vertexIds[index]);
  const edges = new Map();
  const neighbors = Array.from({ length: triangles.length / 3 }, () => []);
  const incident = Array.from({ length: vertices.size }, () => []);
  for (let face = 0; face < triangles.length / 3; face++) {
    const ids = Array.from(triangles.subarray(face * 3, face * 3 + 3));
    for (let corner = 0; corner < 3; corner++) {
      const first = ids[corner];
      const second = ids[(corner + 1) % 3];
      incident[first].push(face);
      const key = `${Math.min(first, second)}:${Math.max(first, second)}`;
      if (!edges.has(key)) edges.set(key, []);
      edges.get(key).push({ first, second, face });
    }
  }
  for (const adjacent of edges.values()) {
    if (adjacent.length !== 2 || adjacent[0].first !== adjacent[1].second || adjacent[0].second !== adjacent[1].first) {
      throw new RangeError('Solid geometry requires closed oriented manifold edges after exact position welding.');
    }
    neighbors[adjacent[0].face].push(adjacent[1].face);
    neighbors[adjacent[1].face].push(adjacent[0].face);
  }
  const visited = new Set([0]);
  const stack = [0];
  while (stack.length) {
    for (const neighbor of neighbors[stack.pop()]) if (!visited.has(neighbor)) {
      visited.add(neighbor);
      stack.push(neighbor);
    }
  }
  if (visited.size !== triangles.length / 3) throw new RangeError('Solid geometry requires one connected boundary.');
  for (let vertex = 0; vertex < incident.length; vertex++) {
    if (incident[vertex].length === 0) continue;
    const links = new Map();
    for (const face of incident[vertex]) {
      const other = Array.from(triangles.subarray(face * 3, face * 3 + 3)).filter(index => index !== vertex);
      for (let side = 0; side < 2; side++) {
        if (!links.has(other[side])) links.set(other[side], []);
        links.get(other[side]).push(other[1 - side]);
      }
    }
    if (Array.from(links.values()).some(link => link.length !== 2)) throw new RangeError('Solid geometry requires manifold vertex links.');
    const reached = new Set();
    const pending = [links.keys().next().value];
    while (pending.length) {
      const current = pending.pop();
      if (reached.has(current)) continue;
      reached.add(current);
      pending.push(...links.get(current));
    }
    if (reached.size !== links.size) throw new RangeError('Solid geometry requires a single cycle at each vertex link.');
  }
  return triangles;
}

function subtractPoints(first, second) {
  return vec3.subtract(createVector(), first, second);
}

function cornerOf(triangle, corner) {
  return createVector(triangle[corner * 3], triangle[corner * 3 + 1], triangle[corner * 3 + 2]);
}

function coneContains(origin, first, second, point, normal) {
  const edgeA = subtractPoints(first, origin);
  const edgeB = subtractPoints(second, origin);
  const direction = subtractPoints(point, origin);
  const cross = createVector();
  const denominator = vec3.dot(vec3.cross(cross, edgeA, edgeB), normal);
  const firstWeight = vec3.dot(vec3.cross(cross, direction, edgeB), normal) / denominator;
  const secondWeight = vec3.dot(vec3.cross(cross, edgeA, direction), normal) / denominator;
  return firstWeight >= -EPSILON && secondWeight >= -EPSILON;
}

function validateSelfIntersections(record, welded, maximum) {
  const counter = budget(maximum, 'maxValidationPairs');
  const segment = new Float64Array(6);
  castTriangles(record, record, createMatrix(), counter, (first, second, firstId, secondId) => {
    if (firstId >= secondId) return false;
    if (!trianglesIntersect(first, second, segment)) return false;
    const firstIds = Array.from(welded.subarray(firstId * 3, firstId * 3 + 3));
    const secondIds = Array.from(welded.subarray(secondId * 3, secondId * 3 + 3));
    const shared = firstIds.filter(index => secondIds.includes(index));
    if (shared.length === 0 || shared.length === 3) throw new RangeError('Solid boundary intersects itself.');
    const firstPoints = [0, 1, 2].map(corner => cornerOf(first, corner));
    const secondPoints = [0, 1, 2].map(corner => cornerOf(second, corner));
    const firstNormal = triangleNormal(first, createVector());
    const secondNormal = triangleNormal(second, createVector());
    const coplanar = vec3.length(vec3.cross(createVector(), firstNormal, secondNormal)) <= EPSILON;
    if (shared.length === 2) {
      if (coplanar) {
        const origin = firstPoints[firstIds.indexOf(shared[0])];
        const edge = subtractPoints(firstPoints[firstIds.indexOf(shared[1])], origin);
        const firstTip = subtractPoints(firstPoints[firstIds.findIndex(index => !shared.includes(index))], origin);
        const secondTip = subtractPoints(secondPoints[secondIds.findIndex(index => !shared.includes(index))], origin);
        const firstSide = vec3.dot(vec3.cross(createVector(), edge, firstTip), firstNormal);
        const secondSide = vec3.dot(vec3.cross(createVector(), edge, secondTip), firstNormal);
        if (firstSide * secondSide >= 0) throw new RangeError('Solid adjacent faces overlap or have ambiguous coplanar sides.');
      }
      return false;
    }
    const origin = firstPoints[firstIds.indexOf(shared[0])];
    if (!coplanar) {
      const segmentStart = segment.subarray(0, 3);
      const segmentEnd = segment.subarray(3, 6);
      if (vec3.distance(segmentStart, origin) > EPSILON || vec3.distance(segmentEnd, origin) > EPSILON) throw new RangeError('Solid faces intersect beyond their shared vertex.');
      return false;
    }
    const firstOther = firstPoints.filter((point, index) => firstIds[index] !== shared[0]);
    const secondOther = secondPoints.filter((point, index) => secondIds[index] !== shared[0]);
    if (secondOther.some(point => coneContains(origin, ...firstOther, point, firstNormal)) || firstOther.some(point => coneContains(origin, ...secondOther, point, secondNormal))) {
      throw new RangeError('Solid coplanar faces intersect beyond their shared vertex.');
    }
    return false;
  });
  return counter.tests;
}

// A scene query casts thousands of rays against one part with the same matrix, so the last validated state is kept.
function matrixState(record, values) {
  const cached = record.matrixCache;
  if (cached && ArrayBuffer.isView(values) === cached.typed && values.length === 16 && cached.source.every((value, position) => value === values[position])) return cached.state;
  const state = computeMatrixState(record, values);
  record.matrixCache = { source: Array.from(values), typed: ArrayBuffer.isView(values), state };
  return state;
}

function computeMatrixState(record, values) {
  if ((!Array.isArray(values) && !ArrayBuffer.isView(values)) || values.length !== 16) throw new TypeError('Query matrix requires 16 affine components.');
  const elements = Array.from(values, value => {
    if (typeof value !== 'number' || !Number.isFinite(value) || !Number.isFinite(Math.fround(value))) throw new RangeError('Query matrix requires finite Float32 components.');
    return Math.fround(value);
  });
  if (elements[3] !== 0 || elements[7] !== 0 || elements[11] !== 0 || elements[15] !== 1) throw new RangeError('Query matrix must be affine.');
  const matrix = mat4.multiply(createMatrix(), Float64Array.from(elements), record.normalization);
  const determinant = mat4.determinant(matrix);
  if (!Number.isFinite(determinant) || determinant === 0) throw new RangeError('Query matrix must be nonsingular.');
  const inverse = mat4.invert(createMatrix(), matrix);
  if (!inverse || !inverse.every(Number.isFinite)) throw new RangeError('Query matrix inverse exceeds the precision domain.');
  const bounds = transformBounds(record.bounds, matrix);
  if (!bounds.every(value => Number.isFinite(value) && Number.isFinite(Math.fround(value)))) throw new RangeError('Query world coordinates exceed finite Float32 bounds.');
  const resolution = maximumAbsolute(bounds) * 2 ** -21 + 2 ** -149;
  if (record.minimumAltitude / rotationScaleNorm(inverse) <= resolution) throw new RangeError('Query transformed triangles collapse within the Float32 precision domain.');
  return { matrix, inverse, bounds };
}

function relativeState(second, transform) {
  const inverse = mat4.invert(createMatrix(), transform);
  const inverseNorm = inverse ? rotationScaleNorm(inverse) : 0;
  const maximum = maximumAbsolute(transformBounds(second.bounds, transform));
  if (!Number.isFinite(maximum) || maximum > 1e6 || second.minimumAltitude / inverseNorm <= 1e-8) {
    throw new RangeError('Relative mesh transform exceeds the normalized triangle precision domain.');
  }
}

function containment(record, point, counter) {
  if (!boundsContainPoint(record.bounds, point)) return { inside: false, attempts: 0 };
  const triangle = new Float64Array(9);
  const normal = createVector();
  const hit = createVector();
  const weights = createVector();
  let previous;
  let accepted = 0;
  let attempts = 0;
  for (const direction of DIRECTIONS) {
    attempts++;
    const rayDirection = vec3.normalize(createVector(), direction);
    let count = 0;
    let ambiguous = false;
    traverseTriangleBvh(
      record.bvh,
      (bounds, offset) => rayBoxDistance(point, rayDirection, bounds, offset),
      score => Number.isFinite(score),
      triangleId => {
        counter.charge();
        readTriangle(record.positions, record.bvh.indices, triangleId, triangle);
        triangleNormal(triangle, normal);
        const offsetFromCorner = subtractPoints(point, cornerOf(triangle, 0));
        if (Math.abs(vec3.dot(normal, rayDirection)) <= EPSILON && Math.abs(vec3.dot(normal, offsetFromCorner)) <= EPSILON) {
          ambiguous = true;
          return true;
        }
        const distance = intersectRayTriangle(point, rayDirection, triangle);
        if (distance < 0) return false;
        vec3.scaleAndAdd(hit, point, rayDirection, distance);
        barycentricWeights(hit, triangle, weights);
        if (distance <= EPSILON || Math.min(weights[0], weights[1], weights[2]) <= EPSILON) {
          ambiguous = true;
          return true;
        }
        count++;
        return false;
      },
    );
    if (ambiguous) continue;
    const inside = count % 2 === 1;
    if (accepted && previous !== inside) throw new RangeError('Solid containment has inconsistent ray witnesses.');
    previous = inside;
    accepted++;
    if (accepted === 2) return { inside, attempts };
  }
  throw new RangeError('Solid containment is indeterminate after bounded ray retries.');
}

function localVector(input, name) {
  if (!isFloat32Triple(input)) throw new TypeError(`${name} requires three finite Float32-representable components.`);
  return createVector(...input);
}

function queryLocalSurface(record, pointInput, directionInput, options) {
  const originalPoint = localVector(pointInput, 'Query point');
  const point = vec3.scale(createVector(), subtractPoints(originalPoint, record.center), 1 / record.scale);
  if (maximumAbsolute(point) > 1e6) throw new RangeError('Query point exceeds the normalized precision domain.');
  const maximum = options.maxDistance ?? Infinity;
  if ((maximum !== Infinity && (!Number.isFinite(maximum) || !Number.isFinite(Math.fround(maximum)))) || maximum < 0) {
    throw new RangeError('maxDistance must be nonnegative and Float32-representable, or Infinity.');
  }
  const counter = budget(integer(options.maxTriangleTests ?? 2_000_000, 100_000_000, 'maxTriangleTests'), 'maxTriangleTests');
  let rayDirection;
  if (directionInput !== undefined) {
    const direction = localVector(directionInput, 'Projection direction');
    if (vec3.length(direction) === 0) throw new RangeError('Projection direction must be nonzero.');
    rayDirection = vec3.normalize(direction, direction);
  }
  let bestDistance = maximum / record.scale;
  let bestLocalDistance = maximum;
  let bestTriangle = Infinity;
  let bestPoint;
  let bestNormal;
  let bestWeights;
  const triangle = new Float64Array(9);
  const candidate = createVector();
  const candidateLocal = createVector();
  traverseTriangleBvh(
    record.bvh,
    (bounds, offset) => rayDirection ? rayBoxDistance(point, rayDirection, bounds, offset) : pointBoxDistance(point, bounds, offset),
    score => Number.isFinite(score) && score <= bestDistance + EPSILON,
    triangleId => {
      counter.charge();
      readTriangle(record.positions, record.bvh.indices, triangleId, triangle);
      if (rayDirection) {
        const hitDistance = intersectRayTriangle(point, rayDirection, triangle);
        if (hitDistance < 0) return false;
        vec3.scaleAndAdd(candidate, point, rayDirection, hitDistance);
      } else {
        closestPointOnTriangle(point, triangle, candidate);
      }
      const distance = vec3.distance(candidate, point);
      if (!Number.isFinite(distance)) throw new RangeError('Surface query exceeds the numerical precision domain.');
      vec3.add(candidateLocal, vec3.scale(candidateLocal, candidate, record.scale), record.center);
      const localDistance = vec3.distance(candidateLocal, originalPoint);
      // Apply the caller's cutoff in its original frame, avoiding normalized subtraction at exact endpoints.
      if (localDistance > bestLocalDistance || (localDistance === bestLocalDistance && triangleId >= bestTriangle)) return false;
      const weights = barycentricWeights(candidate, triangle, createVector());
      const normal = triangleNormal(triangle, createVector());
      if (!weights || !weights.every(Number.isFinite) || vec3.length(normal) === 0) throw new RangeError('Surface query has invalid triangle coordinates.');
      bestDistance = distance;
      bestLocalDistance = localDistance;
      bestTriangle = triangleId;
      bestPoint = Float64Array.from(candidateLocal);
      bestWeights = weights;
      bestNormal = normal;
      return false;
    },
  );
  if (!bestPoint) return { hit: null, triangleTests: counter.tests };
  const distance = bestLocalDistance;
  if (!Number.isFinite(distance) || !bestPoint.every(value => Number.isFinite(Math.fround(value)))) throw new RangeError('Surface query hit exceeds finite Float32 coordinates.');
  return { hit: { point: Array.from(bestPoint), distance, triangle: bestTriangle, barycentric: Array.from(bestWeights), normal: Array.from(bestNormal) }, triangleTests: counter.tests };
}

function nearestRayHit(record, origin, direction) {
  const triangle = new Float64Array(9);
  let bestDistance = Infinity;
  let bestTriangle = -1;
  traverseTriangleBvh(
    record.bvh,
    (bounds, offset) => rayBoxDistance(origin, direction, bounds, offset),
    score => Number.isFinite(score) && score <= bestDistance,
    triangleId => {
      readTriangle(record.positions, record.bvh.indices, triangleId, triangle);
      const distance = intersectRayTriangle(origin, direction, triangle);
      if (distance >= 0 && distance < bestDistance) {
        bestDistance = distance;
        bestTriangle = triangleId;
      }
      return false;
    },
  );
  if (bestTriangle < 0) return null;
  return { triangle: bestTriangle, point: vec3.scaleAndAdd(createVector(), origin, direction, bestDistance) };
}

function readRayField(ray, field) {
  const input = ray[field];
  if (!isFloat32Triple(input)) throw new TypeError(`Ray ${field} requires three finite Float32 values.`);
  return createVector(...Array.from(input, Math.fround));
}

function raycastIndex(current, matrix, ray) {
  const state = matrixState(current, matrix);
  if (!ray || typeof ray !== 'object') throw new TypeError('ray requires origin and direction.');
  const origin = readRayField(ray, 'origin');
  const direction = readRayField(ray, 'direction');
  if (vec3.length(direction) === 0) throw new RangeError('Ray direction must be nonzero.');
  const maximum = ray.maxDistance ?? Infinity;
  if ((maximum !== Infinity && !Number.isFinite(maximum)) || maximum < 0) throw new RangeError('Ray maxDistance must be nonnegative.');
  const localOrigin = vec3.transformMat4(createVector(), origin, state.inverse);
  const localDirection = vec3.normalize(createVector(), transformDirection(vec3.normalize(createVector(), direction), state.inverse));
  if (maximumAbsolute(localOrigin) > 1e6) throw new RangeError('Ray origin exceeds the normalized query precision domain.');
  const result = nearestRayHit(current, localOrigin, localDirection);
  if (!result) return null;
  const worldPoint = vec3.transformMat4(createVector(), result.point, state.matrix);
  const distance = vec3.distance(worldPoint, origin);
  if (!Number.isFinite(distance) || !worldPoint.every(value => Number.isFinite(Math.fround(value)))) throw new RangeError('Ray hit exceeds finite world coordinates.');
  if (distance > maximum) return null;
  const triangle = new Float64Array(9);
  readTriangle(current.positions, current.bvh.indices, result.triangle, triangle);
  const weights = barycentricWeights(result.point, triangle, createVector());
  if (!weights || !weights.every(Number.isFinite)) throw new RangeError('Ray barycentric coordinates exceed the query precision domain.');
  return { point: Array.from(worldPoint), distance, triangle: result.triangle, barycentric: Array.from(weights) };
}

function firstVertexIn(record, transform) {
  const offset = record.bvh.indices[0] * 3;
  return vec3.transformMat4(createVector(), record.positions.subarray(offset, offset + 3), transform);
}

/** Copies static geometry into a private normalized BVH. Returned handles expose no mesh internals. */
export function createMeshQueryIndex(geometry, options = {}) {
  optionsObject(options, INDEX_OPTIONS);
  const maxTriangles = integer(options.maxTriangles ?? 250_000, 1_000_000, 'maxTriangles');
  const maxVertices = integer(options.maxVertices ?? 250_000, 1_000_000, 'maxVertices');
  const maxValidationPairs = integer(options.maxValidationPairs ?? 2_000_000, 100_000_000, 'maxValidationPairs');
  const solid = options.solid ?? false;
  if (typeof solid !== 'boolean') throw new TypeError('solid must be boolean.');
  const memoryBudgetMiB = options.memoryBudgetMiB ?? 64;
  if (!Number.isFinite(memoryBudgetMiB) || memoryBudgetMiB <= 0 || memoryBudgetMiB > 1024) throw new RangeError('memoryBudgetMiB must be within zero and 1024.');
  const metadata = validateGeometry(geometry, maxVertices, maxTriangles);
  const reservedBytes = metadata.vertexCount * (solid ? 152 : 24) + metadata.triangleCount * (solid ? 512 : 128);
  if (reservedBytes > memoryBudgetMiB * 1024 * 1024) throw new RangeError('Mesh query allocation estimate exceeds memoryBudgetMiB.');
  const welded = solid ? topology(geometry) : null;
  const positions = new Float64Array(geometry.positions.length);
  for (let offset = 0; offset < positions.length; offset += 3) {
    for (let axis = 0; axis < 3; axis++) positions[offset + axis] = (geometry.positions[offset + axis] - metadata.center[axis]) / metadata.scale;
  }
  const normalization = Float64Array.of(metadata.scale, 0, 0, 0, 0, metadata.scale, 0, 0, 0, 0, metadata.scale, 0, metadata.center[0], metadata.center[1], metadata.center[2], 1);
  const bounds = Float64Array.of(Infinity, Infinity, Infinity, -Infinity, -Infinity, -Infinity);
  for (let offset = 0; offset < positions.length; offset += 3) {
    for (let axis = 0; axis < 3; axis++) {
      bounds[axis] = Math.min(bounds[axis], positions[offset + axis]);
      bounds[3 + axis] = Math.max(bounds[3 + axis], positions[offset + axis]);
    }
  }
  const bvh = buildTriangleBvh(positions, new Uint32Array(geometry.indices), { leafSize: 8, maxDepth: 64 });
  const record = { ...metadata, normalization, positions, bounds, bvh, disposed: false, solid };
  const validationPairs = solid ? validateSelfIntersections(record, welded, maxValidationPairs) : 0;
  const memoryPlan = Object.freeze({ reservedBytes, memoryBudgetMiB, vertexCount: metadata.vertexCount, triangleCount: metadata.triangleCount, validationPairs });
  const handle = Object.freeze({
    solid,
    memoryPlan,
    info: Object.freeze({ vertexCount: metadata.vertexCount, triangleCount: metadata.triangleCount, estimatedBytes: reservedBytes }),
    nearest(point, options = {}) {
      optionsObject(options, NEAREST_OPTIONS);
      return queryLocalSurface(live(handle), point, undefined, options);
    },
    project(ray) {
      optionsObject(ray, PROJECT_OPTIONS);
      if (ray.direction === undefined) throw new TypeError('Projection requires direction.');
      return queryLocalSurface(live(handle), ray.origin, ray.direction, ray);
    },
    raycast(matrix, ray) {
      return raycastIndex(live(handle), matrix, ray);
    },
    dispose() {
      if (record.disposed) return;
      record.disposed = true;
      record.positions = null;
      record.bvh = null;
    },
  });
  records.set(handle, record);
  return handle;
}

/** Surface contacts are not proof of volume penetration. Closed solids additionally test containment. */
export function createMeshPairQuery(indexA, indexB, options = {}) {
  optionsObject(options, PAIR_OPTIONS);
  const first = live(indexA);
  const second = live(indexB);
  const mode = options.mode ?? 'surfaces';
  if (mode !== 'surfaces' && mode !== 'closed-solids') throw new RangeError('Query mode must be surfaces or closed-solids.');
  if (mode === 'closed-solids' && (!first.solid || !second.solid)) throw new RangeError('Closed-solid queries require two validated solid indices.');
  const maximum = integer(options.maxTriangleTests ?? 2_000_000, 100_000_000, 'maxTriangleTests');
  return Object.freeze({
    evaluate(matrixA, matrixB) {
      const currentA = live(indexA);
      const currentB = live(indexB);
      const stateA = matrixState(currentA, matrixA);
      const stateB = matrixState(currentB, matrixB);
      const result = { kind: mode === 'surfaces' ? 'surface-disjoint' : 'separate', solidRelation: mode === 'surfaces' ? 'not-tested' : 'outside', triangles: null, triangleTests: 0, rayAttempts: 0 };
      if (!boundsOverlap(stateA.bounds, stateB.bounds)) return result;
      const relativeB = mat4.multiply(createMatrix(), stateA.inverse, stateB.matrix);
      const relativeA = mat4.multiply(createMatrix(), stateB.inverse, stateA.matrix);
      relativeState(currentB, relativeB);
      relativeState(currentA, relativeA);
      const counter = budget(maximum, 'maxTriangleTests');
      const contact = castTriangles(currentA, currentB, relativeB, counter, (firstTriangle, secondTriangle, firstId, secondId) => {
        if (!trianglesIntersect(firstTriangle, secondTriangle)) return false;
        result.triangles = [firstId, secondId];
        return true;
      });
      if (contact) {
        result.kind = 'surface-intersection';
        result.solidRelation = mode === 'surfaces' ? 'not-tested' : 'boundaries-intersect';
      } else if (mode === 'closed-solids') {
        const firstInside = containment(currentB, firstVertexIn(currentA, relativeA), counter);
        const secondInside = containment(currentA, firstVertexIn(currentB, relativeB), counter);
        result.rayAttempts = firstInside.attempts + secondInside.attempts;
        if (firstInside.inside && secondInside.inside) throw new RangeError('Solid containment witnesses are inconsistent.');
        if (firstInside.inside || secondInside.inside) {
          result.kind = 'contained';
          result.solidRelation = firstInside.inside ? 'a-in-b' : 'b-in-a';
        }
      }
      result.triangleTests = counter.tests;
      return result;
    },
  });
}

/** A query index over indexed triangles in any typed or plain arrays, for callers that hold render geometry or MeshData triangles. */
export function createTriangleSurfaceIndex({ positions, indices }) {
  const wholeIndices = Uint32Array.from(indices);
  if (wholeIndices.some((index, slot) => index !== indices[slot])) throw new TypeError('indices must be whole vertex numbers');
  return createMeshQueryIndex({ positions: Float32Array.from(positions), indices: wholeIndices });
}