Problem with multiple paths exclude

[tomashanacek]

Actual result:

http://sketch.paperjs.org/#S/lZTLboMwEEV/xWKRgIQIGAoNVVf5gapdhiwcMykojh3ZkFaN8u81D+epJpQFYHNnPPfMiL3FyQas1PpYQ0ULy7WoyJv1ZIJUQbbgZ3xHZP+OXhGHL/RGqsJ7B1oR/snA3mcc6WsrSl6laB76kYswjhdut6/KH2i28bOL9M1sl1yB1PoVYQoyfnBeMp5xc2yQ8e55dqS9v4hpIzqRR/LcbmVNDTYOQu9J1xBOnT81URK3muSOJgniJotOdidPPHVREp0LKBMKcl14JWswruCbsjoHA3J0tClBGZMzsdmKmued2Q4TLUqWS+CaYBfqqXpZSUIru8vguH2qqw++Y0ivSsZmggmZovGSEboe3+DGffF4UIeDRHc4OLXSdNjXKPBT8LDDhkVrfXSsQC/xMBJN4JVdbDjg04dG9phCm0zCRuzAds6hhD2UcNjYB3q+g+gWCtZj7+P/QMEGiq5gGA18RSM0NMILGnjITLTpTjz0L2Epgaxbn8pK54vDLw==

Expected result:

[lehni]

@hkrish, I have started looking into this one, and it looks like segments are getting dropped that are not even involved in intersections... Would you have time to analyze this one? I don't know where to start looking.

[lehni]

For some reason this actually got worse with the generally improved boolean code... It used to look like this:

Now it looks like this:

[lehni]

Here a simplified version that highlights the first error. I imagine the other errors are an accumulation of the same thing going wrong: Segments that are not directly involved in intersections appear to get dropped:

var shape0 = new Path.Rectangle({
    point: [304, 226],
    size: [328, 328]
});

var shape1 = new Path({
    segments: [[213.5, 239], [476.5, 279], [716, 233.5], [469, 74]],
    closed: true
});

var res1 = new CompoundPath({
    children: [shape0.subtract(shape1), shape1.subtract(shape0)],
    fillColor: 'black'
});

var shape2 = new Path.Rectangle({
    point: [174, 128],
    size: [309, 251],
    strokeColor: 'yellow'
});

var res = res1.subtract(shape2);
res.fillColor = 'red';

Resulting in:

Instead of:

[lehni]

Update: Forget about this, it's not the same issues, as outlined by @hkrish below:

And here another, even simple example that fails:

var shape0 = new Path.Rectangle({
    point: [304, 226],
    size: [328, 328]
});

var shape1 = new Path({
    segments: [[213.5, 239], [476.5, 279], [716, 233.5], [469, 74]],
    closed: true
});

var shape2 = new CompoundPath({
    children: [shape0, shape1],
    fillColor: 'black'
});

var shape3 = new Path.Rectangle({
    point: [174, 128],
    size: [309, 251],
    strokeColor: 'yellow'
});

var res = shape2.subtract(shape3);
res.fillColor = 'red';

[hkrish]

@lehni Your last example here and the one before if not equivalent. The last example has a compound path with two overlapping paths. which technically cannot be supported by boolean because the compoundpath effectively is self-intersecting! It may be rendered here identical to your previous example, but what matters to boolean code is the path topology and they are very different.

I can't reproduce the bug in example before last, in sketch.

[lehni]

Yeah this one's not happening in Sketch, which is running v0.9.21, but others like it further down in the original code... But it's happening in the new code base, so you need to run it locally...

[lehni]

But I think you're hinting at the cause of the problem: self intersecting compound paths. Even the original example is creating them:

res1 = new CompoundPath({
    children: [shape0.subtract(shape1), shape1.subtract(shape0)],
    fillColor: 'black',
    visible: true
});

So I guess we need to first check for and resolve self intersection on compound paths before performing operations?

[lehni]

Oh forget that. Those are not self-intersecting... But yeah, the new code is now dropping / shifting those segments and I have no clue why. This is not once happening in the boolean-test code, or any other tests I have.

[lehni]

Here's a link with the above example failing with the latest version of paper.js:

https://dl.dropboxusercontent.com/u/85606/paper.js/bugs/541/541.html

[hkrish]

