Curve.isStraight() return false with straight line with straight handle

[naan]

In this change, Curve.isStraight uses handle point rather control point to get distance from Line(p1, p2) which I think some case doesn't work.

Here's Sketch

The following code getting distance h1 / h2 seems wrong to me. Shouldn't this to be comparing with control point (point+handleIn/Out) instead of handleIn/Out?

            } else if (l.getDistance(h1) < epsilon
                    && l.getDistance(h2) < epsilon) {

I'm testing on develop branch.

[lehni]

It's measuring the absolute handle, meaning point1 + handle1 / point2 + handle2, so this shouldn't be wrong… I will look into it.

[lehni]

Ha, you're right! I am assuming absolute positions there, but they are vectors at this point. Great find! : )

[lehni]

Fixing this is easy, but it does produce a row of failing tests due to this recent change here:

d204175

@iconexperience it now finds much more intersections in situations where paths almost overlap, as it falls back onto the line-line more often. I think if we manage to get overlap detection working better, than these should go away... And it actually helps in my situations with my path offsetting experiments, so it does seem to be the right step. What do you think?

[iconexperience]

This is quite a discovery. But I am wondering if the conditions for a curve being straight should not be more strict. Look at this example:

If the blue circles have a radius of epsilon this would count as a straight curve. Is this really what we want? Maybe if we introduced a collinearity condition, everything would be fine.

Do you remember why the code was changed?

[lehni]

We used to check for collinearity only, see #1066 / 803dfb6, but that has caused issues too, as described in the issue. We could include additional collinearity checks again. I will create a separate branch for this, where you can see the unit tests failing also.

[lehni]

@iconexperience I've pushed the code now to https://github.com/paperjs/paper.js/tree/is-straight (see bad4d02)

I included a hack that prevents the unit tests from failing, see here:

bad4d02#diff-6393c249dbbb25dc0e510bd9d91b268dR1771

The local function hasNoHandles() is used instead of Curve.isStraight() as soon as we are in the recursive call tree, which is a much stricter check for straight lines. This prevents the new issues. If you switch to always using Curve.isStraight(), by changing...

check = recursion ? hasNoHandles : Curve.isStraight,

...to...

check = Curve.isStraight,

...you will see the error in effect in the unit tests.

I have introduced an optional 2nd epsilon argument for Curve.isStraight(), and if you provide Numerical.EPSILON instead of Numerical.GEOMETRIC_EPSILON, then things are bit better, but still we get many failing tests.

This should serve as good base for further testing.

[lehni]

Some more insight:

• by always using Curve.isStraight() there, I get 31 failing tests.
• if I reduce the epsilon as described, I get 21 failing tests.
• if I add collinearity tests back as described, I get 10 failing tests.

To test for collinearity as well in Curve.isStraight(), change this line...

            } else if (l.getDistance(p1.add(h1)) < e
                    && l.getDistance(p2.add(h2)) < e) {

...to...

            } else if (l.getDistance(p1.add(h1)) < e
                    && l.getDistance(p2.add(h2)) < e
                    && h1.isCollinear(v) && h2.isCollinear(v)) {

[lehni]

The remaining issues then all stem from this sketch here by you, @iconexperience:
#1073 (comment)

We used to find 4 intersections, now it finds 7...

[lehni]

I should add that all the remaining failing tests, regardless of the versions described in #1269 (comment), are only occurring with almost overlapping curves. Without the collinearity checks, but with reduced epsilon, I get 31 intersections instead of 4 in one test. This may not be a bad thing actually, it just means we should improve how we handle overlaps probably...

What I find interesting is that when I use this version that produces the most intersections, all my remaining issues in my path offsetting experiments go away (situations such as #1263). This doesn't mean it's right, but maybe it is...

[iconexperience]

I am still trying to catch up, but just one remark: Checking for handles should never return true after the first recursion, because the handles will never be zero after splitting the curve (onyl for extremely short curves). Eventually the will be located at 1/3 and 2/3 after some more splitting. So with the hack you have basically gone back to the old algorithm, only with a smaller limit to calls.

[lehni]

That-s a very interesting observation! The hack I just implemented to preserve previous behavior, since this is basically more or less what the wrong definition of isStraight() did. But what you just pointed out means that the only difference between the old algorithm and my addition was that once sub-divided curves where short enough, they were handled by line-line / line-curve, and this was enough for quite a few edge cases to disappear in my offsetting experiments.

With @naan discovering this issue here, we found out about this mistake with rather good timing. But now we have a whole lot of new question marks : )

@hkrish recently mentioned his approach of handling overlaps to me, I will find out if this is something that may help us prevent these edge cases.

But I would also like to roll out v0.10.3 today, so I need to think about how to fix this temporarily (by reverting back to previous behavior probably).

[lehni]

@iconexperience one remark: we don't have smaller call limits anymore, we're back to the old ones.

[iconexperience]

@lehni I notices the call limits change just after posting my comment. And yes, I think the best would be to have a temporary fix. This is quite a big discovery and should be investigated closely.

[lehni]

I just tried this out, to see if it makes any difference, basically only checking straight curves on the first call of addCurveIntersections():

straight1 = abort || !recursion && Curve.isStraight(v1, epsilon),
straight2 = abort || !recursion && Curve.isStraight(v2, epsilon);

and this creates a new issue: In the overlap edge case #1239 in the unit tests, one intersection is not found anymore. This used to be found when the fat-line epsilon was 1e-9, now it's 1e-12 along with the new handling of "straight-enough" curves, which causes the same intersection to be found also, and adding this solved many edge cases in my offsetting code. Note that this is not a valid confirmation in itself; until the cases are actually analyzed it could just be luck, but it's an indication nonetheless.

This basically means that the case where curves are so small after many subdivisions that it's ok to treat it as a line does indeed solve issues.

[lehni]

Interesting... If I reduce the maximum for recursion from 48 to 40, then almost all tests succeed again except for one.

[lehni]

@iconexperience look at 8461d8d, with this everything works again, and the correct isStraight() is now actually in use in the algorithm.

The only problem I am seeing now is that due to the added collinearity checks which solved the breaking cases, I am back to seeing issues in my offsetting experiments. But that just needs more investigation now, and thanks to this issue here I now have a hint.

[naan]

glad I found a good one. Nice work always!