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.

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).