Also the first example is interesting. The bugs seems to be scattered in multiple places. I have a fixed version in code.

I think it is all about what different methods and constructors expect as inputs and failing silently. (We do badly need a good type system! :)) The case on linenumber 39 (sketch below) , ideally should produce a non-self-intersecting subtracted result. This is the only bug related to boolean code in this issue I think.

http://sketch.paperjs.org/#S/rVbfj+I2EP5XpjwcicTlwNlbelz3gV2p6kmntrrrQ6XNVjLJQHIYO7IdKF3t/96x84PAwQqp5WEJnvFkvu+bz97ngeQbHMwGX9do03wwGqQqc7/fvQOT8xLHidxy3TzDHUjcwe/c5tEXTC2XK4HBcyKBPqUqpJ3BYzy+GQFjt0+jet0U/6BbZj+OgP60y4U0qCnf6gqB3vb4C9fFE3yrjIWl0rAtTMVFYQq5iuALbtQWMxDcok7kS/gxkYlse5wksv7u9Rc8ty9YcmHQ76iTIp5lgU9zDQdsEkfvqeH4Q3gx52Z663Omr+RMJ7euChV7pc7thxFMb/oJqVCGgN15HlpU+Hcqqgxb1t90MDWaFuSD2pSqklkNtuY0zQuRaZREd701MtXCap7aoK4QjppSJ4Fx2MqyLIR4UELpGQwXgqfrYUN3U1B7JYKwA3BYOAjCmii7amAmUxqYyWEy2oEZE1ns/eTcwJxpVmM27E9Gj0bP2puuNYrQCrvAI0VPqHTbT/hiLZHsEHBpnsamwjkmKUQdgn9oBv4z2qGBhUa+Bpsj8AXRCSkXAjK1k1Ei59Tp2R4SeU+hs32Aw//T27fw86c/Z/BHXhhYoURN/jHAwaBYEqFkJkOqkMWgJPhUz7FyH1WysF7S+07ej/2ef1U7mAOXGdAGrhFKrUrUkDZcumIm8jseeksUl4bkSy35W0mxpz5wY8Aq2Cm9hl1BOU4H8wOhpvIO3jxqpYiMKFLf1lxrvo/opVbZfYlRWZk84mUp9oHfNqK+um2ht80luY+1rne/6gQSb94benrR4YdX6cQh7MghjgElMBJqFSSD+ZIUqMfzr0bHGSSDkePzGwkTkZ7FFj/zPeoDnt5p+dua70GSGjusCc351j1hJ4UXFgQubSJfq/o4foo6xMQVQa5w2Dd13ACKr7sFJnTcT26+NzWjW2DMrjT1SiPKI1v3PM1aT8c+crWZ2YmR4tbM8ZGJ2HVm7vviE/ANrJTzE8201XvvaEM3LNB0asXTHLhpLO4uOY/GFKrG1h8O32c3+RteBstKkm5KBjx85u7eSNe7wuCdvziID1tpCTwqzEMbCsKXMOzOj+9h986PU+j/2X8n9ov/L/u5MTjy36nf4mM/stMLqneE4Rb13uZOLpOrSmSwQJpIUDojZxyd0nNykjfYJW9dMDYjY3/1bV1h7ETS/1/+JvAuMoPZ49PLvw==

[lehni]

And here the latest version of sketch, for immediate simpler testing:

https://dl.dropboxusercontent.com/u/85606/paper.js/sketch/index.html#S/jVDNboMwDH6VKBdaKUIQWlipduoLTNsROKTBK4g0qZKwaqv67jN0VB27LIdItj/7+7lQLY5Ac/rWgZcNZXRvQXQn02rvaF5UjEpTD4APYYlrxAki8kw0nMmL8E34CtILfVCwuJSa4Bs3c1Ik0YoRztOK3fqu/YKhzZ8Ywa8q9XW5LXWp73fjh7vTNQeHI6AS3Cx4nIRrvJlsKkaKVZaOVTZWWZwOEwSMs3TDSLaqJm6pjIM6J9728IvXgptYd+Z4Mr2uH9ll06ragkb2m/PQ9XtvhfSLm+Il+5E+G0TLifq9VWpnlLE5CfZKyC74a5z/K9A4w0BjTG4WaIRe+Tq+t701HUyUn6CUOQdz00g4WJ+p5gMG++FdNOICC3Wwpddv

