1

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

jmasterx
  • 52,639
  • 96
  • 311
  • 557
  • possible duplicate of [Drawing path by Bezier curves](http://stackoverflow.com/questions/2956967/drawing-path-by-bezier-curves) –  Jul 12 '10 at 04:29
  • wait, ok, so your problem isn't figuring out how to create a bezier curve from all the points you have, the problem is you have TOO MANY points, and you want to turn an arbitrary number of points into a smooth curve not necessary directly generated from all, or any of the points you take as input? – matt Jul 12 '10 at 05:47
  • Yes thats what im looking for – jmasterx Jul 12 '10 at 06:37
  • You could treat it as a signal processing problem and downsample your points (ie a time signal with two components, treat it like stereo audio or something) – Spudd86 Jul 12 '10 at 16:13
  • well firstly, I think you will find that most of those programs turn the path into a MIXTURE of strait and curved (bezier) paths, so you can have sharp corners ect. – matt Jul 13 '10 at 01:25
  • oh, and maybe look for algorithms that turn bitmaps into vector graphics. they have 'smoothness' coefficients that determine how edges are transformed in to curves ect. so they would be doing what you want to do, and would probably be an easier thing to search for. – matt Jul 13 '10 at 01:28

4 Answers4

1

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.

cape1232
  • 999
  • 6
  • 21
0

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

tkerwin
  • 9,559
  • 1
  • 31
  • 47
  • What if you throw away a large set of points that make sense, and then decide to keep a single rare out lier? – reuscam Jul 13 '10 at 00:33
0

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.

cape1232
  • 999
  • 6
  • 21
0

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.

Matti Pastell
  • 9,135
  • 3
  • 37
  • 44