Sign in to follow this  
Jiia

Caveman Normalization

Recommended Posts

Jiia    592
I'm sure I'm about to be heavily laughed at, but here goes anyways. I'm trying to understand why a square root is needed to normalize a vector. When I normalize using the square root of the sum of sqaures, I get values that are unequal to 1. They are close to 1, but always off a bit. Is a unit 3-dimensional vector's length not quite the sum of the absolute axes? In other words, is abs(x) + abs(y) + abs(z) the length? If not, what is happening with sqrt(x * x + y * y + z * z) that makes the length correct? I did a test with a brute force negative check:
FLOAT x=56.0f, y=40.0f, z=-20.0f;
UINT loops = 0x00FFFFFF;
while(loops--)
{
	res = 1.0f / ( ( (x < 0.0f) ? -x : x ) + ( (y < 0.0f) ? -y : y ) + ( (z < 0.0f) ? -z : z ) );
//	res = 1.0f / ( abs(x) + abs(y) + abs(z) );
//	res = 1.0f / sqrtf((x * x) + (y * y) + (z * z));

	x *= res;
	y *= res;
	z *= res;
}




The sqrtf method takes about 5 seconds to execute this, and the caveman (likely incorrect) method takes less than 1 second. Using the abs() functions instead of conditional checks takes around 13 seconds [lol]. The sum of absolute axes is always exactly 1.0 with the negative checks. The compiler may also be doing something that speeds up the negative checks. Hopefully not. Can anyone explain what is incredibly stupid about what I'm doing here? I'm sure there are several things [smile] Thanks! [Edited by - Jiia on October 16, 2004 10:40:11 PM]

Share this post


Link to post
Share on other sites
Kuladus    380
I'm sure you are after the Euclidean length, which is indeed

euc = sqrt(x*x+y*y+z*z);


"In other words, is abs(x) + abs(y) + abs(z) the length?"
Not the Euclidean length.

Note:

sqrt(x*x+y*y+z*z) does not equal abs(x)+abs(y)+abs(z)

"When I normalize using the square root of the sum of sqaures, I get values that are unequal to 1..."
When you find the length of the normalised vector it should be equal to one.

Not quite sure what your problem is...?

Share this post


Link to post
Share on other sites
Jiia    592
Quote:
Original post by Kuladus
Not quite sure what your problem is...?

You mean I'm an idiot / nutcase and there is little help for me? [lol]

I didn't really have a problem, other than being confused. The idea of a unit vector was throwing me off. I'm thinking unit = 1. But it's one distance point, not that the sum is equal to 1.

So the actual distance from vector(0,0,0) to vector(5,5,5) is not 15, it's around 8.5 or so, and my sum normalization version is way off. Actually, I must be having a really bad day to think this was right.

Thanks for trying to make sense of my half-unbaked idea [smile]

Share this post


Link to post
Share on other sites
Jiia    592
Quote:
Original post by Kuladus
Not completely half-baked :)

[lol] Perhaps a quarter-baked?

Quote:
What you were describing is the L1 vector norm (whereas the Euclidean distance is the L2 norm.)

Only by coincidence. I really had no idea what I was babbling about [smile] Are there actually uses for this L1 norm? Using this as a direction would push objects more slowly in diagonal directions, right?

Thanks again.

Share this post


Link to post
Share on other sites
Dmytry    1151
Why sqrt(x*x+y*y+z*z) is a length of vector in Euclidean space :
Read somewhere about Pythagorean theorem.(google.)

***********************************
abs(x) + abs(y) + abs(z)
is, IIRC, called Manhattan distance.
In 2D it's

0
*
**
*
*****X,Y

it's number of stars in such ascii path.(note that number of stars doesn't depend to path as long as you don't go back.)
It's not equal to sqrt(x*x+y*y+z*z)

And as about making it be unit-length. If you normalize using /(abs(x) + abs(y) + abs(z)) you make vector be placed on surface of "unit octohedron", surface where (abs(x) + abs(y) + abs(z))=1
Using max(abs(x) , abs(y) , abs(z)) you make it be placed on surface of unit cube, surface where max(abs(x) , abs(y) , abs(z))=1

Using sqrt(x*x+y*y+z*z) , on unit sphere, surface where sqrt(x*x+y*y+z*z)=1

(this =1 will only work for formules that works like normalization - if you normalize once, or normalize twice,result is the same)

**********

if in some space(euclidean or not) you have some norm of vector given by L(x,y,z) , and L(k*x,k*y,k*z)=k*L(x,y,z) , normalization
can be done by nvector=vector*(1/L(vector)) , so we have
L(nvector)=L(vector*(1/L(vector)))=L(vector)*(1/L(vector))=1

