Skip to content

3D engine that AI agents drive

20.9 KB
Raw Blame
// Cuts away the part of a triangle that an opaque triangle on the same plane covers (issue #751). Two faces on one plane
// fight for every pixel they share; once the hidden one is gone there is nothing left to fight, at any depth precision and
// however deep the stack is. flush-resolve.js picks the pairs and the winner; this file does the cutting.
//
// Two rules keep the cut from showing. A cut stops a few float32 steps inside the winner, so the two faces overlap by a hair
// instead of meeting on a line that rounding could open. And a vertex a cut puts on an edge is given to every triangle on
// that edge, in this face and in the next one, so no edge has a vertex on one side only (a T-junction leaks single pixels).
import { float32Step } from './flush-search.js';

/** Numbers per cut: the triangle that is cut, then the three corners (x, y, z) of the winner in the geometry's own space. */
export const FLUSH_CUT_STRIDE = 10;
/** Shared area (square metres) under which a pair is ranked instead of cut: 1 cm2. */
export const FLUSH_CUT_MINIMUM_AREA = 1e-4;
const PER_VERTEX_FIELDS = ['positions', 'normals', 'uvs', 'lightUvs', 'colors', 'skyVisibility', 'surfaceMasks'];
const MARGIN_STEPS = 4;
const DEGENERATE_AREA_SHARE = 1e-12;
const CACHED_CUTS_PER_GEOMETRY = 8;

const clippedByGeometry = new WeakMap();

export function sameNumbers(first, second) {
  if (first.length !== second.length) return false;
  for (let index = 0; index < first.length; index++) {
    if (first[index] !== second[index]) return false;
  }
  return true;
}

function createPiece(points) {
  const piece = { points, minU: Infinity, minV: Infinity, maxU: -Infinity, maxV: -Infinity };
  for (const point of points) {
    piece.minU = Math.min(piece.minU, point.u);
    piece.minV = Math.min(piece.minV, point.v);
    piece.maxU = Math.max(piece.maxU, point.u);
    piece.maxV = Math.max(piece.maxV, point.v);
  }
  return piece;
}

function doubledArea(points) {
  let doubled = 0;
  for (let index = 0; index < points.length; index++) {
    const following = points[(index + 1) % points.length];
    doubled += points[index].u * following.v - following.u * points[index].v;
  }
  return Math.abs(doubled);
}

// The points of one triangle while it is cut. A point's weights say where it sits in the uncut triangle, so every vertex
// array can be interpolated for it later. Two cuts that reach the same spot get the same point: the grid finds it again.
function createPointSet(tolerance) {
  const cells = new Map();
  const all = [];
  const cellOf = value => Math.round(value / tolerance);
  function find(u, v) {
    const cellU = cellOf(u);
    const cellV = cellOf(v);
    for (let offsetU = -1; offsetU <= 1; offsetU++) {
      for (let offsetV = -1; offsetV <= 1; offsetV++) {
        const point = cells.get(`${cellU + offsetU},${cellV + offsetV}`);
        if (point && Math.abs(point.u - u) <= tolerance && Math.abs(point.v - v) <= tolerance) return point;
      }
    }
    return null;
  }
  function add(u, v, weights, vertex = -1) {
    const point = { u, v, weights, vertex, position: null, seam: null };
    cells.set(`${cellOf(u)},${cellOf(v)}`, point);
    all.push(point);
    return point;
  }
  function between(start, end, along) {
    const u = start.u + (end.u - start.u) * along;
    const v = start.v + (end.v - start.v) * along;
    return find(u, v) ?? add(u, v, [0, 1, 2].map(corner => start.weights[corner] + (end.weights[corner] - start.weights[corner]) * along));
  }
  return { all, add, between, tolerance };
}

// Splits a convex polygon along the line where `distances` is zero. A point within the tolerance of the line is on it and
// belongs to both sides, so a line through a vertex makes no second vertex beside it.
function splitPolygon(points, distances, pointSet) {
  const inside = [];
  const outside = [];
  const sides = distances.map(distance => (distance > pointSet.tolerance ? 1 : distance < -pointSet.tolerance ? -1 : 0));
  for (let index = 0; index < points.length; index++) {
    const following = (index + 1) % points.length;
    if (sides[index] >= 0) inside.push(points[index]);
    if (sides[index] <= 0) outside.push(points[index]);
    if (sides[index] * sides[following] < 0) {
      const crossing = pointSet.between(points[index], points[following], distances[index] / (distances[index] - distances[following]));
      if (inside.at(-1) !== crossing) inside.push(crossing);
      if (outside.at(-1) !== crossing) outside.push(crossing);
    }
  }
  return { inside, outside, reaches: sides.includes(1) };
}

