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

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

Conversion of Quadratic Bezier curve to Cubic Bezier Curve
==========================================================

Problem: Prove that a quadratic Bezier curve with 3 control points
P20(x20, y20), P21(x21, y21), P22(x22, y22) can be exactly represented
by a cubic Bezier curve with 4 control points P30(x30, y30), P31(x31,
y31), P32(x32, y32), P33(x33, y33) where

x30 = x20 and y30 = y20
x33 = x22 and y33 = y22

x31 = x20 + 2/3 (x21 - x20)
y31 = y20 + 2/3 (y21 - y20)

x32 = x21 + 1/3 (x22 - x21)
y32 = y21 + 1/3 (y22 - y21)

Proof:

Since the quadratic Bezier curve has 3 control points, we can use either
Bernstein or B-spline as the basis function. Bernstein is equivalent to
B-spline if N = M where N+1 is the number of control points and M is the
degree of the Bezier curve. Likewise for the cubic curve which has 4
control points.

So a quadratic curve P2(t) where 0 <= t <= 1 can be written as

x2(t) = x20*B02(t) + x21*B12(t) + x22*B22(t)
y2(t) = y20*B02(t) + y21*B12(t) + y22*B22(t)

where B[k][n](t) is the Bernstein basis function given by

      B[k][n](t) = n!x^k(1-x)^(n-k)/(k!(n-k)!)

(See Computer Graphics literature for details. I used Plastock and
Kelley's Schaum's Outline Series on Computer Graphics Chapter 9)

Similarly a cubic curve P3(t) where 0 <= t <= 1 can be written as

x3(t) = x30*B03(t) + x31*B13(t) + x32*B23(t) + x33*B33(t)
y3(t) = y30*B03(t) + y31*B13(t) + y32*B23(t) + y33*B33(t)

Boundary conditions:

1. To fit a quadratic curve to a cubic curve i.e.

   P2(t) = P3(t)

2. The start and end points of both curve must agree i.e.

   x30 = x20 and y30 = y20
   x33 = x22 and y33 = y22

Procedure of proof:

For the x coordinates:
1. Equate P2(t) and P3(t) above i.e. equate expressions for x2(t) and
x3(t).

        x3(t) = x2(t)
that is
        x30*B03(t) + x31*B13(t) + x32*B23(t) + x33*B33(t)
        = x20*B02(t) + x21*B12(t) + x22*B22(t)

2. Substitute x30 = x20 and x33 = x22.

        x20*B03(t) + x31*B13(t) + x32*B23(t) + x22*B33(t)
        = x20*B02(t) + x21*B12(t) + x22*B22(t)

3. Move the terms x20 and x22 on the left hand side to the right hand
side.
        x31*B13(t) + x32*B23(t)
        = x20*(B02(t)-B03(t)) + x21*B12(t) + x22*(B22(t)-B33(t))

4. Expand all B[k][n](t) basis function in terms of t. Simplify terms.
Dividing throughout by t(1-t) to obtain:

       3(1-t)*x31 + 3t*x32 = (1-t)*x20 + 2*x21 + t*x22

5. Put t=0 to get x31

        3*x31 = x20 + 2*x21
          x31 = 1/3 (x20 + 2*x21) = 2/3 (x21 - x20) + x20

6. Put t=1 to get x32

        3*x32 = x22 + 2*x21
          x32 = 1/3 (x22 + 2*x21) = 1/3 (x22 - x21) + x21

Likewise for y.

Quad errat demonstradum (Proven as required)