When line surface intersection fails due to tangency, try the nearest… - #1751

With the second commit, this is handling 1291_1743_cube_cut_tangent_outside_still_fails_simplified.slvs very nicely. However it still fails ASAN tests down in polygon.cpp for reasons I have no idea.

The previous problem of the edge being broken into pieces was due to the recursive subdivision of the curved surface. Once the pieces were sufficiently flat it tried to intersect the vertical edge with the surface and it was somehow passing the test because the lines were coincident, so it added a lot of intersections. This 2nd commit checks for parallel lines and fails intersection for those.

It also has a problem if you make the protruding side coincident - including the control point - AND make it single sided so the fillet cut does not extend past the top of the original extrusion. In that case the one side flickers with naked edges. It will do so if you drag either control point along its edge but it's always the one side that flickers regardless of which point is dragged. (not sure this description makes sense).

Actually the shell appears OK. When I said "fails" above it was just indicating naked edges, and also the fact that ASAN fails on the regression test. This does work (no naked edges) when the fillet cut is two sided so it extends past the box top. @BoykoNeov This would be good for Claude to have a look at when you get back ;-)

Written by Claude Opus 5 — both this text and the code it describes; posted by @BoykoNeov.

@phkahler — had a look. Short version: the ASan failure is my fault, not yours, and underneath it there is one real regression. Everything below is reproduced locally (MSVC, Debug, Ninja, no sanitizers), on a worktree of this PR with submodules at the pinned revisions, and identically with ENABLE_OPENMP both OFF and ON.

1. The ASan failure is a cascade of my own test, and it's a red herring

There is no memory-safety error. Of the three failing jobs:

