Archived

This topic is now archived and is closed to further replies.

Custom Normalizing function not correct

This topic is 4981 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 may not be a math genius, but shouldn''t this work?
	void _NormalizeTileVert(D3DXVECTOR3 & n, float tX, float SqrtY, float tZ)
	{
		float mag = float( sqrt( (tX*tX) + SqrtY + (tZ*tZ) ) );
		if (mag != 0.0f)
		{
			mag = 1.0f / mag;
			n.x *= mag;
			n.y *= mag;
			n.z *= mag;
		}
	}
The SqrtY parameter is the already-squared Y value of the input Vector. Previously I was using D3DXVec3Normalize with the exact same input, and things were just dandy. But since I thought this would be faster, I tested it out. I get a flat-lit terrain, much as if I had calculated all normals pointing directly up. Where am I stupid?

Share this post


Link to post
Share on other sites
[edit: Warning! Read with care! May contain crap ]

This will work only if you call it like this

D3DXVECTOR3 vec;
_NormalizeTileVert (vec, vec.x, vec.y*vec.y, vec.z);

[edit: so what...?]
You said you thought it would be faster... Are you sure optimizing this would increase performance? It's just that premature optimization is evil and especially when it produces incorrect results!

And what I think is that this won't optimize anything. You could do two things:
1. Pre-calculate y2. But if you can do that, you can also pre-normalize the vector [edit: ok, maybe not]
2. Forgot... it's too late (2.15 am)

If you really want to keep it this way, at least change SqrtY to SqrY or you will soon be feeding the function with sqrt(y)...

[edit: How are you calling the function?]


[edited by - nonpop on April 22, 2004 7:23:44 PM]

Share this post


Link to post
Share on other sites
Your code is a bit messy. First of all, the chances of a floating point value precisely equalling zero are roughly negative, so remove that slow, hideous if() statement. Second, use sqrtf() instead of making a double to float cast. Third... why are you calling the function with 4 parameters? You can accept a D3DXVECTOR3 and return a D3DXVECTOR3, or work with a reference to a D3DXVECTOR3, or pointers, or whatever you want. Passing separated coordinates is poor design.

Fifth, if you are that worried about performance, declare the function as inline. Six, your naming conventions need to be revised, because you will get confused by them later; as nonpop suggested, use SqrY or YSqred or something instead of SqrtY. Also, you are not normalizing a vertex, so your function''s name should be NormalizeTileVertexNormal or NormalizeVector or something like that. Clarity goes a long way towards making your code easy to work with, improve, and debug.

Unless you are normalizing trillions of vectors per frame, precomputing y^2 is probably a waste of time. In the majority of cases a precalculation that removes one multiplication is a waste; storing the value of y^2 can lead to cache thrashing and other lovely performance issues.

I would strongly recommend you profile your code if you have not already done so, and look very carefully at what is taking up your CPU clocks. If you are spending so much time normalizing vectors, you probably need to reconsider how your engine is designed. You''ll probably find that, performance-wise, you won''t be able to outdo the efficiency of D3DXVec3Normalize unless you are extremely handy with assembler and hand-tuned code optimization.

All that said, here''s a suggestion for how to revise your function; again let me recommend that you profile your code and make sure that using your own normalization function is really going to earn you something worthwhile:


inline void _NormalizeVector(D3DXVECTOR3 & vector)
{
float mag = 1.0f / sqrtf( vector.x*vector.x + vector.y*vector.y + vector.z*vector.z );
vector.x *= mag;
vector.y *= mag;
vector.z *= mag;
}



Of course if you need to preserve the original value of the vector (for some strange reason) then it is easy enough to tweak this to return a distinct variable instead of modifying the original.

The only problem I can see in your code (other than potentially poor programming practices) is that n.x may not be equal to tX, n.y*n.y not equal to SqrtY, and so on.



PiQ Software - Tiny KeyCounter - Freon 2/7 Raytracing Accelerator

Share this post


Link to post
Share on other sites
Apologies for the stupidity of the question. I dont know what I was thinking with that code. The answer was not the math, it was me not paying attention to my operators somehow. Sorry again for wasting your time. The more I look at that the more I wonder what I thought I was doing. Please just forget you ever read this.

The solution was simple. Apparently your reply jump started my brain:

