Smooth Bezier splines

Apparently, having mathematically defined curves that pass through a set of desired points is a thing. And (cubic) Bezier splines are popular for this. Professor Dagan (mentioned previously) sent me a link.

Smooth Bézier Spline Through Prescribed Points

The article outlines a method that given a set of points you want your Bezier curve to pass through, calculate the required control points of the Bezier curve. This is similar to what I wrote here.

The difference is that my method requires the inverse of the coefficient matrix to exist, which it does. The method in that article requires the first and second derivatives of the Bezier curve to be continuous.

Cubic polynomials and cubic Beziers

So it turns out that for cubic Bezier curves, t values of 0, 1/3, 2/3 and 1 have special meanings. A general cubic polynomial is of the form

y = a0 + a1 * x + a2 * x^2 + a3 * x^3

where ai’s are real constants.

If the variable x is limited to the interval x0 <= x <= x0 + χ (that's the Greek letter Chi), where χ > 0, then it’s equivalent to a special case of cubic Bezier curves. Namely, when the t values are 0, 1/3, 2/3 and 1.

In fact, there’s a mathematical proof of it. Thanks to Professor Samuel Dagan of Tel-Aviv University for writing in and letting me know of his work. Here’s more of his work.

Does the point lie on the Bezier curve?

Someone recently asked me how to tell if a point lies on a Bezier curve.

For the purposes of discussion, it’s a quadratic Bezier curve and all 3 control points are known (or the start and end points and the 1 control point if you prefer). You can read more about the reverse process of finding the control points here, which is the reference point of that person’s question.

The answer is actually straightforward. Substitute everything into the Bezier curve equation and solve for t. Here’s the quadratic Bezier equation:
B(t) = (1-t)^2 * p0 + 2(1-t)t * p1 + t^2 * p2

Let’s say p0 is [1,1] and p1 is [1.5,4.5] and p2 is [2,3]. We’ll keep the points in 2 dimensions to keep the maths working less cumbersome. And let’s say the point you want to check is [1.8,3.4]. We substitute all the points into the equation, and we get this:

[1.8,3.4] = (1-t)^2 * [1,1] + 2(1-t)t * [1.5,4.5] + t^2 * [2,3]

I know, it doesn’t look pretty. But hey, we’re doing this by hand. If you’re writing code to generalise the solution, the code will probably look just a little uglier, but the solution will come out faster. Like probably instantly given the current modern processors.

Because we’re dealing with 2 dimensional points, that equation splits into 2 separate equations (with scalars instead of vectors as coefficients), like so:
1.8 = (1-t)^2 * 1 + 2(1-t)t * 1.5 + t^2 * 2
3.4 = (1-t)^2 * 1 + 2(1-t)t * 4.5 + t^2 * 3

If you have 3 dimensional points, you’d have 3 equations. Note that even then, the degree of your equations remains as 2. The degree of the Bezier curve is independent of the number of dimensions you’re working with.

If you simplify
1.8 = (1-t)^2 * 1 + 2(1-t)t * 1.5 + t^2 * 2

You get t = 0.8. It so happens that in this case, there’s only one solution.

If you simplify
3.4 = (1-t)^2 * 1 + 2(1-t)t * 4.5 + t^2 * 3

You get
5*t^2 – 7*t + 2.4 = 0

and after solving for that, you get t = 0.6 or t = 0.8 (you’re a smart person, you know how to solve a quadratic equation, right?)

Now, the solution t=0.8 appears in the solution sets of both equations. Therefore, the point [1.8,3.4] lies on the Bezier curve. In fact, t=0.8 is the t value.

Multiple solutions

What if you get multiple t values appearing in multiple solution sets of equations?

Consider the case where p0 is [1,1], p1 is [2,3], and p2 is [1,1]. Notice that the start and end points are the same point. Let’s say you want to know if the point [1,1] lies on the curve (yes I know it’s the same point). Substituting all the points, we get:

[1,1] = (1-t)^2 * [1,1] + 2(1-t)t * [2,3] + t^2 * [1,1]

This gives us the 2 equations:
1 = 1 – 2*t + t^2 + 4*t – 4*t^2 + t^2
1 = 1 – 2*t + t^2 + 6*t – 6*t^2 + t^2

They simplify to:
2*t^2 – 2*t = 0
4*t^2 – 4*t = 0

Hey presto! The solution set is t=0 or t=1 for both equations. Therefore, the point [1,1] lies on the curve. In fact, it lies on the curve where t=0 or t=1. And t=0 and t=1 happens to coincide with the start and end points respectively.

The whole point (haha!) is that, as long as you have at least one value of t that appears in the solution sets of all the equations, then said point you’re checking lies on the curve.

Higher degree Bezier curves

This is a toughie. If you have a cubic Bezier curve, then you’re solving a degree 3 polynomial (of t). If you have a Bezier curve of degree N, then you’re solving a degree N polynomial.

There are algorithms to solve generic degree polynomials, but they are out of scope here. Assuming the highest degree of Bezier curves you’ll ever work with is 3 (cubic), then this Wikipedia article on cubic functions will help. Remember, cubic Bezier curve equations are still cubic equations.

Higher dimensionality

The number of dimensions you’re working with determines the number of equations you need to solve. If you’re working with 5 dimensional points, then you need to solve for 5 equations.

For example, if you’re working with cubic Bezier curves and using 5 dimensional points, then you need to solve 5 cubic functions. You will have possibly 3 (unique) t values for each equation. Let’s say your solution sets are as follows:
t = -1, 3, 5
t = 0, 1, 3
t = -2, 2, 3
t = 3, 3, 4 (yay repeated values!)
t = 3, 6, 8

The value t=3 appears in all 5 sets of solutions, therefore your point lies on the curve.

Keep it real

In the process of solving your equations, there’s a possibility that you might get imaginary solutions. You know, those involving the square root of -1. Dismiss them.

Your Bezier curve is in the real world. The point you’re checking must therefore also lie in the real world.

Unless you’re working with some abstract imaginary Bezier curves on an advanced maths paper. Then good luck to you! The logic above for solving still applies.

Actual applications

When applying the above, you don’t usually get nice numbers like [1.8,3.4] lying on the curve with t=0.8. You get numbers with lots of numbers behind the decimal point that seems to continue forever. You don’t get exact values.

What if you get a t=0.798 for one equation, and t=0.802 for another equation?

Use your common sense. Set an error margin for what is acceptable.

My suggestion is to NOT use the values of t to check for the margin. Substitute the values of t into the equation, and then check the points if they’re within the error margin.

This means you don’t check the difference between t=0.798 and t=0.802, which is 0.04. Is 0.04 within your error margin? Maybe. But you’re not checking for this.

You substitute t=0.798 and t=0.802 into the equation, and you get 2 points: [1.798,3.40198] and [1.802,3.39798]

Then you say, “Are these points close enough that I consider them to be the same point?” Use whatever you think is appropriate. I think the Euclidean distance norm works fine. Then check if that “close enough” criteria is within your error margin.

If you’re checking for [1.8,3.4], then ask yourself, “Is [1.8,3.4] close enough to [1.798,3.40198]? And is [1.8,3.4] close enough to [1.802,3.39798]?”

Obviously, doing this by hand sucks big time. Good thing you’re a programmer.

Bezier curves prefer tea

My maths professor was hammering on the fact that Citroen used Bezier curves to make sure their cars have aesthetically pleasing curves. Again. (This is not a sponsored post from the automaker).

While I appreciate his effort in trying to make what I’m learning relevant to the real world, I kinda got the idea that Citroen used Bezier curves in their design process. Right about the 3rd tutorial lesson.

My professor then went on to give us homework. “Us” meaning 5 of us. It was an honours degree course. It wasn’t like there was a stampede to take post-graduate advanced maths lessons, you know.

Oh yes, homework. My professor, with wisdom acquired over years of teaching, gave a blend of theoretical and calculation-based questions. Any question that had the words “prove”, “justify”, “show” are probably theoretical questions. Calculation-based questions are like “What is 1 + 1?”. Everyone, at least theoretically (haha!), should be able to do the calculation-based questions. The theoretical questions would require more thinking (“Prove that such and such Bezier curve is actually equal to such and such.”).

My friend, who took the course with me, loved calculation-based questions. She’d sit patiently and hammer at the numbers and the calculator. I can’t say I love them. My professor once gave a question that amounted to solving a system of 5 linear equations with 5 unknowns, which amounted to solving a 5 by 5 matrix. By hand. (It involves 15 divisions, 50 multiplications and 50 subtractions. There’s a reason why linear algebra and numerical methods were pre-requisites) I wanted to scream in frustration, throw my foolscap paper at him, and strangle him. Not necessarily in that order.

This coming from someone who is fine with writing a C program doing memory allocations (using the malloc function. And then manually freeing the pointer with the memory allocation. We didn’t have garbage collection, ok?) to simulate an N-sized matrix, and then perform Gauss-Jordan elimination on the matrix. I used that program to solve a 100 by 100 matrix. But I dreaded solving a 5 by 5 matrix by hand.

It probably explains why I remember Bezier curves so much.

Anyway, a while ago, someone sent me a question (through Facebook, of all channels). He asked, for a given “y” value of a Bezier curve, how do you find the “x” value?

That is a question without a simple answer. The answer is, there’s no guarantee there’s only one “x” value. A cubic Bezier curve has a possibility of having 1, 2 or 3 “x” values (given a “y”). Here’s the “worst” case scenario:

Multi x values

So you can have at most 3 “x” values. In the case of the person who asked the question, this is not just wrong, but actually dangerous. The person was an engineer, working on software that cuts metal (or wood). The software had a Bezier curve in it, which it used to calculate (x,y) coordinate values to direct the laser beam (or whatever cutting tool) to the next point (and thus cut the material).

If a “y” value has multiple “x” values, the software won’t know which “x” value you want. And thus cut the material wrongly.

The only way a Bezier curve has only 1 value, is if it’s monotonically increasing/decreasing. That means for all values of x and y such that x <= y [or x >= y], that f(x) <= f(y) [or f(x) >= f(y)].

Bezier curves don’t work well in the Cartesian plane. They work fine after you’ve used them to calculate values, and then transfer onto the Cartesian plane. Bezier curves prefer to work with values of t.

3D Bézier curve editor

Timo Suoranta created a 3D Bézier curve editor. As of this writing, the program runs on Windows and requires OpenGL version 3 or later (shaders are involved). Here’s a screenshot:

Bezier curve editor
[click for larger image]

It looks awesome. What, no? Then you have to understand picking. In 2D, any point you click on the screen is exact. The point you click on is the point selected.

In 3D, it’s different. There are an infinite number of planes behind that virtual screen you picked on. Think of looking up at the clouds in the sky. You know the water droplets are scattered sparsely and densely in the sky. You know they are in a 3D space. But you, looking up at the sky, only see one plane, the 2D plane that has the water droplets rendered onto.

In this case, it’s simpler. We are only concerned with the points on the Bézier curve itself. Timo used the closest point to the clicked point on the screen as the chosen point. Basically you “shoot” a ray from the clicked point into the vanishing point in the far distance (far far far distance, as in infinity far). When your ray hits the Bézier curve, that’s the chosen point. You can find out more about the method by searching on the Internet for “3d picking” or something similar.

So how do you edit a point once it’s chosen? Timo solved it by using 3 cones to represent the X, Y and Z axes. Dragging on the cones move the point along the respective direction of the axis. Notice the 3 cones at the right side.

Bezier curve editor with axes
[click for larger image]

I believe most 3D rendering software use something similar to edit points.

Now notice the small details Timo added:

  • The floor is a checker board to illustrate the notion of space
  • The vertical lines drawn from the points on the curve to the checker board to show the spatial relation
  • If you hover over the big blue spheres, the checker board, or the curve itself, they glow pulse-like

Wait, you haven’t downloaded the program? Here’s the link.

Help! Getting a “nice” reverse engineered Bézier curve

Commenter Timo wants to know how to get a nice shape for a reverse engineered Bézier curve.

The question started from calculating the control points of a cubic Bézier curve if you’re given 4 points that lie on the curve, assuming the first and last given points were also the first and last control points. I wrote a similar article for a quadratic Bézier curve too.

To sum up, you have 1 degree of freedom when working on a quadratic Bézier curve. In the case of a cubic Bézier curve, you have 2 degrees of freedom, meaning 2 variables in the calculation that you have to decide on. Now this posed a problem, because there are an infinite number of solutions. How do you decide on a numeric value?

Well, for a quadratic Bézier curve, the simplest and obvious option is to choose the second given point (since the first and last control points are determinable) to be at the halfway mark. For a cubic Bézier curve, the second and third given points are chosen to be at the 1/3 and 2/3 mark along the curve respectively. Now this may or may not be suitable, but it does give you something to start with.

I want to state right now, that I had not been doing formal mathematics for a while. There is a limit to what I know, and I’m not an expert. I just know enough to figure out how to solve problems. Sometimes, it’s not enough. Keep that in mind.

“Nice curve” is subjective

Now Timo’s problem is getting a better shaped cubic Bézier curve from those calculations. Since the 4 given points are fixed, and the first and last control points are also fixed, the only thing you can manipulate are the second and third control points. Which in turn means deciding on values of u and v to get a “nice” cubic Bézier curve in the end.

This, “niceness”, is a subjective criteria. How do you determine if a cubic Bézier curve looks nice? Remember that we don’t have the control points yet. So we don’t know how the curve looks like. So we don’t even know if manipulating the second and third control point to not be at 1/3 and 2/3 will result in a nice curve. It’s a chicken and egg problem.

Apportioned chord length

During the correspondence with Timo, some solutions were discussed. The next simplest set of values to try for u and v are calculated based on the given points.

Let d1 be the distance between the first and second given point.
Let d2 be the distance between the second and third given point.
Let d3 be the distance between the third and last (fourth) given point.

Then let u = d1/(d1 + d2 + d3) and v = (d1 + d2)/(d1 + d2 + d3). This should result in a curve that’s “better shaped” than the (u,v) pair (1/3, 2/3). When I wrote that article for the cubic curve version, this was the next default set of values for u and v, but I didn’t want to add too much more. Well, nobody asked, so I left it as it was.

It turns out that Don Lancaster already wrote about it. He called it “apportioned chords” method.
http://www.tinaja.com/glib/nubz4pts1.pdf

Inflection points

Then Timo had another problem. He wanted the second and third given points to also lie at the “loop tips”. What are loop tips? After some clarification, I believe Timo is referring to the inflection points on the curve. An inflection point

is a point on a curve at which the curvature (second derivative) changes signs. The curve changes from being concave upwards (positive curvature) to concave downwards (negative curvature), or vice versa.

A cubic Bézier curve can have 0, 1 or 2 inflection points. If it’s a straight line, it has 0. If it’s U-shaped, it has 1. And if it zigzags, it has 2. And Adrian Colomitchi proved that there are at most 2 inflection points on a cubic Bézier curve.

UPDATE: The following diagram is wrong. Please refer to this article for the correct version. I was thinking of points where the second derivative was zero, not when it changed signs (as defined above).

Inflection points

As you can see, inflection points don’t necessarily have to coincide with the given points.

By the way, I used Paint.NET for the illustration. I took a screenshot of me drawing the curve, still with the given points visible (noted by the small squares). Paint.NET appears to have succeeded in doing the very thing Timo wants, to render a cubic Bézier curve using 4 given points. Of course, I’m assuming the image editor is using cubic Bézier curves…

The math paper

I found another reference with a more explicit mathematical formulation to help Timo.
http://www.cis.usouthal.edu/~hain/general/Publications/Bezier/bezier%20cccg04%20paper.pdf

As of this writing, page 3 of that paper explicitly shows the calculation needed to find the inflection points of a cubic Bézier curve, if they exist. Let me emphasise that again. The curve might have 2 inflection points, only 1 inflection point, or none at all (a straight line, the trivial version of a Bezier curve, has no inflection points).

Maximum curvature

Then Timo found another forum posting for the fast calculation of maximum curvature. An inflection point would have the “maximum curvature”. The problem with that solution is that it assumes we have the control points.

So my suggestion was to do iteration. Use my method to get a set of control points. Perhaps use the apportioned chords to start off with a good set of control points. Then apply the maximum curvature solution to find the inflection points and the associated values of t. With those values of t, pump them back into my method to find a new set of control points. Pump those control points into the maximum curvature solution to find inflection points and their t values. Iterate till the t values between iterations are within acceptable margins of error.

Caveat: I don’t know if this combination of 2 algorithms in an iterative manner will converge. I have not tested this. Use at your own risk.

Scaling up to 3 dimensions

Anyway, Timo found another solution himself (he didn’t say what though). He still needed to handle that cusp point. What cusp point, you ask? It’s in page 3 of that paper I mentioned above. That paper is for 2 dimensional cubic Bézier curves. The degree of the curve is independent of the degree of the dimensions. Timo wants to know how the 3 dimensional case will look like.

Now, the method of finding inflection points is to do a cross product of the first derivative and second derivative of the cubic Bézier curve equation. The Bézier curve is parametrised into

x(t) = ax * t^3 + bx * t^2 + cx * t + dx
y(t) = ay * t^3 + by * t^2 + cy * t + dy

and using the Bézier basis matrix, the coefficients are

ax = -x0 + 3*x1 – 3*x2 + x3
bx = 3*x0 – 6*x1 + 3*x2
cx = -3*x0 + 3*x1
dx = x0

ay = -y0 + 3*y1 – 3*y2 + y3
by = 3*y0 – 6*y1 + 3*y2
cy = -3*y0 + 3*y1
dy = y0

Set the cross product to 0. The inflection points are found at values of t when you solve that equation:

x’ * y” – x” * y’ = 0

where x’ and x” are the first and second derivatives of x(t). Similarly for y’ and y”. The solution is in that paper I mentioned before.

This is if the curve is in 2D. The cross product of 2D vectors is a scalar. And we set the scalar to 0 to solve for t. The cross product of 3D vectors is a vector, and so we’re solving with a zero vector.

So with
z(t) = az * t^3 + bz * t^2 + cz * t + dz
for the third dimension, we have

x’ = 3 * ax * t^2 + 2 * bx * t + cx
y’ = 3 * ay * t^2 + 2 * by * t + cy
z’ = 3 * az * t^2 + 2 * bz * t + cz

x” = 6 * ax * t + 2 * bx
y” = 6 * ay * t + 2 * by
z” = 6 * az * t + 2 * bz

The cross product is the determinant of the following
Cross product

where i, j, k are the unit vectors. I’ll leave it to you to find out the formula for the determinant of a 3 by 3 matrix.

So we’re going to solve this:
0 = (y’ * z’’ – z’ * y’’) * i – (x’ * z’’ – z’ * x’’) * j + (x’ * y’’ – y’ * x’’) * k
where 0 is the zero vector.

This implies that

y’ * z’’ – z’ * y’’ = 0
x’ * z’’ – z’ * x’’ = 0
x’ * y’’ – y’ * x’’ = 0

This time the zeroes are scalars. We now have 3 times the number of equations to solve when compared to the 2D case. This means there are potentially 6 values of t for the inflection points to check. Hopefully, there will be repeated values of t. Hopefully, the number of unique values of t is 2 or less (remember Adrian’s proof?).

If a t value is repeated, it’s probably an inflection point. What if we get 6 unique values? Is a 6-unique-value case even possible? I don’t know. You’ll have to interpret the values in the best way you can, based on some assumptions and arguments.

What do you think?

So after reading through that entire article, what do you think? Comments on the methods I described? Do you have a new method? Your thoughts on whether this problem is even solvable? That I’m a complete idiot?

Let me know in a comment. Or better, write a blog post and tell me about it. Because if it took me that long to explain the solutions, your solution is probably just as long. It’s a Bézier curve. A picture might be appropriate.

Reverse engineering quadratic Bézier curves

I wrote an article on cubic Bézier curves almost 3 years ago. And there had been emails and comments sporadically during that period. The latest one was from a lady, so I decided to write something about it (yes, I’m biased).

The recurring (if you count 2 or 3 as recurring) question is about quadratic Bézier curves. I provided a method for calculating the 4 control points of a cubic Bézier curve, given 4 points that the curve has to pass through. The question is, how do you calculate the 3 control points of a quadratic Bézier curve, given 3 points that the curve has to pass through? The 1st and 3rd points are also the end points of the curve.

As with the cubic version, there are infinitely many solutions. The question I posed above missed out a crucial element which would give a unique solution. How far along the curve is the 2nd point? Let’s look at the quadratic Bézier equation first:

B(t) = (1-t)^2 * p0 + 2(1-t)t * p1 + t^2 * p2

where p0, p1 and p2 are the control points, and t in [0,1]

Suppose you have 3 points that the curve has to pass through. The 1st and 3rd points are also the 1st and 3rd control points (substitute t=0 and t=1 into the equation to see why that is so). That leaves the 2nd control point to be calculated. If you didn’t know, the inner control points of a Bézier curve don’t necessarily fall on the curve itself (and usually don’t).

Since you know the 3 points that pass through the curve, and the 1st and 3rd control points are known, let the points be p0, f and p2, where f is the point on the curve when t=u. Stating the value of u is the crucial element for a unique solution. In the case of a quadratic Bézier curve, the value off the top of my head is 1/2. Meaning the 2nd known point is assumed to fall about halfway along the curve. You may have a different opinion based on the problem you’re trying to solve.

So let’s substitute into the equation, shall we? At the 2nd known point f, we have

f = (1-u)^2 * p0 + 2(1-u)u * p1 + u^2 * p2

Rearranging the terms, we have

p1
= [f – (1-u)^2 * p0 – u^2 * p2] / 2(1-u)u
= 1/(2(1-u)u) * f – (1-u)/2u * p0 – u/2(1-u) * p2

Remember that u is determined by you (1/2 is a good value if you have no other information otherwise). p0, f, and p2 are the 3 known points that pass through the curve (f is the point where t=u). So the only unknown is p1, the 2nd control point.

And I can “cancel” the (1-u) and u terms in the simplification because u is strictly between 0 and 1. In particular, u cannot be equal to 0 or 1.

There you have it. A unique solution to finding the control points of a quadratic Bézier curve.

An example

But hey, I’m feeling generous. I’ll do up a solution with real values.

Suppose you have 3 points [1,1], [2,3], [4,2] that pass through a quadratic Bézier curve. The 1st and 3rd points, [1,1] and [4,2] are the 1st and 3rd control points respectively. That leaves calculating the 2nd control point such that the curve pass through [2,3] when t=0.5 (let’s assume [2,3] is halfway along the curve).

Let’s look at the final stage of our 2nd control point calculation

p1
= 1/(2(1-u)u) * f – (1-u)/2u * p0 – u/2(1-u) * p2
= 1/(2*(1-0.5)*0.5) * [2,3] – (1-0.5)/(2*0.5) * [1,1] – (0.5)/(2*(1-0.5)) * [4,2]
= 2 * [2,3] – 0.5 * [1,1] – 0.5 * [4,2]
= [4,6] – [0.5,0.5] – [2,1]
= [1.5,4.5]

So the final control points are [1,1], [1.5,4.5] and [4,2].

Quadratic Bezier curve

Curve tension

But wait, there’s bonus material! The lady also asked about curve tension. I’m not sure if that’s the correct term. Basically, she wanted to know how to skew the 2nd control point towards the 1st or 3rd control points.

This one’s easy. Just adjust your u value. If you assume u=0.2, then the 2nd control point is skewed towards p0, the 1st control point. If you assume u=0.8, then the 2nd control point is skewed towards p2, the 3rd control point.

So to skew towards p0, let u be closer to 0. To skew towards p2, let u be closer to 1.

Remember, u is decided by you, unless the problem you’re solving states otherwise.

Linear and cubic interpolation

Interpolation is a method of calculating a value from a set of given values. We’ll be looking at interpolation with a bias towards image processing, but the theory can be generalised for other purposes. You’ve probably already solved some interpolation problems without knowing it. Let me give you an example.

A distance problem

Suppose there are 3 towns A, B, C and they happen to lie on a straight line, in that order. B is 5 kilometres away from A, and C is 15 kilometres away from A. If you travel one quarter of the way from town B to town C, how far are you from town A?

Distance problem

To solve it, you can figure out the distance between B and C, which is 15 – 5 = 10 km. One quarter of the way means 1/4 * 10 = 2.5 km. Then add the distance between A and B to this and you have 5 + 2.5 = 7.5 km.

Linear interpolation

If you visualise the problem as interpolating between 2 points, then B becomes the point p0 with a value of 5 (km) and C becomes the point p1 with a value of 15 (km). The usual variable used is t, so the generic formula is:
f(t) = (1 – t) * p0 + t * p1, where t lies between 0 and 1 inclusive.

Using this, we have
f(1/4) = (1 – 1/4) * 5 + 1/4 * 15
= 3/4 * 5 + 1/4 * 15
= 7.5

This is linear interpolation. Linearity refers to the power of the variable t, which is 1. Note that there’s no stopping you from using negative values of t or values greater than 1.

Suppose you travelled from B to A one quarter of the distance between B and C. How far are you from town A?
f(-1/4) = (1 – (-1/4)) * 5 + (-1/4) * 15
= 5/4 * 5 – 1/4 * 15
= 2.5

Suppose you travelled from B to C and went past C by a quarter of the way. How far are you from town A?
f(5/4) = (1 – 5/4) * 5 + 5/4 * 15
= -1/4 * 5 + 5/4 * 15
= 17.5

What happens if you get a negative result?
f(-1) = (1 – (-1)) * 5 + (-1) * 15
= 2 * 5 – 15
= -5

It means you’re 5 kilometres away from town A. You’re just in the opposite direction from towns B and C. The calculation result is correct. It’s how you interpret the value.

Applications in image processing

A common operation in image processing is manipulating height maps. Height maps are usually greyscale bitmap files where a white pixel (RGB values are 255 for all 3) is the highest point, and a black pixel (RGB values are 0 for all 3) is the lowest point.

Terrain editor in Bryce

You know enlarging photographs can give you some weird results. What happens is you’re trying to fill in the blanks in a larger image using values from the original image. Where do you think the image editing software comes up with values? Interpolation.

If you think of the red, green and blue values of image pixels as 3 different “height maps”, then you’re just performing interpolation on 3 values. Suppose we’re talking about linear interpolation between two pixels. You’ll interpolate between the red component of the 2 pixels and get a value. Similarly you do it for the green and blue components. The calculated results of the red, green and blue become the interpolated colour.

Cubic Bezier interpolation

There are all kinds of cubic curves available. The Catmull–Rom spline, the non-uniform rational B-spline (NURBS) and I didn’t really want to write anything on the subject after I remember my Hermite splines… I love Bezier curves though, so I thought maybe I can write something with that.

Instead of 2 points used in linear interpolation, cubic interpolation uses 4 points. To illustrate, suppose you’re on an undulating plain with small hills undulating in their usual carefree manner. You’re in between two such (undulating) hills and you want to find out how high you are.

Instead of linear interpolating your way through these two (undulating) hills, the better way will be to interpolate with another 2 (undulating) hills! Ok, I’m stopping with the undulating thing…

Undulating hill interpolation

The Bezier curve equation looks like this:
B(t) = (1-t)^3 * p0 + 3*(1-t)^2 * t * p1 + 3*(1-t)* t^2 * p2 + t^3 * p3
where p0, p1, p2, p3 are the (height) values, and t lies between 0 and 1 inclusive.

You will be between p1 and p2. Let’s also assume that the hills are equidistant from each other. Like the pixels on an image, the hills shall be of equal distance from its neighbour.

Because of this equidistant property, p1 is 0.33 (roughly 1/3) units away from p0, p2 is 0.67 (roughly 2/3) units away from p0 and p3 is 1 unit away from p0.

How do you know what’s the value of t to use? You might be able to calculate the t if you do linear interpolation between p1 and p2. But that t value is different from the t value in the Bezier curve.

Ahhh… once you get the t-linear value, you interpolate with 0.33 and 0.67 to get the t-Bezier value. Confused? Suppose you’re one quarter way from p1 to p2. Your t-linear value is 1/4. Interpolate that with 0.33 and 0.67 to get
f(1/4) = (1 – 1/4) * 0.33 + 1/4 * 0.67
= 0.415

And 0.415 is your t-Bezier value. Voila!

You skipped the quadratic power!

I know. It’s logical to think that there’s a power 2 somewhere. But there isn’t. There is one fundamental flaw with quadratic interpolation. Which segment do you use?

Quadratic interpolation has issues...

In closing

Interpolation is just a method of creating data values using a set of existing data. What those created values mean is up to you to interpret.

In image processing, interpolation can be used to fill in blanks when enlarging an image. It doesn’t guarantee that the enlarged image looks good. Image processing is very much an aesthetic-based operation. I’ll talk a bit more on this when I get to writing code to rotate images.

Reverse engineering Bezier curves

My initial contact with Bezier curves came when I was studying 3 dimensional computer graphics. The professor introduced the standard cubic Bezier curve equation, which looks something like this

B(t) = (1-t)3p0 + 3(1-t)2tp1 + 3(1-t)t2p2 + t3p3
where p0, p1, p2, p3 are the control points.

WARNING: you might find this an intensive discussion on math, 3D theory and programming.

So the interesting thing about Bezier curves is that they are easy to work with, theoretically and programmatically. There’s only one problem; the curve does not pass through its control points. The curve actually lies in the convex hull of the control points.Convex hull of bezier curve
This means the control points may not lie on the curve, which makes calculating tangents and normals (for use in 3D trigonometry) tedious.

What I want to do is to define four points and have a Bezier curve passing through all four points. Basically, given the four original points q0, q1, q2 and q3, I will find four points p0, p1, p2 and p3 such that the Bezier curve calculated using points p(i), will pass through the points q(i).

So going back to the equation above, when t is zero, the equation effectively collapses into just p0. When t is one, the equation gives p3. When t is between zero and one, the resulting point lies on the curve itself, so iterating t from zero to one will give the Bezier curve. Since we know the curve will pass through p0 and p3, we need to find p1 and p2.

Suppose we want the curve to pass through p0 when t=0, f when t=u, g when t=v and p3 when t=1, where f and g are the points to be passed through. Next, we make sure that 0 < u,v < 1 and u not equal to v. These conditions will ensure a solution can be found. Next, we substitute the desired points into the equation:

f = (1-u)3p0 + 3(1-u)2up1 + 3(1-u)u2p2 + u3p3
g = (1-v)3p0 + 3(1-v)2vp1 + 3(1-v)v2p2 + v3p3

The two equations are then simplified into

3(1-u)2up1 + 3(1-u)u2p2 = c
3(1-v)2vp1 + 3(1-v)v2p2 = d

where
c = f – (1-u)3p0 – u3p3
d = g – (1-v)3p0 – v3p3

UPDATE: I’m assuming that u = 1/3 and v = 2/3, but they can be any value as long as 0 < u,v < 1 and u not equal to v (and logically u < v). It is likely that f is somewhere 1/3 of the way between p0 and p3, and that g is somewhere 2/3 of the way between p0 and p3. BUT it’s not a given, so you still need to determine that. 1/3 and 2/3 just happens to be the “logical, and common-sensical” default.

This set of equations has a unique solution when 0 < u,v < 1 and u not equal to v, and assuming c and d aren’t both zero vectors. The equations have a unique solution because the determinant is not zero. Let’s transform the set of equations into matrix form before explaining what a determinant is.

The determinant for the above 2 by 2 matrix on the left-most side is
3(1-u)2u * 3(1-v)v2 – 3(1-u)u2 * 3(1-v)2v

Factorising this, we get
9uv(1-u)(1-v)[(1-u)v – u(1-v)]
= 9uv(1-u)(1-v)[v -uv -u +uv]
= 9uv(1-u)(1-v)[v – u]

Since 9 obviously is not equal to 0, and 0 < u,v < 1 (so u,v not equal to 0 and (1-u),(1-v) not equal to 0) and u not equal to v (so v-u is not equal to 0), therefore, the determinant is not equal to 0. By a theorem in linear algebra, this means the set of (linear) equations has a unique solution. For a 2 by 2 matrix, the determinant can be obtained by taking the product of the top-left element and bottom-right element, then subtract the product of the top-right element and bottom-left element. Like drawing a cross.

Next, we multiply the inverse of the 2 by 2 matrix on the left of both sides of the equation and we get

Note that the inverse will cancel the matrix on the left side. The inverse (of a 2 by 2 matrix) is obtained by swapping the top-left and bottom-right elements, then switch the signs of the top-right and bottom-left elements, and then divide each element by the determinant. The determinant is non-zero, so division by zero is not a problem. A non-zero determinant also means an inverse actually exists (by another theorem in linear algebra), so all of this works out fine. Now all you have to do is calculate that right side and that’s it. Make sure you calculate for x, y and z, meaning you have to do the calculation three times.

The determinant of an n by n matrix is generally difficult to find, as is the inverse of one. Refer to a linear algebra text book for the theories (they usually use a method called Gaussian elimination. The programmatic approach uses a slightly modified version to reduce computational errors). There’s a “quick and dirty” method for getting the determinant for a 3 by 3 matrix, but anything higher requires the aforementioned theories.

You can download my C program code of reverse engineering a Bezier curve to learn more.

If you enjoyed this article and found it useful, please share it with your friends. You should also subscribe to get the latest articles (it’s free).