function winnerCorners(cuts, cut, axisU, axisV) {
  const offset = cut * FLUSH_CUT_STRIDE + 1;
  return [0, 1, 2].map(corner => ({ u: cuts[offset + corner * 3 + axisU], v: cuts[offset + corner * 3 + axisV] }));
}

function edgeKey(start, end) {
  const forward = start.u < end.u || (start.u === end.u && start.v <= end.v);
  const [low, high] = forward ? [start, end] : [end, start];
  return `${low.u},${low.v},${high.u},${high.v}`;
}

// The winner's three edges on the plane's two largest axes, each as a start and a unit direction turned so that the
// inside of the winner is at positive distance. An edge is moved `margin` into the winner where the cut face goes on
// beyond it. It stays where it is when two winners share it (it is inside the covered area) and when the whole cut face
// lies on the winner's side of it (nothing goes on beyond it, so moving it would only leave a strip under the winner).
// Null for a winner that is a line on these axes.
function winnerEdges(corners, sharedEdges, margin, facePoints, tolerance) {
  const turn = (corners[1].u - corners[0].u) * (corners[2].v - corners[0].v) - (corners[1].v - corners[0].v) * (corners[2].u - corners[0].u) >= 0 ? 1 : -1;
  const edges = [];
  for (let index = 0; index < 3; index++) {
    const start = corners[index];
    const end = corners[(index + 1) % 3];
    const length = Math.hypot(end.u - start.u, end.v - start.v);
    if (!(length > 0)) return null;
    const edge = { u: start.u, v: start.v, directionU: turn * (end.u - start.u) / length, directionV: turn * (end.v - start.v) / length, margin };
    if (sharedEdges.get(edgeKey(start, end)) > 1 || facePoints.every(point => edgeDistance(edge, point) >= -tolerance)) edge.margin = 0;
    edges.push(edge);
  }
  edges.minU = Math.min(corners[0].u, corners[1].u, corners[2].u);
  edges.maxU = Math.max(corners[0].u, corners[1].u, corners[2].u);
  edges.minV = Math.min(corners[0].v, corners[1].v, corners[2].v);
  edges.maxV = Math.max(corners[0].v, corners[1].v, corners[2].v);
  return edges;
}

function edgeDistance(edge, point) {
  return edge.directionU * (point.v - edge.v) - edge.directionV * (point.u - edge.u);
}

function isCovered(points, edges, margin) {
  return points.every(point => edges.every(edge => edgeDistance(edge, point) >= -margin));
}

// What is left of a convex piece outside the winner, as convex pieces; null when the winner does not reach into it. Each
// edge line splits off the part beyond it; what is inside all three is the hidden part.
function subtractWinner(piece, edges, margin, pointSet) {
  if (piece.maxU < edges.minU || piece.minU > edges.maxU || piece.maxV < edges.minV || piece.minV > edges.maxV) return null;
  let remaining = piece.points;
  const kept = [];
  for (const edge of edges) {
    const { inside, outside, reaches } = splitPolygon(remaining, remaining.map(point => edgeDistance(edge, point) - edge.margin), pointSet);
    if (!reaches || inside.length < 3) return null;
    // A sliver between an edge of the winner and its moved line lies under the winner: it is hidden, not left over.
    if (outside.length >= 3 && !isCovered(outside, edges, margin)) kept.push(createPiece(outside));
    remaining = inside;
  }
  if (doubledArea(remaining) <= margin * margin) return null;
  return kept;
}

// The frame one triangle is cut in: its corners on the plane's two largest axes, and the largest coordinate in play.
function triangleFrame(geometry, triangle) {
  const { positions, indices } = geometry;
  const offsets = [0, 1, 2].map(corner => indices[triangle * 3 + corner] * 3);
  const edgeOne = [0, 1, 2].map(axis => positions[offsets[1] + axis] - positions[offsets[0] + axis]);
  const edgeTwo = [0, 1, 2].map(axis => positions[offsets[2] + axis] - positions[offsets[0] + 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]];
  const dropped = normal.reduce((best, value, axis) => (Math.abs(value) > Math.abs(normal[best]) ? axis : best), 0);
  let largest = 0;
  for (const offset of offsets) largest = Math.max(largest, Math.abs(positions[offset]), Math.abs(positions[offset + 1]), Math.abs(positions[offset + 2]));
  return { offsets, axisU: (dropped + 1) % 3, axisV: (dropped + 2) % 3, largest };
}

