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/mesh.ts
export type V2 = [number, number];
export type V3 = [number, number, number];
export type Face = [number, number, number];
export interface Edge {
  id: number;
  a: number;
  b: number;
  faces: number[];
}
export interface Mesh {
  name: string;
  vertices: V3[];
  faces: Face[];
  edges: Edge[];
  faceEdges: number[][];
  normals: V3[];
  warnings: string[];
  dimensions: V3;
  inverted: boolean;
  /** One planar surface per group; rendering triangles are implementation details. */
  facePolygons: string[];
}
export const MAX_FACES = 2000;
export const sub = (a: V3, b: V3): V3 => [a[0] - b[0], a[1] - b[1], a[2] - b[2]];
export const dot = (a: V3, b: V3) => a[0] * b[0] + a[1] * b[1] + a[2] * b[2];
export const cross = (a: V3, b: V3): V3 => [
  a[1] * b[2] - a[2] * b[1],
  a[2] * b[0] - a[0] * b[2],
  a[0] * b[1] - a[1] * b[0],
];
export const length = (a: V3) => Math.hypot(...a);
export const distance = (a: V3, b: V3) => length(sub(a, b));
export const cross2 = (a: V2, b: V2, c: V2) =>
  (b[0] - a[0]) * (c[1] - a[1]) - (b[1] - a[1]) * (c[0] - a[0]);

export function inside(p: V2, t: V2[]) {
  const signs = t.map((a, i) => cross2(a, t[(i + 1) % t.length], p));
  return signs.every((n) => n >= -1e-8) || signs.every((n) => n <= 1e-8);
}

// Separating axes: contact at a shared edge/vertex is allowed; positive area is not.
export function overlaps(a: V2[], b: V2[], epsilon = 1e-7): boolean {
  for (const poly of [a, b])
    for (let i = 0; i < poly.length; i++) {
      const p = poly[i],
        q = poly[(i + 1) % poly.length];
      const len = Math.hypot(q[0] - p[0], q[1] - p[1]);
      if (len < epsilon) continue;
      const axis: V2 = [-(q[1] - p[1]) / len, (q[0] - p[0]) / len];
      const aa = a.map((v) => v[0] * axis[0] + v[1] * axis[1]);
      const bb = b.map((v) => v[0] * axis[0] + v[1] * axis[1]);
      if (
        Math.min(Math.max(...aa), Math.max(...bb)) - Math.max(Math.min(...aa), Math.min(...bb)) <=
        epsilon
      )
        return false;
    }
  return true;
}

export function triangulate(ids: number[], vertices: V3[]): Face[] {
  if (ids.length === 3) return [ids as Face];
  if (ids.length > 512)
    throw new Error('An OBJ polygon has over 512 vertices. Triangulate it before importing.');
  const normal: V3 = [0, 0, 0];
  ids.forEach((id, i) => {
    const p = vertices[id],
      q = vertices[ids[(i + 1) % ids.length]];
    normal[0] += (p[1] - q[1]) * (p[2] + q[2]);
    normal[1] += (p[2] - q[2]) * (p[0] + q[0]);
    normal[2] += (p[0] - q[0]) * (p[1] + q[1]);
  });
  const drop = normal.map(Math.abs).indexOf(Math.max(...normal.map(Math.abs)));
  const points = ids.map((id) => vertices[id].filter((_, i) => i !== drop) as V2);
  const area = points.reduce(
    (s, p, i) =>
      s + p[0] * points[(i + 1) % points.length][1] - p[1] * points[(i + 1) % points.length][0],
    0,
  );
  if (Math.abs(area) < 1e-16)
    throw new Error(
      'An OBJ polygon has no area or crosses itself. Repair the model before importing.',
    );
  const winding = Math.sign(area),
    remaining = ids.map((_, i) => i),
    out: Face[] = [];
  while (remaining.length > 3) {
    let found = false;
    for (let j = 0; j < remaining.length; j++) {
      const a = remaining[(j + remaining.length - 1) % remaining.length],
        b = remaining[j],
        c = remaining[(j + 1) % remaining.length];
      if (cross2(points[a], points[b], points[c]) * winding <= 1e-12) continue;
      if (
        remaining.some(
          (k) =>
            k !== a && k !== b && k !== c && inside(points[k], [points[a], points[b], points[c]]),
        )
      )
        continue;
      out.push([ids[a], ids[b], ids[c]]);
      remaining.splice(j, 1);
      found = true;
      break;
    }
    if (!found)
      throw new Error(
        'An OBJ polygon is self-intersecting or degenerate. Triangulate or repair it first.',
      );
  }
  out.push(remaining.map((i) => ids[i]) as Face);
  return out;
}

