search
Sunday, 2011 July 10, 08:47 — curve-fitting

blending curves

I made some progress on an old project: to make outline fonts based on some favorite old bitmap fonts, by automatic fitting of smooth curves to the sequences of dots.

(The image above is in Scalable Vector Graphic format. If you see nothing, you may – dare I say it – need to update your browser. It works in Firefox 5, Safari 5, Chrome 12, Kindle.)

Each arc is a parametric curve of the form z=integral(exp(i·F(t))), where F is a real-valued polynomial. (I use a Taylor series for the integral.)

When F is linear, the curve is a circle. When F is quadratic, the curve is called a clothoid or Cornu spiral or Euler spiral; besides æsthetic design, such curves are much used for railroads and highways, where abrupt changes in lateral acceleration are unwelcome.

The black arcs are circles, passing through maximal sequences of dots. Where two black arcs share dots, I join them with a red arc. For a smooth join, F (the tangent angle) and its first derivative (the curvature) must match. Red arcs are joined by green, then blue, brown, teal.

I stalled in November when I couldn’t see how to blend the arcs; this week I had a new idea, which works better than I expected. The collection of constraints requires F in the blending arcs to be quartic (fourth-power polynomials), and I was afraid that they’d be too wiggly.

Some flaws remain:

A long blending arc sometimes misses its dots, failing the project’s primary criterion; I commented out the test for this, because it regularly crashes for a reason that so far eludes me.

Some glyphs have unnecessary wiggles; for a mild example, in this ‘s’ a red-green segment at the top looks too flat. A future version will consider many composite paths in parallel, choosing that which minimizes the first derivative of curvature (second derivative of F).

• comment by Anton — Sunday, 2011 July 10, 11:27

I also haven’t yet provided for loops like ‘O’.

• comment by Anton — Sunday, 2011 July 10, 21:29

In a path composed of clothoids, the first derivative of curvature has discontinuities but no extrema. That feature didn’t hit me until today.

• comment by Anton — Monday, 2011 July 11, 14:24

Here is the ‘s’ pruned to show only those arcs of which at least part remains in the final composite.

• comment by Dan Weinreb — Sunday, 2011 July 31, 10:51

It looks fine on Google Chrome 12, just for reference.

This is cool. Are you going to do the rest of the alphabet?

• comment by Anton — Sunday, 2011 July 31, 12:01

Of course! My goal has always been to publish a font that matches all the characters of the original.

• comment by Anton — Wednesday, 2013 April 3, 23:50

Where I said “minimizes the first derivative of curvature”, I meant “minimizes the integral of the square of the first derivative of curvature”.

Subscribe without commenting