3D engine that AI agents drive
JavaScript 3d3d-engineagentic-aiai-agentsblenderclaude-codegame-enginegaussian-splattinggltfjavascriptmcpmcp-servermodel-context-protocolpath-tracerpath-tracingpbrrenderingthreejs-alternativewebgl2webgpu
import { facePolygons, buildPolygonMesh, boundaryLoops, faceOfCorner } from './mesh-polygons.js';
// bridge_edge_loops and grid_fill. Both work on boundary loops: chains of edges that have one face.
const MAX_GRID_VERTICES = 65536;
function position(mesh, extraPositions, vertex) {
if (vertex >= mesh.vertexCount) return extraPositions[vertex - mesh.vertexCount];
return [mesh.positions[vertex * 3], mesh.positions[vertex * 3 + 1], mesh.positions[vertex * 3 + 2]];
}
const lerp = (first, second, fraction) => first.map((value, axis) => value + (second[axis] - value) * fraction);
const distanceSquared = (first, second) => first.reduce((sum, value, axis) => sum + (value - second[axis]) ** 2, 0);
function newVertex(mesh, extraPositions, point, extraSources = null, source = -1) {
extraPositions.push(point);
extraSources?.push(source);
return mesh.vertexCount + extraPositions.length - 1;
}
function strip(vertices, sourceFace, tag) {
return { vertices, sourceFace, sourceCorners: vertices.map(() => -1), sourceEdges: vertices.map(() => -1), keepTags: false, tags: [tag] };
}
/** The shift of the second loop against the first that puts matching vertices closest together. */
function bestShift(mesh, first, second) {
let best = 0;
let bestCost = Infinity;
for (let shift = 0; shift < first.length; shift++) {
let cost = 0;
for (let index = 0; index < first.length; index++) {
cost += distanceSquared(position(mesh, [], first[index]), position(mesh, [], second[(index + shift) % second.length]));
}
if (cost < bestCost - 1e-12) {
best = shift;
bestCost = cost;
}
}
return best;
}
/**
* Join two boundary loops with a strip of quads, `segments` quads deep. The loops must have the same number of edges.
* Closed loops are matched at the rotation that puts vertices closest, then turned by `twist` vertices. The strip faces
* wind opposite to the faces already on each loop, so the result is a closed surface where both loops were holes.
* Strip faces get `<name>.bridge`.
*/
export function bridgeEdgeLoops(mesh, edgeMask, { segments = 1, twist = 0, name = 'bridge' } = {}) {
const loops = boundaryLoops(mesh, edgeMask);
if (loops.length !== 2) {
throw new RangeError(`The edge rule selects ${loops.length} boundary loops; bridge needs exactly 2. Use { "open": true } for every hole, or { "open": { "inside": { "min": [x, y, z], "max": [x, y, z] } } } to pick some.`);
}
const [first, second] = loops;
if (first.closed !== second.closed) throw new RangeError('One loop is closed and the other is an open chain; bridge needs two of the same kind.');
if (first.vertices.length !== second.vertices.length) {
throw new RangeError(`The loops have ${first.vertices.length} and ${second.vertices.length} edges; bridge needs the same number. Run subdivide_edges on the shorter one first.`);
}
const edgeCount = first.vertices.length;
const closed = first.closed;
if ((edgeCount + 1) * (segments + 1) > MAX_GRID_VERTICES) throw new RangeError('The bridge would make too many vertices. Lower segments.');
const near = chainPoints(mesh, first);
const farReversed = chainPoints(mesh, second).reverse();
const shift = closed ? (bestShift(mesh, near, farReversed) + (twist % edgeCount) + edgeCount) % edgeCount : 0;
const far = near.map((_, index) => farReversed[(index + shift) % farReversed.length]);
const extraPositions = [];
const extraSources = [];
const rows = [near];
for (let row = 1; row < segments; row++) {
rows.push(near.map((vertex, index) => newVertex(
mesh, extraPositions, lerp(position(mesh, extraPositions, vertex), position(mesh, extraPositions, far[index]), row / segments),
extraSources, { from: vertex, to: far[index], t: row / segments },
)));
}
rows.push(far);
const polygons = facePolygons(mesh);
const sourceFace = faceOfCorner(mesh, first.corners[0]);
for (let row = 0; row < segments; row++) {
for (let index = 0; index < edgeCount; index++) {
const next = (index + 1) % near.length;
polygons.push(strip([rows[row][next], rows[row][index], rows[row + 1][index], rows[row + 1][next]], sourceFace, `${name}.bridge`));
}
}
return { mesh: buildPolygonMesh(mesh, polygons, extraPositions, extraSources), loopEdges: edgeCount, strips: segments * edgeCount };
}
function faceNextCorner(mesh, corner) {
const face = faceOfCorner(mesh, corner);
return corner + 1 === mesh.faceOffsets[face + 1] ? mesh.faceOffsets[face] : corner + 1;
}
// A closed loop lists each vertex once; an open chain also needs the vertex its last edge ends on.
function chainPoints(mesh, loop) {
if (loop.closed) return [...loop.vertices];
const lastCorner = loop.corners[loop.corners.length - 1];
return [...loop.vertices, mesh.cornerVertices[faceNextCorner(mesh, lastCorner)]];
}
// ----- grid_fill -----
function turnAngle(mesh, previous, vertex, next) {
const before = position(mesh, [], vertex).map((value, axis) => value - position(mesh, [], previous)[axis]);
const after = position(mesh, [], next).map((value, axis) => value - position(mesh, [], vertex)[axis]);
const size = Math.hypot(...before) * Math.hypot(...after) || 1;
const cosine = before.reduce((sum, value, axis) => sum + value * after[axis], 0) / size;
return Math.acos(Math.max(-1, Math.min(1, cosine)));
}
/**
* The split of a loop of even length into sides a, b, a, b that puts the four corners on its sharpest turns. Splits whose
* grid would pass MAX_GRID_VERTICES are not tried, so a loop too long for any split fails instead of running for minutes.
*/
function chooseCorners(mesh, vertices) {
const count = vertices.length;
const turns = vertices.map((vertex, index) => turnAngle(mesh, vertices[(index + count - 1) % count], vertex, vertices[(index + 1) % count]));
let best = null;
for (let a = 1; a < count / 2; a++) {
const b = count / 2 - a;
if ((a + 1) * (b + 1) > MAX_GRID_VERTICES) continue;
for (let start = 0; start < count; start++) {
const score = turns[start] + turns[(start + a) % count] + turns[(start + a + b) % count] + turns[(start + 2 * a + b) % count]
- Math.abs(a - b) * 1e-6;
if (!best || score > best.score + 1e-9) best = { score, a, b, start };
}
}
if (!best) throw new RangeError(`A loop of ${count} edges would pass ${MAX_GRID_VERTICES} grid vertices. Use fill_holes.`);
return best;
}
function gridPolygons(mesh, loop, name, extraPositions) {
const vertices = loop.vertices;
const count = vertices.length;
const { a, b, start } = chooseCorners(mesh, vertices);
const at = offset => vertices[(start + offset) % count];
const grid = Array.from({ length: a + 1 }, () => new Array(b + 1));
for (let i = 0; i <= a; i++) {
grid[i][0] = at(i);
grid[i][b] = at(2 * a + b - i);
}
for (let j = 0; j <= b; j++) {
grid[a][j] = at(a + j);
grid[0][j] = at(count - j);
}
const corner = (i, j) => position(mesh, extraPositions, grid[i][j]);
for (let i = 1; i < a; i++) {
for (let j = 1; j < b; j++) {
const u = i / a;
const v = j / b;
const point = [0, 1, 2].map(axis => (1 - v) * corner(i, 0)[axis] + v * corner(i, b)[axis]
+ (1 - u) * corner(0, j)[axis] + u * corner(a, j)[axis]
- ((1 - u) * (1 - v) * corner(0, 0)[axis] + u * (1 - v) * corner(a, 0)[axis] + (1 - u) * v * corner(0, b)[axis] + u * v * corner(a, b)[axis]));
grid[i][j] = newVertex(mesh, extraPositions, point);
}
}
const sourceFace = faceOfCorner(mesh, loop.corners[0]);
const faces = [];
for (let i = 0; i < a; i++) {
for (let j = 0; j < b; j++) {
faces.push(strip([grid[i][j], grid[i][j + 1], grid[i + 1][j + 1], grid[i + 1][j]], sourceFace, `${name}.fill`));
}
}
return faces;
}
/**
* Fill each closed boundary loop of the selected edges with a grid of quads, which needs an even number of edges
* (at least 4). The loop is cut into four sides at its sharpest corners, opposite sides holding the same number of
* edges; inner points come from a Coons patch. Cells get `<name>.fill`.
*/
export function gridFill(mesh, edgeMask, { name = 'grid' } = {}) {
const loops = boundaryLoops(mesh, edgeMask);
if (loops.length === 0) throw new RangeError('The edge rule selects no boundary loop. Use { "open": true } to pick the holes.');
const polygons = facePolygons(mesh);
const extraPositions = [];
for (const loop of loops) {
const count = loop.vertices.length;
if (!loop.closed) throw new RangeError('A selected boundary chain is open; grid_fill needs closed loops.');
if (count < 4 || count % 2 !== 0) throw new RangeError(`A loop has ${count} edges; grid_fill needs an even number, at least 4. Subdivide one edge or use fill_holes.`);
for (const polygon of gridPolygons(mesh, loop, name, extraPositions)) polygons.push(polygon);
}
return { mesh: buildPolygonMesh(mesh, polygons, extraPositions), loops: loops.length };
}