[lehni]

You see, the example you just posted produces a ton of weird errors with the new code base:

https://dl.dropboxusercontent.com/u/85606/paper.js/sketch/index.html#S/rVbfj+I2EP5XpjwcicTlwNlbelz3gV2p6kmntrrrQ6XNVjLJQHIYO7IdKF3t/96x84PAwQqp5WEJnvFkvu+bz97ngeQbHMwGX9do03wwGqQqc7/fvQOT8xLHidxy3TzDHUjcwe/c5tEXTC2XK4HBcyKBPqUqpJ3BYzy+GQFjt0+jet0U/6BbZj+OgP60y4U0qCnf6gqB3vb4C9fFE3yrjIWl0rAtTMVFYQq5iuALbtQWMxDcok7kS/gxkYlse5wksv7u9Rc8ty9YcmHQ76iTIp5lgU9zDQdsEkfvqeH4Q3gx52Z663Omr+RMJ7euChV7pc7thxFMb/oJqVCGgN15HlpU+Hcqqgxb1t90MDWaFuSD2pSqklkNtuY0zQuRaZREd701MtXCap7aoK4QjppSJ4Fx2MqyLIR4UELpGQwXgqfrYUN3U1B7JYKwA3BYOAjCmii7amAmUxqYyWEy2oEZE1ns/eTcwJxpVmM27E9Gj0bP2puuNYrQCrvAI0VPqHTbT/hiLZHsEHBpnsamwjkmKUQdgn9oBv4z2qGBhUa+Bpsj8AXRCSkXAjK1k1Ei59Tp2R4SeU+hs32Aw//T27fw86c/Z/BHXhhYoURN/jHAwaBYEqFkJkOqkMWgJPhUz7FyH1WysF7S+07ej/2ef1U7mAOXGdAGrhFKrUrUkDZcumIm8jseeksUl4bkSy35W0mxpz5wY8Aq2Cm9hl1BOU4H8wOhpvIO3jxqpYiMKFLf1lxrvo/opVbZfYlRWZk84mUp9oHfNqK+um2ht80luY+1rne/6gQSb94benrR4YdX6cQh7MghjgElMBJqFSSD+ZIUqMfzr0bHGSSDkePzGwkTkZ7FFj/zPeoDnt5p+dua70GSGjusCc351j1hJ4UXFgQubSJfq/o4foo6xMQVQa5w2Dd13ACKr7sFJnTcT26+NzWjW2DMrjT1SiPKI1v3PM1aT8c+crWZ2YmR4tbM8ZGJ2HVm7vviE/ANrJTzE8201XvvaEM3LNB0asXTHLhpLO4uOY/GFKrG1h8O32c3+RteBstKkm5KBjx85u7eSNe7wuCdvziID1tpCTwqzEMbCsKXMOzOj+9h986PU+j/2X8n9ov/L/u5MTjy36nf4mM/stMLqneE4Rb13uZOLpOrSmSwQJpIUDojZxyd0nNykjfYJW9dMDYjY3/1bV1h7ETS/1/+JvAuMoPZ49PLvw==

[hkrish]

Ok. I will look at this later. The new code base seems to have changed a bit since I last looked at it.

[lehni]

Yeah I have merged in the improved cubic solver, reduced tolerance and epsilon, merged and fixed your other changes from the boolean-operations branch (then called cubic-solver), and spent a lot of work on fixing bugs and addressing edge cases lately. I will go back in time to see when this issue emerged, but I have a feeling it's linked to better precision somehow.

[lehni]

The issue appears with the commit where I switched over to the new root finder, before applying all the other changes: cdfd21ddd3ac50f2eb35618d6d9a1efa7c00cffd

[hkrish]

Interesting.

We can possibly step though the boolean code (just for the initial subtraction), and isolate where the issue is happening due to the solvecubic (comparing the return data from new and old solve cubic).

[lehni]

But perhaps more importantly, it seems to appear with this merging commit here on now gone the boolean-operations branch: 878be7962e4f0dcf658f51aa6e916a116a3bb822

[lehni]

Unfortunately there were almost 7 months in between... So many things have changed. Reviewing those things now, stay tuned.

[hkrish]

Yup. A breaking merge is the worst kind of headache.

[lehni]

Ha, I am sure there are other worst headaches : )

