trimesh-boolean

Triangle mesh boolean operations for JavaScript — supports open surfaces.

Unlike every other mesh boolean package in the npm ecosystem, trimesh-boolean works on open (non-watertight) meshes like terrain surfaces, DTMs, and partial shells. It also works on closed solids.

Why trimesh-boolean?

| Package | Open surfaces? | Approach | |---------|----------------|----------| | three-bvh-csg | No | BVH-accelerated BSP | | three-csg-ts | No | BSP tree (TS) | | manifold-3d | No | WASM C++ | | trimesh-boolean | Yes | Moller intersection + fan triangulation + shared Steiner points + hybrid boundary/barrier-normal classification + heffalump per-triangle classifier |

Every existing package requires closed, manifold input. If you're working with terrain surfaces, geological models, or any open mesh — they won't work. trimesh-boolean will.

Install

npm install trimesh-boolean

Or use the CDN for browser scripts:

<script src="https://unpkg.com/trimesh-boolean/build/trimesh-boolean.min.js"></script>
<!-- Exposes window.TrimeshBoolean -->

Links: npm · GitHub · Live Demo

Live demo (GitHub Pages)

Two pages:

• Workflows — every pipeline as a runnable walkthrough. Each one shows the code it actually runs (the listing is generated from the function itself, so it cannot drift), the geometry before and after, and the measured effect. Includes the T-junction repair comparison: the legacy resolver leaves 66.7% of triangles correctly wound, the hole-free one leaves 100%.
• Boolean playground — load surfaces, run operations, inspect and re-classify the splits by hand.

The live demo is built and deployed automatically on every push to main or master by .github/workflows/pages.yml (npm run build:docs in CI). You do not need to commit the docs/ folder for the site to update.

One-time repo setting: GitHub → Settings → Pages → Build and deployment → Source: GitHub Actions (not “Deploy from a branch”). After that, each push runs the workflow and refreshes the demo.

To preview the same build locally:

npm run build:docs

Edit demos only under examples/ (Vite root). Local dev: npm run dev.

Quick Start

Start here. booleanAuto runs the BMS pipeline and finishes the result, so you get valid geometry from one call:

import { booleanAuto } from 'trimesh-boolean';

var result = booleanAuto(terrainSoup, cutterSoup, 'subtract');
// result.soup   -> the finished triangles
// result.ok     -> true when every output invariant holds
// result.report -> what was repaired, and what was refused (and why)

Output quality is an invariant, not an option — there is no flag to disable correct winding. What you can choose is how hard to work: quality: "strict" (default) finishes the result, quality: "raw" hands back the merged boolean untouched.

Two engines live in this package and they do different jobs:

| | use it for | notes | |---|---|---| | booleanAuto / bmsBooleanOp | open, non-watertight, non-manifold surfaces — terrain, DTMs, mining shells | the engine this library exists for | | boolean | simple closed solids | classic flood-fill + half-space; kept for compatibility |

They do not call each other. If your inputs are survey surfaces, use booleanAuto.

Lower-level API

import { boolean, splitMeshPair, mergeSplitGroups,
         splitToComponents, mergeSmallComponents, mergeComponents,
         selectSplits, repairMesh, intersectMeshPair,
         heffalumpClassify, shouldUseHeffalump,
         reclassifyTriangles, reclassifyAtPoint, reclassifyRegion } from 'trimesh-boolean';

// Triangle soup: simple {v0, v1, v2} objects
var meshA = [
  { v0: {x:0,y:0,z:0}, v1: {x:2,y:0,z:0}, v2: {x:1,y:2,z:0} },
  // ... more triangles
];
var meshB = [/* ... */];

// One-shot boolean operation
var result = boolean(meshA, meshB, 'subtract');
// result = { soup: Triangle[], points: Vertex[], triangles: WeldedTri[] }

// Split-and-pick workflow (inspect groups before merging)
var split = splitMeshPair(meshA, meshB);
// split.groups = { aInside, aOutside, bInside, bOutside }
// split.segments = TaggedSegment[]
var merged = mergeSplitGroups(split.groups, 'union');

// Custom surface workflow — user picks individual components
var comps = splitToComponents(split.groups);
// comps = [{ mesh:"A", side:"inside", index:0, soup:[...], triCount:599 }, ...]
comps = mergeSmallComponents(comps, 50);  // collapse tiny fragments
var picked = mergeComponents([
  { soup: comps[0].soup },              // keep A-inside #0
  { soup: comps[2].soup, flip: true }   // keep B-outside #0, flip normals
]);

// ── BMS Pipeline (v0.5.0) — hybrid classification + per-component walks ──
import { bmsBooleanOp } from 'trimesh-boolean';

var bms = bmsBooleanOp(meshA, meshB, null, { preRepair: true });
// bms.groups = { aInside, aOutside, bInside, bOutside }
// bms.segments = pool-vertex intersection segments
// bms.polylines = chained intersection polylines
// bms.meshEdgePolys = { A: {...}, B: {...} } — per-mesh boundary polygons
// bms.componentWalks = per-component boundary walk segments
// bms.pool = shared vertex pool

// BMS + splitToComponents for per-region analysis
var comps = splitToComponents(bms.groups);
// 9 components for double-crossing terrain + convoluted block

