O-Town Graphics

Saturday, June 17, 2006

Numerical precision

Irrlicht has a few big no-no's in the numerical precision department. I had my first real surprising 3D bug in Starbourne when the camera is tracking the ship and suddenly the whole 3D scene disappears. I instantly suspect it isn't my code (my gut reaction lately and it usually turns out to be correct). I'm suprised niko fell for some of the common things to watch out for... or perhaps one of his contributors didn't realize that the real world sucks.

The fact that I was able to instantly pinpoint a problem of numerical precision as a NAN and even set the breakpoint within the code at the right place scares me. It scares me because I used to be SO scared of not really understanding what is going on in 3D and once I come across a tricky bug how can I fix it? But to have someone better than me fall in silly traps mean that perhaps all I lack is experience... and intellectually I have the capability of "getting it", even if it does take a long time. Perhaps few people do, perhaps people just implement things without a full understanding and get away with it.. Of course, I can live with and almost cherish a few bugs because I love niko's programming style and plus it gives me some real world practice with working with the innards of a 3D engine.

To reiterate, numerical precision issues can occur in many ways. I recommend reading the Collision Detection book for further details by Christer Ericson for more details.

Here is a few common pointers
1. Do not check a floating point for a number directly. Because of numerical accuracy it is often likely that a number will never be completely equal. Addition of large numbers by small numbers often causes precision loss so sometimes, (float)A + (float)B != A + B. So, you must set a tolerance level called epsilon and do a check. So if you want to check if float A == 0.0f, the best way is to actually do
if (fabs(A) < epsilon) { .. } 
where say epsilon is small, like 0.000001. You can make it smaller for doubles. Of course, this applies to multiplication, division, and subtraction too.. whenever you are doing operations where the magnitude of the number varys greatly, this is often a big source of loss. Simply stated - floats are a necessary evil. They have the most precision clustered around the origin of the number line (0.0), but the precision decreases as you move to + or -
std::numeric_limits<float> ::max
. So you must be aware that the precision actually changes depending on the number!

2. Watch out for division by ZERO! Seriously, this isn't a game. Divison by zero can happen almost anywhere. So don't do it! Check the dividend and replace it with an epsilon if you must. But then you may have to watch out for overflow! So be careful and try to make sure an equation is stabilized. Do not divide a very big number by a very small number. With planes, you should probably switch to a thick plane implementation as described by Ericson's book.

3. Watch out for fucking inverse tangent function shit. Jesus christ, that's a dangerous function. Watch the values! Make sure they are in range and clamp them if necessary. Watch out for the angles that can produce degenerate values, like near 90 degree increments.

4. Euler angles - Holy fucking shit don't use them. Use axis-angle instead.

Well folks, that is all. I feel the passion exploding in this one. I hate when my 3D scene disappears.

5 Comments:

  • Comparing floats with regards to an epsilon isn't really correct. You'll need to use a smaller epsilon closer to zero and a larger epsilon closer to max_float. You want to check the number of distinct floating point values between two floats or the number of ULPs. Here are all the really dirty details:

    http://www.cygnus-software.com/papers/comparingfloats/Comparing%20floating%20point%20numbers.htm
    http://tinyurl.com/oagd2

    By Anonymous Parveen, at 2:26 AM  

  • Ah, but I didn't say anything about the floating point epsilon. Your thinking of an epsilon where it equals the smallest value such that 1 + epsilon > 1. This epsilon is much larger than that. So, it is more of an experimental number used to help prevent divide by zero's and overflows.

    It isn't really effective to scale epsilon in calculations, because your equations should never need such scaling in the first place. All equations that deal with both really large and really small numbers at the same time should be mentally flagged as having issues. Even if you do correctly scale the epsilon after analyzing the range of the floating point numbers in question, your still looking at a failure of accuracy... making your robust floating point numbers useless anyhow. Imagine a collision detection routine that scales the epsilon and considers it "okay" that shipA is within 10,000 meters of ship B, just because the comparison is done with such distance away from the center of the number line. That signals a failure of the algorithm. If a larger epsilon, like 10 ^ -5 isn't sufficient to prevent under and overflow, you should probably look into either a higher precision number or a better strategy.

    One more thing, there are some cases where it would be good to estimate the effects of the floating point epsilon. One example is applying decals, because the equation itself deals directly with the differences between the near and far plane. And in this case it isn't about accuracy - it is about the fact that you really do need an epsilon big enough to offset a pixel to the next z value in the z-buffer.

    By Blogger Wizards1stRule, at 5:43 AM  

  • Actually Matt, Parveen is right on this one; using an absolute tolerance like your blog post suggested is rarely the right thing to do. Most times you want to use a relative tolerance (or, indeed, a combination of both). I cover the issue of absolute vs. relative tolerances at length in Section 11.3.1 of my book.

    Of course, ideally you probably should work within a fixed range so you can properly anticipate your errors and set an appropriate absolute tolerance. Unfortunately, it tends to be hard to do that in practice, with e.g. game artists having full control of the extents of the game art assets (levels) they create (or similar for other industries, e.g. CAD/CAM users).

    By Anonymous Christer Ericson, at 1:22 PM  

  • Thanks for the post, Eric. My main point was that it is superior than doing nothing. But a solution that is often inadequate (or rarely the right thing to do, as you say) is just that, inadequate, and because of this I've updated my blog to reflect that scaling the epsilon is important. Thanks a lot for the clarification! Hopefully people will bring up this issue (numerical precision) more because it does seem like it is not talked about enough. Which precisely explains why many people have no idea about the issues and people like me who even recently started learning it still haven't completely scratched the surface. Again I am new to 3D programming as a career (only 5 months so far) so it is really exciting to be able to talk to real people in the industry and have them respond to my little blog!

    By Blogger Wizards1stRule, at 11:14 PM  

  • Have good day Wizards1stRule, I like your blog and I want to exchange your blog link with my link,
    my blog is Arts Collections .
    pls feedback to me.
    -----------------------------------------------------------------------------------------------------------
    Good Google Link About Arts

    By Blogger Jonh Neo, at 2:33 PM  

Post a Comment

<< Home