This is available from trappen.vsl.ist.ucf.edu
Fixed point FAQ, 2/2
  旼컴컴컴컴컴컴컴컴컴컴[ Rage Technologies, Inc. ]컴컴컴컴컴컴컴컴컴컴컴컴커
                                                                            
                               - Members -                                  
                         ] Myth: Ideas / Coder [                            
                        ] Night Stalker: Coder [                            
                         ] SKoRPiON: Musician [                             
                                                                            
                            - Support Board -                               
            ] Shadow Lands: (407) 851-2313, run by Night Stalker [          
                                                                            
컴좔컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컨컴
      How to use Fixed Point (16.16) Math (Part 2 of 2) - by Night Stalker
컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴

[1] Introduction
컴컴컴컴컴컴컴컴

    Welcome to part 2 of the 'How to use Fixed Point Math' series.  We will be
delving into the world of verticies and matricies and other miscellaneous
functions that can be used to assist in 3D rendering.

    This code is straight C.  It capitalizes on part 1's code to be able to do
fixed point multiplication and other operations.  If you haven't read part 1,
you might want to look it over before you continue.


[2] Vectors
컴컴컴컴컴

    Alright, let's start off with vectors.  We need a good definition of a
vector, especially if we expect to do 3D math.  Since the only type that
seems to fit good with this restriction is your standard  vector,
I think the following definition would work fine:

袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴

typedef Fixed32 Vector[3];     // Vector

袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴

    Now, how would we access the specific  values inside this vector?
Easy.  You need to make 'macros' to access each value:

袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴

// Macros for Vector access
#define VECT_X      0
#define VECT_Y      1
#define VECT_Z      2

袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴

    So if you want the Y component of vector 'A', you would use 'A[VECT_Y]'.


[3] Basic vector math and stuff
컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴

    Ok, the vector access macros work great, but we need a faster way to 'make'
a vector.  Quite simply done, actually:

袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴

void make_vector(Vector v, Fixed32 x, Fixed32 y, Fixed32 z)
{
    *v++ = x;
    *v++ = y;
    *v   = z;
}

袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴

    See how easy that is?  :)  Just make a pointer to your vector, and
increment it along the way.

    Let's get into some basic math and other basic functions with vectors:

袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴

void VectCopy(Vector sv, Vector dv)
{
    memcpy(dv, sv, 12);
}

void VectAdd(Vector v1, Vector v2, Vector dv)
{
    *dv++ = v1[VECT_X] + v2[VECT_X];
    *dv++ = v1[VECT_Y] + v2[VECT_Y];
    *dv   = v1[VECT_Z] + v2[VECT_Z];
}

void VectSub(Vector v1, Vector v2, Vector dv)
{
    *dv++ = v1[VECT_X] - v2[VECT_X];
    *dv++ = v1[VECT_Y] - v2[VECT_Y];
    *dv   = v1[VECT_Z] - v2[VECT_Z];
}

Fixed32 VectLen(Vector v)
{
    // We use the High Precision Square Root here.
    return FixedSqrtHP(FixedSquare(*v) + FixedSquare(v[1]) + FixedSquare(v[2]));
}

袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴

    VectCopy() does just what it says.  It copies a vector to another one.
Could be useful, could be useless, but very easy to implement.

    VectAdd() and VectSub() also are pretty self-explanatory.

    But, what does VectLen() do?  It returns the length of a vector.  How do
you find the length of a standard  vector?  You don't actually find
the LENGTH of the vector, you find the distance between the vector and the
center of your world at <0, 0, 0>.  Now, if for some reason, you need the
length of the vector squared, you'll find this function is much faster than
VectLen():

袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴

Fixed32 VectLen_2(Vector v)
{
    return (FixedSquare(*v) + FixedSquare(v[1]) + FixedSquare(v[2]));
}

袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴

    As you can see, it doesn't use the square root.  So why square a square
root when you could just chop it off?

    If you're still confused about the length, think back to trigonometry
