Skip to content

3D engine that AI agents drive

30.1 KB
Raw Blame
import { createMeshData, DOMAINS } from './mesh-data.js';
import { faceNormals } from './mesh-normals.js';
import { triangulateMesh } from './mesh-render.js';
import { cornerCycles, cornerFaces, edgeCornerTable, UnionFind } from './mesh-topology.js';
import { selectEdges, edgeFaces } from './mesh-bevel.js';
import { requireFiniteInRange } from './modeling-limits.js';

/** The gap between islands, as a share of the square: NaN gives non-finite uv and 0.5 or more leaves no room. */
export const MAX_UV_MARGIN = 0.2;
export function requireUvMargin(functionName, margin) {
  requireFiniteInRange(functionName, 'margin', margin, 0, MAX_UV_MARGIN);
}

// Automatic UV unwrapping: seams from an edge rule, extra cuts until every island is a disk, least-squares conformal
// maps (LSCM, the "Conformal" method Blender offers) solved per island, area normalisation for an even texel density,
// and shelf packing into the unit square.

const MAX_CUT_ROUNDS = 8;
const MAX_SOLVER_ITERATIONS = 4000;

const subtract = (first, second) => [first[0] - second[0], first[1] - second[1], first[2] - second[2]];
const dot = (first, second) => first[0] * second[0] + first[1] * second[1] + first[2] * second[2];
const cross = (first, second) => [first[1] * second[2] - first[2] * second[1], first[2] * second[0] - first[0] * second[2], first[0] * second[1] - first[1] * second[0]];
const length = vector => Math.hypot(vector[0], vector[1], vector[2]);
const normalize = vector => {
  const size = length(vector);
  return size === 0 ? [0, 0, 0] : [vector[0] / size, vector[1] / size, vector[2] / size];
};

function positionOf(mesh, vertex) {
  return [mesh.positions[vertex * 3], mesh.positions[vertex * 3 + 1], mesh.positions[vertex * 3 + 2]];
}

/**
 * Corner groups that share one UV vertex (corners of one mesh vertex joined across uncut edges) and faces grouped
 * into islands (faces joined across uncut edges). Edges with other than two consistently wound faces always cut.
 */
function groupsAndIslands(mesh, seam, table, nextCorner, facesOfCorners) {
  const corners = new UnionFind(mesh.cornerCount);
  const faces = new UnionFind(mesh.faceCount);
  for (let edge = 0; edge < mesh.edgeCount; edge++) {
    if (seam[edge] || table.edgeOffsets[edge + 1] - table.edgeOffsets[edge] !== 2) continue;
    const first = table.edgeCorners[table.edgeOffsets[edge]];
    const second = table.edgeCorners[table.edgeOffsets[edge] + 1];
    if (mesh.cornerVertices[first] === mesh.cornerVertices[second]) continue;
    corners.union(first, nextCorner[second]);
    corners.union(nextCorner[first], second);
    faces.union(facesOfCorners[first], facesOfCorners[second]);
  }
  const islandOfRoot = new Map();
  const islands = [];
  for (let face = 0; face < mesh.faceCount; face++) {
    const root = faces.find(face);
    if (!islandOfRoot.has(root)) {
      islandOfRoot.set(root, islands.length);
      islands.push({ faces: [] });
    }
    islands[islandOfRoot.get(root)].faces.push(face);
  }
  return { corners, islands };
}