[lehni]

Alright, I went through all changes, and undid one after the other in the version of the library that is in use on the dropbox-sketch link in my comment above. I undid every single one of them, except the new cubic solver. And the issue is still happening in the same way, plus you now see the effect of the Math.random() call again, and the results are different each time (I fixed that in the meantime). So it is because of different results from the solver, and you are right, we should compare those.

[lehni]

And here we go. The formulas producing different roots are below.

@hkrish, time for you to perform your magic : )

a = 2.2737367544323206*10^-13; b = -3.410605131648481*10^-13; c = 0; d = 5.684341886080802*10^-14; // old: [0.4999999999999998] new: []
a = -2.2737367544323206*10^-13; b = 3.410605131648481*10^-13; c = 0; d = -1.1368683772161603*10^-13; // old: [1] new: []
a = -2.8421709430404007*10^-13; b = 4.263256414560601*10^-13; c = 0; d = 0; // old: [-0] new: []
a = 2.8421709430404007*10^-13; b = -4.263256414560601*10^-13; c = 0; d = 1.4210854715202004*10^-13; // old: [0.999999985170896] new: []

[iconexperience]

Either I am doing something very wrong or something is broken in the CompoundPath constructor: Can somebody please take a look at this very simple example and confirm that the Compound path should be visible, black and the same shape as the yellow rectangle:

http://sketch.paperjs.org/#S/jVFLbsMgEL0KYlGnkuXYzc5VV7lA1SzjLDAe18iTwQLc/JS7F7DdVl0FJARPo/fjxkkcgZd814OTHU+51E14r9fMdmKAvKIvYeY7e2MEJ/YuXJd9gHSCPhFWt4qYX4NW5Eq2f8nzlPnjkE64VVfw8CbAm19YkQXj51uBFiq6P79W9EereEir+Ec6a0W4eESr1hpDrClfZsfaGSHdavIQ5uJE1irErUZt/GxyAUR9SiKJ7wnOEscGlo6e5gAVGbBLjK0+DnqkJsRZQshOYWOAvOEosrj90SpZUqOQfTJbDnxZOyJedoC+Emg8uzMjRCdh+/+rDYg+9mN5uT/cvwE=

[lehni]

Ha, strange... It seems that the item bool0 doesn't get moved over... Will have to investigate. Could you create a separate issue for this?

[iconexperience]

Created this as new issue https://github.com/paperjs/paper.js/issues/614

[lehni]

@hkrish just to make sure, you've seen this comment here, right? https://github.com/paperjs/paper.js/issues/541#issuecomment-68778779

[hkrish]

Yup. I will get back by end of this week :)

On 2015Jan06, at 11:41 pm, Jürg Lehni notifications@github.com wrote:

@hkrish https://github.com/hkrish just to make sure, you've seen this comment here, right? #541 (comment) https://github.com/paperjs/paper.js/issues/541#issuecomment-68778779 — Reply to this email directly or view it on GitHub https://github.com/paperjs/paper.js/issues/541#issuecomment-68948145.

[lehni]

Cool, and no rush : ) Just wanted to make sure you got it.

[hkrish]

@lehni I cant seem to find the bug. The new cubic solver returns this

Which is the correct values (I also checked with numpy). Are you sure you are calling the new solver?

[lehni]

Oh damn, I got the roots arrays confused... So the new solver finds more solutions, and that's what's causing the error. You can see it in action here now, including the logging to the browser console (not the sketch console). So it seems that finding all the solutions now is causing these issues... What to do now?

https://dl.dropboxusercontent.com/u/85606/paper.js/sketch/index.html#S/jVDNboMwDH6VKBdaKUIQWlipduoLTNsROKTBK4g0qZKwaqv67jN0VB27LIdItj/7+7lQLY5Ac/rWgZcNZXRvQXQn02rvaF5UjEpTD4APYYlrxAki8kw0nMmL8E34CtILfVCwuJSa4Bs3c1Ik0YoRztOK3fqu/YKhzZ8Ywa8q9XW5LXWp73fjh7vTNQeHI6AS3Cx4nIRrvJlsKkaKVZaOVTZWWZwOEwSMs3TDSLaqJm6pjIM6J9728IvXgptYd+Z4Mr2uH9ll06ragkb2m/PQ9XtvhfSLm+Il+5E+G0TLifq9VWpnlLE5CfZKyC74a5z/K9A4w0BjTG4WaIRe+Tq+t701HUyUn6CUOQdz00g4WJ+p5gMG++FdNOICC3Wwpddv