class in high school.  (Sorry if you're there now.. )  The Pythagorean
Equation was:

                                a = b + c

    But this is two dimensions, not three!  That's why our formula works:

                             a = x + y + z

    Knowing this, you should understand why this next function works:

袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴

Fixed32 VectDist(Vector v1, Vector v2)
{
    return FixedSqrtHP(FixedSquare((*v1) - (*v2)) +
                       FixedSquare(v1[1] - v2[1]) +
                       FixedSquare(v1[2] - v2[2]));
}

Fixed32 VectDist_2(Vector v1, Vector v2)
{
    return (FixedSquare((*v1) - (*v2)) + FixedSquare(v1[1] - v2[1]) +
            FixedSquare(v1[2] - v2[2]));
}

袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴

    Same set of rules, except instead of finding the length, you're finding
the distance between two vectors.  And again, if you need your distance value
squared, use VectDist_2().


[4] Even more vector math
컴컴컴컴컴컴컴컴컴컴컴컴

    Allright, let's get into some stuff you either learned in Calculus 3, or
are getting ready to.  (Myself being the latter of the two... )

袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴

void ScaleVect(Vector v, Fixed32 factor)
{
    *v++ = FixedMul(*v, factor);
    *v++ = FixedMul(*v, factor);
    *v   = FixedMul(*v, factor);
}

void NormalizeVect(Vector v)
{
    Fixed32 factor;

    factor = OneOver(VectLen(v));

    *v++ = FixedMul(*v, factor);
    *v++ = FixedMul(*v, factor);
    *v   = FixedMul(*v, factor);
}

Fixed32 DotProduct(Vector v1, Vector v2)
{
    return (FixedMul(v1[VECT_X], v2[VECT_X]) +
            FixedMul(v1[VECT_Y], v2[VECT_Y]) +
            FixedMul(v1[VECT_Z], v2[VECT_Z]));
}

void CrossProduct(Vector v1, Vector v2, Vector dv)
{
    *dv++ = FixedMul(v1[VECT_Y], v2[VECT_Z]) - FixedMul(v1[VECT_Z], v2[VECT_Y]);
    *dv++ = FixedMul(v1[VECT_Z], v2[VECT_X]) - FixedMul(v1[VECT_X], v2[VECT_Z]);
    *dv   = FixedMul(v1[VECT_X], v2[VECT_Y]) - FixedMul(v1[VECT_Y], v2[VECT_X]);
}

Fixed32 CrossZProduct(Vector v1, Vector v2)
{
    return FixedMul(*v1, v2[VECT_Y]) - FixedMul(v1[VECT_Y], *v2);
}

袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴

    ScaleVect() is pretty self-explanatory.  You pass in a factor, and it
multiplies the entire vector by that factor.

    NormalizeVect() normalizes a vector (hence it's name).  If you don't really
understand what it does, picture this:  You have a polygon (make it 3 sided,
for ease) floating in space.  If you take a normal to this polygon, you will
have a vector standing straight out (perpendicular) in the middle of the
polygon.  Just picture the same thing happening for a vector.

    DotProduct() and CrossProduct() do just what they say.  They take the dot
product and the cross product of two vectors, respectively.  These are quite
useful in calculating light sources.

    CrossZProduct() simply returns the Z component of the cross product, just
in case you might need it for something.  :)


[5] Matricies
컴컴컴컴컴컴

    Okay, you know everything about vectors now.  Let's hit matricies.  Again,
we need a good definition.  Well, since most 3D operations can be done with a
3-by-4 matrix (allowing transformational, rotational, and scalar matrix
multiplication), the following definition suits our needs perfectly:

袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴

typedef Fixed32 Matrix[12];    // Matrix[3][4]

袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴

    And we might as well define an identity matrix so we can create one
easily:

袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴

Fixed32 identity_matrix[12] =
{
    ONE,     0,     0,   0,
      0,   ONE,     0,   0,
      0,     0,   ONE,   0,
};

void make_identity_matrix(Matrix m)
{
    memcpy(m, identity_matrix, 48);
}

袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴

    What about scaling matricies and rotational matricies, you ask?  Allright,
here they are:

袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴

void make_scale_matrix(Matrix m, Vector sv)
{
    *m++ = *sv++;  *m++ =     0;  *m++ =  0;   *m++ =  0;
    *m++ =     0;  *m++ = *sv++;  *m++ =  0;   *m++ =  0;
    *m++ =     0;  *m++ =     0;  *m++ = *sv;  *m   =  0;
}

void make_trans_matrix(Matrix m, Vector tv)
{
    *m++ = ONE;  *m++ =   0;  *m++ =   0;  *m++ = *tv++;
    *m++ =   0;  *m++ = ONE;  *m++ =   0;  *m++ = *tv++;
    *m++ =   0;  *m++ =   0;  *m++ = ONE;  *m   = *tv;
}

void make_xrot_matrix(Matrix m, Iangle theta)
{
    Fixed32 trig_sin, trig_cos;

    CosSin(theta, &trig_cos, &trig_sin);

    *m++ = ONE;  *m++ =         0;  *m++ =         0;  *m++ = 0;
    *m++ =   0;  *m++ =  trig_cos;  *m++ =  trig_sin;  *m++ = 0;
    *m++ =   0;  *m++ = -trig_sin;  *m++ = -trig_cos;  *m   = 0;
}

void make_yrot_matrix(Matrix m, Iangle theta)
{
    Fixed32 trig_sin, trig_cos;

    CosSin(theta, &trig_cos, &trig_sin);

    *m++ =  trig_cos;  *m++ =   0;  *m++ = -trig_sin;  *m++ = 0;
    *m++ =         0;  *m++ = ONE;  *m++ =         0;  *m++ = 0;
    *m++ = -trig_sin;  *m++ =   0;  *m++ =  trig_cos;  *m   = 0;
}

void make_zrot_matrix(Matrix m, Iangle theta)
{
    Fixed32 trig_sin, trig_cos;

    CosSin(theta, &trig_cos, &trig_sin);

    *m++ =  trig_cos;  *m++ =  trig_sin;  *m++ =   0;  *m++ = 0;
    *m++ = -trig_sin;  *m++ =  trig_cos;  *m++ =   0;  *m++ = 0;
    *m++ =         0;  *m++ =         0;  *m++ = ONE;  *m   = 0;
}

袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴

    And a simple copy function to copy one matrix to another:

袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴

void MatrixCopy(Matrix sm, Matrix dm)
{
    memcpy(dm, sm, 48);
}

袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴

    Allright, which ones of you are totally lost about this matrix ordeal and
who isn't?  Those of you that understand, you can skip the next paragraph...

    Having matricies is an ideal way to transform verticies.  The basic idea
is to create a matrix and multiply it by a vector.  So if you had an identity
matrix and multiplied it by all the vectors in your object, nothing would
happen.  However, if you started with an x-rotational matrix of 20 Iangles,
and multiplied each vector by this matrix, your object would rotate on the
X axis by 20 Iangles.  You can also concatenate matricies together to say,
rotate and scale at the same time with just a single matrix!  Hopefully you
understand now.  :)

    Allright, now you need to concatenate two matricies together.  Here's how