// ── Heffalump Classifier (v0.5.5) — per-triangle classification for defective meshes ──
import { heffalumpClassify, shouldUseHeffalump } from 'trimesh-boolean';

// Auto-detect if meshes have non-manifold edges
if (shouldUseHeffalump(meshA, meshB)) {
  // heffalumpClassify classifies each triangle individually
  // Works on meshes with fragmented boundaries, cracks, and holes
  var hResult = heffalumpClassify(megaSoup, segments, meshA, meshB);
  // hResult.aInside, hResult.aOutside, hResult.bInside, hResult.bOutside
  // hResult.componentWalks — boundary walk segments for visualization
}

// Manual reclassification — fix misclassified triangles interactively
import { reclassifyAtPoint } from 'trimesh-boolean';
var fix = reclassifyAtPoint(groups, clickX, clickY, clickZ, 0.01);
// fix = { moved: true, mesh: "A", from: "inside", to: "outside" }

// Just intersection segments (no boolean)
var segments = intersectMeshPair(meshA, meshB);
// segments = [{ p0: {x,y,z}, p1: {x,y,z} }, ...]

// Mesh repair
var repaired = await repairMesh(meshA, {
  closeMode: 'stitch',
  snapTolerance: 0.01
});

Three.js Adapter

import { booleanFromMeshes, meshToSoup, soupToMesh } from 'trimesh-boolean/three';

// Boolean on Three.js meshes directly — runs BMS + finishing (v0.7.1+)
var resultMesh = booleanFromMeshes(threeGroupA, threeGroupB, 'subtract');
scene.add(resultMesh);

// Or convert manually
var soup = meshToSoup(threeMesh);
var mesh = soupToMesh(soup, { color: 0xff0000 });

Since v0.7.1 booleanFromMeshes runs the BMS pipeline via booleanAuto. Before that it ran the classic engine, so Three.js consumers silently missed the open-surface path. Pass { engine: 'classic' } for the old behaviour.

UTM precision. soupToMesh builds geometry in a local frame, putting the centroid on mesh.position. Three stores positions as Float32, whose spacing at a UTM northing of 7.4e6 is 0.5 m — writing absolute survey coordinates straight in silently collapses nearby vertices. Measured: 6771845.678 stores as 6771845.5, an error of 0.178 m. In the local frame the same value carries about 1e-6 m. Pass { recenter: false } for the old behaviour; only safe near the origin.

Note this is a storage limit, independent of the exact predicates used internally: orient3d gives exact signs, not exact coordinates.

API Reference

boolean(soupA, soupB, operation)

Perform a boolean operation on two triangle soups.

• soupA / soupB: Triangle[] — arrays of { v0, v1, v2 } where each vertex is { x, y, z }
• operation: "subtract" | "union" | "intersect"
• Returns: { soup, points, triangles } or null

splitMeshPair(soupA, soupB)

Split two meshes into 4 inside/outside groups without combining them. This is the "split-and-pick" workflow: compute groups, then the caller decides which to keep.

• soupA / soupB: Triangle[]
• Returns: { groups: { aInside, aOutside, bInside, bOutside }, segments } or null

mergeSplitGroups(groups, operation)

Merge split groups into a single result based on the operation type.

• groups: { aInside, aOutside, bInside, bOutside } from splitMeshPair
• operation: "subtract" | "union" | "intersect"
• Returns: { soup, points, triangles } or null

splitToComponents(groups, options?)

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.

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?)

Merge small fragment components into their nearest same-group (mesh + side) larger component by centroid proximity. Cleans up tiny classification artifacts.

• comps: Component array from splitToComponents
• threshold: Triangle count below which a component is merged (default: 50)
• Returns: Reduced component array with fragments absorbed

mergeComponents(picks)

Merge an arbitrary selection of component soups into a single welded result. Works with the output of splitToComponents — pass in the components the user has selected.

• picks: [{ soup: Triangle[], flip?: boolean }, ...]
• Returns: { soup, points, triangles } or null

selectSplits(groups, selections)

Select specific split groups by name, with optional normal flipping.

• groups: { aInside, aOutside, bInside, bOutside } from splitMeshPair
• selections: { aInside?: boolean|"flip", aOutside?: boolean|"flip", bInside?: boolean|"flip", bOutside?: boolean|"flip" }
• Returns: { soup, points, triangles } or null

Output Verification & Finishing (v0.7.0+)

A boolean result is not automatically valid geometry, and a repair is not automatically an improvement. These three APIs measure instead of assuming.

booleanAuto(soupA, soupB, operation, options?)

Boolean + merge + gated finishing, in one call. The recommended entry point.

var r = booleanAuto(terrain, cutter, 'subtract');
if (!r.ok) console.warn(r.report.after.checks.filter(c => !c.ok));

| option | default | meaning | |---|---|---| | quality | "strict" | "strict" finishes the result; "raw" returns the merged boolean | | classifier | "auto" | passed to bmsBooleanOp | | tolerance | derived | shared by the boolean and the finisher so they agree | | expectClosed | false | require a closed solid in the report |

verifyOutput(soup, options?)

Read-only invariant check. Mutates nothing, repairs nothing, reports.

var v = verifyOutput(soup);
// v.ok, v.checks[], v.stats { triangles, vertices, openEdges,
//                             nonManifoldEdges, area, components, volume }

