Code Story

Thursday, September 22, 2005

AC-AXIS Rotate

In the 1980s when 3D graphics on personal computers was in its infancy, and when no PC graphics card had a usable resolution beyond 320x200, let alone 3D graphics capability. When a Play Station was something you find in kindergartens, and when the only good book that covered the subject of 3D was ”Interactive Computer Graphics” by Foley and Van Dam. We were busy innovating the latest and fastest 3D rendering engine primitives. I wrote Bresenham's line scan converters that averaged 1 and ½ machine code instructions per pixel, oh yes, and a triangle routine that would render 3D triangles at the fastest possible speed the computers of the day allowed. I used self-generating code. Look Up Tables for fast access, unrolled code to produce the most peculiar hand-crafted set of assembler instructions you've ever seen. We were creative with programming mathematical equations. I even knew what a Quaternion was, and how to interpolate Quaternions. The stuff we worked on then is embedded in the latest 3D hardware and software of today. We lived and breathed 3D graphics. We ruled!

Back then, I was invited for an interview by a games developer in the south of England. I had heard of this development team since they were one of the very few unfortunate developers who accepted writing 3D games and Flightsims for the British Archimedes computer made by Acorn, which I happened to have.

I was interviewed by the technical and research directors of the company. After passing the barrage of questions with flying colours, the research director started asking me about 3D rotations and compilers (I could not see the relationship between the two), which I could answer with ease. Bring it on...

Then half way through the interview, he looked at me with an evil-eye and asked: "How would you do AC AXIS ROTATE then?"...

Excuse me? A C? A C AXIS? ROTATE?!! WHAT? I went through every filed section in my memory for an “A” Matrix, “C” Matrix, “AC” Matrix multiplication? Alternating Current AXIS? Inverse XY = AC? What is he on about? Damn Foley and Van Dam for not mentioning this in their Computer Graphics book. They don't know everything, I knew it. I will never read their books again. Still, I had to find an answer to the question, I'll come back to Foley et al later. My brain told me to use the following string as an answer: "I'm sorry, I don't know!!!"

Soon the interview ended and I was on my way driving back home. The journey took just over an hour. I didn't enjoy the scenic route I took. AC AXIS ROTATE? What the? I know nothing!

A few weeks later I was offered a job by the company as the lead programmer for one of their new and exciting projects. A large-scale 3D space game for the PC . Which I accepted.

When I started my new position, I was going through existing code and got to the graphics engine section which was written by the same Mr research director.

Scrolling down the code, I could not believe my eyes. I found the following text with the familiar name: ac_axis_rotate...

I MEAN. NO WAY!!! ac_axis huh? You must be kidding me right? So, AC-AXIS ROTATE or shall I say ac_axis_rotate, is a name of a function the research director wrote? How the hell am I supposed to know that? I mean, how am I supposed to know what function names he had in his code? He might as well had asked me about the contents of his pockets. Was he having fun at my expense? I mentioned this to one of the programmers at the company and after laughing hysterically for what seemed like 10 minutes he said, "fun, I don't think so, I bet he meant it!"

