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.
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);
}