__forceinline void _NormalizeTileVert(D3DXVECTOR3 & n, const float tX, const float tY, const float tZ)
{
float mag = 1.0f / sqrtf( (tX*tX) + (tY*tY) + (tZ*tZ) );
n.x = tX * mag;
n.y = tY * mag;
n.z = tZ * mag;
}


Just fyi, it was called like this:


_NormalizeTileVert( pVertex[VBIndex].vecNorm,
HeightMap[z-1][x-1] + HeightMap[z][x-1] + HeightMap[z][x-1] + HeightMap[z+1][x-1]
- HeightMap[z-1][x+1] - HeightMap[z][x+1] - HeightMap[z][x+1] - HeightMap[z+1][x+1],
64.0f,
HeightMap[z-1][x-1] + HeightMap[z-1][x] + HeightMap[z-1][x] + HeightMap[z-1][x+1]
- HeightMap[z+1][x-1] - HeightMap[z+1][x] - HeightMap[z+1][x] - HeightMap[z+1][x+1] );


The previous method was the same except using D3DXVec3Normalize(). As you can see, the reason that the parameters are not passed into the function as a Vector, is that they are not in vector form to begin with. My actual function was inlined, and was passed const values. I didnt use sqrtf because I didnt find it in my documentation (MSVC++ 6.0). It does however compile, so I'm using it now.

>>the chances of a floating point value precisely equalling zero are roughly negative

But its still possible. I suppose I could add some incredibly small fraction to the sqrtf result to ensure nothing horrible ever happens.

Thanks again and apologies all round.

[edited by - Corroded on April 22, 2004 8:55:27 PM]

Share this post


Link to post
Share on other sites
No apologies necessary; we all have to learn this stuff somehow. I daresay I''ve made a lot more (and worse) mistakes than that. The important thing is that you are willing to learn from it and move on I don''t consider my time wasted at all. If it were a waste of time I would have simply gone and done something else instead; as far as I''m concerned the more programmers the world has the happier we will all be.

I see now why you aren''t passing a vector into the function; in that case the way you have it set up is fine. However, I would recommend you tread carefully around __forceinline. In general the compiler knows a lot more than you do about how the assembly code is laid out, so it can make better decisions about when to do inlining. Before you make the jump to __forceinline, be sure you very carefully and thoroughly profile your code, and set up a comprehensive test case to make sure the effects of __forceinline are beneficial. There''s nothing wrong with using it - just be sure you are using it for a good reason. If a less dangerous tool will do the job, use it instead. After all, very few people would consider it wise to use a shotgun to open their front door when a key does the job much more elegantly

One final comment on the if() statement: a conditional inside a piece of code that is called a lot will hurt performance. You may run into cache mispredictions or other nasty things that end up chewing away a lot of CPU time. It is unlikely that you will get cache mispredictions in a test that simple, but the principle holds: don''t use conditionals more than you absolutely have to. First of all, mag will never be zero, because the y coordinate is 64. If you use the normalization code in other places, you cannot assume this; but in the context of the code you listed above, you know for a fact that mag will never be 0. Secondly, even if it is 0, the effects will be minimal. You may get incorrect lighting or a very minor performance drop, but it will happen only in incredibly rare situations. Weigh the costs and benefits: you will lose performance with the conditional, period. At the very least it is an extra instruction which can contribute to cache problems. At the worst you will cause cache misses which are very, very harmful for your speed. On the other hand, removing the conditional will give you temporary and virtually unnoticable problems in extremely rare situations. This kind of cost/benefit analysis is crucial to doing good code optimization, so start early

Share this post


Link to post
Share on other sites
Thanks for your time and the tips. I''ll take this into consideration.

I use __forceinline at the moment as I dont have an optimizing compiler (academic version) and it does a crappy job at figuring out what to do. I suppose its a bad habit to get into though as I wont be using this compiler forever. I am careful not to force inline anything over a few lines or which is called in many places.

I''ve only recently discovered the very real danger of cache misses, branch misprediction, etc involved in conditional statements and many other innocuous "appearing" code. I''ve been trying to redo my support code but its been a deep wade.

Any and all code improvement tips are always welcome. I do this kind of thing to learn so all criticism is of the constructive kind IMO

Good day!

Share this post


