Merge, spin, bridge, slide and smooth

/**
 * Merge vertices into one: at their centre, at the first or the last listed, or at a point. Faces that lose corners
 * shrink; faces left with fewer than three go. → the vertex kept.
 */
export function mergeVerts(m, verts, at = 'center') {
  const vs = [...new Set(verts)].filter((v) => !m.vertDead(v));
  if (vs.length < 2) return vs[0] ?? -1;
  const keep = at === 'last' ? vs[vs.length - 1] : vs[0];
  let p;
  if (Array.isArray(at)) p = at;
  else if (at === 'center') { p = [0, 0, 0]; for (const v of vs) p = add(p, P3(m, v)); p = mul(p, 1 / vs.length); }
  else p = P3(m, keep);
  const map = new Map(vs.map((v) => [v, keep]));
  remap(m, map);
  m.setPos(keep, p[0], p[1], p[2]);
  return keep;
}

/** Merge vertices closer than `dist` (among `verts`, else all): → how many were merged away. */
export function mergeByDistance(m, dist, verts = null) {
  const vs = verts ? [...new Set(verts)] : Array.from({ length: m.nv }, (_, i) => i);
  const live = vs.filter((v) => !m.vertDead(v));
  const cell = Math.max(dist, 1e-9), grid = new Map(), map = new Map();
  const kk = (x, y, z) => x + ',' + y + ',' + z;
  for (const v of live) {
    const p = P3(m, v), c = p.map((x) => Math.floor(x / cell));
    let hit = -1;
    for (let dx = -1; dx <= 1 && hit < 0; dx++) for (let dy = -1; dy <= 1 && hit < 0; dy++) for (let dz = -1; dz <= 1 && hit < 0; dz++) {
      for (const w of grid.get(kk(c[0] + dx, c[1] + dy, c[2] + dz)) || []) if (len(sub(P3(m, w), p)) <= dist) { hit = w; break; }
    }
    if (hit >= 0) { map.set(v, hit); continue; }
    const k = kk(c[0], c[1], c[2]);
    if (!grid.has(k)) grid.set(k, []);
    grid.get(k).push(v);
  }
  if (map.size) remap(m, map);
  return map.size;
}

/**
 * Spin: extrude a region of faces (or open border edges) round an axis `steps` times by `angle` (radians) in all,
 * about `center`, axis `axis` (unit). A full turn (2π) joins the last step to the first. → {verts (the last copy's), faces}.
 */
