Generating a cubic bezier curve from rough points

Question

I'm looking for a way to make my application produce smoother results in freehand mode. Right now it simply adds each mousemove points and makes a polygon out of this. I noticed modern vector applications produce bezier curves to make it look much smoother and im wondering how this is done? So how can I get the 4 points to do bezier interpolation with rough user input of a smooth curve?

Thanks

Answer 1

How about storing a new point only when you're a certain distance threshold away from your last point?

Answer 2

Something like, but not exactly like, ransac (see Ransac) might work nicely here. Ransac simultaneously finds a solution while eliminating outliers. Ransac is good when it is cheap to generate a hypothesis from a small subset of data and easy to test the hypothesis against the whole set. This is a decent fit for your problem.

The basic idea:
Loop:

1. randomly pick a small number of points from the complete set to create a bezier curve.
2. compute the distance to that curve for every point you have.
3. eliminate points that are further than some threshold.
4. <see below>
   
5. sum the squared distances of the remaining points for a score.
6. keep the solution with the best score.

To make this truly ransac, you need to find a function for 4 that solves your original problem. D'oh. That is, you need to be able to calculate a curve based on all the points that weren't eliminated in step 3. That's why I suggested the above. It is quick and easy, and might get you very close, especially since you really don't have gross outliers.

Answer 3

If you want to solve the general problem, you can use levenberg-marquardt (LM) optimization.

You want to define a bezier curve with some small number of points. You use LM to optimize the parameters of the curve (the point locations) by minimizing the squared distance to the curve for all of your points. This is your objective function, the sum of squared distances.

The trick is computing the gradient and hessian for LM. You can do this numerically without having to work out any math. Use numerical differentiation to compute the Jacobian (J) which you use to find the gradient. (The Jacobian is also used by LM to approximate the Hessian.)

Matti mentioned GSL for smoothing splines. I didn't know about GSL, but it turns out that it has implementations of LM and numerical differentiation.

Answer 4

You could also use a smoothing spline. If you are OK with GPL have a look at the GSL http://www.gnu.org/software/gsl/ for an implementation.