PDA

View Full Version : Getting Normal vectors



SpaceCadet
04-14-2000, 04:00 PM
I'm designing a simulator that requires me to find the normal vector at any point in a large topographic map, i.e. 10,000,000 polygons. I thought about using some sort of tree structure to just store the data about each polygon, but memory is a serious issue. I was wondering if anyone knows any methods of getting the normal vector that is fast and memory efficent.

Humus
04-15-2000, 12:38 PM
Just use vector cross product:
if you have vertices p1 = (x1,y1,z1),p2 = (x2,y2,z2),p3 = (x3,y3,z3), form these vectors: v1 = p2 - p1, v2 = p3 - p1;
Then the normal is given by v1 x v2

lgrosshennig
04-17-2000, 12:20 PM
Hi there!

The fastest way to generate the inverse square root in native x86 is using a 1k floating point lookup table and some "bitstuffing".
You only have to set some addional bits and you got a 15 bit accurate inverse square root within 13-40 clockcycles (depending on a cache hit), compared to around 140 for the native x86 floating point stuff. You can calculate the inverse square root even faster with isse or 3dnow! (the later one ONLY if you don't switch between floating point / mmx & 3dnow frequently!).

I can post/mail you the c source if you want http://www.opengl.org/discussion_boards/ubb/smile.gif

Best regards,

LG http://www.opengl.org/discussion_boards/ubb/biggrin.gif

And may the vector be with you!

Gorg
04-17-2000, 01:51 PM
lgrosshennig, I d'like to see the code. Would you mind posting it on the forum?

lgrosshennig
04-18-2000, 01:26 PM
I guess, I already said that I don't mind giving the x86 float C source free, and here it is:

// code snipped starts here ******

#define IEEE_MANT_BITS 23
#define IEEE_EXP_BITS 8
#define IEEE_SIGN_BITS 1
#define IEEE_EXP_BIAS 127

#define INVSQRT_TABLE_SEED_MANT_BITS 9
#define INVSQRT_TABLE_SEED_EXP_BITS 1
#define INVSQRT_TABLE_LENGTH_BITS (INVSQRT_TABLE_SEED_MANT_BITS + INVSQRT_TABLE_SEED_EXP_BITS)
#define INVSQRT_TABLE_NUM_ENTRIES (1 << INVSQRT_TABLE_LENGTH_BITS)
#define INVSQRT_TABLE_ENTRY_BITS 10

#define EXP_OF(x) (*(unsigned long *)&(x) & 0x7f800000)

typedef struct _tab_in
{
unsigned int mpad: ((IEEE_MANT_BITS + 1) - INVSQRT_TABLE_LENGTH_BITS);
unsigned int lookup: INVSQRT_TABLE_LENGTH_BITS;
unsigned int epad: 7;
unsigned int spad: 1;
} tab_in;
typedef struct _tab_out
{
unsigned int mpad: (IEEE_MANT_BITS - INVSQRT_TABLE_ENTRY_BITS);
unsigned int lookup: INVSQRT_TABLE_ENTRY_BITS;
unsigned int epad: 8;
unsigned int spad: 1;
} tab_out;

union myfp
{
float fp;
// used to build the lookup table
tab_in tab_in_;
tab_out tab_out_;
};


unsigned int InvSqrtTab[INVSQRT_TABLE_NUM_ENTRIES];

void BuildInvSqrtTable()
{

static int done = 0;
int i;

if (done) return;
done = 1;

for (i = 0; i < INVSQRT_TABLE_NUM_ENTRIES; i++)

{
union myfp fin, fout;
fin.fp = 1.0F;
fin.tab_in_.lookup = i;

// calculate the real value
fout.fp = 1.0F / (float)sqrt((double)fin.fp);

// Add the value to the table. 1.0 is special.
if (fout.fp == 1.0F)
InvSqrtTab[i] = 0x3FF << (IEEE_MANT_BITS - INVSQRT_TABLE_ENTRY_BITS);
else
InvSqrtTab[i] = fout.tab_out_.lookup << (IEEE_MANT_BITS - INVSQRT_TABLE_ENTRY_BITS);
}
};

/////////////////////////////////////////////////////////////////////////////////////////
float InverseSquareRoot(float x)
{
unsigned int index;
float r;
unsigned long *dptr = (unsigned long *)&r;

*(unsigned long *)&r = ((((3 * IEEE_EXP_BIAS - 1) << IEEE_MANT_BITS) - EXP_OF(x)) >> 1) & 0x7f800000;

index = ((*(unsigned long *)&x) >> (IEEE_MANT_BITS - INVSQRT_TABLE_ENTRY_BITS + 1)) & (INVSQRT_TABLE_NUM_ENTRIES - 1);

*dptr |= InvSqrtTab[index];

return r;
};


/////////////////////////////////////////////
void SinCos(float rad, float *sincos)
{
__asm
{
mov eax, sincos

fld rad

fsincos

fstp DWORD PTR [EAX+4]
fstp DWORD PTR [EAX]
}
}

// code snipped stops here ****

Some comments to the source.

When you start your programm you should call up "BuildInvSqrtTable()" to build up the lookuptable. If you want an inverse square root of an given float, just call InverseSquareRoot(float x) to get it.
I addtionaly added the code to the sinus AND the cosinus of an given radian within 120 clockcycles (compared to the at least 240 clockcycles you normaly) have to spend).

If you want the isse or 3dnow! code, I need to know your REAL name, please Email me!

To be quiet honest, this code was inspired by the senior chief engienier of 3dlabs!

(please forgive my poor english)

Kind regards,

LG http://www.opengl.org/discussion_boards/ubb/biggrin.gif

And my the vector be with you!