/** UV vertices, uncut interior edges and boundary loops of one island. */
function describeIsland(mesh, island, corners, nextCorner, seam) {
  const localOf = new Map();
  const vertexOfLocal = [];
  const cornerLocal = new Map();
  const edgeUses = new Map();
  const interiorEdges = new Set();
  for (const face of island.faces) {
    for (let corner = mesh.faceOffsets[face]; corner < mesh.faceOffsets[face + 1]; corner++) {
      const root = corners.find(corner);
      if (!localOf.has(root)) {
        localOf.set(root, vertexOfLocal.length);
        vertexOfLocal.push(mesh.cornerVertices[corner]);
      }
      cornerLocal.set(corner, localOf.get(root));
    }
  }
  for (const face of island.faces) {
    for (let corner = mesh.faceOffsets[face]; corner < mesh.faceOffsets[face + 1]; corner++) {
      const from = cornerLocal.get(corner);
      const to = cornerLocal.get(nextCorner[corner]);
      const key = from < to ? `${from},${to}` : `${to},${from}`;
      edgeUses.set(key, (edgeUses.get(key) ?? 0) + 1);
      if (!seam[mesh.cornerEdges[corner]]) interiorEdges.add(mesh.cornerEdges[corner]);
    }
  }
  const boundaryNeighbours = new Map();
  for (const [key, uses] of edgeUses) {
    if (uses !== 1) continue;
    const [from, to] = key.split(',').map(Number);
    if (!boundaryNeighbours.has(from)) boundaryNeighbours.set(from, []);
    if (!boundaryNeighbours.has(to)) boundaryNeighbours.set(to, []);
    boundaryNeighbours.get(from).push(to);
    boundaryNeighbours.get(to).push(from);
  }
  const loops = [];
  const visited = new Set();
  for (const start of boundaryNeighbours.keys()) {
    if (visited.has(start)) continue;
    const loop = [];
    const stack = [start];
    visited.add(start);
    while (stack.length) {
      const vertex = stack.pop();
      loop.push(vertex);
      for (const neighbour of boundaryNeighbours.get(vertex)) {
        if (!visited.has(neighbour)) {
          visited.add(neighbour);
          stack.push(neighbour);
        }
      }
    }
    loops.push(loop);
  }
  const euler = vertexOfLocal.length - edgeUses.size + island.faces.length;
  return { localOf, vertexOfLocal, cornerLocal, interiorEdges, loops, euler, isDisk: loops.length === 1 && euler === 1 };
}

class MinHeap {
  constructor() {
    this.keys = [];
    this.items = [];
  }

  get size() {
    return this.keys.length;
  }

  push(key, item) {
    let index = this.keys.length;
    this.keys.push(key);
    this.items.push(item);
    while (index > 0) {
      const parent = (index - 1) >> 1;
      if (this.keys[parent] <= key) break;
      this.swap(index, parent);
      index = parent;
    }
  }

  pop() {
    const top = [this.keys[0], this.items[0]];
    const lastKey = this.keys.pop();
    const lastItem = this.items.pop();
    if (this.keys.length) {
      this.keys[0] = lastKey;
      this.items[0] = lastItem;
      let index = 0;
      for (;;) {
        const left = index * 2 + 1;
        const right = left + 1;
        let smallest = index;
        if (left < this.keys.length && this.keys[left] < this.keys[smallest]) smallest = left;
        if (right < this.keys.length && this.keys[right] < this.keys[smallest]) smallest = right;
        if (smallest === index) break;
        this.swap(index, smallest);
        index = smallest;
      }
    }
    return top;
  }

  swap(first, second) {
    [this.keys[first], this.keys[second]] = [this.keys[second], this.keys[first]];
    [this.items[first], this.items[second]] = [this.items[second], this.items[first]];
  }
}

/** Shortest path along the given edges from any source vertex to any target vertex (Dijkstra by edge length). */
function shortestPath(mesh, edges, sources, targets) {
  const neighbours = new Map();
  for (const edge of edges) {
    const first = mesh.edgeVertices[edge * 2];
    const second = mesh.edgeVertices[edge * 2 + 1];
    const distance = length(subtract(positionOf(mesh, first), positionOf(mesh, second)));
    if (!neighbours.has(first)) neighbours.set(first, []);
    if (!neighbours.has(second)) neighbours.set(second, []);
    neighbours.get(first).push({ vertex: second, edge, distance });
    neighbours.get(second).push({ vertex: first, edge, distance });
  }
  const best = new Map();
  const previous = new Map();
  const queue = new MinHeap();
  for (const source of sources) {
    best.set(source, 0);
    queue.push(0, source);
  }
  while (queue.size) {
    const [distance, vertex] = queue.pop();
    if (distance > best.get(vertex)) continue;
    if (targets.has(vertex) && !sources.has(vertex)) {
      const path = [];
      let current = vertex;
      while (previous.has(current)) {
        const step = previous.get(current);
        path.push(step.edge);
        current = step.from;
      }
      return { path, end: vertex };
    }
    for (const next of neighbours.get(vertex) ?? []) {
      const candidate = distance + next.distance;
      if (candidate < (best.get(next.vertex) ?? Infinity)) {
        best.set(next.vertex, candidate);
        previous.set(next.vertex, { from: vertex, edge: next.edge });
        queue.push(candidate, next.vertex);
      }
    }
  }
  return null;
}

