Fandom

Academic Publishing Wiki

Approximating cubic Bezier curves

693pages on
this wiki
Add New Page
Talk4 Share
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.

Ad blocker interference detected!


Wikia is a free-to-use site that makes money from advertising. We have a modified experience for viewers using ad blockers

Wikia is not accessible if you’ve made further modifications. Remove the custom ad blocker rule(s) and the page will load as expected.