you do it:

袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴

void ConcatMatrices(Matrix m1, Matrix m2, Matrix dm)
{
    int i, temp;

    temp = 0;
    i = 3;
    while (i--)
    {
        *dm++ = FixedMul(m1[temp  ], m2[0]) +
                FixedMul(m1[temp+1], m2[4]) +
                FixedMul(m1[temp+2], m2[8]);

        *dm++ = FixedMul(m1[temp  ], m2[1]) +
                FixedMul(m1[temp+1], m2[5]) +
                FixedMul(m1[temp+2], m2[9]);

        *dm++ = FixedMul(m1[temp  ], m2[2]) +
                FixedMul(m1[temp+1], m2[6]) +
                FixedMul(m1[temp+2], m2[10]);

        *dm++ = FixedMul(m1[temp  ], m2[3]) +
                FixedMul(m1[temp+1], m2[7]) +
                FixedMul(m1[temp+2], m2[11]) + m1[temp+3];

        temp += 4;
    }
}

袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴

    Yep, that's it.  If you forgot matrix multiplication, go open your Algebra
book and look it up.  :)

    There's also a couple of other "quicker" methods of adding translation and
rotational matricies together instead of concatenating them together.  You
might find these functions a bit useful to pull out that little bit of extra
performance:

袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴

void trans_matrix(Matrix m, Vector dv)
{
    m[ 3] += *dv++;
    m[ 7] += *dv++;
    m[11] += *dv;
}

void append_xrot_matrix(Matrix m, Iangle theta)
{
    Fixed32 trig_sin, trig_cos;
    Fixed32 temp0, temp1, temp2;

    CosSin(theta, &trig_cos, &trig_sin);

    temp0 = FixedMul(trig_cos, m[4]) + FixedMul(-trig_sin, m[8]);
    temp1 = FixedMul(trig_cos, m[5]) + FixedMul(-trig_sin, m[9]);
    temp2 = FixedMul(trig_cos, m[6]) + FixedMul(-trig_sin, m[10]);

    m[8]  = FixedMul(trig_sin, m[4]) + FixedMul(trig_cos, m[8]);
    m[9]  = FixedMul(trig_sin, m[5]) + FixedMul(trig_cos, m[9]);
    m[10] = FixedMul(trig_sin, m[6]) + FixedMul(trig_cos, m[10]);

    m[4]  = temp0;
    m[5]  = temp1;
    m[6]  = temp2;
}