Link to post
Share on other sites
quote:
Original post by ApochPiQ
Your code is a bit messy. First of all, the chances of a floating point value precisely equalling zero are roughly negative, so remove that slow, hideous if() statement.


Hideous and slow? More like very appropriate and having no discernible effect on speed. Removing it is just asking for a divide by zero and some screwy bugs that are hard to track down.

Share this post


Link to post
Share on other sites
A few points:

1.) Don''t use an underscore at the beginning of your function names - the C++ standard says:
quote:

17.4.3.1.2 Global names

1 Certain sets of names and function signatures are always reserved to the implementation:

— Each name that contains a double underscore (__) or begins with an underscore followed by an uppercase letter (2.11) is reserved to the implementation for any use.

— Each name that begins with an underscore is reserved to the implementation for use as a name in the global namespace.



2.) If you have the academic version of Visual Studio you can get the optimizing compiler for free - MS just released it recently. There''s been quite a bit of discussion about it on these forums and if you look around you should be able to find instructions on installing it to replace your current compiler.

3.) A low level math function like normalize is not the place for error checking. Callers of normalize should take responsibility for passing in valid data (i.e. no vectors with a magnitude of 0) - that way you don''t impose a performance penalty on code that doesn''t need the check. If you want to avoid the hard to track down bugs Dobbs warns about then put in an assert - that way you''ll get notified in debug builds of a bug in the calling code but won''t suffer a performance penalty in release builds. The important point is that passing a vector with 0 magnitude to a normalize function is a bug in the calling code (since there is no defined answer), not something that the normalize function itself should check for. There is no way for the normalize function to know what is an appropriate way to handle such invalid input.

Share this post


Link to post
Share on other sites
quote:
Original post by Dobbs
Hideous and slow? More like very appropriate and having no discernible effect on speed. Removing it is just asking for a divide by zero and some screwy bugs that are hard to track down.



quote:
Original post by ApochPiQ
One final comment on the if() statement: a conditional inside a piece of code that is called a lot will hurt performance. You may run into cache mispredictions or other nasty things that end up chewing away a lot of CPU time. It is unlikely that you will get cache mispredictions in a test that simple, but the principle holds: don''t use conditionals more than you absolutely have to. First of all, mag will never be zero, because the y coordinate is 64. If you use the normalization code in other places, you cannot assume this; but in the context of the code you listed above, you know for a fact that mag will never be 0. Secondly, even if it is 0, the effects will be minimal. You may get incorrect lighting or a very minor performance drop, but it will happen only in incredibly rare situations. Weigh the costs and benefits: you will lose performance with the conditional, period. At the very least it is an extra instruction which can contribute to cache problems. At the worst you will cause cache misses which are very, very harmful for your speed. On the other hand, removing the conditional will give you temporary and virtually unnoticable problems in extremely rare situations. This kind of cost/benefit analysis is crucial to doing good code optimization, so start early



I think that should be fairly self-explanatory.




PiQ Software - Tiny KeyCounter - Freon 2/7 Raytracing Accelerator

Share this post


Link to post
Share on other sites
>>1.) Don't use an underscore at the beginning of your function names - the C++ standard says:

Yes. Its a possibly bad habit I've formed from I-dont-know-where. I use the underscore to indicate a private function of a class. In this way it will never coincide with anything in the global namespace, and it sorts all my private data in the VC intellisense class-completion box so I dont have to actually think.

>>2.) If you have the academic version of Visual Studio you can get the optimizing compiler for free - MS just released it recently. There's been quite a bit of discussion about it on these forums and if you look around you should be able to find instructions on installing it to replace your current compiler.

I went and downloaded that. I did a search and did indeed find many discussions on optimizing compilers, but very little on the this being recently released and how to integrate it. I'm almost 100% sure I can integrate it into the VC IDE and use it as my default compiler. I was unable to find information on how to do this, and after poking around with the VC options I'm still just as clueless. Do you happen to have a link to a thread/page that might give me a place to start?

>>I think that should be fairly self-explanatory.

It most certainly was; to me anyhow.

You gentlemen have been most helpful.

[edited by - Corroded on April 22, 2004 12:31:26 AM]

Share this post


Link to post
Share on other sites
quote:
Original post by Corroded
>>1.) Don''t use an underscore at the beginning of your function names - the C++ standard says:

