Back to Nappakura
SOURCE / PINNED RELEASE

Made of little things.

Nappakura

Release
a75ca0f8b596…
Author-recorded commit
4463126213fa…
License
LICENSE
Author’s source reference
nostr://npub182jczunncwe0jn6frpqwq3e0qjws7yqqnc3auccqv9nte2dnd63scjm4rf/wss%3A%2F%2Fgit.napplet.soy%2F/n-8db03001b62

Archive hash verified: b448d77b767ae754…. The source-to-build association is the author’s claim; it has not been independently rebuilt.

src/modelling.ts
import { cross, dot, length, makeMesh, sub, triangulate, MAX_FACES } from './mesh.js';
import type { V3, Mesh, Face } from './mesh.js';

/** Editable polygons in millimetres. Rendering triangles never define selection. */
export interface Solid {
  vertices: { id: string; point: V3 }[];
  polygons: { id: string; vertices: string[] }[];
  nextId: number;
}
export type ElementKind = 'vertex' | 'edge' | 'polygon';
const fail = (message: string): never => {
  throw new Error(message);
};
const finite = (n: number) => Number.isFinite(n) && Math.abs(n) <= 100000;
export const edgeKey = (a: string, b: string) => [a, b].sort().join(':');
const point = (s: Solid, id: string) =>
  s.vertices.find((v) => v.id === id)?.point ??
  fail(`Unknown vertex ${id}. Inspect the current document.`);
const polygon = (s: Solid, id: string) =>
  s.polygons.find((p) => p.id === id) ??
  fail(`Unknown polygon ${id}. Inspect the current document.`);
const vertex = (s: Solid, p: V3) => {
  const id = `v${s.nextId++}`;
  s.vertices.push({ id, point: p });
  return id;
};
const face = (s: Solid, vertices: string[]) => {
  const id = `p${s.nextId++}`;
  s.polygons.push({ id, vertices });
  return id;
};
const average = (points: V3[]): V3 =>
  [0, 1, 2].map((i) => points.reduce((n, p) => n + p[i], 0) / points.length) as V3;
const add = (a: V3, b: V3): V3 => a.map((n, i) => n + b[i]) as V3;
const mul = (a: V3, n: number): V3 => a.map((v) => v * n) as V3;

export function solidEdges(s: Solid) {
  const edges = new Map<
    string,
    {
      id: string;
      vertices: [string, string];
      polygons: string[];
      directions: string[];
    }
  >();
  for (const p of s.polygons)
    p.vertices.forEach((a, i) => {
      const b = p.vertices[(i + 1) % p.vertices.length],
        id = edgeKey(a, b);
      const e = edges.get(id) ?? {
        id,
        vertices: [a, b],
        polygons: [],
        directions: [],
      };
      e.polygons.push(p.id);
      e.directions.push(a);
      edges.set(id, e);
    });
  return [...edges.values()];
}