function cornerPoints(geometry, frame, pointSet) {
  return frame.offsets.map((offset, corner) => pointSet.add(geometry.positions[offset + frame.axisU], geometry.positions[offset + frame.axisV], [0, 1, 2].map(index => (index === corner ? 1 : 0)), offset / 3));
}

// One triangle after its cuts as `{ frame, pointSet, pieces, corners }`, or null when no cut reached it.
function cutTriangle(geometry, triangle, cuts, cutStart, cutEnd, coordinateStep) {
  const frame = triangleFrame(geometry, triangle);
  let largest = frame.largest;
  for (let value = cutStart * FLUSH_CUT_STRIDE; value < cutEnd * FLUSH_CUT_STRIDE; value++) {
    if (value % FLUSH_CUT_STRIDE !== 0) largest = Math.max(largest, Math.abs(cuts[value]));
  }
  const step = Math.max(coordinateStep, float32Step(largest));
  const margin = MARGIN_STEPS * step;
  const pointSet = createPointSet(step);
  const corners = cornerPoints(geometry, frame, pointSet);
  const whole = createPiece(corners);
  const wholeArea = doubledArea(corners);
  const winners = [];
  const sharedEdges = new Map();
  for (let cut = cutStart; cut < cutEnd; cut++) {
    const winner = winnerCorners(cuts, cut, frame.axisU, frame.axisV);
    winners.push(winner);
    for (let index = 0; index < 3; index++) {
      const key = edgeKey(winner[index], winner[(index + 1) % 3]);
      sharedEdges.set(key, (sharedEdges.get(key) ?? 0) + 1);
    }
  }
  let pieces = [whole];
  for (const winner of winners) {
    const edges = winnerEdges(winner, sharedEdges, margin, corners, step);
    if (!edges) continue;
    const next = [];
    for (const piece of pieces) {
      const left = subtractWinner(piece, edges, margin, pointSet);
      if (left) next.push(...left);
      else next.push(piece);
    }
    pieces = next;
  }
  if (pieces.length === 1 && pieces[0] === whole) return null;
  pieces = pieces.filter(piece => doubledArea(piece.points) > DEGENERATE_AREA_SHARE * wholeArea);
  return { frame, pointSet, pieces, corners };
}

function positionKey(positions, offset) {
  return `${positions[offset]},${positions[offset + 1]},${positions[offset + 2]}`;
}

// One side of a triangle as the mesh edge it lies on: a key that every triangle on that edge agrees on, whatever its own
// vertex numbers, and whether this triangle runs along it from the lower end.
function meshEdge(geometry, frame, opposite) {
  const start = frame.offsets[(opposite + 1) % 3];
  const end = frame.offsets[(opposite + 2) % 3];
  const startKey = positionKey(geometry.positions, start);
  const endKey = positionKey(geometry.positions, end);
  const forward = startKey <= endKey;
  return { key: forward ? `${startKey}|${endKey}` : `${endKey}|${startKey}`, forward, start, end };
}

// The corner a point lies opposite of when it sits on a side of the uncut triangle and is not a corner itself, else -1.
function sideOf(point) {
  const zeros = point.weights.filter(weight => weight === 0).length;
  return zeros === 1 ? point.weights.indexOf(0) : -1;
}

// Notes every vertex a cut put on a mesh edge in `seams`, so the triangles on the other side of that edge get it too. Two
// triangles that were cut at the same spot of an edge share one position, to the bit.
function noteSeamPoints(geometry, cut, seams) {
  const { positions } = geometry;
  for (const point of new Set(cut.pieces.flatMap(piece => piece.points))) {
    const opposite = sideOf(point);
    if (opposite < 0) continue;
    const edge = meshEdge(geometry, cut.frame, opposite);
    const along = edge.forward ? point.weights[(opposite + 2) % 3] : point.weights[(opposite + 1) % 3];
    const [low, high] = edge.forward ? [edge.start, edge.end] : [edge.end, edge.start];
    const length = Math.hypot(positions[high] - positions[low], positions[high + 1] - positions[low + 1], positions[high + 2] - positions[low + 2]);
    const entries = seams.get(edge.key) ?? [];
    seams.set(edge.key, entries);
    let entry = entries.find(candidate => Math.abs(candidate.along - along) * length <= cut.pointSet.tolerance);
    if (!entry) {
      entry = { along, position: [0, 1, 2].map(axis => Math.fround(positions[low + axis] + (positions[high + axis] - positions[low + axis]) * along)) };
      entries.push(entry);
    }
    point.seam = entry;
    point.position = entry.position;
  }
}

