What is the winding rule used by `PathCombine::RemoveInteriorPoints`?

[ctrlcctrlv]

It seems buggy to me but I'm not sure I'm using it right as there seems to be no consideration of winding given in your docs.

[Logicalshift]

Ah, you probably want to use path_remove_overlapped_points(), which doesn't have an entry in PathCombine, so I probably need to add one.

'Remove interior points' in this case classifies any point within the outermost perimeter of the path as 'interior'. (That's essentially a stricter than usual version of the non-zero winding rule)

'Remove overlapped points' considers every edge as moving from inside to outside of the path (so it effectively uses the even-odd winding rule)

They have slightly different use-cases: 'remove interior points' is good for cleaning up something like a path resulting from a brush stroke where it doesn't (initially) contain any holes but instead might self-overlap. 'Remove overlapped points' is useful for cleaning up more complex paths where there might be holes.

This implementation of 'remove interior points' is quite useful if you think in terms of building up a path via the arithmetic operations: ie, remove the interior points of subpaths and then add or subtract them to create holes. PathCombine was made with this way of describing paths in mind - it's a more explicit way of describing the shape of something than relying on winding rules (the output is a path where all edges are exterior edges, so it everything effectively uses the even-odd winding rule).

(Think the documentation needs some updating to make this all a lot more clear to start with)

[ctrlcctrlv]

Sorry, I don't quite understand. I have support for both your modes in MFEKpathops.

path_remove_overlapped_points results in this for example:

It results in buggy output across the font:

It seems it's not the right mode either.

[ctrlcctrlv]

If you want to see exactly what I see, MFEKpathops is the project.

https://github.com/MFEK/pathops/blob/227b9663984b728e4ad241980545eb498ae52832/src/boolean.rs#L123

apply_flo is my attempt to use your modes…

    let out = match pathop {
        FloPathOp::RemoveInterior => flopath::path_remove_interior_points::<PwBez, PwBez>(&pw.segs, 1.),
        FloPathOp::RemoveOverlapping => flopath::path_remove_overlapped_points::<PwBez, PwBez>(&pw.segs, 1.),
        FloPathOp::Intersect => flopath::path_intersect::<PwBez, PwBez, PwBez>(&pw.segs, &o_pw.expect("mode requires operand").segs, 1.),
        FloPathOp::Add => flopath::path_add::<PwBez, PwBez, PwBez>(&pw.segs, &o_pw.expect("mode requires operand").segs, 1.),
        FloPathOp::Sub => flopath::path_sub::<PwBez, PwBez, PwBez>(&pw.segs, &o_pw.expect("mode requires operand").segs, 1.),
    };

I get best output from PathCombine::RemoveInteriorPoints, but really I don't get usable output from either.

Inputs will always be something like this—

I'm just failing to understand why it's so off.

[ctrlcctrlv]

Huh, looking at it again has given me something of a “eureka”.

I think my accuracy was way too tolerant.

I lowered it by around ten orders of magnitude and now get—

[ctrlcctrlv]

Yeah unfortunately your RemoveInteriorPoints code just hates certain glyphs though. g.low especially.

Sigh…don't worry, you're not the only one whose code I've managed to break, cf. adobe-type-tools/afdko#1463.

[Logicalshift]

Hmm: this looks more like a bug when detecting where two curves intersect, or possibly incorrect edge ordering with overlapping curves. The filled-in 'g' in your example looks like it could be either.

Looking at your example, I'd think the most likely cause is that overlapping portion of the glyph isn't generating collisions properly. Looking at your update: yes, the accuracy is passed into curve_intersects_curve_clip() and will affect the results there, so that could definitely be part of it. It's a numeric algorithm so it's probably always going to have cases that fail, but if it's that, you've probably found a case that's fixable.

A bug in edge ordering should affect the addition and overlaps operations more than 'remove interior' - essentially when there are two perfectly overlapping paths, flo_curves needs to treat a ray leaving the interior of the shape as leaving in the opposite order to which it entered it to generate correct results.

(A third possibility is a bug in the ray/curve intersection algorithm: that's a bit more robust in general so it's more of an outside possibility)

Do you have the points that you're supplying to make up that g? I've got an idea what I might do to find this issue but there might be some fine-tuning involved to find curves that exhibit the bug. (The graph_path_svg_string() function is made for tracking down these kinds of bug by illustrating what the algorithm is doing at a point in time)

[ctrlcctrlv]

Yes, here's g.low.glif for Regular

<?xml version="1.0" encoding="UTF-8"?>
<glyph name="g.low" format="2">
  <advance width="516"/>
  <outline>
    <contour>
      <point x="-14.354116" y="66.98954" type="curve"/>
      <point x="-8.825491" y="59.061977"/>
      <point x="2.0829022" y="57.11726"/>
      <point x="10.010462" y="62.645885" type="curve"/>
      <point x="109.23956" y="131.84758"/>
      <point x="220.10713" y="230.321"/>
      <point x="346.346" y="230.321" type="curve"/>
      <point x="359.739" y="230.321"/>
      <point x="372.6144" y="229.27303"/>
      <point x="385.84747" y="227.63289" type="curve"/>
      <point x="395.43906" y="226.44408"/>
      <point x="404.1783" y="233.25589"/>
      <point x="405.36713" y="242.84747" type="curve"/>
      <point x="406.5559" y="252.43907"/>
      <point x="399.7441" y="261.1783"/>
      <point x="390.15253" y="262.36713" type="curve"/>
      <point x="375.48575" y="264.18494"/>
      <point x="361.17783" y="265.32098"/>
      <point x="346.346" y="265.32098" type="curve"/>
      <point x="210.86183" y="265.32098"/>
      <point x="96.09466" y="165.35109"/>
      <point x="-10.010462" y="91.35412" type="curve"/>
      <point x="-17.93802" y="85.82549"/>
      <point x="-19.882742" y="74.9171"/>
    </contour>
    <contour>
      <point x="390.48355" y="262.32288" type="curve"/>
      <point x="390.48355" y="262.32288"/>
      <point x="390.48355" y="262.32288"/>
      <point x="390.48355" y="262.32288" type="curve"/>
      <point x="377.00385" y="264.25543"/>
      <point x="363.86914" y="265.193"/>
      <point x="350.21" y="265.193" type="curve"/>
      <point x="236.90161" y="265.193"/>
      <point x="134.97865" y="206.31824"/>
      <point x="80.15723" y="107.048355" type="curve"/>
      <point x="67.51044" y="84.14772"/>
      <point x="54.6194" y="55.136375"/>
      <point x="54.6194" y="28.425" type="curve"/>
      <point x="54.6194" y="-6.1496105"/>
      <point x="76.49837" y="-30.502699"/>
      <point x="111.745" y="-30.5027" type="curve"/>
      <point x="240.37683" y="-30.502699"/>
      <point x="359.86557" y="135.03012"/>
      <point x="408.73233" y="235.33554" type="curve"/>
      <point x="412.9653" y="244.02426"/>
      <point x="409.35318" y="254.49936"/>
      <point x="400.66446" y="258.73233" type="curve"/>
      <point x="391.97574" y="262.9653"/>
      <point x="381.50064" y="259.35318"/>
      <point x="377.26767" y="250.66446" type="curve"/>
      <point x="335.21295" y="164.34161"/>
      <point x="224.40115" y="4.4973"/>
      <point x="111.745" y="4.4973" type="curve"/>
      <point x="95.83539" y="4.4973"/>
      <point x="89.6194" y="13.047722"/>
      <point x="89.6194" y="28.425" type="curve"/>
      <point x="89.6194" y="48.828964"/>
      <point x="101.21961" y="72.796196"/>
      <point x="110.81477" y="90.16301" type="curve"/>
      <point x="159.52303" y="178.32274"/>
      <point x="249.60486" y="230.193"/>
      <point x="350.21" y="230.193" type="curve"/>
      <point x="362.2078" y="230.193"/>
      <point x="373.68958" y="229.37274"/>
      <point x="385.51645" y="227.67712" type="curve"/>
      <point x="395.0836" y="226.3055"/>
      <point x="403.95123" y="232.94928"/>
      <point x="405.32288" y="242.51643" type="curve"/>
      <point x="406.69452" y="252.08359"/>
      <point x="400.05072" y="260.95123"/>
    </contour>
    <contour>
      <point x="400.7546" y="258.68808" type="curve"/>
      <point x="392.09033" y="262.97083"/>
      <point x="381.59467" y="259.41888"/>
      <point x="377.31192" y="250.75461" type="curve"/>
      <point x="326.3861" y="147.72835"/>
      <point x="275.4168" y="44.72375"/>
      <point x="224.32448" y="-58.22003" type="curve"/>
      <point x="224.32355" y="-58.221897"/>
      <point x="224.40028" y="-58.0744"/>
      <point x="224.47699" y="-57.926895" type="curve"/>
      <point x="224.55371" y="-57.779392"/>
      <point x="224.6304" y="-57.631878"/>
      <point x="224.62941" y="-57.633705" type="curve"/>
      <point x="196.89201" y="-108.592964"/>
      <point x="125.29187" y="-279.617"/>
      <point x="78.8109" y="-279.617" type="curve"/>
      <point x="66.41349" y="-279.617"/>
      <point x="49.4785" y="-275.47705"/>
      <point x="49.4785" y="-260.366" type="curve"/>
      <point x="49.4785" y="-167.8235"/>
      <point x="303.24353" y="-62.688316"/>
      <point x="377.21945" y="-24.395418" type="curve"/>
      <point x="428.20877" y="1.9987056"/>
      <point x="479.00412" y="29.644754"/>
      <point x="526.05536" y="62.67728" type="curve"/>
      <point x="533.9656" y="68.23069"/>
      <point x="535.8761" y="79.14512"/>
      <point x="530.3227" y="87.055336" type="curve"/>
      <point x="524.7693" y="94.96555"/>
      <point x="513.85486" y="96.87613"/>
      <point x="505.94467" y="91.322716" type="curve"/>
      <point x="389.78024" y="9.768924"/>
      <point x="14.4785" y="-126.83389"/>
      <point x="14.4785" y="-260.366" type="curve"/>
      <point x="14.4785" y="-296.29556"/>
      <point x="46.39315" y="-314.617"/>
      <point x="78.8109" y="-314.617" type="curve"/>
      <point x="157.64651" y="-314.617"/>
      <point x="219.20493" y="-140.81"/>
      <point x="255.37059" y="-74.366295" type="curve"/>
      <point x="255.37158" y="-74.36447"/>
      <point x="255.44736" y="-74.21882"/>
      <point x="255.52312" y="-74.07316" type="curve"/>
      <point x="255.59886" y="-73.9275"/>
      <point x="255.6746" y="-73.78183"/>
      <point x="255.67552" y="-73.77997" type="curve"/>
      <point x="306.77625" y="29.180716"/>
      <point x="357.75394" y="132.20222"/>
      <point x="408.68808" y="235.24539" type="curve"/>
      <point x="412.97083" y="243.90968"/>
      <point x="409.41888" y="254.40533"/>
    </contour>
  </outline>
</glyph>

[Logicalshift]

Thanks. A bit of editing and I get this as a representation in flo_curves own datatypes (for future reference):

        let paths           = vec![
            BezierPathBuilder::<SimpleBezierPath>::start(Coord2(-14.354116, 66.98954))
              .curve_to(
                (Coord2(-8.825491, 59.061977),
                 Coord2(2.0829022, 57.11726)),
                Coord2(10.010462, 62.645885))
              .curve_to(
                (Coord2(109.23956, 131.84758),
                 Coord2(220.10713, 230.321)),
                Coord2(346.346, 230.321))
              .curve_to(
                (Coord2(359.739, 230.321),
                 Coord2(372.6144, 229.27303)),
                Coord2(385.84747, 227.63289))
              .curve_to(
                (Coord2(395.43906, 226.44408),
                 Coord2(404.1783, 233.25589)),
                Coord2(405.36713, 242.84747))
              .curve_to(
                (Coord2(406.5559, 252.43907),
                 Coord2(399.7441, 261.1783)),
                Coord2(390.15253, 262.36713))
              .curve_to(
                (Coord2(375.48575, 264.18494),
                 Coord2(361.17783, 265.32098)),
                Coord2(346.346, 265.32098))
              .curve_to(
                (Coord2(210.86183, 265.32098),
                 Coord2(96.09466, 165.35109)),
                Coord2(-10.010462, 91.35412))
              .curve_to(
                (Coord2(-17.93802, 85.82549),
                 Coord2(-19.882742, 74.9171)),
                Coord2(-14.354116, 66.98954))
              .build(),

            BezierPathBuilder::<SimpleBezierPath>::start(Coord2(390.48355, 262.32288))
              .curve_to(
                (Coord2(390.48355, 262.32288),
                 Coord2(390.48355, 262.32288)),
                Coord2(390.48355, 262.32288))
              .curve_to(
                (Coord2(377.00385, 264.25543),
                 Coord2(363.86914, 265.193)),
                Coord2(350.21, 265.193))
              .curve_to(
                (Coord2(236.90161, 265.193),
                 Coord2(134.97865, 206.31824)),
                Coord2(80.15723, 107.048355))
              .curve_to(
                (Coord2(67.51044, 84.14772),
                 Coord2(54.6194, 55.136375)),
                Coord2(54.6194, 28.425))
              .curve_to(
                (Coord2(54.6194, -6.1496105),
                 Coord2(76.49837, -30.502699)),
                Coord2(111.745, -30.5027))
              .curve_to(
                (Coord2(240.37683, -30.502699),
                 Coord2(359.86557, 135.03012)),
                Coord2(408.73233, 235.33554))
              .curve_to(
                (Coord2(412.9653, 244.02426),
                 Coord2(409.35318, 254.49936)),
                Coord2(400.66446, 258.73233))
              .curve_to(
                (Coord2(391.97574, 262.9653),
                 Coord2(381.50064, 259.35318)),
                Coord2(377.26767, 250.66446))
              .curve_to(
                (Coord2(335.21295, 164.34161),
                 Coord2(224.40115, 4.4973)),
                Coord2(111.745, 4.4973))
              .curve_to(
                (Coord2(95.83539, 4.4973),
                 Coord2(89.6194, 13.047722)),
                Coord2(89.6194, 28.425))
              .curve_to(
                (Coord2(89.6194, 48.828964),
                 Coord2(101.21961, 72.796196)),
                Coord2(110.81477, 90.16301))
              .curve_to(
                (Coord2(159.52303, 178.32274),
                 Coord2(249.60486, 230.193)),
                Coord2(350.21, 230.193))
              .curve_to(
                (Coord2(362.2078, 230.193),
                 Coord2(373.68958, 229.37274)),
                Coord2(385.51645, 227.67712))
              .curve_to(
                (Coord2(395.0836, 226.3055),
                 Coord2(403.95123, 232.94928)),
                Coord2(405.32288, 242.51643))
              .curve_to(
                (Coord2(406.69452, 252.08359),
                 Coord2(400.05072, 260.95123)),
                Coord2(390.48355, 262.32288))
              .build(),

            BezierPathBuilder::<SimpleBezierPath>::start(Coord2(400.7546, 258.68808))
              .curve_to(
                (Coord2(392.09033, 262.97083),
                 Coord2(381.59467, 259.41888)),
                Coord2(377.31192, 250.75461))
              .curve_to(
                (Coord2(326.3861, 147.72835),
                 Coord2(275.4168, 44.72375)),
                Coord2(224.32448, -58.22003))
              .curve_to(
                (Coord2(224.32355, -58.221897),
                 Coord2(224.40028, -58.0744)),
                Coord2(224.47699, -57.926895))
              .curve_to(
                (Coord2(224.55371, -57.779392),
                 Coord2(224.6304, -57.631878)),
                Coord2(224.62941, -57.633705))
              .curve_to(
                (Coord2(196.89201, -108.592964),
                 Coord2(125.29187, -279.617)),
                Coord2(78.8109, -279.617))
              .curve_to(
                (Coord2(66.41349, -279.617),
                 Coord2(49.4785, -275.47705)),
                Coord2(49.4785, -260.366))
              .curve_to(
                (Coord2(49.4785, -167.8235),
                 Coord2(303.24353, -62.688316)),
                Coord2(377.21945, -24.395418))
              .curve_to(
                (Coord2(428.20877, 1.9987056),
                 Coord2(479.00412, 29.644754)),
                Coord2(526.05536, 62.67728))
              .curve_to(
                (Coord2(533.9656, 68.23069),
                 Coord2(535.8761, 79.14512)),
                Coord2(530.3227, 87.055336))
              .curve_to(
                (Coord2(524.7693, 94.96555),
                 Coord2(513.85486, 96.87613)),
                Coord2(505.94467, 91.322716))
              .curve_to(
                (Coord2(389.78024, 9.768924),
                 Coord2(14.4785, -126.83389)),
                Coord2(14.4785, -260.366))
              .curve_to(
                (Coord2(14.4785, -296.29556),
                 Coord2(46.39315, -314.617)),
                Coord2(78.8109, -314.617))
              .curve_to(
                (Coord2(157.64651, -314.617),
                 Coord2(219.20493, -140.81)),
                Coord2(255.37059, -74.366295))
              .curve_to(
                (Coord2(255.37158, -74.36447),
                 Coord2(255.44736, -74.21882)),
                Coord2(255.52312, -74.07316))
              .curve_to(
                (Coord2(255.59886, -73.9275),
                 Coord2(255.6746, -73.78183)),
                Coord2(255.67552, -73.77997))
              .curve_to(
                (Coord2(306.77625, 29.180716),
                 Coord2(357.75394, 132.20222)),
                Coord2(408.68808, 235.24539))
              .curve_to(
                (Coord2(412.97083, 243.90968),
                 Coord2(409.41888, 254.40533)),
                Coord2(400.7546, 258.68808))
              .build()
        ];

which I can plug into a demo app to get a basic rendering like this (without trying any of the point removal functions):

so I think I've got this right. The overlapping section at the top of the glyph looks ripe for triggering one of the bugs I'm thinking of, so I'm going to see if I can't get something to happen next.

[Logicalshift]

I've put this demo code on a branch: https://github.com/Logicalshift/flo_curves/blob/issue-14/demos/remove_interior_points/src/main.rs so you can check my results for yourself.

I'm still investigating, but I've found a few things. If I remove the interior points and then add the paths (which looks like it might be what your intent is), everything seems to work:

                let paths = paths.iter()
                    .map(|path| path_remove_interior_points::<_, SimpleBezierPath>(&vec![path.clone()], 0.01))
                    .fold(vec![], |a, b| path_add::<_, _, SimpleBezierPath>(&a, &b, 0.01));

Produces this:

That looks right to me.

Just calling remove_interior_points on the paths also looks right:

That's slightly infuriating: I can't reproduce the problem you're having. There are a couple of possibilities here: one is that the version of the glyph I'm using is slightly off and that's changing where the rays are being cast so that the bug isn't occurring. If it's an edge ordering bug that would make sense. I have tried a version that casts rays at all the edges to see if any produced an inconsistency with no result though.

Another possibility is something to do with the coordinate type you're using: flo_curves does let you implement the coordinate trait on any type you like, but that does have the potential for causing problems if there's some difference in behaviour or precision. 32-bit precision floats in particular have caused problems in the past. Note that this could still be a bug in flo_curves if the difference in results is reasonable (the last issue I found with 32-bit precision was an edge ordering bug, for instance).

[Logicalshift]

I updated the test to use the types from MFEKmath with the same results so that seems to eliminate that as a possible cause.

[ctrlcctrlv]

Are you able to repro with MFEKpathops?

[ctrlcctrlv]

Maybe my implementation there is faulty.

[ctrlcctrlv]

@Logicalshift I think you should try with glifparser itself, into Piecewise from MFEKmath. If that doesn't repro that's not easily understandable. But I can send you a whole directory of broken examples if you'd like.

I just pushed MFEK/pathops@0cf30a6 which lowers its accuracy so you'll be using my exact code.