3D engine that AI agents drive
JavaScript 3d3d-engineagentic-aiai-agentsblenderclaude-codegame-enginegaussian-splattinggltfjavascriptmcpmcp-servermodel-context-protocolpath-tracerpath-tracingpbrrenderingthreejs-alternativewebgl2webgpu
// Finds pairs of triangles that draw the same plane in the same place (issue #751): inside one part and across parts, exactly
// flush or a few millimetres to centimetres apart. Such pairs z-fight, since the rasteriser snaps two triangles on one plane to
// slightly different depths. flush-resolve.js turns the pairs into a draw rank per triangle.
//
// Triangles are hashed by their normal (sign folded, so opposite faces meet) and by a grid over their boxes. A triangle is
// native to the finest grid where it spans few cells and a guest in the coarser ones, so a wall of two triangles and the
// thousand small faces on it meet without the wall being listed in a thousand cells. Nothing is cut short silently: parts
// past the triangle budget come back in `unchecked`, and `truncated` says the pair budget ran out.
/** Shared area under this share of the smaller triangle is edge contact or rounding, not a fight. */
export const FLUSH_MINIMUM_AREA_SHARE = 1e-4;
const FLUSH_MINIMUM_AREA = 1e-8;
const DEFAULT_TRIANGLE_BUDGET = 2_000_000;
const DEFAULT_PAIR_BUDGET = 4_000_000;
const MAXIMUM_TESTED_PAIRS = 8_000_000;
const SWEEP_AXIS_LEAN = 0.5;
const SAME_FACING =Math.cos(Math.PI / 180);
// Normals one degree apart differ by at most 0.0175 per component. Each triangle is listed in every normal cell within half
// of that, so two such triangles always share a cell.
const NORMAL_STEPS = 20;
const NORMAL_REACH = 0.0088;
const NORMAL_RANGE = 2 * NORMAL_STEPS + 3;
const NEAR_DOMINANT = 0.02;
const NATIVE_CELL_LIMIT = 64;
const GRID_LEVEL_SCALE = 16;
const GRID_LEVELS = 2;
const CELL_SAMPLES = 4096;
// A JS Map holds at most 2^24 entries and throws a bare RangeError past it. The grid stops listing triangles at this many
// native cells and is built again with cells twice as wide, up to MAXIMUM_GRID_COARSENINGS times.
const MAXIMUM_GRID_ENTRIES = 16_000_000;
const MAXIMUM_GRID_COARSENINGS = 8;
// Tags whose vertex shader moves vertices (renderer.js DEFORMING_TAGS): their triangles are not where the geometry says.
const DEFORMING_TAGS = new Set(['foliage', 'grass', 'water', 'fire', 'smoke']);
const localBoundsByGeometry = new WeakMap();
export function localBounds(geometry) {
let bounds = localBoundsByGeometry.get(geometry);
if (bounds) return bounds;
bounds = [Infinity, Infinity, Infinity, -Infinity, -Infinity, -Infinity];
const { positions } = geometry;
for (let offset = 0; offset < positions.length; offset += 3) {
for (let axis = 0; axis < 3; axis++) {
bounds[axis] = Math.min(bounds[axis], positions[offset + axis]);
bounds[3 + axis] = Math.max(bounds[3 + axis], positions[offset + axis]);
}
}
localBoundsByGeometry.set(geometry, bounds);
return bounds;
}
export function worldBounds(part) {
const local = localBounds(part.geometry);
const matrix = part.matrix;
const bounds = [Infinity, Infinity, Infinity, -Infinity, -Infinity, -Infinity];
for (let corner = 0; corner < 8; corner++) {
const x = corner & 1 ? local[3] : local[0];
const y = corner & 2 ? local[4] : local[1];
const z = corner & 4 ? local[5] : local[2];
for (let axis = 0; axis < 3; axis++) {
const value = matrix[axis] * x + matrix[4 + axis] * y + matrix[8 + axis] * z + matrix[12 + axis];
bounds[axis] = Math.min(bounds[axis], value);
bounds[3 + axis] = Math.max(bounds[3 + axis], value);
}
}
return bounds;
}
export function determinantSign(matrix) {
const determinant = matrix[0] * (matrix[5] * matrix[10] - matrix[6] * matrix[9])
- matrix[4] * (matrix[1] * matrix[10] - matrix[2] * matrix[9])
+ matrix[8] * (matrix[1] * matrix[6] - matrix[2] * matrix[5]);
return determinant < 0 ? -1 : 1;
}
export function boundsDiagonal(bounds) {
return Math.hypot(bounds[3] - bounds[0], bounds[4] - bounds[1], bounds[5] - bounds[2]);
}
/** The distance between neighbouring float32 values at this magnitude. */
export function float32Step(magnitude) {
return 2 ** (Math.floor(Math.log2(Math.max(magnitude, 1e-30))) - 23);
}
/** Planes closer than this (metres) are one plane: 0.1 mm, or eight float32 steps of the largest coordinate when that is more. */
export function flushTolerance(largestCoordinate) {
return Math.max(1e-4, 8 * float32Step(largestCoordinate));
}
/** Same-facing planes up to this far apart (metres) can still fight far from the camera; `diagonal` spans both parts. */
export function nearTolerance(diagonal) {
return Math.min(0.25, Math.max(0.002, 1.5e-4 * diagonal));
}
/** Whether a part's drawn triangles leave its geometry (skin, morph, crowd, wind, liquid), so a search of the geometry says nothing. */
export function isDeformingPart(part) {
const { geometry, material } = part;
if (part.skin || part.morph || part.crowd || geometry.skinIndices || geometry.morphTargets) return true;
return DEFORMING_TAGS.has(material?.tag) || material?.transmission > 0;
}
// Parts with one geometry and one matrix are stacked copies (hundreds of dust motes parked at one spot). They draw the same
// depth bit for bit, so two of them stand for the stack.
function searchableParts(parts) {
const stacks = new Map();
const searchable = [];
for (const part of parts) {
if (!part.geometry?.indices?.length || isDeformingPart(part)) continue;
const stack = stacks.get(part.geometry) ?? new Map();
stacks.set(part.geometry, stack);
const pose = Array.prototype.join.call(part.matrix, ',');
const copies = stack.get(pose) ?? 0;
if (copies >= 2) continue;
stack.set(pose, copies + 1);
searchable.push(part);
}
return searchable;
}
// Past the budget the largest parts are searched, since a large flush face is the one people see; the rest is `unchecked`.
function withinTriangleBudget(parts, triangleBudget) {
const entries = parts.map((part, order) => ({ part, order, bounds: worldBounds(part), triangles: part.geometry.indices.length / 3 }));
const total = entries.reduce((sum, entry) => sum + entry.triangles, 0);
if (total <= triangleBudget) return { entries, unchecked: [] };
const bySize = [...entries].sort((first, second) => boundsDiagonal(second.bounds) - boundsDiagonal(first.bounds));
const kept = [];
const unchecked = [];
let used = 0;
for (const entry of bySize) {
if (used + entry.triangles <= triangleBudget) {
used += entry.triangles;
kept.push(entry);
} else {
unchecked.push(entry.part);
}
}
kept.sort((first, second) => first.order - second.order);
return { entries: kept, unchecked };
}
// World-space corners (9 numbers), unit normal (3), box (6) and area of every non-degenerate triangle, part after part.
function readTriangles(entries) {
const capacity = entries.reduce((sum, entry) => sum + entry.triangles, 0);
const table = {
count: 0,
corners: new Float64Array(capacity * 9),
normals: new Float64Array(capacity * 3),
boxes: new Float64Array(capacity * 6),
areas: new Float64Array(capacity),
owner: new Uint32Array(capacity),
local: new Uint32Array(capacity),
};
entries.forEach((entry, partIndex) => readPartTriangles(table, entry.part, partIndex));
return table;
}
function readPartTriangles(table, part, partIndex) {
const { positions, indices } = part.geometry;
const matrix = part.matrix;
const flip = determinantSign(matrix);
const { corners, normals, boxes } = table;
for (let triangle = 0; triangle < indices.length; triangle += 3) {
const base = table.count * 9;
for (let corner = 0; corner < 3; corner++) {
const vertex = indices[triangle + corner] * 3;
const x = positions[vertex];
const y = positions[vertex + 1];
const z = positions[vertex + 2];
corners[base + corner * 3] = matrix[0] * x + matrix[4] * y + matrix[8] * z + matrix[12];
corners[base + corner * 3 + 1] = matrix[1] * x + matrix[5] * y + matrix[9] * z + matrix[13];
corners[base + corner * 3 + 2] = matrix[2] * x + matrix[6] * y + matrix[10] * z + matrix[14];
}
const edgeOneX = corners[base + 3] - corners[base];
const edgeOneY = corners[base + 4] - corners[base + 1];
const edgeOneZ = corners[base + 5] - corners[base + 2];
const edgeTwoX = corners[base + 6] - corners[base];
const edgeTwoY = corners[base + 7] - corners[base + 1];
const edgeTwoZ = corners[base + 8] - corners[base + 2];
const normalX = edgeOneY * edgeTwoZ - edgeOneZ * edgeTwoY;
const normalY = edgeOneZ * edgeTwoX - edgeOneX * edgeTwoZ;
const normalZ = edgeOneX * edgeTwoY - edgeOneY * edgeTwoX;
const length = Math.hypot(normalX, normalY, normalZ);
if (!(length > 1e-12)) continue;
const id = table.count;
const scale = flip / length;
normals[id * 3] = normalX * scale;
normals[id * 3 + 1] = normalY * scale;
normals[id * 3 + 2] = normalZ * scale;
for (let axis = 0; axis < 3; axis++) {
const low = Math.min(corners[base + axis], corners[base + 3 + axis], corners[base + 6 + axis]);
const high = Math.max(corners[base + axis], corners[base + 3 + axis], corners[base + 6 + axis]);
boxes[id * 6 + axis] = low;
boxes[id * 6 + 3 + axis] = high;
}
table.areas[id] = length / 2;
table.owner[id] = partIndex;
table.local[id] = triangle / 3;
table.count++;
}
}
// Twice the median triangle extent: most triangles then touch a handful of cells.
function gridCellSize(table, reach) {
const extents = [];
const stride = Math.max(1, Math.floor(table.count / CELL_SAMPLES));
for (let id = 0; id < table.count; id += stride) {
const box = id * 6;
extents.push(Math.max(table.boxes[box + 3] - table.boxes[box], table.boxes[box + 4] - table.boxes[box + 1], table.boxes[box + 5] - table.boxes[box + 2]));
}
extents.sort((first, second) => first - second);
return Math.max(2 * extents[extents.length >> 1], 4 * reach, 1e-6);
}
// The normal cells a triangle is listed in. The sign is folded by the dominant component; when another component is nearly
// as large and has the other sign, both folds are listed, so two near-equal normals never fold apart.
function normalCellsOf(table, id, cells) {
const x = table.normals[id * 3];
const y = table.normals[id * 3 + 1];
const z = table.normals[id * 3 + 2];
const largest = Math.max(Math.abs(x), Math.abs(y), Math.abs(z));
let positive = false;
let negative = false;
for (const component of [x, y, z]) {
if (Math.abs(component) < largest - NEAR_DOMINANT) continue;
if (component < 0) negative = true;
else positive = true;
}
cells.length = 0;
for (const sign of [1, -1]) {
if (sign > 0 ? !positive : !negative) continue;
const lowX = Math.round((x * sign - NORMAL_REACH) * NORMAL_STEPS);
const highX = Math.round((x * sign + NORMAL_REACH) * NORMAL_STEPS);
const lowY = Math.round((y * sign - NORMAL_REACH) * NORMAL_STEPS);
const highY = Math.round((y * sign + NORMAL_REACH) * NORMAL_STEPS);
const lowZ = Math.round((z * sign - NORMAL_REACH) * NORMAL_STEPS);
const highZ = Math.round((z * sign + NORMAL_REACH) * NORMAL_STEPS);
for (let cellX = lowX; cellX <= highX; cellX++) {
for (let cellY = lowY; cellY <= highY; cellY++) {
for (let cellZ = lowZ; cellZ <= highZ; cellZ++) {
const cell = ((cellX + NORMAL_STEPS + 1) * NORMAL_RANGE + cellY + NORMAL_STEPS + 1) * NORMAL_RANGE + cellZ + NORMAL_STEPS + 1;
if (!cells.includes(cell)) cells.push(cell);
}
}
}
}
return cells;
}
const cellRange = new Int32Array(6);
const estimateNormalCells = [];
// The grid cells a triangle's box touches at one level, grown by half the reach so two boxes within the reach share a cell.
// Returns how many cells that is.
function cellRangeOf(table, id, cellSize, reach) {
let cells = 1;
for (let axis = 0; axis < 3; axis++) {
const low = Math.floor((table.boxes[id * 6 + axis] - reach / 2) / cellSize);
const high = Math.floor((table.boxes[id * 6 + 3 + axis] + reach / 2) / cellSize);
cellRange[axis] = low;
cellRange[3 + axis] = high;
cells *= high - low + 1;
}
return cells;
}
// The finest grid level where the triangle spans at most NATIVE_CELL_LIMIT cells.
function nativeLevelOf(table, id, cellSize, reach) {
let level = 0;
while (level < GRID_LEVELS && cellRangeOf(table, id, cellSize * GRID_LEVEL_SCALE ** level, reach) > NATIVE_CELL_LIMIT) level++;
return level;
}
// How many native cell entries buildCells would make, projected from CELL_SAMPLES evenly spaced triangles.
function estimateNativeEntries(table, cellSize, reach) {
const stride = Math.max(1, Math.floor(table.count / CELL_SAMPLES));
let sampledEntries = 0;
let sampled = 0;
for (let id = 0; id < table.count; id += stride) {
const level = nativeLevelOf(table, id, cellSize, reach);
const normalCellCount = normalCellsOf(table, id, estimateNormalCells).length;
sampledEntries += level === GRID_LEVELS ? normalCellCount : normalCellCount * cellRangeOf(table, id, cellSize * GRID_LEVEL_SCALE ** level, reach);
sampled++;
}
return (sampledEntries / sampled) * table.count;
}
function cellKey(normalCell, level, cellX, cellY, cellZ) {
const mixed = Math.imul(cellX, 73856093) ^ Math.imul(cellY, 19349663) ^ Math.imul(cellZ, 83492791) ^ Math.imul(normalCell * GRID_LEVELS + level, 0x9e3779b1);
return mixed >>> 0;
}
// Lists every triangle in the cells of its own level (`natives`), then as a guest in the coarser cells that hold a native.
// The last level is one cell per normal cell, for triangles too large for any grid. Returns null when the natives would pass
// MAXIMUM_GRID_ENTRIES, so the caller can try wider cells.
function buildCells(table, cellSize, reach) {
const levels = Array.from({ length: GRID_LEVELS + 1 }, () => new Map());
const nativeLevel = new Uint8Array(table.count);
const normalCells = [];
const visitCells = (id, level, visit) => {
normalCellsOf(table, id, normalCells);
if (level === GRID_LEVELS) {
for (const normalCell of normalCells) visit(normalCell);
return;
}
cellRangeOf(table, id, cellSize * GRID_LEVEL_SCALE ** level, reach);
const [lowX, lowY, lowZ, highX, highY, highZ] = cellRange;
for (const normalCell of normalCells) {
for (let cellX = lowX; cellX <= highX; cellX++) {
for (let cellY = lowY; cellY <= highY; cellY++) {
for (let cellZ = lowZ; cellZ <= highZ; cellZ++) visit(cellKey(normalCell, level, cellX, cellY, cellZ));
}
}
}
};
let nativeEntries = 0;
for (let id = 0; id < table.count; id++) {
const level = nativeLevelOf(table, id, cellSize, reach);
nativeLevel[id] = level;
const cells = levels[level];
visitCells(id, level, key => {
nativeEntries++;
const cell = cells.get(key);
if (cell) cell.natives.push(id);
else cells.set(key, { natives: [id], guests: [] });
});
if (nativeEntries > MAXIMUM_GRID_ENTRIES) return null;
}
for (let id = 0; id < table.count; id++) {
for (let level = nativeLevel[id] + 1; level <= GRID_LEVELS; level++) {
const cells = levels[level];
if (cells.size === 0) continue;
visitCells(id, level, key => cells.get(key)?.guests.push(id));
}
}
return levels.flatMap(cells => [...cells.values()]);
}
// Wider cells list each triangle in fewer of them and leave the pairs found the same. A grid is made wider only when a sample
// of the triangles projects past MAXIMUM_GRID_ENTRIES, or when building it passes that, so every scene that fit keeps its grid.
function buildCoarsenedCells(table, reach) {
let cellSize = gridCellSize(table, reach);
for (let coarsening = 0; coarsening <= MAXIMUM_GRID_COARSENINGS; coarsening++, cellSize *= 2) {
if (estimateNativeEntries(table, cellSize, reach) > MAXIMUM_GRID_ENTRIES) continue;
const cells = buildCells(table, cellSize, reach);
if (cells) return cells;
}
throw new RangeError(`The coplanar search has ${table.count} triangles in a scene too large to index. Pass environment.resolveCoplanar: false to skip the search, or split the scene into smaller ones.`);
}
const clipFirst = new Float64Array(32);
const clipSecond = new Float64Array(32);
const sharedCentre = new Float64Array(2);
// Clips triangle `second` against triangle `first` on the plane's two largest axes (Sutherland-Hodgman). Returns the shared
// area in square metres and leaves the centre of the shared piece in `sharedCentre`.
function sharedArea(table, first, second, dropped, axisU, axisV) {
const { corners, normals } = table;
let polygon = clipFirst;
let next = clipSecond;
let size = 3;
for (let corner = 0; corner < 3; corner++) {
polygon[corner * 2] = corners[second * 9 + corner * 3 + axisU];
polygon[corner * 2 + 1] = corners[second * 9 + corner * 3 + axisV];
}
const base = first * 9;
const turn = (corners[base + 3 + axisU] - corners[base + axisU]) * (corners[base + 6 + axisV] - corners[base + axisV])
- (corners[base + 3 + axisV] - corners[base + axisV]) * (corners[base + 6 + axisU] - corners[base + axisU]) >= 0 ? 1 : -1;
for (let edge = 0; edge < 3 && size > 0; edge++) {
const startU = corners[base + edge * 3 + axisU];
const startV = corners[base + edge * 3 + axisV];
const edgeU = corners[base + ((edge + 1) % 3) * 3 + axisU] - startU;
const edgeV = corners[base + ((edge + 1) % 3) * 3 + axisV] - startV;
let nextSize = 0;
let previousU = polygon[size * 2 - 2];
let previousV = polygon[size * 2 - 1];
let previousSide = turn * (edgeU * (previousV - startV) - edgeV * (previousU - startU));
for (let index = 0; index < size; index++) {
const currentU = polygon[index * 2];
const currentV = polygon[index * 2 + 1];
const currentSide = turn * (edgeU * (currentV - startV) - edgeV * (currentU - startU));
if ((currentSide >= 0) !== (previousSide >= 0)) {
const along = previousSide / (previousSide - currentSide);
next[nextSize * 2] = previousU + (currentU - previousU) * along;
next[nextSize * 2 + 1] = previousV + (currentV - previousV) * along;
nextSize++;
}
if (currentSide >= 0) {
next[nextSize * 2] = currentU;
next[nextSize * 2 + 1] = currentV;
nextSize++;
}
previousU = currentU;
previousV = currentV;
previousSide = currentSide;
}
const swap = polygon;
polygon = next;
next = swap;
size = nextSize;
}
if (size < 3) return 0;
let doubled = 0;
let centreU = 0;
let centreV = 0;
for (let index = 0; index < size; index++) {
const following = (index + 1) % size;
doubled += polygon[index * 2] * polygon[following * 2 + 1] - polygon[following * 2] * polygon[index * 2 + 1];
centreU += polygon[index * 2];
centreV += polygon[index * 2 + 1];
}
sharedCentre[0] = centreU / size;
sharedCentre[1] = centreV / size;
return Math.abs(doubled) / 2 / Math.max(Math.abs(normals[first * 3 + dropped]), 1e-12);
}
// Where a triangle's plane sits along the dropped axis above the point (u, v).
function planeHeight(table, id, dropped, axisU, axisV, u, v) {
const { corners, normals } = table;
const slope = normals[id * 3 + axisU] * (u - corners[id * 9 + axisU]) + normals[id * 3 + axisV] * (v - corners[id * 9 + axisV]);
return corners[id * 9 + dropped] - slope / normals[id * 3 + dropped];
}
function createPairTest(table, entries, reach, pairBudget, testedPairLimit, result) {
const { corners, normals, boxes, areas, owner } = table;
const seen = new Set();
const tolerances = new Map();
const pairTolerance = (firstPart, secondPart) => {
const key = Math.min(firstPart, secondPart) * entries.length + Math.max(firstPart, secondPart);
let tolerance = tolerances.get(key);
if (tolerance === undefined) {
const first = entries[firstPart].bounds;
const second = entries[secondPart].bounds;
tolerance = nearTolerance(Math.hypot(
Math.max(first[3], second[3]) - Math.min(first[0], second[0]),
Math.max(first[4], second[4]) - Math.min(first[1], second[1]),
Math.max(first[5], second[5]) - Math.min(first[2], second[2]),
));
tolerances.set(key, tolerance);
}
return tolerance;
};
return function testPair(one, other) {
// Two cells of one triangle can hash to one key, which lists it twice.
if (one === other) return;
const first = Math.min(one, other);
const second = Math.max(one, other);
for (let axis = 0; axis < 3; axis++) {
if (boxes[first * 6 + 3 + axis] < boxes[second * 6 + axis] - reach) return;
if (boxes[second * 6 + 3 + axis] < boxes[first * 6 + axis] - reach) return;
}
const normalX = normals[first * 3];
const normalY = normals[first * 3 + 1];
const normalZ = normals[first * 3 + 2];
const absoluteX = Math.abs(normalX);
const absoluteY = Math.abs(normalY);
const absoluteZ = Math.abs(normalZ);
let dropped = 0;
if (absoluteY > absoluteX && absoluteY >= absoluteZ) dropped = 1;
else if (absoluteZ > absoluteX && absoluteZ > absoluteY) dropped = 2;
const axisU = (dropped + 1) % 3;
const axisV = (dropped + 2) % 3;
// Triangles that only touch along an edge share no area: the boxes must overlap across the plane's two axes. This drops the
// neighbours of one dense flat mesh before they cost a plane test, a Set entry and a clip (issue #1216).
if (boxes[first * 6 + 3 + axisU] <= boxes[second * 6 + axisU] || boxes[second * 6 + 3 + axisU] <= boxes[first * 6 + axisU]) return;
if (boxes[first * 6 + 3 + axisV] <= boxes[second * 6 + axisV] || boxes[second * 6 + 3 + axisV] <= boxes[first * 6 + axisV]) return;
const facing = normalX * normals[second * 3] + normalY * normals[second * 3 + 1] + normalZ * normals[second * 3 + 2];
if (Math.abs(facing) < SAME_FACING) return;
const opposite = facing < 0;
// A face against a floor looks away from it and is culled, unless one of the two shows both sides.
if (opposite && entries[owner[first]].part.material?.doubleSided !== true && entries[owner[second]].part.material?.doubleSided !== true) return;
const tolerance = pairTolerance(owner[first], owner[second]);
for (let corner = 0; corner < 3; corner++) {
const distance = (corners[second * 9 + corner * 3] - corners[first * 9]) * normalX
+ (corners[second * 9 + corner * 3 + 1] - corners[first * 9 + 1]) * normalY
+ (corners[second * 9 + corner * 3 + 2] - corners[first * 9 + 2]) * normalZ;
if (Math.abs(distance) > tolerance) return;
}
const pairKey = first * table.count + second;
if (seen.has(pairKey)) return;
// A Set holds at most 2^24 keys: a big flat part beside dense props can reach that, so stop the search instead of throwing.
if (seen.size >= testedPairLimit) {
result.truncated = true;
result.truncatedAt ??= entries[owner[second]].part.name;
return;
}
seen.add(pairKey);
const area = sharedArea(table, first, second, dropped, axisU, axisV);
if (area < Math.max(FLUSH_MINIMUM_AREA, FLUSH_MINIMUM_AREA_SHARE * Math.min(areas[first], areas[second]))) return;
if (result.pairs.length >= pairBudget) {
result.truncated = true;
result.truncatedAt ??= entries[owner[second]].part.name;
return;
}
const lift = planeHeight(table, second, dropped, axisU, axisV, sharedCentre[0], sharedCentre[1]) - planeHeight(table, first, dropped, axisU, axisV, sharedCentre[0], sharedCentre[1]);
const gap = lift * normals[first * 3 + dropped];
// The two planes are one plane when the gap is within the rounding of the coordinates of these two triangles, not of the
// whole scene: a far backdrop must not blur the order of faces near the origin.
let largestCoordinate = 0;
for (let value = 0; value < 6; value++) largestCoordinate = Math.max(largestCoordinate, Math.abs(boxes[first * 6 + value]), Math.abs(boxes[second * 6 + value]));
result.pairs.push({ first, second, gap, area, opposite, flush: Math.abs(gap) <= flushTolerance(largestCoordinate) });
};
}
// A triangle never drops an axis its normal barely leans on (the dropped axis has a component of at least 0.577), so that axis
// is one the shared area is measured along: two triangles only share area when their boxes overlap there, with no reach.
function inPlaneSweepAxis(normals, id) {
let axis = 0;
for (let candidate = 1; candidate < 3; candidate++) {
if (Math.abs(normals[id * 3 + candidate]) < Math.abs(normals[id * 3 + axis])) axis = candidate;
}
return Math.abs(normals[id * 3 + axis]) < SWEEP_AXIS_LEAN ? axis : -1;
}
// Natives are swept along one axis against each other; every native is also tested against every guest of the cell.
function testCell(cell, table, reach, testPair) {
const { natives, guests } = cell;
const { boxes, normals } = table;
const sweepAxis = natives.length > 2 ? inPlaneSweepAxis(normals, natives[0]) : -1;
const sweepReach = sweepAxis < 0 ? reach : 0;
const sweepFrom = Math.max(sweepAxis, 0);
if (natives.length > 2) natives.sort((first, second) => boxes[first * 6 + sweepFrom] - boxes[second * 6 + sweepFrom]);
for (let index = 0; index < natives.length; index++) {
const native = natives[index];
const end = boxes[native * 6 + 3 + sweepFrom] + sweepReach;
for (let other = index + 1; other < natives.length; other++) {
if (boxes[natives[other] * 6 + sweepFrom] > end) break;
testPair(native, natives[other]);
}
for (let other = 0; other < guests.length; other++) testPair(native, guests[other]);
}
}
/**
* Pairs of triangles that draw the same plane in the same place. A part is `{ name, geometry: { positions, indices }, matrix,
* material? }`; deforming parts (isDeformingPart) are left out. Returns `{ parts, count, owner, local, areas, corners, pairs,
* unchecked, truncated }`: `corners` holds nine world coordinates per triangle, `pairs` holds `{ first, second, gap, area, opposite, flush }` with triangle ids below `count`, `owner[id]` the
* index into `parts` and `local[id]` the triangle inside that part's geometry. `gap` is in metres along the first triangle's
* normal, positive when the second triangle is in front of it; `flush` says the gap is within rounding (flushTolerance), so the
* two lie on one plane; `opposite` marks a pair that faces opposite ways (one part is double sided). `unchecked` lists parts
* past `triangleBudget`.
*/
export function findFlushPairs(parts, { triangleBudget = DEFAULT_TRIANGLE_BUDGET, pairBudget = DEFAULT_PAIR_BUDGET, testedPairLimit = MAXIMUM_TESTED_PAIRS } = {}) {
const { entries, unchecked } = withinTriangleBudget(searchableParts(parts), triangleBudget);
const table = readTriangles(entries);
const result = { parts: entries.map(entry => entry.part), count: table.count, owner: table.owner, local: table.local, areas: table.areas, corners: table.corners, pairs: [], unchecked, truncated: false };
if (table.count < 2) return result;
const sceneBounds = [Infinity, Infinity, Infinity, -Infinity, -Infinity, -Infinity];
for (const { bounds } of entries) {
for (let axis = 0; axis < 3; axis++) {
sceneBounds[axis] = Math.min(sceneBounds[axis], bounds[axis]);
sceneBounds[3 + axis] = Math.max(sceneBounds[3 + axis], bounds[3 + axis]);
}
}
// No pair of parts spans more than the scene, so this is the widest gap any pair is tested with.
const reach = nearTolerance(boundsDiagonal(sceneBounds));
const testPair = createPairTest(table, entries, reach, pairBudget, testedPairLimit, result);
for (const cell of buildCoarsenedCells(table, reach)) testCell(cell, table, reach, testPair);
result.pairs.sort((first, second) => first.first - second.first || first.second - second.second);
return result;
}