// Gives a triangle the seam vertices of its three sides that it does not have yet.
function addSeamPoints(geometry, cut, seams) {
  for (let opposite = 0; opposite < 3; opposite++) {
    const edge = meshEdge(geometry, cut.frame, opposite);
    const entries = seams.get(edge.key);
    if (!entries) continue;
    const start = cut.corners[(opposite + 1) % 3];
    const end = cut.corners[(opposite + 2) % 3];
    for (const entry of entries) {
      if (cut.pointSet.all.some(point => point.seam === entry)) continue;
      const along = edge.forward ? entry.along : 1 - entry.along;
      const point = cut.pointSet.between(start, end, along);
      if (point.seam || point.vertex >= 0) continue;
      point.seam = entry;
      point.position = entry.position;
    }
  }
}

// The points of a piece with every other point of the triangle that lies on one of its sides put in between, so the piece
// and its neighbours have the same vertices along the side they share.
function withPointsOnSides(piece, pointSet) {
  const own = new Set(piece.points);
  const ring = [];
  for (let index = 0; index < piece.points.length; index++) {
    const start = piece.points[index];
    const end = piece.points[(index + 1) % piece.points.length];
    const length = Math.hypot(end.u - start.u, end.v - start.v);
    ring.push(start);
    if (!(length > 0)) continue;
    const onSide = [];
    for (const point of pointSet.all) {
      if (own.has(point)) continue;
      const along = ((point.u - start.u) * (end.u - start.u) + (point.v - start.v) * (end.v - start.v)) / length;
      if (along <= pointSet.tolerance || along >= length - pointSet.tolerance) continue;
      const away = Math.abs((end.u - start.u) * (point.v - start.v) - (end.v - start.v) * (point.u - start.u)) / length;
      if (away <= pointSet.tolerance) onSide.push({ point, along });
    }
    onSide.sort((one, other) => one.along - other.along);
    for (const { point } of onSide) ring.push(point);
  }
  return ring;
}

function hasPointOnSide(ring, tolerance) {
  return ring.some((point, index) => {
    const previous = ring[(index + ring.length - 1) % ring.length];
    const following = ring[(index + 1) % ring.length];
    const length = Math.hypot(following.u - previous.u, following.v - previous.v);
    return Math.abs((following.u - previous.u) * (point.v - previous.v) - (following.v - previous.v) * (point.u - previous.u)) <= tolerance * length;
  });
}

// A convex ring as triangles. A ring with points along its sides is fanned from its middle: a fan from a corner would
// leave those points beside a long edge, held only by a triangle with no area.
function fanRing(ring, pointSet) {
  if (!hasPointOnSide(ring, pointSet.tolerance)) return ring.slice(1, -1).map((point, index) => [ring[0], point, ring[index + 2]]);
  const middle = pointSet.add(
    ring.reduce((sum, point) => sum + point.u, 0) / ring.length,
    ring.reduce((sum, point) => sum + point.v, 0) / ring.length,
    [0, 1, 2].map(corner => ring.reduce((sum, point) => sum + point.weights[corner], 0) / ring.length),
  );
  return ring.map((point, index) => [middle, point, ring[(index + 1) % ring.length]]);
}

// Every per-vertex array grown by the new vertices, each the weighted mix of the three corners of the triangle it was cut
// from. A vertex on a seam takes the position the seam holds, so both sides of the seam get the same bits.
function extendVertexArrays(geometry, added) {
  const vertexCount = geometry.positions.length / 3;
  const extended = {};
  for (const field of PER_VERTEX_FIELDS) {
    const values = geometry[field];
    if (!values) continue;
    const stride = values.length / vertexCount;
    const grown = new values.constructor(values.length + added.length * stride);
    grown.set(values);
    added.forEach(({ corners, point }, vertex) => {
      const target = values.length + vertex * stride;
      if (field === 'positions' && point.position) {
        grown.set(point.position, target);
        return;
      }
      for (let component = 0; component < stride; component++) {
        grown[target + component] = values[corners[0] * stride + component] * point.weights[0]
          + values[corners[1] * stride + component] * point.weights[1]
          + values[corners[2] * stride + component] * point.weights[2];
      }
    });
    extended[field] = grown;
  }
  return extended;
}

