pathops change contour direction/start point

[Adrien Tétar]

Hi all,

I'm using SkOpBuilder to perform boolean operations on paths (with winding fill rule) and it seems that as a side effect the pathops are 1. reversing the contours and 2. shifting the start point by one.

Is that an intended/accepted side-effect? It breaks idempotency of the function, and nullipotency in the case of non overlapping input paths.

That's a bit of a problem because, first for my uses (font editor) it's nice to avoid sparse changes also this means the SkOpBuilder will modify paths that are not overlapping at all (in this case it's idempotent modulo 2, though).

Attached is an illustration of what I mean for a simple square path. Thanks.

[Adrien Tétar]

Additional finding: it seems the result path uses even odd fill type instead of winding (see below). Which is surprising given the calls to FixWinding() in SkOpBuilder::resolve().

paths?

path.setFillType(SkPath::kWinding_FillType);

path.moveTo(112, 595);

path.lineTo(-262, 554);

path.lineTo(-217, 185);

path.lineTo(160, 213);

path.lineTo(112, 595);

path.close();

path.setFillType(SkPath::kWinding_FillType);

path.moveTo(429, 415);

path.lineTo(-71, 425);

path.lineTo(-37, -25);

path.lineTo(362, -30);

path.lineTo(429, 415);

path.close();

result?

path.setFillType(SkPath::kEvenOdd_FillType);

path.moveTo(133.876f, 420.902f);

path.lineTo(-71, 425);

path.lineTo(-53.7826f, 197.122f);

path.lineTo(160, 213);

path.lineTo(133.876f, 420.902f);

path.close();

[Cary Clark]

It is working as designed. Path ops implements a very general algorithm that does not attempt to preserve the contour point order. 

It would certainly be possible to preserve point order and winding with additional bookkeeping, but this is beyond the scope of the project to date.

Feel free to file a feature request at bug.skia.org with your requirements.

--
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+unsubscribe@googlegroups.com.
To post to this group, send email to skia-d...@googlegroups.com.
Visit this group at https://groups.google.com/group/skia-discuss.
For more options, visit https://groups.google.com/d/optout.

[Adrien Tétar]

Thanks. Any way I could "fixup" the result path using Skia APIs? I noticed doing the boolean op twice gives me back the right contour data. Would calling FixWinding() on the result of SkOpBuilder::resolve() do the job?

To unsubscribe from this group and stop receiving emails from it, send an email to skia-discuss...@googlegroups.com.

[Cary Clark]

It would be helpful if you provide a sample series of operations and the expected outcome. You  can use fiddle.skia.org to create an example.

To unsubscribe from this group and stop receiving emails from it, send an email to skia-discuss+unsubscribe@googlegroups.com.

[Adrien Tétar]

Thanks Cary. Does skia have any code to convert outlines from even odd to winding?

[Cary Clark]

Internally, yes, we have code to detect direction and reverse contours so that even odd paths and winding paths draw the same. There's no exposed / public interface.

To unsubscribe from this group and stop receiving emails from it, send an email to skia-discuss+unsubscribe@googlegroups.com.

[Behdad Esfahbod]

On Monday, November 13, 2017 at 11:39:39 AM UTC-8, Cary Clark wrote:

Internally, yes, we have code to detect direction and reverse contours so that even odd paths and winding paths draw the same. There's no exposed / public interface.

That's exactly what we need.  Modern fonts are filled with winding rules, so we need to get outline for that.  Any way to expose that easily?

Thanks
 

[cos...@anthrotype.com]

Are you referring to the private static method SkOpBuilder::FixWinding in src/pathops/SkOpBuilder.cpp, or to something else?

[Cary Clark]

Before I start working on this, it would be really helpful for one of you to write down the requirements.

For instance, you might only care about preserving the contour direction and start if the contour is unmodified.

Or, you might want to specify the direction of the outermost contour.

Or, you may require that if two overlapping contours are clockwise that the union of the pair is also clockwise.

That could be a simple as one or more links to fiddle.skia.org or one or more examples added to a bug at bug.skia.org,

with the desired outcome. It will be helpful for me to have some test data and to see how you are using the

interface.

If that is too daunting, let's meet in person to hash this out.

To unsubscribe from this group and stop receiving emails from it, send an email to skia-discuss+unsubscribe@googlegroups.com.

[Adrien Tétar]

Cary,

Le mardi 14 novembre 2017 19:40:35 UTC+1, Cary Clark a écrit :

For instance, you might only care about preserving the contour direction and start if the contour is unmodified.

Or, you might want to specify the direction of the outermost contour.

Or, you may require that if two overlapping contours are clockwise that the union of the pair is also clockwise.

That's a good question, afaict we want to preserve the outermost contour direction and apply winding direction for the rest. Is that technically sound?

[Essentially we want to preserve as much as possible of: contour direction, start point and the order of contours.]

Below example paths & see attached pictures (union operation is performed).

Sample source path:

path.setFillType(SkPath::kWinding_FillType);

path.moveTo(375, 24);

path.cubicTo(567, 24, 723, 180, 723, 372);

path.cubicTo(723, 563, 567, 719, 375, 719);

path.cubicTo(184, 719, 28, 563, 28, 372);

path.cubicTo(28, 180, 184, 24, 375, 24);

path.close();

path.moveTo(375, 147);

path.cubicTo(252, 147, 151, 248, 151, 372);

path.cubicTo(151, 495, 252, 595, 375, 595);

path.cubicTo(499, 595, 599, 495, 599, 372);

path.cubicTo(599, 248, 499, 147, 375, 147);

path.close();

path.moveTo(175, 180);

path.lineTo(232, 120);

path.lineTo(386, 226);

path.lineTo(805, -96);

path.lineTo(918, -22);

path.lineTo(379, 332);

path.lineTo(175, 180);

path.close();

SkPathOps-Union:

path.setFillType(SkPath::kWinding_FillType);

path.moveTo(217.908f, 211.971f);

path.cubicTo(176.678f, 252.8f, 151, 309.476f, 151, 372);

path.cubicTo(151, 495, 252, 595, 375, 595);

path.cubicTo(499, 595, 599, 495, 599, 372);

path.cubicTo(599, 315.346f, 578.125f, 263.492f, 543.624f, 223.88f);

path.lineTo(379, 332);

path.lineTo(217.908f, 211.971f);

path.close();

path.moveTo(570.527f, 84.1918f);

path.cubicTo(514.776f, 46.2132f, 447.451f, 24, 375, 24);

path.cubicTo(184, 24, 28, 180, 28, 372);

path.cubicTo(28, 563, 184, 719, 375, 719);

path.cubicTo(567, 719, 723, 563, 723, 372);

path.cubicTo(723, 290.285f, 694.743f, 215.092f, 647.481f, 155.669f);

path.lineTo(918, -22);

path.lineTo(805, -96);

path.lineTo(570.527f, 84.1918f);

path.close();

path.moveTo(464.508f, 165.667f);

path.lineTo(386, 226);

path.lineTo(293.66f, 162.441f);

path.cubicTo(318.916f, 152.475f, 346.362f, 147, 375, 147);

path.cubicTo(406.849f, 147, 437.114f, 153.663f, 464.508f, 165.667f);

path.close();

What we want:

path.setFillType(SkPath::kWinding_FillType);

path.moveTo(375, 24);

path.cubicTo(447.449f, 24, 514.773f, 46.2123f, 570.523f, 84.1944f);

path.lineTo(805, -96);

path.lineTo(918, -22);

path.lineTo(647.476f, 155.673f);

path.cubicTo(694.741f, 215.087f, 723, 290.283f, 723, 372);

path.cubicTo(723, 563, 567, 719, 375, 719);

path.cubicTo(184, 719, 28, 563, 28, 372);

path.cubicTo(28, 180, 184, 24, 375, 24);

path.close();

path.moveTo(151, 372);

path.cubicTo(151, 495, 252, 595, 375, 595);

path.cubicTo(499, 595, 599, 495, 599, 372);

path.cubicTo(599, 315.339f, 578.12f, 263.481f, 543.612f, 223.887f);

path.lineTo(379, 332);

path.lineTo(217.911f, 211.973f);

path.cubicTo(176.68f, 252.798f, 151, 309.475f, 151, 372);

path.close();

path.moveTo(375, 147);

path.cubicTo(346.367f, 147, 318.927f, 152.473f, 293.675f, 162.452f);

path.lineTo(386, 226);

path.lineTo(464.495f, 165.677f);

path.cubicTo(437.104f, 153.661f, 406.843f, 147, 375, 147);

path.close();

(FYI, more discussion on  this repo & issue: https://github.com/fonttools/skia-pathops/issues/10 )

Thanks,

[Adrien Tétar]

Actually, I think the contour order does not matter so much. What we really need is:

1. proper winding direction in resulting contours, with same outer contour direction as source

2. unmodified contours don't get changed (same direction and start point), this creates spurious noise/diffs in our display and in the files

If we have these two things I think it'll be fine.

Thanks,

[Ben Wagner]

Just to note this here, I created https://bugs.chromium.org/p/skia/issues/detail?id=7682 with a simple test case (intersect a smaller circle with a larger one).

To unsubscribe from this group and stop receiving emails from it, send an email to skia-discuss+unsubscribe@googlegroups.com.

[Gábor]

Hi,

I arrived here as I browsed for the same problem and it doesn't seem to be fixed yet. In addition to the problems described here, I also found that unioning even-odd paths will also come out as winding, no matter what. It seems to me that path ops, in general, are completely wrong. The necessary functions might be there inside but they're not called correctly and we are not allowed to call them to fix our paths. Any chance of progress here? Right now I'm implementing my own union logic to work around the issues.

> Modern fonts are filled with winding rules, so we need to get outline for that. 

I wouldn't say that. One of them do (TTF), the other doesn't (OTF). Obviously, all rules should be observed both in input and output.

Bye,

  Gábor

[Gábor]

Hi,

eating a bit of humble pie, it seems you're already a bit ahead of the bug but in SkiaSharp we don't yet have access to AsWinding. Well, that might be my problem...

Bye,

  Gábor