Robustness: validate cavities before mutating; repair with exact predicates or reject atomically#6
Merged
Merged
Conversation
Add three primitives to geometry, all backed by Shewchuk's adaptive-precision predicates via the robust crate in 2D/3D: - robust_orientation: like orientation() but exact, with no log-det cutoff; resolves the true sign of determinants that slogdet rounds to zero on slivers (falls back to orientation() in other dimensions) - robust_in_circumsphere: strict exact in-circumsphere test (incircle/insphere normalized by the simplex orientation so the answer is orientation-independent); None outside 2D/3D - precise_volume: simplex volume from the adaptive-precision determinant value, immune to the cancellation that corrupts plain f64 volumes of high-aspect slivers These deliberately do NOT replace the reference-compatible tolerance based tests; they exist for the cavity validation/repair path added in the next commit, where geometric truth matters more than bug compatibility. Sign conventions are pinned by unit tests against orientation() on well-conditioned inputs plus a below-cutoff sliver case.
Sliver simplices (mixed coordinate scales force aspect ratios ~1e7)
feed the floating-point circumsphere test cancellation noise, so the
cascade can assemble a cavity that is not re-triangulable: voids or
protrusions (volume not conserved), a falsely-empty cavity that leaves
the inserted point unconnected, or a cavity that swallows every
simplex of the point while its total volume sits below the
conservation check's absolute tolerance (making that check vacuous).
The Python reference asserts volume conservation only AFTER mutating -
a failing insertion corrupts its state - and silently orphans vertices
in the cases its check cannot see.
bowyer_watson now computes the would-be (deleted, created) outcome and
validates it read-only, BEFORE any mutation:
- volume conservation is checked with adaptive-precision determinant
volumes (geometry::precise_volume), so the check compares true
volumes instead of cancellation noise
- the point must end up connected (catches both the empty-cavity and
the swallowed-hull-simplices failure modes)
When validation fails, the cavity is repaired and re-validated: in
2D/3D it is rebuilt from the seeds with exact insphere predicates
(geometry::robust_in_circumsphere) - the exact Delaunay cavity is
connected, void-free, and star-shaped around the point - and in higher
dimensions it is pruned to the seed component and shrunk until every
hole face is visible from the point. If even the repaired cavity fails
validation, the insertion is rejected with the triangulation untouched
(same AssertionError as before, or ValueError when the point cannot be
connected), and add_point rolls back its vertex on these rejections,
so a failed insertion is fully atomic and callers can skip the point
and continue.
Well-conditioned insertions never enter the repair path and behave
bit-identically to the reference (the 64 cross-validation tests pass
unchanged). Stress sweeps over 50 seeds x {mixed-scale, off-origin,
near-duplicate, random} x {2D,3D}: corrupted end states drop from
99/400 runs on main to 0/400, with every former corruption now either
repaired (e.g. all 22 previously-failing insertions in the hull-heavy
3D benchmark now succeed) or atomically rejected. A/B benchmark shows
no performance change on well-conditioned workloads. Policy documented
in src/tolerances.rs.
Seeded mixed-scale and near-duplicate sweeps (2D/3D, 10 seeds each) assert the contract from src/tolerances.rs: insertions either succeed and connect the new vertex, or raise leaving vertices and simplices exactly as they were; no vertex ever loses its last simplex; the internal indexes stay consistent. Plus a regression test for the empty-cavity orphan (mixed-scale seed 2) and a guard that random unit-cube sweeps never reject (the repair path must not fire on well-conditioned input).
This was referenced Jun 10, 2026
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
1 participant
Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.
Summary
Fixes the known mixed-coordinate-scale failure mode documented in
src/tolerances.rs: sliver simplices (aspect ratio ~1e7) feed the floating-point circumsphere test cancellation noise, so Bowyer-Watson can assemble a cavity that is not re-triangulable. On main this corrupts state: the volume-conservation assert fires only after mutation, and the failure modes the assert cannot see (cavities whose total volume sits below its absolute tolerance) silently orphan vertices.Three changes, in order of the commits:
Exact geometric primitives (
geometry.rs, newrobustdependency):robust_orientation,robust_in_circumsphere, andprecise_volume, backed by Shewchuk's adaptive-precision predicates in 2D/3D. These deliberately do not replace the reference-compatible tolerance tests; they serve the repair path only.Validate before mutate, repair, or reject (
triangulation.rs):bowyer_watsoncomputes the would-be(deleted, created)outcome read-only and validates it — volume conservation (with precise volumes) and point connectivity (catches the empty-cavity and swallowed-hull-simplices orphan modes the assert is blind to). On failure the cavity is repaired and re-validated: 2D/3D rebuild it with exact insphere predicates (the exact Delaunay cavity is connected, void-free, star-shaped); 4D+ prune to the seed component and shrink until star-shaped. If even the repaired cavity fails, the insertion is rejected with the triangulation untouched (sameAssertionError, orValueErrorwhen the point cannot be connected), andadd_pointrolls back its vertex — failed insertions are fully atomic, so callers can skip the point and continue.Tests pinning the contract (seeded mixed-scale/near-duplicate sweeps in 2D/3D, atomicity of rejections, no orphans, invariant holds, and a guard that well-conditioned inputs never reject).
Well-conditioned insertions never enter the repair path and behave bit-identically to the reference — all 64 cross-validation tests pass unchanged.
Stress results (50 seeds per pattern, end-state classification)
"corrupt" = invariant broken, a vertex lost its last simplex, a successful insertion left its vertex unconnected, or a rejection leaked the vertex. Construction-time orphans from scipy/QHull merging near-degenerate points are excluded (reference-identical behavior).
Performance
A/B benchmark vs main, same machine, best of 3: no change (2D 5k 0.139→0.137 s, 3D 2k 0.160→0.157 s, 4D 500 0.239→0.247 s, hull-heavy 2D 1.063→1.042 s). The hull-heavy 3D spiral benchmark previously had 22 insertions fail with AssertionError per run; all 22 now succeed via repair, and the run is still marginally faster (0.699→0.676 s).
examples/adaptive_learnernd.pykeeps its 3.5× speedup.Verification
pytest: 106 passed (64 existing cross-validation + 42 new robustness)cargo test --lib --tests: 18 passed (incl. predicate sign-convention pins)