Skia PathOps accuracy

[Kari Pihkala]

Hi!

I'm using Skia PathOps to process paths. Most of the times, it works just great, but I have noticed that sometimes the result is not what I expect. 

I watched the excellent video about the PathOps [1], and according to that there are cases where floating point inaccuracy can give wrong results. I wonder if that is the case here or is this something that the algorithms should be able to handle?

Also, are there any ways to avoid these kind of errors? Can the paths be preprocessed somehow to prevent this?

Here are my paths and the result for kDifference_PathOp. I was expecting to get one subpath, but instead I get two. Also, I didn't expect the positive y points of the path1 to be clipped away (37.7109375, 1.3515625 and 37.203125, 0.9609375). I also get wrong results for a union, intersection and XOR with these paths. I'm running this on 64-bit Mac OS X with SkScalar defined as 32-bit float.

SkPath path1;

path1.moveTo(39.9375, -5.8359375);

path1.lineTo(40.625, -5.7890625);

path1.lineTo(37.7109375, 1.3515625);

path1.lineTo(37.203125, 0.9609375);

path1.close();

SkPath path2;

path2.moveTo(37.52734375, -1.44140625);

path2.cubicTo(37.8736991882324, -1.69921875, 38.1640625, -2.140625, 38.3984375, -2.765625);

path2.lineTo(38.640625, -2.609375);

path2.cubicTo(38.53125, -1.89583337306976, 38.0664443969727, -0.154893040657043, 38.0664443969727, -0.154893040657043);

path2.cubicTo(38.0664443969727, -0.154893040657043, 37.1809883117676, -1.18359375, 37.52734375, -1.44140625);

path2.close();

SkPath result;

Op(path1, path2, kDifference_PathOp, &result);

-- The result:

M 38.6537, -2.64481

L 38.6537, -2.64481 ; 39.9375, -5.83594

L 39.9375, -5.83594 ; 40.625, -5.78906

L 40.625, -5.78906 ; 39.3321, -2.62091

C 39.3321, -2.62091 ; 39.3353, -2.62884 ; 38.6505, -2.63681 ; 38.6537, -2.64481

Close back to 38.6537, -2.64481

M 38.6397, -2.60997

L 38.6397, -2.60997 ; 37.7943, -0.508542

C 37.7943, -0.508542 ; 37.9357, -0.306823 ; 38.0664, -0.154893 ; 38.0664, -0.154893

C 38.0664, -0.154893 ; 38.0664, -0.154893 ; 38.5312, -1.89583 ; 38.6406, -2.60938

L 38.6406, -2.60938 ; 38.6397, -2.60997

Close back to 38.6397, -2.60997

BR,

Kari

[1] https://www.youtube.com/watch?v=OmfliNQsk88

[Cary Clark]

Hi Kari

Glad to hear that pathops works some of the time. 

I reproduced your error and I'll look at it as soon as I can. It's a good bug because it evades my check to make sure that the output is correct, so I'm curious to see what's going on.

Thanks for reporting the bug.

Cary

--
You received this message because you are subscribed to the Google Groups "skia-discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to skia-discuss...@googlegroups.com.
To post to this group, send email to skia-d...@googlegroups.com.
Visit this group at http://groups.google.com/group/skia-discuss.
For more options, visit https://groups.google.com/d/optout.

[Cary Clark]

Kari

It looks like the core of the bug is that the cubic/line intersection produces three roots:

0.9209839077022843 - 1.5878989430294932i

0.9209839077022843 + 1.5878989430294932i

103352.91588534783

because the real root is so large compared to the imaginary roots, the imaginary roots are treated as valid and an intersection is found where the cubic T == 0.92098...

The code needs to validate that T and make sure that the line and the cubic occupy nearly the same point that their respective T values suggest. I have this logic for other intersection types, but not for the cubic/line combination, thus the bug.

I'll let you know when I'm able to get a fix in.

Cary

[Kari Pihkala]

Hi Cary,

thank you for a quick response. Nice that you liked the bug and found
the reason for it.

I actually like your approach to calculate the intersection points
analytically. Converting cubics to quads for some cases is also a
clever idea.

Is there a reason why it doesn't just ignore the roots which have an
imaginary component? I would think that they don't represent any real
intersection points.

Great that you can fix the bug.

Kari

2014-04-28 23:56 GMT+03:00 'Cary Clark <cary...@google.com>' via
skia-discuss <skia-d...@googlegroups.com>:

> You received this message because you are subscribed to a topic in the
> Google Groups "skia-discuss" group.
> To unsubscribe from this topic, visit
> https://groups.google.com/d/topic/skia-discuss/afe93k0ABR4/unsubscribe.
> To unsubscribe from this group and all its topics, send an email to

[Cary Clark]

Kari

I don't compute the imaginary component, so I don't know its there. I compare my computations with Mathematica to look for errors, so that's how I know the imaginary roots exist. Sometimes, the imaginary component is so small that the real part of the root is valid within an error tolerance, which is why it is appropriate to find it at least some of the time.

Cary

[Cary Clark]

Kari

You should be copied on the bug progress here:

https://code.google.com/p/skia/issues/detail?id=2488

If you find additional problems, feel free to file a bug. Click on the 'New Issue' button at the link above, add repro steps, and assign it to me : cary...@google.com

Thanks

[Kari Pihkala]

Hi Cary,

that bug doesn’t appear anymore. 

However, I found another similar bug. I filed it, but I couldn't find a way to assign it to you, so here's a link to it:

https://code.google.com/p/skia/issues/detail?id=2504

I’ll follow the new bug to see what the outcome will be.

BR,

Kari

[Kari Pihkala]

Hi Cary,

I noticed that you fixed the earlier bug by using binary search as a fallback. It's a shame that it requires that for those rare cases.

This probably needs to be done for cubic-to-cubic intersections, too. I filed a bug about something that looks like it.

https://code.google.com/p/skia/issues/detail?id=2540

Kari

keskiviikko, 30. huhtikuuta 2014 16.53.17 UTC+3 Cary Clark kirjoitti: