From: "David C. Ullrich" <ullrich@math.okstate.edu>
Subject: Re: Q: Bezier curve editing
Date: Fri, 07 Jan 2000 12:40:22 -0600
Newsgroups: sci.math
Summary: How are Bezier curves related to splines?

    Turns out that there's more than one thing commonly described
as a "Bezier curve". I just found there are Bezier curves in (La?)TeX,
which are quadratic splines: if A and B are two points and C is a
control point then the curve passes through A and B, and the
line through A and C is tangent to the curve at A, while the line
through B and C is tangent to the curve at B. (Note I said that the
line is tangent to the curve, which says nothing about the magnitude
of the tangent vector to the curve at A and B. If you work it out
you see there's exactly one quadratic curve satisfying these
conditions - this depends on the fact that the dimension is 2.)

    Otoh in Postscript or the MS Windows GDI Bezier curves
are cubic splines. This means you can specify the endpoints
of a curve and also specify the tangent vectors to the curve
at the endpoints (and that works out that way in any dimension,
although those programs only do it in 2 dimensions.) The mapping
between "points and tangent vectors" and "points and control
points" always seemed curious to me, although I gather it
makes sense for reasons I've never worried about:
    If A, D are the endpoints and B, C are the control points
then the tangent to the curve at A is the vector (B - A)/3
(or maybe (B-A)*3, (A-B)/3 or (A-B)*3, I don't think
it really matters here and now) and the tangent to the
curve at D is (C-D)/3 (or one of the other three permutations.)

    I don't know what Corel is doing, exactly. It's always seemed
to me that there are a few missing control points in the Bezier
curves in drawing programs - could be Corel draw is using
quadratic splines as in LaTeX or it could be cubic splines
with C=D in the notation above.

    Do you really only get to drag points on the curve? You should
be able to drag control points which are not points on the curve,
affecting the curve's shape.

Toby wrote:

> 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.
>
> Thanks,
> Toby.
>
> --
> Toby
> http://filmstills.freeservers.com/
==============================================================================

From: "David C. Ullrich" <ullrich@math.okstate.edu>
Subject: Re: Q: Bezier curve editing
Date: Mon, 10 Jan 2000 14:05:03 -0600
Newsgroups: sci.math

Kevin Foltinek wrote:

> In article <38763316.46679005@math.okstate.edu> "David C. Ullrich"
> <ullrich@math.okstate.edu> writes:
>
> >     Turns out that there's more than one thing commonly described
> > as a "Bezier curve".
>
> A Bezier curve of "order" n (n an integer >= 0) is defined by (n+1)
> control points (p_0,...,p_n) by the following:
>   x(t) = \sum_{i=0}^n \choose(n,i) t^i (1-t)^{n-i} p_i ,
> where 0<=t<=1.  (I think I got the formula right...)

    Oh... sure enough that's what I said for n = 3 and also
for n = 2 . I had two essentially different descriptions
("specify endpoints and tangent vectors at the endpoints"
versus "specify endpoints and tangent directions at the
endpoints") and hadn't realized they both fit into the
same box - this is much more satisfactory, thanks.

>
> > I just found there are Bezier curves in (La?)TeX,
> > which are quadratic splines:
>
> I think usually "spline" means something different.  A spline goes
> through a specified set of points;

    You're probably right. I thought it was more general than
that, for example I thought that a curve interpolating given
values and derivatives up to some order also counted as a
"spline". (As opposed to just specifying the values, ie
going through specified points.)

> a Bezier curve (usually) does not
> (except for the first and last control points).

    With a 3rd-order Bezier curve you can specify exactly the
values and first derivatives at t=0 and t=1; this makes it a
"spline" in the above sense, spline or not.

> (I don't know what's
> in the TeX packages to which you refer.)

    I've never tried it, but a LaTeX book says that the /bezier
command in the picture environment gives something as
above with n = 2. (Not that they put it that way.)

>
> Kevin.
==============================================================================

From: foltinek@math.utexas.edu (Kevin Foltinek)
Subject: Re: Q: Bezier curve editing
Date: 11 Jan 2000 11:08:07 -0600
Newsgroups: sci.math

In article <387A3B6F.E68F2196@math.okstate.edu> "David C. Ullrich"
<ullrich@math.okstate.edu> writes:

> I thought it was more general than
> that, for example I thought that a curve interpolating given
> values and derivatives up to some order also counted as a
> "spline". (As opposed to just specifying the values, ie
> going through specified points.)

I suppose it could be argued that specifying n control points can be
interpreted as specifying the endpoints and derivatives up through
some order.  To be more precise, if n is even, say n=2k, then you
specify (k-1) derivatives and the k-th direction at each endpoint; if
n is odd, say n=2k+1, then you specify k derivatives at each
endpoint.  Let's define a JD-space JD^n([0,1],R^m) to be either a
jets-and-direction space (n even) or a jet space (n odd), of maps from
[0,1] to R^m.  Then what you're saying is that specifying the control
points of a Bezier curve is equivalent to specifying two points in
JD^n, one point being over t=0, the other being over t=1.

Then a Bezier curve is a little bit more than a polynomial spline (of
a certain degree) between those two points: it is a polynomial spline
with the additional property it is the lift of a curve in R^m.  (By
"lift" I really mean the graph of the jet or jet+direction of a
curve.)

> > a Bezier curve (usually) does not
> > (except for the first and last control points).
> 
>     With a 3rd-order Bezier curve you can specify exactly the
> values and first derivatives at t=0 and t=1; this makes it a
> "spline" in the above sense, spline or not.

Yes, with the interpretation that a spline in jet-space must be the
lift of a curve in R^2.  In this case, you would specify j^1 at t=0
and t=1; say j^1(0)=(0,p0,3*(p1-p0)); and j^2(0)=(1,p2,3*(p2-p1)).
Note that these are simply two points in R^5; the problem of
determining a cubic curve from one to the other is underdetermined.
However, with the additional constraint that the cubic curve be the
lift of a curve in R^2, it is a well-posed problem.

An interesting interpretation, I think.

Kevin.
==============================================================================

From: "David C. Ullrich" <ullrich@math.okstate.edu>
Subject: Re: Q: Bezier curve editing
Date: Tue, 11 Jan 2000 11:44:01 -0600
Newsgroups: sci.math

Kevin Foltinek wrote:

> In article <38763316.46679005@math.okstate.edu> "David C. Ullrich"
> <ullrich@math.okstate.edu> writes:
> [...]
>
> > I just found there are Bezier curves in (La?)TeX,
> > which are quadratic splines:
>
> I think usually "spline" means something different.  A spline goes
> through a specified set of points; a Bezier curve (usually) does not
> (except for the first and last control points).

    The relevant guy down the hall wasn't here the other day. He
says that specifying points and tangent vectors amounts to
Hermite interpolation, which I gather everybody but me
already understood, and he also says that it's perfectly proper
to call the resulting curve a "Hermite spline".
==============================================================================

From: foltinek@math.utexas.edu (Kevin Foltinek)
Subject: Re: Q: Bezier curve editing (ii)
Date: 11 Jan 2000 11:56:30 -0600
Newsgroups: sci.math

In article <85cc5q$reg$1@nnrp1.deja.com> tobbster@my-deja.com writes:

> Second attempt, since the first seemed to cause some confusion. I will
> try to be more specific.

I replied to your first attempt, and have since thought a little more
about it, and now I'll amend my first response (as well as, umm,
provide a few minor bug fixes).

