Approximating cubic Bezier curves

A method to approximate a cubic Bezier curve using two quadratic Bezier curves, ensuring that the curves meet at a given t value.
== Background ==
This method was developed to help with game AI in vehicular racing games, using neural networks and genetic algorithms, specifically the AI for the free software game Ecksdee.
Levels in Ecksdee are created with Blender. The Blender spline tool uses cubic Bezier curves. It is preferable that the AI use quadratic Bezier curves for its representation of the centre-line of the track, so that the neural network will have fewer inputs, and therefore be smaller, thereby making it easier to train using a genetic algorithm. Therefore we want to approximate cubic Bezier curves using quadratic Bezier curves, that will exactly match the original cubic curve for a specific value of t (the vehicle's present position on the track curve). For algorithmic reasons, we want to replace each cubic curve with two quadratic curves.
== Definitions ==
Let B(t) define the original cubic Bezier curve. We wish to split this into two halves, approximated by quadratic Bezier curves B_0(t) and B_1(t).
B(t) = (1 - t)^3 P_0 + 3t(1-t)^2 P_1 + 3t^2(1 - t) P_2 + t^3P_3 , t \in [0,1]
B_0(t) = (1 - t)^2 Q_0 + 2t(1 - t) Q_1 + t^2 Q_2 , t \in [0,1]
B_1(t) = (1 - t)^2 Q_2 + 2t(1 - t) Q_3 + t^2 Q_4 , t \in [0,1]
== Known equalities ==
The start point of B_0 is also the start point of B. The end point of B_1 is also the end point of B. The end point of B_0 and the start point of B_1 are both equal to the value of B at t = \tfrac{1}{2}.
Q_0 = P_0
Q_2 = B(\tfrac{1}{2})
Q_4 = P_3
== Problem ==
The control points P_n of the cubic curve are known. We need to find the remaining unknown control points, Q_1 and Q_3, of the quadratic curves.
Suppose the following propositions:
1. B(t) = B_0(2t), t \in [0,\tfrac{1}{2}]
2. B(t) = B_1(2t - 1), t \in [\tfrac{1}{2},1]
== Solution in proposition 1 ==
(1 - 2t)^2 Q_0 + 4t(1 - 2t) Q_1 + 4t^2 Q_2 = (1 - t)^3 P_0 + 3t(1-t)^2 P_1 + 3t^2(1 - t) P_2 + t^3 P_3
Expand polynomials of t:
(4t^2 - 4t + 1)Q_0 + (-8t^2 + 4t)Q_1 + 4t^2 Q_2 = (-t^3 + 3t^2 - 3t + 1)P_0 + (3t^3 - 6t^2 + 3t)P_1 + (-3t^3 + 3t^2)P_2 + t^3 P_3
Solve for Q_1 (recall that Q_0 = P_0):
(-8t^2 + 4t) Q_1 = (-t^3 - t^2 + t + 1) P_0
 + (3t^3 - 6t^2 + 3t) P_1
 + (-3t^3 + 3t^2) P_2
 + t^3 P_3
 + (-4t^2) Q_2
Factor out while dividing:
\frac{-4t^2}{-8t^2 + 4t} = \frac{t^2}{2t^2 - t} = \frac{t^2}{2t(t - \tfrac{1}{2})} = \frac{t}{2t - 1}
Divide by the coefficient of Q_1:
Q_1 = (\tfrac{1}{8} t + \tfrac{3}{16}) P_0
 + (- \tfrac{3}{8} t + \tfrac{9}{16}) P_1
 + (\tfrac{3}{8} t - \tfrac{3}{16}) P_2
 + (- \tfrac{1}{8} t - \tfrac{1}{16}) P_3
 + \frac{t}{2t - 1} Q_2
Simplify:
L = \tfrac{1}{8} (P_0 - 3P_1 + 3P_2 - P_3)
M = \tfrac{1}{16} (3P_0 + 9P_1 - 3P_2 - P_3)
Q_1 = Lt + M - \frac{tQ_2}{2t - 1}
== Solution in proposition 2 ==
(2 - 2t)^2 Q_2 + (4t - 2)(2 - 2t) Q_3 + (2t - 1)^2 Q_4 = (1 - t)^3 P_0 + 3t(1-t)^2 P_1 + 3t^2(1 - t) P_2 + t^3 P_3
Expand polynomials of t:
(4t^2 - 8t + 4) Q_2 + (-8t^2 + 12t - 4) Q_3 + (4t^2 - 4t + 1) Q_4 = (-t^3 + 3t^2 - 3t + 1)P_0 + (3t^3 - 6t^2 + 3t)P_1 + (-3t^3 + 3t^2)P_2 + t^3 P_3
Solve for Q_3 (recall that Q_4 = P_3):
(-8t^2 + 12t - 4) Q_3 = (-t^3 + 3t^2 - 3t + 1) P_0
 + (3t^3 - 6t^2 + 3t) P_1
 + (-3t^3 + 3t^2) P_2
 + (t^3 - 4t^2 + 4t - 1) P_3
 + (-4t^2 + 8t - 4) Q_2
Factor out while dividing:
\frac{-4t^2 + 8t - 4}{-8t^2 + 12t - 4} = \frac{t^2 - 2t + 1}{2t^2 - 3t + 1} = \frac{(t - 1)^2}{2(t - 1)(t - \tfrac{1}{2})} = \frac{t - 1}{2t - 1}
Divide by the coefficient of Q_3:
Q_3 = (\tfrac{1}{8} t - \tfrac{3}{16}) P_0
 + (- \tfrac{3}{8} t + \tfrac{3}{16}) P_1
 + (\tfrac{3}{8} t + \tfrac{3}{16}) P_2
 + (- \tfrac{1}{8} t + \tfrac{5}{16}) P_3
 + \frac{t - 1}{2t - 1} Q_2
Simplify:
L = \tfrac{1}{8} (P_0 - 3P_1 + 3P_2 - P_3)
N = \tfrac{1}{16} (-3P_0 + 3P_1 + 3P_2 + 5P_3)
Q_3 = Lt + N + \frac{(t - 1)Q_2}{2t - 1}
== Conclusion ==
Propositions 1 and 2 were defined for t \in [0,\tfrac{1}{2}] and t \in [\tfrac{1}{2},1] respectively. We wish to redefine them for t \in [0,1], so for the first we multiply t by \tfrac{1}{2} and for the second we add 1 before multiplying t by \tfrac{1}{2}.
Thus, the control points Q_n of our two approximating quadratic Bezier curves, defined in terms of the control points P_n of the original cubic Bezier curve being approximated:
L = \tfrac{1}{16} (P_0 - 3P_1 + 3P_2 - P_3)
M = \tfrac{1}{16} (3P_0 + 9P_1 - 3P_2 - P_3)
N = \tfrac{1}{16} (-3P_0 + 3P_1 + 3P_2 + 5P_3)
Q_0 = P_0
Q_1 = Lt + M - \frac{t}{2(t - 1)}Q_2
Q_2 = B(\tfrac{1}{2})
Q_3 = L(t + 1) + N + \frac{t - 1}{2t}Q_2
Q_4 = P_3
Q_1 and Q_3 are non-constant; they vary with respect to t. This is how we can be sure that the approximation curve exactly meets the original curve for a specific value of t.
== Author ==
This method was devised and worked out by Mat Sutcliffe (Oktal 01:22, 2 May 2007 (UTC)), who also authored this document.
== References ==
wikipedia:Bezier curve;
Math::Polynomial Perl module I used to help divide polynomials;
Blender free 3D modelling software mentioned in this document;
Ecksdee free vehicular racing game for which this method was devised.