Add documentation of the algorithm

[behdad]

Here's the original sketch of the algorithm I wrote to James in July:

Hey,

Here are my thoughts of a new, IMO much more elegant approach:

- Convince yourself that if we cut the curve into n segments with equal
parameter lengths (ie, cut at t=i/n), then each of the new points are placed
in the middle of the control points on their two sides,

- For each of the resulting cubic's, we are going to choose a control point
that will be the one used for the quadratic; let's call this new point the
corner.   For sub-curve i, use the two existing control points to come up with
two candidates for the corner.  The candidates are chosen such that the
resulting quadratic curve will have the same tangent as the cubic at the
corresponding endpoints.  Ie, for a sub-curve with p0,p1,p2,p3, we find q0 and
q1 such that:

  (d Cubic(p0,p1,p2,p3) / dt)[t=0] = (d Quadratic(p0,q0,p3) / dt)[t=0]
  (d Cubic(p0,p1,p2,p3) / dt)[t=1] = (d Quadratic(p0,q1,p3) / dt)[t=1]

Then, we choose the corner q to be ((n-i)*q0 + i*q1) / n where i is the index
of the segment.

This ensures that the resulting quadratic spline has the same tangents as the
original curve at the endpoints.

  - After choosing corners, position the on-curve points to lie in the middle
of the neighboring corners.  Ie, don't encode them in the glyf encoding.

The only part I have not figured out is the error function.  After error
function is figured out, just increase n until feasible solution is found.

Do you think you can experiment with this?

Cheers,
behdad

to which James responded:

Okay, well I just wanted to make an observation that I thought was interesting. Not sure if you noticed but I think your comparison

(d Cubic(p0,p1,p2,p3) / dt)[t=0] = (d Quadratic(p0,q0,p3) / dt)[t=0]

comes out to

2 (q0 - p0) = 3 (p1 - p0)

or

q0 = p0 + 3/2 (p1 - p0)

with a symmetric equality using p3 & p2 for the other end of the curve. This is cool because it's basically the method I was using originally to patch the intersection method, except now we interpolate over time between q0 and q1 instead of always taking the midpoint.

and I replied:

Yes, I came up with this as a way of generalizing your method :)

[anthrotype]

this is very good, thanks for sharing!

[behdad]

There are also two other insights that led to the development of the algorithm:

• Curves will remain interpolation-compatible if at every new on-curve point, the ratio of the length of the distance to the two control points on its sides are the same in all masters,
• Because of the implicit-point optimization in TrueType glyf table encoding, an algorithm that only produces implicit off-curve points is very competitive. Ie, a conversion to 5 segments that use implicit-points only take the same storage as a conversion to 3 segments without implicit-points.