/** Vertex farthest (along the given edges) from a start vertex. */
function farthestVertex(mesh, edges, start) {
  const all = new Set();
  for (const edge of edges) {
    all.add(mesh.edgeVertices[edge * 2]);
    all.add(mesh.edgeVertices[edge * 2 + 1]);
  }
  let farthest = start;
  let farthestDistance = -1;
  for (const vertex of all) {
    const distance = length(subtract(positionOf(mesh, vertex), positionOf(mesh, start)));
    if (distance > farthestDistance) {
      farthestDistance = distance;
      farthest = vertex;
    }
  }
  return farthest;
}

/**
 * Add cuts until every island is a disk: islands with several boundary loops get a cut along the shortest path
 * joining two loops; closed islands get a slit between two far-apart vertices. Returns the number of edges added.
 */
function cutToDisks(mesh, seam, table, nextCorner, facesOfCorners) {
  let added = 0;
  for (let round = 0; round < MAX_CUT_ROUNDS; round++) {
    const { corners, islands } = groupsAndIslands(mesh, seam, table, nextCorner, facesOfCorners);
    let changed = false;
    for (const island of islands) {
      const description = describeIsland(mesh, island, corners, nextCorner, seam);
      if (description.isDisk || !description.interiorEdges.size) continue;
      let path = null;
      if (description.loops.length >= 2) {
        const sources = new Set(description.loops[0].map(local => description.vertexOfLocal[local]));
        const targets = new Set(description.loops.slice(1).flat().map(local => description.vertexOfLocal[local]));
        path = shortestPath(mesh, description.interiorEdges, sources, targets);
      } else if (description.loops.length === 0) {
        const anyVertex = description.vertexOfLocal[0];
        const first = farthestVertex(mesh, description.interiorEdges, anyVertex);
        const second = farthestVertex(mesh, description.interiorEdges, first);
        path = shortestPath(mesh, description.interiorEdges, new Set([first]), new Set([second]));
      }
      if (!path || !path.path.length) continue;
      for (const edge of path.path) {
        if (!seam[edge]) {
          seam[edge] = 1;
          added++;
          changed = true;
        }
      }
    }
    if (!changed) break;
  }
  return added;
}

/**
 * Least squares by conjugate gradients on the normal equations (CGLS), starting from x. Rows are compressed:
 * rowOffsets, columns and values. Columns are scaled by their norms first (Jacobi preconditioning).
 */
