Academic Publishing Wiki
Register
Advertisement
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 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 (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 define the original cubic Bezier curve. We wish to split this into two halves, approximated by quadratic Bezier curves and .

Known equalities[]

The start point of is also the start point of . The end point of is also the end point of . The end point of and the start point of are both equal to the value of at .

Problem[]

The control points of the cubic curve are known. We need to find the remaining unknown control points, and , of the quadratic curves.

Suppose the following propositions:

1.

2.

Solution in proposition 1[]

Expand polynomials of :

Solve for (recall that ):

Factor out while dividing:

Divide by the coefficient of :

Simplify:

Solution in proposition 2[]

Expand polynomials of :

Solve for (recall that ):

Factor out while dividing:

Divide by the coefficient of :

Simplify:

Conclusion[]

Propositions 1 and 2 were defined for and respectively. We wish to redefine them for , so for the first we multiply by and for the second we add before multiplying by .

Thus, the control points of our two approximating quadratic Bezier curves, defined in terms of the control points of the original cubic Bezier curve being approximated:

and are non-constant; they vary with respect to . This is how we can be sure that the approximation curve exactly meets the original curve for a specific value of .

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.

Advertisement