export function deriveSolid(s: Solid, name = 'Model') {
  if (
    !s ||
    !Array.isArray(s.vertices) ||
    !Array.isArray(s.polygons) ||
    s.vertices.length > MAX_FACES * 3 ||
    !s.polygons.length ||
    s.polygons.length > MAX_FACES ||
    !Number.isSafeInteger(s.nextId) ||
    s.nextId < 1
  )
    fail('Invalid editable geometry.');
  const ids = new Set<string>();
  for (const item of [...s.vertices, ...s.polygons]) {
    if (
      !/^[vp][1-9][0-9]*$/.test(item.id) ||
      ids.has(item.id) ||
      Number(item.id.slice(1)) >= s.nextId
    )
      fail('Invalid or duplicate geometry ID.');
    ids.add(item.id);
  }
  for (const v of s.vertices)
    if (!Array.isArray(v.point) || v.point.length !== 3 || !v.point.every(finite))
      fail('Coordinates must be finite millimetres.');
  const indices = new Map(s.vertices.map((v, i) => [v.id, i]));
  const triangles: Face[] = [],
    facePolygons: string[] = [];
  const seen = new Set<string>();
  for (const p of s.polygons) {
    if (
      !Array.isArray(p.vertices) ||
      p.vertices.length < 3 ||
      p.vertices.length > 512 ||
      new Set(p.vertices).size !== p.vertices.length
    )
      fail('A polygon needs at least three distinct vertices.');
    const key = [...p.vertices].sort().join(':');
    if (seen.has(key)) fail('Duplicate polygons are not allowed.');
    seen.add(key);
    const list = p.vertices.map(
      (id) => indices.get(id) ?? fail('A polygon refers to a missing vertex.'),
    );
    const ts = triangulate(
      list,
      s.vertices.map((v) => v.point),
    );
    const [pa, pb, pc] = ts[0].map((i) => s.vertices[i].point);
    const pn = cross(sub(pb, pa), sub(pc, pa));
    if (list.some((i) => Math.abs(dot(sub(s.vertices[i].point, pa), pn)) > length(pn) * 1e-5))
      fail(
        'Every polygon must be planar. Split the polygon before moving a corner out of its plane.',
      );
    for (const t of ts) {
      const [a, b, c] = t.map((i) => s.vertices[i].point);
      if (length(cross(sub(b, a), sub(c, a))) < 1e-7)
        fail('This edit would create a degenerate face.');
      triangles.push(t);
      facePolygons.push(p.id);
    }
  }
  if (triangles.length > MAX_FACES)
    fail(`This editor supports ${MAX_FACES} triangles. Simplify the model first.`);
  const edges = solidEdges(s);
  if (edges.some((e) => e.polygons.length > 2)) fail('This edit would create a non-manifold edge.');
  if (edges.some((e) => e.polygons.length === 2 && e.directions[0] === e.directions[1]))
    fail('Adjacent polygons must have consistent winding.');
  // The incident polygon fan at a vertex must remain connected (no bow-ties).
  for (const v of s.vertices) {
    const incident = s.polygons.filter((p) => p.vertices.includes(v.id)).map((p) => p.id);
    const visited = new Set(incident.slice(0, 1));
    const around = edges.filter((e) => e.vertices.includes(v.id));
    for (let i = 0; i < incident.length; i++)
      for (const e of around)
        if (e.polygons.some((id) => visited.has(id))) e.polygons.forEach((id) => visited.add(id));
    if (
      visited.size !== incident.length ||
      around.filter((e) => e.polygons.length === 1).length > 2
    )
      fail('This edit would create a non-manifold vertex.');
  }
  const mesh = makeMesh(
    s.vertices.map((v) => v.point),
    triangles,
    name,
    false,
  );
  // makeMesh normalizes and welds imports. Edits must not silently lose topology.
  const used = new Set(s.polygons.flatMap((p) => p.vertices));
  if (mesh.faces.length !== triangles.length || mesh.vertices.length !== used.size)
    fail('This edit collapses vertices or faces. Use an explicit weld instead.');
  mesh.facePolygons = facePolygons;
  const vertexIds = s.vertices.filter((v) => used.has(v.id)).map((v) => v.id);
  return {
    mesh,
    facePolygons,
    vertexIds,
    size: Math.max(...mesh.dimensions),
    edges,
  };
}

export function solidFromMesh(mesh: Mesh, size: number): Solid {
  const s: Solid = { vertices: [], polygons: [], nextId: 1 };
  const ids = mesh.vertices.map((v) => vertex(s, mul(v, size)));
  for (const group of new Set(mesh.facePolygons)) {
    const faces = mesh.faces
      .map((f, i) => ({ f, i }))
      .filter(({ i }) => mesh.facePolygons[i] === group);
    const directed = faces.flatMap(({ f, i }) =>
      f.flatMap((v, j) => {
        const b = f[(j + 1) % 3];
        const e =
          mesh.edges[
            mesh.faceEdges[i].find(
              (e) => mesh.edges[e].a === Math.min(v, b) && mesh.edges[e].b === Math.max(v, b),
            )!
          ];
        return e.faces.filter((fi) => mesh.facePolygons[fi] === group).length === 1 ? [[v, b]] : [];
      }),
    );
    const loop = directed.length ? [directed[0][0]] : [];
    let cursor = loop[0];
    for (let n = 0; n < directed.length; n++) {
      const next = directed.filter(([a]) => a === cursor);
      if (next.length !== 1) break;
      cursor = next[0][1];
      if (cursor === loop[0]) break;
      loop.push(cursor);
    }
    if (loop.length === directed.length && cursor === loop[0])
      face(
        s,
        loop.map((i) => ids[i]),
      );
    else
      for (const { f } of faces)
        face(
          s,
          f.map((i) => ids[i]),
        );
  }
  return s;
}

