trimesh-build-js

Build triangle meshes, open or closed, from point clouds of underground voids: caves, drives, tunnels, stopes, CMS cavity scans and blast-hole voids. Break lines you digitise become hard edges. A closed mesh reports its enclosed volume.

The output is a BMS (Brent's Mega Soup) pair from trimesh-boolean: a createVertexPool pool plus a mega soup of { v0, v1, v2, mesh, origIdx } triangles that share PoolVertex objects. It goes straight into bmsBooleanOp. toIndexed() turns it into the { positions, index } form Kirra's addGeneratedSurface takes.

Vanilla JavaScript, ES modules, no WASM. Depends on las-laz-js, delaunator, @kninnug/constrainautor and trimesh-boolean.

Live demo: brentbuffham.github.io/trimesh-build-js. It meshes synthetic voids, the bundled Wookey Hole cave, or your own LAS/LAZ file in the browser, and shows open loops, break line edges, non-manifold edges and which way the normals face. The source is in examples/; run npm run dev to work on it locally.

How it works

Every point gets a local patch:

1. Take its k nearest neighbours and fit a plane through them.
2. Drop neighbours from another wall (the bridging guard).
3. Project the patch to 2D and triangulate it with Delaunator, or Constrainautor when break lines are in the patch.
4. Keep only the triangles that touch the point (its umbrella).

A triangle is accepted when the patches of 2 of its 3 vertices agree on it. Accepted triangles are welded by the BMS vertex pool. The mesh is then cleaned, voting gaps of 6 edges or fewer are filled, and the winding is made consistent. Normals point out of rock into the void.

Install

npm install trimesh-build-js

Use

import { openLas } from "las-laz-js";
import { buildMesh, toIndexed } from "trimesh-build-js";

var las = await openLas(file);
var pts = await las.readPoints({ fields: ["x", "y", "z"] });

var result = buildMesh(
	{ count: pts.count, x: pts.x, y: pts.y, z: pts.z },
	{
		thin: 0.05,                    // raw scans: even out scan-line sampling (metres, 3D)
		denoise: { iterations: 3 },    // raw scans: smooth before meshing
		viewpoints: [[x, y, z]],       // scanner positions (in the void), if known
		breaklines: [{ vertices: [[x, y, z], ...], closedLoop: false }]
	}
);

result.mesh.closed;          // true only when no edge is open or over-shared
result.mesh.enclosedVolume;  // m³ when closed, else null
result.mesh.boundaryLoops;   // open edges, as loops of pool vertex ids
result.report;               // counts from every stage

// Booleans: the BMS pair is origin-shifted; shift the other mesh the same way
// bmsBooleanOp(result.soup, otherSoup, "subtract")

// Kirra
var indexed = toIndexed(result);   // { positions: Float64Array (world), index: Uint32Array }
// addGeneratedSurface({ id, name, positions: indexed.positions, index: indexed.index, layerName })

Using every core

buildMeshAsync gives the same mesh as buildMesh, with the per-point triangulation spread over worker threads. You tell it how to start a worker, and the library supplies the worker script:

import { buildMeshAsync } from "trimesh-build-js";

// browser
var result = await buildMeshAsync(cols, {
	thin: 0.05,
	workers: "auto",
	createWorker: function () {
		return new Worker(new URL("trimesh-build-js/worker/browser", import.meta.url), { type: "module" });
	},
	onProgress: function (stage, fraction) { /* thin, denoise, prepare, reconstruct, weld, orient, done */ }
});

// Node
import { Worker } from "node:worker_threads";
var workerUrl = new URL(import.meta.resolve("trimesh-build-js/worker/node"));
var result = await buildMeshAsync(cols, { workers: 8, createWorker: function () { return new Worker(workerUrl); } });

workers: "auto" uses one fewer than the cores, at most 8 (more gains almost nothing), and stays on the calling thread below 20,000 points after thinning, where starting workers costs more than it saves (8 workers take 1.3x as long at 10,000 points and half as long at 100,000). A number is used as given. After the threaded stages, what is left runs on one thread: thinning, the weld, orientation and the visibility vote. On WALL.las (4.3M points, thin 0.1) that is 8.9 s for the weld and 25.6 s for orientation of a 58 s build.

At 1M points on a 24-core machine the whole build takes about 14.5 s (triangulation 3.4 s), down from 55 s in 0.2.0, and peaks at about 1.1 GB. For a browser tab, set maxPoints: the build then stops with TOO_MANY_POINTS and a suggested thin value instead of running out of memory.

Patching loops

From 0.6.0 the repair functions below live in trimesh-repair-js and are re-exported here for one release; import them from trimesh-repair-js.

patchLoop fills one open loop you choose. It works like Fill in Kirra's Mesh Edit, and is ported from LocalVoidFill.fillLoopWithTriangles. It uses trimesh-boolean's triangulateLoop on the loop's own vertices and turns each new triangle to agree with its neighbour. The result is then re-oriented and re-validated, so result.mesh stays current.

import { patchLoop, patchLoops } from "trimesh-build-js";

patchLoop(result, 0);                                  // loop index in result.mesh.boundaryLoops
patchLoop(result, pickedPoints);                        // or world [x, y, z] points, e.g. picked in Kirra
patchLoop(result, 2, { method: "centroid" });           // force one method
patchLoops(result, { maxEdges: 50 });                   // every loop up to 50 edges
// patchLoop  -> { added, method, refused: [{ loop, reason }] }
// patchLoops -> { added, patched, methods: { fair, fan, centroid, vertexFan }, refused }

| method | What it does | |---|---| | "auto" (default) | Tries fair, then fan, centroid and vertexFan, and uses the first that is valid. | | "fair" | Liepa (2003): the best triangulation of the loop, refined to the mesh's edge length, with the new points faired (smoothed) into the surrounding surface, so the patch bulges with the wall instead of cutting across it. | | "fan" | Kirra's Fill: triangulateLoop on the loop's own vertices. No new points. | | "centroid" | One new point at the loop centre, fanned to every loop edge. | | "vertexFan" | A fan from one loop vertex to all the others, trying each vertex in turn. |

Figure-8 loops. A loop that passes through one vertex twice, where two holes touch at a pinch point, is split there into simple loops (ported from trimesh-boolean's _splitSelfTouching). Each lobe is then patched on its own.

What works on real data. On the Wookey Hole sample at 5 cm thinning, auto closes 498 of 500 loops, 495 of them by fair, in about 1.2 s, with no non-manifold edges and no fold edges. Part 3 of the survey closes completely. A spherical cap cut from a sphere mesh (9% of its volume) refills to within 0.5% of the full volume with fair, against 9% short with a flat centroid fan.

fair steps aside, and auto moves on, when the patch would come within the weld tolerance of the mesh (it pushes a point out up to three times first) or when every triangulation needs an edge the mesh already has. Loops over 400 edges start from a centroid fan rather than the O(n³) best triangulation. Where the mesh reaches into a hole with long, thin triangles, the patch's first row stays as coarse as those loop edges (loop edges are never split), so it follows the surface less well there.

A loop is refused, never thrown on, when it runs along a break line, isn't simple, or when every method would give an edge a third triangle. fillGaps (automatic, loops of 6 edges or fewer, auto) and closeHoles (opt-in, centroid) use the same per-loop code. In the demo, tick patch loops and click near a red loop, then press Patch selected or Enter, or use Patch all.

Raw scans need thinning and denoising

Scanners sample densely along scan lines, often about 1 mm apart, and LAS files round coordinates (often to 1 mm). A point's nearest neighbours then lie on one line, and no plane fits them. Use thin to even out the spacing (it calls las-laz-js dedupe). Then use denoise to bring the noise well below the spacing (it calls las-laz-js denoisePoints).

Two blast-hole scans of about 1 million points each, thinned to 5 cm (about 16,000 points), went from 511 and 477 open loops without denoising to 87 and 65 with three denoise passes. Both had no non-manifold edges and took under 3 s. Keep the thinning spacing well above the scan noise: at 3 cm, on the same scans with 1.3 cm of noise, patches disagree and the mesh folds.

Options

| Option | Default | Meaning | |---|---|---| | origin | cloud centroid | Shift applied before any work. Required for a Float32 cloud, whose values must already be world − origin. | | normals | computed | Per-point normals (3 per point). The sign is ignored. | | thin | off | Minimum 3D point spacing, via las-laz-js dedupe. | | denoise | off | true or { method, iterations, k, maxDistance } for las-laz-js denoisePoints. | | breaklines | none | [{ vertices: [[x,y,z], ...], closedLoop }], world coordinates. | | viewpoints | none | Scanner positions; normals face the nearest one. | | k | 20 | Neighbours per patch. | | maxRadiusMultiplier | 3 | Neighbour cull distance, × the median neighbour distance. | | minNeighbours | 6 | A point with fewer neighbours is skipped (boundary or outlier). | | normalAgreement | 0.5 | Bridging guard: drop neighbours with |n·n| below this. | | maxPlaneOffset | 0.5 | Bridging guard: drop neighbours further than this × scale off the plane. | | minVotes | 2 | Patches that must agree on a triangle. | | tolerance | max(1 mm, 0.25 × spacing) | Weld distance. Input points closer than this are merged before meshing, and so are break line vertices. | | breaklineSnap | 0.001 | Cloud points this close to a break line are dropped (world units). | | maxGapEdges | 6 | Voting gaps up to this many edges are filled. 0 turns it off. | | repairFolds | true | Cut twisted strips at their folds so the mesh can be oriented (see Orientation). | | visibility | true | Ray vote for the void side of open components without viewpoints (see Orientation); false, or { samples, rays, minMargin } (defaults 1000, 8, 0.2). | | closeHoles | false | { maxLoopEdges }: fill real holes with a centroid fan. | | checkSelfIntersections | false | Count the places the mesh passes through itself and put them in report.selfIntersections (crossingPairs, coplanarPairs, triangles, ms). It takes seconds on a large mesh, so it is off by default. countSelfIntersections(result) does the same on any result, for instance after patchLoops: Wookey Hole part 3 has 203 crossing pairs in 162,268 triangles as built and 15,798 after patching, because a faired patch can cut through the wall beside it. |

Only bad input throws (TrimeshBuildError with a code): wrong column lengths, a Float32 cloud with no origin, non-finite coordinates, crossing break lines, or fewer than 3 points. Problems with the result are reported, never thrown.

Orientation

Normals are flipped for each connected component:

• with viewpoints, normals face the nearest scanner position;
• otherwise, a closed mesh has its void inside, so normals point inward (negative signed volume);
• otherwise, an open component gets a ray vote ("visibility"). Rays are cast into both sides from about 1,000 triangles, sampled by area. Inside a cave, drive or hole, the rays cast into the void come back off the opposite wall, while those cast into the rock escape, so normals point at the side whose rays come back (after Takayama, Jacobson & Sorkine 2014). The rays can hit every triangle, because holes often split a cave into separate wall pieces. perComponent[i].margin is |H+ − H−| / (H+ + H−) over the two sides' hit rates;
• a component with a weak vote (margin under 0.2, or fewer than 10% of rays coming back on either side, as on flat terrain) is left "unresolved". Its winding is still consistent; only its overall direction is unknown.

The vote runs once at the end of buildMesh (report.visibilityMs), and again after patchLoop or patchLoops. On Wookey Hole it takes about 0.2 s. On part 3, which patchLoops closes completely, the sign the vote chose for the cave matches the closed mesh's signed volume on all 154,341 triangles.

Winding spreads across the flattest edges first (Hoppe et al. 1992's minimum spanning tree, over triangles rather than points). That matters because a scan mesh can hold twisted, Möbius-like strips between holes, where no winding is consistent. Walking flattest-first leaves each strip's seam on its sharpest crease, the fold that makes the twist. repairFolds (on by default, also exported) then removes the triangles on those seams. The cuts join neighbouring holes, which the gap fill or patchLoops close as usual. On Wookey Hole that removes 565 triangles (0.2%) and leaves no fold edges (mesh.orientationConflicts), before and after patching every loop; it was about 3,600 after patching before. report.foldsRemoved counts them. A triangle on a break line edge is never removed; report.foldsKept counts the conflicts left for that reason.

Known limits

• Close walls. Two walls closer than about the point spacing can't be told apart locally. At the free edges of two close parallel sheets, the patch sees both edge rows as one strip, so bridging can happen there, even at 2 × spacing.
• Small closed pieces and floating slabs have no reliable side. A closed piece is oriented as a cavity (void inside), but in a cave scan the small ones are usually boulders, whose void is outside; and the ray vote cannot decide a boulder or a thin slab (both sides see walls). On Wookey Hole after patching, 13 to 16 such pieces (500 to 800 triangles) and 2 to 7 "unresolved" ones (220 to 9,344) keep an arbitrary winding, and show as the back-face colour from inside. The big surfaces (289k, 496k and 175k triangles) agree with an independent vote everywhere. (A thin sealed sheet used to be reversed by its volume; since 0.6.7 the vote decides it, and when it cannot the earlier winding stays.)
• Break line junctions. Break lines may meet at a shared vertex (vertices closer than the weld tolerance are merged). A break line ending on another line's interior (a T-junction) is rejected like a crossing; add a vertex to the other line at that point.
• Deferred: ball pivoting and screened Poisson (as extra algorithms), decimation, smoothing, tiling of very large clouds, adaptive k.

Sample data

examples/public/samples/wookey-hole.laz is a 381,870-point survey of Wookey Hole cave, made with an iPhone 13 Pro photogrammetry workflow. It comes from CaveSurveys, github.com/CaveSurveys/Wookey-Hole, shared with "Feel free to distribute and use!". It drives a cave test and the demo's Wookey Hole cave source. wookey-hole-2.laz (638,466 points) and wookey-hole-3.laz (194,016 points) are the survey's other two parts, in the same coordinate frame, taken from the vertices of its OBJ meshes; see examples/public/samples/README.md.

At thin: 0.05 it meshes in about 6 s to about 260,000 triangles. 99% of them are in one surface, with no non-manifold edges and no fold edges. It has no viewpoints, so its sign comes from the ray vote: the cave orients as "visibility". The file is not part of the npm package.

Tests

npm test

The real-scan tests run only when the BHP scan files are on the machine; otherwise they are skipped.

Licence

MIT. Brent Buffham, kirra-design.com.