Checks: noDegenerateTriangles, noDuplicateTriangles, consistentWinding (a shared edge must be traversed in opposite directions by its two triangles), manifoldEdges, noTJunctions, and closed under { expectClosed: true }. Open surfaces pass by default — the normal case for terrain and DTM work.

Identity is a neighbourhood weld, not toFixed string keys. volume is computed after translating to the centroid: at UTM scale the raw sum is catastrophic cancellation (measured: 89,000,000 m³ reported for a 55,000 m³ solid).

Use it to check output, not to guess from input. The internal censusMessy gate inspects inputs and can report clean on meshes that demonstrably contain T-junctions.

assessRepair(before, after, options?)

Run a repair on a copy, diff the two reports, and decide.

var candidate = resolveTJunctionsHoleFree(soup, tol, 4);
var a = assessRepair(soup, candidate);
if (a.recommend === 'keep') soup = candidate;
else console.log(describeAssessment(a));   // says exactly what it would damage

Returns recommend: "keep" | "discard", harmful, and itemised benefits / damage. Volume is only judged when the baseline is sound (0 open, 0 non-manifold) — against a broken baseline the figure means nothing.

finishMesh(soup, options?)

Applies dedupCoincident, resolveTJunctionsHoleFree and orientWinding, each gated by assessRepair, keeping a stage only when it strictly reduces violations. It never returns geometry worse than its input.

var f = finishMesh(soup);
// f.soup, f.ok, f.applied[], f.skipped[] (stage + reason), f.before, f.after

The gate is load-bearing, not defensive. Measured on real survey data:

| pair | before | finishMesh | ungated | |---|---|---|---| | terrain × cylinder | consistentWinding:40 | clean | clean | | terrain × cup | consistentWinding:46 | clean | clean | | terrain × convoluted | 108 violations | 2 | manifoldEdges:2 | | shell × presplit-a | 4 | 4, untouched | 6 — worse |

On that last row hole-free T-junction resolution trades 4 T-junctions for 2 degenerates, 3 non-manifold edges and 1 remaining T-junction. Ungated, that ships as "repaired".

No deleting stage is included. Deleting geometry stitched into a mesh tears it open — measured elsewhere as 1827 slivers removed producing 3567 open edges and 90 components — while welding dissolves the same junk for free.

⚠️ repairMesh still defaults to sliverRatio: 0.01, which is that ruinous setting. Assess before trusting it as a blind default.

BMS Pipeline (v0.4.0+)