export function primitive(kind: 'box' | 'plane' | 'cylinder', size: number, segments = 8): Solid {
  if (!finite(size) || size <= 0 || size > 2000) fail('Choose a size above 0 and at most 2000 mm.');
  const s: Solid = { vertices: [], polygons: [], nextId: 1 },
    h = size / 2;
  if (kind === 'box') {
    const ids = [
      [-h, -h, -h],
      [h, -h, -h],
      [h, h, -h],
      [-h, h, -h],
      [-h, -h, h],
      [h, -h, h],
      [h, h, h],
      [-h, h, h],
    ].map((p) => vertex(s, p as V3));
    [
      [0, 3, 2, 1],
      [4, 5, 6, 7],
      [0, 1, 5, 4],
      [1, 2, 6, 5],
      [2, 3, 7, 6],
      [3, 0, 4, 7],
    ].forEach((p) =>
      face(
        s,
        p.map((i) => ids[i]),
      ),
    );
  } else if (kind === 'plane') {
    face(
      s,
      [
        [-h, -h, 0],
        [h, -h, 0],
        [h, h, 0],
        [-h, h, 0],
      ].map((p) => vertex(s, p as V3)),
    );
  } else if (kind === 'cylinder') {
    if (!Number.isInteger(segments) || segments < 3 || segments > 64)
      fail('Choose 3–64 cylinder sides.');
    const rings = [-h, h].map((z) =>
      Array.from({ length: segments }, (_, i) =>
        vertex(s, [
          h * Math.cos((i * 2 * Math.PI) / segments),
          h * Math.sin((i * 2 * Math.PI) / segments),
          z,
        ]),
      ),
    );
    face(s, [...rings[0]].reverse());
    face(s, rings[1]);
    for (let i = 0; i < segments; i++) {
      const j = (i + 1) % segments;
      face(s, [rings[0][i], rings[0][j], rings[1][j], rings[1][i]]);
    }
  } else fail('Unknown primitive.');
  deriveSolid(s);
  return s;
}

export function selectionVertices(s: Solid, kind: ElementKind, ids: string[]) {
  if (!Array.isArray(ids) || !ids.length || new Set(ids).size !== ids.length)
    fail('Select distinct elements first.');
  if (kind === 'polygon') return [...new Set(ids.flatMap((id) => polygon(s, id).vertices))];
  if (kind === 'edge')
    return [
      ...new Set(
        ids.flatMap(
          (id) => solidEdges(s).find((e) => e.id === id)?.vertices ?? fail(`Unknown edge ${id}.`),
        ),
      ),
    ];
  if (kind !== 'vertex') fail('Select vertices, edges or polygons.');
  ids.forEach((id) => point(s, id));
  return ids;
}

export function transform(
  s: Solid,
  kind: ElementKind,
  ids: string[],
  operation: 'move' | 'rotate' | 'scale',
  values: V3,
  pivot?: V3,
) {
  if (!Array.isArray(values) || values.length !== 3 || !values.every(finite))
    fail('Enter three finite transform values.');
  const selected = selectionVertices(s, kind, ids),
    center = pivot ?? average(selected.map((id) => point(s, id)));
  if (!Array.isArray(center) || center.length !== 3 || !center.every(finite))
    fail('Invalid pivot.');
  if (operation === 'scale' && values.some((v) => v <= 0)) fail('Scale factors must be positive.');
  for (const id of selected) {
    const v = s.vertices.find((v) => v.id === id)!;
    if (operation === 'move') v.point = add(v.point, values);
    else if (operation === 'scale')
      v.point = add(center, sub(v.point, center).map((n, i) => n * values[i]) as V3);
    else if (operation === 'rotate') {
      let p = sub(v.point, center);
      values.forEach((degrees, axis) => {
        const a = (axis + 1) % 3,
          b = (axis + 2) % 3,
          t = (degrees * Math.PI) / 180,
          c = Math.cos(t),
          d = Math.sin(t),
          x = p[a],
          y = p[b];
        p[a] = x * c - y * d;
        p[b] = x * d + y * c;
      });
      v.point = add(center, p);
    } else fail('Unknown transform.');
  }
}

function planarRegion(s: Solid, ids: string[]) {
  selectionVertices(s, 'polygon', ids);
  const ps = ids.map((id) => polygon(s, id)),
    first = ps[0].vertices.map((id) => point(s, id));
  const n0 = first.reduce<V3>(
      (sum, a, i) => add(sum, cross(a, first[(i + 1) % first.length])),
      [0, 0, 0],
    ),
    n = mul(n0, 1 / length(n0));
  if (!n.every(Number.isFinite)) fail('Select a non-degenerate face.');
  if (ps.some((p) => p.vertices.some((id) => Math.abs(dot(sub(point(s, id), first[0]), n)) > 1e-5)))
    fail('Region extrusion needs coplanar faces.');
  const selected = new Set(ids),
    visited = new Set([ids[0]]),
    edges = solidEdges(s);
  for (let i = 0; i < ids.length; i++)
    for (const e of edges)
      if (e.polygons.some((id) => visited.has(id)))
        e.polygons.filter((id) => selected.has(id)).forEach((id) => visited.add(id));
  if (visited.size !== ids.length) fail('Select one connected face region.');
  const boundary = ps.flatMap((p) =>
    p.vertices.flatMap((a, i) => {
      const b = p.vertices[(i + 1) % p.vertices.length];
      return edges.find((e) => e.id === edgeKey(a, b))!.polygons.filter((id) => selected.has(id))
        .length === 1
        ? [[a, b]]
        : [];
    }),
  );
  if (!boundary.length) fail('The selected region has no boundary to extrude.');
  return { ps, n, boundary };
}

