Skip to content

3D engine that AI agents drive

11.7 KB
Raw Blame
import { createMeshQueryIndex, createMeshPairQuery } from './mesh-query.js';
import { faceNormals } from './mesh-normals.js';
import { triangulateMesh } from './mesh-render.js';

/**
 * Shape checks that need a spatial index: parts that cross, solids that cross themselves, walls too thin to print or
 * survive a bevel, parts that float free, and meshes that are almost symmetric. Each check has a budget so a lint call
 * stays cheap; a check that would pass it is skipped and named in the result instead of running long.
 */
export const GEOMETRY_LINT_BUDGET = Object.freeze({
  maxTrianglesPerPart: 20_000,
  maxTotalTriangles: 60_000,
  maxPartPairs: 64,
  maxThinWallSamples: 256,
  maxSymmetryVertices: 50_000,
  maxSampleElements: 8,
});

// Fractions of the mesh bounds diagonal.
const THIN_WALL_RATIO = 0.005;
const CONTACT_RATIO = 1e-4;
const SYMMETRY_MATCH_RATIO = 1e-4;
// Below this share of matched vertices a mesh is simply not symmetric; at or above it, the misses are mistakes.
const SYMMETRY_INTENT_SHARE = 0.8;
const IDENTITY_MATRIX = Object.freeze([1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1]);

function partFaces(facePart, partCount) {
  const faces = Array.from({ length: partCount }, () => []);
  for (let face = 0; face < facePart.length; face++) faces[facePart[face]].push(face);
  return faces;
}

/**
 * Triangle corners of the faces of each part, in face order: a quad splits along its shorter diagonal and a concave
 * polygon is ear clipped, so the triangles stay inside the face (a fan from one corner would cross a concave one).
 */
function faceTriangles(mesh) {
  const { normals } = faceNormals(mesh);
  const { triangleCorners } = triangulateMesh(mesh, normals);
  const firstTriangle = new Uint32Array(mesh.faceCount + 1);
  for (let face = 0; face < mesh.faceCount; face++) {
    firstTriangle[face + 1] = firstTriangle[face] + mesh.faceOffsets[face + 1] - mesh.faceOffsets[face] - 2;
  }
  return { triangleCorners, firstTriangle };
}

/** Compacts the triangles of one part into a Float32/Uint32 geometry for the query index. */
function partGeometry(mesh, faces, { triangleCorners, firstTriangle }) {
  const compactIndex = new Map();
  const positions = [];
  const indices = [];
  const compact = corner => {
    const vertex = mesh.cornerVertices[corner];
    let index = compactIndex.get(vertex);
    if (index === undefined) {
      index = compactIndex.size;
      compactIndex.set(vertex, index);
      positions.push(mesh.positions[vertex * 3], mesh.positions[vertex * 3 + 1], mesh.positions[vertex * 3 + 2]);
    }
    return index;
  };
  for (const face of faces) {
    for (let cornerSlot = firstTriangle[face] * 3; cornerSlot < firstTriangle[face + 1] * 3; cornerSlot++) {
      indices.push(compact(triangleCorners[cornerSlot]));
    }
  }
  return { positions: Float32Array.from(positions), indices: Uint32Array.from(indices) };
}

function geometryBounds(geometry) {
  const min = [Infinity, Infinity, Infinity];
  const max = [-Infinity, -Infinity, -Infinity];
  for (let offset = 0; offset < geometry.positions.length; offset += 3) {
    for (let axis = 0; axis < 3; axis++) {
      min[axis] = Math.min(min[axis], geometry.positions[offset + axis]);
      max[axis] = Math.max(max[axis], geometry.positions[offset + axis]);
    }
  }
  return { min, max };
}

function boundsGap(first, second) {
  let squared = 0;
  for (let axis = 0; axis < 3; axis++) {
    const gap = Math.max(first.min[axis] - second.max[axis], second.min[axis] - first.max[axis], 0);
    squared += gap * gap;
  }
  return Math.sqrt(squared);
}

function limitedSample(elements) {
  return elements.slice(0, GEOMETRY_LINT_BUDGET.maxSampleElements);
}

function findFloatingParts(bounds, contactDistance) {
  if (bounds.length < 2) return [];
  const floating = [];
  for (let part = 0; part < bounds.length; part++) {
    const touching = bounds.some((other, otherPart) => otherPart !== part && boundsGap(bounds[part], other) <= contactDistance);
    if (!touching) floating.push(part);
  }
  return floating;
}

