The math behind Bezier cubic splines

The math behind Bezier cubic splines

Loading
Loading Social Plug-ins...
Language: English
Save to myLibrary Download PDF
Go to Page # Page of 5
 
Author: Don Lancaster (Fellow) | Visits: 2490 | Page Views: 2504
Domain:  High Tech Category: IT Subcategory: Computer Graphics 
Upload Date:
Short URL: https://www.wesrch.com/electronics/pdfEL11TZMPNLEIA
Loading
Loading...



px *        px *

* Default width and height in pixels. Change it to your required dimensions.

 
Contents:
The Math Behind Bezier Cubic Splines
Don Lancaster Synergetics, Box 809, Thatcher, AZ 85552 copyright c2005 as GuruGram 58. http://www.tinaja.com don@tinaja.com (928) 428-4073

ezier Cubic Splines are an excellent and preferred method to draw the smooth continuous curves often found in typography, CAD/CAM, and graphics in general. Among their many advantages is a very sparse data set allowing a mere eight values (or four x,y points) to completely define a full and carefully controlled and device independent curve. Many tutorials and examples are now present in our Cubic Spline Library. A brief and useful intro appears here. While the underlying math behind Bezier cubic splines is amazingly simple, its derivation seems to be quite hard to find. So, what I thought we'd do here is find out exactly where the funny numbers relating cubic spline power coefficients
and control points come from.

B

Let us once again begin by excerpting some key Bezier Cubic Spline properties from our HACK62.PDF tutorial...
Here is a cubic spline shown in its graph space...
influence point #1 The first influence point sets the direction and the enthusiasm that the spline leaves the initial point on the curve. (x1, y1) influence point #2 (x2, y2)

(x0, y0) initial point

(x3, y3) final point

The second influence point sets the direction and the enthuasiasm that the spline enters the final point on the curve.

Here is how a cubic spline appears in its equation space... x = At 3 + Bt 2 + Ct + D y = Et 3 + Ft 2 + Gt + H
t (for time) always goes from zero at the initial point to a one at the final point.

-- 58 . 1 --

This is a faster "cube free" form of the equation space math... x = ((( At ) + B ) t + C ) t + D y = ((( Et ) + F ) t + G ) t + H
How to get from graph space to equation space...

A = x 3 - 3x 2 + 3x 1 - x 0 B = 3x 2 - 6x 1 + 3x 0 C = 3x 1 - 3x 0 D = x0

E = y3 - 3y2 + 3y1 - y0 F = 3y2 -6 y1 + 3y0 G = 3y1 - 3y0 H = y0

How to get from equation space to graph space... x0 = x1 = x2 = x3 =
D D + C/3 D + 2C / 3 + B / 3 D+C+B+A

y0 = H y1 = H + G/3 y 2 = H + 2G / 3 + F / 3 y3 = H + G + F + E

You can easily take these numbers on faith and prove that they work. But to truly understand cubic splines, we need to take a closer look to see exactly where all those strange "threes" and "sixes" really come from. In general, we can relate any four x control point variables to any four A-D cubic power coefficients. And similarly for y. The trick is to find a useful relationship between the two. And that is what Bezier Cubic Splines are fundamentally all about. And where some really sneaky math comes in. It turns out there is a special class of math operators that are known as Basis Functions. Some of these are also called Bernstein Polynomials...
A Bernstein Polynomial of order three is exactly what you need to relate Bezier control points to cubic spline coefficients.

So, how do we create a Basis Function of order three? Start off with...
1=1

... and then make this rather bizarre transformation to it...
(1 - t) + t = 1

-- 58 . 2 --

You often might restrict t (or "time") to values from 0 to 1. To create most any group of Bernstein Polynomial Basis Functions, you simply raise both sides of this equation to a desired power. And then separate terms of interest. Our crucial cubic Bernstein polynomial is...
Thus... ((1 - t) + t) 3 = 1 Expands to... (1 - t) 3 + 3t(1-t) 2 + 3t 2(1 - t) + t 3 = 1 Whose terms can be redefined as... B0(t) + B1(t) + B2(t) + B3(t) = 1

