FANDOM


This article is a working preliminary draft, NOT yet submitted for peer review. Leave your comments on the discussion page (talk page) or contact the First Author, Oktal, at their talk page or by email.

A method to approximate a cubic Bezier curve using two quadratic Bezier curves, ensuring that the curves meet at a given $ t $ value.

Background Edit

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 Edit

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 Edit

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 Edit

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 Edit

$ (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 Edit

$ (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 Edit

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 Edit

This method was devised and worked out by Mat Sutcliffe (Oktal 01:22, 2 May 2007 (UTC)), who also authored this document.

References Edit

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.

Community content is available under CC-BY-SA unless otherwise noted.