export function spin(m, { faces = [], edges = [], center = [0, 0, 0], axis = [0, 0, 1], angle = Math.PI * 2, steps = 12 } = {}) {
  const n = Math.max(1, Math.min(512, Math.round(steps)));
  const full = Math.abs(Math.abs(angle) - Math.PI * 2) < 1e-9;
  const rot = (p, a) => {
    const k = norm(axis), q = sub(p, center), c = Math.cos(a), sn = Math.sin(a);
    return add(center, add(add(mul(q, c), mul(cross(k, q), sn)), mul(k, dot(k, q) * (1 - c))));
  };
  let curF = liveFaces(m, faces), curE = edges.filter((h) => !m.heDead(h) && m.hTw[h] < 0), made = [];
  if (curF.length) {
    // a region facing against the way it turns is turned over first, so the solid made faces out
    let nrm = [0, 0, 0], c = [0, 0, 0], k = 0;
    const t = [0, 0, 0];
    for (const f of curF) { m.faceNormalRaw(f, t); nrm = add(nrm, t); c = add(c, m.faceCenter(f)); k++; }
    const tangent = mul(cross(norm(axis), sub(mul(c, 1 / k), center)), Math.sign(angle) || 1);
    if (dot(nrm, tangent) < 0) curF = flipFaces(m, curF);
  }
  const start = new Map();
  // the region where it starts: a cap there (the region's own faces move on with the spin)
  const startCap = curF.map((f) => ({ corners: m.faceCorners(f, []).slice(), mat: m.fMat[f], from: f }));
  const firstVerts = new Set();
  for (const c of startCap) for (const h of c.corners) firstVerts.add(m.hV[h]);
  for (const h of curE) { firstVerts.add(m.hV[h]); firstVerts.add(m.head(h)); }
  for (let i = 1; i <= n; i++) {
    const r = curF.length ? extrudeRegion(m, curF) : extrudeEdges(m, curE);
    const a = (angle * i) / n;
    for (const v of r.verts) {
      if (!start.has(v)) {
        // the copy's start: the vertex it came from, followed back to the first step's
        const src = sourceOf(m, v);
        start.set(v, start.get(src) ?? src);
      }
      const p0 = P3(m, start.get(v));
      const p = rot(p0, a);
      m.setPos(v, p[0], p[1], p[2]);
    }
    made = r.verts;
    if (curF.length) curF = r.faces;
    else curE = openOf(m, r.verts);
  }
  if (full) {
    // the last step lands on the first: its end faces go, its ring is merged onto the start's
    if (curF.length) m.removeFaces(curF, { keepLoose: true });
    mergeByDistance(m, 1e-7 * Math.max(1, len(sub(P3(m, made[0] ?? 0), center))), [...firstVerts, ...made]);
  } else if (startCap.length) {
    m.replaceFaces([], startCap.map((c) => { const rc = c.corners.slice().reverse(); return { verts: rc.map((h) => m.hV[h]), mat: c.mat, corners: rc }; }));
  }
  return { verts: made };
}

/** The vertex a freshly copied vertex was made from: the one at the same place joined to it by an edge. */
function sourceOf(m, v) {
  const p = P3(m, v);
  for (const h of m.outgoing(v)) { const w = m.head(h); if (len(sub(P3(m, w), p)) < 1e-12) return w; }
  for (let h = 0; h < m.nh; h++) if (!m.heDead(h) && m.head(h) === v) { const w = m.hV[h]; if (len(sub(P3(m, w), p)) < 1e-12) return w; }
  return v;
}

// B runs the opposite way round to A when facing it: try both directions and every rotation
let best = null;
for (const dir of [1, -1]) for (let r = 0; r < n; r++) {
  let d = 0;
  for (let i = 0; i < n; i++) d += len(sub(P3(m, A[i]), P3(m, B[(r + dir * i + n * n) % n])));
  if (!best || d < best.d) best = { d, dir, r };
}

/** Put the slid vertices at t (−1…1) along their rails from their places in `base` (Float64Array of x, y, z per vertex, or the mesh's own). */
export function applySlide(m, rails, t, base) {
  for (const [v, r] of rails) {
    const p = base ? [base[v * 3], base[v * 3 + 1], base[v * 3 + 2]] : P3(m, v);
    const w = t >= 0 ? r.a : r.b;
    if (w < 0) continue;
    const q = lerp(p, P3(m, w), Math.abs(t));
    m.setPos(v, q[0], q[1], q[2]);
  }
}

export function smoothVerts(m, verts, { factor = 0.5, repeat = 1 } = {}) {
  const vs = [...new Set(verts)].filter((v) => !m.vertDead(v) && m.vHe[v] >= 0);
  for (let r = 0; r < repeat; r++) {
    const next = vs.map((v) => {
      const border = m.isBoundaryVert(v);
      const nb = m.outgoing(v).map((h) => m.head(h));
      if (border) { const ring = m.outgoing(v); nb.length = 0; nb.push(m.head(ring[ring.length - 1]), m.hV[m.hPv[ring[0]]]); }
      let c = [0, 0, 0];
      for (const w of nb) c = add(c, P3(m, w));
      c = mul(c, 1 / nb.length);
      return lerp(P3(m, v), c, factor);
    });
    vs.forEach((v, i) => m.setPos(v, next[i][0], next[i][1], next[i][2]));
  }
}