3D engine that AI agents drive
JavaScript 3d3d-engineagentic-aiai-agentsblenderclaude-codegame-enginegaussian-splattinggltfjavascriptmcpmcp-servermodel-context-protocolpath-tracerpath-tracingpbrrenderingthreejs-alternativewebgl2webgpu
import test from 'node:test';
import assert from 'node:assert/strict';
import { clipFlushOverlaps, FLUSH_CUT_STRIDE } from '../src/flush-clip.js';
// A unit square on the plane y = 0 as two triangles, with a UV, a colour and a sky value that are linear in x and z.
function squareGeometry() {
const corners = [[0, 0], [0, 1], [1, 1], [1, 0]];
return {
positions: new Float32Array(corners.flatMap(([x, z]) => [x, 0, z])),
normals: new Float32Array(corners.flatMap(() => [0, 1, 0])),
uvs: new Float32Array(corners.flatMap(([x, z]) => [x, z])),
colors: new Float32Array(corners.flatMap(([x, z]) => [x, z, 0.5])),
skyVisibility: new Float32Array(corners.map(([x, z]) => 0.25 * x + 0.5 * z)),
indices: new Uint32Array([0, 1, 2, 0, 2, 3]),
};
}
// One cut per triangle of the square for every winner, sorted by the triangle that is cut.
function cutsOf(winners, triangles = [0, 1]) {
const cuts = [];
for (const triangle of triangles) {
for (const winner of winners) cuts.push(triangle, ...winner.flatMap(([x, z]) => [x, 0, z]));
}
assert.equal(cuts.length % FLUSH_CUT_STRIDE, 0);
return new Float64Array(cuts);
}
function triangleNormalAndArea(positions, indices, triangle) {
const [first, second, third] = [0, 1, 2].map(corner => indices[triangle * 3 + corner] * 3);
const edgeOne = [0, 1, 2].map(axis => positions[second + axis] - positions[first + axis]);
const edgeTwo = [0, 1, 2].map(axis => positions[third + axis] - positions[first + axis]);
const normal = [edgeOne[1] * edgeTwo[2] - edgeOne[2] * edgeTwo[1], edgeOne[2] * edgeTwo[0] - edgeOne[0] * edgeTwo[2], edgeOne[0] * edgeTwo[1] - edgeOne[1] * edgeTwo[0]];
return { normal, area: Math.hypot(...normal) / 2 };
}
function areaOf(geometry) {
let area = 0;
for (let triangle = 0; triangle < geometry.indices.length / 3; triangle++) area += triangleNormalAndArea(geometry.positions, geometry.indices, triangle).area;
return area;
}
const INSIDE = [[0.25, 0.25], [0.25, 0.75], [0.75, 0.25]];
const ACROSS_THE_CORNER = [[0.5, 0.5], [0.5, 1.5], [1.5, 0.5]];
test('what is left of the cut face and the face that covers it add up to the area of their union', () => {
for (const { winner, shared } of [{ winner: INSIDE, shared: 0.125 }, { winner: ACROSS_THE_CORNER, shared: 0.25 }]) {
const square = squareGeometry();
const { geometry, sources } = clipFlushOverlaps(square, cutsOf([winner]));
assert.notEqual(geometry, square);
const winnerArea = 0.5 * (winner[1][1] - winner[0][1]) * (winner[2][0] - winner[0][0]);
const union = 1 + winnerArea - shared;
assert.ok(Math.abs(areaOf(geometry) + winnerArea - union) < 1e-6, `clipped ${areaOf(geometry)} against ${1 - shared}`);
assert.equal(sources.length, geometry.indices.length / 3);
assert.ok(sources.every(source => source === 0 || source === 1));
}
});
test('two winners that overlap each other are still cut out once', () => {
const square = squareGeometry();
const second = [[0.25, 0.25], [0.75, 0.25], [0.75, 0.75]].map(([x, z]) => [x, z]);
// INSIDE and `second` share the triangle between the centre and the edge z = 0.25: their union is 3/16.
const { geometry } = clipFlushOverlaps(square, cutsOf([INSIDE, [second[0], second[2], second[1]]]));
// Each cut stops four float32 steps inside its winner, which is worth about 1e-6 of area along these edges.
assert.ok(Math.abs(areaOf(geometry) - (1 - 3 / 16)) < 2e-6);
});
test('every per-vertex array is interpolated for the new vertices, and the old vertices are kept as they were', () => {
const square = squareGeometry();
const { geometry } = clipFlushOverlaps(square, cutsOf([INSIDE]));
const vertexCount = geometry.positions.length / 3;
assert.ok(vertexCount > 4);
assert.deepEqual(Array.from(geometry.positions.subarray(0, 12)), Array.from(square.positions));
for (const [field, stride] of [['normals', 3], ['uvs', 2], ['colors', 3], ['skyVisibility', 1]]) {
assert.equal(geometry[field].length, vertexCount * stride, field);
assert.ok(geometry[field] instanceof Float32Array);
}
for (let vertex = 0; vertex < vertexCount; vertex++) {
const x = geometry.positions[vertex * 3];
const z = geometry.positions[vertex * 3 + 2];
assert.equal(geometry.positions[vertex * 3 + 1], 0);
assert.deepEqual(Array.from(geometry.normals.subarray(vertex * 3, vertex * 3 + 3)), [0, 1, 0]);
assert.ok(Math.abs(geometry.uvs[vertex * 2] - x) < 1e-6 && Math.abs(geometry.uvs[vertex * 2 + 1] - z) < 1e-6);
assert.ok(Math.abs(geometry.colors[vertex * 3] - x) < 1e-6 && Math.abs(geometry.colors[vertex * 3 + 2] - 0.5) < 1e-6);
assert.ok(Math.abs(geometry.skyVisibility[vertex] - (0.25 * x + 0.5 * z)) < 1e-6);
}
});
test('the pieces keep the winding of the face they were cut from', () => {
const { geometry } = clipFlushOverlaps(squareGeometry(), cutsOf([ACROSS_THE_CORNER]));
for (let triangle = 0; triangle < geometry.indices.length / 3; triangle++) {
assert.ok(triangleNormalAndArea(geometry.positions, geometry.indices, triangle).normal[1] > 0);
}
});
test('untouched geometry keeps its identity', () => {
const square = squareGeometry();
assert.deepEqual(clipFlushOverlaps(square, new Float64Array(0)), { geometry: square, sources: null });
const beside = [[2, 0], [2, 1], [3, 0]];
assert.equal(clipFlushOverlaps(square, cutsOf([beside])).geometry, square, 'a winner that does not reach the face cuts nothing');
const alongTheEdge = [[1, 0], [1, 1], [2, 0]];
assert.equal(clipFlushOverlaps(square, cutsOf([alongTheEdge])).geometry, square, 'sharing an edge is not covering');
});
test('a fully covered triangle is dropped, and the other triangles keep their vertices', () => {
const square = squareGeometry();
const firstTriangle = [[0, 0], [0, 1], [1, 1]];
const { geometry, sources } = clipFlushOverlaps(square, cutsOf([firstTriangle], [0]));
assert.deepEqual(Array.from(geometry.indices), [0, 2, 3]);
assert.deepEqual(Array.from(sources), [1]);
assert.equal(geometry.positions.length, square.positions.length, 'no vertex was needed');
const everything = [[-1, -1], [-1, 3], [3, -1]];
assert.equal(clipFlushOverlaps(square, cutsOf([everything])).geometry.indices.length, 0);
});
test('the same cuts on the same geometry return the same object', () => {
const square = squareGeometry();
const first = clipFlushOverlaps(square, cutsOf([INSIDE]));
assert.equal(clipFlushOverlaps(square, cutsOf([INSIDE])), first);
assert.notEqual(clipFlushOverlaps(square, cutsOf([ACROSS_THE_CORNER])), first);
assert.notEqual(clipFlushOverlaps(squareGeometry(), cutsOf([INSIDE])), first);
});
test('a cut stops a few float32 steps inside the winner, so the two faces overlap instead of opening a seam', () => {
const square = squareGeometry();
const { geometry } = clipFlushOverlaps(square, cutsOf([INSIDE]), 1e-4);
// With a coordinate step of 0.1 mm the hole is the winner pulled in by 0.4 mm on each of its three edges.
const inradius = 2 * 0.125 / (0.5 + 0.5 + Math.SQRT1_2);
const shrunk = 0.125 * ((inradius - 4e-4) / inradius) ** 2;
assert.ok(Math.abs(1 - areaOf(geometry) - shrunk) < 1e-6);
});