function solveLeastSquares({ rowOffsets, columns, values }, columnCount, rightSide, x) {
  const rowCount = rowOffsets.length - 1;
  const columnScale = new Float64Array(columnCount);
  for (let entry = 0; entry < values.length; entry++) columnScale[columns[entry]] += values[entry] * values[entry];
  for (let column = 0; column < columnCount; column++) columnScale[column] = columnScale[column] > 0 ? 1 / Math.sqrt(columnScale[column]) : 0;
  const scaled = new Float64Array(values.length);
  for (let entry = 0; entry < values.length; entry++) scaled[entry] = values[entry] * columnScale[columns[entry]];
  const multiply = (vector, result) => {
    for (let row = 0; row < rowCount; row++) {
      let sum = 0;
      for (let entry = rowOffsets[row]; entry < rowOffsets[row + 1]; entry++) sum += scaled[entry] * vector[columns[entry]];
      result[row] = sum;
    }
  };
  const multiplyTransposed = (vector, result) => {
    result.fill(0);
    for (let row = 0; row < rowCount; row++) {
      const value = vector[row];
      for (let entry = rowOffsets[row]; entry < rowOffsets[row + 1]; entry++) result[columns[entry]] += scaled[entry] * value;
    }
  };
  const squaredNorm = vector => {
    let sum = 0;
    for (let index = 0; index < vector.length; index++) sum += vector[index] * vector[index];
    return sum;
  };
  // Solve for y = x / scale.
  const y = new Float64Array(columnCount);
  for (let column = 0; column < columnCount; column++) y[column] = columnScale[column] > 0 ? x[column] / columnScale[column] : 0;
  const residual = new Float64Array(rowCount);
  multiply(y, residual);
  for (let row = 0; row < rowCount; row++) residual[row] = rightSide[row] - residual[row];
  const gradient = new Float64Array(columnCount);
  multiplyTransposed(residual, gradient);
  const direction = Float64Array.from(gradient);
  const step = new Float64Array(rowCount);
  let gamma = squaredNorm(gradient);
  const tolerance = gamma * 1e-16;
  for (let iteration = 0; iteration < MAX_SOLVER_ITERATIONS && gamma > tolerance && gamma > 0; iteration++) {
    multiply(direction, step);
    const stepNorm = squaredNorm(step);
    if (stepNorm === 0) break;
    const alpha = gamma / stepNorm;
    for (let column = 0; column < columnCount; column++) y[column] += alpha * direction[column];
    for (let row = 0; row < rowCount; row++) residual[row] -= alpha * step[row];
    multiplyTransposed(residual, gradient);
    const nextGamma = squaredNorm(gradient);
    const beta = nextGamma / gamma;
    for (let column = 0; column < columnCount; column++) direction[column] = gradient[column] + beta * direction[column];
    gamma = nextGamma;
  }
  for (let column = 0; column < columnCount; column++) x[column] = y[column] * columnScale[column];
  return x;
}

/** Project island vertices onto the plane of the island's area-weighted normal (counter-clockwise from the front). */
function planarProjection(mesh, description, triangles, normal) {
  const reference = Math.abs(normal[0]) < 0.9 ? [1, 0, 0] : [0, 1, 0];
  const tangent = normalize(cross(reference, normal));
  const bitangent = cross(normal, tangent);
  return description.vertexOfLocal.map(vertex => {
    const point = positionOf(mesh, vertex);
    return [dot(point, tangent), dot(point, bitangent)];
  });
}

