Towards a replacement to the «Expand Stroke…» function

[ctrlcctrlv]

I, and others, have reported many Expand Stroke bugs, which no one seems to know how to fix. (For example, #3694, #3264, #3242, #3240, etc.)

Expand Stroke bugs are rarely ever fixed. I hope @skef doesn't hope me quoting him in some private correspondence to help make my point:

I'm wary of [Expand Stroke]. It seems like GW approached a lot of the tricker spline code by tinkering rather than drawing on theory or established algorithms. I stared at #3432 for a while (for example) after finding that non-termination condition and still don't have much of an idea of how the algorithm is supposed to work

@skef is much better at Bézier spline math than I am, so if he doesn't understand how GW's algorithms work, I stand no chance of doing so.

The function is also aging, and to think that we could extend it is dubious at best. For example, we might want to make it so that you could vary the width of points along the spline as is possible with the width tool in e.g. Illustrator or via multiple plugins (Letterink, etc) to Glyphs.app or in Inkscape via «Power Stroke».

My questions are:

• What “established algorithms” would help the situation?
  • Perhaps InkScape's, which seems very Robust? Perhaps Noodler's, used by Glyphs.app? Something else I'm not aware of?
• Is it even possible to replace the «Expand Stroke…» dialog wholesale?
  • Obviously at first we'd want to have them side-by-side until we replicated all the functionality.

[skef]

Ideally a "stroke" would be a sequence of potentially joining Bezier segments, which may be lines or curves. The "y" in #3264 shows how it's not always that simple. Anyway, the way this stuff works in general is that you take each segment and deal with it separately and then merge the results. The artifacts the common FontForge error refers to as "fragments" are, I believe, per-segment lines/curves entities (either segments or multi-segment paths -- I'm not sure).

The general idea is to produce an offset of each side of the stroke. It's provably impossible to produce the exact curves in the general case, but you pick a non-perfect degree of approximation to fall within. The most widely discussed and cited offsetting algorithm seems to be Tiller-Hanson but many other approaches have also been developed.

Of course, the theory of offsetting on its own doesn't tell you how to implement a Calligraphic (rectangular) pen. I've glanced at GW's code enough to know that it's based on curve approximation rather than direct calculation. If I were asked this question in an interview, I would offer an algorithm like:

1. Iterate through points on the segment at some interval
2. For each point x calculate the normal angle a at that point.
3. Call d = dist(a) to get a configurable distance away from the point based on the angle. (This is where Circular/Calligraphic/Polygon come in. The angle at the point gives the distance away.)
4. Use a and d to calculate an offset point nx
5. Pick a Bezier order and do a least-squares-fit for a curve of that order on the calculated points.
6. Reduce the higher-order Bezier curve to multiple Cubic/Quadratic segments with one of the standard algorithms for that purpose.

And there you have your custom offset-curve for one side of a segment.

Now, however, you have to join all of these individual segments together, with caps and joins of the selected types. Seems like there would be lots of ugly special cases!

[skef]

And ... think about "y" in #3264. It has lines that overlap but that end at different places. How does/should that interact with "join style"? Maybe there should be a pre-processing step to eliminate those. But what if they don't overlap exactly, but are very close?

Ugh.

[ctrlcctrlv]

Just speaking as someone who makes fonts in FontForge, the "y" case is a really natural thing to draw, and the fact that I can't stroke paths like that is regularly annoying and requires me to do workarounds like split up my paths

[ctrlcctrlv]

InkScape has no trouble with it. Perhaps we should think of this as two issues, the regular path stroking and the calligraphic path stroking, which I seldom use due to how buggy it is.

[skef]

Hmm, I've presumably already failed my interview. The line relevant line swept by the polygon often won't be at the normal angle. So you have to consider the shape and angle together and produce a distance and angle based on the "nib" shape. I think what you want is to "move" an imaginary line at the parallel angle (not the normal angle) towards the nib until they intersect, and then that intersection point gives you the distance and new angle for nx.

[ctrlcctrlv]

PS: It seems like what we want to achieve is called in mathematics a Minkowski sum, but doing Minkowski sums of curves seems non-trivial.

[ctrlcctrlv]

(Or impossible.)

[ctrlcctrlv]

cc: @mekkablue

[frank-trampe]

@ctrlcctrlv, I made a fairly big set of changes to splineoverlap.c a year or two ago to add relational geometry and to eliminate a lot of failure cases. That is likely familiar and accessible territory. The stuff in splinestroke.c has mostly gone unmaintained since George disappeared. We can certainly look at it in depth, but let me give some background.

Overlap removal was once a total disaster. We considered using lib2geom from Inkscape, but there were several deal-breakers. One of them was that certain values or entities required conversion, such that there was some chance that removing overlap with no overlap present would still change the splineset. Accordingly, I put a bit of work to get the overlap removal routines to work most of the time. Much of the effort involved adding relational geometry (using pre-removal adjacency in post-processing, essentially). Apparently, those efforts were not perfect, but the code is now familiar enough to me and clean enough that I can probably solve the problems that originate in splineoverlap.c (#3694, for example).

splinestroke.c, though, is a different matter. It is a bit more broken and a bit less familiar to me. The fact that so few things actually work correctly, combined with the fact that there is no null case in which it is not expected to produce changes, makes it easier both to make substantive changes and to use a "non-native" tool for the stroking. Even with that, the complexity of mapping back and forth between vastly different data structures might be a deal-breaker. We probably need to figure out how much is broken. In particular, there is some chance that a small restructuring would let us delegate more of the stroking process to the more fixable overlap removal routines.

I will look at both of these things in depth next week.

[ctrlcctrlv]

@frank-trampe :

First of all, thanks for taking a look at #3694. I wrongly categorized it was an expand stroke bug when it's really an overlap bug, as the error message says.

I might be willing to add lib2geom support to FontForge…but I wouldn't go so far as to ask that my lib2geom support phase out the legacy FontForge stroker, considering there are many reasons people might want to use it.

I'm not promising to do this (although I'll certainly give it a try), but I'm just asking if I, or I and @skef working together, did do it, whether or not you'd accept it:

☞ Proposal

• Add a new element to the Expand Stroke dialog, “Method”—«Legacy» or «2Geom».
• Add a new compile time option, disabled by default, --with-lib2geom.
• Add to the documentation that if you have trouble with “Expand Stroke”, try compiling with 2Geom.
• Make new files 2geom.c and 2geom.h to handle the new Expand Stroke functionality.
• Perhaps, in 2Geom mode, add UI elements related to dashed lines, which is something I need for another project. But at the very least we'd want to replicate everything as it is in 2Geom mode, at least for the circular brush!

[ilyaza]

I want to say something extremely simple about rectangular pens (or, more generally, Minkowsky sums with polygons). However, I do not think this was already discussed:

• Given a shape, take 4 suitable parallel translations of the shape.
• Remove overlaps.

Then this gives “about 99%” of the Minkowsky sum. What is missing are “the joiners” corresponding to the parts of the initial contour going approximately in the direction of the sides of the rectangle. In the simplest cases, if one knows the points where the tangent goes in the corresponding direction, it is enough to take union with the corresponding rectangles, and remove overlaps.

Moreover, I have a conjecture (I did not wake up yet, so cannot check it):

• To construct these joiners, it is enough to have code which calculates the Minkowsky sum with a side of the polygon (if the polygon is convex???).

If the conjecture is false, then still having a code to add a segment is enough in the case of a parallelogram: a parallelogram is a Minkowsky sum of its two sides, and addition is associative: so just add one side, then another.

[ilyaza]

Right: for Minkowsky sum A⊕B of B and C, the pair (b,c) of points b,c on boundaries of B and C does not contribute to the the boundary of A⊕B unless there are tangent lines at b and at c which are parallel. (Here we assume there are many tangents at a corner — as usual.)

So if C is a polygon with corners cᵢ, then this would construct the sum:

• Take translations of B by cᵢ⸣s.
• Mark points bⱼ which are corners of B and points on the boundary of B with tangent lines in the direction of sides of C.
• Take translations of C by bⱼ⸣s.
• Remove overlaps between all these translations.

[ilyaza]

Oups, I left out one case: B may have whole pieces of the boundary which go in the direction of a side of C. So there should be another bullet point above (trivial to implement if C is a rectangle; simple if C is convex).

[ilyaza]

No, what is said above is not 100% correct: it finds all the pieces of boundary correctly, but it may have some “junk” inside. For example, consider a Minkowsky sum of two straight perpendicular segments…

[skef]

Incidentally, this past day I've been looking at lib2geom and its integration with Inkscape. Unfortunately they've made some design decisions that go against typical FontForge conventions.

Mainly there is no provision for any kind of "payload", hard-coded or not, in the Geom:: Bezier points, and more generally no reliable notion of point identity. One effect of this is that round trips through 2Geom operations reset Inkscape node types. In FontForge you'd also lose generalized types, some other stuff like point names.

It's an interesting question how much work it would be to improve round trips through lib2geom, and whether any of those folks would be interested/amenable. But there's no easy fix.