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)³p0 + 3(1-t)²tp1 + 3(1-t)t²p2 + t³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)³p0 + 3(1-u)²up1 + 3(1-u)u²p2 + u³p3
g = (1-v)³p0 + 3(1-v)²vp1 + 3(1-v)v²p2 + v³p3

The two equations are then simplified into

3(1-u)²up1 + 3(1-u)u²p2 = c
3(1-v)²vp1 + 3(1-v)v²p2 = d

where
c = f – (1-u)³p0 – u³p3
d = g – (1-v)³p0 – v³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)²u * 3(1-v)v² – 3(1-u)u² * 3(1-v)²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.

Zip up or shut up

Today, I’m reminded of an article I read in the Men’s Health magazine. I can’t remember the entire thing, but there was something that stuck to my mind. Now, if there are ladies reading this, you might want to stop right here and go read something else, because what follows will be a shocking revelation of an undisclosed men’s toilet habit which might jar your sensibilities. Perhaps you ladies might even find this secret natural (hey, men actually do this!), but since I’ve never been in a ladies washroom before…

You still here?

Ok, here it is, and I want you to read everything carefully and slowly.

There is nothing, absolutely NOTHING, that is so important, that you have to talk about it with your pants down.

There had been quite a few instances where I’ll be, uh, minding my own business while in the washroom, and two guys would waltz in to do their business. And they would be talking to each other. They could be talking about a recent project, or the decision of so-and-so, or about the details of a business deal (a real one thankfully, not the one happening in the washroom. Sheesh.).

I don’t know about you, but I find it kind of awkward conversing while holding my pants up. Especially if you are also making sure the other person isn’t looking at you. Seriously, you could have struck lottery (and positively thrilled to tell me), the building could be on fire, or Armageddon is nigh. I don’t care what it is, it can wait a couple of minutes.

Embarrassingly,  as I’m writing this, I recall a presentation for my Japanese language class. I wrote a scene with my fellow student, where both of us were in the toilet and discussing details of a karaoke session we were going for afterwards. Ah, the follies of youth…

Which brings me to a related point. Do not use your mobile phone in the toilet either! Barbara Pachter, author of “New Rules @ Work” says,

No one wants to be on the other end of a flushing toilet.

I doubt anyone has an interest in the fascinating sounds produced in water closets too.

Hot Fuzz – Hilariously Funny

After a long and tiring week, I was deciding what to do to amuse myself on this Sunday afternoon. I went to my usual local movie site, and found the movie “Hot Fuzz”. Then I remember seeing the preview a while back, and thought it was funny. So my plan for the afternoon was set.

Quick digression: fuzz informally means the police.

The movie is about this high flyer of a policeman, I’m sorry, police officer, Nicholas Angel, who was transferred to the quiet village of Sandford because he had a 400% arrest rate compared with his peers, and he’s embarrassing the entire department.

So there he was, itching to squash some crime, and he arrested some underage teenagers for drinking in a pub, the night before he was even officially to report for work. I can identify with him a little, when sometimes I feel my talents could be put to better use… oh well.

Amidst dealing with his recalcitrant colleagues, villagers with uncanny knowledge of goings-on and a partner who longs for big action, Angel manages to sit through a 3 hour long horribly blasphemous rendition of Romeo and Juliet, takes on the unexciting task of finding a swan, and taking care of his Japanese peace lily.

There are traffic accidents (I’m sorry, traffic collisions), flaming houses and exciting chases on foot. There’s arterial spray, decapitation and exploding bombs. If you can stand a little blood (CSI sort of conditioned me), and a little “colour” in the dialogue (officers dump change into a box whenever someone swears), and open-minded on your beliefs, then “by the power of Castle Grayskull”, you absolutely have to watch this movie.