 http://www.intel-assembler.it/  (c)2019 intel-assembler.it   info@intel-assembler.it Search :  Index  Intel Platform Article & Guides Download Software

23/01/2009 Featured Article: How to remove Buzus Virus (permalink)

 :::4133649:::  Web www.intel-assembler.it Download Tell a friend

How to use Fixed Point (16.16) Math Part 2

2° part about fast handling vectors and matrixes

(by night stalker)

Second part of Night Stalker's fast math handling. This chapter shows how to handle vectors and matrixes using fixed point math.

+----------------------[ 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
----------------------------------------------------------------------------

 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.

 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;     // 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]'.

 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)+FixedSquare(v));
}

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

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 th
e
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) + FixedSquare(v));
}

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

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 - v2) +
FixedSquare(v1 - v2));
}

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

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

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

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

 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;    // Matrix

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

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

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

Fixed32 identity_matrix =
{
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) +
FixedMul(m1[temp+1], m2) +
FixedMul(m1[temp+2], m2);

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

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

*dm++ = FixedMul(m1[temp  ], m2) +
FixedMul(m1[temp+1], m2) +
FixedMul(m1[temp+2], m2) + 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 += *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) + FixedMul(-trig_sin, m);
temp1 = FixedMul(trig_cos, m) + FixedMul(-trig_sin, m);
temp2 = FixedMul(trig_cos, m) + FixedMul(-trig_sin, m);

m  = FixedMul(trig_sin, m) + FixedMul(trig_cos, m);
m  = FixedMul(trig_sin, m) + FixedMul(trig_cos, m);
m = FixedMul(trig_sin, m) + FixedMul(trig_cos, m);

m  = temp0;
m  = temp1;
m  = 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) + FixedMul(trig_sin, m);
temp1 = FixedMul(trig_cos, m) + FixedMul(trig_sin, m);
temp2 = FixedMul(trig_cos, m) + FixedMul(trig_sin, m);

m  = FixedMul(-trig_sin, m) + FixedMul(trig_cos, m);
m  = FixedMul(-trig_sin, m) + FixedMul(trig_cos, m);
m = FixedMul(-trig_sin, m) + FixedMul(trig_cos, m);

m  = temp0;
m  = temp1;
m  = 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) + FixedMul(-trig_sin, m);
temp1 = FixedMul(trig_cos, m) + FixedMul(-trig_sin, m);
temp2 = FixedMul(trig_cos, m) + FixedMul(-trig_sin, m);

m = FixedMul(trig_sin, m) + FixedMul(trig_cos, m);
m = FixedMul(trig_sin, m) + FixedMul(trig_cos, m);
m = FixedMul(trig_sin, m) + FixedMul(trig_cos, m);

m = temp0;
m = temp1;
m = 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;
}

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

 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.

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

 TopDownload Tell a friend Similar Articles

How to use Fixed Point (16.16) Math Part 1
Want fast math? Use Fixed point math in asm and C
(by Night Stalker)

Tags: math

 webmaster jes writers rguru, tech-g, aiguru, drAxsite optimized for IE/Firefox/Chrome with 1024x768 resolution ALL TRADEMARKS ® ARE PROPERTY OF LEGITTIMATE OWNERS.© ALL RIGHTS RESERVED. hosting&web - www.accademia3.it find rguru on Code