Jump to content
  • Advertisement
Sign in to follow this  
Numsgil

Some kind of fast unit vector normalization?

This topic is 4878 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I've been doing some research, and I've come across references to a fast vector normalization algorithm that uses Newton-Raphson approximations for the inverse square root. Unfortunately, I can't actually find the algorithm. Does anyone know it or another method for quickly finding the unit vector for a vector?

Share this post


Link to post
Share on other sites
Advertisement
you can also use the rsqrtss assembly instruction for processors that have SSE. It gives 12-bits of precision and runs with just 4 cycles of latency, so the slowest part of the normalization would be dotting the vector on itself.

Share this post


Link to post
Share on other sites
that InvSqrt is slower than 1.0/sqrt(x), atleast on my computer anyway =)

try this one:


float __declspec(naked) __fastcall isqrt ( float x )
{
__asm
{
mov eax, 0be6eb508h
mov dword ptr [esp-12], 03fc00000h
sub eax, dword ptr [esp+4]
sub dword ptr [esp+4], 800000h
shr eax, 1
mov dword ptr [esp-8], eax
fld dword ptr [esp-8]
fmul st, st
fld dword ptr [esp-8]
fxch st(1)
fmul dword ptr [esp+4]
fld dword ptr [esp-12]
fld st(0)
fsub st, st(2)
fld st(1)
fxch st(1)
fmul st(3), st
fmul st(3), st
fmulp st(4), st
fsub st, st(2)
fmul st(2), st
fmul st(3), st
fmulp st(2), st
fxch st(1)
fsubp st(1), st
fmulp st(1), st
ret 4
}
}


Share this post


Link to post
Share on other sites
In case vector is already very close to unit length, you can use that:
v=v*(1.5-0.5*(v.x*v.x+v.y*v.y+v.z*v.z))

clickster

Note: if vector is quite non-unit-length, this thing will "explode", in sense that it'll get further and further from 1 and will quickly leave the floating point range.
Other things that is _actually_ closely based on Newton's method (interactive demonstration how Newton's method works) usually does not "explode" so badly, but often are slower.

Share this post


Link to post
Share on other sites
Quote:
Original post by glSmurf
that InvSqrt is slower than 1.0/sqrt(x), atleast on my computer anyway =)

try this one:

*** Source Snippet Removed ***


Yes, on my computer too (athlon XP). InvSqrt gives less precision and is slower than the standard sqrt. Maybe it uses SSE when I compile something with full optimization. I don't know.

...and look out for all those invalid benchmarktests.

Share this post


Link to post
Share on other sites
v=v*(1.5-0.5*(v.x*v.x+v.y*v.y+v.z*v.z));

this is actually slower than my simple normalize function


inline void Vector::normalize()
{
double d = x * x + y * y + z * z;

if ( d == 1.0 || d == 0.0 ) return;

d = 1.0 / sqrt(d);

x *= d;
y *= d;
z *= d;
}




I use doubles for all sqrt/cos/sin and so on ...as for instance sqrt is alot faster than sqrtf.

and using my isqrt asm function then this is as fast as I could get it:


inline void Vector::normalize()
{
float d = x * x + y * y + z * z;

if ( d == 1.0f || d == 0.0f ) return;

d = isqrt(d);

x *= d;
y *= d;
z *= d;
}



Share this post


Link to post
Share on other sites
well maybe itss not he best benchmark test ever made but al functions geet tested under the same conditions:


int time = glutGet(GLUT_ELAPSED_TIME);

for (int j=0; j<10000000; ++j)
{
v.normalize();
//v = v*(1.5-0.5*(v.x*v.x+v.y*v.y+v.z*v.z));
}

time = glutGet(GLUT_ELAPSED_TIME) - time;

printf("time: %i\n", time);



dont know if my result are due to hardware or faulty benchmark tests.
As I said my simple normalize() was the fastest on my computer ..never said it was the best for YOU.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!