trimesh-boolean - npm Package Compare versions

Comparing version

0.5.11

0.5.12

+130

src/util/indexedComponents.js

		/**
		* @module util/indexedComponents
		*
		* Connected-component decomposition of ALREADY-INDEXED triangle groups — the indexed
		* twin of {@link module:boolean/booleanOp.splitToComponents}, without soup or toFixed
		* string keys.
		*
		* A boolean split's four groups (aInside/aOutside/bInside/bOutside) each break into one
		* or more connected pieces. The soup version flood-fills a mega-soup keyed by vertex
		* coordinate strings — heavy allocations that OOM at millions of triangles. Here the
		* triangles already reference a shared vertex pool by INTEGER index (as produced by
		* {@link module:util/indexGroups.indexGroups} or `bmsBooleanOp({ indexed: true })`), so
		* components are a plain union-find over those indices: O(N·α(N)), no soup, no strings.
		*
		* NOTE: connectivity here is shared-VERTEX (two triangles sharing any pool vertex are in
		* the same component), which is the natural relation on an indexed mesh. On a clean,
		* seam-welded boolean result this agrees with the soup path's shared-EDGE relation; on
		* meshes with genuine vertex-only touches it is (deliberately) coarser. For an exact
		* edge-based equivalent on soup, use `findConnectedComponentsPooled`.
		*
		* Pure — no globals, no THREE, no deps.
		*/

		/**
		* Union-find (disjoint set) over vertex indices, grouping triangles that share any
		* vertex into connected components.
		*
		* @param {Array<Array<number>>} tris - triangles as [i,j,k] index triples into a shared pool
		* @returns {Array<Array<Array<number>>>} array of components, each an array of its triangles
		*/
		export function connectedComponentsIndexed(tris) {
		var parent = new Map();

		function find(x) {
		if (!parent.has(x)) { parent.set(x, x); return x; }
		var root = x;
		while (parent.get(root) !== root) root = parent.get(root);
		// path compression
		while (parent.get(x) !== root) { var next = parent.get(x); parent.set(x, root); x = next; }
		return root;
		}
		function union(a, b) {
		var ra = find(a), rb = find(b);
		if (ra !== rb) parent.set(ra, rb);
		}

		for (var t = 0; t < tris.length; t++) {
		var tr = tris[t];
		find(tr[0]); // ensure present
		union(tr[0], tr[1]);
		union(tr[1], tr[2]);
		}

		// Bucket triangles by their component root, preserving first-seen order.
		var byRoot = new Map();
		var order = [];
		for (var t2 = 0; t2 < tris.length; t2++) {
		var root = find(tris[t2][0]);
		var arr = byRoot.get(root);
		if (!arr) { arr = []; byRoot.set(root, arr); order.push(root); }
		arr.push(tris[t2]);
		}
		var out = [];
		for (var i = 0; i < order.length; i++) out.push(byRoot.get(order[i]));
		return out;
		}

		var GROUP_META = [
		{ key: "aInside", mesh: "A", side: "inside" },
		{ key: "aOutside", mesh: "A", side: "outside" },
		{ key: "bInside", mesh: "B", side: "inside" },
		{ key: "bOutside", mesh: "B", side: "outside" }
		];

		/**
		* Decompose the four indexed groups into connected components, mirroring the shape of
		* `splitToComponents` so the same consumer code works unchanged — but each component
		* carries INDEXED triangles ([i,j,k] into the shared `points`), not soup.
		*
		* @param {{ points: Array, groups: { aInside, aOutside, bInside, bOutside } }} indexed
		* as returned by `indexGroups` or `bmsBooleanOp(..., { indexed: true }).indexed`
		* @param {number} [smallThreshold=0] - components with fewer triangles than this are
		* merged into the largest component of their group (matches mergeSmallComponents)
		* @returns {Array<{ mesh, side, group, index, points, triangles, triCount }>}
		*/
		export function decomposeIndexedGroups(indexed, smallThreshold) {
		var points = indexed.points;
		var out = [];
		for (var g = 0; g < GROUP_META.length; g++) {
		var meta = GROUP_META[g];
		var tris = indexed.groups[meta.key] \|\| [];
		if (tris.length === 0) continue;
		var comps = connectedComponentsIndexed(tris);
		if (smallThreshold && smallThreshold > 0 && comps.length > 1) {
		comps = mergeSmallIndexedComponents(comps, smallThreshold);
		}
		for (var c = 0; c < comps.length; c++) {
		out.push({
		mesh: meta.mesh, side: meta.side, group: meta.key, index: c,
		points: points, triangles: comps[c], triCount: comps[c].length
		});
		}
		}
		return out;
		}

		/**
		* Fold components below `threshold` triangles into the largest component (so a boolean
		* seam doesn't leave dozens of stray slivers as their own regions). Mirrors
		* `mergeSmallComponents` for the indexed representation.
		*
		* @param {Array<Array<Array<number>>>} comps
		* @param {number} threshold
		* @returns {Array<Array<Array<number>>>}
		*/
		export function mergeSmallIndexedComponents(comps, threshold) {
		if (comps.length <= 1) return comps;
		var largest = 0;
		for (var i = 1; i < comps.length; i++) if (comps[i].length > comps[largest].length) largest = i;
		var keep = [], strays = [];
		for (var j = 0; j < comps.length; j++) {
		if (j === largest \|\| comps[j].length >= threshold) keep.push(comps[j]);
		else strays.push(comps[j]);
		}
		if (strays.length) {
		var big = comps[largest];
		for (var s = 0; s < strays.length; s++) for (var k = 0; k < strays[s].length; k++) big.push(strays[s][k]);
		}
		return keep;
		}

