skia splits complex curves at inflections

[typemytype]

left: the source (as pasted below) middle: booleanOperations right: skia

there is a point added which is not in the source, this needs to be solved

<glyph name="c" format="2">
  <advance width="500"/>
  <outline>
    <contour>
      <point x="108.0" y="524.0"/>
      <point x="246.0" y="473.0"/>
      <point x="246.0" y="527.0" type="curve" smooth="yes"/>
      <point x="246.0" y="593.0"/>
      <point x="169.0" y="631.0"/>
      <point x="108.0" y="631.0" type="curve"/>
      <point x="108.0" y="524.0" type="line"/>
    </contour>
    <contour>
      <point x="469.0" y="573.0" type="curve" smooth="yes"/>
      <point x="469.0" y="607.0"/>
      <point x="432.0" y="641.0"/>
      <point x="356.0" y="641.0" type="curve" smooth="yes"/>
      <point x="227.0" y="641.0"/>
      <point x="185.0" y="540.0"/>
      <point x="185.0" y="406.0" type="curve"/>
      <point x="257.0" y="406.0" type="line"/>
      <point x="257.0" y="412.0"/>
      <point x="257.0" y="428.0"/>
      <point x="257.0" y="466.0" type="curve" smooth="yes"/>
      <point x="257.0" y="529"/>
      <point x="288" y="549.0"/>
      <point x="361.0" y="549.0" type="curve" smooth="yes"/>
      <point x="441" y="549.0"/>
      <point x="469.0" y="548"/>
    </contour>
  </outline>
</glyph>

[anthrotype]

hm. It looks like Skia is splitting the cubic bezier curve at the inflection point. Maybe it's because we are using a function called Simplify in order to remove the overlaps and splitting at inflection points could be part of its contract.. Or maybe skia needs to split at inflections in order to perform its operations. I am not sure how we could prevent this from happening.

[behdad]

I think Cary is interested in seeing these bugs.

[anthrotype]

I think Cary is interested in seeing these bugs.

sure, I will notify him if we confirm that these are actually bugs, rather than intended behavior.

In this particular case, the splitting of the cubic curve seems to be done intentionally.

The SkOpEdgeBuilder class (responsible for converting a SkPath into a set of contours and segments) is calling a method named ComplexBreak; the inline comment says:

// Split complex cubics (such as self-intersecting curves or
// ones with difficult curvature) in two before proceeding.
// This can be required for intersection to succeed.

https://github.com/google/skia/blob/87a7372928043db83fd9019eada25cfcfd1b0706/src/pathops/SkOpEdgeBuilder.cpp#L269-L273

This method checks that the curve is monotonic (either increasing or decreasing) in both X and Y, otherwise it splits it to make it so:

https://github.com/google/skia/blob/6fdbf6161bcb299f855fd467ac4cdbf38c14a5cb/src/pathops/SkPathOpsCubic.cpp#L244

So.. the monotonicity of the curves this seems to me like a requirement to make the curve-to-curve intersection algorithm to work properly.

I think we need to check for such "complex" curves upfront, and if we detect that they are still present after we called skia to remove the overlaps, try to re-join them.

[anthrotype]

I put a printf immediately after the call to SkDCubic::ComplexBreak and I can confirm that is what is happening for this particular glyph.

[typemytype]

the most important part is: the extra point should not be there :)

from skimming the SkOpEdgeBuilder code this feels like an intermediate state of the curves, not a final result. I guess this should be solved inside skia. Your other proposal is very similar to what booleanOperation already does (for every kind of curve)

We can only communicate with Cary (I dont know him) through the skia bug tracking?

[anthrotype]

we can also use the mailing list https://groups.google.com/forum/#!forum/skia-discuss

[typemytype]

this really feels like a bug, even what is a complex curve...

left: the source (as pasted below) middle: booleanOperations right: skia

the orange rects are the differences with the booleanOperation result

<?xml version="1.0" encoding="UTF-8"?>

[anthrotype]

it's consistent with what I noted above. In the first path, the complex curve is split at the infection point. In the second one, I'm not sure what are you pointing at. Is it the fact that an additional contour (moveTo in bold red/pink) is added?

[typemytype]

the bottom part is also a complex curve to me: the question is what defines a complex curve, they both dont have self intersection parts and the off curves goes far beyond the inflection point.

[anthrotype]

yes, they are complex (probably no one will want to draw them like that), but what exactly is it that you don't like with the way the second path is being clipped by skia? That it is splitting off the small contour at the bottom-right while it's not doing the same at the top-right? Or the fact that it's adding the extra contour whereas in the result from booleanOperation (in the middle) keeps it as a single contour?

[typemytype]

the bottom part is fine :) (with a complex curve) the top part is not oke: it should not add extra points where its not needed. Its clearly possible to draw that curve without that extra point. I know its not a good curve, but assume a drawing of rounded italic without extreme points...

[typemytype]

The goal should be 'remove the overlap' not correct the contour, this is an other problem to solve. Its always possible to split an existing curve in parts without losing curve quality. So I dont see why that extra point should remain.

[typemytype]

my visual drawbot test script: https://gist.github.com/typemytype/ada7589bd2a564cefac681f45c3374e5

[anthrotype]

thanks for sharing that!

[behdad]

Ok so currently Skia adds points at inflection points. We should ask Cary if that can be avoided.