export function parseModel(bytes: Uint8Array, name: string): Mesh {
  if (bytes.length > 8 * 1024 * 1024) throw new Error('Use a model smaller than 8 MiB.');
  const vertices: V3[] = [],
    faces: Face[] = [];
  if (name.toLowerCase().endsWith('.obj')) {
    const lines = new TextDecoder()
      .decode(bytes)
      .replace(/\\\r?\n/g, ' ')
      .split(/\r?\n/);
    for (const line of lines) {
      const [kind, ...tokens] = line.split('#')[0].trim().split(/\s+/);
      if (kind === 'v') {
        if (tokens.length < 3) throw new Error('An OBJ vertex is incomplete.');
        vertices.push(tokens.slice(0, 3).map(Number) as V3);
      }
      if (kind === 'f') {
        const ids = tokens.map((token) => {
          const n = Number(token.split('/')[0]);
          const id = n < 0 ? vertices.length + n : n - 1;
          if (!Number.isInteger(n) || n === 0 || id < 0 || id >= vertices.length)
            throw new Error('An OBJ face refers to a missing vertex.');
          return id;
        });
        if (ids.length < 3) throw new Error('An OBJ face needs at least three vertices.');
        if (ids[0] === ids.at(-1)) ids.pop();
        faces.push(...triangulate(ids, vertices));
      }
      if (faces.length > MAX_FACES || vertices.length > 100000)
        throw new Error(
          `This version supports up to ${MAX_FACES.toLocaleString()} triangles. Simplify the mesh first.`,
        );
    }
  } else if (name.toLowerCase().endsWith('.stl')) {
    const view = new DataView(bytes.buffer, bytes.byteOffset, bytes.byteLength);
    const count = bytes.length >= 84 ? view.getUint32(80, true) : 0;
    if (bytes.length >= 84 && 84 + count * 50 === bytes.length) {
      if (count > MAX_FACES)
        throw new Error(
          `This STL has ${count.toLocaleString()} triangles. Simplify it to ${MAX_FACES.toLocaleString()} or fewer.`,
        );
      for (let i = 0; i < count; i++) {
        const face: Face = [vertices.length, vertices.length + 1, vertices.length + 2];
        for (let j = 0; j < 3; j++) {
          const o = 84 + i * 50 + 12 + j * 12;
          vertices.push([
            view.getFloat32(o, true),
            view.getFloat32(o + 4, true),
            view.getFloat32(o + 8, true),
          ]);
        }
        faces.push(face);
      }
    } else {
      const source = new TextDecoder().decode(bytes);
      if (!/^\s*solid\b/i.test(source)) throw new Error('Invalid or truncated STL file.');
      const facets = [...source.matchAll(/facet\s+normal\s+[^\r\n]+[\s\S]*?endfacet/gi)];
      if (facets.length > MAX_FACES)
        throw new Error(`Simplify this STL to ${MAX_FACES.toLocaleString()} triangles or fewer.`);
      for (const facet of facets) {
        const matches = [...facet[0].matchAll(/\bvertex\s+(\S+)\s+(\S+)\s+(\S+)/gi)];
        if (matches.length !== 3) throw new Error('An STL facet must have exactly three vertices.');
        const base = vertices.length;
        vertices.push(...matches.map((m) => m.slice(1, 4).map(Number) as V3));
        faces.push([base, base + 1, base + 2]);
      }
      if ((source.match(/\bfacet\s+normal\b/gi) || []).length !== facets.length)
        throw new Error('Incomplete STL facet.');
    }
  } else throw new Error('Choose an OBJ or STL file.');
  return makeMesh(vertices, faces, name);
}