and if L(something)=1 , something is said to be unit-length... err, unit-norm, normalized.

Share this post


Link to post
Share on other sites
oliii    2196
Why is that a stupid question? It's just knowledge. You have it or you haven't, nothing wrong about that.

To put it simply, you know vector coordinates relates to an orthogonal frame (right angle), where one axis goes up, one goes right.

So, when you trace a segment from the origin to a point (x, y), you can see it forms a right angle triangle. Pythagoras' theorem states that the square length of the hypothenuse (the segment, or the side of the triangle opposite the right angle), is equal to the sum of the square lengths of the two other sides of the triangle.

C2 = A2 + B2

C is the length of the segment (which is the hypothenuse), and A and B are the coordinates of the vector along the axes of the frame.

in vector terms, L is the vector, (x, y) it's coordinates.

L2 = x2 + y2

so |L| = sqrt(x2 + y2)

Pythagorean Theorem

Share this post


Link to post
Share on other sites
shadow12345    100
Something else I'd like to point out, often times when you normalize a vector and then check its length, it often won't be exactly 1.0f units, rather often it will be 1.00002 with some extra bits on the mantissa.

Share this post


Link to post
Share on other sites
Dmytry    1151
Quote:
Original post by shadow12345
Something else I'd like to point out, often times when you normalize a vector and then check its length, it often won't be exactly 1.0f units, rather often it will be 1.00002 with some extra bits on the mantissa.

and sorry for offtopic, but BTW, it's one of the reasons why
angle_between_vectors=acos(DotProduct(a,b)/(Length(a)*Length(b)))
or
angle_between_vectors=acos(DotProduct(a,b))

is not a good thing for small angles. You can easily get something like acos(1.0000000382313) even if vectors is slightly inparallel. As result, bugs ,indefined results, or at best bad precision at small angles.
And why
angle_between_vectors=atan2(Length(CrossProduct(a,b)),DotProduct(a,b))
(it works for non-normalized as well as for normalized)
is alot better. Also it may even be faster because there's only one square root.

Share this post


Link to post
Share on other sites
johnb    351
Quote:
Original post by Dmytry
And why
angle_between_vectors=atan2(Length(CrossProduct(a,b)),DotProduct(a,b))
(it works for non-normalized as well as for normalized)
is alot better. Also it may even be faster because there's only one square root.


If performance matters so much that you're counting square roots you can eliminate them altogther, as if

tan t = |a ^ b] / (a . b)

then

tan2t = (|a ^ b| / (a . b))2
= |a ^ b|2 / (a . b)2

The numerator and denominator on the right hand side can be calculated without taking the square root, in particular as |a ^ b|2 is just |a ^ b| . |a ^ b|.

t can then be calculated using an inverse function to x2/y2= tan2t. This is not a library function but you can define it yourself and come up with something faster than the atan2 and sqrt it replaces.

Share this post


Link to post
Share on other sites
Charles B    863
Quote:
Original post by Jiia
...
The sqrtf method takes about 5 seconds to execute this, and the caveman (likely incorrect) method takes less than 1 second. Using the abs() functions instead of conditional checks takes around 13 seconds [lol].


Yes you lack of knowledge. None considered you are an idiot. Just a math illiterate ;)

Now that you probably know about L1(Manhattan) and L2(Pythagoras, Euclidian) norms. You should also be interested to know about the L0 norm : max(|x|, |y|, |z|).

Here is my touch of speedy math addict.

Your measurement is not significant for a pro game coder. You were possibly in debug mode (cf your remark about abs()) and surely not with the optimizations of the most recent compilers. Today 3DNow/SSE give you rsqrt for free. And even if conditional moves are also very fast, the standard normalization is faster than the caveman hack. So no deal, only cons, no pros. Caveman is deprecated, it was a useful trick ... ten years ago.

EDIT : just realized you were necessarilly in DEBUG mode. Else, with OPTIMIZATIONS ON all your tests would return 0 seconds. Because any compiler would detect redundant computations (constant inputs) and no outputs. The code would be totally culled, considered as dead code. Measuring/profiling code in DEBUG is quasi non sense (apart measuring number of calls).

Share this post


Link to post
Share on other sites
Quote:
Original post by Charles B

Now that you probably know about L1(Manhattan) and L2(Pythagoras, Euclidian) norms. You should also be interested to know about the L0 norm : max(|x|, |y|, |z|).



That's actually the L-infinity norm. I don't actually think there is an L0 norm, see definition of the vector norms on

Vector Norm

Share this post


Link to post
Share on other sites
Charles B    863
Right, memory failure here ;) There is a picture to remember it. See the unit 'circle' of the norm evolve from square to circle, to square again, turned of 45 degrees.

Learned all that 15 years ago.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this