function findIntersectingParts(geometries, bounds, contactDistance, skipped) {
  const crossing = [];
  // Larger than every part index, so two different pairs never share a code.
  const pairStride = Math.max(1000, geometries.length);
  let pairsTested = 0;
  for (let first = 0; first < geometries.length; first++) {
    for (let second = first + 1; second < geometries.length; second++) {
      if (boundsGap(bounds[first], bounds[second]) > contactDistance) continue;
      if (pairsTested++ >= GEOMETRY_LINT_BUDGET.maxPartPairs) {
        skipped.add('intersecting-parts');
        return crossing;
      }
      const firstIndex = createMeshQueryIndex(geometries[first]);
      const secondIndex = createMeshQueryIndex(geometries[second]);
      try {
        const result = createMeshPairQuery(firstIndex, secondIndex).evaluate(IDENTITY_MATRIX, IDENTITY_MATRIX);
        if (result.kind === 'surface-intersection') crossing.push(first * pairStride + second);
      } catch {
        skipped.add('intersecting-parts');
      } finally {
        firstIndex.dispose();
        secondIndex.dispose();
      }
    }
  }
  return crossing;
}

const SELF_INTERSECTION_MESSAGE = /intersect|overlap/i;

function hasSelfIntersection(geometry, skipped) {
  try {
    createMeshQueryIndex(geometry, { solid: true }).dispose();
    return false;
  } catch (error) {
    if (SELF_INTERSECTION_MESSAGE.test(error.message)) return true;
    skipped.add('self-intersection');
    return false;
  }
}

function faceCentroid(mesh, face) {
  const start = mesh.faceOffsets[face];
  const end = mesh.faceOffsets[face + 1];
  const centroid = [0, 0, 0];
  for (let corner = start; corner < end; corner++) {
    for (let axis = 0; axis < 3; axis++) centroid[axis] += mesh.positions[mesh.cornerVertices[corner] * 3 + axis];
  }
  return centroid.map(value => value / (end - start));
}

/** Casts a ray from each sampled face straight into the solid; a near hit means the wall is thin there. */
function findThinFaces(mesh, geometry, faces, normals, diagonal) {
  const index = createMeshQueryIndex(geometry);
  const nudge = diagonal * CONTACT_RATIO;
  const limit = diagonal * THIN_WALL_RATIO;
  const stride = Math.max(1, Math.ceil(faces.length / GEOMETRY_LINT_BUDGET.maxThinWallSamples));
  const thin = [];
  try {
    for (let position = 0; position < faces.length; position += stride) {
      const face = faces[position];
      const normal = [normals[face * 3], normals[face * 3 + 1], normals[face * 3 + 2]];
      const centroid = faceCentroid(mesh, face);
      const origin = centroid.map((value, axis) => value - normal[axis] * nudge);
      const hit = index.raycast(IDENTITY_MATRIX, { origin, direction: normal.map(value => -value) });
      if (hit && hit.distance + nudge < limit) thin.push(face);
    }
  } finally {
    index.dispose();
  }
  return thin;
}

function cellKey(cell) {
  return `${cell[0]},${cell[1]},${cell[2]}`;
}

/** Vertices that have no partner when the mesh is mirrored across the plane at `plane` on one axis. */
function unmatchedMirrorVertices(mesh, axis, plane, tolerance) {
  const cellSize = tolerance * 4;
  const cells = new Set();
  const cellOf = point => point.map(value => Math.round(value / cellSize));
  const pointOf = vertex => [mesh.positions[vertex * 3], mesh.positions[vertex * 3 + 1], mesh.positions[vertex * 3 + 2]];
  for (let vertex = 0; vertex < mesh.vertexCount; vertex++) cells.add(cellKey(cellOf(pointOf(vertex))));
  const unmatched = [];
  for (let vertex = 0; vertex < mesh.vertexCount; vertex++) {
    const mirrored = pointOf(vertex);
    mirrored[axis] = 2 * plane - mirrored[axis];
    const home = cellOf(mirrored);
    let matched = false;
    for (let x = -1; x <= 1 && !matched; x++) {
      for (let y = -1; y <= 1 && !matched; y++) {
        for (let z = -1; z <= 1 && !matched; z++) {
          matched = cells.has(cellKey([home[0] + x, home[1] + y, home[2] + z]));
        }
      }
    }
    if (!matched) unmatched.push(vertex);
  }
  return unmatched;
}