[lehni]

To clarify: Here is how the above output should have looked like. But the code is using the solutions of the new solver, and that's why it is now failing.

a = 2.2737367544323206*10^-13; b = -3.410605131648481*10^-13; c = 0; d = 5.684341886080802*10^-14; // old:  [] new: [0.4999999999999998]
a = -2.2737367544323206*10^-13; b = 3.410605131648481*10^-13; c = 0; d = -1.1368683772161603*10^-13; // old: [] new: [1]
a = -2.8421709430404007*10^-13; b = 4.263256414560601*10^-13; c = 0; d = 0; // old: [] new: [-0]
a = 2.8421709430404007*10^-13; b = -4.263256414560601*10^-13; c = 0; d = 1.4210854715202004*10^-13; // old: [] new: [0.999999985170896]

[lehni]

@hkrish, I'm on to something, probably best if you wait with further inquiries until I post more results.

[lehni]

@hkrish: Alright, so I wasn't logging all crucial data, and here is where things go wrong:

a = 2.2737367544323206*10^-13; b = -3.410605131648481*10^-13; c = 0; d = 5.684341886080802*10^-14; // old: res = -1, roots =  [] new: res = 1, roots = [0.4999999999999998]

The old solver was returning -1 to indicate infinite solutions, while the new solver returns 0.4999~ as the one intersection. I haven't looked yet into if the solutions are indeed infinite, but the problem then is that with the new solver, Curve.getParameterOf() does not find the curve time parameter for the given intersection point, hence resulting in the lost points in the resulting shape.

[hkrish]