Well I must respect that, from now on, I promise, I will be doing the same when I start interviewing people (the ones I don't like of course). Let me see: "How would you do adjustMACHNO?", "Do you know QMRvel?", "Can you normaliseMV huh? Can you punk? Well can ya?" I have a whole list of function names, and I don't mean the ones which I have published as open source. These are secret ones, no one will know them, in fact I haven't even written the code, I'll just invent the names. I must get someone else to suffer like I did. ac_axis_rotate? *%##(@!!*#@!%%!

ac_axis rotate turned out to be at the heart of the graphics engine code. Flight and space sims require free movement in 3D space. You need to be able to rotate about all three principal axes: X, Y and Z. Since computer games do not have to be accurate when representing rotations, programmers tended to use simple Euler angle additions to achieve 3D animation. This of course is incorrect, and problems start to occur in certain situations particularly when you are pitched right up near 90 degrees, you start rotating in the wrong direction. This is referred to as Gimbal Lock. The research director decided to incorrectly represent his rotations as an easy way out and try to fix the problem when it occurred by brute force, or more precisely, by his function ac_axis_rotate. If you played a Flightsim which used this code and you did a loop-the-loop, your aircraft wobbled strangely half way through. That wobble, ladies and gentlemen is ac_axis_rotate at work, trying desperately to fix the problem of Gimbal Lock and saving you from going in the wrong direction eventually heading straight to the ground. Had the rotations been represented by cumulative matrix or quaternion multiplications, it would have been a correct and wobble-free representation and you could do your loop-the-loop smoothly without the need for ac_axis_rotate altogether.

Gimbal Lock may be OK in computer games, but, if you watched Apollo 13, when things went wrong while the crew were in space, one of of the Shuttle crew shouted: "Don't get into Gimbal Lock!" - You mean NASA equipped their Shuttle with software that represented rotation in space using Euler angles? If I knew, I would have sent them a copy of ac_axis_rotate, it may cause the Shuttle to have weird wobbles but at least they won't be too scared getting into Gimbal Lock. Although the effect of ac_axis_rotate and real gravitational forces may be as fatal as crashing!

So for NASA's sake or in case you are interested (I would fully understand if you are not), here is the full listing of the ac_axis_rotate code. I am sure you might find a good use for it. I personally am planning on printing it on T-Shirts and giving them away free to people I know who are prone to Gimbal Locking. An apparent symptom after a heavy drinking session. I knew I would finally find a good use for this code.

Note: All questions relating to this function should be directed to the research director who wrote it. Don't expect a comprehensible answer and don't be surprised if you end up talking about compiler theory either!


void ac_axis_rotate(Svector *r, Svector *dr)
{
int rr, pr, yr;
int tanrx, srz, crz, crx;
int pitch;

srz = SIN(r->z);
crz = COS(r->z);
crx = COS(r->x);

pitch = ABS((short)r->x);

if (pitch <= DEG(88)) {
tanrx = TAN(r->x);
rr = dr->z +
(int)TRIG_SHIFT(MUL(
(int) TRIG_SHIFT(MUL(dr->x,tanrx)),srz)) -
(int)TRIG_SHIFT(MUL(
(int) TRIG_SHIFT(MUL(dr->y,tanrx)), crz));

pr = (int)TRIG_SHIFT((MUL(dr->x,crz) + MUL(dr->y,srz)));

if (crx != 0)
yr = MULDIV(dr->y,crz,crx) - MULDIV(dr->x,srz,crx);
else
yr = 0;
} else {
pr = (int)TRIG_SHIFT((MUL(dr->x,crz) + MUL(dr->y,srz)));
rr = dr->z;
yr = 0;
}

r->x = ADDANGLE(r->x,pr);
r->y = ADDANGLE(r->y,yr);
r->z = ADDANGLE(r->z,rr);
pitch = (short)r->x;

if (ABS(pitch) > DEG_90) {
if (pitch > 0)
r->x = DEG_90 - (pitch - DEG_90) - DEG_1;
else
r->x = -DEG_90 + (pitch + DEG_90) + DEG_1;
r->y = ADDANGLE(r->y, DEG_180);
r->z = ADDANGLE(r->z, DEG_180);
}
}

Creative Binary

No serious programmer does not know what the binary number system is, how to use it, count, add, subtract, XOR, OR, shift and AND in it. They can even do a lot more than that, human creativity is endless, unlike computers'.

For computers, binary operations are the lowest level the computer "understands". Computers are not clever at using binary. In fact, they are very dumb. If computers were designed to use the decimal system, I cannot imagine the heat that the Pentium Processor would generate. You could possibly use it instead of your central heating system.

The binary number system was chosen for computers precisely because of its simplicity, and to keep the Pentium fan small-ish. It's much easier to design circuits and represent digits electronically that have only two states or symbols: 0 or 1, true or false, on or off, ie binary.

When it comes to humans or programmers more specifically, the situation is somewhat different. A friend of mine used to insert binary notation in his normal everyday sentences: "I am active-low today", meaning: I am at binary 1 when I do not have a current through me!! Don't ask. Or, “I went to the cash machine and it returned FALSE” - i.e. it wouldn't give him money (and we all know why, don't we), or my favorite, is my mathematician programmer friend who used to advertise the fact that the pin codes for his credit cards are arranged as a "tree" in binary digits! Since pin codes normally comprise four decimal digits, then to make a tree in binary, I guess he would have written his pin code down something like this:


You might think that these don't look like trees, but you will have to be a machine code programmer to see it. Just like in the Matrix.

So, does this mean that real trees are pin codes for some global bank? I'll have to think about that!

Having been encouraged by the “usefulness” of binary in everyday life I decided to do the same. I started writing down my pin codes and passwords in binary safe in the knowledge that not everyone is a programmer and therefore, no one will be able to decipher my code. In fact, it would make my note book look cool and important, But wait, what if a pick-pocket pinched my wallet and he happened to be a top class 6502 machine-code programmer or even worse, 68000? This is worrying. I must do something about this, I can't just write my pin code down in "straight" binary! Maybe I can apply binary arithmetic and logical operations to it to make it more secure. I could XOR the bits or AND them with something. That's what I'll do, this way they'll never find out.

A year or so down the line I forgot my pin code for my cash card. No problemo, I knew I had it written down somewhere, in binary no less. I looked for my note book and sure enough I had the following entries:

1101 1010 0011 0111 1100
0001 1011 1100 1010 1111

Great, this is 13 10 3 7 12 1 11 12 10 15 !!!? This didn't look anything like any of my pin codes!! Wait, maybe I shifted the bits left by 1. What did I do with the carry bit? Where is the Status-Register when you need it? Maybe, I XORed all the bits with 11111111 then shifted them right (logical shifts of course, I hate arithmetic shifts). No? Did I ROR the bits into some other fictitious bits? I tried every operation I could think of but could not get my pin code back. I ran out of options. Well, I could write a program which would systematically go through all possible combinations, but I had a feeling that it would not work either and it would take ages to write the program. I needed my cash urgently. The only option left was to pick up the phone and call the bank: "I lost my pin code, could you please send me a new one?"

A few days later I received my new pin code. It was very reassuring to see that they had sent it in straight decimal without dividing it or multiplying it by some weird number.

That evening, I wrote one more thing in my note book next to my binary coded indecipherable pin code: “Don't use binary unless you are a dumb computer and however dumb computers are, they are damn right better at using binary than you. Stick to decimal”