Yes. Its a possibly bad habit I''ve formed from I-dont-know-where. I use the underscore to indicate a private function of a class. In this way it will never coincide with anything in the global namespace, and it sorts all my private data in the VC intellisense class-completion box so I dont have to actually think.



I believe its time to look into the inner workings of this mysterious C++ utility called ''namespace'' --> thats what they were designed for

Share this post


Link to post
Share on other sites
quote:
Original post by Corroded
>>1.) Don't use an underscore at the beginning of your function names - the C++ standard says:

Yes. Its a possibly bad habit I've formed from I-dont-know-where. I use the underscore to indicate a private function of a class. In this way it will never coincide with anything in the global namespace, and it sorts all my private data in the VC intellisense class-completion box so I dont have to actually think.

A name that begins with an underscore followed by an uppercase letter (like your _NormalizeVector() function) is reserved to the implementation for any use, including macros and keywords, which means even if it's a private member of a class (which the examples you gave didn't appear to be, presumably you've posted them out of context) it could cause problems. Namespaces won't help there either. The chances of it actually causing a collision in most cases are slim but it still seems best to avoid it to me. If you must use an underscore for your private class members, use an underscore followed by a lowercase letter rather than an uppercase letter. Personally I think leading underscores are ugly but that's a matter of taste. Anyway, in practice it's probably not that big a deal.

quote:
I'm almost 100% sure I can integrate it into the VC IDE and use it as my default compiler. I was unable to find information on how to do this, and after poking around with the VC options I'm still just as clueless. Do you happen to have a link to a thread/page that might give me a place to start?

Try this thread. I remember seeing discussions somewhere on how to integrate the compiler into non-Professional versions of Visual Studio but since I already have a version of VS with the optimizing compiler I didn't pay close attention.

(Edit) - looks like ApochPiq beat me to it.

[edited by - mattnewport on April 23, 2004 1:29:05 AM]

Share this post


Link to post
Share on other sites
>>I believe its time to look into the inner workings of this mysterious C++ utility called 'namespace' --> thats what they were designed for

Huh? Are you suggesting that I place all my private class members in a namespace? That would not only be rather silly, but would result in design issues where-in private functions would be unable to access any public data of the class...

>>I believe this thread contains some things you may be interested in.

Excellent! I perused that thread and it does indeed contain several useful tidbits. It appears that my silly little post has brought me some other rather useful information.

>>A name that begins with an underscore followed by an uppercase letter (like your _NormalizeVector() function) is reserved to the implementation for any use

True true. Its one of those habits that I know I should really break before it bites me in the butt. Perhaps I should come up with a less problem-prone naming convention.

Cheers

[edited by - Corroded on April 23, 2004 1:37:27 AM]

Share this post


Link to post
Share on other sites
"After all, very few people would consider it wise to use a shotgun to open their front door when a key does the job much more elegantly "

awesome! ^^

Share this post


Link to post
Share on other sites
Hi Corroded,

The point I think people are trying to make, is that you don''t need any naming convention for member functions of a class, because they won''t conflict anyway (they should always be qualifiable, at the least).

I''ll just go ahead and second everybody else, you really do want to break your habit of this naming convention because one day it will absolutely kick your ass, because some implementations really can do weird things with macros and so forth that will just replace your text, regardless of namespace etc.

-Mezz

Share this post


Link to post
Share on other sites
quote:
Original post by ApochPiQ
quote:
Original post by Dobbs
Hideous and slow? More like very appropriate and having no discernible effect on speed. Removing it is just asking for a divide by zero and some screwy bugs that are hard to track down.



quote:
Original post by ApochPiQ
One final comment on the if() statement: a conditional inside a piece of code that is called a lot will hurt performance. You may run into cache mispredictions or other nasty things that end up chewing away a lot of CPU time. It is unlikely that you will get cache mispredictions in a test that simple, but the principle holds: don''t use conditionals more than you absolutely have to. First of all, mag will never be zero, because the y coordinate is 64. If you use the normalization code in other places, you cannot assume this; but in the context of the code you listed above, you know for a fact that mag will never be 0. Secondly, even if it is 0, the effects will be minimal. You may get incorrect lighting or a very minor performance drop, but it will happen only in incredibly rare situations. Weigh the costs and benefits: you will lose performance with the conditional, period. At the very least it is an extra instruction which can contribute to cache problems. At the worst you will cause cache misses which are very, very harmful for your speed. On the other hand, removing the conditional will give you temporary and virtually unnoticable problems in extremely rare situations. This kind of cost/benefit analysis is crucial to doing good code optimization, so start early



