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

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.

Let your phone ring at least twice

There was this time when I had to clarify something with someone, and I decided to call her (instead of emailing her). So I dialled her number, and she picked up the phone almost immediately. I mean, I was still pulling reference material together, and I was actually counting on the phone ringing a couple of times to give me time. I was pushed off balance by the suddenness of her voice.

So I developed this habit of waiting for the phone to ring twice. Because when the first ring occurs, I have to mentally shift from my programming to being able to take calls. By the time I’m prepared to take the call, the second ring occurs. I then take the time to clear my throat (the last thing people want is to be greeted by a hoarse voice). And when the second ring finishes, I pick it up, grabbing a notepad and pen in the process to take down notes if required.

People expect the phone to ring.

Letting the phone ring a couple of times also gives you time to prepare yourself. It could be an important person on the line, and you are wasting the opportunity if you sound weak, hoarse and unprepared.

Why would you sound hoarse? From personal experience, because my job is mainly programming, I seldom need to converse. My throat starts to, uh, “coagulate”. After 3 to 4 hours of non-talking, I’m going to need to clear my throat.

Or if you happen to be eating something (a piece of chocolate, a biscuit/cookie or sweets), you are going to sound like someone talking with their mouth full. Which you are! The two phone rings are going to give you time to swallow that chocolate or push that sweet to your cheek so you can speak properly.

Add to the fact that you greet the other person on the line (you do greet with a “Good morning” or “Good afternoon” right?), the phone conversation will go a lot smoother.

Master your development tool of choice

Following the spirit of “Master your programming language of choice“, is the skillful use of your favourite development environment or IDE (integrated development environment), such as Microsoft Visual Studio or Dev-C++. You need to know the shortcuts, keyword highlighting and anything else that will make your programming job easier.

For example, if you deal with strings a lot (say SQL statements), it will help if your IDE makes it easier to find on the screen. The standard seems to be red colour for strings. The default colour highlighting for Visual Studio 2003 is black. How can you find any string literal in your code quickly if the string literal is the same colour as your code?

With all the advancements in development tools (such as Intellisense), you should be focusing on the one thing that computers cannot do for you: thinking. Thinking of the algorithm that will implement your business logic. Thinking of the different possibilities that your logic can succeed or fail, and handle them. There are lots of code generation tools out there to make your life easier. That said, there will be instances where you have to do the actual coding yourself.

Your greatest asset is your ability to think.