`crossingsRemoved` makes these two contours disappear about bezierkit

[hfutrell]

@mbutterick I was able to reproduce this issue! As you reported, the result is falsely empty. I'm not sure why yet, but I'm saving this test data for later.

     let firstCurves: [BezierCurve] = [BezierKit.CubicCurve(p0: CGPoint(x: 28.0, y: 14.0),
                                                               p1: CGPoint(x: 32.0, y: 21.0),
                                                               p2: CGPoint(x: 33.0, y: 42.0),
                                                               p3: CGPoint(x: 30.0, y: 53.0)),
                                          BezierKit.CubicCurve(p0: CGPoint(x: 30.0, y: 53.0),
                                                               p1: CGPoint(x: 19.0, y: 32.0),
                                                               p2: CGPoint(x: 22.0, y: 26.0),
                                                               p3: CGPoint(x: 28.0, y: 14.0))]

        let secondCurves: [BezierCurve] = [BezierKit.CubicCurve(p0: CGPoint(x: 42.0, y: 38.0),
                                                                p1: CGPoint(x: 42.0, y: 53.0),
                                                                p2: CGPoint(x: 36.0, y: 53.0),
                                                                p3: CGPoint(x: 27.0, y: 53.0)),
                                           BezierKit.CubicCurve(p0: CGPoint(x: 27.0, y: 53.0),
                                                                p1: CGPoint(x: 19.0, y: 40.0),
                                                                p2: CGPoint(x: 29.0, y: 32.0),
                                                                p3: CGPoint(x: 42.0, y: 38.0))]

        let component1 = PathComponent(curves: firstCurves)
        let component2 = PathComponent(curves: secondCurves)
        let path = Path(components: [component1, component2])
        let result = path.crossingsRemoved()
        XCTAssertFalse(result.isEmpty)

[mbutterick]

My credibility is restored 😉

[hfutrell]

Haha, well you're pretty credible in my book. The issues you open always have the exact data needed to reproduce which makes them pretty stellar.

[hfutrell]

delving into this a bit (and please pardon my stream of consciousness):

The top intersection shown in this diagram is actually two separate nearby intersections, one at (30.01, 52.98) and the other at (29.99, 52.98). If we look at the first contour (the long skinny one), the first nearby intersection falls on its first curve at t = 0.99929, and the second nearby intersection falls on its second curve at t = 0.00036. If we look at the second contour, the first nearby intersection falls on its first curve at t = 0.88399, and the second nearby intersection falls on the same curve at t = 0.88474. These intersections are actually being computed accurately, and oddly do not appear to be the cause of the failure.

Next in AugmentedGraph we classify the edges, and appear to do so correctly for the first contour (we even classify the tiny edge of the contour between the two nearby intersections correctly). The problem is with when we go to classify the second contour. When we classify the edge from the first curve at t = 0.884 to the second curve at t = 0.364 we falsely conclude that this edge should be excluded from the solution.

[hfutrell]

It looks like if we do component2.contains(CGPoint(x: 28.52584147560618, y: 52.99912729740088)) we are getting the wrong answer. I think this is the root of the problem. contains says the point is contained but in fact the point should have a y value greater than the curve 52.997 making it fall outside the contour.

[hfutrell]

