Problem

splat-transform --decimate hangs indefinitely on certain inputs, wedging the production GPU pipeline until its 2h timeout. Reproduced on a 9.84M-gaussian PLY where nearly every gaussian is coincident at the origin (degenerate/uninitialized capture).

There are two independent failures, both triggered by the same degenerate input:

1. O(N²) KD-tree build hang

nthElement in src/lib/spatial/kd-tree.ts used a 2-way Lomuto partition that only moves elements strictly less than the pivot. When a coordinate is all-equal, nothing moves and the selection range shrinks by one per pass — each pass O(N) — so the KD-tree build degrades from O(N log N) to O(N²). At ~10M coincident points that never completes. The stall is on the CPU before any GPU work dispatches, which is why it reproduced on both WebGPU/Vulkan and Metal.

Fix: 3-way (Dutch National Flag) partition. Equal elements collapse in a single pass, restoring O(N log N). For distinct coordinates the equal block is one element, so the median index and resulting tree are identical to before — no behavioural change for normal splats, no memory impact (in-place).

2. Decimate makes no progress on degenerate input

With every point coincident, all KNN distances are 0 and the traversal returns the same ~K shared neighbour indices for every query, so the directed-edge graph funnels onto a handful of targets. The greedy disjoint-pair matching can then only merge ~K pairs per pass (17, in the repro) instead of ~N/2, so it crawls toward the target across thousands of passes. The existing degenerate guards only fire on zero progress (edgeCount === 0, pairs.length === 0), so a tiny-but-nonzero matching slips through.

Fix: a no-progress guard. When a pass's matching is exhausted before reaching the target (pairs.length < mergesNeeded) yet removes less than MIN_ITERATION_PROGRESS (5%) of the current splats, throw a clear error rather than grind. A well-formed scene removes ~50% per exhausted pass, so legitimate multi-pass decimation never trips it; it's gated on matching exhaustion, so single-pass decimation can't trip it either.

Testing

• New test/kd-tree.test.mjs: builds a tree over 100k coincident points (would hang pre-fix) in milliseconds; brute-force KNN correctness on sets with frequent ties.
• New test/decimate.test.mjs case: a fully-coincident scene now throws the stall error instead of grinding.
• Full suite green (566 tests) incl. render-golden — no tie-break or behavioural shift on valid scenes. Lint clean.
• End-to-end on the original 9.84M PLY: previously hung 30+ min (136+ passes, never finishing); now fails in ~10s with a clear message and non-zero exit.