Subject: TTF to PS curve conversion (2/5)

From: "L.S.Ng" <[email-masked]>
Date: Sat, 28 May 1994 16:29:02 BST

Algorithm for Spliting Long Bezier B-spline Curve
=================================================

Here I present my findings without rigourous mathematical proof. The
results were verified using a small C program.  I shall seek formal
mathematical proof for the results.

A Quadratic Bezier B-spline curve can have N+1 control points, where
N >= 2. It is possible to represent exactly such a curve with N-1 short
Quadratic Beizer B-spline curve segments each of which has 3 control
points only.

Suppose P(t)(X(t), Y(t)) is the 'Long' Quadratic Bezier B-spline curve
defined by N+1 control points P0(X0, Y0), P1(X1, Y1) ...  P[N](X[N],
Y[N]).  Here 0 <= t <= n - m + 1, where m is the degree of the B-spline
i.e. m = 2 and (n+1) is the number of control points, so n = N. Hence
0 <= t <= N-1.

Let p[i](s) be a short Quadratic Bezier B-spline curve segment such that
0<=i<=N-2, so that there are N-1 segments.  Each segment has 3 control
points p0[i], p1[i] and p2[i], whose coordinates are (x0[i], y0[i]),
(x1[i], y1[i]) and (x2[i], y2[i]) respectively.  Here the parameter of
the curve, s, is such that 0 <= s <= n - m + 1. Here n+1=3 and m=2.
Hence 0 <= s <= 1.

It was found that

p0[i] = P(i)
x0[i] = X(i)
y0[i] = Y(i)

p1[i] = P[i+1]
x1[i] = X[i+1]
y1[i] = Y[i+1]

p2[i] = P(i+1)
x2[i] = X(i+1)
y2[i] = Y(i+1)

where i is an integer such that 0 <= i <= N-1 and N+1 is the number of
the control points in the long curve P(t).

In words, the starting point p0[i] of the i-th segment is the point
P(t) where t=i and t is an integer. The middle control point p1[i] of
the i-th segment is the [i+1]-th control point, P[i+1], of the long
curve P(t). The end point p2[i] of the i-th segment is the point P(t)
where t=i+1 and t is an integer.

For example, the zeroth segment (i=0) (remeber we deal with number base
0). The starting point of this segment is P(0) which is also P0. The
middle control point of this segment (i=0) is P[i+1] that is P1. The end
point of this segment is P(i+1) or P(1).

Note that P(1) lies between P1 and P2.  It is the intersection of the
curve and the straight line joining P1 and P2. Also the slope at P(1) is
the same as the slope of the straight line joining P1 and P2.

In general, P(i), where i is an integer, lies between P[i] and P[i+1]
except at the begin and end points where P(i) coincides with either one
of them.  P(i) is the intersection of the curve P(t) and the straight
line joining P[i] and P[i+1].  The slope of P(t) and this point is the
same as the slope of the straight line joining P[i] and P[i+1].

This properties provides a quick way of sketching the points P(t) where
t=i is an integer.

The next segment is the 'first' segment (i=1). The starting point is
P(i) that is P(1). This conincides with the end point of the previous
segment. Not only that, the differential is also continuos, resulting in
a smooth curve. The middle point of this segment is P[i+1] or P2. In
other words, the middle control point of the first segment is the second
control point (of the long curve P(t)). The end point of this segment is
P(2).

Note the difference of P(i) and P[i]. P(i) is the point on
P(t) evalutated at the point where t=i. P[i] is the i-th control point
of the curve P(t).

Finally, the last segment is the (N-2)-th segment (i=N-2). As there are
only N-1 segments, the last number is N-2. The control points are
P(N-2), P[N-1] and P(N-1).

Note that at the last point of P(t), P(N-1) = P[N].  Also the beginning
point P(0) = P[0].

This enables the control points p0, p1, p2 of each short segment p[i](s)
to be found. This in turn fully defines each short segment p[i](s).
Hence the long curve P(t) can be represented exactly by short segments
of p[i](s) where i is an integer such that 0 <= i <= N-2, and N + 1 is
the number of control points in the long curve P(t), and 0<=s<=1.