export function makeMesh(raw: V3[], rawFaces: Face[], name: string, repair = true): Mesh {
  if (!raw.length || !rawFaces.length) throw new Error('This file has no polygon faces.');
  if (rawFaces.length > MAX_FACES || raw.length > 100000)
    throw new Error('Model exceeds the 2,000-triangle limit.');
  if (raw.some((v) => v.length !== 3 || v.some((n) => !Number.isFinite(n) || Math.abs(n) > 1e12)))
    throw new Error('The model contains invalid coordinates.');
  if (
    rawFaces.some(
      (f) => f.length !== 3 || f.some((i) => !Number.isInteger(i) || i < 0 || i >= raw.length),
    )
  )
    throw new Error('The model contains invalid face indices.');
  const min: V3 = [Infinity, Infinity, Infinity],
    max: V3 = [-Infinity, -Infinity, -Infinity];
  const used = new Set(rawFaces.flat());
  raw.forEach((v, index) => {
    if (!used.has(index)) return;
    v.forEach((n, i) => {
      min[i] = Math.min(min[i], n);
      max[i] = Math.max(max[i], n);
    });
  });
  const dimensions = max.map((n, i) => n - min[i]) as V3,
    span = Math.max(...dimensions);
  if (span < 1e-12) throw new Error('The model has zero size.');
  const normalized = raw.map((v) => v.map((n, i) => (n - (min[i] + max[i]) / 2) / span) as V3);
  const vertices: V3[] = [],
    mapping: number[] = [],
    bins = new Map<string, number[]>(),
    eps = 1e-7;
  for (const [index, v] of normalized.entries()) {
    if (!used.has(index)) {
      mapping.push(-1);
      continue;
    }
    const cell = v.map((n) => Math.floor(n / eps));
    let id = -1;
    for (let x = -1; x <= 1 && id < 0; x++)
      for (let y = -1; y <= 1 && id < 0; y++)
        for (let z = -1; z <= 1 && id < 0; z++) {
          const found = bins
            .get(`${cell[0] + x},${cell[1] + y},${cell[2] + z}`)
            ?.find((i) => distance(vertices[i], v) <= eps);
          if (found !== undefined) id = found;
        }
    if (id < 0) {
      id = vertices.length;
      vertices.push(v);
      const key = cell.join(',');
      bins.set(key, [...(bins.get(key) || []), id]);
    }
    mapping.push(id);
  }
  const faces: Face[] = [],
    seen = new Set<string>();
  let removed = 0;
  rawFaces.forEach((rawFace) => {
    const f = rawFace.map((i) => mapping[i]) as Face,
      key = [...f].sort((a, b) => a - b).join(',');
    if (
      new Set(f).size < 3 ||
      length(cross(sub(vertices[f[1]], vertices[f[0]]), sub(vertices[f[2]], vertices[f[0]]))) <
        1e-12 ||
      seen.has(key)
    ) {
      removed++;
      return;
    }
    seen.add(key);
    faces.push(f);
  });
  if (!faces.length) throw new Error('All faces are degenerate or duplicates.');
  const edges: Edge[] = [],
    faceEdges: number[][] = faces.map(() => []),
    edgeMap = new Map<string, number>();
  faces.forEach((f, fi) =>
    f.forEach((a, j) => {
      const b = f[(j + 1) % 3],
        key = [Math.min(a, b), Math.max(a, b)].join(':');
      let id = edgeMap.get(key);
      if (id === undefined) {
        id = edges.length;
        edgeMap.set(key, id);
        edges.push({ id, a: Math.min(a, b), b: Math.max(a, b), faces: [] });
      }
      edges[id].faces.push(fi);
      faceEdges[fi].push(id);
    }),
  );
  let repaired = 0,
    conflicts = 0;
  if (repair) {
    const visited = new Set<number>();
    for (let seed = 0; seed < faces.length; seed++) {
      if (visited.has(seed)) continue;
      const component = [seed];
      visited.add(seed);
      for (let k = 0; k < component.length; k++) {
        const fi = component[k];
        for (const ei of faceEdges[fi]) {
          const edge = edges[ei];
          if (edge.faces.length !== 2) continue;
          const next = edge.faces.find((n) => n !== fi)!;
          const direction = (f: Face) => f[(f.indexOf(edge.a) + 1) % 3] === edge.b;
          const same = direction(faces[fi]) === direction(faces[next]);
          if (visited.has(next)) {
            if (same) conflicts++;
            continue;
          }
          if (same) {
            faces[next] = [faces[next][0], faces[next][2], faces[next][1]];
            repaired++;
          }
          visited.add(next);
          component.push(next);
        }
      }
      const closed = component.every((fi) =>
        faceEdges[fi].every((ei) => edges[ei].faces.length === 2),
      );
      const volume = component.reduce((sum, fi) => {
        const f = faces[fi];
        return sum + dot(vertices[f[0]], cross(vertices[f[1]], vertices[f[2]]));
      }, 0);
      if (closed && volume < 0)
        component.forEach((fi) => {
          faces[fi] = [faces[fi][0], faces[fi][2], faces[fi][1]];
        });
    }
  }
  // Canonical IDs survive winding repair and project reloads. Face iteration
  // order cannot identify edges: repairing winding changes that order.
  edges.sort((a, b) => a.a - b.a || a.b - b.b);
  faceEdges.forEach((list) => list.splice(0));
  edges.forEach((edge, id) => {
    edge.id = id;
    edge.faces.forEach((face) => faceEdges[face].push(id));
  });
  const normals = faces.map((f) => {
    const n = cross(sub(vertices[f[1]], vertices[f[0]]), sub(vertices[f[2]], vertices[f[0]]));
    const l = length(n);
    return n.map((x) => x / l) as V3;
  });
  const warnings: string[] = [];
  const open = edges.filter((e) => e.faces.length === 1).length,
    nonManifold = edges.filter((e) => e.faces.length > 2).length;
  if (open) warnings.push(`${open} open edges have no matching glue tabs.`);
  if (nonManifold)
    warnings.push(
      `${nonManifold} non-manifold edges cannot be joined. Repair them in your modeler.`,
    );
  if (removed) warnings.push(`Removed ${removed} degenerate or duplicate faces.`);
  if (repaired) warnings.push(`Corrected winding on ${repaired} faces.`);
  if (conflicts) warnings.push('Inconsistent surface orientation: check fold directions manually.');
  return {
    name: name.slice(0, 120),
    vertices,
    faces,
    edges,
    faceEdges,
    normals,
    warnings,
    dimensions,
    inverted: false,
    facePolygons: planarGroups(faces, edges, normals),
  };
}

