Fast way of normalising vectors

[tryptamine]

Does anyone know of a faster way to normalise a (2D) vector other than this:

Code: Select all

length = sqrt(x*x + y*y);
x /= length;
y /= length;

Admittedly it doesn't seem to be taking up too much time (yet), but that square root for every surface normal I have is a bit scary... I could precalculate them (maybe), but where's the fun in that?

(I'm not using the C sqrt() function BTW, but somebody else's fast square root function, so it isn't quite as bad as it could be)

[_case]

what platform? ie. x86(MMX/SSE/SSE2) or something more exotic, say like MIPS ?

i take it your not just after another fast square root function/sqrt table etc. ? but rather someway of bypassing sqrt altogeather to get normalization of your vectors?

[Riff]

If you have a reciprocal square root function available, obtain the reciprocal square root and substitute multiplies for the divides. Multiplies are much faster that divides on x86 processors, and many systems have fast hardware multiply but no divide. The Nuon Aries processors are a good example. They can perform a hardware multiply-and-shift instruction in two cycles but must use table based division routines to perform divides, so divisions are 10x more expensive than multiplies, if not more.

You could also perform normalization in a vertex program in order to move the burden over to the video card, or you could use a cubemap to perform normalization.

In many cases, full blown normalization is not necessary and all you really need to do is multiply the transformed normal vector by a scale factor.

[tryptamine]

The target processor is a MIPS R3000 (Net Yaroze), so I only get hardware integer multiplication and division, as well as hardware matrix operations.

i take it your not just after another fast square root function/sqrt table etc. ? but rather someway of bypassing sqrt altogeather to get normalization of your vectors?

Exactly - as long as I keep the ratio between the X and Y components of my vector, is that usually enough?

In many cases, full blown normalization is not necessary and all you really need to do is multiply the transformed normal vector by a scale factor.

Ah - then is the sqrt() used mainly to prevent overflow during matrix operations? Thanks, i'll give that a shot - even if it turns out that I really do need a fully normalised vector, hopefully that will be enough for me to do a surface test and only sqrt() the normals I really need - i'm still learning, but things are beginning to click into place.

[pogo]

A few points:

There's no fast way to do this on the MIPS, but avoiding divides will speed it up. Try to find a reciprocal square root ("rsqrt"), use that instead of the square root and multiply instead of divide.

If your vectors are close to normal already you may be able to use a linear approximation. I did this on a similar platform a few years ago for quaternions, to deal with the output of Euler integration, where the resulting quaternions were only slightly non-normal. But you haven't described a situation where this would be appropriate.

In 2D you could use a lookup method similar to atan. First work out what half-quadrant your vector is in (between N & NW, between NW & E, etc.), and work out the ratio of the smallest to the largest, e.g. if |x| < |y| then calculate |x| / |y|. This is between 0 and 1. Use this to lookup in a table of e.g. 1024 vectors, then rotate the looked up vector into the correct half quadrant. This sounds like a lot of work but there's only one divide involved, apart from which it's all integer math which the MIPS does very quickly.