I think that should be fairly self-explanatory.


I missed the part about y always being 64 so you''re right in this case but I don''t agree with you in general...

First, I''ve run into some fun bugs with zero magnitude vectors - like game objects/models that suddenly disappear and are never seen again - so in my experience this can be a serious problem.

As for misprediction - the zero magnitude vector is probably a rare corner case for most applications so the branch won''t be mispredicted very often (and if it''s a common case perhaps it should be handled explicitly, no?).

Share this post


Link to post
Share on other sites
The principle here is not to remove error checking; the principle is that conditionals in heavily-used code are a performance killer. Cache mispredictions in this case are not going to be common - but the fact is, the mere presence of the conditional is taking up some cycles. If the program is normalizing vectors so often that the performance of the normalization code is important, those few cycles can make a big difference.

In this particular case, mattnewport said it first: zero-magnitude vectors cannot be normalized, period; the result is undefined. If you are trying to normalize a zero-magnitude vector, you have serious issues in your mathematics and code design at other places in the program. For something like Mathematica, a check for zero-magnitude is important. For a game, where that case should damn well never occur, the check is a waste of time. Again, if you are normalizing zero-magnitude vectors, your software is broken higher up in the chain than the normalization code itself. Fix the real problem, not the symptoms.

Share this post


Link to post
Share on other sites
Actually, with branch prediction on modern processors, that if statement will only take more cycles when it is mispredicted. After the first two or three calls, it will always predict a non-zero value and won''t take any extra cycles. It will take extra cycles when there is a zero value, but that''s such a rare case that it doesn''t matter.

As far as zero values being a "mistake", floating point can give you wierd results because of rounding. Better to be safe than sorry. Removing error checking because you "think" you will get a speed up is almost never a good idea.

Also, as far as moving the error checking outside the function; then you have multiple locations where code is reproduced, more potential for programmer error, duplicated code, more work for you and the compiler. Hardly worth removing one if statement that only takes more time if a zero magnitude is found (which, as you said, probably won''t happen).

karg

Share this post


Link to post
Share on other sites
The error checking should not be moved into other parts of the code; the error checking should simply not exist. A 3D engine should never have any occasion to deal with zero-length vectors, especially in the realm of surface normals. I''ve seen floating point error do some really strange stuff, but I''ve never seen it produce a precisely 0.00 result as an accident.

Again, as I said above, the principle is not to remove simple error checks because they handle vanishingly rare cases; the principle is to design the code so that error checking is not needed in performance-critical sections.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
If you know a bit about how floating point works, you''d know that it is very much possible to predict the errors you will get, and that errors from rounding WILL NOT EVER cause a value to "accidentaly" become zero.

Share this post


Link to post
Share on other sites
quote:
Original post by Karg
Also, as far as moving the error checking outside the function; then you have multiple locations where code is reproduced, more potential for programmer error, duplicated code, more work for you and the compiler. Hardly worth removing one if statement that only takes more time if a zero magnitude is found (which, as you said, probably won''t happen).

The point is that a normalize() function doesn''t have enough information to handle invalid input correctly. What do you propose the function should do if it finds it''s input has magnitude 0? The function given simply fails silently which is a very bad ''solution'' - you just pass the bad data on to cause problems elsewhere. By the time the problem shows up it may be very hard to track back to the source of the problem. I''ve seen normalize() type functions which return an arbitrary unit vector (e.g. (1, 0, 0)) when passed a 0 length input which is even worse - a low level function like normalize() is in no position to decide what is a suitable way to ''fix up'' bad input. The fact is that passing a 0 vector into a normalize() function indicates a bug in the calling code and that''s where a fix should be applied. A reasonable solution is to put an assert in the function so that you''ll catch bad data during testing and have the information you need to fix the problem rather than fix the symptoms. Performance is really a side issue here - the central issue is that calling a normalize() function with a 0 length vector is a bug at the call site and so should be caught and fixed at the call site.

Share this post


Link to post
Share on other sites