Sign in to follow this  
Cornstalks

Algorithm for "grabbing" a Bezier spline/cubic Bezier curve

Recommended Posts

I'm just getting into Bezier splines, and I'm okay with defining them, but now I'd like to start manipulating them. Each segment of my spline is a cubic Bezier curve, with a start and end point and two control points. Essentially, just imagine how many vector editors, like Inkscape or Illustrator, create Bezier splines by creating a series of cubic Bezier curves.

I'm interested in being able to "grab" my Bezier spline/curve and "dragging" it around, much like if in Inkscape you click and drag on the curve itself (not on one of the points), and it auto-manipulates the necessary control points.

That is, if I have a Bezier spline S, made up of three cubic Bezier curves B1, B2, and B3, and I have a point P which I know is on B2, what algorithm can I use to determine new control points for B2 such that B2 passes through P', where P' is a "moved" P (i.e. if I move P, I want to determine the control points needed for B2 to continue passing through this moved P)?

I'm not sure if there's a term to search for here, but I'm kinda stuck here.

Share this post


Link to post
Share on other sites
Ideally you will draw the control points and let the user drag them independently. To move the whole curve the user would type Ctrl-A to select All and then could drag any point to move the whole curve.

You may prefer Catmull Rom splines as they feature control points that lie on the curve (just the span 1 to 2), where Bezier defines a control polygon and only the endpoints 0 and 3 are on the curve). You can convert between them with a formula that is not too bad (see [url="http://www.cemyuksel.com/research/catmullrom_param/catmullrom_cad.pdf"]Figure [/url]4).

Share this post


Link to post
Share on other sites
My google-foo has improved and I think googling "dragging Bezier curve" and "Bezier curve through point" are some of the better things to search for, for any future readers. I've found a few good sources, none of which I've had the time to implement, but I've skimmed them and I think they have my answer:

[url="http://polymathprogrammer.com/2007/06/27/reverse-engineering-bezier-curves/"]Reverse engineering Bezier curves[/url] (given 4 points q0, q1, q2, q3, find points p0, p1, p2, p3 that create a Bezier curve that pass through all q points)
[url="http://stackoverflow.com/questions/4838695/bezier-curve-through-three-points"]Bezier curve through three points[/url] (this seems to be the method Inkscape uses, and I'll probably try something similar)
[url="http://stackoverflow.com/questions/2316865/drag-a-bezier-curve-to-edit-it"]Drag Bezier curve to edit it[/url]
[url="http://math.stackexchange.com/questions/53819/changing-a-bezier-curve-by-dragging-a-point-on-the-curve-itself-rather-than-a-co"]Changing a bezier curve by dragging a point on the curve itself rather than a control point[/url] (links to item #2, as well as another solution in C#)

Share this post


Link to post
Share on other sites
[quote name='Catmull Dog' timestamp='1347372170' post='4978889']
Ideally you will draw the control points and let the user drag them independently.
[/quote]
Not in my application. I want to hide the control points (and if I ever decide to expose them, I still want the user to be able to drag the curve itself). As for why: it's for phones/tablets, and I'm afraid exposing the control points will clutter an already small screen.

[quote name='Catmull Dog' timestamp='1347372170' post='4978889']
To move the whole curve the user would type Ctrl-A to select All and then could drag any point to move the whole curve.
[/quote]
That's just moving the entire spline, which is simple. I'm not talking about moving the curve/spline together as whole; I'm talking about "dragging/grabbing" the curve and algorithmically modifying the control points (not the two end points of the curve) so the curve "morphs" as you drag it. I may not be doing a great job at explaining it; if you've got Inkscape or some vector edition program, draw a straight line with the pen tool, and then click and drag on the middle of the line to bow it. That's what I'm after.

[quote name='Catmull Dog' timestamp='1347372170' post='4978889']
You may prefer Catmull Rom splines as they feature control points that lie on the curve (just the span 1 to 2), where Bezier defines a control polygon and only the endpoints 0 and 3 are on the curve). You can convert between them with a formula that is not too bad (see [url="http://www.cemyuksel.com/research/catmullrom_param/catmullrom_cad.pdf"]Figure[/url]4).
[/quote]
I've looked at Catmull-Rom splines, but I'm more interested in Bezier curves specifically because it's contained in the convex hull of its control points, which allows me to make some guarantees about the generated curve. I don't know if Catmull-Rom splines hold the same property (taking their tangents into account when making the convex hull), but either way cubic Bezier curves match the overall effect I'm after. But thanks for the suggestion and link for converting between the two.

Share this post


Link to post
Share on other sites
I think I understand what you want to do: the point P on the curve is a dependent variable which is a function of independent variables (the control parameters C = c0, c1, c2, etc. are the inputs to the curve function F). So you know F(C) = P, you want to find deltaC such that F(C + deltaC) = P + v where v is the vector displacement the user specified by dragging.

(I have a feeling the above is incomplete if not completely wrong, since the curve function which specifies P is a function of the control points *and* the t parameter which specifies a point on the curve.)

I feel like this should be a pretty simple vector calculus solution, it seems quite similar to rigid body constraint solving: for a ball-and-socket joint, there is a point on each body which is a dependent variable (a function of the rigid body state and the local coordinates of the point), you have a known change in position and/or velocity that you want to be applied to the constrained points, and you need to determine the resulting change to the rigid body state (the independent variables) which will effect the desired change to the constraint points.

And/or some sort of optimization/error-minimization solution might be applicable (i.e given a point on the curve specified by the scalar t, how do you need to adjust the control points to minimize the length of the vector (F(C,t) - p) where p is the desired worldspace position of the point).

Sadly I'm quite rusty with my math so I can't actually provide or suggest a solution.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this