+1

-1

package.json

		{
		"name": "trimesh-boolean",
		"version": "0.5.11",
		"version": "0.5.12",
		"description": "Triangle mesh boolean operations — supports open surfaces, terrain intersection, and mesh repair",
		@@ -5,0 +5,0 @@ "type": "module",

+28

-2

README.md

		@@ -164,3 +164,3 @@ # trimesh-boolean

		### `splitToComponents(groups)`
		### `splitToComponents(groups, options?)`

		@@ -170,4 +170,26 @@ Decompose each of the 4 split groups into connected components (disconnected mesh regions). Useful for multi-crossing surfaces where a single group contains multiple spatially separated zones.
		- groups: `{ aInside, aOutside, bInside, bOutside }` from `splitMeshPair`
		- options.pooled: `boolean` — route each group through the integer-id `findConnectedComponentsPooled` fast path (identical result, far less string hashing at scale). Default off.
		- options.tolerance: `number` — vertex-weld quantization for the pooled path (default `1e-6`)
		- Returns: `[{ mesh: "A"\|"B", side: "inside"\|"outside", index: number, soup: Triangle[], triCount: number }, ...]` — sorted largest-first within each group

		### Scaling at millions of triangles

		`findConnectedComponents` and the default `splitToComponents` key their edge map on `toFixed(6)` strings; at millions of triangles that string hashing dominates time and heap. Three opt-in, back-compatible integer-id paths avoid it (the default string paths are unchanged):

		- `findConnectedComponentsPooled(soup, options?)` — same shared-edge adjacency and largest-first ordering as `findConnectedComponents`, but vertices are hashed to integer ids so the edge map uses integer keys. Identical result on clean input. `options.tolerance` defaults to `1e-6`.
		- `splitToComponents(groups, { pooled: true })` — the same, applied to all four groups.
		- `connectedComponentsIndexed(tris)` / `decomposeIndexedGroups(indexed, smallThreshold?)` — decompose an already-indexed result (`indexGroups(...)` or `bmsBooleanOp(..., { indexed: true }).indexed`) with no soup and no re-hashing. Connectivity here is shared-vertex (union-find over pool ids), which is coarser than the soup path's shared-edge relation — on a clean seam-welded result they agree; on meshes with genuine vertex-only touches the indexed decompose yields fewer, larger components. `decomposeIndexedGroups` returns `[{ mesh, side, group, index, points, triangles, triCount }, ...]` where `triangles` are `[i,j,k]` triples into the shared `points`.

		```javascript
		import { bmsBooleanOp, splitToComponents, decomposeIndexedGroups } from 'trimesh-boolean';

		// Soup, pooled edge-based components (drop-in accelerator):
		var bms = bmsBooleanOp(meshA, meshB, null, { indexed: true });
		var comps = splitToComponents(bms.groups, { pooled: true });

		// Or decompose the indexed twin directly — no soup:
		var indexedComps = decomposeIndexedGroups(bms.indexed);
		// indexedComps[0] = { mesh, side, group, index, points, triangles: [[i,j,k], ...], triCount }
		```

		### `mergeSmallComponents(comps, threshold?)`
		@@ -395,4 +417,8 @@
		\| `findConnectedComponents(soup)` \| Split a soup into connected components via shared edges \|
		\| `splitToComponents(groups)` \| Decompose 4 split groups into per-component list \|
		\| `findConnectedComponentsPooled(soup, options?)` \| Integer-id twin of the above — same result, no `toFixed` string keys (see [Scaling](#scaling-at-millions-of-triangles)) \|
		\| `splitToComponents(groups, options?)` \| Decompose 4 split groups into per-component list (`{ pooled: true }` for the fast path) \|
		\| `connectedComponentsIndexed(tris)` \| Components of an already-indexed mesh via shared-vertex union-find \|
		\| `decomposeIndexedGroups(indexed, smallThreshold?)` \| Decompose indexed groups (shared pool + `[i,j,k]`) — soup-free \|
		\| `mergeSmallComponents(comps, threshold?)` \| Merge small fragments into nearest same-group neighbor \|
		\| `mergeSmallIndexedComponents(comps, threshold)` \| Fold small indexed components into the largest \|
		\| `mergeComponents(picks)` \| Merge user-selected component soups into welded result \|
		@@ -399,0 +425,0 @@ \| `selectSplits(groups, selections)` \| Select specific groups with optional flip \|

+9

-3

src/boolean/booleanOp.js

		@@ -29,3 +29,3 @@ /**
		import { fillOpenEdgeLoops } from "../repair/fillOpenLoops.js";
		import { findConnectedComponents } from "../util/connectedComponents.js";
		import { findConnectedComponents, findConnectedComponentsPooled } from "../util/connectedComponents.js";
		import { forceCloseIndexedMesh } from "../repair/forceClose.js";
		@@ -419,7 +419,11 @@
		* @param {{ aInside: Array, aOutside: Array, bInside: Array, bOutside: Array }} groups
		* @param {{ pooled?: boolean, tolerance?: number }} [options] `pooled: true` routes each
		* group through the integer-id `findConnectedComponentsPooled` fast path (identical
		* result, far less string hashing at scale). Default (omitted) is the classic path.
		* @returns {Array<{ mesh: string, side: string, index: number, soup: Array, triCount: number }>}
		*/
		export function splitToComponents(groups) {
		export function splitToComponents(groups, options) {
		if (!groups) return [];
		var result = [];
		var pooled = !!(options && options.pooled);

		@@ -438,3 +442,5 @@ var groupDefs = [

		var components = findConnectedComponents(soup);
		var components = pooled
		? findConnectedComponentsPooled(soup, options)
		: findConnectedComponents(soup);
		for (var c = 0; c < components.length; c++) {
		@@ -441,0 +447,0 @@ result.push({

+50

-1

src/index.d.ts

		@@ -184,3 +184,4 @@ /**
		export function splitToComponents(
		groups: SplitResult["groups"]
		groups: SplitResult["groups"],
		options?: { pooled?: boolean; tolerance?: number }
		): SplitComponent[];
		@@ -327,1 +328,49 @@
		export function findConnectedComponents(soup: TriangleSoup): TriangleSoup[];

		/**
		* Integer-id ("pooled") twin of findConnectedComponents — an opt-in fast path for large
		* soups. Same shared-edge adjacency and largest-first ordering, but vertices are hashed to
		* integer ids so the edge map avoids toFixed string keys. Identical result on clean input.
		*/
		export function findConnectedComponentsPooled(
		soup: TriangleSoup,
		options?: { tolerance?: number }
		): TriangleSoup[];

		// ── Indexed connected components (integer-id, soup-free) ──

		/** A triangle as an [i, j, k] triple of indices into a shared points pool. */
		export type IndexedTri = [number, number, number];

		/**
		* Connected components of an already-indexed mesh via shared-vertex union-find.
		* O(N·α(N)), no soup, no string keys. Connectivity is shared-vertex (see module note);
		* for an exact edge-based equivalent on soup use findConnectedComponentsPooled.
		*/
		export function connectedComponentsIndexed(tris: IndexedTri[]): IndexedTri[][];

		export interface IndexedComponent {
		/** "A" \| "B" — which input mesh it came from */
		mesh: string;
		/** "inside" \| "outside" — relative to the other mesh */
		side: string;
		/** Source group key: "aInside" \| "aOutside" \| "bInside" \| "bOutside" */
		group: string;
		/** Component index within its group (0 = largest) */
		index: number;
		/** Shared vertex pool (same reference across all components) */
		points: Vertex[];
		/** This component's triangles as [i,j,k] triples into `points` */
		triangles: IndexedTri[];
		/** Number of triangles */
		triCount: number;
		}

		/**
		* Decompose the four indexed groups (from indexGroups or bmsBooleanOp({ indexed: true }))
		* into connected components, mirroring splitToComponents but keeping the indexed form.
		*/
		export function decomposeIndexedGroups(indexed: IndexedGroups, smallThreshold?: number): IndexedComponent[];

		/** Fold indexed components below `threshold` triangles into the largest component. */
		export function mergeSmallIndexedComponents(comps: IndexedTri[][], threshold: number): IndexedTri[][];

+4

-1

src/index.js

		@@ -81,2 +81,5 @@ /**
		export { dist3, distSq3, triangleArea3D, computeBounds, cross, lerpVert, vKey, edgeKey, countOpenEdges } from "./util/math.js";
		export { findConnectedComponents } from "./util/connectedComponents.js";
		export { findConnectedComponents, findConnectedComponentsPooled } from "./util/connectedComponents.js";

		// ── Indexed connected components (integer-id, soup-free — opt-in scaling path) ──
		export { connectedComponentsIndexed, decomposeIndexedGroups, mergeSmallIndexedComponents } from "./util/indexedComponents.js";

+97

-0

src/util/connectedComponents.js

		@@ -81,1 +81,98 @@ /**
		}

		/**
		* Integer-id ("pooled") twin of {@link findConnectedComponents} — an opt-in fast
		* path for large soups. Identical shared-EDGE adjacency and largest-first ordering
		* as the default, but each distinct vertex is assigned an integer id via a quantized
		* hash, so the edge map is keyed by pure integers (`lo * P + hi`) instead of
		* `toFixed(6)` string concatenations. At millions of triangles this removes the
		* string hashing that dominates the default's time + heap.
		*
		* Results are identical to `findConnectedComponents` on clean input (the two share
		* the same 6-dp quantization by default), so this is a drop-in accelerator — the
		* default function is left untouched.
		*
		* @param {Array<{ v0: {x,y,z}, v1: {x,y,z}, v2: {x,y,z} }>} soup
		* @param {{ tolerance?: number }} [options] `tolerance` = vertex-weld quantization in
		* world units (default `1e-6`, mirroring the default's 6-decimal rounding).
		* @returns {Array<Array<{ v0: {x,y,z}, v1: {x,y,z}, v2: {x,y,z} }>>} components, largest-first
		*/
		export function findConnectedComponentsPooled(soup, options) {
		if (!soup \|\| soup.length === 0) return [];
		if (soup.length === 1) return [soup.slice()];

		var tolerance = (options && options.tolerance != null) ? options.tolerance : 1e-6;
		var inv = 1 / tolerance;

		// Step 1) Assign each distinct vertex a small integer id via a quantized hash.
		// One (short) key per vertex — 3 per triangle — replaces the default's long
		// toFixed keys; the edge map below is then pure-integer keyed.
		var vertId = new Map();
		function id(v) {
		var key = Math.round(v.x * inv) + "," + Math.round(v.y * inv) + "," + Math.round(v.z * inv);
		var i = vertId.get(key);
		if (i === undefined) { i = vertId.size; vertId.set(key, i); }
		return i;
		}
		var triIds = new Array(soup.length);
		for (var t = 0; t < soup.length; t++) {
		var tri = soup[t];
		triIds[t] = [id(tri.v0), id(tri.v1), id(tri.v2)];
		}
		// Edge-key stride. Both endpoint ids are < P, so lo*P+hi is a unique integer key
		// while P*P stays within 2^53 (safe up to ~94M distinct vertices — far past scale).
		var P = vertId.size;

		// Step 2) Build edge -> triangle index map (integer keys, no strings).
		var edgeToTris = new Map();
		function addEdge(a, b, ti) {
		var lo = a < b ? a : b;
		var hi = a < b ? b : a;
		var key = lo * P + hi;
		var arr = edgeToTris.get(key);
		if (!arr) { arr = []; edgeToTris.set(key, arr); }
		arr.push(ti);
		}
		for (var i2 = 0; i2 < soup.length; i2++) {
		var ids = triIds[i2];
		addEdge(ids[0], ids[1], i2);
		addEdge(ids[1], ids[2], i2);
		addEdge(ids[2], ids[0], i2);
		}

		// Step 3) Per-triangle neighbor list.
		var neighbors = new Array(soup.length);
		for (var ni = 0; ni < soup.length; ni++) neighbors[ni] = [];
		edgeToTris.forEach(function(tris) {
		for (var a = 0; a < tris.length; a++) {
		for (var b = a + 1; b < tris.length; b++) {
		neighbors[tris[a]].push(tris[b]);
		neighbors[tris[b]].push(tris[a]);
		}
		}
		});

		// Step 4) BFS to find connected components.
		var visited = new Uint8Array(soup.length);
		var components = [];
		for (var seed = 0; seed < soup.length; seed++) {
		if (visited[seed]) continue;
		var component = [];
		var queue = [seed];
		visited[seed] = 1;
		var head = 0;
		while (head < queue.length) {
		var cur = queue[head++];
		component.push(soup[cur]);
		var nbrs = neighbors[cur];
		for (var n = 0; n < nbrs.length; n++) {
		if (!visited[nbrs[n]]) { visited[nbrs[n]] = 1; queue.push(nbrs[n]); }
		}
		}
		components.push(component);
		}

		// Step 5) Sort largest-first.
		components.sort(function(a, b) { return b.length - a.length; });
		return components;
		}

build/trimesh-boolean-three.esm.js.map