Very short segments lead to many extraneous points

[simoncozens]

Consider a glyph designed for CNC routers which cannot change direction quick enough to draw sharp corners; you have to add tiny line segments to help change direction:

Sample glif:

<?xml version="1.0" encoding="UTF-8"?>
<glyph name="A" format="2">
        <advance width="600"/>
        <unicode hex="0041"/>
        <outline>
                <contour>
                        <point x="0" y="150" type="move"/>
                        <point x="100" y="150" type="line"/>
                        <point x="100" y="141" type="line"/>
                        <point x="0" y="0" type="line"/>
                </contour>
        </outline>
</glyph>

Unfortunately when this is stroked with MFEKstroker, you get lots of weird points:

Which (when combined with #15) makes the outline really bad...

Mitigating #15 will fix the problems in the top right, but the bottom right is still urgh.

[simoncozens]

Cc @rosawagner

[ctrlcctrlv]

please post the full MFEKstroke command line which generated this

[simoncozens]

./target/debug/MFEKstroke CWS --width 75 --input cnc.glif --output cnc-stroked.glif

[ctrlcctrlv]

@simoncozens For such a small patch, my #15 patch to flo_curves sure is providing a lot of benefit even to things I wasn't thinking about at the time:

The difference between left and right is just increased strictness of accuracy. I played around with it a bit to try to make it perfect, but didn't quite get there I'm afraid. Maybe another time. However, certainly this is much better than what you've got.

[ctrlcctrlv]

@simoncozens How does this look?

OK, I did cheat a bit.

While thinking about the problem (how can I get these circle arcs to behave?) I realized, "hey wait a minute, I just want full circles at every place the path ends…that is to say, I want all joins treated as caps. So, why don't I just do that and let the overlap engine deal with it?"

And so that's what I did. Can I add that as an option and close this?

[ctrlcctrlv]

For more information:

FontForge is able to perfectly join the path. I'm not seeing any downsides to this method, and compared to somehow re-adding information about the original points to fix_path—the function in VWS.rs that actually adds the joins and therefore needs to be able to determine a circular arc's center—very simple. I'm quite pleased with it.

[simoncozens]

Yeah, that’s a very nice approach.

[ctrlcctrlv]

@simoncozens You can now simply provide --segmentwise to MFEKstroke. In case you are hooking into this library directly, the commit https://github.com/MFEK/stroke/commit/7fcf9d0dde09e1451f3a406b137b85d5ea523b11 may be instructive.

[simoncozens]

With that change, I'm getting Empty piecewise has no start point.

equal.glif:

<?xml version='1.0' encoding='UTF-8'?>
<glyph name="equal" format="2">
  <advance width="554"/>
  <unicode hex="003D"/>
  <outline>
    <contour>
      <point x="454" y="422" type="move"/>
      <point x="100" y="422" type="line"/>
      <point x="100" y="423" type="line"/>
    </contour>
    <contour>
      <point x="454" y="222" type="move"/>
      <point x="100" y="222" type="line"/>
      <point x="100" y="223" type="line"/>
    </contour>
  </outline>
</glyph>

Command line: MFEKstroke CWS --segmentwise --input equal.glif --output equal-stroke.glif --width 25

[ctrlcctrlv]

@simoncozens I think I found the issue. See https://github.com/MFEK/math.rlib/commit/26e0073c57d75e9eb963177614332bb567907692

He was using whole units as a check for colocated handles, which is way too large I think.

It works for me now.

[RosaWagner]

Using --segmentwise I am still having this issue I am using this command: fontmake -f --filter 'ufostroker::StrokeFilter(Segmentwise=True,Width=40,pre=True)' -g Relief.glyphs --filter DecomposeTransformedComponentsFilter --overlaps-backend pathops -o ttf

[ctrlcctrlv]

That strikes me as perhaps being caused by rounding to integer done for TTF format?

[isdat-type]

From our own tests, the Expand Stroke function in FontForge seems to remain the best rendering from our skeletal / monolinear drawings, see screenshots (even slightly better than Noodler script on Glyphs App and similar to Outliner script in Robofont). Can Ufostroker use the script library behind Expand Stroke in FontForge to improve the TTF / Fontmake / MFEK export process? Apparently @ctrlcctrlv already mentioned similar remarks earlier.

[ctrlcctrlv]

@RosaWagner I think the behavior you are seeing is expected because you're using oval shaped caps/joins and not round ones.

Unlike a lot of similar software, MFEKstroke supports both.

Make sure to use JoinType::Circle and CapType::Circle, not Round. @simoncozens will know if his Python thing supports the distinction.

[RosaWagner]

Thanks @ctrlcctrlv I gonna try that and give you feedback

[simoncozens]

It's not going to work because I didn't know about circle - when I looked at the code it only had round and square. I'll add support for that.

[simoncozens]

OK, please try upgrading to ufostroke v0.2.4 and setting pre=True,Startcap="round", Endcap="round", JoinType="round" in your fontmake command line.

[RosaWagner]

Still with the weird segment joins:

[ctrlcctrlv]

Did you misread @simoncozens ? You need "circle", not round.

[ctrlcctrlv]

"Circle" → circular arcs. "Round" → elliptical arcs.

To be clear, it's possible "circle" is broken. I'll look into if so. But please confirm you are using the right one.

[simoncozens]

I’m easily confused and gave Rosalie bad information. Trying again.

[RosaWagner]

More points, still not smooth

[ctrlcctrlv]

Okay. Is this a precision issue? Did you do some round before showing me that?

[ctrlcctrlv]

Because "more points" isn't necessarily considered by me to be a problem, unless those are their actual locations at f32 accuracy…I had planned for Bézier simplification to be part of MFEKpathops by the way—unfortunately, MFEK Foundation Grant № 4, Series of 2022 badly fell through, @prajwalprabhu wasn't able to finish it. It's possible I'll do it myself. One of the ways to simplify a Bézier path (to the degree it's acceptable for type design) is to try to draw elliptic arcs between the segments as well as the normal best-fit thing you're doing, to see which is better. If the elliptical is better, you can take segments of your overall path and express them as elliptical arcs, which are much easier to turn into Bézier at n accuracy.

MFEK Fndn №4 of 2022 will get done somehow. Either I will reassign it or do it myself (revoke it).

[simoncozens]

More points isn't the problem. "Still not smooth" is the problem. And OpenType points need to be rounded.

[ctrlcctrlv]

Thank you, I will look into. Just needed to confirm that. Can I have the exact input A shape?

[ctrlcctrlv]

(Also I consider this a new issue so will open a new one and not reopen this one)

[ctrlcctrlv]

Reopened per https://github.com/MFEK/math.rlib/issues/27#issuecomment-1105909028.

[ctrlcctrlv]

Good news.

I believe I just had the insight that will fix this.

The problem always keeps coming back to https://github.com/MFEK/math.rlib/blob/bd3ee6bd3b30298a6c7f2b1db6877b24f3c95c37/src/glyphbuilder/mod.rs#L151, which takes a circle and two tangents.

It contains odd language like:

        // we shoot rays from the right of both of the tangents to find a center of the circle we're
        // going to make an arc of

You all know I have no formal math training and that's why this library was my project's very first grant, before I was doing the foundation thing. So take my opinion with a grain of salt—but these functions look highly unorthodox to me. And every time I fix a case, I break another.

I'd note something worrying I found in the research… @MatthewBlanchard wrote that his elliptical joins/caps were actually rare across software. They don't exist in PostScript.

That might mean they aren't reliably possible. Might.

Here's what I'm going to do: tear out the function circle_arc_to. Totally rewrite it. Do something Matt would probably hate if he were still on this project: use Skia's conicTo to make a circular arc:

I'll use the ability it has to convert conics to cubic Béziers, although not directly, you must go through quads, I implemented it in glifparser.rlib.

If this fails, we're not "screwed" as it were. The code for CWS right now is based heavily on VWS.

It's possible that Matt recognized that certain things help VWS while sacrificing accuracy, but these things hurt CWS.

So, I could change the way CWS fundamentally works—by making it call Skia instead.

Your input is appreciated because I realize that using Skia just for finding arc paths is…unorthodox, but I'm out of other ideas.

[ctrlcctrlv]

Oh, not quite out of ideas after all!

I hadn't realized that Kurbo contains one of these:

pub struct SvgArc {
    pub from: Point,
    pub to: Point,
    pub radii: Vec2,
    pub x_rotation: f64,
    pub large_arc: bool,
    pub sweep: bool,
}

I think that I can describe the path we need with a kurbo::SvgArc as well as I could with an SkPath with a conicTo. I'll definitely try Kurbo first as it's less destructive to expectations (no need to force you to compile with Skia if you need CWS).

[simoncozens]

I'm not convinced this is the problem in this case.

More important than the construction of the curves is the question of what to do about short segments. When expanding a stroke, any short segments which lie within the "zone of influence" of expansion should be subsumed into the construction and should not create additional points. Here's a rough sketch of what I would expect the output to be:

Note that although there is a short horizontal segment, the output should reflect the ideal path expansion in which this segment is subsumed. Of course you already manage to do this overlap correction for the point marked in blue above:

but not for the curve at the top.

By all means play with arcs, but before constructing the arc, you need some kind of path sweeping and overlap filtering to make sure the arc is not more complicated than the user expects it to be.

[ctrlcctrlv]

@simoncozens Sorry, I still don't seem to quite understand how you get the output you get. It seems like you're using some kind of path overlap removal.

MFEKstroke doesn't do anything similar to Skia PathOps.

For explanatory purpose, I decided to make this image to show the problem. Everywhere where circle joins would normally be drawn, I drew lines instead, and I put a red guide path for the original path:

Here's a paint drawing I did of what the first two joins should do:

As you can see our conceptions are so different so I'm not sure why

[simoncozens]

I'm not describing what I can get, but what I want. I think algorithms for type designers have to prioritize aesthetics over mathematical correctness, and that means you may need to approximate and smooth out certain rough edges to get the best result; I think the most aesthetically correct result here is one on-curve point at the apex rather than two. Trying to make a curve at 1 and a curve at 3:

and joining them to a line (or worse, a curve) at 2 is going to make for really nasty curvature continuity issues.

[MatthewBlanchard]

I think this is actually a joining issue, though. FontForge's output looks great and respects the tiny line.

[ctrlcctrlv]

Thanks for confirming I'm on the right track @MatthewBlanchard, very appreciated. :)

Speaking to what @simoncozens wants—yes, I agree, what you want, having the result of a union'd stroke output, is outside the scope of MFEKstroke. It's inside the scope of math.rlib—sort of—but it's more of a job for MFEKpathops (BOOLEAN subcommand).

I expect to eventually move some of the more "nuts and bolts" parts of MFEK/pathops→src/boolean.rs into math.rlib, especially the calling convention based on EnginePathOp.

If you need that moved sooner rather than later please let me know. The reason it hasn't moved yet is I want to be able to give more solid recommendations as to the cases one should prefer EngineOp::Skia over EngineOp::FloCurves. For now MFEKpathops-BOOLEAN is a highly alpha/testing command—I consider the functions in math.rlib more stable.

[ctrlcctrlv]

Oh, and the second thing you want, the removal of short segments, and just drawing an arc across the larger join, is also within scope, but not for segments of the length I'm fixing right now, for shorter ones. FontForge's output is good, and these ones should still have a thin line.

[MatthewBlanchard]

Re: the circular cap problem that comment you quoted in a post above does have something to do with this.

I think that the intersection point it's finding to push the handles out along is clearly wrong (the green point at the intersection of the line segments extending the path along it's (-)derivative. Don't have a ton of time rn to look into this further but that's where I'd start.

Also while I think segmentwise might work it's a hack that's gonna find edge cases in overlap removal algorithms like nothing else.

[ctrlcctrlv]

Also while I think segmentwise might work it's a hack that's gonna find edge cases in overlap removal algorithms like nothing else.

Yes, that's why I reopened this. Please see my comment in https://github.com/MFEK/math.rlib/issues/27#issuecomment-1105909028:

This issue is getting closed because --segmentwise was a hack which I thought would be fine, but circular arcs are not perfectly representable as cubic Bezier curves.

So, any overlap merge would struggle with these two overlapping Bézier curves which are almost—yet not quite—equivalent.

Issue #16—not #17—is getting reopened because segmentwise is not an appropriate fix.

I will then try to fix once again the path builder method of creating stroke outlines.

Thanks for user patience.

See, I had to find out the hard way what you already knew, hehe.

I believed originally that segmentwise would lead to no bugs because we already have crazy internal paths that resolve just fine. I did not understand that I was playing with major precision-error fire.

[ctrlcctrlv]

@MatthewBlanchard Also, your belief is my belief as well. But I do have a question. Why, when you wrote this code, did you not keep track of what point in the original we're attempting to join?

Why do the join functions have to calculate it? That seems flawed.

That's why I wrote above:

It contains odd language like:

   // we shoot rays from the right of both of the tangents to find a center of the circle we're
   // going to make an arc of

“Odd language” was my charitable way of saying that this type of joining point calculation is highly uncommon across libraries. I read Skef's implementation plus another implementation and yours is unique in this way.

[ctrlcctrlv]

If there's a reason not to keep track of the point we're on I'd like to know it before I change the code such that all join functions know which point on the original curve they're joining right now. (For circle_arc_to it is the center of the circular arc join we wish to draw.)

[MatthewBlanchard]

Nope you can do that instead it's probably more sound. It's going to find the same point in theory.

[ctrlcctrlv]

Thanks for answering. I think that the error is precision in the calculation, not that there's anything wrong with the maths.

Note for example this image I posted November last year before I came up with segmentwise:

I knew exactly what was wrong with this but had no way of figuring out why your shooting rays method was not working.

I even drew out the rays and to me it looks like you're right they should find the center.

But I think precision is preventing them from doing so.

[ctrlcctrlv]

(Turns out I might be more capable at this stuff than I let on :stuck_out_tongue_closed_eyes: which is good given I have to maintain it)

[MatthewBlanchard]

Remember why I did this. You would need to do a significant amount of book keeping to make sure that you can match up the join to the original point I think. Or do the joining as you create the path and not in a separate pass after. The second is better but a non insignificant amount of work would be required.

The approach in theory works on any path with disjoint primitives.

[ctrlcctrlv]

@MatthewBlanchard I've been working on the second one, and it's requiring a big API change, but overall I think it'll work.

#[derive(Clone, Debug, PartialEq)]
pub enum JoinOperation {
    ArcTo,
    CircleArcTo,
    LineTo,
    MiterTo,
}

#[derive(Clone, Debug, PartialEq)]
pub enum CapOperationType<'a, PD: PointData> {
    CapWithJoin(glifparser::glif::JoinType),
    CustomCapAcross{ cap: &'a Glif<PD> }
}

#[derive(Clone, Debug, PartialEq)]
pub struct CapOperation<'a, PD: PointData> {
    pub op: CapOperationType<'a, PD>,
    pub from: (f32, f32),
    pub tangentf: f32,
    pub to: (f32, f32),
    pub tangentt: f32,
    pub point_on_original: Vector,
}

 Cargo.toml                         |   4 ++--
 src/bezier/mod.rs                  |   2 +-
 src/glyphbuilder/mod.rs            | 151 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++----------------------------------------------------------------
 src/variable_width_stroking/mod.rs |   6 ++++--
 4 files changed, 94 insertions(+), 69 deletions(-)

[ctrlcctrlv]

Those structures aren't final—literally don't have a prototype yet, just placeholders. :)