-
Notifications
You must be signed in to change notification settings - Fork 1.2k
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Failing boolean operation with near-collinear lines #887
Comments
And here the isolated lines, with some logging of |
This is just an idea, but it might work. Right now when checking for overlaps, we permit a tolerance of
Or in other words, we create a fat line with the width 2*epsilon for curve 1 and check if the handles of curve 1 and the whole curve 2 is within this fat line. |
That's an interesting proposal! But just to be clear, I wasn't speaking about the overlap checks yet, just the current removal that happens through But indeed, right now no overlaps are found on these two curves: |
...And as stated in #874, in the future this removal shouldn't be handled by |
I think that we should not change Regarding |
Yeah, I agree. I've made some first tests and it turns out it's rather easy to get |
@iconexperience check here, I implemented your suggestion and it works like a charm: 0d172a7#diff-6393c249dbbb25dc0e510bd9d91b268dR1875 I thought I would have to modify the curve values when deciding that they are straight (projecting them onto the line they are tested against), but it turns out at least in this example here that's not required, due to the tolerances in the |
Nice. Here is my implementation just for comparison: /**
* Code to detect overlaps of intersecting based on work by
* @iconexperience: https://github.com/paperjs/paper.js/issues/648
*/
getOverlaps: function(v1, v2) {
var abs = Math.abs,
timeEpsilon = /*#=*/Numerical.CURVETIME_EPSILON,
geomEpsilon = /*#=*/Numerical.GEOMETRIC_EPSILON,
straight1 = Curve.isStraight(v1),
straight2 = Curve.isStraight(v2),
straight = straight1 && straight2;
function getEndDistSquared(v) {
var x = v[6] - v[0],
y = v[7] - v[1];
return x * x + y * y;
}
var flip = getEndDistSquared(v1) < getEndDistSquared(v2),
l1 = flip ? v2 : v1,
l2 = flip ? v1 : v2,
line = new Line(l1[0], l1[1], l1[6], l1[7]);
var straightOverlap = line.getDistance(new Point(l1[2], l1[3])) < geomEpsilon &&
line.getDistance(new Point(l1[4], l1[5])) < geomEpsilon &&
line.getDistance(new Point(l2[0], l2[1])) < geomEpsilon &&
line.getDistance(new Point(l2[2], l2[3])) < geomEpsilon &&
line.getDistance(new Point(l2[4], l2[5])) < geomEpsilon &&
line.getDistance(new Point(l2[6], l2[7])) < geomEpsilon;
if ((straight1 || straight2) && !straightOverlap)
return null;
var v = [v1, v2],
pairs = [];
// Iterate through all end points: First p1 and p2 of curve 1,
// then p1 and p2 of curve 2.
for (var i = 0, t1 = 0;
i < 2 && pairs.length < 2;
i += t1 === 0 ? 0 : 1, t1 = t1 ^ 1) {
var t2 = Curve.getParameterOf(v[i ^ 1], new Point(
v[i][t1 === 0 ? 0 : 6],
v[i][t1 === 0 ? 1 : 7]));
if (t2 != null) { // If point is on curve
var pair = i === 0 ? [t1, t2] : [t2, t1];
// Filter out tiny overlaps
// TODO: Compare distance of points instead of curve time?
if (pairs.length === 0 ||
abs(pair[0] - pairs[0][0]) > timeEpsilon &&
abs(pair[1] - pairs[0][1]) > timeEpsilon)
pairs.push(pair);
}
// If we checked 3 points but found no match,
// curves cannot overlap.
if (i === 1 && pairs.length === 0)
break;
}
if (pairs.length !== 2) {
pairs = null;
} else if (!straightOverlap) {
// Straight pairs don't need further checks. If we found
// 2 pairs, the end points on v1 & v2 should be the same.
var o1 = Curve.getPart(v1, pairs[0][0], pairs[1][0]),
o2 = Curve.getPart(v2, pairs[0][1], pairs[1][1]);
// Check if handles of the overlapping curves are the same too.
if (abs(o2[2] - o1[2]) > geomEpsilon ||
abs(o2[3] - o1[3]) > geomEpsilon ||
abs(o2[4] - o1[4]) > geomEpsilon ||
abs(o2[5] - o1[5]) > geomEpsilon)
pairs = null;
}
return pairs;
} |
Very similar, but yours is a little bit cleverer, doing the handles check only on non-straight curves. |
|
Yes I agree : ) As for the comments, does this cover it? a7fc04a |
Two tiny suggestions:
|
Yes, that's better. I'm getting sluggish : ) |
That was quite a big change in a very short time :) Did this actually solve the last failing unit test case? |
No not yet, but it sets the base for it. With this in place, the "self-overlaps" get properly detected in the example in #887 (comment). What's left to do is to implement their removal, as outlined in #874. And thanks to all the boolean unit tests that cover many of the known edge cases now, I can now much more confidently change things in such a way. |
I also finally understood my hack for 'adjusted' winding contributions last evening, when realizing that these 'adjusted' numbers were only in use anymore when picking the starting segment. And it turned out that their sole use was to avoid segments that are part of overlaps as starting points : ) So that lead to the nice simplifications in 4a10fe3#diff-83b0f841b43dce90324008de0d976e25R593 I feel more and more confident about understanding all aspects of the boolean code now, including my own hacks that are nearly gone now. |
This all sounds very nice. Do you want me to do anything at the moment? I am a bit packed with other things, but will keep listening. |
No I think we're nearly there. The ball is in my court now : ) |
It looks rather simple in the end, but to remove overlap range segments first and then perform tracePath(), all based on the same set of found crossings and overlaps was a daunting task, due to path mutation. |
And it's so nice to finally have decent boolean operation tests in place that I trust! |
Congratulations! I have my automated test up and running, and so far not problems were found. Super cool! |
So I just did a quick performance comparison, and have good news: I could not measure any slow-downs resulting from 5a16d0c! That's really great, and not what I expected. It's solid code, all through! |
After 4a10fe3, this is the last failing unit test in the test suite:
Sketch
I think it boils down to the two lines running down and up in the inside of the red shape being almost collinear, but having handles in the range of -1e-8 to 1e-10, leading to
isStraight()
returningfalse
, and henceisCollinear()
too. I think this also relates to #838, but am not quite sure how to best handle this. @iconexperience, what do you think?The text was updated successfully, but these errors were encountered: