Subject: Revised TTF to PS (2/5)

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

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

(Revised 28-5-94)

Here I present my findings without rigourous mathematical proof. The
results were verified using a small C program.  I shall seek
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] = 1/2*(P[i]+P[i+1])
x0[i] = 1/2*(X[i]+X[i+1])
y0[i] = 1/2*(Y[i]+Y[i+1])
except at i=0, p0[i]=P0

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

p2[i] = 1/2*(P[i+1]+P[i+2])
x2[i] = 1/2*(X[i+1]+X[i+2])
y2[i] = 1/2*(Y[i+1]+Y[i+2])
except at i=N-2, p2[i]=P[N]

where i is an integer such that 0 <= i <= N-2 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 midpoint
between the i-th control point P[i] and the (i+1)-th control point
P[i+1].  The middle control point p1[i] of the i-th segment is the
[i+1]-th control point, P[i+1].  The end point p2[i] of the i-th segment
is the midpoint between the (i+1)-th control point P[i+1] and the
(i+2)-th control point P[i+2].

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

The midpoint between P1 and P2 is the intersection of the curve and the
straight line joining P1 and P2.  Also the slope of the curve at this
point is the same as the slope of the straight line joining P1 and P2.

In general, the midpoint between P[i] and P[i+1], except at the begin
and end points, is also 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 also the same as the slope of the straight line joining P[i] and
P[i+1].

The next segment is the 'first' segment (i=1). The starting point is
the end point of the previous segment, i.e. midpoint of P1 and P2.
At this point the differential is also continuos, resulting in a smooth
curve.  The middle control 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 the midpoint between P2 and P3.

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
mid(P[N-2],P[N-1]), P[N-1] and P[N].

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.