Changing a bezier curve by dragging a point on the curve itself rather than a control point

Question

I'm developing an iPhone app that allows users to cut out part of an image from its background. In order to do this, they'll connect a bunch of bezier curves together to form the clipping path. Rather than have them move the control points of the curves in order to change the curve, I'd like them to be able to move a point on the curve itself. At this point, I'm not set on using quadratic rather than cubic beziers, or vice versa. The rest of this post will discuss the issue from the point of view of quadratic curves, but I would love an answer that provides solutions to both.

It seems to me that there are two possible methods for accomplishing this:

1. By determining the relationship between the point on the curve and the true control point. If this can be done, then the new location of the control point can be calculated based on the new location of the point on the curve.

2. By using an equation that can estimate a bezier curve based on two end points and a third point on the curve (if cubic, then a third and fourth point on the curve).

Are either of these possible? I've been googling this for a while and have come across a couple potential solutions using method #2, but I don't fully understand either:

Solution 1 (click here): I think I understand the code in this example well enough, but I don't know how to calculate t.

Solution 2 (click here): This code is written in C#. I tried converting it to Objective-C (the language used for iPhone apps), but ultimately got stuck on the "solvexy()" function because I don't see how i or j are used after calculating their values.

In regards to method #1, it seems to me that there should be some mathematical relationship between the control point, and the point on the curve through which a tangent to the curve at that point would be perpendicular to a line drawn from the control point to that point.

Here are a couple illustrations: quadratic, cubic.

The idea is that this point which lies on the curve, through which the perpendicular tangent is drawn, is the point that users would be dragging in order to modify the curve.

Answer 1

If your only problem is to find the point at which the tangent line is perpendicular to the direction to the control point and to find the control point that has this property for a given waypoint on the curve, you can try the following. Let's do quadratic curves. If A is the beginning, B is the end (both fixed), C is the control and X is the waypoint, we have the system

$X=(1-t)^2A+2t(1-t)C+t^2B$ (curve equation)

$\langle X-C,-(1-t)A+(1-2t)C+tB\rangle=0$ (orthogonality relation).

Suppose we know $C$. Then plugging $X$ from the first equation into the second, we get a cubic equation for $t$, which we can solve quickly by either bisection, or Newton, or a combination of both.

The inverse problem is similar. Express $C$ from the first equation and plug the result into the second one. Now you'll get a fifth degree equation to solve but if bisection is quick enough for you (you do not need really high precision for point dragging), you can do everything without too heavy thinking (we need to make sure that the singularities at the endpoints are dealt with in some reasonable way, so if the user drags the point close to one of the endpoints you don't have an aberrant behavior but I do not want to think of this singularity problem before you tell me if this approach works for you in general).

The cubic curves have two controls, so the problem is ill-posed for them as stated.

Answer 2

I think the simplest thing that would work in your application is to show the user 4 special points on the parametric cubic curve, and allow the user to manipulate those 4 special points. (Allowing the user to pick any point on the curve, and move it, makes things more complicated).

I think this is the same as what Stephen H. Noskowicz calls "Cubic Four Point" representation, aka the quadratic Lagrange with t1 = 1/3 and t2 = 2/3.

While your user is moving those 4 special points U0, U1, U2, U3 around, periodically you find a cubic Bezier curve that goes through those 4 points using John Burkardt's approach:

P0 = U0
P1 = (1/6)*( -5*U0 + 18*U1 - 9*U2 + 2*U3 )
P2 = (1/6)*(  2*U0 -  9*U1 +18*U2 - 5*U3 )
P3 = U3.

That gives you the Bezier curve representation of the same cubic curve -- a series of 4 control points. You then feed those 4 control points (the endpoints P0 and P3, and the intemediate control points P1 and P2) into any Bezier curve plotter.

The resulting curve (usually) doesn't touch P1 or P2, but it will start at X0, go exactly through X1 and X2, and end at X3.

(This uses the special points at t=0, 1/3, 2/3, and 1. It's possible to, instead, use the special points at t=1, 1/4, 3/4, and 1, as shown at How do I find a Bezier curve that goes through a series of points? . Or, I suppose, any 4 distinct t values. But I suspect the 0, 1/3, 2/3, 1 values are used most often, and I don't see any advantage to using any other fixed values).