@mbutterick in Util.swift could you try changing the line 190 to if discriminant < -1.0e-14 { and line 207 to if discriminant > 1.0e-14 { and report results?

I think this should do the trick.

[mbutterick]

Before the patch, here are the glyphs that fail:

glyph X in [AFFont: Advocate Slab C45 Regular, 706 glyphs] did not have overlap removed successfully
glyph y in [AFFont: Advocate Slab C51 Regular, 764 glyphs] did not have overlap removed successfully
glyph k in [AFFont: Advocate Slab C53 Regular, 775 glyphs] did not have overlap removed successfully
glyph y.mid in [AFFont: Advocate Slab C51 Regular, 764 glyphs] did not have overlap removed successfully
glyph y in [AFFont: Advocate Slab C61 Regular, 764 glyphs] did not have overlap removed successfully
glyph K in [AFFont: Advocate Slab C63 Regular, 775 glyphs] did not have overlap removed successfully
glyph k.alt in [AFFont: Advocate Slab C53 Regular, 775 glyphs] did not have overlap removed successfully
glyph y.mid in [AFFont: Advocate Slab C61 Regular, 764 glyphs] did not have overlap removed successfully
glyph k.mid in [AFFont: Advocate Slab C53 Regular, 775 glyphs] did not have overlap removed successfully
glyph k.alt.mid in [AFFont: Advocate Slab C53 Regular, 775 glyphs] did not have overlap removed successfully

After the patch:

glyph iogonek.mid in [AFFont: Advocate Slab C43 Regular, 775 glyphs] did not have overlap removed successfully
glyph iogonek.mid in [AFFont: Advocate Slab C45 Regular, 706 glyphs] did not have overlap removed successfully
glyph iogonek.mid in [AFFont: Advocate Slab C51 Regular, 764 glyphs] did not have overlap removed successfully
glyph iogonek.mid in [AFFont: Advocate Slab C61 Regular, 764 glyphs] did not have overlap removed successfully
glyph iogonek.mid in [AFFont: Advocate Slab C53 Regular, 775 glyphs] did not have overlap removed successfully
glyph iogonek.mid in [AFFont: Advocate Slab C55 Regular, 706 glyphs] did not have overlap removed successfully
glyph iogonek.mid in [AFFont: Advocate Slab C63 Regular, 775 glyphs] did not have overlap removed successfully

So the patch is apparently fixing one bug & introducing another (because the two sets of problem glyphs have nothing in common).

The interesting common feature of the first set of glyphs is that they all have diagonal parts — curious why that would consistently trigger a bug.

The interesting feature of the second set is that it's the same glyph in different styles. The iogonek.mid is shown below. I will have to experiment some more to see which points in the glyph are causing the problem (though based on the results, I suspect it’s where the ogonek accent is intersecting the bottom).

Here’s a fragment of the glyph that still manifests the problem:

And the debug report for that fragment:

path.components.map { $0.curves } =
[[BezierKit.CubicCurve(p0: (96.0, 75.0), p1: (96.0, 71.0), p2: (97.0, 70.0), p3: (101.0, 70.0)), BezierKit.LineSegment(p0: (101.0, 70.0), p1: (187.0, 70.0)), BezierKit.CubicCurve(p0: (187.0, 70.0), p1: (192.0, 70.0), p2: (194.0, 71.0), p3: (194.0, 77.0)), BezierKit.CubicCurve(p0: (194.0, 77.0), p1: (194.0, 578.0), p2: (96.0, 578.0), p3: (96.0, 75.0))], [BezierKit.CubicCurve(p0: (61.0, 85.0), p1: (61.0, 70.0), p2: (61.0, 70.0), p3: (76.0, 70.0)), BezierKit.LineSegment(p0: (76.0, 70.0), p1: (214.0, 70.0)), BezierKit.CubicCurve(p0: (214.0, 70.0), p1: (229.0, 70.0), p2: (229.0, 70.0), p3: (229.0, 85.0)), BezierKit.CubicCurve(p0: (229.0, 85.0), p1: (229.0, 158.0), p2: (61.0, 158.0), p3: (61.0, 85.0))], [BezierKit.LineSegment(p0: (216.0, 103.0), p1: (182.0, 118.0)), BezierKit.CubicCurve(p0: (182.0, 118.0), p1: (123.0, 90.0), p2: (144.0, -45.0), p3: (144.0, -19.0)), BezierKit.CubicCurve(p0: (144.0, -19.0), p1: (144.0, 26.0), p2: (170.0, 64.0), p3: (216.0, 97.0)), BezierKit.LineSegment(p0: (216.0, 97.0), p1: (216.0, 103.0))]]
path.crossingsRemoved().components.map { $0.curves } =
[]

In this case, I notice that as with the previous cases, it has a little “point” sticking below a horizontal line. (Maybe your patch corrects the “pointing up” case but breaks the “pointing down” case?)

[hfutrell]

@mbutterick this is extremely helpful feedback. Before I had you set the value to 1.0e-14 it was effectively set at 1.0e-8. Perhaps I am being too aggressive with my change. I noticed that to fix the first path specifically I only need to set it as low as 1.0e-10, which is 10,000x larger than 1.0e-14. We might try 1.0e-10, 1.0e-11, 1.0e-12 or 1.0e-13 here instead. Any of these values might have some chance of working without causing regressions.

For some reason I can't reproduce the issue you are having using the fragment you sent me. Here is my code:

   let curves1: [BezierCurve] = [CubicCurve(p0: CGPoint(x: 96.0, y: 75.0),
                                                 p1: CGPoint(x: 96.0, y: 71.0),
                                                 p2: CGPoint(x: 97.0, y: 70.0),
                                                 p3: CGPoint(x: 101.0, y: 70.0)),
                                      LineSegment(p0: CGPoint(x: 101.0, y: 70.0),
                                                  p1: CGPoint(x: 187.0, y: 70.0)),
                                      CubicCurve(p0: CGPoint(x: 187.0, y: 70.0),
                                                 p1: CGPoint(x: 192.0, y: 70.0),
                                                 p2: CGPoint(x: 194.0, y: 71.0),
                                                 p3: CGPoint(x: 194.0, y: 77.0)),
                                      CubicCurve(p0: CGPoint(x: 194.0, y: 77.0),
                                                 p1: CGPoint(x: 194.0, y: 578.0),
                                                 p2: CGPoint(x: 96.0, y: 578.0),
                                                 p3: CGPoint(x: 96.0, y: 75.0))]
            let component1 = PathComponent(curves: curves1)

            let curves2: [BezierCurve] = [CubicCurve(p0: CGPoint(x: 61.0, y: 85.0),
                                                     p1: CGPoint(x: 61.0, y: 70.0),
                                                     p2: CGPoint(x: 61.0, y: 70.0),
                                                     p3: CGPoint(x: 76.0, y: 70.0)),
                                          BezierKit.LineSegment(p0: CGPoint(x: 76.0, y: 70.0),
                                                                p1: CGPoint(x: 214.0, y: 70.0)),
                                          BezierKit.CubicCurve(p0: CGPoint(x: 214.0, y: 70.0),
                                                               p1: CGPoint(x: 229.0, y: 70.0),
                                                               p2: CGPoint(x: 229.0, y: 70.0),
                                                               p3: CGPoint(x: 229.0, y: 85.0)),
                                          BezierKit.CubicCurve(p0: CGPoint(x: 229.0, y: 85.0),
                                                               p1: CGPoint(x: 229.0, y: 158.0),
                                                               p2: CGPoint(x: 61.0, y: 158.0),
                                                               p3: CGPoint(x: 61.0, y: 85.0))]
            let component2 = PathComponent(curves: curves2)

            let curves3: [BezierCurve] = [LineSegment(p0: CGPoint(x: 216.0, y: 103.0),
                                                      p1: CGPoint(x: 182.0, y: 118.0)),
                                          CubicCurve(p0: CGPoint(x: 182.0, y: 118.0),
                                                     p1: CGPoint(x: 123.0, y: 90.0),
                                                     p2: CGPoint(x: 144.0, y: -45.0),
                                                     p3: CGPoint(x: 144.0, y: -19.0)),
                                          CubicCurve(p0: CGPoint(x: 144.0, y: -19.0),
                                                     p1: CGPoint(x: 144.0, y: 26.0),
                                                     p2: CGPoint(x: 170.0, y: 64.0),
                                                     p3: CGPoint(x: 216.0, y: 97.0)),
                                          LineSegment(p0: CGPoint(x: 216.0, y: 97.0),
                                                      p1: CGPoint(x: 216.0, y: 103.0))]
            let component3 = PathComponent(curves: curves3)
            let path = Path(components: [component1, component2, component3])
            XCTAssertNotEqual(path.crossingsRemoved(), Path())

Here's the results of crossingsRemoved ... I think iit looks correct (pardon the fact it's flipped vertically).

[mbutterick]

Whoops, I made a mistake typing your patch — I didn’t notice that the second number is positive. That explains where the “new bug” came from … 🤦

The revised results:

1. If I type your patch correctly (setting line 190 to -1.0e-14 and 207 to 1.0e-14), then all the errors are cleared.

2. If I adjust the constants to ±1.0e-12, I still get an error on one of the K glyphs.

3. If I adjust the constants to ±1.0e-13, then the errors are still cleared.

[hfutrell]

@mbutterick wohoo! It sounds like either 1.0e-13 or 1.0e-14 could work. I'll use 1.0e-14 for now.

[hfutrell]

@mbutterick I've added a unit test using your data and merged the fix into the branch 0.9-release. I'm closing the issue now.

[mbutterick]

Thank you!