Jump to content
  • Advertisement
Sign in to follow this  
Kest

Cross product failure

This topic is 3812 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

This is a painfully simple question, of which the lack of answer is simply painful. What is the best course of action to take when the parameters passed to a cross product function are incabable of creating a valid cross product?
x = (a.y * b.z) - (a.z * b.y);
y = (a.z * b.x) - (a.x * b.z);
z = (a.x * b.y) - (a.y * b.x);

float d = (x * x) + (y * y) + (z * z);
if( !(d > 0) )
  ThrowAFit();
I'm having a pretty tricky time catching the code that causes these situations, because of floating point precision. Vectors that are about to be normalized look okay until I try to normalize them. The values are apparently too small to be computed correctly when I reach code such as..
float mag = 1.0f / sqrtf((x * x) + (y * y) + (z * z));
One way or another, mag often ends up with #INDO type markings and breaks the whole system apart. Is there any established norm for detecting float-based vectors that are too small to normalize? Or is there any trick to normalizing them? Or does anyone have any related advice at all?

Share this post


Link to post
Share on other sites
Advertisement
Technically, the cross product doesn't have any "invalid" results since the zero-vector is perfectly acceptable as a result. In the normalization code however, you want to check and see if the length is below a certain epsilon value. This differs from application to application, and is really just a value you know to be "too small" for any vector length your code should be expected to work with.

At any rate, what your code does when it detects a very small vector is up to you.

Share this post


Link to post
Share on other sites
What I don't really understand is why the vector size makes any difference. If the floating point is large enough to have a value, would it not be possible to just scale it by a large number to fix it? If it's to be normalized anyway, it doesn't seem like it would change anything.

Share this post


Link to post
Share on other sites
Yes, use double. I often found a double solves quite a lot of problems.

Otherwise, are you ending with NaN, or infinities? The solution for infinities is simple. Detect some minimal value for DOT product of the vector. If you have NaNs, you are screwed.

Share this post


Link to post
Share on other sites
It's not the size of precision error that's a problem (float vs double). It's just not being sure of how to deal with it when it happens.

Share this post


Link to post
Share on other sites
Hi Kest,

I currently have exactly the same problem as you. The interesting thing is, that the low floating point precisicion can even lead to cases where the sign of the crossproduct is wrong. The category of your problem is very popular within the field of computational geometry and is quite a big one. See here for a good
explanation:
http://www.informatik.uni-trier.de/Reports/TR-08-2004/rnc6_03_schirra.pdf

Mesh-processing algorithms often rely on the evaluation of crossproducts, dotproducts and intersection computations. Degenerate cases (for example extreme slivery triangles) may lead to cases where the low precision creates some slightly false values which make your algorithm decide wrong - and in the end your application crashes or hangs in an endless loop.

In your case:
Zippster is right. There is no invalid crossproduct, but invalid results caused by inprecise floating point computations.
Normalizing the vectors before doing the cp makes things even worse because of the division.

If your algorithm is only interested in the sign of the crossproduct to make a decision then there are methods for computing the sign of the cp-result without computing the cp itsself which will be much more robust.

Another solution would be to increase the precision. Maybe you wanna try doubles first. It doesnt really solve the problem but it lowers the chances of those degenerate cases. If that isnt enough look for "arbitrary precision arithmetics". There are couples of libraries out there. Those datatypes overcome the precision problem of floats/doubles but are much more slower. To speed up those techniques there are so called filtering techniques which you can apply before doing the computation. The filter will detect whether the computation can produce a correct result. If this can not be assured then some higher precision arithmetics are employed.

Another alternative would be the use of a computational geometry package. I currently work with CGAL (computational geometry algorithm library). Its quite modern and looks really promising. I can not tell you how good it works since Im still implementing and I use it the first time. So no results yet.

I hope I could help you a bit. I know those problems are really nasty and notorious. Good luck.
David


Share this post


Link to post
Share on other sites
I think I've found an arbitrary number to verify the (squared) length of vectors before choosing to normalize and cross them to obtain other vectors.

The function..
BOOL CheckLength() const { return (x * x) + (y * y) + (z * z) > MATHRES; }
where..
const float MATHRES = 0.0000000001f;


Is there anything that looks questionable about this? It feels questionable. But if there's nothing else that can be done, I suppose it will work.

Share this post


Link to post
Share on other sites
I use 1.e-5
Also, try to keep your vectors around unit length. If the vectors are too small and you are trying to compute a cross product, then I guess that's your problem.

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.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!