Ego surfing, I happend by and saw this. Though I see this is quite old. An algorithm for "grabbing a curve" that has off the curve control points is quite simple. I guess I didn't include it in my book. Bummer, but I got it from David Forsey in 2000 on UseNet comp.graphics.algorithms. It pairs the cursor with, IIR the nearest control point, then just moves the control point the same distance as the cursor.
Regards, Steve Noskowicz
Here is my rewrite followed by the original.
If the formatting is too screwy, email me for an original on my site or...
noskosteve /at/ Yahoo /dot/ com:
How to "grab" a spot on a curve to move it (familiar notation).
For a parmetric cubic curve, a point on the curve at parameter t (Pt) is defined by:
P(t) or Pt = Sum Pi*Bi(t) = P1B1(t) + P2B2(t) + P3B3(t) + P4B4(t).
Pi are the 4 control points and Bi are the respective weighting functions.
To "grab" a spot on the curve and relocate it, you are moving some Pt to Pt'. Let the amount you move it be Pt = (New point - old point) = Pt'- Pt.
Choose a control point to be moved. (see page 2). Any will do, but choosing the "closest" in parametric space works best. Let's say we'll move P2. Call the new position P2'.
This makes P2 = P2' - P2
The old point on the curve was: Pt = P1B1(t) + P2B2(t) + P3B3(t) + P4B4(t)
The new point on the curve will be: Pt'= P1B1(t) + P2'B2(t) + P3B3(t) + P4B4(t)
Subtract the Old from the New: Pt = Pt'- Pt = (P2' - P2) B2(t) = P2*B2(t)
Solving for P2: P2 = Pt / B2(t)
Then solve for the New P2 (P2'): P2' = P2 + [ Pt / B2(t) ]
OR P2' = P2 + ( [Pt'- Pt] / B2(t) )
So... In general:
Given: a point on the curve called Pt at parameter "t", "near" control point "n".
To move that point on the curve to a new location which differs in position by Pt, move Pn by Pt/Bn(t)
In other words:
Select a spot on the curve to be moved and its new location.
Determine the parameter value of this spot.
Calculate the change in spot position, Pt.
Divide this change, Pt, by the basis function (for the target control point or Bn(t) ) which is evaluated at the selected parameter (t).
Finally, add this to the control point (P2) location. This is the same function and t for all dimensions, so only one calculation is required.
Note that this requires calculating the weighting function for the target control point at the parameter value (t) of the location selected on the curve. You obtain it from the scan for the target "t".
This works with any basis function.
if Curve = Control Pt*Weight
then Control Pt = Curve / Weight
Further areas for consideration.
Finding the point on the curve to be moved.
First, the parameter value of the selected (grabbed) location on the curve must be determined. This must be a sequential search rather than binary because the curve may double back. This could make the true closest point "un-findable" if the curve approaches then moves away from the cursor before going back to closest location the cursor. It can be a coarse-fine search, such as stepping in t steps of 0.1 or larger to find the bracketing locations, then subdividing that sub-segment to hit the curve. The limit being the closest to the nearest pixel on the screen.
This takes the form of re-calculating the curve without needing to draw it; only calculating the distance.
Choosing the target control point.
For the cubic Bézier, the following are proposed.
1) Because the end control points are directly accessable, one method is to divide the segment, and therefore the parameter range, in halves and pick the inner control point related to the half occupied by the grab-location.
P1 0.0 - 0.5
P2 0.5 - 1.0
This, however, can cause an extreme effect upon a control point (and the curve) when the curve is grabbed very near an end. In an attempt to alleviate this, #2 is suggested.
2) Divide the segment, and therefore the parameter range, into 6ths. (It could actually be any fraction, but this seems "natural") The end points are used for the first sixth (0-1/6) and last sixth (5/6-1). The inner control points are then used for the inner thirds. That is 1/6 to 3/6 and 3/6 to 5/6
Given P0, P1, P2, P3, the range of "t" to use for each point is:
P0 0.0 - 0.16667
P1 0.16667 - .5
P2 0.5 - 0.83333
P3 0.83333 - 1.0
The weighting functions in the Basic Image Editor are:
P0 W1(t) = Ft1*t3 + Fu1*t2 + Fv1*t + Fw1
P1 W2(t) = Ft2*t3 + Fu2*t2 + Fv2*t + Fw2
P2 W3(t) = Ft3*t3 + Fu3*t2 + Fv3*t + Fw3
P3 W4(t) = Ft4*t3 + Fu4*t2 + Fv4*t + Fw4
Original posting. Conversion to standard names is on page 1
Date: Fri, 07 Jan 2000 14:48:10 -0800
From: David Forsey
Organization: Radical Entertainment
Subject: Re: Q: Bezier curve editing
I would be most grateful if anyone could answer this straightforward
question for me.
In graphics programs (such as Corel Draw) the user can directly manipulate
(cubic) Bezier curves. The user can "grab" a point on the curve and drag it
around. The control points move so that the new point is on the new curve
(at the same parameter value, I suppose). The endpoints stay fixed.
How do the control points move? A direct solution can't work because only 3
points are known on the new curve, and 4 would be needed for a cubic. I
wondered about cubic Hermite interpolation, but don't see where the tangent
vectors would come from.
For the parmetric cubic curve C(U), for a point P on the curve at parameter u.
P = C(u) = Sum Vi Bi(u) = V1B1(u) + V2B2(u) + V3B3(u) + V4B4(u).
(where the Vi are the 4 control points and the Bi are the basis functions)
You want to move P to P'. Let deltaP = P'- P.
Choose a control point that will be used to change the shape of the curve.
Anyone will do, but choosing the closest in parametric space works best.
Lets say we'll move V2. To make it clear lets call this new position X.
The old point on the curve was:
P = V1B1(u) + V2B2(u) + V3B3(u) + V4B4(u)
The new point on the curve will be:
P'= V1B1(u) + XB2(u) + V3B3(u) + V4B4(u)
Subtract them appropriately:
deltaP = (V2 - X) B2(u) = deltaV2 B2(u)
A little algebra:
deltaV = deltaP / B2(u) Shouldn't this be: deltaV2 = deltaP / B2(u)
So... to move a point P on the curve by deltaP, move V2 by deltaP/B2(u)
This works with any basis function, b-spline or bezier or whatever as well
as for surfaces.
You can also move multiple control vertices to move that point on the curve.
See "A Technique for the Direct Manipulation of Spline Curves", Bartels/Beatty
Graphic Interface '89. There are subsequent papers that cover altering the
tangent and curvature at specified points on a spline.