export function extrude(s: Solid, ids: string[], distance: number) {
  if (!finite(distance) || Math.abs(distance) < 0.01) fail('Extrusion must be at least 0.01 mm.');
  const { ps, n, boundary } = planarRegion(s, ids);
  const replacements = new Map(
    [...new Set(ps.flatMap((p) => p.vertices))].map((id) => [
      id,
      vertex(s, add(point(s, id), mul(n, distance))),
    ]),
  );
  ps.forEach((p) => {
    p.vertices = p.vertices.map((id) => replacements.get(id)!);
  });
  for (const [a, b] of boundary) face(s, [a, b, replacements.get(b)!, replacements.get(a)!]);
}

export function inset(s: Solid, id: string, ratio: number) {
  if (!Number.isFinite(ratio) || ratio <= 0 || ratio >= 1)
    fail('Inset ratio must be between 0 and 1 (remaining face scale).');
  const { ps, n } = planarRegion(s, [id]),
    p = ps[0],
    old = [...p.vertices],
    points = old.map((id) => point(s, id)),
    center = average(points);
  if (
    points.some(
      (b, i) =>
        dot(
          cross(
            sub(b, points[(i + points.length - 1) % points.length]),
            sub(points[(i + 1) % points.length], b),
          ),
          n,
        ) < -1e-7,
    )
  )
    fail('Inset currently supports convex polygons.');
  p.vertices = points.map((v) => vertex(s, add(center, mul(sub(v, center), ratio))));
  old.forEach((a, i) => {
    const j = (i + 1) % old.length;
    face(s, [a, old[j], p.vertices[j], p.vertices[i]]);
  });
}

export function splitEdge(s: Solid, id: string, fraction = 0.5) {
  const edge = solidEdges(s).find((e) => e.id === id) ?? fail('Select an existing edge.');
  if (!Number.isFinite(fraction) || fraction <= 0 || fraction >= 1)
    fail('Split fraction must be between 0 and 1.');
  const [a, b] = edge.vertices,
    v = vertex(s, add(point(s, a), mul(sub(point(s, b), point(s, a)), fraction)));
  for (const p of s.polygons)
    for (let i = 0; i < p.vertices.length; i++)
      if (edgeKey(p.vertices[i], p.vertices[(i + 1) % p.vertices.length]) === id) {
        p.vertices.splice(i + 1, 0, v);
        break;
      }
  return v;
}

export function weld(s: Solid, ids: string[]) {
  if (ids.length < 2) fail('Select at least two vertices to weld.');
  selectionVertices(s, 'vertex', ids);
  const selected = new Set(ids),
    keep = ids[0],
    target = average(ids.map((id) => point(s, id)));
  s.vertices.find((v) => v.id === keep)!.point = target;
  s.polygons = s.polygons
    .map((p) => {
      const list = p.vertices.map((id) => (selected.has(id) ? keep : id));
      return {
        ...p,
        vertices: list.filter((id, i) => id !== list[(i + list.length - 1) % list.length]),
      };
    })
    .filter((p) => p.vertices.length >= 3);
  s.vertices = s.vertices.filter((v) => !selected.has(v.id) || v.id === keep);
}

export function fillBoundary(s: Solid, edgeId: string) {
  const edges = solidEdges(s).filter((e) => e.polygons.length === 1),
    seed = edges.find((e) => e.id === edgeId) ?? fail('Choose an open boundary edge.');
  const directed = edges.map((e) => {
    const p = polygon(s, e.polygons[0]),
      i = p.vertices.findIndex(
        (a, i) => edgeKey(a, p.vertices[(i + 1) % p.vertices.length]) === e.id,
      );
    return [p.vertices[i], p.vertices[(i + 1) % p.vertices.length]];
  });
  let current = seed.vertices[0];
  const loop: string[] = [];
  while (!loop.includes(current)) {
    loop.push(current);
    const next = directed.filter((e) => e[0] === current);
    if (next.length !== 1) fail('Boundary must be a simple loop.');
    current = next[0][1];
  }
  if (current !== loop[0]) fail('Boundary must be a simple loop.');
  face(s, loop.reverse());
}

/** Copy-before-edit gives callers an atomic result, even when validation fails. */
export function editSolid(s: Solid, action: (copy: Solid) => void) {
  const copy = structuredClone(s);
  action(copy);
  const used = new Set(copy.polygons.flatMap((p) => p.vertices));
  copy.vertices = copy.vertices.filter((v) => used.has(v.id));
  deriveSolid(copy);
  return copy;
}