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

Comments

  1. This is nice, but there is an important point to note: There are an infinite number of Bezier curves passing through those four points. Choosing different values of u and v (for t) might produce very different Bezier curves.

  2. Vincent Tan says:

    Yes, there are an infinite number of Bezier curves. For simplicity’s sake, you can fix the values of u and v, say 0.33 and 0.67 respectively. This will then fix the resulting Bezier curve.

    Oh right, I didn’t mention default values of 1/3 and 2/3 anywhere in the article nor the source code. I guess they seemed so obvious to me that I neglected to mention them. Oops.

    The flexibility of u and v values is up to you, as long as 0< u,v <1 and u not equal to v. Practicality and simplification usually forces some kind of default value to theories... at least that's my experience... 🙂 Thanks for pointing that out!

  3. Mr Tan,
    This formula is very nice. Actually I am having a problem on calculating the control points, given a set of 2D curve data.

    I’ll try this with a set of t=0 to t=1,
    maybe with a simple interval of 0, 0.3,0.6, 1.

    I’m not programming the codes using C, since I’m currently doing this mini project using Matlab.

    The thing that ponders my mind is, once you’ve gotten the control points P1, P2, if you plot back the bezier curve equation P0,P1,P2,P3, will you get the exact curve similar to our curve earlier?

    Thanks man, you rock, cheers.

  4. Vincent Tan says:

    The short answer to your question is “Yes!”. That’s exactly what I’m doing. I’m finding the P1 and P2 that defines the Bezier curve I want, assuming the 4 points to pass through are P0, f, g, and P3 (disregarding numerical errors of course).

    You’ll probably find it easier to code in Matlab, since Matlab can calculate your inverse and manipulate vectors and matrices much better than arrays in C.

    Actually, I came up with the theory and algorithm because I was trying to move a game camera through 3D space. I just wanted to define 4 points and have the camera move semi-organically in a curve passing through those 4 points. The results look great, though I haven’t verified that my Bezier curve was correct… If you find that it doesn’t, let me know, and I’ll post your findings.

    And uh, you can call me Vincent… Mr Tan makes me feel positively old… and thanks for your compliments!

  5. I verified the control points (P1 and P2) are correct, provided that the user knows the value of the interval t at given f and g coordinates.

    That’s awesome.

    And in one situation when the user only a set of coordinates that defines a curve…The user knows the value of f and g…but not the ‘t’ for f and g.

    I tried this using various techniques, such as arc length approximation (after discretization of curve using splines), or simply having t = 1/segments, and all…

    But this forces the control point to be different than the desired/expected control point when the user knows the t value…

    As a mathematician, what could you suggest? I tried making a ‘learning algorithm’ but it drains me and I’m not getting nowhere 😆

    Cheers dude, you rock 😀

  6. Vincent Tan says:

    I don’t think you can find the control points without fixing the t values… As Yonatan mentioned above, there are an infinite number of Bezier curves passing through those 4 points. You just need to change the values of u and v accordingly, and you’ll get a new curve.

    Even if your desired pass-through points are spaced, for example, with one point away, and 3 points close together, you can’t say with certainty that the t values are 0, 0.8, 0.9 and 1 respectively.

    From what I can understand from your original comment, you’re probably trying to find a Bezier curve of degree n+1 to fit n points of 2D curve data. This means you’re not dealing with just u and v. You’re dealing with (n-2) variables. It’s going to be tough, trying to allow flexibility and still retain accuracy.

    Hopefully, your curve data comes with regularly spaced x-coordinate values, meaning the i-th point is maybe d units on the x axis away from (i-1)-th point. Then you can set t = 1/segments.

    If not, then the d(i)s are different from each other. So see if you can form a function for t based on the d(i)s. I hope you understand what I’m talking about…

    Then you can try formulating the matrix as given in the article, but expanding it for a (n+1) degree Bezier curve. And you can solve for all the P(i)s for i=1 to (n-1) all at one go.

    I’m suggesting the (n+1) degree approach instead of piece-wise cubic, because the piece-wise cubic Bezier curves might form a continuous curve, but not smooth (not differentiable) at the end points.

  7. Vincent,
    I work backwards to the quadratic bezier curve instead of guessing the t value for the cubic bezier curve.

    I tried the arc-length approximation but it doesnt lead me anywhere, because even if we knew the value of our Control Points, the coordinate on the curve is not evenly spaced…Eventhough the t is with even interval, for example t = 0,0.2,0.4,0.6,0.8,1.

    This is getting more and more interesting. I made a simple learning algorithm so that the program can guess the coordinate of the correct Control Point when the user input the set of the coordinate curve…So now we have the correct coordinate of CP, and the precise value of t.

    Working with quadratic bezier curve is easy, but less flexibility in curve shape. I am now looking into re-parameterization.

    Thanks Vincent, you’re the best. 🙂

  8. Vincent Tan says:

    You’re welcome. I’m glad you got something out of it.

  9. Good work Vincent!

    This is exactly what I need, only I typically have more than four points.

    Have you any idea how to go about this? For segments to match, the angles must match. The only conclusion is that I need to vary u and v. It should be possible, I think, but the math eludes me.

    Tia,
    Guus.

  10. Vincent Tan says:

    Hi Guus, suppose that you want a Bezier curve passing through 10 points. Then you’re working with a degree 9 Bezier curve, and there are 8 unknowns (and not 2, as in u and v).

    If you follow the logic I wrote, you’d have to solve an 8 by 8 matrix. I don’t know the required conditions to guarantee a solution.

    This is why you’d need to do Gaussian elimination to iteratively compute a solution, if there’s one (instead of the quick and dirty method I used with a 2 by 2 inverse matrix multiplication).

    You’re welcome to do research on how to solve 8 linear equations with 8 unknowns using Gaussian elimination. That’s how I would do it if I wanted.

  11. Vincent,

    Thanks, I will put some effort in resolving this. There are a few mathematicians in my family, so I should be able to get help.

    Ciao,
    Guus.

  12. Vincent Tan says:

    Hey Guus, let me know how it turns out. I want to know if it can be scaled to higher degree Bezier curves too.

  13. You might want to look into cardinal splines. They are the typical way to solve a point interpolation problem:
    http://en.wikipedia.org/wiki/Cardinal_spline#Cardinal_spline

    It may be equivalent to your formulation… I confess that I just skimmed your equations. I ended up here by mistake when looking for something else.

  14. Vincent Tan says:

    Cardinal splines *do* look similar to my formulation. Thanks Bill.

  15. Man, you are awesome!!!!!! this article is fantastic. thanks!!!!!!!!!!!!!!!!!!!!!!!

Trackbacks

  1. […] 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 […]

  2. […] wrote something on reverse engineering Bezier curves about… *goes to check* woah, 2 years ago! I don’t remember it being that long… […]