Review

A polynomial is a vector: the polynomial is the vector , and scaling/adding polynomials is exactly scaling/adding vectors.

In this chapter we put polynomial vectors to work and build one of the most widely used tools in computer graphics - the Bezier curve.

---

9.1 A general guideline to describe curves

By describing a curve, we mean writing down one or more (algebraic) equations that, when plotted on a 2D plane or a 3D space, give rise to the curve they describe. A simple description of the curve can have the format , possibly with some constraints on the value of - for example , a wavier , or this polynomial curve .

9.1.1 Understanding the problem: y = f(x) is not enough

Consider this sideways parabola, described by the equation .

Or this circle, described by the equation .

These curves simply cannot be described by an equation y = f(x). The reason is that y = f(x) is a function. A function has a unique output for a given input - it cannot have two different outputs for the same input. But the curves above clearly have two different y-values for many values of x. They can be described by other equations involving x and y, but that can get quite tricky and complicated pretty fast.

9.1.2 Understanding a solution

One possible, and commonly used, solution to describing (almost) any curve is:

Describe and as functions of a third variable :

Then plot y-versus-x on a 2D plane. These equations are also called parametric equations - you are using a parameter to describe how and behave as functions of . The curves we saw above can be expressed in parametric form like so:

• : trace as sweeps from to .
• : trace as sweeps from to .
• : trace as sweeps from to .

A pythonic pseudocode for plotting a curve may look like:

def x(t):
    return some_function(t)

def y(t):
    return some_other_function(t)

def sample_t(start=0, end=1, num_points=100):
    step = (end-start)/(num_points-1)
    return [start + i*step for i in range(num_points)]
    
ts = sample_t()
xs = [x(t) for t in ts]
ys = [y(t) for t in ts]
plot(xs,ys)

---

9.1.3 Extending to 3 or more dimensions

We can use parametric curves to describe curves in any dimension. If we have a curve in three dimensions, all we need to do is describe z as a function of t, . Then for each value of t, we get a point (x(t), y(t), z(t)) on the curve in three dimensions.

In the code, you just need to add a few more lines:

def z(t):
    return yet_another_function(t)

ts = sample_t()
xs = [x(t) for t in ts]
ys = [y(t) for t in ts]
zs = [z(t) for t in ts]
plot(xs,ys)

---

9.2 Bezier curves

The core idea behind Bezier curves is simple:

Use polynomial functions and , and then plot y-versus-x.

Since a polynomial function is just a vector, we just need to find two vectors x and y and then plot y-versus-x. Note that this idea can be easily extended to Bezier curves in 3D space as well: we just need three vectors described by polynomials , , and then plot (x,y,z) in 3D space.

9.2.1 Bezier curve of second degree

We start with the identity

where each term is a polynomial - and hence a vector:

• , i.e. the blue curve
• , i.e. the pink curve
• , i.e. the green curve

These three vectors form the basis for calculating the Bezier curve. Note that for all three curves, whenever the input is between 0 and 1, the output is also between 0 and 1, as you can see if you zoom into this unit region to see it clearly (or zoom back out). And since the three polynomials sum to , their outputs at any are three weights that add up to exactly 1.

Remember that we want polynomial functions (aka vectors) and . We get them by taking weighted sums of these basis vectors. The weights and come from the three input points needed to create a Bezier curve of degree two: , , :

That's it! Given three points , and , you can calculate the parametric equations and and then plot y-versus-x to get the Bezier path. Let's see it in action.

We start with the three pink anchor points , and .

Joining the anchor points in order gives the grey control polygon.

We build the curve directly from the parametric polynomials we derived above. The point is just the weighted sum of the three anchors, using the basis polynomials as weights:

As sweeps from 0 to 1, this point moves through space; trace its path and you get the teal Bezier curve. Some observations:

• At the weights are , so the curve starts exactly at .
• At the weights are , so it ends exactly at .
• 's weight peaks at only 0.5, so at the curve is pulled toward but never reaches it.

---

9.2.2 Bezier curve of third degree

We start with the identity

where:

• , i.e. the blue curve
• , i.e. the pink curve
• , i.e. the green curve
• , i.e. the amber curve

These four vectors form the basis for calculating the Bezier curve of degree three. This looks a lot like what we did for Bezier curves of degree two. Again, for all four of these polynomials, whenever the input is between 0 and 1, the output is also between 0 and 1, as you can see if you zoom into this unit region to see it clearly (or zoom back out), and they sum to 1.

The parametric polynomial equations (aka vectors) and are again weighted sums of these four basis vectors, with the weights coming from the four input points , , , :

and similarly for with the weights .

Let's look at an example with the four anchor points , , and .

As before, the grey control polygon joins the anchors in order. We build the curve exactly as we did for degree two: the point is the weighted sum of the four anchors, using the four basis polynomials as weights:

As sweeps from 0 to 1, trace its path and you get the teal Bezier curve of degree three. Some observations:

• At the weights are , so the curve starts exactly at .
• At the weights are , so it ends exactly at .
• At the curve leans toward but never touches it, since 's weight is never 1.
• At it leans toward but never touches it, since 's weight is never 1.

