Sketching Clothoid Splines Using Shortest Paths

Ilya Baran     Jaakko Lehtinen     Jovan Popović

We obtain high-quality piecewise-clothoid curves from hand-drawn sketches.

Paper and supplement: PDF (Eurographics 2010)
Video: MOV (3MB, no sound)
Code: Cornucopia is a rewrite of my original prototype. It's about 8x faster than timings in the paper. To just play around, here's a Windows binary.


Clothoid splines are gaining popularity as a curve representation due to their intrinsically pleasing curvature, which varies piecewise linearly over arc length. However, constructing them from hand-drawn strokes remains difficult. Building on recent results, we describe a novel algorithm for approximating a sketched stroke with a fair (i.e., visually pleasing) clothoid spline. Fairness depends on proper segmentation of the stroke into curve primitives -- lines, arcs, and clothoids. Our main idea is to cast the segmentation as a shortest path problem on a carefully constructed weighted graph. The nodes in our graph correspond to a vastly overcomplete set of curve primitives that are fit to every subsegment of the sketch, and edges correspond to transitions of a specified degree of continuity between curve primitives. The shortest path in the graph corresponds to a desirable segmentation of the input curve. Once the segmentation is found, the primitives are fit to the curve using non-linear constrained optimization. We demonstrate that the curves produced by our method have good curvature profiles, while staying close to the user sketch.

Back to my homepage