Then there may be an accuracy issue with how getParameterOf works. (Haven't stepped through this to find out exactly where.)

Because there is definitely a root at 0.5 (within [0, 1]). Here is numpy plot of the cubic.

The only time a cubic can have infinitely many solutions is when the cubic represents a straight line and lies on the x axis.

[lehni]

getParameterOf() is rather trivial. It searches the solutions for the point's x-coordinate on the x-cubic, and the y-coordinate on the y-cubic. Then it iterates through all solutions and sees if there's a match with the same curve time parameter on both (allowing a difference of Numerical.TOLERANCE). The problem here is that while 0.5 is found for x, there's a different solution for the y value:

x: [0.4999999999999998]
y: [0.5541722068563936]

And I guess before, the x-cubic was considered a line due to different tolerances and the fact that all its factors are very small.

[hkrish]

Can you please post the bezier coefficients of the curve represented by a = 2.2737367544323206_10^-13; b = -3.410605131648481_10^-13; c = 0; d = 5.684341886080802*10^-14;?

On 2015Jan10, at 6:13 pm, Jürg Lehni notifications@github.com wrote:

getParameterOf() is rather trivial. It searches the solutions for the point's x-coordinate on the x-cubic, and the y-coordinate on the y-cubic. Then it iterates through all solutions and sees if there's a match with the same curve time parameter on both (allowing a difference of Numerical.TOLERANCE). The problem here is that while 0.5 is found for x, there's a different solution for the y value:

x: [0.4999999999999998] y: [0.5541722068563936]

And I guess before, the x-cubic was considered a line due to different tolerances and the fact that all its factors are very small.

— Reply to this email directly or view it on GitHub https://github.com/paperjs/paper.js/issues/541#issuecomment-69463235.

[lehni]

And here the values of the y-cubic that result in the 0.5541722068563936 solution: a = 602.4714828897338; b = -903.7072243346007; c = 0; d = 175

[lehni]

Yes, here its array notation:

[304, 554, 304, 554, 304.0000000000001, 252.7642585551331, 304.0000000000001, 252.7642585551331]

[lehni]

And the intersection point for which it is trying to find the curve time parameter is:

[304.00000000000006, 379]

[lehni]

I can see how that tiny movement in x direction (from 0.0 to 0.0000000000001) can cause huge imprecisions.... But how to correctly handle this?

[hkrish]

Can I have the stack trace as well, when you pause at the solveCubic routine with these values. I just need to know where are we coming from as well.

On 2015Jan10, at 6:18 pm, Jürg Lehni notifications@github.com wrote:

And the found point is:

[304.00000000000006, 379] — Reply to this email directly or view it on GitHub https://github.com/paperjs/paper.js/issues/541#issuecomment-69463385.

[lehni]

at Function.Base.extend.statics.solveCubic (file:///Users/lehni/Dropbox/Public/Paper.js/sketch/bower_components/paper/dist/paper-full.js:5836:16)
at Function.Base.extend.statics.getParameterOf (file:///Users/lehni/Dropbox/Public/Paper.js/sketch/bower_components/paper/dist/paper-full.js:5850:15)
at Curve.Base.extend.Base.each.getParameterOf (file:///Users/lehni/Dropbox/Public/Paper.js/sketch/bower_components/paper/dist/paper-full.js:5984:16)
at CurveLocation.Base.extend.getParameter (file:///Users/lehni/Dropbox/Public/Paper.js/sketch/bower_components/paper/dist/paper-full.js:6418:37)
at compare (file:///Users/lehni/Dropbox/Public/Paper.js/sketch/bower_components/paper/dist/paper-full.js:6559:32)
at Array.sort (native)
at Path.Item.extend.getIntersections (file:///Users/lehni/Dropbox/Public/Paper.js/sketch/bower_components/paper/dist/paper-full.js:6576:14)
at computeBoolean (file:///Users/lehni/Dropbox/Public/Paper.js/sketch/bower_components/paper/dist/paper-full.js:8507:20)
at PathItem.inject.subtract (file:///Users/lehni/Dropbox/Public/Paper.js/sketch/bower_components/paper/dist/paper-full.js:8797:11)

[lehni]

The reason why it's happening in Array.sort / compare is because only then the curve location is asked for its parameter, and CurveLocation#getParameter() is using getParameterOf() to convert the point to a curve time parameter.

[hkrish]

I guess the "found point's " t is then ~ 0.5541722068563936. The X cubic is ill conditioned, so the we should use Y cubic to convert points to parameter. This could be a check to avoid these cases. also can you please post some context into all these, Like a stack trace, what I want to know is on a higher level why are we ending up here, like where is the arraysort happening? etc, is is before we return the intersectios or with in the boolean code/winding/propagating winding etc. If I know this may be we can find a better alternative to solving that higher level issue instead.

Perhaps the best and most sane thing to do is to condition the input so as to limit the precision of the boolean operations to something we can manage. Like 'rounding' the input to any boolean operations to the nearest 5th decimal point or so. At this level, we are operating on pixels, so 5 decimal places may be good enough. This shouldn't be all that hard to test if it works.

[lehni]

Here an example that reproduces the same issue without all the boolean code, simply by using getIntersections(). I think the ill-conditioned bezier must be a result of continuous sub-division in the fat-line clipping code. See how the first of the two found and logged intersections does not have a parameter value? That's where the above solutions don't match.

https://dl.dropboxusercontent.com/u/85606/paper.js/sketch/index.html#S/jVJPb4IwFP8qDRc0Ng2gwsTt5Gm3ZTsChwpPINbWtHVmM373vRYlc6dxgLzX39/QSyD5AYI8+NiDrbuABrVq3PzJNTEdP0JEXoiEM3njtmPvUFsuWwGTSykJPkfVS5uTYh4tKEmStKLD3vTf4NbJEyX4qkp5na5LWcpRN/6le1cz0B5AWoPMIonnbIma81VFSbHIUj9lfsri1J0gwJ+lK0qyRXX3roUy0OTE6hM8+GowznWoxcxpazWv7WSI42BjuORfpeMMS8fY7k/pCPMky3hcW632sFFC6ZyEXyCEOocPwVDOoKPLx1qwr9KCNujaK2mGeIkD75QmE49HcLTGz7OnMgGytR0uZrMpuYV0uEbZ30U2va6xhaMUfcV8Dfw9TtoxEM12vRA+KfJCDU14O6sxiRLAhGrvfEpGIa7xEmFmp3R1pfAebTXwvbcwQV5U1x8=

[hkrish]

Awesome. Thanks. I will look into this

On 2015Jan10, at 7:35 pm, Jürg Lehni notifications@github.com wrote:

Here an example that reproduces the same issue without all the boolean code, simply by using getIntersections(). I think the ill-conditioned bezier must be a result of continuous sub-division in the fat-line clipping code. See how the first of the two found and logged intersections does not have a parameter value? That's where the above solutions don't match.

https://dl.dropboxusercontent.com/u/85606/paper.js/sketch/index.html#S/jVJPb4IwFP8qDRc0Ng2gwsTt5Gm3ZTsChwpPINbWtHVmM373vRYlc6dxgLzX39/QSyD5AYI8+NiDrbuABrVq3PzJNTEdP0JEXoiEM3njtmPvUFsuWwGTSykJPkfVS5uTYh4tKEmStKLD3vTf4NbJEyX4qkp5na5LWcpRN/6le1cz0B5AWoPMIonnbIma81VFSbHIUj9lfsri1J0gwJ+lK0qyRXX3roUy0OTE6hM8+GowznWoxcxpazWv7WSI42BjuORfpeMMS8fY7k/pCPMky3hcW632sFFC6ZyEXyCEOocPwVDOoKPLx1qwr9KCNujaK2mGeIkD75QmE49HcLTGz7OnMgGytR0uZrMpuYV0uEbZ30U2va6xhaMUfcV8Dfw9TtoxEM 12vRA+KfJCDU14O6sxiRLAhGrvfEpGIa7xEmFmp3R1pfAebTXwvbcwQV5U1x8= https://dl.dropboxusercontent.com/u/85606/paper.js/sketch/index.html#S/jVJPb4IwFP8qDRc0Ng2gwsTt5Gm3ZTsChwpPINbWtHVmM373vRYlc6dxgLzX39/QSyD5AYI8+NiDrbuABrVq3PzJNTEdP0JEXoiEM3njtmPvUFsuWwGTSykJPkfVS5uTYh4tKEmStKLD3vTf4NbJEyX4qkp5na5LWcpRN/6le1cz0B5AWoPMIonnbIma81VFSbHIUj9lfsri1J0gwJ+lK0qyRXX3roUy0OTE6hM8+GowznWoxcxpazWv7WSI42BjuORfpeMMS8fY7k/pCPMky3hcW632sFFC6ZyEXyCEOocPwVDOoKPLx1qwr9KCNujaK2mGeIkD75QmE49HcLTGz7OnMgGytR0uZrMpuYV0uEbZ30U2va6xhaMUfcV8Dfw9TtoxEM12vRA+KfJCDU14O6sxiRLAhGrvfEpGIa7xEmFmp3R1pfAebTXwvbcwQV5U1x8= — Reply to this email directly or view it on GitHub https://github.com/paperjs/paper.js/issues/541#issuecomment-69466466.

[lehni]

One more observation:

Here the current code in the beginning of solveCubic(), changed a bit to have some tolerance in the comparisons of a and d with 0, currently MACHINE_EPSILON:

    solveCubic: function(a, b, c, d, roots, min, max) {
        var x, b1, c2, nRoots = 0;
        if (abs(a) < MACHINE_EPSILON) {
            a = b;
            b1 = c;
            c2 = d;
            x = Infinity;
        } else if (abs(d) < MACHINE_EPSILON) {
            b1 = b;
            c2 = c;
            x = 0;
        } else {

If I change the tolerance there to 1e-12, then the x-cubic is seen as linear again, and -1 is returned... Perhaps it's simply a question of allowing a bit more tolerance here?

[hkrish]

That’s one possibility.

I am tempted to say may we can close this off that way. But the real issue is that, we can’t handle infinite precision, this kind of patches of making it work might fail tomorrow again when another issue comes up. We need to have a robust solution that we know works in all cases.

It is possible to do this without arbitrary precision math. CGAL does it with certain type of approaches and algorithms while keeping numerical operations in check. But that’s more of longterm strategy, I guess.

But for now may be this is good.

On 2015Jan10, at 6:15 pm, Jürg Lehni notifications@github.com wrote:

0.5541722068563936

[lehni]

I could lower Numerical.EPSILON to 1e-12 globally (currently it's at 1e-13 and it used to be at 1e-11), and then use that value there. Will perform some tests...

[lehni]

Alright, with 1e-12 we're back to the previous behavior, which is good. The issue outlined in the original report still fails, for the reason outlined in https://github.com/paperjs/paper.js/issues/541#issuecomment-68764206 What do you recommend to do here to address this, @hkrish?