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);
}
}

3 Comments:

  • This is the funniest and most clever writing I've ever read about coding!

    Sam, you rule!

    By Anonymous Rita, at 7:02 PM  

  • I use it instead of classical Euler's transform:
    R[R[R[Ox,a]Oy,b]R[Ox,a]Oz,c].R[R[Ox,a]Oy,b].R[Ox,a]
    Do you think it can really solve gimble lock problem? I'm only a student in computer science. I'm programming my first 3D FPS, I have to finish it before the 16th of Juny. Best regards

    By Anonymous Julien GOUESSE (gouessej@yahoo.fr), at 7:45 AM  

  • Julien

    I am not sure I understand your notation.

    If you keep your rotations as Euler angles (I am assuming that a, b, c are) and you interpolate rotations in Euler space (ie linearly) using these angles and computing the rotation matrices for the X,Y, and Z axes, you will get into Gimble Lock at near 90 degrees when you are rotating all three axes together.

    You can fix your rotations to two axes only or maintain a rotation matrix, which represents all successive rotations for your objects. You update this matrix by multiplying it with pre-set rotation matrices in the axis you choose (X, Y or Z).

    Make sure that you use high precision values for your matrix, since after a while, numerical errors will be introduced quickly and the object will start to skew (look strange). There are ways to re-align the matrix (which you can do every so many frames) to avoid numerical discrepancies. You will be able to extract direction vectors from this matrix in order to interpolate the positions of your objects.

    If you give me more precise explanation (clearer notation) then I might be able to help more.

    Good luck

    Sam.

    By Anonymous Sam, at 9:21 AM  

Post a Comment

<< Home