/** Least-squares conformal map of one disk island; returns [u, v] per local vertex. */
function conformalMap(mesh, description, triangles, normal) {
  const initial = planarProjection(mesh, description, triangles, normal);
  const count = initial.length;
  if (count < 3 || !description.isDisk) return initial;
  // Pin the two boundary vertices farthest apart, at their projected positions.
  const boundary = description.loops[0];
  let pinA = boundary[0];
  let pinB = boundary[0];
  let widest = -1;
  for (const first of boundary) {
    for (const second of boundary) {
      const distance = length(subtract(positionOf(mesh, description.vertexOfLocal[first]), positionOf(mesh, description.vertexOfLocal[second])));
      if (distance > widest) {
        widest = distance;
        pinA = first;
        pinB = second;
      }
    }
    if (boundary.length > 400) break;
  }
  const columnOf = new Int32Array(count * 2).fill(-1);
  let columns = 0;
  for (let local = 0; local < count; local++) {
    if (local === pinA || local === pinB) continue;
    columnOf[local * 2] = columns++;
    columnOf[local * 2 + 1] = columns++;
  }
  const pinned = new Map([[pinA, initial[pinA]], [pinB, initial[pinB]]]);
  const rowOffsets = [0];
  const rowColumns = [];
  const rowValues = [];
  const rightSide = [];
  const pushRow = (entries, constant) => {
    for (const [column, value] of entries) {
      rowColumns.push(column);
      rowValues.push(value);
    }
    rowOffsets.push(rowColumns.length);
    rightSide.push(constant);
  };
  for (const [first, second, third] of triangles) {
    const pointA = positionOf(mesh, description.vertexOfLocal[first]);
    const pointB = positionOf(mesh, description.vertexOfLocal[second]);
    const pointC = positionOf(mesh, description.vertexOfLocal[third]);
    const edgeAB = subtract(pointB, pointA);
    const edgeAC = subtract(pointC, pointA);
    const sideLength = length(edgeAB);
    const doubleArea = length(cross(edgeAB, edgeAC));
    if (sideLength === 0 || doubleArea === 0) continue;
    // Local triangle coordinates: A at the origin, B on the x axis.
    const local = [[0, 0], [sideLength, 0], [dot(edgeAC, edgeAB) / sideLength, doubleArea / sideLength]];
    const weight = 1 / Math.sqrt(doubleArea);
    const vertices = [first, second, third];
    // W_j = (x_{j+2} - x_{j+1}) + i (y_{j+2} - y_{j+1}); sum_j W_j (u_j + i v_j) = 0 for a conformal map.
    const real = [];
    const imaginary = [];
    let realConstant = 0;
    let imaginaryConstant = 0;
    for (let index = 0; index < 3; index++) {
      const next = local[(index + 1) % 3];
      const after = local[(index + 2) % 3];
      const wReal = (after[0] - next[0]) * weight;
      const wImaginary = (after[1] - next[1]) * weight;
      const vertex = vertices[index];
      if (pinned.has(vertex)) {
        const [u, v] = pinned.get(vertex);
        realConstant += wReal * u - wImaginary * v;
        imaginaryConstant += wImaginary * u + wReal * v;
      } else {
        real.push([columnOf[vertex * 2], wReal], [columnOf[vertex * 2 + 1], -wImaginary]);
        imaginary.push([columnOf[vertex * 2], wImaginary], [columnOf[vertex * 2 + 1], wReal]);
      }
    }
    pushRow(real, -realConstant);
    pushRow(imaginary, -imaginaryConstant);
  }
  const x = new Float64Array(columns);
  for (let local = 0; local < count; local++) {
    if (columnOf[local * 2] === -1) continue;
    x[columnOf[local * 2]] = initial[local][0];
    x[columnOf[local * 2 + 1]] = initial[local][1];
  }
  const rows = { rowOffsets: Int32Array.from(rowOffsets), columns: Int32Array.from(rowColumns), values: Float64Array.from(rowValues) };
  solveLeastSquares(rows, columns, rightSide, x);
  return initial.map((point, local) => pinned.has(local) ? pinned.get(local) : [x[columnOf[local * 2]], x[columnOf[local * 2 + 1]]]);
}

function convexHull(points) {
  const sorted = [...points].sort((left, right) => left[0] - right[0] || left[1] - right[1]);
  const turn = (origin, first, second) => (first[0] - origin[0]) * (second[1] - origin[1]) - (first[1] - origin[1]) * (second[0] - origin[0]);
  const lower = [];
  for (const point of sorted) {
    while (lower.length >= 2 && turn(lower.at(-2), lower.at(-1), point) <= 0) lower.pop();
    lower.push(point);
  }
  const upper = [];
  for (const point of [...sorted].reverse()) {
    while (upper.length >= 2 && turn(upper.at(-2), upper.at(-1), point) <= 0) upper.pop();
    upper.push(point);
  }
  return [...lower.slice(0, -1), ...upper.slice(0, -1)];
}

/** Rotate island coordinates so their bounding box has the least area (tested along every hull edge). */
function rotateToSmallestBox(points) {
  const hull = convexHull(points);
  let bestAngle = 0;
  let bestArea = Infinity;
  for (let index = 0; index < hull.length; index++) {
    const next = hull[(index + 1) % hull.length];
    const angle = -Math.atan2(next[1] - hull[index][1], next[0] - hull[index][0]);
    const cosine = Math.cos(angle);
    const sine = Math.sin(angle);
    let minimumX = Infinity;
    let maximumX = -Infinity;
    let minimumY = Infinity;
    let maximumY = -Infinity;
    for (const [x, y] of hull) {
      const rotatedX = x * cosine - y * sine;
      const rotatedY = x * sine + y * cosine;
      minimumX = Math.min(minimumX, rotatedX);
      maximumX = Math.max(maximumX, rotatedX);
      minimumY = Math.min(minimumY, rotatedY);
      maximumY = Math.max(maximumY, rotatedY);
    }
    const area = (maximumX - minimumX) * (maximumY - minimumY);
    if (area < bestArea) {
      bestArea = area;
      bestAngle = angle;
    }
  }
  const cosine = Math.cos(bestAngle);
  const sine = Math.sin(bestAngle);
  return points.map(([x, y]) => [x * cosine - y * sine, x * sine + y * cosine]);
}