function clipGeometry(geometry, cuts, coordinateStep) {
  const { indices } = geometry;
  const triangleCount = indices.length / 3;
  const vertexCount = geometry.positions.length / 3;
  const cutCount = cuts.length / FLUSH_CUT_STRIDE;
  const cutTriangles = new Map();
  const seams = new Map();
  let cut = 0;
  for (let triangle = 0; triangle < triangleCount && cut < cutCount; triangle++) {
    const cutStart = cut;
    while (cut < cutCount && cuts[cut * FLUSH_CUT_STRIDE] === triangle) cut++;
    if (cut === cutStart) continue;
    const result = cutTriangle(geometry, triangle, cuts, cutStart, cut, coordinateStep);
    if (!result) continue;
    cutTriangles.set(triangle, result);
    noteSeamPoints(geometry, result, seams);
  }
  if (cutTriangles.size === 0) return { geometry, sources: null };
  const clippedIndices = [];
  const sources = [];
  const added = [];
  for (let triangle = 0; triangle < triangleCount; triangle++) {
    let result = cutTriangles.get(triangle);
    if (!result && seams.size > 0) {
      // An uncut triangle on a seam is split at the seam's vertices too.
      const frame = triangleFrame(geometry, triangle);
      if ([0, 1, 2].some(opposite => seams.has(meshEdge(geometry, frame, opposite).key))) {
        const pointSet = createPointSet(Math.max(coordinateStep, float32Step(frame.largest)));
        const corners = cornerPoints(geometry, frame, pointSet);
        result = { frame, pointSet, pieces: [createPiece(corners)], corners };
      }
    }
    if (!result) {
      clippedIndices.push(indices[triangle * 3], indices[triangle * 3 + 1], indices[triangle * 3 + 2]);
      sources.push(triangle);
      continue;
    }
    addSeamPoints(geometry, result, seams);
    const corners = [indices[triangle * 3], indices[triangle * 3 + 1], indices[triangle * 3 + 2]];
    for (const piece of result.pieces) {
      const ring = withPointsOnSides(piece, result.pointSet);
      for (const fan of fanRing(ring, result.pointSet)) {
        for (const point of fan) {
          if (point.vertex >= 0) continue;
          point.vertex = vertexCount + added.length;
          added.push({ corners, point });
        }
        clippedIndices.push(fan[0].vertex, fan[1].vertex, fan[2].vertex);
        sources.push(triangle);
      }
    }
  }
  return {
    geometry: { ...geometry, ...extendVertexArrays(geometry, added), indices: new Uint32Array(clippedIndices) },
    sources: new Uint32Array(sources),
  };
}

/**
 * Cuts the hidden part out of the triangles of `geometry`. `cuts` is a Float64Array of FLUSH_CUT_STRIDE numbers per cut,
 * sorted by the triangle that is cut: that triangle's number, then the corners of the triangle that covers it, in the
 * geometry's own space. `coordinateStep` is the float32 step of the coordinates the part is drawn at, in the geometry's
 * units; a cut stops a few of those steps (or of the geometry's own, when larger) inside the winner. Returns
 * `{ geometry, sources }`: a new geometry with every per-vertex array interpolated for the new vertices and `sources[n]`
 * the uncut triangle that clipped triangle n came from; or the same `geometry` and `sources: null` when nothing was cut.
 * A fully covered triangle is dropped. The result is kept per geometry, so the same cuts return the same object.
 */
export function clipFlushOverlaps(geometry, cuts, coordinateStep = 0) {
  if (cuts.length === 0) return { geometry, sources: null };
  const cached = clippedByGeometry.get(geometry) ?? [];
  clippedByGeometry.set(geometry, cached);
  let entry = cached.find(candidate => sameNumbers(candidate.cuts, cuts));
  if (!entry) {
    entry = { cuts, clipped: clipGeometry(geometry, cuts, coordinateStep) };
    cached.push(entry);
    if (cached.length > CACHED_CUTS_PER_GEOMETRY) cached.shift();
  }
  return entry.clipped;
}