3D engine that AI agents drive
JavaScript 3d3d-engineagentic-aiai-agentsblenderclaude-codegame-enginegaussian-splattinggltfjavascriptmcpmcp-servermodel-context-protocolpath-tracerpath-tracingpbrrenderingthreejs-alternativewebgl2webgpu
import { createMeshData, DOMAINS } from './mesh-data.js';
// Mutable polygon topology in BMesh's model, stored as typed arrays indexed by element number.
//
// Vertex v: position, and one "edge slot" in its disk cycle (-1 when loose).
// Edge e: two endpoint slots, 2e and 2e+1. Slot s belongs to vertex edgeVertex[s]. diskNext/diskPrev link the slots
// around one vertex, which plays the role of BMesh's v1_disk_link and v2_disk_link. edgeLoop is one loop of the
// radial cycle (-1 for a wire edge).
// Loop l: one face corner. loopVertex is the corner's vertex, loopEdge runs from it to the next corner's vertex.
// loopNext/loopPrev walk the face, loopRadialNext/Prev walk the faces sharing loopEdge.
// Face f: one loop and the corner count.
// Removed elements are flagged and recycled through free lists; toMeshData() compacts.
const INITIAL_CAPACITY = 16;
function grow(array, capacity, fill) {
const next = new array.constructor(capacity);
next.set(array);
if (fill !== undefined) next.fill(fill, array.length);
return next;
}
class ElementStore {
constructor(fields, capacity) {
this.fields = fields;
this.capacity = capacity;
this.count = 0;
this.liveCount = 0;
this.free = [];
this.removed = new Uint8Array(capacity);
this.arrays = {};
for (const [name, { type, width, fill }] of Object.entries(fields)) {
this.arrays[name] = new type(capacity * width);
if (fill !== undefined) this.arrays[name].fill(fill);
}
this.attributes = new Map();
}
ensureCapacity(required) {
if (required <= this.capacity) return;
let capacity = this.capacity;
while (capacity < required) capacity *= 2;
for (const [name, { width, fill }] of Object.entries(this.fields)) {
this.arrays[name] = grow(this.arrays[name], capacity * width, fill);
}
for (const attribute of this.attributes.values()) {
attribute.data = grow(attribute.data, capacity * attribute.size);
}
this.removed = grow(this.removed, capacity);
this.capacity = capacity;
}
allocate() {
let index;
if (this.free.length) {
index = this.free.pop();
this.removed[index] = 0;
} else {
this.ensureCapacity(this.count + 1);
index = this.count;
this.count++;
}
for (const attribute of this.attributes.values()) {
attribute.data.fill(0, index * attribute.size, (index + 1) * attribute.size);
}
this.liveCount++;
return index;
}
release(index) {
this.removed[index] = 1;
this.free.push(index);
this.liveCount--;
}
isLive(index) {
return Number.isInteger(index) && index >= 0 && index < this.count && !this.removed[index];
}
requireLive(index, label) {
if (!this.isLive(index)) throw new RangeError(`${label} ${index} does not exist or was already removed.`);
}
}
export class EditMesh {
constructor(capacities = {}) {
this.vertices = new ElementStore({
position: { type: Float32Array, width: 3 },
edgeSlot: { type: Int32Array, width: 1, fill: -1 },
}, Math.max(INITIAL_CAPACITY, capacities.vertices ?? 0));
this.edges = new ElementStore({
vertex: { type: Int32Array, width: 2, fill: -1 },
diskNext: { type: Int32Array, width: 2, fill: -1 },
diskPrev: { type: Int32Array, width: 2, fill: -1 },
loop: { type: Int32Array, width: 1, fill: -1 },
}, Math.max(INITIAL_CAPACITY, capacities.edges ?? 0));
this.loops = new ElementStore({
vertex: { type: Int32Array, width: 1 },
edge: { type: Int32Array, width: 1 },
face: { type: Int32Array, width: 1 },
next: { type: Int32Array, width: 1 },
prev: { type: Int32Array, width: 1 },
radialNext: { type: Int32Array, width: 1 },
radialPrev: { type: Int32Array, width: 1 },
}, Math.max(INITIAL_CAPACITY, capacities.loops ?? 0));
this.faces = new ElementStore({
loop: { type: Int32Array, width: 1, fill: -1 },
size: { type: Int32Array, width: 1 },
}, Math.max(INITIAL_CAPACITY, capacities.faces ?? 0));
}
storeForDomain(domain) {
if (domain === 'point') return this.vertices;
if (domain === 'edge') return this.edges;
if (domain === 'face') return this.faces;
if (domain === 'corner') return this.loops;
throw new RangeError(`Unknown domain ${domain}.`);
}
/** Add (or return) a per-element attribute array that grows with the domain. */
ensureAttribute(domain, name, type = Float32Array, size = 1) {
const store = this.storeForDomain(domain);
let attribute = store.attributes.get(name);
if (attribute) {
if (attribute.data.constructor !== type || attribute.size !== size) throw new TypeError(`Attribute ${name} already exists with another type or size.`);
return attribute;
}
attribute = { data: new type(store.capacity * size), size };
store.attributes.set(name, attribute);
return attribute;
}
attribute(domain, name) {
return this.storeForDomain(domain).attributes.get(name);
}
get vertexCount() { return this.vertices.liveCount; }
get edgeCount() { return this.edges.liveCount; }
get faceCount() { return this.faces.liveCount; }
get loopCount() { return this.loops.liveCount; }
// ----- vertices -----
createVertex(x, y, z) {
const vertex = this.vertices.allocate();
const position = this.vertices.arrays.position;
position[vertex * 3] = x;
position[vertex * 3 + 1] = y;
position[vertex * 3 + 2] = z;
this.vertices.arrays.edgeSlot[vertex] = -1;
return vertex;
}
vertexPosition(vertex, target = [0, 0, 0]) {
const position = this.vertices.arrays.position;
target[0] = position[vertex * 3];
target[1] = position[vertex * 3 + 1];
target[2] = position[vertex * 3 + 2];
return target;
}
setVertexPosition(vertex, x, y, z) {
const position = this.vertices.arrays.position;
position[vertex * 3] = x;
position[vertex * 3 + 1] = y;
position[vertex * 3 + 2] = z;
}
// ----- disk cycles -----
slotVertex(slot) {
return this.edges.arrays.vertex[slot];
}
/** Edges around a vertex, in disk order. */
vertexEdges(vertex) {
const result = [];
const first = this.vertices.arrays.edgeSlot[vertex];
if (first === -1) return result;
const diskNext = this.edges.arrays.diskNext;
let slot = first;
do {
result.push(slot >> 1);
slot = diskNext[slot];
} while (slot !== first);
return result;
}
vertexDegree(vertex) {
const first = this.vertices.arrays.edgeSlot[vertex];
if (first === -1) return 0;
const diskNext = this.edges.arrays.diskNext;
let count = 0;
let slot = first;
do {
count++;
slot = diskNext[slot];
} while (slot !== first);
return count;
}
/** The edge between two vertices, or -1. Walks the first vertex's disk cycle, as BM_edge_exists does. */
findEdge(first, second) {
const start = this.vertices.arrays.edgeSlot[first];
if (start === -1) return -1;
const diskNext = this.edges.arrays.diskNext;
const edgeVertex = this.edges.arrays.vertex;
let slot = start;
do {
if (edgeVertex[slot ^ 1] === second) return slot >> 1;
slot = diskNext[slot];
} while (slot !== start);
return -1;
}
linkSlot(slot) {
const vertex = this.edges.arrays.vertex[slot];
const edgeSlot = this.vertices.arrays.edgeSlot;
const diskNext = this.edges.arrays.diskNext;
const diskPrev = this.edges.arrays.diskPrev;
const first = edgeSlot[vertex];
if (first === -1) {
diskNext[slot] = slot;
diskPrev[slot] = slot;
edgeSlot[vertex] = slot;
return;
}
const last = diskPrev[first];
diskNext[last] = slot;
diskPrev[slot] = last;
diskNext[slot] = first;
diskPrev[first] = slot;
}
unlinkSlot(slot) {
const vertex = this.edges.arrays.vertex[slot];
const edgeSlot = this.vertices.arrays.edgeSlot;
const diskNext = this.edges.arrays.diskNext;
const diskPrev = this.edges.arrays.diskPrev;
const next = diskNext[slot];
if (next === slot) {
edgeSlot[vertex] = -1;
} else {
const previous = diskPrev[slot];
diskNext[previous] = next;
diskPrev[next] = previous;
if (edgeSlot[vertex] === slot) edgeSlot[vertex] = next;
}
diskNext[slot] = -1;
diskPrev[slot] = -1;
}
// ----- edges -----
/** Return the edge between two distinct vertices, creating a wire edge when none exists. */
ensureEdge(first, second) {
if (first === second) throw new RangeError('An edge needs two distinct vertices.');
const existing = this.findEdge(first, second);
if (existing !== -1) return existing;
const edge = this.edges.allocate();
this.edges.arrays.vertex[edge * 2] = first;
this.edges.arrays.vertex[edge * 2 + 1] = second;
this.edges.arrays.loop[edge] = -1;
this.linkSlot(edge * 2);
this.linkSlot(edge * 2 + 1);
return edge;
}
edgeVertices(edge) {
return [this.edges.arrays.vertex[edge * 2], this.edges.arrays.vertex[edge * 2 + 1]];
}
edgeOtherVertex(edge, vertex) {
const vertices = this.edges.arrays.vertex;
return vertices[edge * 2] === vertex ? vertices[edge * 2 + 1] : vertices[edge * 2];
}
/** Loops in the radial cycle of an edge: one per face using it. */
edgeLoops(edge) {
const result = [];
const first = this.edges.arrays.loop[edge];
if (first === -1) return result;
const radialNext = this.loops.arrays.radialNext;
let loop = first;
do {
result.push(loop);
loop = radialNext[loop];
} while (loop !== first);
return result;
}
edgeFaceCount(edge) {
const first = this.edges.arrays.loop[edge];
if (first === -1) return 0;
const radialNext = this.loops.arrays.radialNext;
let count = 0;
let loop = first;
do {
count++;
loop = radialNext[loop];
} while (loop !== first);
return count;
}
removeEdge(edge) {
this.edges.requireLive(edge, 'Edge');
while (this.edges.arrays.loop[edge] !== -1) {
this.removeFace(this.loops.arrays.face[this.edges.arrays.loop[edge]]);
}
this.unlinkSlot(edge * 2);
this.unlinkSlot(edge * 2 + 1);
this.edges.release(edge);
}
// ----- loops and faces -----
linkRadial(loop, edge) {
const edgeLoop = this.edges.arrays.loop;
const radialNext = this.loops.arrays.radialNext;
const radialPrev = this.loops.arrays.radialPrev;
const first = edgeLoop[edge];
if (first === -1) {
radialNext[loop] = loop;
radialPrev[loop] = loop;
edgeLoop[edge] = loop;
return;
}
const last = radialPrev[first];
radialNext[last] = loop;
radialPrev[loop] = last;
radialNext[loop] = first;
radialPrev[first] = loop;
}
unlinkRadial(loop) {
const edge = this.loops.arrays.edge[loop];
const edgeLoop = this.edges.arrays.loop;
const radialNext = this.loops.arrays.radialNext;
const radialPrev = this.loops.arrays.radialPrev;
const next = radialNext[loop];
if (next === loop) {
edgeLoop[edge] = -1;
return;
}
const previous = radialPrev[loop];
radialNext[previous] = next;
radialPrev[next] = previous;
if (edgeLoop[edge] === loop) edgeLoop[edge] = next;
}
/**
* Create a face over existing vertices in winding order, creating missing edges.
* Returns the face index. Rejects repeated vertices and duplicate faces over the same vertex cycle.
*/
createFace(vertices) {
const size = vertices.length;
if (size < 3) throw new RangeError('A face needs at least three vertices.');
if (new Set(vertices).size !== size) throw new RangeError('A face cannot repeat a vertex.');
for (const vertex of vertices) {
if (!this.vertices.isLive(vertex)) throw new RangeError(`Vertex ${vertex} does not exist.`);
}
if (this.faceExists(vertices)) throw new RangeError('A face over these vertices already exists.');
const edges = new Array(size);
for (let corner = 0; corner < size; corner++) {
edges[corner] = this.ensureEdge(vertices[corner], vertices[(corner + 1) % size]);
}
const face = this.faces.allocate();
const loopArrays = this.loops.arrays;
let firstLoop = -1;
let previousLoop = -1;
for (let corner = 0; corner < size; corner++) {
const loop = this.loops.allocate();
loopArrays.vertex[loop] = vertices[corner];
loopArrays.edge[loop] = edges[corner];
loopArrays.face[loop] = face;
if (previousLoop === -1) {
firstLoop = loop;
} else {
loopArrays.next[previousLoop] = loop;
loopArrays.prev[loop] = previousLoop;
}
previousLoop = loop;
this.linkRadial(loop, edges[corner]);
}
loopArrays.next[previousLoop] = firstLoop;
loopArrays.prev[firstLoop] = previousLoop;
this.faces.arrays.loop[face] = firstLoop;
this.faces.arrays.size[face] = size;
return face;
}
/** Whether a face already uses exactly these vertices in any order, as BM_face_exists does. */
faceExists(vertices) {
const firstEdge = this.findEdge(vertices[0], vertices[1]);
if (firstEdge === -1) return false;
const wanted = new Set(vertices);
return this.edgeLoops(firstEdge).some(loop => {
const face = this.loops.arrays.face[loop];
return this.faces.arrays.size[face] === vertices.length && this.faceVertices(face).every(vertex => wanted.has(vertex));
});
}
/** Remove a face and its loops. Edges and vertices stay, as BM_face_kill. */
removeFace(face) {
this.faces.requireLive(face, 'Face');
const loopArrays = this.loops.arrays;
const first = this.faces.arrays.loop[face];
let loop = first;
do {
const next = loopArrays.next[loop];
this.unlinkRadial(loop);
this.loops.release(loop);
loop = next;
} while (loop !== first);
this.faces.arrays.loop[face] = -1;
this.faces.release(face);
}
/** Remove a vertex together with every edge and face using it. */
removeVertex(vertex) {
this.vertices.requireLive(vertex, 'Vertex');
while (this.vertices.arrays.edgeSlot[vertex] !== -1) {
this.removeEdge(this.vertices.arrays.edgeSlot[vertex] >> 1);
}
this.vertices.release(vertex);
}
faceLoops(face) {
const result = [];
const next = this.loops.arrays.next;
const first = this.faces.arrays.loop[face];
let loop = first;
do {
result.push(loop);
loop = next[loop];
} while (loop !== first);
return result;
}
faceVertices(face) {
return this.faceLoops(face).map(loop => this.loops.arrays.vertex[loop]);
}
/** Faces sharing an edge with the given face (each neighbour listed once). */
faceNeighbors(face) {
const neighbors = new Set();
for (const loop of this.faceLoops(face)) {
for (const other of this.edgeLoops(this.loops.arrays.edge[loop])) {
const otherFace = this.loops.arrays.face[other];
if (otherFace !== face) neighbors.add(otherFace);
}
}
return [...neighbors];
}
*liveIndices(domain) {
const store = this.storeForDomain(domain);
for (let index = 0; index < store.count; index++) {
if (!store.removed[index]) yield index;
}
}
}
function reserve(store, count) {
store.ensureCapacity(count);
store.count = count;
store.liveCount = count;
}
/**
* Build an EditMesh from MeshData in one pass over typed arrays, keeping element order (vertex, edge, face and loop
* indices equal MeshData's vertex, edge, face and corner indices) and copying every attribute.
*/
export function editMesh(mesh) {
const edit = new EditMesh({
vertices: mesh.vertexCount, edges: mesh.edgeCount, loops: mesh.cornerCount, faces: mesh.faceCount,
});
for (const domain of DOMAINS) {
for (const [name, attribute] of Object.entries(mesh.attributes[domain])) {
edit.ensureAttribute(domain, name, attribute.data.constructor, attribute.size);
}
}
reserve(edit.vertices, mesh.vertexCount);
reserve(edit.edges, mesh.edgeCount);
reserve(edit.loops, mesh.cornerCount);
reserve(edit.faces, mesh.faceCount);
edit.vertices.arrays.position.set(mesh.positions);
const edgeVertex = edit.edges.arrays.vertex;
for (let edge = 0; edge < mesh.edgeCount; edge++) {
const first = mesh.edgeVertices[edge * 2];
const second = mesh.edgeVertices[edge * 2 + 1];
if (edit.findEdge(first, second) !== -1) throw new RangeError(`MeshData has a duplicate edge at ${edge}.`);
edgeVertex[edge * 2] = first;
edgeVertex[edge * 2 + 1] = second;
edit.linkSlot(edge * 2);
edit.linkSlot(edge * 2 + 1);
}
const loopArrays = edit.loops.arrays;
const faceLoop = edit.faces.arrays.loop;
const faceSize = edit.faces.arrays.size;
for (let face = 0; face < mesh.faceCount; face++) {
const start = mesh.faceOffsets[face];
const end = mesh.faceOffsets[face + 1];
faceLoop[face] = start;
faceSize[face] = end - start;
for (let corner = start; corner < end; corner++) {
loopArrays.vertex[corner] = mesh.cornerVertices[corner];
loopArrays.edge[corner] = mesh.cornerEdges[corner];
loopArrays.face[corner] = face;
loopArrays.next[corner] = corner + 1 === end ? start : corner + 1;
loopArrays.prev[corner] = corner === start ? end - 1 : corner - 1;
edit.linkRadial(corner, mesh.cornerEdges[corner]);
}
}
for (const domain of DOMAINS) {
const store = edit.storeForDomain(domain);
for (const [name, attribute] of Object.entries(mesh.attributes[domain])) {
store.attributes.get(name).data.set(attribute.data);
}
}
return edit;
}
function compactAttribute(attribute, liveIndices) {
const size = attribute.size;
const data = new attribute.data.constructor(liveIndices.length * size);
for (let output = 0; output < liveIndices.length; output++) {
const input = liveIndices[output];
for (let component = 0; component < size; component++) {
data[output * size + component] = attribute.data[input * size + component];
}
}
return { data, size };
}
function liveIndexArray(store) {
const live = new Uint32Array(store.liveCount);
let output = 0;
for (let index = 0; index < store.count; index++) {
if (store.removed[index]) continue;
live[output] = index;
output++;
}
return live;
}
/** Compact an EditMesh into immutable MeshData. Loose vertices are kept; wire edges are dropped. */
export function meshData(edit) {
const liveVertices = liveIndexArray(edit.vertices);
if (!liveVertices.length) throw new RangeError('The mesh has no vertices left.');
const vertexMap = new Int32Array(edit.vertices.count).fill(-1);
for (let output = 0; output < liveVertices.length; output++) vertexMap[liveVertices[output]] = output;
const sourcePositions = edit.vertices.arrays.position;
const positions = new Float32Array(liveVertices.length * 3);
for (let output = 0; output < liveVertices.length; output++) {
const input = liveVertices[output];
positions[output * 3] = sourcePositions[input * 3];
positions[output * 3 + 1] = sourcePositions[input * 3 + 1];
positions[output * 3 + 2] = sourcePositions[input * 3 + 2];
}
const liveFaces = liveIndexArray(edit.faces);
if (!liveFaces.length) throw new RangeError('The mesh has no faces left.');
const faceOffsets = new Uint32Array(liveFaces.length + 1);
const faceSize = edit.faces.arrays.size;
for (let output = 0; output < liveFaces.length; output++) {
faceOffsets[output + 1] = faceOffsets[output] + faceSize[liveFaces[output]];
}
const cornerCount = faceOffsets[liveFaces.length];
const cornerVertices = new Uint32Array(cornerCount);
const cornerEdges = new Uint32Array(cornerCount);
const liveLoops = new Uint32Array(cornerCount);
const edgeMap = new Int32Array(edit.edges.count).fill(-1);
const liveEdges = new Uint32Array(edit.edges.liveCount);
let liveEdgeCount = 0;
const loopArrays = edit.loops.arrays;
const faceLoop = edit.faces.arrays.loop;
let corner = 0;
for (let output = 0; output < liveFaces.length; output++) {
const first = faceLoop[liveFaces[output]];
let loop = first;
do {
const edge = loopArrays.edge[loop];
if (edgeMap[edge] === -1) {
edgeMap[edge] = liveEdgeCount;
liveEdges[liveEdgeCount] = edge;
liveEdgeCount++;
}
cornerVertices[corner] = vertexMap[loopArrays.vertex[loop]];
cornerEdges[corner] = edgeMap[edge];
liveLoops[corner] = loop;
corner++;
loop = loopArrays.next[loop];
} while (loop !== first);
}
const keptEdges = liveEdges.subarray(0, liveEdgeCount);
const edgeVertices = new Uint32Array(liveEdgeCount * 2);
const sourceEdgeVertex = edit.edges.arrays.vertex;
for (let output = 0; output < liveEdgeCount; output++) {
const edge = keptEdges[output];
edgeVertices[output * 2] = vertexMap[sourceEdgeVertex[edge * 2]];
edgeVertices[output * 2 + 1] = vertexMap[sourceEdgeVertex[edge * 2 + 1]];
}
const liveByDomain = { point: liveVertices, edge: keptEdges, face: liveFaces, corner: liveLoops };
const attributes = {};
for (const domain of DOMAINS) {
attributes[domain] = {};
for (const [name, attribute] of edit.storeForDomain(domain).attributes) {
attributes[domain][name] = compactAttribute(attribute, liveByDomain[domain]);
}
}
return createMeshData({ positions, faceOffsets, cornerVertices, edgeVertices, cornerEdges, attributes });
}