export function bounds2d(points) {
  let minimumX = Infinity;
  let maximumX = -Infinity;
  let minimumY = Infinity;
  let maximumY = -Infinity;
  for (const [x, y] of points) {
    minimumX = Math.min(minimumX, x);
    maximumX = Math.max(maximumX, x);
    minimumY = Math.min(minimumY, y);
    maximumY = Math.max(maximumY, y);
  }
  return { minimumX, minimumY, width: maximumX - minimumX, height: maximumY - minimumY };
}

function signedArea2d(first, second, third) {
  return ((second[0] - first[0]) * (third[1] - first[1]) - (second[1] - first[1]) * (third[0] - first[0])) / 2;
}

function triangleArea3d(mesh, description, [first, second, third]) {
  const pointA = positionOf(mesh, description.vertexOfLocal[first]);
  const toB = subtract(positionOf(mesh, description.vertexOfLocal[second]), pointA);
  const toC = subtract(positionOf(mesh, description.vertexOfLocal[third]), pointA);
  return length(cross(toB, toC)) / 2;
}

/**
 * Flatten one island: conformal map (or a planar projection when it is not a disk), facing up, scaled so its UV area
 * equals its surface area, rotated to its smallest box. Reports flipped triangles and area distortion.
 */
function flattenIsland(mesh, island, context) {
  const { corners, nextCorner, seam, faceNormal, faceArea, triangleCorners, trianglesOfFace } = context;
  const description = describeIsland(mesh, island, corners, nextCorner, seam);
  const triangles = [];
  const normalSum = [0, 0, 0];
  let area = 0;
  for (const face of island.faces) {
    area += faceArea[face];
    for (let axis = 0; axis < 3; axis++) normalSum[axis] += faceNormal[face * 3 + axis] * faceArea[face];
    for (const triangle of trianglesOfFace.get(face) ?? []) {
      triangles.push([0, 1, 2].map(offset => description.cornerLocal.get(triangleCorners[triangle * 3 + offset])));
    }
  }
  let points = conformalMap(mesh, description, triangles, normalize(normalSum));
  let uvArea = 0;
  for (const [first, second, third] of triangles) uvArea += signedArea2d(points[first], points[second], points[third]);
  if (uvArea < 0) {
    points = points.map(([u, v]) => [-u, v]);
    uvArea = -uvArea;
  }
  const scaleToArea = uvArea > 0 ? Math.sqrt(area / uvArea) : 1;
  points = rotateToSmallestBox(points.map(([u, v]) => [u * scaleToArea, v * scaleToArea]));
  let flipped = 0;
  let distortion = 0;
  for (const triangle of triangles) {
    const area2d = signedArea2d(points[triangle[0]], points[triangle[1]], points[triangle[2]]);
    const area3d = triangleArea3d(mesh, description, triangle);
    if (area2d < 0) flipped++;
    if (area3d > 0) distortion += Math.abs(Math.abs(area2d) / area3d - 1) * area3d;
  }
  return {
    island, description, triangles, points, area, flipped,
    distortion: area > 0 ? distortion / area : 0,
    box: bounds2d(points),
  };
}

/** Shelf layout of island boxes for one row width: offsets per island and the overall extent. */
function shelfLayout(placed, rowWidth, gap) {
  const offsets = [];
  let cursorX = 0;
  let cursorY = 0;
  let rowHeight = 0;
  let layoutWidth = 0;
  for (const item of placed) {
    if (cursorX > 0 && cursorX + item.box.width > rowWidth) {
      cursorX = 0;
      cursorY += rowHeight + gap;
      rowHeight = 0;
    }
    offsets.push([cursorX - item.box.minimumX, cursorY - item.box.minimumY]);
    cursorX += item.box.width + gap;
    rowHeight = Math.max(rowHeight, item.box.height);
    layoutWidth = Math.max(layoutWidth, cursorX - gap);
  }
  return { offsets, extent: Math.max(layoutWidth, cursorY + rowHeight, 1e-12) };
}

