Premium
Sketching Clothoid Splines Using Shortest Paths
Author(s) -
Baran Ilya,
Lehtinen Jaakko,
Popović Jovan
Publication year - 2010
Publication title -
computer graphics forum
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.578
H-Index - 120
eISSN - 1467-8659
pISSN - 0167-7055
DOI - 10.1111/j.1467-8659.2009.01635.x
Subject(s) - sketch , segmentation , shortest path problem , computer science , curvature , arc length , graph , spline (mechanical) , mathematics , algorithm , artificial intelligence , computer vision , theoretical computer science , geometry , arc (geometry) , structural engineering , engineering
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.