function findAsymmetry(mesh, bounds, diagonal) {
  const found = [];
  for (const [axis, name] of [[0, 'x'], [2, 'z']]) {
    // A mirrored model is usually centred on the origin; otherwise on its bounds or its mean. Take the best plane.
    let mean = 0;
    for (let vertex = 0; vertex < mesh.vertexCount; vertex++) mean += mesh.positions[vertex * 3 + axis];
    const planes = [0, (bounds.min[axis] + bounds.max[axis]) / 2, mean / mesh.vertexCount];
    const candidates = planes.map(plane => unmatchedMirrorVertices(mesh, axis, plane, diagonal * SYMMETRY_MATCH_RATIO));
    const unmatched = candidates.reduce((best, candidate) => (candidate.length < best.length ? candidate : best));
    const matchedShare = 1 - unmatched.length / mesh.vertexCount;
    if (unmatched.length > 0 && matchedShare >= SYMMETRY_INTENT_SHARE) found.push({ axis: name, unmatched });
  }
  return found;
}

// The query index rejects triangles below its precision domain; a check that cannot run is named, never thrown.
function attempt(check, skipped, work, fallback) {
  try {
    return work();
  } catch {
    skipped.add(check);
    return fallback;
  }
}

function problem(kind, elements, extra = {}) {
  return { kind, count: elements.length, sample: limitedSample(elements), ...extra };
}

/**
 * Runs the spatial checks on a polygon mesh. `solidParts` lists the parts that are closed, consistently wound and
 * outward facing. Returns { problems, skipped }, where each problem has kind, count and a sample of element indices
 * (part pairs as first * max(1000, partCount) + second, parts, faces or vertices by kind).
 */
export function lintMeshGeometry(mesh, { facePart, partCount, solidParts, bounds, diagonal }) {
  const skipped = new Set();
  const found = [];
  const faces = partFaces(facePart, partCount);
  const contactDistance = diagonal * CONTACT_RATIO;
  const totalFaces = faces.reduce((total, partFaceList) => total + partFaceList.length, 0);
  // Budgets count faces; a quad is two triangles, so these are loose upper-bound proxies for triangles.
  const withinFaceBudget = totalFaces <= GEOMETRY_LINT_BUDGET.maxTotalTriangles
    && faces.every(partFaceList => partFaceList.length <= GEOMETRY_LINT_BUDGET.maxTrianglesPerPart);
  // A face too large to triangulate cannot be checked; the spatial checks are named as skipped instead of thrown.
  const triangles = withinFaceBudget ? attempt('triangulation', new Set(), () => faceTriangles(mesh), null) : null;
  if (triangles) {
    const geometries = faces.map(partFaceList => partGeometry(mesh, partFaceList, triangles));
    const partBounds = geometries.map(geometryBounds);
    const crossing = attempt('intersecting-parts', skipped, () => findIntersectingParts(geometries, partBounds, contactDistance, skipped), []);
    if (crossing.length) found.push(problem('intersecting-parts', crossing));
    const selfCrossing = solidParts.filter(part => hasSelfIntersection(geometries[part], skipped));
    if (selfCrossing.length) found.push(problem('self-intersection', selfCrossing));
    const { normals } = faceNormals(mesh);
    const thinFaces = solidParts.flatMap(part => attempt('thin-wall', skipped, () => findThinFaces(mesh, geometries[part], faces[part], normals, diagonal), []));
    if (thinFaces.length) found.push(problem('thin-wall', thinFaces));
    const floating = findFloatingParts(partBounds, contactDistance);
    if (floating.length) found.push(problem('floating-part', floating));
  } else {
    for (const check of ['intersecting-parts', 'self-intersection', 'thin-wall', 'floating-part']) skipped.add(check);
  }
  if (mesh.vertexCount <= GEOMETRY_LINT_BUDGET.maxSymmetryVertices) {
    for (const { axis, unmatched } of findAsymmetry(mesh, bounds, diagonal)) {
      found.push(problem('asymmetric', unmatched, { axis }));
    }
  } else {
    skipped.add('asymmetric');
  }
  return { problems: found, skipped: [...skipped] };
}