/**
 * Pack islands into the unit square: each lies landscape, tallest first, in shelves; several row widths are tried and
 * the most compact kept (rotate false keeps each island upright). Sets item.offset and returns the scale from island units to UV.
 */
export function packIslands(placed, margin, rotate = true) {
  for (const item of placed) {
    if (rotate && item.box.height > item.box.width) {
      item.points = item.points.map(([u, v]) => [v, -u]);
      item.box = bounds2d(item.points);
    }
  }
  placed.sort((left, right) => right.box.height - left.box.height || right.box.width - left.box.width);
  const totalBoxArea = placed.reduce((sum, item) => sum + Math.max(item.box.width, 1e-9) * Math.max(item.box.height, 1e-9), 0);
  const gap = margin * Math.sqrt(totalBoxArea) * 1.2;
  const widest = Math.max(...placed.map(item => item.box.width));
  let best = null;
  for (let factor = 0.6; factor <= 3; factor += 0.1) {
    const layout = shelfLayout(placed, Math.max(widest, Math.sqrt(totalBoxArea) * factor), gap);
    if (!best || layout.extent < best.extent) best = layout;
  }
  placed.forEach((item, index) => {
    item.offset = best.offsets[index];
  });
  return (1 - 2 * margin) / best.extent;
}

/** Mark edges between faces that face different principal axes, inside the given islands. Returns edges added. */
function splitIntoAxisCharts(mesh, islands, seam, table, faceNormal) {
  const axisOfFace = face => {
    let best = 0;
    for (let axis = 1; axis < 3; axis++) {
      if (Math.abs(faceNormal[face * 3 + axis]) > Math.abs(faceNormal[face * 3 + best])) best = axis;
    }
    return best * 2 + (faceNormal[face * 3 + best] < 0 ? 1 : 0);
  };
  const facesOfCorners = cornerFaces(mesh);
  const chosen = new Uint8Array(mesh.faceCount);
  for (const island of islands) for (const face of island.faces) chosen[face] = 1;
  let added = 0;
  for (let edge = 0; edge < mesh.edgeCount; edge++) {
    if (seam[edge] || table.edgeOffsets[edge + 1] - table.edgeOffsets[edge] !== 2) continue;
    const first = facesOfCorners[table.edgeCorners[table.edgeOffsets[edge]]];
    const second = facesOfCorners[table.edgeCorners[table.edgeOffsets[edge] + 1]];
    if (!chosen[first] || !chosen[second] || axisOfFace(first) === axisOfFace(second)) continue;
    seam[edge] = 1;
    added++;
  }
  return added;
}

/**
 * Unwrap the mesh into corner attribute `uv` (and edge attribute `seam`).
 * seams: an edge rule (see selectEdges), default { angle: 60 }. Islands that still are not disks, fold over, or stretch
 * more than maxDistortion are split into charts by the axis their faces face and flattened again.
 * margin: gap between islands and around the square, as a fraction of it. Returns the new mesh and a report:
 * islands, seamEdges (from the rule), cutEdges (added to make disks), chartEdges (added by the split), flatIslands
 * (projected, not disks), flipped triangles, areaDistortion (area-weighted mean of |uv area / mesh area - 1| after one
 * global scale), and utilization (share of the square islands cover).
 */
