# 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

```bash
npm install trimesh-boolean
```

Or use the CDN for browser scripts:

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

**Links:** [npm](https://www.npmjs.com/package/trimesh-boolean) · [GitHub](https://github.com/brentbuffham/trimesh-boolean) · [Live Demo](https://brentbuffham.github.io/trimesh-boolean/)

### Live demo (GitHub Pages)

The [live demo](https://brentbuffham.github.io/trimesh-boolean/) is **built and deployed automatically** on every push to `main` or `master` by [`.github/workflows/pages.yml`](.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:

```bash
npm run build:docs
```

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

## Quick Start

```javascript
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

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

// Boolean on Three.js meshes directly
var resultMesh = booleanFromMeshes(threeGroupA, threeGroupB, 'subtract');
scene.add(resultMesh);

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

## 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`.

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

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`

### 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](#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`

```javascript
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

```javascript
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.

```javascript
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**:

```js
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](#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 |
| `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](#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](https://github.com/brentbuffham/Kirra) application. Kirra surfaces use the format `{ vertices: [{x,y,z}, ...] }` per triangle. To convert to trimesh-boolean soup:

```javascript
// 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:

```javascript
// 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](https://github.com/mapbox/delaunator)** — Fast Delaunay triangulation
- **[@kninnug/constrainautor](https://github.com/kninnug/Constrainautor)** — Constrained Delaunay
- **[robust-predicates](https://github.com/mourner/robust-predicates)** — Exact arithmetic orientation and incircle tests
- **[tiny-exact-math](https://www.npmjs.com/package/tiny-exact-math)** — Exact cross product and dot product for degenerate-case handling

Optional peer dependency:
- **[three](https://threejs.org/)** `>=0.150.0` — Only needed for `trimesh-boolean/three` adapter

## License

MIT