A method to approximate a cubic Bezier curve using two quadratic Bezier curves, ensuring that the curves meet at a given ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle B(t)}$ define the original cubic Bezier curve. We wish to split this into two halves, approximated by quadratic Bezier curves ${\displaystyle B_0(t)}$ and ${\displaystyle B_1(t)}$.

${\displaystyle 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]}$

${\displaystyle B_0(t) = (1 - t)^2 Q_0 + 2t(1 - t) Q_1 + t^2 Q_2 , t \in [0,1]}$

${\displaystyle 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 ${\displaystyle B_0}$ is also the start point of ${\displaystyle B}$. The end point of ${\displaystyle B_1}$ is also the end point of ${\displaystyle B}$. The end point of ${\displaystyle B_0}$ and the start point of ${\displaystyle B_1}$ are both equal to the value of ${\displaystyle B}$ at ${\displaystyle t = \tfrac{1}{2}}$.

${\displaystyle Q_0 = P_0}$

${\displaystyle Q_2 = B(\tfrac{1}{2})}$

${\displaystyle Q_4 = P_3}$

## Problem

The control points ${\displaystyle P_n}$ of the cubic curve are known. We need to find the remaining unknown control points, ${\displaystyle Q_1}$ and ${\displaystyle Q_3}$, of the quadratic curves.

Suppose the following propositions:

1. ${\displaystyle B(t) = B_0(2t), t \in [0,\tfrac{1}{2}]}$

2. ${\displaystyle B(t) = B_1(2t - 1), t \in [\tfrac{1}{2},1]}$

## Solution in proposition 1

${\displaystyle (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 ${\displaystyle t}$:

${\displaystyle (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 ${\displaystyle Q_1}$ (recall that ${\displaystyle Q_0 = P_0}$):

${\displaystyle (-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:

${\displaystyle \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 ${\displaystyle Q_1}$:

${\displaystyle 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:

${\displaystyle L = \tfrac{1}{8} (P_0 - 3P_1 + 3P_2 - P_3)}$

${\displaystyle M = \tfrac{1}{16} (3P_0 + 9P_1 - 3P_2 - P_3)}$

${\displaystyle Q_1 = Lt + M - \frac{tQ_2}{2t - 1}}$

## Solution in proposition 2

${\displaystyle (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 ${\displaystyle t}$:

${\displaystyle (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 ${\displaystyle Q_3}$ (recall that ${\displaystyle Q_4 = P_3}$):

${\displaystyle (-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:

${\displaystyle \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 ${\displaystyle Q_3}$:

${\displaystyle 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:

${\displaystyle L = \tfrac{1}{8} (P_0 - 3P_1 + 3P_2 - P_3)}$

${\displaystyle N = \tfrac{1}{16} (-3P_0 + 3P_1 + 3P_2 + 5P_3)}$

${\displaystyle Q_3 = Lt + N + \frac{(t - 1)Q_2}{2t - 1}}$

## Conclusion

Propositions 1 and 2 were defined for ${\displaystyle t \in [0,\tfrac{1}{2}]}$ and ${\displaystyle t \in [\tfrac{1}{2},1]}$ respectively. We wish to redefine them for ${\displaystyle t \in [0,1]}$, so for the first we multiply ${\displaystyle t}$ by ${\displaystyle \tfrac{1}{2}}$ and for the second we add ${\displaystyle 1}$ before multiplying ${\displaystyle t}$ by ${\displaystyle \tfrac{1}{2}}$.

Thus, the control points ${\displaystyle Q_n}$ of our two approximating quadratic Bezier curves, defined in terms of the control points ${\displaystyle P_n}$ of the original cubic Bezier curve being approximated:

${\displaystyle L = \tfrac{1}{16} (P_0 - 3P_1 + 3P_2 - P_3)}$

${\displaystyle M = \tfrac{1}{16} (3P_0 + 9P_1 - 3P_2 - P_3)}$

${\displaystyle N = \tfrac{1}{16} (-3P_0 + 3P_1 + 3P_2 + 5P_3)}$

${\displaystyle Q_0 = P_0}$

${\displaystyle Q_1 = Lt + M - \frac{t}{2(t - 1)}Q_2}$

${\displaystyle Q_2 = B(\tfrac{1}{2})}$

${\displaystyle Q_3 = L(t + 1) + N + \frac{t - 1}{2t}Q_2}$

${\displaystyle Q_4 = P_3}$

${\displaystyle Q_1}$ and ${\displaystyle Q_3}$ are non-constant; they vary with respect to ${\displaystyle t}$. This is how we can be sure that the approximation curve exactly meets the original curve for a specific value of ${\displaystyle 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

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.