export function unwrapUv(mesh, { seams = { angle: 60 }, margin = 0.01, maxDistortion = 0.25 } = {}) {
  requireUvMargin('unwrapUv', margin);
  requireFiniteInRange('unwrapUv', 'maxDistortion', maxDistortion, 0, 100);
  const table = edgeCornerTable(mesh);
  const { nextCorner } = cornerCycles(mesh);
  const facesOfCorners = cornerFaces(mesh);
  const seam = selectEdges(mesh, seams, edgeFaces(mesh));
  let seamEdges = 0;
  for (let edge = 0; edge < mesh.edgeCount; edge++) seamEdges += seam[edge];
  const { normals: faceNormal, areas: faceArea } = faceNormals(mesh);
  // A closed island (a sphere, a rounded box with no sharp edges) flattens badly from a single slit, so it goes
  // straight to axis charts instead of being solved twice.
  const initial = groupsAndIslands(mesh, seam, table, nextCorner, facesOfCorners);
  const closedIslands = initial.islands.filter(island => !describeIsland(mesh, island, initial.corners, nextCorner, seam).loops.length);
  let chartEdges = closedIslands.length ? splitIntoAxisCharts(mesh, closedIslands, seam, table, faceNormal) : 0;
  let cutEdges = cutToDisks(mesh, seam, table, nextCorner, facesOfCorners);
  const { triangleCorners, triangleFaces } = triangulateMesh(mesh, faceNormal);
  const trianglesOfFace = new Map();
  for (let triangle = 0; triangle < triangleFaces.length; triangle++) {
    const face = triangleFaces[triangle];
    if (!trianglesOfFace.has(face)) trianglesOfFace.set(face, []);
    trianglesOfFace.get(face).push(triangle);
  }
  const flattenAll = () => {
    const { corners, islands } = groupsAndIslands(mesh, seam, table, nextCorner, facesOfCorners);
    const context = { corners, nextCorner, seam, faceNormal, faceArea, triangleCorners, trianglesOfFace };
    return islands.map(island => flattenIsland(mesh, island, context));
  };
  let placed = flattenAll();
  const poor = placed.filter(item => !item.description.isDisk || item.flipped > 0 || item.distortion > maxDistortion);
  if (poor.length) {
    const splitEdges = splitIntoAxisCharts(mesh, poor.map(item => item.island), seam, table, faceNormal);
    chartEdges += splitEdges;
    if (splitEdges) {
      cutEdges += cutToDisks(mesh, seam, table, nextCorner, facesOfCorners);
      placed = flattenAll();
    }
  }
  const islands = placed.map(item => item.island);
  const flatIslands = placed.filter(item => !item.description.isDisk).length;
  const scale = packIslands(placed, margin);
  const uv = new Float32Array(mesh.cornerCount * 2);
  let flipped = 0;
  let uvAreaTotal = 0;
  let meshAreaTotal = 0;
  const triangleRatios = [];
  for (const item of placed) {
    const final = item.points.map(([u, v]) => [margin + (u + item.offset[0]) * scale, margin + (v + item.offset[1]) * scale]);
    for (const face of item.island.faces) {
      for (let corner = mesh.faceOffsets[face]; corner < mesh.faceOffsets[face + 1]; corner++) {
        const [u, v] = final[item.description.cornerLocal.get(corner)];
        uv[corner * 2] = u;
        uv[corner * 2 + 1] = v;
      }
    }
    for (const [first, second, third] of item.triangles) {
      const area2d = signedArea2d(final[first], final[second], final[third]);
      const pointA = positionOf(mesh, item.description.vertexOfLocal[first]);
      const area3d = length(cross(subtract(positionOf(mesh, item.description.vertexOfLocal[second]), pointA), subtract(positionOf(mesh, item.description.vertexOfLocal[third]), pointA))) / 2;
      if (area2d < 0) flipped++;
      uvAreaTotal += Math.abs(area2d);
      meshAreaTotal += area3d;
      triangleRatios.push([Math.abs(area2d), area3d]);
    }
  }
  const globalRatio = meshAreaTotal > 0 ? uvAreaTotal / meshAreaTotal : 1;
  let distortion = 0;
  for (const [area2d, area3d] of triangleRatios) {
    if (area3d > 0) distortion += Math.abs(area2d / (area3d * globalRatio) - 1) * area3d;
  }
  const attributes = {};
  for (const domain of DOMAINS) attributes[domain] = { ...mesh.attributes[domain] };
  attributes.corner.uv = { data: uv, size: 2 };
  const seamData = new Uint8Array(seam);
  attributes.edge.seam = { data: seamData, size: 1 };
  const result = createMeshData({
    positions: mesh.positions, faceOffsets: mesh.faceOffsets, cornerVertices: mesh.cornerVertices,
    edgeVertices: mesh.edgeVertices, cornerEdges: mesh.cornerEdges, attributes,
  });
  return {
    mesh: result,
    islands: islands.length,
    seamEdges,
    cutEdges,
    chartEdges,
    flatIslands,
    flipped,
    areaDistortion: meshAreaTotal > 0 ? distortion / meshAreaTotal : 0,
    utilization: uvAreaTotal,
  };
}