void append_yrot_matrix(Matrix m, Iangle theta)
{
    Fixed32 trig_cos, trig_sin;
    Fixed32 temp0, temp1, temp2;

    CosSin(theta, &trig_cos, &trig_sin);

    temp0 = FixedMul(trig_cos, m[0]) + FixedMul(trig_sin, m[8]);
    temp1 = FixedMul(trig_cos, m[1]) + FixedMul(trig_sin, m[9]);
    temp2 = FixedMul(trig_cos, m[2]) + FixedMul(trig_sin, m[10]);

    m[8]  = FixedMul(-trig_sin, m[0]) + FixedMul(trig_cos, m[8]);
    m[9]  = FixedMul(-trig_sin, m[1]) + FixedMul(trig_cos, m[9]);
    m[10] = FixedMul(-trig_sin, m[2]) + FixedMul(trig_cos, m[10]);

    m[0]  = temp0;
    m[1]  = temp1;
    m[2]  = temp2;
}

void append_zrot_matrix(Matrix m, Iangle theta)
{
    Fixed32 trig_cos, trig_sin;
    Fixed32 temp0, temp1, temp2;

    CosSin(theta, &trig_cos, &trig_sin);

    temp0 = FixedMul(trig_cos, m[0]) + FixedMul(-trig_sin, m[4]);
    temp1 = FixedMul(trig_cos, m[1]) + FixedMul(-trig_sin, m[5]);
    temp2 = FixedMul(trig_cos, m[2]) + FixedMul(-trig_sin, m[6]);

    m[4] = FixedMul(trig_sin, m[0]) + FixedMul(trig_cos, m[4]);
    m[5] = FixedMul(trig_sin, m[1]) + FixedMul(trig_cos, m[5]);
    m[6] = FixedMul(trig_sin, m[2]) + FixedMul(trig_cos, m[6]);

    m[0] = temp0;
    m[1] = temp1;
    m[2] = temp2;
}

袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴

    There's one important function I haven't given to you yet, and it's VITAL
to being able to do these transformations in the first place.  The following
function will take a vector and a matrix and multiply them together to give
you your new vector:

袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴

void XformVector(Matrix m, Vector sv, Vector dv)
{
    Fixed32 sv0, sv1, sv2;

    sv0 = *sv++;
    sv1 = *sv++;
    sv2 = *sv;

    *dv++ = FixedMul(*m++, sv0) + FixedMul(*m++, sv1) +
            FixedMul(*m++, sv2) + *m++;

    *dv++ = FixedMul(*m++, sv0) + FixedMul(*m++, sv1) +
            FixedMul(*m++, sv2) + *m++;

    *dv   = FixedMul(*m++, sv0) + FixedMul(*m++, sv1) +
            FixedMul(*m++, sv2) + *m;
}

袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴袴

[6] Conclusion
컴컴컴컴컴컴컴

    Well, congradulations!  If you made it this far, then you understand just
about everything there is to know about fixed point math, vector and matrix
multiplication.

    Again, and as always, if you run into any problems, we'll be happy to help
you out.

                                                - Night Stalker

-------------------------------------------------------------------------------

Look for other Rage Technologies, Inc. stuff coming soon:

        - Our first major demo, "Transvectoring".  The theme is to
          show off our new 3-D engine with lightsourcing and texture
          mapping... REALLY fast.  Also to show what objects beyond
          3D really look like.  For example, a 4D or a 5D cube.  Maybe
          more.  Expected release date:  Mid '95 (?)

        - Night Hawk 0.2 BBS.  The first BBS software to show that
          ANSI is dead, and RIP is a thing of the past.  Features
          include: True multitasking, full video and audio routines,
          and more.  Expected release date:  Early/Mid '96.

-------------------------------------------------------------------------------

Other news:

        - Shadow Lands is still not up.  Blame Night Stalker.  He's too
          lazy to sell his old 486/33 to run the board on a DX4-100.
          We'll let you know when he gets off his duff and has Shadow
          Lands online.

        - Rage Technologies, Inc. has a mailing list.  If you'd like to
          get ahold of any one of us, send E-mail to:

                                      ragetech@trappen.vsl.ist.ucf.edu

        - Rage Technologies, Inc. also has an experimental FTP server
          running.  If you would like to get any Rage products, simply
          anonymous FTP to:  trappen.vsl.ist.ucf.edu.  All Rage files
          are located in /pub/ragetech.


Back to the3D Game Programming Resource page.