3D engine that AI agents drive
JavaScript 3d3d-engineagentic-aiai-agentsblenderclaude-codegame-enginegaussian-splattinggltfjavascriptmcpmcp-servermodel-context-protocolpath-tracerpath-tracingpbrrenderingthreejs-alternativewebgl2webgpu
import { meshBounds, tagCounts } from './mesh-data.js';
import { lintMeshGeometry } from './mesh-lint-geometry.js';
import { faceNormals } from './mesh-normals.js';
import { cornerFaces, edgeCornerTable, faceParts } from './mesh-topology.js';
const SAMPLE_LIMIT = 8;
// Neighbouring faces whose normals have a dot product below this lie on top of each other, facing opposite ways.
const FOLDED_NORMAL_DOT = -0.99;
// Every problem names the operation that usually fixes it, so an agent can act without another lookup.
export const MESH_PROBLEMS = Object.freeze({
'non-manifold-edge': { severity: 'error', fix: 'Delete the extra faces or split the edge; booleans and solidify need two faces per edge.' },
'inconsistent-winding': { severity: 'error', fix: 'Run flip_normals with select { faces: sample }: sample lists faces (not edges) that wind against their neighbours, at most 8 of them, so lint again after flipping until it comes back clean.' },
'inverted-part': { severity: 'error', fix: 'Run flip_normals on the part; its normals point inward.' },
'degenerate-face': { severity: 'error', fix: 'Run merge_by_distance, or dissolve_faces on the zero-area faces.' },
'loose-vertex': { severity: 'warning', fix: 'Run delete_loose to remove them; loose vertices do not render and confuse bounds.' },
'boundary-edge': { severity: 'warning', fix: 'Open surface. Run fill_holes to cap each boundary loop, or add solidify if the part must be closed.' },
});
// Spatial checks, opt in through lintMesh(mesh, { geometry: true }) because each builds a BVH. All are warnings: a mesh
// can cross itself, be thin or float on purpose, so none of them turns ok off.
export const GEOMETRY_PROBLEMS = Object.freeze({
'intersecting-parts': { severity: 'warning', fix: 'Two parts cross each other (sample holds first * max(1000, part count) + second part index). Move them apart, or run a union boolean if they should be one solid.' },
'self-intersection': { severity: 'warning', fix: 'A closed part cuts through itself. Undo the last extrude, inset or translate that folded it, or lower its offset.' },
'thin-wall': { severity: 'warning', fix: 'The wall behind these faces (sample is face indices) is under 0.5% of the mesh size thick. Thicken it with solidify, or move the faces apart.' },
'floating-part': { severity: 'warning', fix: 'This part (sample is part indices) touches no other part. Translate it onto its neighbour, or ignore this if it is meant to stand alone.' },
asymmetric: { severity: 'warning', fix: 'The mesh is mirror-symmetric except for the vertices in sample. Rebuild one half and mirror it, or set_position those vertices to their partners.' },
'folded-face': { severity: 'warning', fix: 'Two neighbouring faces fold back onto each other (sample is edge indices), usually after an inset, extrude or bevel went past the face limit. Lower thickness or width, or undo that operation.' },
'non-planar-quad': { severity: 'warning', fix: 'These quads (sample is face indices) fold by more than 45 degrees across their diagonal and pinch shading. Triangulate them, or flatten their corners.' },
'skewed-quad': { severity: 'warning', fix: 'These quads (sample is face indices) have a corner over 60 degrees from a right angle. Dissolve or slide edges so corners stay near 90 degrees.' },
});
const NON_PLANAR_QUAD_DEGREES = 45;
const SKEWED_QUAD_DEGREES = 60;
function roundMetric(value) {
return Math.round(value * 1e4) / 1e4;
}
/**
* Interior vertex valence and quad shape quality (corner angle deviation from 90 degrees, aspect ratio and diagonal fold).
* Boundary vertices are excluded from pole counts because an open rim naturally has degree 2 or 3.
*/
export function meshTopologyMetrics(mesh, table = edgeCornerTable(mesh), problems = null) {
const degree = new Uint32Array(mesh.vertexCount);
const boundaryVertex = new Uint8Array(mesh.vertexCount);
for (let edge = 0; edge < mesh.edgeCount; edge++) {
const first = mesh.edgeVertices[edge * 2];
const second = mesh.edgeVertices[edge * 2 + 1];
degree[first]++;
degree[second]++;
if (table.edgeOffsets[edge + 1] - table.edgeOffsets[edge] !== 2) {
boundaryVertex[first] = 1;
boundaryVertex[second] = 1;
}
}
let regular = 0;
let valence3 = 0;
let valence5 = 0;
let valence6Plus = 0;
for (let vertex = 0; vertex < mesh.vertexCount; vertex++) {
if (degree[vertex] === 0 || boundaryVertex[vertex]) continue;
if (degree[vertex] === 4) regular++;
else if (degree[vertex] === 3) valence3++;
else if (degree[vertex] === 5) valence5++;
else if (degree[vertex] >= 6) valence6Plus++;
}
const positions = mesh.positions;
let quadCount = 0;
let meanAngleDeviation = 0;
let maxAngleDeviation = 0;
let maxAspectRatio = 1;
let maxWarpAngle = 0;
for (let face = 0; face < mesh.faceCount; face++) {
const start = mesh.faceOffsets[face];
if (mesh.faceOffsets[face + 1] - start !== 4) continue;
quadCount++;
const v0 = mesh.cornerVertices[start] * 3;
const v1 = mesh.cornerVertices[start + 1] * 3;
const v2 = mesh.cornerVertices[start + 2] * 3;
const v3 = mesh.cornerVertices[start + 3] * 3;
const corners = [v0, v1, v2, v3];
let shortestEdge = Infinity;
let longestEdge = 0;
let faceMaxDeviation = 0;
let faceDeviationSum = 0;
for (let index = 0; index < 4; index++) {
const current = corners[index];
const next = corners[(index + 1) & 3];
const previous = corners[(index + 3) & 3];
const nextX = positions[next] - positions[current];
const nextY = positions[next + 1] - positions[current + 1];
const nextZ = positions[next + 2] - positions[current + 2];
const prevX = positions[previous] - positions[current];
const prevY = positions[previous + 1] - positions[current + 1];
const prevZ = positions[previous + 2] - positions[current + 2];
const edgeLength = Math.hypot(nextX, nextY, nextZ);
if (edgeLength < shortestEdge) shortestEdge = edgeLength;
if (edgeLength > longestEdge) longestEdge = edgeLength;
const crossLength = Math.hypot(nextY * prevZ - nextZ * prevY, nextZ * prevX - nextX * prevZ, nextX * prevY - nextY * prevX);
const angle = Math.atan2(crossLength, nextX * prevX + nextY * prevY + nextZ * prevZ) * 180 / Math.PI;
const deviation = Math.abs(angle - 90);
faceDeviationSum += deviation;
if (deviation > faceMaxDeviation) faceMaxDeviation = deviation;
}
meanAngleDeviation += faceDeviationSum / 4;
if (faceMaxDeviation > maxAngleDeviation) maxAngleDeviation = faceMaxDeviation;
if (shortestEdge > 1e-12) {
const aspect = longestEdge / shortestEdge;
if (aspect > maxAspectRatio) maxAspectRatio = aspect;
}
const diagX = positions[v2] - positions[v0];
const diagY = positions[v2 + 1] - positions[v0 + 1];
const diagZ = positions[v2 + 2] - positions[v0 + 2];
const e01x = positions[v1] - positions[v0];
const e01y = positions[v1 + 1] - positions[v0 + 1];
const e01z = positions[v1 + 2] - positions[v0 + 2];
const e03x = positions[v3] - positions[v0];
const e03y = positions[v3 + 1] - positions[v0 + 1];
const e03z = positions[v3 + 2] - positions[v0 + 2];
const n1x = e01y * diagZ - e01z * diagY;
const n1y = e01z * diagX - e01x * diagZ;
const n1z = e01x * diagY - e01y * diagX;
const n2x = diagY * e03z - diagZ * e03y;
const n2y = diagZ * e03x - diagX * e03z;
const n2z = diagX * e03y - diagY * e03x;
const len1 = Math.hypot(n1x, n1y, n1z);
const len2 = Math.hypot(n2x, n2y, n2z);
let warpAngle = 0;
if (len1 > 1e-12 && len2 > 1e-12) {
const cosine = Math.max(-1, Math.min(1, (n1x * n2x + n1y * n2y + n1z * n2z) / (len1 * len2)));
warpAngle = Math.acos(cosine) * 180 / Math.PI;
if (warpAngle > maxWarpAngle) maxWarpAngle = warpAngle;
}
if (problems) {
if (warpAngle > NON_PLANAR_QUAD_DEGREES) addQualityProblem(problems, 'non-planar-quad', face);
const touchesHighPole = [v0, v1, v2, v3].some(offset => degree[offset / 3] >= 6);
if (faceMaxDeviation > SKEWED_QUAD_DEGREES && !touchesHighPole) addQualityProblem(problems, 'skewed-quad', face);
}
}
return {
valence: { regular, poles3: valence3, poles5: valence5, poles6Plus: valence6Plus },
quadQuality: {
meanAngleError: quadCount ? roundMetric(meanAngleDeviation / quadCount) : 0,
maxAngleError: roundMetric(maxAngleDeviation),
maxAspect: roundMetric(maxAspectRatio),
maxWarp: roundMetric(maxWarpAngle),
},
};
}
function addQualityProblem(problems, kind, element) {
let problem = problems.get(kind);
if (!problem) {
problem = { kind, ...GEOMETRY_PROBLEMS[kind], count: 0, sample: [] };
problems.set(kind, problem);
}
problem.count++;
if (problem.sample.length < SAMPLE_LIMIT) problem.sample.push(element);
}
function addProblem(problems, kind, element) {
let problem = problems.get(kind);
if (!problem) {
problem = { kind, ...MESH_PROBLEMS[kind], count: 0, sample: [] };
problems.set(kind, problem);
}
problem.count++;
if (problem.sample.length < SAMPLE_LIMIT) problem.sample.push(element);
}
// An edge shared by two consistently wound faces whose normals point opposite ways is a fold: the surface doubles back.
function flagFoldedEdges(mesh, table, facesOfCorners, problems) {
const { normals, areas } = faceNormals(mesh);
for (let edge = 0; edge < mesh.edgeCount; edge++) {
const start = table.edgeOffsets[edge];
if (table.edgeOffsets[edge + 1] - start !== 2) continue;
const first = facesOfCorners[table.edgeCorners[start]];
const second = facesOfCorners[table.edgeCorners[start + 1]];
if (first === second || !areas[first] || !areas[second]) continue;
const alignment = normals[first * 3] * normals[second * 3]
+ normals[first * 3 + 1] * normals[second * 3 + 1]
+ normals[first * 3 + 2] * normals[second * 3 + 2];
if (alignment < FOLDED_NORMAL_DOT) addQualityProblem(problems, 'folded-face', edge);
}
}
/**
* Signed volume of each part, from the divergence theorem over its triangulated fan.
* Only meaningful for closed, consistently wound parts.
*/
function partVolumes(mesh, facePart, partCount) {
const volumes = new Float64Array(partCount);
const positions = mesh.positions;
for (let face = 0; face < mesh.faceCount; face++) {
const start = mesh.faceOffsets[face];
const end = mesh.faceOffsets[face + 1];
const anchor = mesh.cornerVertices[start] * 3;
for (let corner = start + 1; corner + 1 < end; corner++) {
const second = mesh.cornerVertices[corner] * 3;
const third = mesh.cornerVertices[corner + 1] * 3;
volumes[facePart[face]] += (
positions[anchor] * (positions[second + 1] * positions[third + 2] - positions[second + 2] * positions[third + 1]) +
positions[anchor + 1] * (positions[second + 2] * positions[third] - positions[second] * positions[third + 2]) +
positions[anchor + 2] * (positions[second] * positions[third + 1] - positions[second + 1] * positions[third])
) / 6;
}
}
return volumes;
}
// A slightly skewed ray direction avoids running exactly along axis-aligned edges and faces.
const RAY_DIRECTION = [0.8017837, 0.5345225, 0.2672612];
/** Whether the ray from origin along RAY_DIRECTION crosses triangle (firstOffset, secondOffset, thirdOffset), by Moller-Trumbore. */
function rayHitsTriangle(origin, positions, firstOffset, secondOffset, thirdOffset) {
const edgeFirst = [positions[secondOffset] - positions[firstOffset], positions[secondOffset + 1] - positions[firstOffset + 1], positions[secondOffset + 2] - positions[firstOffset + 2]];
const edgeSecond = [positions[thirdOffset] - positions[firstOffset], positions[thirdOffset + 1] - positions[firstOffset + 1], positions[thirdOffset + 2] - positions[firstOffset + 2]];
const [directionX, directionY, directionZ] = RAY_DIRECTION;
const perpendicular = [
directionY * edgeSecond[2] - directionZ * edgeSecond[1],
directionZ * edgeSecond[0] - directionX * edgeSecond[2],
directionX * edgeSecond[1] - directionY * edgeSecond[0],
];
const determinant = edgeFirst[0] * perpendicular[0] + edgeFirst[1] * perpendicular[1] + edgeFirst[2] * perpendicular[2];
if (Math.abs(determinant) < 1e-12) return false;
const inverse = 1 / determinant;
const toOrigin = [origin[0] - positions[firstOffset], origin[1] - positions[firstOffset + 1], origin[2] - positions[firstOffset + 2]];
const u = (toOrigin[0] * perpendicular[0] + toOrigin[1] * perpendicular[1] + toOrigin[2] * perpendicular[2]) * inverse;
if (u < 0 || u > 1) return false;
const cross = [
toOrigin[1] * edgeFirst[2] - toOrigin[2] * edgeFirst[1],
toOrigin[2] * edgeFirst[0] - toOrigin[0] * edgeFirst[2],
toOrigin[0] * edgeFirst[1] - toOrigin[1] * edgeFirst[0],
];
const v = (directionX * cross[0] + directionY * cross[1] + directionZ * cross[2]) * inverse;
if (v < 0 || u + v > 1) return false;
const distance = (edgeSecond[0] * cross[0] + edgeSecond[1] * cross[1] + edgeSecond[2] * cross[2]) * inverse;
return distance > 0;
}
/** Whether a vertex of `part` lies inside the faces of the other parts (odd number of ray crossings). */
function insideOtherPart(mesh, facePart, part) {
let face = 0;
while (facePart[face] !== part) face++;
const vertex = mesh.cornerVertices[mesh.faceOffsets[face]] * 3;
const origin = [mesh.positions[vertex], mesh.positions[vertex + 1], mesh.positions[vertex + 2]];
let crossings = 0;
for (let other = 0; other < mesh.faceCount; other++) {
if (facePart[other] === part) continue;
const start = mesh.faceOffsets[other];
const anchor = mesh.cornerVertices[start] * 3;
for (let corner = start + 1; corner + 1 < mesh.faceOffsets[other + 1]; corner++) {
if (rayHitsTriangle(origin, mesh.positions, anchor, mesh.cornerVertices[corner] * 3, mesh.cornerVertices[corner + 1] * 3)) crossings++;
}
}
return crossings % 2 === 1;
}
/**
* Faces to flip so every part with inconsistent winding becomes consistent. Faces are two-coloured by walking shared
* edges, switching colour across an inconsistently wound edge; the smaller colour of each part is the one to flip.
*/
function facesWoundAgainstNeighbours(mesh, table, facesOfCorners, facePart, partWindingBroken) {
const neighbours = Array.from({ length: mesh.faceCount }, () => []);
for (let edge = 0; edge < mesh.edgeCount; edge++) {
const start = table.edgeOffsets[edge];
if (table.edgeOffsets[edge + 1] - start !== 2) continue;
const first = facesOfCorners[table.edgeCorners[start]];
const second = facesOfCorners[table.edgeCorners[start + 1]];
const sameDirection = mesh.cornerVertices[table.edgeCorners[start]] === mesh.cornerVertices[table.edgeCorners[start + 1]] ? 1 : 0;
neighbours[first].push(second, sameDirection);
neighbours[second].push(first, sameDirection);
}
const colour = new Int8Array(mesh.faceCount).fill(-1);
const facesToFlip = [];
for (let seed = 0; seed < mesh.faceCount; seed++) {
if (colour[seed] !== -1 || !partWindingBroken[facePart[seed]]) continue;
const members = [seed];
colour[seed] = 0;
for (let cursor = 0; cursor < members.length; cursor++) {
const face = members[cursor];
for (let index = 0; index < neighbours[face].length; index += 2) {
const neighbour = neighbours[face][index];
if (colour[neighbour] !== -1) continue;
colour[neighbour] = colour[face] ^ neighbours[face][index + 1];
members.push(neighbour);
}
}
const flippedColour = members.filter(face => colour[face] === 1).length * 2 <= members.length ? 1 : 0;
for (const face of members) {
if (colour[face] === flippedColour) facesToFlip.push(face);
}
}
return facesToFlip.sort((a, b) => a - b);
}
/**
* Check a mesh for problems that break later operations or rendering.
* Returns { ok, counts, parts, tags, bounds, problems }, where each problem has kind, severity, count, a sample of
* element indices (faces, edges or vertices by kind; for inconsistent-winding the faces to flip) and a suggested fix. ok is false when any error is present.
*/
export function lintMesh(mesh, { geometry = false } = {}) {
const problems = new Map();
const table = edgeCornerTable(mesh);
const facesOfCorners = cornerFaces(mesh);
const { facePart, partCount } = faceParts(mesh, table, facesOfCorners);
const partOpen = new Uint8Array(partCount);
const partWindingBroken = new Uint8Array(partCount);
const woundEdges = [];
for (let edge = 0; edge < mesh.edgeCount; edge++) {
const start = table.edgeOffsets[edge];
const faceCount = table.edgeOffsets[edge + 1] - start;
const part = facePart[facesOfCorners[table.edgeCorners[start]]];
if (faceCount === 1) {
addProblem(problems, 'boundary-edge', edge);
partOpen[part] = 1;
} else if (faceCount > 2) {
addProblem(problems, 'non-manifold-edge', edge);
partOpen[part] = 1;
} else if (mesh.cornerVertices[table.edgeCorners[start]] === mesh.cornerVertices[table.edgeCorners[start + 1]]) {
addProblem(problems, 'inconsistent-winding', edge);
partWindingBroken[part] = 1;
woundEdges.push(edge);
}
}
if (woundEdges.length) {
const facesToFlip = facesWoundAgainstNeighbours(mesh, table, facesOfCorners, facePart, partWindingBroken);
problems.get('inconsistent-winding').sample = facesToFlip.slice(0, SAMPLE_LIMIT);
}
const bounds = meshBounds(mesh);
const diagonal = Math.hypot(...bounds.max.map((value, axis) => value - bounds.min[axis]));
const minimumArea = (diagonal * 1e-7) ** 2;
const { areas } = faceNormals(mesh);
for (let face = 0; face < mesh.faceCount; face++) {
if (areas[face] <= minimumArea) addProblem(problems, 'degenerate-face', face);
}
if (geometry) flagFoldedEdges(mesh, table, facesOfCorners, problems);
const used = new Uint8Array(mesh.vertexCount);
for (const vertex of mesh.cornerVertices) used[vertex] = 1;
for (let vertex = 0; vertex < mesh.vertexCount; vertex++) {
if (!used[vertex]) addProblem(problems, 'loose-vertex', vertex);
}
const volumes = partVolumes(mesh, facePart, partCount);
let closedParts = 0;
let cavities = 0;
const solidParts = [];
for (let part = 0; part < partCount; part++) {
if (partOpen[part] || partWindingBroken[part]) continue;
closedParts++;
if (volumes[part] >= 0) {
solidParts.push(part);
continue;
}
// A negative shell inside another part is a cavity (a hollow), which is valid; elsewhere it is inside out.
if (insideOtherPart(mesh, facePart, part)) cavities++;
else addProblem(problems, 'inverted-part', part);
}
const topology = meshTopologyMetrics(mesh, table, geometry ? problems : null);
const problemList = [...problems.values()];
let skippedChecks;
if (geometry) {
const spatial = lintMeshGeometry(mesh, { facePart, partCount, solidParts, bounds, diagonal });
for (const found of spatial.problems) problemList.push({ ...found, ...GEOMETRY_PROBLEMS[found.kind] });
if (spatial.skipped.length) skippedChecks = spatial.skipped;
}
const ok = !problemList.some(problem => problem.severity === 'error');
return {
ok,
counts: { vertices: mesh.vertexCount, edges: mesh.edgeCount, faces: mesh.faceCount, corners: mesh.cornerCount },
parts: { count: partCount, closed: closedParts, cavities },
valence: topology.valence,
quadQuality: topology.quadQuality,
topologyScore: computeTopologyScore(mesh, ok, topology),
tags: tagCounts(mesh),
bounds,
problems: problemList,
...(skippedChecks ? { skippedChecks } : {}),
};
}
function computeTopologyScore(mesh, ok, { valence, quadQuality }) {
if (!ok || mesh.faceCount === 0) return 0;
let quadCount = 0;
for (let face = 0; face < mesh.faceCount; face++) {
if (mesh.faceOffsets[face + 1] - mesh.faceOffsets[face] === 4) quadCount++;
}
const quadShare = quadCount / mesh.faceCount;
const interiorVertices = valence.regular + valence.poles3 + valence.poles5 + valence.poles6Plus;
const regularShare = interiorVertices > 0 ? (valence.regular + 0.5 * valence.poles3 + 0.5 * valence.poles5) / interiorVertices : 1;
const angleHealth = Math.max(0, 1 - quadQuality.meanAngleError / 60);
const warpHealth = Math.max(0, 1 - quadQuality.maxWarp / 90);
const shapeHealth = (angleHealth + warpHealth) / 2;
return roundMetric(0.5 * quadShare + 0.25 * regularShare + 0.25 * shapeHealth);
}