## 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)^{3}**p0** + 3(1-t)^{2}t**p1** + 3(1-t)t^{2}**p2** + t^{3}**p3**

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.

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)^{3}**p0** + 3(1-u)^{2}u**p1** + 3(1-u)u^{2}**p2** + u^{3}**p3**

**g** = (1-v)^{3}**p0** + 3(1-v)^{2}v**p1** + 3(1-v)v^{2}**p2** + v^{3}**p3**

The two equations are then simplified into

3(1-u)^{2}u**p1** + 3(1-u)u^{2}**p2** = **c**

3(1-v)^{2}v**p1** + 3(1-v)v^{2}**p2** = **d**

where

**c** = **f** – (1-u)^{3}**p0** – u^{3}**p3**

**d** = **g** – (1-v)^{3}**p0** – v^{3}**p3**

**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)^{2}u * 3(1-v)v^{2} – 3(1-u)u^{2} * 3(1-v)^{2}v

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