Numerical precision - Update

I just got a post from a few people including Christer Ericcson on the importance of scaling your epsilon value. Although my post is right to some extent (it is a good start, and definately superior to doing absolutely nothing), unfortunately it is also inadequate. In addition to a fixed tolerance, one should also consider scaling the epsilon value so you have a relative tolerance level. For more information see his response on my last blog entry about Numerical Precision.

3D engines galore

I can't seem to keep away. If I'm not working on the VRML 3D renderer at work, I'm working on Irrlicht at home (well, mostly my game that USES Irrlicht, but to me its just one big entity). I added FSAA (full-screen antialiasing) support in the OpenGL renderer to Irrlicht tonight (or is it this morning?) plus fixed 3 bugs in vector2d class plus one.. well (1 of which may be more of a 'feature-lack'). At this rate Niko might make me an honorary German ;-) German engineering..in DA house

I think it is time to start looking into per-pixel lighting... but alas, I should probably focus on the more boring parts of my TODO list in the ever quest to bring an epic to life.

In fact, my TODO list needs a TODO list to manage all the TODOs. TODO - Sleep.

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.

Silicon Valley ... FIGHT!

The Fight Club of Silicon Valley

Recently there have been reports of fight clubs in Silicon Valley, California. Apparently some tech guys just have to get militant. So... I can only imagine the insults coming from a team of core computer graphic programmers when they decide things must get bloody :)

"Yo, fool, Don't make me bitch slap you past the far plane, you'll be clipped, fool!"

"Oh yeah, well I'll punch you so hard you'll be spun around and back-face culled"

"Ha, take one step and I'll project your face on the infinite plane of my fist"

"I'll slice you up faster than Cohen-Sutherland's Clipping Algorithm"

"Whoa, that's pretty intense man"

"Not as an intense as the union of my surf board to your chest"

"That's impossible, I'm too intact for that...who do you think you are, Delaney?"

Then Mom comes: "Hey guys, come back inside, stop all this z-fighting!"

A few random thoughts

I've collected a few articles on fluid dynamics. To much of my amazingment, the math doesn't look horribly difficult. After a point you start to shrug off complex math because it is simply just one of those things that you get used to, so you adapt and hack at it.

The advantages of fluid dynamics is it gives you a much more realistic model for modeling smoke, water, fire, and gases. Essentially these fluids act as set of forces that all affect each other like an interconnected grid. A good model will allow you to simulate smoke stacks, nuclear explosions, even flames of fire.

In other news, Irrlicht uses a left-handed coordinate system and it upsets my balance of life. It angers me, just because I'm so used to a right-handed system. How dare they share a model with Direct3D :) Sure it makes sense from a conceptual standpoint, especially since the perspective transformation of OpenGL will flip the z-coordinate anyway in clip space so it becomes left-handed. I digress though.. it still pains me :)

To review, the basic method to convert from a left-handed system to a right-handed system is you must change the order of triangle vertices when importing models - p0 p1 p2 becomes p0 p2 p1 (which thus flips the normals - this is important, otherwise you have all your objects being backface culled, hehe), and then you must flip the z coordinates. Not too bad. Irrlicht also seems to treat the y axis as a z axis and vise-versa when importing 3D Studio models. But I need to verify their codebase to make sure.

When reading my real-time collision detection book by Christer Ericson I can't help but wonder why no one has mentioned thick planes to me before. It seems not only elegant but in some ways practically mandatory as to ensure numerical stability. Case in point - intersect a nearly parallel line segment against a plane using a parametric equation and solve for t, where t = [ 0, 1 ] indicates an interesction. The problem is as the two are closer to parallel, t approaches +- infinity! That is SO not good :) Thus, you must use thick planes and conditional code to solve for things robustly. So what are thick planes? Instead of solving the equation of a plane N.(P-P0)=0, you solve it like N.(P-P0)<epsilon where epsilon is the a very small value. That small value makes the plane "thick". Of course, this simplicity has many rammifications in algorithms (such as clipping), hence you should refer to the Ericson's book for more details. But do not do clipping without it! (That includes BSP tree's, jackass!)

Z-buffer / decal derivation and Starbourne

Well, I've been rather busy. As my 3D career progresses, things are starting to become clearer in my head. I'm gaining a more firm grasp on the mathematics and the code. I've noticed that a lot of the times, developing code is just sweat - work that needs to be done. You have to put in the time to get the results.


I found an error in the derivation of Eric Lengyel's excellent book. In Mathematics for 3d Game Programming & Computer Graphics, Second edition, P. 276, there is an estimate of the epsilon given in order to help calculate a z-buffer offset for decal application:

|epsilon| >= (1 / 2^m-1) * (f-n)/(f+n)

Where f = far plane, n = near plane, and m = number of bits of precision in the z-buffer. According to Eric, "The minimum epsilon equation was derived by considering that the offset shown in Equation (9.4) is a constant epsilon * (f+n)/(f-n) at all depths. In an m-bit depth buffer, the distance between discrete z values is 1/(2^m-1), so we just set the offset equal to this value and solve for epsilon. As already mentioned, this value is just a theoretical lower bound. Its exact value isn't meant to be used, but instead the calculation is meant to give you an idea of what general size your offsets need to be."

However, as confirmed via e-mail, this reasoning only works if the range of the normalized z-buffer was between 0 and 1. But since that offset was found a perspective z equation that is supposed to normalize z-values from -1 to 1, the discrete z values map from -1 to 1, hence the distance between the discrete z-values actually twice as much - 2 / (2^m - 1). I have confirmed with Eric that the correct epsilon equation is:

|epsilon| >= (2 / 2^m-1) * (f-n)/(f+n)

I would like to reiterate that this value is considered by the industry professionals as essentially a theoritical low-bound for the actual epsilon values. Hence, you need to use an experimental value in conjuction with the theoritical value to truely eliminate z-fighting when implementing a decal functionality.

In other news, I've started developing Starbourne, the space game, in my free time. The details of this title are shrouded in mystery (as any indie game should be), except I will admit it is based on the excellent Irrlicht game engine.