3D engine that AI agents drive
JavaScript 3d3d-engineagentic-aiai-agentsblenderclaude-codegame-enginegaussian-splattinggltfjavascriptmcpmcp-servermodel-context-protocolpath-tracerpath-tracingpbrrenderingthreejs-alternativewebgl2webgpu
// Ear clipping for a simple contour with disjoint holes. Points are [x, y]; triangles come back counter-clockwise.
function cross(origin, first, second) {
return (first[0] - origin[0]) * (second[1] - origin[1]) - (first[1] - origin[1]) * (second[0] - origin[0]);
}
export function signedArea(ring) {
let area = 0;
for (let index = 0, previous = ring.length - 1; index < ring.length; previous = index++) {
area += ring[previous][0] * ring[index][1] - ring[index][0] * ring[previous][1];
}
return area / 2;
}
function samePosition(first, second) {
return first[0] === second[0] && first[1] === second[1];
}
function segmentsTouch(startA, endA, startB, endB) {
const sideStartB = cross(startA, endA, startB);
const sideEndB = cross(startA, endA, endB);
const sideStartA = cross(startB, endB, startA);
const sideEndA = cross(startB, endB, endA);
if (Math.sign(sideStartB) * Math.sign(sideEndB) < 0 && Math.sign(sideStartA) * Math.sign(sideEndA) < 0) return true;
const within = (from, to, point) => point[0] >= Math.min(from[0], to[0]) && point[0] <= Math.max(from[0], to[0]) &&
point[1] >= Math.min(from[1], to[1]) && point[1] <= Math.max(from[1], to[1]);
return sideStartB === 0 && within(startA, endA, startB) || sideEndB === 0 && within(startA, endA, endB) ||
sideStartA === 0 && within(startB, endB, startA) || sideEndA === 0 && within(startB, endB, endA);
}
// True when the direction toward target leaves the vertex into the region on the left of the ring.
function pointsIntoRegion(previous, vertex, next, target) {
if (cross(previous, vertex, next) > 0) return cross(vertex, next, target) > 0 && cross(vertex, target, previous) > 0;
return !(cross(vertex, previous, target) > 0 && cross(vertex, target, next) > 0);
}
function crossesBoundary(points, rings, from, to, ignoredA, ignoredB) {
for (const ring of rings) {
for (let index = 0; index < ring.length; index++) {
const start = ring[index];
const end = ring[(index + 1) % ring.length];
if (start === ignoredA || end === ignoredA || start === ignoredB || end === ignoredB) continue;
if (segmentsTouch(points[from], points[to], points[start], points[end])) return true;
}
}
return false;
}
function bridgeHole(points, rings, merged, hole) {
let holeStart = 0;
for (let index = 1; index < hole.length; index++) {
if (points[hole[index]][0] > points[hole[holeStart]][0]) holeStart = index;
}
const holeVertex = hole[holeStart];
const holePrevious = hole[(holeStart + hole.length - 1) % hole.length];
const holeNext = hole[(holeStart + 1) % hole.length];
const candidates = [...new Set(merged)]
.map(vertex => ({ vertex, distance: Math.hypot(points[vertex][0] - points[holeVertex][0], points[vertex][1] - points[holeVertex][1]) }))
.sort((left, right) => left.distance - right.distance);
for (const { vertex } of candidates) {
if (!pointsIntoRegion(points[holePrevious], points[holeVertex], points[holeNext], points[vertex])) continue;
if (crossesBoundary(points, rings, holeVertex, vertex, holeVertex, vertex)) continue;
for (let position = 0; position < merged.length; position++) {
if (merged[position] !== vertex) continue;
const previous = points[merged[(position + merged.length - 1) % merged.length]];
const next = points[merged[(position + 1) % merged.length]];
if (!pointsIntoRegion(previous, points[vertex], next, points[holeVertex])) continue;
const rotated = hole.map((_, offset) => hole[(holeStart + offset) % hole.length]);
merged.splice(position + 1, 0, ...rotated, holeVertex, vertex);
return;
}
}
throw new RangeError('Triangulation could not connect a hole to the contour. Adjust the holes.');
}
function mergeHoles(points, outer, holes) {
const rings = [outer, ...holes];
const merged = [...outer];
const pending = holes.map(hole => hole.slice()).sort((left, right) => {
const rightmost = ring => Math.max(...ring.map(vertex => points[vertex][0]));
return rightmost(right) - rightmost(left);
});
for (const hole of pending) bridgeHole(points, rings, merged, hole);
return merged;
}
function clipEars(points, ring) {
const count = ring.length;
const previousOf = Array.from({ length: count }, (_, index) => (index + count - 1) % count);
const nextOf = Array.from({ length: count }, (_, index) => (index + 1) % count);
const triangles = [];
const at = slot => points[ring[slot]];
const isCoincident = (slot, tip) => [previousOf[tip], tip, nextOf[tip]].some(corner => samePosition(at(slot), at(corner)));
const containsOtherVertex = tip => {
const first = at(previousOf[tip]);
const second = at(tip);
const third = at(nextOf[tip]);
for (let slot = nextOf[nextOf[tip]]; slot !== previousOf[tip]; slot = nextOf[slot]) {
if (isCoincident(slot, tip)) continue;
if (cross(at(previousOf[slot]), at(slot), at(nextOf[slot])) > 0) continue;
const vertex = at(slot);
if (cross(first, second, vertex) >= 0 && cross(second, third, vertex) >= 0 && cross(third, first, vertex) >= 0) return true;
}
return false;
};
const remove = tip => {
nextOf[previousOf[tip]] = nextOf[tip];
previousOf[nextOf[tip]] = previousOf[tip];
return previousOf[tip];
};
const emit = tip => triangles.push([ring[previousOf[tip]], ring[tip], ring[nextOf[tip]]]);
let remaining = count;
let cursor = 0;
let missed = 0;
while (remaining > 3) {
const area = cross(at(previousOf[cursor]), at(cursor), at(nextOf[cursor]));
const forced = missed > remaining;
if (area === 0) {
cursor = remove(cursor);
remaining--;
missed = 0;
} else if (area > 0 && (forced || !containsOtherVertex(cursor))) {
emit(cursor);
cursor = remove(cursor);
remaining--;
missed = 0;
} else {
cursor = nextOf[cursor];
missed++;
if (missed > remaining * 2) throw new RangeError('Triangulation failed. The contour or holes may touch or cross.');
}
}
if (cross(at(previousOf[cursor]), at(cursor), at(nextOf[cursor])) > 0) emit(cursor);
return triangles;
}
function assertFinitePoints(ring, label) {
ring.forEach((point, index) => {
if (!Number.isFinite(point[0]) || !Number.isFinite(point[1])) {
throw new RangeError(`triangulate ${label} point ${index} must have finite x and y, got [${point[0]}, ${point[1]}].`);
}
});
}
/** Vertex numbers follow the contour, then each hole in order. Returns counter-clockwise [a, b, c] triples. */
export function triangulate(contour, holes) {
if (contour.length === 0) throw new RangeError('triangulate needs a contour with points, got an empty contour. Pass [[x, y], ...].');
if (contour.length < 3) return [];
assertFinitePoints(contour, 'contour');
holes.forEach((hole, index) => assertFinitePoints(hole, `hole ${index}`));
const points = [...contour, ...holes.flat()];
const outerRing = contour.map((_, index) => index);
if (signedArea(contour) < 0) outerRing.reverse();
let offset = contour.length;
const holeRings = holes.map(hole => {
const ring = hole.map((_, index) => offset + index);
offset += hole.length;
if (signedArea(hole) > 0) ring.reverse();
return ring;
});
return clipEars(points, mergeHoles(points, outerRing, holeRings));
}