• Windows builds with ENABLE_SANITIZERS=ON and reports no sanitizer error at all — just one failed check. (That job already runs the exact config I'd have built here, and MSVC ships no LeakSanitizer, so a local ASan build had nothing to add — I used the CI logs for this part and built everything else clean.)
• macOS builds with sanitizers off and fails the same one check.
• Ubuntu fails that same check, and then LeakSanitizer reports one 4096-byte leak.

That leak is mine. test/group/boolean_tangent_crossing/test.cpp:

    CHECK_FALSE(inters);
    CHECK_FALSE(leaks);      // <-- fails here
    CHECK_TRUE(el.l.IsEmpty());
    el.Clear();              // <-- never runs

CHECK_FALSE is do { if(!helper->CheckBool(...)) return; } while(0) — it returns from the test case. So when the check fails, el.Clear() is skipped and the SEdgeList's buffer leaks. That is exactly the reported stack: SEdgeList::AddEdge → List<SEdge>::Add → polygon.cpp:225. It only shows up on Ubuntu because MSVC ships no LeakSanitizer.

So the leak is a consequence of the failure, not a second problem, and chasing it into polygon.cpp was never going to lead anywhere. Sorry — that one cost you time and it was my bug.

Six Boolean tests have that shape — boolean_tangent_crossing, boolean_tangent_fillet, boolean_tangent_spline, boolean_tangent_edge, boolean_knife_edge, boolean_coplanar_union, all of them from the regression work I've contributed here. Every one misleads the same way on failure. The fix is to free first and check after:

    bool noEdges = el.l.IsEmpty();
    el.Clear();
    CHECK_FALSE(inters);
    CHECK_FALSE(leaks);
    CHECK_TRUE(noEdges);

With that applied and no other change, the suite is 264 cases / 937 checks green on current master 52c21e27, and the failure below still reports identically. It's up as BoykoNeov#8 — independent of this PR, and it should go in either way. It fixes no failing test; it just stops a failing test from burying its own message under a leak report.

2. The real failure: this PR regresses group/boolean_tangent_crossing

That test is on master and green there. Building the three trees in the same build directory, changing only the three files this PR touches:

So the first commit is where it starts, and the parallel guard doesn't change it. At head the rest of the suite is fine — exactly this one check fails. Same result with OpenMP on and off, so the parallelism isn't involved.

The model is ruevs' cube_cut with the profile spline made tangent to the cube's face on the other side, its corner left outside, so the line continuing from the tangency crosses that face. It's the same family as the one you're fixing, which is probably why it's the one that trips.

3. What the fallback does on this model

At base, ten PointIntersectingLine calls give up on that shell — eight of them via the parallel break, two by exhausting the 20 iterations. All ten return false, and the Boolean is watertight.

At head, all ten come back true, every one of them through the new fallback:

parallel (surface intersecting line)
found U=1.46869e-08, V=0.0 point=(-16.244 -30.000 30.000)
found U=1, V=0.0 point=(30.000 18.788 30.000)
parallel (surface intersecting line)
found U=1.66632e-08, V=0.0 point=(-16.244 -30.000 30.000)
parallel (surface intersecting line)
found U=1.70595e-08, V=1.0 point=(-16.244 -30.000 0.000)
parallel (surface intersecting line)
found U=0.0, V=0.5 point=(-16.244 -30.000 15.000)
...
failed: I=5, avoid=4
print 8 edges

Two things in there:

• Three "intersections" on one line. (-16.244, -30, 30), (-16.244, -30, 0) and (-16.244, -30, 15) are three different points on the same vertical edge, at its two ends and its midpoint. Same for the other edge: (30, 18.788, 30), (30, 18.788, 0), (30, 18.788, 15). AllPointsIntersectingUntrimmed recurses until each sub-patch is flat and calls PointIntersectingLine on sorig once per sub-patch, so each call seeds from its own patch centre and the fallback walks to a different point of the same edge. The dedup in AllPointsIntersecting compares uv with LENGTH_EPS, so they all survive as separate intersections.
• Every hit is on the boundary, by construction — EdgeCurveIntersection pins *u or *v to exactly 0.0 or 1.0. Two of them are the surface corner (u=1, v=0). A boundary hit is precisely the degenerate case for both ray-cast parity and trim assembly, since the point belongs to two edges and to the neighbouring surface as well.

Downstream, AssemblePolygon fails for surface I=5 with 8 dangling edges (failed: I=5, avoid=4, boolean.cpp:738) and sets booleanFailed. That's the naked edge.

The part I'd take away from this: suppressing eight of the ten hits still leaves the test failing (§4). So the problem doesn't look like a guard that needs tightening — it looks like a boundary-pinned point being the wrong shape of answer for this call, with one of them enough to break the trim.

4. Two things I tried that did not fix it

Both worth knowing so you don't spend the time:

• Fixing the antiparallel hole (see below) — output byte-identical, still fails.
• Not running the fallback on the parallel break (return false instead of break) — cuts the ten hits to exactly the two that came from iteration exhaustion, and it still fails. Both survivors are the same corner (30, 18.788, 30).

So the fallback needs more than a better parallel test; a single manufactured boundary intersection is enough to break the assembly.

5. The parallel guard has two holes anyway

Independent of the above — I measured that neither causes this failure, but both are real:

if(deg + curve->deg == 2) {  // check for parallel lines
    ...
    if(fabs(1.0 - d1.Dot(d2)) < 10*RATPOLY_EPS) return false;

• Antiparallel slips through. For lines pointing opposite ways d1.Dot(d2) is −1, so this evaluates fabs(2.0). The edge direction comes off the surface's control grid (always increasing u/v) while p0→p1 is whatever the caller had, so the relative orientation is arbitrary. fabs(1.0 - fabs(d1.Dot(d2))) closes it.
• The gate is algebraic where the property is geometric. deg + curve->deg == 2 only covers a degree-1 edge. I instrumented it: six of the ten calls on this model print guard SKIPPED, deg=3+1 — the surface edge is a cubic, and a cubic with collinear control points is a straight line. The other four reach the test and print dot=0, i.e. genuinely perpendicular. So on this model the guard never fires at all.

Minor, same function: 1 − cos θ < 1e-7 rejects anything closer than about 4.5e-4 rad — 0.026°, the square root of the number in the source. That may be what you want, but it's a much wider cone than 10*RATPOLY_EPS reads like. (If you switch to a cross-product form, |d1 × d2| = |sin θ| is linear in the angle, so the same 1e-7 would be ~4500× narrower — pick the threshold deliberately rather than reusing the constant.)

And one correction to something I nearly told you: the Vector::WithMagnitude(1) of zero vector! spam next to this test in the CI log is pre-existing — six of them on master in this same test. Not yours.

6. Offer

I have the worktree and build set up, so I can turn any patch around quickly — say the word and I'll run it against the full suite and report back. Two directions that look worth trying, if you want a second pair of hands on them: rejecting a fallback hit unless it's a genuine transversal crossing (the returned point currently isn't checked against the query segment at all), or handling the tangent-at-edge case where the degeneracy is actually understood, in the ray caster rather than in PointIntersectingLine.

Either way, the approach is still the right shape to me — fixing it in ratpoly.cpp is more general than splitting curves after the fact, and it's orthogonal to BoykoNeov#6 rather than competing with it.

@claude and @BoykoNeov First one question for @claude. What does "A boundary hit is precisely the degenerate case for both ray-cast parity and trim assembly, since the point belongs to two edges and to the neighbouring surface as well." mean? How is that a degenerate case? By the way a fillet surface is made the intersection is exactly on the boundary. The fix here just allows it to be found.

1. I agree with your ideas to fix the parallel guard. Please implement that first before trying anything else. Make it a commit on top of this so I can grab it.

2. I wonder if we should exclude the endpoints of the curve here, since those will likely be included via the existing vertex insertion code. I don't know why they might interfere, but it seems worth considering. The test model here only requires that we find one point on the edge of the surface in the middle of the edge.

3. boundary of the segment. You are right, I did not clip to the segment. It seems likely to be correct since the segment is from a PWL representation of a curve, but maybe we should confirm the point is not past either end.

4. Since this is working with the PWL segments, perhaps we should apply a similar fix for the refinement step when intersecting an exact curve. That code will also stop with tangency, but in this case it should not modify the point which is already exactly on the boundary due to this fix.

Anything else you can think of that might get this working with no regressions - it does fix both 1291_1743_cube_cut_tangent_outside... and cube_cut_2, so it has quite a bit going for it.

@claude please give this approach your best shot (best 5 even!) you really understand the nuance of this code sometimes better than me.

First, your question — you're right, and I'm withdrawing two claims

what do you mean by that? For a fillet surface the intersection is exactly on the boundary by construction.

You're right and I can't defend what I wrote. "A boundary hit is precisely the degenerate case for both ray-cast parity and trim assembly" was too strong. Your fillet is the counterexample: the intersection is on the boundary by construction, and finding it is the whole point of the change. Being on a boundary is not the defect.

What I actually had evidence for was much narrower — on these models, the hits that broke things happened to land at endpoints. I generalised that into a statement about boundaries in general, which the evidence didn't support. I've since found what the defect really is, and it isn't where the hit lands.

Second correction from that same comment, which I found while checking the first: I said the uv dedup lets three hits on one edge survive into the trim. That's wrong. Those three were three separate ray casts, and the dedup only runs within a single call, so it never had the opportunity to merge them and isn't at fault. I shouldn't have made the claim.

Where each of your five stands

Both commits sit directly on 70b444c3, this PR's head as it stands — nothing rebased, so they fast-forward:

git fetch https://github.com/BoykoNeov/solvespace pr1751-fallback-fixes
git cherry-pick 62d92299 f70c58ad     # or just merge FETCH_HEAD

1. The parallel guard (your #2)

The test had two holes.

It misses antiparallel. When the two directions point opposite ways d1.Dot(d2) is -1, so fabs(1.0 - d1.Dot(d2)) evaluates fabs(2.0) and nothing is rejected. The edge direction comes off the surface's control grid, which always runs in increasing u and v, while p0 -> p1 is whatever the caller had; which of the two relative orientations you get is arbitrary.

And it gates on degree where the property is geometric. deg + curve->deg == 2 admits only a pair of degree-one curves, but a Bézier whose control points are collinear is a straight line whatever its degree and whatever its weights, and the edge EdgeCurveIntersection() hands you carries whatever degree the surface has in that direction, not the degree its shape deserves.

One test closes both: the magnitude of the cross product of the two unit directions is the sine of the angle between them, which is zero for parallel and antiparallel alike. It's also the quantity that actually matters, since Vector::ClosestPointBetweenLines() divides by its square — that's why the answer is worthless in this case, the division is 0/0. And it's linear in the angle near zero where 1 - cos(angle) is quadratic, so I set the tolerance to the same angle the cosine form accepted at 10*RATPOLY_EPS, about 4.5e-4 rad, rather than reusing that constant, which against a sine would have meant a cone 4500 times narrower.

This changes nothing I can measure, and I'd rather say so than claim a fix. Meshes from 1291_1743_cube_cut_tangent_outside_still_fails_simplified.slvs, cube_cut_2.slvs and curve_curve.slvs are byte-identical with and without it, and the suite is unchanged, OpenMP on and off. On the first model the guard rejects ten line pairs, every one exactly parallel and same-facing — so the old test caught them too. And the cubic edges that used to slip past the degree gate turn out not to be straight at all: they bow 0.354 mm off a 1.41 mm chord. Both holes are real but latent on the models I have. Robustness, not behaviour.

2. The regression, which is the part that matters

boolean_tangent_crossing — the test in master from #1291 — fails on this branch. Here is why, and it is not about boundaries.

PointOnThisAndCurve() is returning the guess it was given. It stops as soon as its two points agree to within RATPOLY_EPS. Where the edge runs tangent to the line being cast, that is already true of the seed it starts from, so it converges on the first iteration and hands the seed straight back. Six of the ten fallback hits on that model are of this kind, and they aren't close calls:

Eight orders of magnitude between the two populations, so the threshold isn't a delicate one.

This is the same degeneracy your guard was written for. You had it right in the thread — "it was somehow passing the test because the lines were coincident." Your guard misses these because it asks whether a curve is straight globally, and here the curves are genuinely curved cubics that happen to run tangent to the line at the point where they meet it. Local, not global.

Why one manufactured point wrecks the model. What comes back isn't an intersection, it's the centre of whatever sub-patch AllPointsIntersectingUntrimmed() had subdivided down to, projected onto the surface. It lands 1.3e-6 to 2.5e-6 mm from the vertex that's really there — and LENGTH_EPS is 1e-6, so that's the worst distance it could have picked: too close to be a second feature, too far to be recognised as the same one. Then, in order:

1. The endpoint test in AllPointsIntersecting() would have dropped these — this is your Add cxx feature cxx_noexcept #3, and you're right that it's the place to look — but its tolerance is LENGTH_EPS/bam and it's outrun by a factor of 1.75 to 2.5.
2. MakeCopySplitAgainst() splits a trim curve twice, within 2e-8 of uv.
3. That leaves a zero-length trim edge, and the Boolean fails.

So on #3: the endpoint filter isn't missing, it's being beaten. Tightening it means picking a tolerance larger than the error of a point that shouldn't exist, which I don't think is winnable. Better not to manufacture the point.

The fix is to require, after PointOnThisAndCurve() succeeds, that the curves actually cross at the point it found — same sine test, same tolerance as the global check. Commit 2.

• boolean_tangent_crossing passes again; whole suite 264 cases, 937 checks green, OpenMP on and off, matching master.
• cube_cut_2.slvs — still fixed, mesh byte-identical to this branch. The new test never fires on it.
• 1291_1743_…simplified.slvs — still fixed, mesh byte-identical. The new test fires four times and changes nothing, so those four hits were doing no work.
• boolean_tangent_spline — fires three times, stays green.

3. A separate bug I hit on the way, worth its own issue

The zero-length trim edge in step 3 above is fatal to AssemblePolygon(), and I think that's a pre-existing hole rather than anything to do with this PR. AssembleContour() searches for a continuation edge before it tests whether the contour has closed, so an edge whose start and end are the same point can never assemble — the search for a successor fails first. And nothing culls one: CullExtraneousEdges() only removes duplicate and antiparallel pairs. So any code path that produces a degenerate trim edge takes the Boolean down, with failed: as the only symptom.

If I remove those edges by hand the Boolean assembles, but the mesh still leaks — the same vertex ends up at two positions 4e-6 mm apart and won't weld. So culling is a band-aid; the real fix is upstream, which is commit 2. But the assembler's inability to survive a degenerate edge seems worth hardening regardless.

4. The limit of my fix, and a question back to you

I've overstated things once on this thread already, so plainly: this shows the new rule breaks none of the models I have. It doesn't show no model needs a tangential hit.

The one shape it rejects is a boundary curve running tangent to the line being cast, at a point where the touch genuinely has to be found. And that is uncomfortably close to your own motivating case — so, concretely: on your fillet, does the boundary curve run tangent to the cast line at the intersection, or does it cross it? If it runs tangent, commit 2 is wrong for you and I'd want the model to work against. If it crosses — the surface is tangent but the boundary curve isn't — then the two cases are cleanly separable and I think this holds.

That's the one thing I can't answer from here, and it decides whether commit 2 is right.

5. Your #5, and an offer

The exact-curve refinement step is untouched. I wanted the regression understood before adding another change on top, and the same question above governs it — if a tangential touch is sometimes legitimate, the criterion for both places needs to be different from the one I've used.

Standing offer from before still holds: send me any patch and I'll run it against the full suite, both OpenMP settings, plus your three models, and report whatever it says.

Written by Claude Opus 5 — both this text and the code it describes; posted by @BoykoNeov.

@ruevs With the 3rd commit this PR now fixes 1291_1743_cuve_cut_tangent_out... as well as cube_cut_2 and it not longer causes a regression with 1291_cube_cut_tangnet_out...

So this fixes the same sketches as BoykoNeov # 6 without doing all the extra work. Instead a fallback is used where line/surface intersection runs into tangency issues. I'd prefer to merge this one and not that one. The other method is interesting (if a bit hackish) so I wonder how to keep it around for reference, or to test with other issues.

@claude no further work for you on this one, but I wanted to say your fix for the parallel test is broken. You used the cross product of two vectors d1 and d2, but neither of them was initialized. This was probably confusion about code from my prior version of the test assigning to those vectors, but that code was removed. Also, that test was just an early exit and didn't need to create a whole function checking for straight curve (colinear points). Your analysis was pretty good though and helped to find a proper fix.

p.s. @ruevs I checked my entire collection of sketches and found no regressions.

Written by Claude Opus 5, posted by @BoykoNeov.

Agreed — merge this one and not #6. Your version reaches the same models through
much less machinery, and you've tested it against a collection I don't have.
Nothing below is an argument for mine; it's the three things I'd want written
down before this merges.

Where the fallback can and can't reach

The two fixes attack the defect from opposite ends. Mine splits a curve wherever
the other operand's curve has a vertex sitting on it, before any surface
intersection runs, so it doesn't depend on anything converging. Yours recovers
the same split point from the failure itself. That's the better trade on these
models. Two places where the recovery can't fire, both read off the code rather
than measured, so treat them as things to watch and not as bugs I can show you:

It only runs when the iteration fails. EdgeCurveIntersection() is reached
only when PointIntersectingLine()'s loop exits without converging. A tangency
that converges to a plausible-but-wrong (u, v) returns true at the
pi.Equals(p, RATPOLY_EPS) check and never gets here.

It tries one of the four patch boundaries. The choice comes from
fabs(*u - 0.5) > fabs(*v - 0.5) on the (u, v) the failed iteration left
behind. Near a corner both are close to a boundary, and only one of them is
tested — and the guess it's choosing from is the one that just failed to
converge. If the case ever shows up, trying the other boundary before returning
false is a cheap addition.

The tolerance you weren't sure about

// I'm not sure what the angle tollerance should be here.

On 1291_1743_cube_cut_tangent_outside_still_fails_simplified.slvs the two
populations are eight orders of magnitude apart: the six hits that wreck the
model sit at sine 1e-8 between the tangents, and the four genuine ones at sine 1,
square on. LENGTH_EPS at 1e-6 lands between them with a hundredfold margin
below and everything above, so on these models it isn't a delicate choice. It's
a sine, so the number is the angle in radians — 1e-6 rad is about 0.2 arc
seconds, which is tight for anything arriving from a real solve, but the measured
gap is wide enough that it doesn't matter here.

The degree gate, in the path this code creates

deg + curve->deg == 2 admits only a pair of degree-one curves, but the edge
EdgeCurveIntersection() builds takes edge.deg = degn (or degm) — the
surface's degree in that direction, not the degree its shape deserves. A Bézier
whose control points are collinear is a straight line whatever its degree, so a
straight boundary on a cubic patch reaches PointOnThisAndCurve() with the
parallel guard switched off, in exactly the fallback the guard was written for.
Latent on everything I have: the cubic edges that got there in my traces bow
0.354 mm off a 1.41 mm chord, so they're not straight and the gate was right to
skip them. Testing the control points for collinearity instead of testing the
degree closes it if you ever want to.

One correction

you used the cross product of two vectors d1 and d2, but neither of them was
initialized

They were — IsLine(Vector *dir) writes the direction through its out-parameter
and only then returns true, and && short-circuits, so d1.Cross(d2) is reached
only when both calls wrote theirs. The diff is what makes it look wrong: it
deletes two initialised declarations and adds one bare Vector d1, d2;. No
disagreement about the outcome — your version is in and mine isn't, and that's
fine.

The offer to run any patch against the full suite still stands.

The degree gate, in the path this code creates

deg + curve->deg == 2 admits only a pair of degree-one curves, but the edge EdgeCurveIntersection() builds takes edge.deg = degn (or degm) — the surface's degree in that direction, not the degree its shape deserves. A Bézier whose control points are collinear is a straight line whatever its degree, so a straight boundary on a cubic patch reaches PointOnThisAndCurve() with the parallel guard switched off, in exactly the fallback the guard was written for. Latent on everything I have: the cubic edges that got there in my traces bow 0.354 mm off a 1.41 mm chord, so they're not straight and the gate was right to skip them. Testing the control points for collinearity instead of testing the degree closes it if you ever want to.

Ha! Claude and I had the same idea this morning. Reading Claude's check [here](https://github.com/BoykoNeov/solvespace/commits/pr1751-fallback-fixes/](https://github.com/BoykoNeov/solvespace/commit/62d92299a594faa950e50d9465fbfa7f019a9104#diff-eab1902864a572597d5255f33a6675454c1826fa88b5468dbf4b769c53127f22R181-R182)
I like it more than @phkahler 's here

So I tried to create a model that breaks "@phkahler" but not "Claude", here it is:

1291_1743_cube_cut_tangent_outside_still_fails_simplified_StraightDegree2Bezier.zip

It is a model with a straight degree 2 bezier (all control points lie on a line) that is coincident with one of the edges of the solid being cut. Unfortunately it does not behave differently, it fails the same way for both versions (@phkahler and Claude).

Interestingly it fails in a different way in the 3.2 release:

I'm out of time for now - in the next 10 days I'll only look at code and comments - no compiling, testing, debugging.

Both this and BoykoNeov#6 / #1746 behave worse than the 3.2 release for this model see here: #1743 (comment).

@ruevs I want to merge this one if you're OK with that. Then we can get over to those solver fixes.