export function demoMesh(): Mesh {
  const vertices: V3[] = [
    [0, 0.7, 0],
    [0, -0.65, 0],
  ];
  for (let i = 0; i < 6; i++) {
    const angle = (i * Math.PI) / 3;
    vertices.push([Math.cos(angle) * 0.6, 0.05, Math.sin(angle) * 0.6]);
  }
  const faces: Face[] = [];
  for (let i = 0; i < 6; i++) {
    const a = 2 + i,
      b = 2 + ((i + 1) % 6);
    faces.push([0, b, a], [1, a, b]);
  }
  return makeMesh(vertices, faces, 'Faceted gem');
}

function planarGroups(faces: Face[], edges: Edge[], normals: V3[]): string[] {
  const parent = faces.map((_, i) => i);
  const root = (i: number): number => (parent[i] === i ? i : (parent[i] = root(parent[i])));
  for (const e of edges)
    if (e.faces.length === 2 && dot(normals[e.faces[0]], normals[e.faces[1]]) > 1 - 1e-10)
      parent[root(e.faces[1])] = root(e.faces[0]);
  return faces.map((_, i) => `surface-${root(i)}`);
}
export const internalEdge = (mesh: Mesh, e: Edge) =>
  e.faces.length === 2 && mesh.facePolygons[e.faces[0]] === mesh.facePolygons[e.faces[1]];
export const polygonCount = (mesh: Mesh, faces = mesh.faces.map((_, i) => i)) =>
  new Set(faces.map((i) => mesh.facePolygons[i])).size;
export const polygonEdges = (mesh: Mesh, face: number) => [
  ...new Set(
    mesh.faces.flatMap((_, i) =>
      mesh.facePolygons[i] === mesh.facePolygons[face]
        ? mesh.faceEdges[i].filter((id) => !internalEdge(mesh, mesh.edges[id]))
        : [],
    ),
  ),
];

/** Collinear segments of one polygon-to-polygon hinge fold as one seam. */
export function seamEdges(mesh: Mesh, edge: Edge): number[] {
  const groups = edge.faces
    .map((f) => mesh.facePolygons[f])
    .sort()
    .join('|');
  const a = mesh.vertices[edge.a],
    direction = sub(mesh.vertices[edge.b], a),
    len = length(direction);
  return mesh.edges
    .filter(
      (e) =>
        !internalEdge(mesh, e) &&
        e.faces
          .map((f) => mesh.facePolygons[f])
          .sort()
          .join('|') === groups &&
        [e.a, e.b].every((v) => length(cross(direction, sub(mesh.vertices[v], a))) < len * 1e-8),
    )
    .map((e) => e.id);
}