Results 1 to 5 of 5

Thread: Getting Normal vectors

  1. #1
    Junior Member Newbie
    Join Date
    Apr 2000
    Posts
    5

    Getting Normal vectors

    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.

  2. #2
    Senior Member OpenGL Guru Humus's Avatar
    Join Date
    Mar 2000
    Location
    Stockholm, Sweden
    Posts
    2,342

    Re: Getting Normal vectors

    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

  3. #3
    Senior Member Regular Contributor
    Join Date
    Mar 2000
    Location
    Germany
    Posts
    183

    Re: Getting Normal vectors

    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

    Best regards,

    LG

    And may the vector be with you!

  4. #4
    Senior Member Frequent Contributor
    Join Date
    Feb 2000
    Posts
    569

    Re: Getting Normal vectors

    lgrosshennig, I d'like to see the code. Would you mind posting it on the forum?

  5. #5
    Senior Member Regular Contributor
    Join Date
    Mar 2000
    Location
    Germany
    Posts
    183

    Re: Getting Normal vectors

    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

    And my the vector be with you!

Similar Threads

  1. normal vectors
    By kalkas in forum OpenGL: Basic Coding
    Replies: 3
    Last Post: 07-26-2011, 03:56 PM
  2. Specify Normal Vectors
    By L.BB in forum OpenGL: GLSL
    Replies: 7
    Last Post: 03-03-2006, 06:06 AM
  3. GL_SMOOTH_SHADING and normal vectors
    By BigRed in forum OpenGL: Advanced Coding
    Replies: 8
    Last Post: 08-05-2004, 03:05 AM
  4. Calculating Normal vectors
    By chuks in forum OpenGL: Basic Coding
    Replies: 3
    Last Post: 08-06-2003, 06:56 AM
  5. calculating normal vectors
    By chuks in forum OpenGL: Advanced Coding
    Replies: 4
    Last Post: 08-06-2003, 06:55 AM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  
Proudly hosted by Digital Ocean