---

9.3 Properties of Bezier curves

9.3.1 The entire curve lies inside the convex hull of the points

For the points [0,-3], [-2,3], [2,2], the Bezier curve always lies inside the triangle formed by these points. This follows from what we noticed about the basis polynomials: for the three weights are all non-negative and sum to 1, so every point of the curve is a weighted average of the anchor points.

The same holds in degree three: for the points [1,-3], [2,3], [-4,2], [3,-1], the Bezier curve always lies inside the convex hull formed by these points.

9.3.2 Tangents at the start and end points point towards the nearest anchor point

Given a Bezier curve of degree 2 with points startPoint, midPoint and endPoint, we draw tangents at startPoint and endPoint:

• The tangent at startPoint points in the same direction as the line joining the points startPoint and midPoint.

• The tangent at endPoint points in the same direction as the line joining the points endPoint and midPoint.

Similarly, given a Bezier curve of degree 3 with points startPoint, midPointA, midPointB and endPoint:

• The tangent at startPoint points in the same direction as the line joining the points startPoint and midPointA.

• The tangent at endPoint points in the same direction as the line joining the points endPoint and midPointB.

You can even get a closed form solution, i.e. an exact equation for the slope of the tangent at any point on a Bezier curve. For a Bezier curve of degree 2:

• At (the start point) the slope is - the slope of the line joining the first two points.
• At (the end point) the slope is - the slope of the line joining the last two points.

Similarly for a Bezier curve of degree 3:

• At the slope is , and at the slope is .

---

9.4 Bezier curves in 3 dimensions

First let's look at the code that takes three or four points as inputs and returns points on a Bezier curve:

def create_polynomial_function(*coefficients):
    def f(x):
        return sum(c * x**i for (i,c) in enumerate(coefficients))
    return f

def sample_t(start=0, end=1, num_points=100):
    step = (end-start)/(num_points-1)
    return [start + i*step for i in range(num_points)]

Point=[float,float]

def get_bezier_curve(*points:[Point]):
    assert len(points) in [3,4]
    xs, ys = list(zip(*points))
    if len(points) == 3:
        x1,x2,x3 = xs
        y1,y2,y3 = ys
        x_coefficients = [x1, 2*(x2-x1), x1 - 2*x2 + x3]
        y_coefficients = [y1, 2*(y2-y1), y1 - 2*y2 + y3]
    elif len(points) == 4:
        x1,x2,x3,x4 = xs
        y1,y2,y3,y4 = ys
        x_coefficients = [x1, 3*(x2-x1), 3*x1 - 6*x2 + 3*x3, -x1 + 3*x2 -3*x3 +  x4]
        y_coefficients = [y1, 3*(y2-y1), 3*y1 - 6*y2 + 3*y3, -y1 + 3*y2 -3*y3 +  y4]
    x = create_polynomial_function(*x_coefficients)
    y = create_polynomial_function(*y_coefficients)
    ts = sample_t()
    return list(zip([x(t) for t in ts], [y(t) for t in ts]))

To extend this idea to create Bezier curves in three dimensions, you only need to modify the get_bezier_curve function. Let's write a new function get_bezier_curve_3d which calculates points on a 3-dimensional Bezier curve:

Point3d = [float,float,float]

def get_bezier_curve_3d(*points:[Point3d]):
    assert len(points) in [3,4]
    xs, ys, zs = list(zip(*points))
    if len(points) == 3:
        x1,x2,x3 = xs
        y1,y2,y3 = ys
        z1,z2,z3 = zs
        x_coefficients = [x1, 2*(x2-x1), x1 - 2*x2 + x3]
        y_coefficients = [y1, 2*(y2-y1), y1 - 2*y2 + y3]
        z_coefficients = [z1, 2*(z2-z1), z1 - 2*z2 + z3]
    elif len(points) == 4:
        x1,x2,x3,x4 = xs
        y1,y2,y3,y4 = ys
        z1,z2,z3,z4 = zs
        x_coefficients = [x1, 3*(x2-x1), 3*x1 - 6*x2 + 3*x3, -x1 + 3*x2 -3*x3 +  x4]
        y_coefficients = [y1, 3*(y2-y1), 3*y1 - 6*y2 + 3*y3, -y1 + 3*y2 -3*y3 +  y4]
        z_coefficients = [z1, 3*(z2-z1), 3*z1 - 6*z2 + 3*z3, -z1 + 3*z2 -3*z3 +  z4]
    x = create_polynomial_function(*x_coefficients)
    y = create_polynomial_function(*y_coefficients)
    z = create_polynomial_function(*z_coefficients)
    ts = sample_t()
    return list(zip([x(t) for t in ts], [y(t) for t in ts], [z(t) for t in ts]))

There are other curves, like cubic splines, which also share very similar ideas to what we discussed here.

In the next chapter, we will look at one of the most important operations in linear algebra - the dot product.

---

← 8. Polynomial curves are vectors in disguise · 10. Dot product →