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

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.

When you have to Paint

When you’re a lowly programmer, you just clock in, do whatever your superiors tell you to do, and you clock out. When you’re a corporate programmer, aaahhh, this is where the fun part comes. You get people saying to you, “Make it more user friendly” or “The login page doesn’t look nice enough. Fix it.” Then you think to yourself, “But I’m supposed to just write code!” Think again.

When I started doing graphics work because there’s no web designer nor graphics artist in my team, I fell back on the good old Windows Paint program. Yes, I can hear people laughing from as far away as the United States…

*pause*

Now that you’ve calmed down, you have to realise that I don’t have professional graphics software, so I make do with what I have. Which isn’t much. So I branched out. I found this wonderful free software that forms the integral part of my graphics work. It’s Paint.NET, and it’s packed with lots of stuff comparable to Photoshop. And together with Windows Paint, I have in possession the basis of my image processing skills.

And for those with Photoshop: more power to you.

It’s not about you. It’s about results.

Recently, something happened that shook my confidence a little. Before I get to that, let me say that I’m a fairly competent in web applications, in particular, .Net web applications. I have done image creation/processing, CSS validations, and making sure the web applications are as cross-browser as possible. I have made the user interface as simple and as easy to use as possible. I’ve read up tons of security measures and implemented many of them on the web server and in programming too. I follow any sensible coding guideline. Database tables are designed to be relevant and scalable for as long a time as possible. I’ve even released two public web sites, all single-handedly done by me.

Now, in between doing new projects, I also try to improve existing ones. So I have this pet project. Being that it’s a pet project, I let my creativity fly on the web application. I tried out my own 3d rendered graphics. I pushed my CSS skills in managing display. I even tested out what was to me very new, AJAX, to make the web application more lively, more “real-time”.

Then one fine day, it was decided that my pet project is actually going to make a difference in the team’s overall productivity. So it became a full-fledged project. Suddenly there was a deadline. Suddenly people are going to see it and use it. I mean like really see this project of mine. And then it happened. My deluge of “change this”, “that’s not right” and “I want it that way” came.

For the first few seconds, I was like outraged. I mean who are they to comment on my work? I was enraged. I was indignant. Then, I calmed down. Because I realise that it doesn’t matter what you think. Ultimately those people who said “do this and do that” are the ones who will use your application. Accept that.

It’s not personal. (Ok, sometimes it is…), so I want you to concentrate on the results. What is it that the users ultimately want? Your code can be the most elegant piece of creative work there is, but if it doesn’t do what the user want, it’s useless.

Focus on the user. And yes, sometimes, you have to let go of your code.

Master your programming language of choice

I have gone through many a program where I would stare at a section of code, trying to figure out what it’s doing. After a while, a light of understanding would flood my consciousness, and I would ask, “Why did someone write like this?”

The problem? The task at hand required a certain function, say formatting output (quite common) for displaying a string of a length of 4 characters from a number between -999 and 999, inclusive of the negative sign. I would then see code checking if the number was negative (to determine if a minus sign was required), string trimming and left/right alignment of the number and so on.

Why did anyone go through all this when there’s a perfectly functioning formatting ability within the standard library of the language? (I’m thinking C at the moment, but most other languages are still applicable) I came to one conclusion: the programmer didn’t know about it.

You can be a better programmer by simply knowing more about the language you’re using. You don’t have to remember every single function available. You just need to know where to look. Albert Einstein said something to the effect of “I don’t remember anything that’s written in a book.” There are online libraries of programming languages. Use them.

As a programmer, you are paid to think up solutions and implement them via code, not reinvent something that’s already done and then code the business logic. Your creative abilities are more important than your memorisation skills.

E equals M C squared

The famous equation of Albert Einstein has a simple elegance to it. I knew of it when I was young, but it didn’t mean anything to me. It probably warms the hearts of scholars of physics though.

The magic happens when I read about something that Robert Kiyosaki (author of “Rich Dad, Poor Dad”) said. In his book, he mentions that money is an idea. This prompted me to think of our earlier human ancestors, where barter trade was the norm. If you have herds of good cattle, you are considered rich. If your sheep produces fabulously soft wool, you are considered rich. In our modern times, if you have tons of those paper notes that your country’s mints are producing, you are considered rich.

What I realised is that, being rich has little to do with money itself. You are rich, because other people consider you to be rich. Having herds of cattle makes you rich because other people need the meat they can get from you. Since they don’t have it, they consider you to be richer than them. If you have a huge bank account, then other people consider you rich because they believe in the numbers they see and in the integrity of the bank.

Money is an idea.

Going back to the equation, I understand it as dividing our universe into two parts, energy and matter (or mass). If money is an idea, then it’s an energy form. And wealth is the material manifestation of this energy. If I want wealth, then I’ll have to materialise it from its energy form. Let’s look at the equation again:

Energy = Matter(mass) x Speed of light x Speed of light

The speed of light is 300000000 metres per second squared. That’s a 3 followed by 8 zeros. I realised that my energy level for wealth has to be extremely high in order to materialise anything.

This explains why many of the millionaires I’ve seen, heard and read about, are passionate, lively, animated and energetic. They create wealth from their ideas! To do this, they have to match their energy levels with that of wealth.

I now look at this equation under a different light.

The “2nd best” theory – Overbalancing

You might want to read part one and two first.

There is this almost obsessive need to “work on your weaknesses” pervading our lives. As a child, when I submit my report book to my dad, he would look it over, and point at some line on a page, and say something like, “How come you got a [insert low grade] for [insert some subject]?”.

After I graduated from university, I came to the “real” world. At my work reviews, my manager would go over my achievements, point at some line on his report, and say something like, “You are very good at [insert strong point], but I want you to improve on [insert weak point].”

Unless the weak point is critically hampering your progress, strengthening the weak point is a colossal waste of time!

Why is this so? Because you have little interest in it. If you had even a passing interest in it, it wouldn’t have been a weak point. You’d want to find out more more about it, even if it’s not one of your natural strengths. You have no feeling for it.

An example of a weak point worth correcting is the ability (or lack thereof) to communicate and work with fellow team members. You do want to work well with others right? Then you’d have an interest in making your relationship with them work.

This is where overbalancing comes in. In this context, it refers to improving every single skill you have, whether or not they create the most value for you. You might have heard of the 80/20 rule. 20% of your efforts produce 80% of your results. It’s hard enough finding out what your strengths are. Using the productive 20% effort on improving your weaknesses is commendable, but impractical.

Use a large part of the 80% effort on improving your complementary skills (to your strengths). The rest of the 80%? Go ahead with improving your weaknesses to do as little damage to your success as possible.