It is very interesting to plot these cubic basis functions...
1.0

(B0)

(B3)

(B1)

(B2)

0.0 t=0

t = 0.5

t = 1.0

For any given t, the four basis functions will exactly sum to give the x value for that t. Which leads to this crucially important Bezier Cubic Spline equation...
x(t) = x0B0(t) + x1B1(t) + x2B2(t) + x3B3(t)

... and the corresponding y(t) equivalent ...
y(t) = y0B0(t) + y1B1(t) + y2B2(t) + y3B3(t)

We can immediately see that initial point x0 sets the start of the curve and that final point x3 sets the end point for us. And that x1 will have its strongest (but not total) influence exactly at t = 1/3. Similarly, x2 will be strongest at t = 2/3.
-- 58 . 3 --

And the magic derivation is...
The x equation deriving the underlying Cubic Spline math is simply...
x0B0(t) + x1B1(t) + x2B2(t) + x3B3(t) = At3 + Bt2 + Ct + D

Along with its y equivalent...
y0B0(t) + y1B1(t) + y2B2(t) + y3B3(t) = Et3 + Ft2 + Gt + H

Since the powers of t have to vary over a 0 to 1 region, these two expressions can be equal only if the constant coefficients for each power of t match....
x3B3(t) = x2B2(t) = x1B1(t) = x0B0(t) = x3t3 = x3t3

x2(3t2(1-t)) = -3x2t3 + 3x2t2 x1(3t(1-t)2) = x0(1-t)3 = 3x1t3 6x1t2 + 3x1t

-x0t3 + 3x0t2 - 3x0t + x0

Now, "think vertically" and regroup to get...
A = x3 - 3x2 + 3x1 - x0 B = 3x2 - 6x1 + 3x0 C = 3x1 - 3x0 D = x0

And similarly for y...
E = y3 - 3y2 + 3y1 - y0 F = 3y2 - 6y1 + 3y0 G = 3y1 - 3y0 H = y0

-- 58 . 4 --

We've already seen that x0, y0 sets the start of the curve and x3, y3 the end. We've also seen that influence point x1, y1 sets the enthusiasm or tension that peaks at t = 1/3. And that x2, y2 sets the enthusiasm or tension that peaks at t = 2/3. There are several ways of getting at the initial and final slopes of the final curve. By definition C will be the initial slope of the x versus t curve and will also equal 3x1 - 3x0. On our x versus y curve, the slope will be (y1 - y0)/(x1 - x0). Thus, the x1, y1 influence point will set the initial slope of the x-y cubic spline curve. And the x2, y2 influence point will similarly set the final slope.

The "Snake in the Box"
It is important to remember that Bezier cubic splines independently relate x and y to a new parametric variable t. Which varies from 0 to 1 from the beginning to the end of the curve. Thus, your final two dimensional x-y plot is really one view of a three dimensional x-y-t plot. One good way to visualize this is to think of your parametric curve as a snake in a box...
x y t t=1

t=0

You look into the end of the box to see how x varies with y. And into the top or side of the box to see the variation versus t. In general, the relationship between x and t will be non-obvious, with t changing faster along the "more bent" portions of the curve. In addition, finding t(x) given x(t) is non trivial. And finding y given x involves first finding t. And really gets ugly fast because there can be multiple y values for a given x in a looped spline.

For More Help
Additional info on cubic splines can be found on our Cubic Spline library page. As are many dozens of examples of Bezier cubic spline techniques. Additional consulting services are available per our Infopack services and on a contract or an hourly basis. Additional GuruGrams are found here. Further GuruGrams await your ongoing support as a Synergetics Partner.
-- 58 . 5 --