The BMS (Brent's Mega Soup) pipeline is a boolean pipeline designed for open surfaces. It solves the core problems of the original pipeline: shared Steiner points, identity-based segment chaining, fan triangulation with guaranteed constraint edges, hybrid classification (v0.5.0), and per-triangle heffalump classification for defective meshes (v0.5.5).

bmsBooleanOp(soupA, soupB, operation?, options?)

Run the full BMS pipeline. Both meshes are split into a unified mega soup where intersection points are shared by object reference (not string matching).

• operation: "subtract" | "union" | "intersect" — omit to get groups only
• options.classifier (v0.5.8): "auto" (default) | "hybrid" | "heffalump". Auto censuses the inputs (non-manifold → heffalump + pre-repair), runs the hybrid classifier, verifies partition / chain-closure / barrier post-conditions, and on any failure re-runs only the classification stage with the heffalump on the existing mega soup. No caller needs to know what a heffalump is anymore.
• options.preRepair: boolean — resolve T-junctions + weld before splitting. Default: auto-enabled when the census finds non-manifold edges.
• options.tolerance: number — vertex pool merge tolerance
• options.indexed: boolean — also attach result.indexed, a compact indexed twin of the groups (one shared points pool + per-group [i,j,k] index triples). Back-compatible: the soup groups are unchanged. See Indexed Group Output below.
• Returns: { groups, segments, polylines, meshEdgePolys, componentWalks, megaSoup, pool, classifier, verification } — classifier reports the path per mesh (e.g. { A: "hybrid", B: "heffalump (partition)" }); verification carries the post-condition check results. With { indexed: true }, also carries indexed (see below).

verifyBmsClassification(megaSoup, triSides, segments, polylines, trisA, trisB) (v0.5.8)

The auto-classifier's post-condition checks, exported standalone: partition (both meshes must have non-empty inside AND outside groups when intersection segments exist), chain closure (every intersection polyline closes or ends on a mesh boundary), and barrier constraint (same-mesh triangles sharing a barrier edge classify to opposite sides). Returns { ok, failures, counts }.

Indexed Group Output

The pipeline's native output is triangle soup — every triangle carries its own three {x,y,z} vertex objects. That form is simple to consume, but it stores each shared vertex many times over (~5–10× heavier than an indexed mesh). For a multi-million-triangle boolean result you'll want the indexed twin: one shared vertex pool plus per-group [i,j,k] index triples. The pool is shared across all four groups, so the seam between aInside/aOutside (and bInside/bOutside) welds automatically — no re-dedupe needed.

This is purely additive: the soup groups are never modified. Opt in on bmsBooleanOp with { indexed: true }, or call indexGroups directly on any soup groups.

indexGroups(groups, tolerance?)

Convert soup split groups into a compact indexed representation.

• groups: { aInside?, aOutside?, bInside?, bOutside? } — soup groups ({ v0, v1, v2 } triangles), as returned by splitMeshPair, bmsBooleanOp, etc.
• tolerance: number — vertex-weld quantization in world units (default: 1e-4)
• Returns: { points, groups } where points is a shared Vertex[] pool and groups is { aInside, aOutside, bInside, bOutside }, each an array of [i, j, k] index triples into points

import { bmsBooleanOp, indexGroups, splitMeshPair } from 'trimesh-boolean';

// Opt in on the pipeline result...
var bms = bmsBooleanOp(meshA, meshB, 'subtract', { indexed: true });
// bms.indexed = { points: Vertex[], groups: { aInside: [i,j,k][], ... } }

// ...or index any soup groups after the fact:
var split = splitMeshPair(meshA, meshB);
var indexed = indexGroups(split.groups, 1e-4);

indexGroupsToTypedArrays(indexed)

Flatten indexed groups into typed arrays for transfer or GPU upload. Positions are the same shared pool across all groups (indices are global), so a BufferGeometry can point every group's index buffer at one position buffer.

• indexed: the return value of indexGroups
• Returns: { positions, index } where positions is a Float64Array of [x,y,z,...] and index is { aInside, aOutside, bInside, bOutside }, each a Uint32Array of flattened triangle indices

import { indexGroupsToTypedArrays } from 'trimesh-boolean';

var flat = indexGroupsToTypedArrays(bms.indexed);
// flat.positions -> Float64Array, flat.index.aInside -> Uint32Array, ...

bmsIntersect(trisA, trisB, options?)

Compute intersections with a shared vertex pool. Every segment endpoint goes through the pool — both meshes get the exact same object reference at each intersection location.

bmsSplit(trisA, trisB, intersectResult)

Re-triangulate crossed triangles using fan triangulation with pool vertex references. Produces a tagged mega soup: [{v0, v1, v2, mesh: "A"|"B", origIdx}].

Since v0.5.8 a fan-sliver guard detects extreme triangle/chain size mismatches (a giant face crossed by a dense intersection chain) and switches that face from corner fans to a chain-constrained CDT seeded with graded interior Steiner points — bounded aspect ratio, no needle "spurs", and no T-junctions (the added points are strictly interior).

bmsChain(segments)

Chain intersection segments using pool vertex identity (integer ID lookup, not distance threshold). Two segments sharing a pool vertex connect by definition.

chainedOpenEdge(tris, megaSoup?, segments?)

Walk the complete open boundary of a mesh as a closed polygon. Uses a half-edge structure to correctly navigate bowtie (non-manifold) vertices. Returns the largest loop as an ordered array of {key, vertex}, with the first vertex repeated at the end.

bmsClosePolylines(polylines, trisA, trisB, megaSoup?, segments?)

Build mesh edge polygons connecting intersection polylines via graph-walks and boundary edge-walks. Graph-walks avoid crossing intersection lines (barrier-aware BFS).

bmsClassify(megaSoup, closedPolylines, segments, trisA, trisB)

Hybrid classification (v0.5.0). Barrier flood-fill produces connected components per mesh. Classification method depends on mesh type:

• Open meshes: boundary topology — component touching mesh open boundary = outside, enclosed by barriers = inside.
• Closed meshes: barrier-normal — dot product of component direction vs other mesh's face normal at barrier edges.

Also extracts per-component boundary walk segments (componentWalks) for visualization.

Self-Intersection Fold Resolver (v0.6.0)

Resolves a self-intersecting, coincident-folded, or non-orientable closed mesh into a clean solid — the case orientSolid alone cannot fix, because a folded component has no consistent winding to orient toward. It re-cuts the coincident and self-crossing triangles into a conforming mesh arrangement, then classifies the resulting cells by generalized winding number (Zhou et al. 2016 + Jacobson et al. 2013).

This is a purely additive feature: every function below is a new export, and no existing API, default, or output changed. The A-vs-B bmsBooleanOp / boolean paths are byte-for-byte unchanged (the new edge-Steiner split path only activates when a self-arrangement populates intersectResult.edgePointsA/B, and the new orientSolid branch only runs under options.coherenceOnly).

bmsSelfResolveIndexed(indexed, options?)

Main entry. Takes and returns indexed geometry — the efficient form for large meshes.

import { bmsSelfResolveIndexed } from 'trimesh-boolean';

var result = bmsSelfResolveIndexed(
  { positions: Float64Array, index: Uint32Array },   // xyz-per-vertex + triangle indices
  { weldTolerance: /* default avgEdge · 0.012 */ }   // all options opt-in
);
// result = { positions: Float64Array, index: Uint32Array, diagnostics }

diagnostics reports what happened, honestly:

• classifier — "cell-complex" when the mesh resolved watertight, "patch" when it fell back (see below).
• arrangementOpenEdges, preOrientSeamViolations — residual non-orientable seams, if any.
• cellComplex.leakedFaceFraction, seamOpenBefore / seamOpenAfter — per-mesh, where inside and outside could not be separated.

Genuinely-degenerate input — coincident folds whose seam glues inside to outside as a single topological cell — cannot be made watertight by any winding method. On those, the resolver falls back to a volume-accurate result (typical volume error < 0.01%) rather than tearing or collapsing the mesh, and reports classifier: "patch". It never ships a proximity-stitch collapse.

Coincident-sheet vs. pinch (v0.6.1). Some degenerate leaks come from near-coincident coplanar sheets — vertices within tolerance but not exactly equal — which the radial fan then glues ambiguously. exactSeamSnap: true (default off) collapses those pairs to exact coincidence with robust predicates, so the facet-merge cancels them and the cell complex can separate inside from outside; only coincident-pair vertices move (≤ tolerance, and a zero-thickness pair encloses no volume, so volume is preserved). Enable it and read diagnostics.exactSeamSnap.coincidentPairs and diagnostics.cellComplexConditioned.leakedFaceFraction: if the leak drops below leakTolerance the mesh closes via the cell complex; if it holds, the leak is a genuine topological pinch (the surface passes through itself — inside and outside are one cell), which no winding method can separate, so it stays on the volume-safe patch. Default-off keeps the 0.6.0 path byte-for-byte unchanged.

bmsSelfResolve(soup, options?)

Soup-form entry ({v0,v1,v2}[] in, { soup, diagnostics } out) for when you are not already indexed.

Pipeline internals (advanced)

Exposed for composition and testing; you normally only need the two entries above.

• coplanarOverlap, emitCoplanarSegments — coincident (coplanar) overlap detection and segment emission. This is the fold case the classic Möller test near-parallel-rejects, so ordinary intersection never sees it.
• bmsSelfIntersect, bmsSelfArrange — self-intersection detection and the conforming self-arrangement (shared-pool edge-Steiner splits → no T-junctions).
• conditionArrangement — opt-in seam snap-round + hole-fill; runs only when the cell complex detects a leak, and is a no-op on watertight input.
• snapCoincidentSheets (v0.6.1) — the exactSeamSnap primitive: union-finds near-coincident coplanar face-pair vertices onto a shared representative (exact coincidence) so facet-merge cancels them; a no-op on non-coincident geometry.
• solidAngle, windingNumber, windingNumberIndexed, extractByWinding, extractByWindingPatches — the generalized winding-number field and surface extraction.
• extractByCellComplex — the volumetric cell-complex classifier (radial edge fans → cells → winding propagation → manifold-by-construction extraction).
• dedupCoincidentTriangles — exact coincident-face deduplication.

Heffalump Classifier (v0.5.5)

The heffalump classifier is a barrier-only classification strategy for meshes with defective topology (non-manifold edges, fragmented boundaries, cracks, holes). Instead of relying on boundary walks (which break when the boundary is fragmented), it classifies each triangle individually:

• Closed other mesh: ray-cast each triangle's centroid through the other mesh (odd crossings = inside)
• Open other mesh: find nearest surface triangle and check which side the centroid is on (normal direction = outside)

heffalumpClassify(megaSoup, segments, trisA, trisB, opts?)

Barrier-only classification for meshes with defective topology. Classifies each triangle individually rather than by flood-filled components.

• megaSoup: Split triangles with mesh tags from bmsSplit
• segments: Intersection segments with pool vertex endpoints
• trisA / trisB: Original mesh triangles
• opts.snapThreshold (v0.5.8, default 0.9): per-component majority-snap ratio. After the per-triangle vote, if ≥ this fraction of a component agrees, the stragglers snap to the majority — this erases lone flipped "spur" triangles whose centroids hug the other surface. Genuinely mixed components (the barrier-gap case) are nowhere near unanimous and stay per-triangle.
• opts.maxSnapStragglers (v0.5.9, default 8): absolute-count gate on the snap. The snap only collapses a tiny minority — it never bulldozes a large, legitimate region that happens to read as a low ratio (e.g. a terrain area inside a prism that is flood-fill-connected to the outside).
• Returns: { aInside, aOutside, bInside, bOutside, componentWalks }

shouldUseHeffalump(trisA, trisB)

Detect whether a mesh pair needs the heffalump classifier. Returns true if either mesh has non-manifold (over-shared) edges.

• Returns: boolean

reclassifyTriangles(groups, mesh, fromSide, triIndices)

Move triangles between inside/outside groups by index. Useful for fixing misclassified triangles programmatically.

• groups: { aInside, aOutside, bInside, bOutside }
• mesh: "A" | "B"
• fromSide: "inside" | "outside" — triangles are moved to the opposite side
• triIndices: number[] — indices within the source array to move
• Returns: Updated groups (mutated in place)

reclassifyAtPoint(groups, cx, cy, cz, tolerance?)

Reclassify a single triangle identified by its centroid coordinates. Useful for click-to-toggle in a 3D viewer.

• cx, cy, cz: Centroid coordinates to match
• tolerance: Match tolerance (default: 0.01)
• Returns: { moved: boolean, mesh?: string, from?: string, to?: string }

reclassifyRegion(groups, mesh, fromSide, seedIdx)

Reclassify a connected region — flood fill from a seed triangle to move all connected same-side triangles together.

• mesh: "A" | "B"
• fromSide: "inside" | "outside"
• seedIdx: Index of the seed triangle in the source array
• Returns: number — count of triangles moved

createVertexPool(tolerance)

Create a shared vertex pool with spatial hash deduplication. Points within tolerance get merged to the same object reference.

intersectMeshPair(trisA, trisB)

Find all intersection segments between two meshes.

• Returns: Segment[] — [{ p0, p1 }, ...]

intersectMeshPairTagged(trisA, trisB)

Like intersectMeshPair but each segment carries source triangle indices.

• Returns: [{ p0, p1, idxA, idxB }, ...]

repairMesh(soup, config?, onProgress?)

High-level async mesh repair pipeline.

• config.closeMode: "none" | "weld" | "stitch" (default: "none")
• config.snapTolerance: Weld tolerance in metres (default: 0)
• config.stitchTolerance: Stitch tolerance (default: 1.0)
• config.removeDegenerate: Remove degenerate/sliver triangles (default: true)
• config.sliverRatio: Sliver aspect ratio threshold (default: 0.01)
• config.cleanCrossings: Remove over-shared edge duplicates (default: true)
• config.removeOverlapping: Remove anti-parallel internal wall triangles (default: false)
• config.overlapTolerance: Overlap detection tolerance (default: 1e-4)
• Returns: Promise<{ soup, points, triangles }>

Repair Functions

Individual repair steps, usable standalone:

| Function | Description | |----------|-------------| | deduplicateSeamVertices(tris, tol?) | Merge coincident seam vertices | | resolveTJunctions(soup, tol?, maxPasses?) | Split edges at T-junction vertices | | resolveTJunctionsHoleFree(soup, tol?, maxPasses?) | Hole-free T-junction resolution (shared welded identity, no cracks) | | cancelCoincidentFaces(soup, tol?) | Cancel opposite-winding coincident pairs (zero-thickness membranes) | | weldVertices(tris, tolerance) | Merge vertices within tolerance → indexed mesh | | weldedToSoup(weldedTris) | Convert indexed mesh back to soup | | removeDegenerateTriangles(tris, minArea?, sliverRatio?) | Remove zero-area and sliver triangles | | extractBoundaryLoops(tris) | Find open boundary loops | | triangulateLoop(loop) | Triangulate a 3D polygon loop | | capBoundaryLoops(tris) | Cap all boundary loops (parallel) | | capBoundaryLoopsSequential(tris) | Cap all boundary loops (sequential) | | stitchByProximity(tris, tolerance?) | Connect nearby boundary edges | | cleanCrossingTriangles(tris) | Remove over-shared edge duplicates | | removeOverlappingTriangles(tris, tol?) | Remove anti-parallel internal walls | | forceCloseIndexedMesh(points, triangles) | Force-close an indexed mesh | | fillOpenEdgeLoops(soup) | Fill closed loops of open edges with fan triangles | | weldBoundaryVertices(tris, tolerance) | Weld boundary-only vertices | | soupToIndexed(tris, tolerance) | Alias for weldVertices — convert soup to indexed mesh | | indexedToSoup(weldedTris) | Alias for weldedToSoup — convert indexed mesh back to soup |

Hole-free repair (v0.6.2)

Polygon/prism cuts on battered (near- but not-quite-vertical) walls can leave two artifacts where the cut grazes a triangle near an edge: sub-tolerance slivers weld back onto the surface with the reverse winding (zero-thickness "membrane" pairs), and the off-edge crossing vertex becomes a T-junction. These preserve volume but z-fight on render and break downstream tooling.

The existing resolveTJunctions keys vertices with toFixed() strings, so two triangles sharing an edge can disagree on that edge's split points and the mesh tears open. The two functions below fix both artifacts without opening the mesh:

import { cancelCoincidentFaces, resolveTJunctionsHoleFree } from "trimesh-boolean";

// 1) remove the zero-thickness membranes (opposite-winding coincident pairs only —
//    same-winding duplicates and degenerates are left for the dedup/degenerate passes)
var soup = cancelCoincidentFaces(piece, weldEps);

// 2) resolve remaining T-junctions hole-free
soup = resolveTJunctionsHoleFree(soup, weldEps);

• Identity is a neighbourhood-weld integer pool (round(x/eps) with a 27-cell search), not toFixed() and not exact rationals — welding is a tolerance operation, so two triangles across a shared edge resolve to the same vertex ids and split that edge identically. Exact predicates stay reserved for orientation signs, not fuzzy identity.
• cancelCoincidentFaces is stricter and safer than removeOverlappingTriangles: it cancels only exact opposite-winding coincident pairs, so it never deletes near-coincident but genuinely-distinct wall triangles (which would tear holes).
• resolveTJunctionsHoleFree re-triangulates each affected triangle with a local-frame Delaunay pass (never a corner fan, which emits collinear zero-area slivers) and re-orients each sub-triangle to the source normal, converging in a couple of passes.
• v0.6.5 — near-edge snap. A seam T-junction usually places the hanging vertex within tolerance of the host edge but not exactly on it. Inserting that raw off-edge vertex left near-collinear points → Delaunay slivers, some dropped as "outside parent" → holes, and the vertex stayed a T-junction on the new sub-edges. Each on-edge hit is now snapped to its perpendicular projection (the point exactly on the host edge), so the fan tiles the parent exactly. The snap moves the point ≤ eps, so the next pass's weld pool re-merges it with the neighbour's vertex — still hole-free. (Before v0.6.5, on a flat 10 m triangle with 0.5 mm-off hits: tj 8 → 7, min sub-area 2.5e-4; after: tj 8 → 0, min sub-area 0.25, no new open edges, at local and UTM scale.)

Component Functions

| Function | Description | |----------|-------------| | findConnectedComponents(soup) | Split a soup into connected components via shared edges | | findConnectedComponentsPooled(soup, options?) | Integer-id twin of the above — same result, no toFixed string keys (see Scaling) | | 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 | | selectSplits(groups, selections) | Select specific groups with optional flip |

Normal Functions

| Function | Description | |----------|-------------| | triNormal(tri) | Unit face normal of a triangle | | ensureZUpNormals(tris) | Flip downward-facing triangles to Z-up | | flipAllNormals(tris) | Reverse all triangle winding | | classifyNormalDirection(tris, isClosed, volume) | Classify dominant normal direction | | computeSignedVolume(tris) | Signed volume via divergence theorem | | computeProjectedArea(tris, plane) | Projected footprint area | | compute3DSurfaceArea(tris) | True 3D surface area |

Intersection Functions

| Function | Description | |----------|-------------| | triTriIntersection(triA, triB) | Moller tri-tri intersection → segment | | triTriIntersectionDetailed(triA, triB) | With signed distances | | chainSegments(segments, threshold) | Chain segments into polylines | | simplifyPolyline(points, spacing) | Distance-based simplification | | buildSpatialGrid(tris, cellSize) | Build XY spatial hash (for Z-ray) | | buildSpatialGridOnAxes(tris, cellSize, getA, getB) | Build spatial hash on arbitrary axes | | queryGrid(grid, bb, cellSize) | Query XY spatial hash | | queryGridOnAxes(grid, a, b, cellSize) | Query arbitrary-axis spatial hash | | computeBBox(tris) | Compute axis-aligned bounding box of a triangle array | | triBBox(tri) | Compute bounding box of a single triangle | | bboxOverlap(a, b) | Test if two bounding boxes overlap | | estimateAvgEdge(tris) | Estimate average edge length of a triangle array |

Boolean Internals (Advanced)

| Function | Description | |----------|-------------| | classifyPointMultiAxis(point, otherTris, grids) | Classify inside/outside via 3-axis majority vote | | classifyByFloodFill(tris, crossedMap, otherTris, otherGrids) | BFS flood-fill classification with multi-axis seeds | | fanTriangulate(tri, segments) | Fan triangulation of crossed triangle (primary method) | | retriangulateWithSteinerPoints(tri, segments) | CDT split of crossed triangle with Steiner points (fallback) | | buildCurtainAndCap(tris, floorOffset) | Extrude boundary to floor + cap | | generateClosingTriangles(tris, maxDist) | Iteratively close boundary gaps |

Internal (non-exported) functions used by the boolean pipeline:

| Function | Description | |----------|-------------| | splitStraddlingAndClassify(tris, classifications, crossedMap, otherTris, otherGrids, otherIdxKey) | Split crossed tris via fan triangulation, classify via border-segment priority + half-space fallback, enforce constraints across segment edges | | halfSpaceTest(point) | Classify a point against the nearest intersection segment using the other mesh's triangle normal | | segHalfSpace(point, seg) | Classify a point against a specific segment's other-mesh triangle plane |

Utility Functions

| Function | Description | |----------|-------------| | dist3(a, b) | 3D Euclidean distance | | distSq3(a, b) | Squared 3D distance | | triangleArea3D(tri) | Triangle area via cross product | | computeBounds(points) | Axis-aligned bounding box | | cross(a, b) | 3D cross product | | lerpVert(a, b, t) | Linear vertex interpolation | | countOpenEdges(tris) | Count boundary and non-manifold edges | | vKey(v) | Vertex to string key for spatial hashing | | edgeKey(k1, k2) | Canonical edge key from two vertex keys | | indexGroups(groups, tolerance?) | Soup groups → shared points pool + per-group [i,j,k] index triples (see Indexed Group Output) | | indexGroupsToTypedArrays(indexed) | Flatten indexed groups → Float64Array positions + per-group Uint32Array indices |

Working with Kirra Surface Data

The library includes real-world mining surface data from the Kirra application. Kirra surfaces use the format { vertices: [{x,y,z}, ...] } per triangle. To convert to trimesh-boolean soup:

// Convert Kirra triangles to trimesh-boolean soup
function kirraToSoup(surface) {
  var soup = [];
  for (var i = 0; i < surface.triangles.length; i++) {
    var verts = surface.triangles[i].vertices;
    if (verts && verts.length >= 3) {
      soup.push({ v0: verts[0], v1: verts[1], v2: verts[2] });
    }
  }
  return soup;
}

Pre-extracted Kirra surfaces (terrain, cylinder, cup, convoluted block) are included in examples/public/kirra-surfaces.json with UTM coordinates centroid-subtracted for demo use. The convoluted block is a 32-triangle open surface that crosses the terrain twice — the hardest test case for multi-crossing classification.

The Three.js demo (examples/index.html) also has Import KAP / Export KAP: import reads surfaces.json from a Kirra .kap ZIP into the Mesh A/B dropdowns; export writes a minimal Kirra-compatible archive (manifest + two surfaces for the current Mesh A and B) for round-tripping or testing in Kirra.

Data Model

The library uses plain JavaScript objects — no classes, no Three.js types:

// Vertex
{ x: number, y: number, z: number }

// Triangle (soup format)
{ v0: Vertex, v1: Vertex, v2: Vertex }

// Welded triangle (indexed format)
{ vertices: [Vertex, Vertex, Vertex] }

// Segment
{ p0: Vertex, p1: Vertex }

How It Works

Boolean Algorithm — Step by Step

Step 1: Intersection Detection

Find all triangle-triangle intersection segments between mesh A and mesh B using the Moller algorithm.

• Each segment records its source triangle indices (idxA, idxB)
• Builds a crossedMap — which triangles are "crossed" by the other mesh
• Issue: Moller can miss near-coplanar or edge-on intersections. Deterministic jitter offsets mitigate this.

Step 2: Spatial Grid Construction

Build 3 spatial hash grids per mesh (XY, YZ, XZ) for accelerated ray casting along Z, X, and Y axes.

• Cell size is 2x the average edge length of each mesh
• Three grids enable multi-axis ray casting (no single-axis blind spots)
• Issue: Very small or very large meshes (sub-mm edges, or UTM 600000+) can cause hash collisions. The library centroid-shifts large coordinates internally.

Step 3: Flood-Fill Classification

BFS from non-crossed seed triangles to classify connected regions as inside/outside via multi-axis majority vote.

• Seed triangles ray-cast along +Z, +X, +Y; 2+ inside votes = inside
• Classification propagates to all connected non-crossed triangles in the same component
• Issue (open surfaces): Ray-casting against an open mesh is unreliable — rays can escape through open edges and give wrong inside/outside results. For open surfaces, Step 5 corrects these errors using the half-space test.

Step 4: Fan Triangulation

Split every crossed triangle at its intersection segment endpoints using fan triangulation (CDT fallback for edge cases).

• Chain intersection segments into ordered polylines
• Identify boundary entry/exit points via barycentric coordinates
• Fan from each original vertex to sequential chain points — every sub-triangle has at least 1 original vertex and 1 edge on the intersection boundary
• Eliminates "pocket triangles" (all-Steiner sub-triangles) that plagued CDT — reduced from 93 to 5 across test meshes
• CDT fallback for: multiple disconnected polylines, entry/exit on same edge, chain endpoint at original vertex

Step 5: Half-Space Classification

Classify every triangle (non-crossed and crossed sub-triangles) using a multi-stage approach:

Step D0 — Border-segment priority: If a crossed sub-triangle shares an edge with an intersection segment, classify its centroid directly against that specific segment's other-mesh triangle plane. This prevents "nearest segment" from picking a wrong crossing in multi-crossing scenarios.

Steps D1-D4 — Fallback chain: half-space test against nearest segment, vertex adjacency inheritance, sub-triangle centroid half-space, ray-cast centroid (last resort).

Step E3 — Constraint enforcement: After initial classification and adjacency propagation, iterate through all segment edges. Sub-triangles sharing a segment edge MUST have opposite classifications (one inside, one outside). Any violations are corrected using the specific segment's plane.

• Calibration: The normal convention (outward vs inward) is auto-detected by sampling points near the intersection, offsetting along the triangle normal, and ray-casting.
• Why this works for open surfaces: Unlike ray-casting (which counts boundary crossings and fails for non-watertight meshes), the half-space test only needs local geometry at the intersection.
• Confidence propagation: Confident classifications propagate to adjacent non-confident triangles via edge adjacency.
• Known limitation: Multi-crossing open surfaces can still have spill where the fallback path picks the wrong nearest segment. See KNOWN_ISSUES.md for details.

Step 6: Seam Deduplication

Merge coincident vertices along the intersection boundary to produce a clean seam.

• Tolerance-based deduplication at 1e-4
• Applied independently to each of the 4 groups (aInside, aOutside, bInside, bOutside)

Step 7: Normal Propagation

Ensure consistent winding order across the result mesh.

• BFS-based winding propagation from a seed triangle
• Falls back to Z-up normal enforcement if BFS doesn't reach all triangles

Step 8: Group Combination

Combine inside/outside groups based on the requested operation.

| Operation | Formula | Groups kept | |-------------|------------------------------------|--------------------------------------| | subtract | A \ B | A-outside-B + B-inside-A (flipped) | | union | A ∪ B | A-outside-B + B-outside-A | | intersect | A ∩ B | A-inside-B + B-inside-A |

Step 9: Weld & Return

Weld the combined triangle soup into an indexed mesh and return { soup, points, triangles }.

Mesh Repair Algorithm

1. Vertex deduplication — spatial-grid merge of coincident vertices
2. T-junction resolution — detect and split edges at mid-edge vertices
3. Welding — merge vertices within tolerance
4. Degenerate removal — filter zero-area and sliver triangles
5. Stitching — connect nearby boundary edges
6. Capping — triangulate boundary loops
7. Force-close — fill remaining gaps iteratively

Dependencies

• delaunator — Fast Delaunay triangulation
• @kninnug/constrainautor — Constrained Delaunay
• robust-predicates — Exact arithmetic orientation and incircle tests
• tiny-exact-math — Exact cross product and dot product for degenerate-case handling

Optional peer dependency:

• three >=0.150.0 — Only needed for trimesh-boolean/three adapter

License

MIT