Repository navigation
PR #1751 fallback fixes from Claude Opus 5 - #1760
ruevs wants to merge 1 commit into
Conversation
Sorry, something went wrong.
This is a combination of 2 commits. - This is the 1st commit message: Fix the parallel test in PointOnNonparallelCurve(). Two straight segments running along the same line are the case that PointOnThisAndCurve() cannot answer. If they are coincident it reports whichever point it happened to start from, and if they are merely parallel it iterates twenty times to no purpose. The test that is supposed to reject them has 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 happened to have, so which of the two relative orientations we 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 Bezier whose control points are collinear is a straight line whatever its degree and whatever its weights, and the edge that EdgeCurveIntersection() hands us carries whatever degree the surface has in that direction, not the degree its shape deserves. So add SBezier::IsLine(), which reports collinear control points and hands back the direction, and gate on that instead. One test closes both holes: 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 for antiparallel alike. It is also the quantity that matters here, since Vector::ClosestPointBetweenLines() divides by its square -- that is why the answer is worthless in this case, the division is 0/0. And it is linear in the angle near zero where 1 - cos(angle) is quadratic, so the tolerance is set to the same angle the cosine form accepted at 10*RATPOLY_EPS, about 4.5e-4 radians, rather than reusing that constant, which against a sine would have meant a cone 4500 times narrower. This changes no result I can measure, and I would rather say that plainly than claim a fix. Meshes exported from 1291_1743_cube_cut_tangent_outside_still_fails_simplified.slvs, cube_cut_2.slvs and curve_curve.slvs are byte-identical to the ones this branch produces without it, and the test suite gives exactly the same result, with OpenMP both on and off. On the first of those models the guard rejects ten line pairs, every one of them exactly parallel and same-facing, so the old test caught them too. The cubic edges that used to slip past the degree gate are not straight at all -- they bow 0.354 mm off a 1.41 mm chord, some 350000 times LENGTH_EPS -- so admitting them to the test changes nothing there either. Both holes are real but latent on the models I have, which makes this a robustness fix rather than a behaviour change. Co-Authored-By: Claude Opus 5 (1M context) <noreply@anthropic.com> - This is the commit message #2: Reject a fallback hit where the curves are tangent rather than crossing. The parallel test at the top of PointOnNonparallelCurve() is a global one: it asks whether two curves run along each other for their whole length. The same degeneracy arises at a single point, between two curves that are each genuinely curved, and there it is just as fatal. That is what breaks boolean_tangent_crossing on this branch. PointOnThisAndCurve() 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 returns that seed unchanged. Six of the ten fallback hits on boolean_tangent_crossing are of this kind, and they are not close calls: the sine of the angle between the two tangents is 1e-8, the gap the iteration is trying to close is 2e-14 to 1e-11, and the point moves by that same 1e-14 to 1e-11 before being declared converged. The other four hits meet at a sine of 1, square on, and move 1e-4 to get there. The two populations are eight orders of magnitude apart, so the threshold is not a delicate one. What comes back is therefore not an intersection but 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 is really there, and LENGTH_EPS is 1e-6, so that is the worst distance it could have picked -- too close to be a second feature, too far to be recognised as the same one. In order: the endpoint test in AllPointsIntersecting() would have dropped these, but it is outrun by 1.75 to 2.5 times; MakeCopySplitAgainst() splits a trim curve twice within 2e-8 of uv; and the zero-length trim edge that leaves can neither be assembled into a contour nor culled, because AssembleContour() looks for a continuation before it tests closure and CullExtraneousEdges() only removes duplicate and antiparallel pairs. The Boolean reports failure. So after PointOnThisAndCurve() succeeds, require that the curves really do cross at the point it found, by the same sine test and the same tolerance the global check uses. The parameters are recomputed from that point rather than threaded out of the iteration, deliberately: this is meant to be a test on the answer, not on the path taken to reach it. boolean_tangent_crossing passes again, and the whole suite is 264 cases and 937 checks green with OpenMP both on and off, matching master. The new test fires four times on 1291_1743_cube_cut_tangent_outside_still_fails_simplified.slvs and leaves its mesh byte-identical, so those four hits were doing no work; it does not fire at all on cube_cut_2.slvs, whose mesh is likewise byte-identical; and it fires three times on boolean_tangent_spline, which stays green. One limit worth stating: this says the rule breaks none of the models I have, not that no model needs a tangential hit on a boundary curve. A fillet edge lying along the line being cast, where the touch genuinely has to be found, would be rejected by it, and I have no test for that shape. Co-Authored-By: Claude Opus 5 (1M context) <noreply@anthropic.com>
|
@ruevs the comments are a little verbose, but this looks good to me. |
Sorry, something went wrong.
In theory this is better, but I don't want to merge it before I come up with a model that fails on current master (with/after your fix) but succeeds with this - thus demonstrating that this is better. It would be some straight bezier with more than two control pints that hits the check... my naive attempt last time failed (I did not put a break point on the check and try to think and come up with a model that will hit it) |
Sorry, something went wrong.
I'm not sure you will find one. I think the first check might be redundant. If the line and curve are parallel it should fail the second test. |
Sorry, something went wrong.
|
Written by Claude Fable 5.1 — both this text and the measurements; posted by @BoykoNeov. @ruevs — you asked for a model where a straight Bézier with more than two control points reaches the check, and @phkahler suspected none would show a difference. Measured, on master 952c11c0 and on this PR's commit cherry-picked onto it, Debug, with a print at every call of PointOnNonparallelCurve() from EdgeCurveIntersection() and one in each of its reject branches. Where such edges come from. Not fonts, in practice — TrueType puts straight sides in as line segments. Of the bundled Bitstream Vera Sans' 1327 quadratic segments exactly one has collinear control points (in ~); Arial, Calibri, Segoe UI, Times, Verdana, Tahoma have 1, 2, 0, 3, 1, 5. The direct source is a spline drawn with its control points on a line, and the natural one is a lathe: every seam of a cylinder or cone lathed from a straight spline is a straight degree-3 edge. Either way nothing reduces the degree, and that is what makes it matter: a flat face bounded by lines is a (1,1) surface and takes the closed-form plane path, the same face bounded by a straight cubic is (3,1) and goes through PointIntersectingLine() and the fallback. A model that reaches the check. A tube lathed about y, outer profile a cubic with control points (8,−5), (8,−2), (8,2), (8,5); a triangular prism straddling the wall with its ridge on the seam ruling x = 8, z = 0. Casting the ridge against the cylinder patches, the line is parallel to every tangent plane, PointIntersectingLine() breaks out as parallel, and the fallback tries the seam edge: degree 3, IsLine() true, sine 0 at that seam and ~1e-10 at the other three. 121 times in one Boolean.
The 88 are the seam the ridge is coincident with: the iteration converges at its seed and the tangents are parallel. The 33 are the other three seams, offset-parallel: ClosestPointBetweenLines() divides 0 by 0, the parameters go NaN, and twenty iterations later it gives up. So every pair this PR's global test rejects, master's local test (or the NaN) rejects one step later. Same on the difference variant, on a flat variant (extruded straight cubic — there the flat (3,1) face is never subdivided, the seed sits at its centre, and the boundary choice is a coin flip that lands on the degree-1 vertical edge: 10 hits, all 1+1), and on six variants with the ridge tilted by 1e-7 to 1e-2 rad. @phkahler is right: for straight edges the first test is redundant with the second. What it buys is skipping twenty iterations on NaN per offset-parallel pair, and the guard now matching what it claims to test — nothing visible. Where they could differ is the tolerance: 4.5e-4 on the sine here, LENGTH_EPS = 1e-6 in the local test. A pair of straight edges between about 0.0001° and 0.026° apart would be rejected here and accepted on master, and master would then compute a real crossing of two lines. Whether a trim ever needs it is model-dependent, and I could not reach that band: with the ridge tilted up to 1e-3 rad the Newton step converges and the fallback is never entered for it; at 1e-2 it is, sine 0.01, both accept. Reading, not measurement — but note the only possible difference runs against this PR, not for it. The fixture does fail on master — for a reason this PR doesn't touch, so I'd rather say so than let it pass as a demonstration. All four cubic variants leave naked edges; the line controls don't; volumes are exact either way. On the flat model the naked edges are the ridge: one segment on the prism's face, four on the extruded face, split at x = 5.09375, 10, 14.90625 — the cubic's t = ¼, ½, ¾. IntersectAgainst()'s plane-against-extrusion branch projects the profile onto the plane and adds it as an exact degree-3 curve, MakePwlInto() forces max_dt = 0.25 above degree 1, and nothing notices the curve is straight; the coincident degree-1 edge gets one segment, and the two polylines of the same line don't match. On the lathe it is the seam split at its parametric midpoint against the ridge whole. A straightness test in MakePwlInto(), or degree reduction of a collinear spline at sketch time, would fix it. Separate issue if you want one. So: no model that fails on master and passes here, as far as I can find, and for straight edges I don't think one exists. Your call whether that reads as "merge, it's the test the comment describes" or "drop the first test altogether". Fixtures, generators and logs on request. |
Sorry, something went wrong.
From here #1751 (comment) squashed into one commit and rebased on master after merging #1751.
Original text:
First, your question — you're right, and I'm withdrawing two claims
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:
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:
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.
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.