I'll do this in some generality.

Given: (n+1) control points in R^m, specifying a Bezier curve:
  x(t) = \sum_{i=0}^n f_i(t) p_i
where 0<=t<=1, f_i(t) depends only on i, n, and t.

Given: A time t*, with 0<t*<1.

Given: A point x*.

Problem: Find (n+1) control points q_i such that the new Bezier curve
  y(t) = \sum_{i=0}^n f_i(t) q_i
satisfies
  y(t*) = x* .

Of course this problem is underdetermined.

However: since the functions f_i are independent of p_i or q_i, what
you have is a system of linear equations;
  y(t) = \sum f_i(t) q_i
is, for any fixed t, m equations (the curve is in R^m) relating y(t)
to q_i.  There are m(n+1) unknowns, the (n+1) points q_i; but you are
only given m conditions, \sum f_i(t*) q_i = x*.

However, from a usability perspective, some other conditions can be
constructed.  First, whatever the solution (q_i) is, should depend
continuously on t*; that is, if you start with two identical curves,
and move two nearby points by exactly the same amount, the resulting
curves should be very similar.  Second, the change in the curve should
be "concentrated" near t*; that is, the endpoints shouldn't change,
and if you move a point very near one endpoint, the curve near the
other endpoint shouldn't change much.

With this in mind, I propose the following candidate solution.
However, this solution will move the endpoints; at the end I'll say a
little bit about how to correct this.

Step 1.  Subdivide the interval [0,1] into n sub-intervals
  [0,1/n], (1/n,2/n], ..., ((n-1)/n),1]
and find which of these n sub-intervals the point t* is in.  Say
that j/n < t* <= (j+1)/n, thereby uniquely defining an integer j such
that 0<=j<=n-1.

Step 2.  Compute s such that
  t*=j/n + s/n.
Let w1 = 1-s, w2 = s.

Step 3.  Solve the system of (2m) equations
  x* = \sum_{i=0}^n f_i(t*) q_i
  w2(q_j-p_j) = w1(q_{j+1}-p_{j+1})
for the (2m) variables (q_j, q_{j+1}).

For i not equal to j or j+1, let q_i=p_i.

What this does:

Step 1 finds the two control points which are "on either side" of t*.
(Whatever that means.)
Step 2 assigns weights to these two control points: w1 to the point
before t*, w2 to the point after.  The closer t* is to a control
point, the larger the weight.
Step 3 finds new control points such that (1) the new curve passes
through the specified point, and (2) the control point closer to t*
moves more than the one further away.

Notes:
1.  The weights can be assigned differently: w1=1-f(s), w2=f(s), where
f(s) is any monotonically increasing function, f(0)=0, f(1)=1.
2.  You can probably come up with a different weighting scheme,
assigning weights to every control point; the condition
  w2(q_j-p_j) = ...
would have to be modified into something much more complicated.
3.  To keep the endpoints stationary, all you have to do is always
assign a weight of zero to an endpoint (remembering that the two
weights should add up to 1).
4.  You can probably do a lot more with the weights, such as modifying
them to somehow reflect "how much" a given control point affects the
curve.  You might need to do this to obtain a "better feel" to how the
curve changes.
5.  There might be a vastly superior method of finding values for j
and s which make this method "look nice".

The nice thing about this approach is that the system of equations is
linear, the coefficients need to be computed only once (per selected
point), therefore the inverse of the matrix needs to be computed only
once, and therefore the new curve can be computed rather quickly -
probably in real time as you move the point around.

Kevin.