WIP: support for quadratic curves

[typemytype]

There are some not implemented errors, mostly related to support for quadratic curves.

While splitting and merging existing curves there are three scenarios possible:

• the beginning of curve is needed
• the ending is needed
• a part somewhere in the middle is needed

A quadratic curves exists of one or more sub quadratic segments, in fontTools those can be created with decomposeQaudraticSegment(...)

Therefore the inputContour.split(tValues) have to split the quad curve nicely in parts, without adding points (by decomposing the curve).

This is work in progress, any help is welcome!

[zjusbo]

Any updates on this issue?

[typemytype]

As stated: any help is welcome. This is not a top priority issue for me...

[typemytype]

I had a second look and committed a working version in: https://github.com/typemytype/booleanOperations/tree/quadratics

but there are some serious considerations to thinking about:

Quads with more then one off curve points will have to add the implied on curve point, as there is no other option to split a quad with x-amount off curves in just 2 curves.

This means that an overlap with an outline of 2 curved parts (tail of a Q) not only adds the 4 intersection point but also adds a maximum of 8 implied on curves. That makes adding 12 on curves, which is not nice at all...

The current state of the quadratics branch adds those implied on curves, pathOps also add those implied on curves.

Maybe a different quadratic splitting must be possible:

• only 2 curve parts after a split
• by re-curving?
• re-position the off curve points, even add 1 or 2 to make the curve work...
• avoid adding the implied on curve point

any assistance or help is appreciated :)

cc @behdad @anthrotype @justvanrossum

[typemytype]

to clarify and some visual explanation:

The implied on curves on the original curve are required in the splitted quadratics. This is unavoidable but this is also causing much bigger problems

the source:

after a union the intersection points are added but also the original implied on curves became fixed on curves:

This action adds 12 on curves point and 8 off curves, from booleanOperation point of view this is not nice. Add rounding to all those points and your tail of the Q became a monster...

So my questions for the smart quad friends is: is there an other way to split a quad at a given point, t-value without adding those previous implied on curve points.

Ive already investigated to add lots of off curve point but this is not sustainable as this could be really lots of off curve points if the split request is close to an implied on curve point.

thanks

(this is the code example drawing: https://gist.github.com/typemytype/d699cdc8b08c44b4f8584ee5d09373f8)

[anthrotype]

Maybe you could elevate the quadratic spline to a cubic Bézier curve using the algorithm in googlefonts/cu2qu#29, split the cubic at intersection points and then convert the remaining segments back to quadratic using again cu2qu.

[typemytype]

this only works with one super heavy assumption: it was originally converted from a cubic...

this does not work for the "o"-like shape without any on curves

[anthrotype]

TrueType quadratic curve segments with implied on-curve points can be thought of as quadratic B-spline curves. If we know the t parameter for a point on a B-spline curve (i.e. your intersection points after clipping), it should be possible to subdivide the curve into two B-spline curves, one on [0,t] and the other on [t,1] using the De Boor algorithm (a generalization of De Casteljiau algorithm):
http://pages.mtu.edu/~shene/COURSES/cs3621/NOTES/spline/B-spline/subdivision.html

That website contains other useful notes about b-splines (see "Unit 6" of http://pages.mtu.edu/~shene/COURSES/cs3621/NOTES/)

It's been a while since I first studied these topics, I forgot most of it..
The idea basically would be, given a TrueType qcurve segment (with implied points) and a point P that lies on that curve (i.e. an intersection point), we want to split the qcuve segment into two qcurve segments, by adding an on-curve control point at P. Thus we need to

• find the t value for the point P on the curve
• represent the TrueType qcuve segment as a quadratic B-spline
• use De Boor algorithm to subdivide and get the control points of the two B-spline curve segments [0, t] and [t, 1].

I remember I also found quite useful this book by G. Farin, "Curves and Surfaces for CAGD" https://www.amazon.com/Curves-Surfaces-CAGD-Practical-Kaufmann/dp/1558607374/

I hope this helps...

[anthrotype]

there's a C++ library called tinyspline for manipulating B-spline curves, which comes with (SWIG-generated) python bindings

https://github.com/msteinbeck/tinyspline/blob/master/examples/python/quickstart.py

[anthrotype]

hm.. actually it's not enough to apply De Boor algorithm and subdivide a single B-spline into two segments, because after the split the "knots" in the resulting segments may no longer be uniformly spaced and thus we won't be able to convert them back into TrueType qcurve segments -- where the "implied" oncurve points, aka. "knot points", must be separated from each other by equal t intervals.
In order to restore such uniformity in the knot vector of the split B-spline segments, my understanding is that we may have to insert several additional knots at uniform intervals, which means the number of control points would also increase by the same amount (if we keep the degree of the curve unchanged).
And while inserting knots is lossless as regards the shape of a B-spline curve, removing knots is a lossy approximation operation (quite a complex one, I imagine).
I'm not sure if this is all worth the effort honestly.. Splitting the quadratic B-spline into its individual quadratic Bezier components (by turning the implied knot points into explicit on-curve control points) in the vicinity of the clipped intersection points (which is what you/pathops seem to be doing already) seems to be the easiest and safest (and matematically correct) solution to the problem.

EDIT: I'd love to be proven otherwise, of course ;)

[behdad]

You need to insert an explicit on-curve point adjacent to wherever the curve is cut. There's no way around that.