essential code #4: curves
Bezier curves are one of the truly unifying concepts in 2d graphics. Points, lines, and “curves” are all beziers. This article covers a few topics I’ve found useful related to beziers: making splines in limited graphics systems (like Flash), and fitting curves to a point set.
For more bezier code, including splitting and pseudo-parallelizaton, see the NuG project.
I posted this a while ago, which explains an approach to creating splines with quadratic segments. I’ve found this approach to work in all cases I’ve tried to do splines in Flash, including in the Flash exporter of K-Sketch. My only warning is that “downsampling” from cubics to quads introduces subtle discontinuities that look, ultimately, awful. Splines are beautiful because they’re clean; when you have little inconsistencies (as introduced by downsampling), the overall effect of the spline is diminished. So I always generate splines using a quadratic method, instead of using a normal cubic method and then downsampling.
A bigger problem is: Given a set of samples, how do you fit a smooth curve? This comes up when trying to glean shapes from freehand input, and in general “beautify” freehand input.
At one time I investigated this problem. In the process I discovered a few very useful methods (essential reading) for dealing with curves:
The centripital method for guessing parameters (Lee) Fitting a k-degree spline to a set of points can be solved using least squares. This requires guessing the parameter distribution. This paper describes a unifying framework for guessing parameters.
Iterative pole curve fitting (Chambelland and Brun) Unlike least square approaches, which can only solve for control points, this method alternately solves for control points and parameter distribution. That is, it find the optimal control point/parameter combination to fit a point set. This paper also explores some methods to analyze curves — like finding foot points — that I had wondered about for some time. HALCYON GLAZE uses the exact method described in this paper for finding foot points.
This is getting into CAG territory, but this stuff is essential when working with curves. And hey, curves — freehand input, floating values, loose connections — are the future of interfaces.
simple beautification?
I was interested in whether a simple UI could be used to clean up curves. My attempt used a slider between three values:
-1: make linear
0: no fitting
+1: make curved
The actual algorithm was just a greedy fitter, using error tolerances assigned to each point (by the slider) to determine when to stop. That is, each point has a maximum error for 1-degree bezier (a line) and a 2-degree bezier (a quad) fits. If the current curve being fitted goes over the min error of the constituent points, then the fit is reset. The middle of the slider was “no allowed error for any”, which forced the fitter to just give up and spit out the points as they came in.
svn: http://resisttheb.org/rtb/fit_factory