Understanding floating point precision and camera space.

zillion42 · Post by **zillion42** » Fri Jun 05, 2009 1:23 pm

[RENAMED] original title was...
Binary Coded Decimals and a custom coordinate system ?

Hi,

I was wondering if anyone has any experience with Binary Coded Decimals in irrlicht.
To start from the beginning I'm trying to achieve greater number precision for my solar system gravity simulation.
http://irrlicht.sourceforge.net/phpBB2/ ... hp?t=32299

I am using a lot of very high numbers like these:
Code:


aswell as very small numbers like this on for example:
Code:
//Day += (1/86400)*timescale; <-- is to small for f64
const f64 incrementF = 1.1574074074074074074074074074074e-5;

Calculations generally work, but the outcome is often far from precise. Also I'm using mixed types. So what I stumbled upon is this generic microsoft explanation:
http://support.microsoft.com/?scid=kb%3 ... &x=12&y=12
Also I have a huge area to cover and the normal vector3df doesn't seem to work well when reaching the outer solar system... So what I would need is another custom coordinate system that works underneath the actual used one, unfortunately I have no idea on how to go about the implementation... Now that is actually 2 questions, anyone pointing me to some source or recommending or explaining some techniques would be greatly appreciated.

thx

BlindSide · Post by **BlindSide** » Fri Jun 05, 2009 2:21 pm

I've heard people using 128 bit integers to encode these kinds of positions. When you need to render just calculate everything's position in vector3df relative to the camera. Well you could used fixed point but you're getting the same precision in the end anyway.

zillion42 · Post by **zillion42** » Fri Jun 05, 2009 2:53 pm

thx for the fast reply... Well I wasnt really considering 128 bits, do I need to ?

Well you could used fixed point

Sound like something I had in mind for the coordinate system, more or less working with areas in which precision is acceptable and cropping the rest as long as the camera resides in one area (squares of space or BB's for example)
And I was looking for a binary coded decimal library of some kind that easily works with irrlicht...
From:
http://support.microsoft.com/?scid=kb%3 ... &x=12&y=12

Floating point decimal values generally do not have an exact binary representation. This is a side effect of how the CPU represents floating point data. For this reason, you may experience some loss of precision, and some floating point operations may produce unexpected results.

This behavior is the end result of one of the following:

* The binary representation of the decimal number may not be exact. -or-

* There is a type mismatch between the numbers used (for example, mixing float and double).

To resolve the behavior, you can either ensure that the value is greater or less than what you need, or you can get and use a Binary Coded Decimal (BCD) library that will maintain the precision.

hybrid · Post by **hybrid** » Fri Jun 05, 2009 9:51 pm

I've never heard of a use of BCD for this purpose, and I guess you will still face some limitations: 1/3 is not exactly representable in the decimal system, so once you have this value you will get some imprecision as well.
Since you don't seem to care for performance you can simply multiply all numbers with 10^20 or something and use an arbitrary size integer library. So basically a poor-man fixed-point solution. Otherwise you can only work with such number ranges with lots of care and numerical analysis.

vitek · Post by **vitek** » Sat Jun 06, 2009 4:45 am

Even if you did use BCD, double or long double, you still have to send vertex data and matrices to the GPU, but the hardware doesn't support any of these. i.e., You have to convert the data back to float for rendering.

Travis

zillion42 · Post by **zillion42** » Sat Jun 06, 2009 1:41 pm

wow, thx for all the replies.
I gave the whole thing more thought and talk with a friend. I still yet haven't given the BCD libraries a shot, will do that regardless of the facts I learned partly through your answers.
Yes, decimals expressed binary have limits no matter how many bits there are to represent them, like hybrid said for example the numer 1/3 will never get represented precisely, same is true for any other periodic decimal.
I found two candidates for testing, one is decNumber++ from IBM the other is called the GNU Multiple Precision Arithmetic Library (GMP), I will report on how it went on.
http://www.alphaworks.ibm.com/tech/decnumberplusplus
http://www.cs.nyu.edu/exact/core/gmp/

And yes, Numerical Analysis is another thing I've been tinkering with, for example instead of using the grotesque high numbers for the planets masses expressed in kilogramm I might aswell find a new base for them, like many astronomers do by expressing them in fractions or multiples of earths mass. Doing so will bring the 9 planets in a range from 0.0558 - 317.83 thus greatly simplifying the matter, but doing so will also change the gravitational constant (not changing, just scaling to keep proportion) which was, even though previously unmentioned, one of the smallest numbers I've been dealing with... 6.67428e-11 ... Now putting a number like that in an equation with the mass of Jupiter (1900000e21) for example is bound to get inprecise. The equation for Jupiter for example went on like so:

Code: Select all

force = (6.67428e-11 * 1900000e21 / pow(distanceInMeters,2));

which is true but highly inpractical. One question though is whether I have the brains to scale both factors into an acceptable range without mistake.

Also I could try using tons instead of kilos and kilometers instead of meters. Not quite sure yet but definitly some mindbending work ahead.

Now the matter of f32 coordinates is an entirely different problem and requires another solution. If I get the term 'fixed point' right, what BlindSide was suggesting is, instead of moving the camera in one direction I could move the whole solar System in the opposite direction. This way, the planets far away can kiss my *** but the important local gravitational intense bodies would always be in an acceptable distance from 0,0,0 giving the camera the required precision after the komma or dot and not in front. Another approach would be dividing the whole solar System into sectors and periodically resetting its position once the camera crosses the border between two sectors... Also here, not quite sure which way to go for but definitly some mindbending work ahead.
A good reading about this I'm currently on to:
http://forums.xna.com/forums/p/26929/147946.aspx

BlindSide · Post by **BlindSide** » Sat Jun 06, 2009 3:05 pm

If I get the term 'fixed point' right, what BlindSide was suggesting is

You got the idea, that's fantastic. But it had nothing to do with the "fixed-point" comment, that was just referring to fixed point decimals as opposed to floating points.

Although not the first thing that comes to mind when dealing with a space-sim, this article regarding the creation of Dungeon Siege (Particularly the "The Precision Issue" section) should be of interest as it describes managing a large continuous world whilst dealing with precision issues: http://www.drizzle.com/~scottb/gdc/continuous-world.htm (A quick read reveals they are using something similar to your "sectors" idea.)

zillion42 · Post by **zillion42** » Sun Jun 07, 2009 1:59 am

instead of moving the camera in one direction I could move the whole solar System in the opposite direction. This way, the planets far away can kiss my *** but the important local gravitational intense bodies would always be in an acceptable distance from 0,0,0 giving the camera the required precision after the komma or dot and not in front.

wont work because then I'm going to run into the same problem. Either the camera is off bounds or the environment, it's the same thing again. Resetting the camera aswell as the environment to an acceptable distance from 0,0,0 seems to be the only solution.

Thx to BlindSide for the excellent link:
http://www.drizzle.com/~scottb/gdc/continuous-world.htm

The Precision Issue

From the beginning, the engineering team knew that the continuous world was going to significantly affect the engine and content design, and the core issue was numerical stability. Imagine two characters walking in formation two meters apart heading east away from the origin. At some point, the distance from each other is overwhelmed by the distance from the origin, and the characters will appear to be “at the same location”.

With floating point, the further you get from the origin, the more precision you lose, which can cause all manner of nasty problems. Things don’t sort right, cracks appear between adjacent meshes, space starts to quantize, and cats and dogs start living together. Dungeon Siege uses the FPU in single precision mode for the obvious performance benefits, and to match the native precision of the video hardware. However, even if we increased the precision, it ultimately could never solve the problem because the world was planned to be, and ended up, incredibly large.

The precision problem meant it would not be possible to have a unified world coordinate space like most other games. Instead, the solution was to segment the continuous world into a set of independent coordinate spaces, and switch among them periodically to reset the precision. A variety of ideas were tried out within these constraints, and we eventually settled on a variation of a standard portal system.

Our solution consists of a relational node-based coordinate system, in which each chunk of geometry (Siege Node) has its own coordinate space, and is linked spatially to neighboring geometry via the doors it shares in common with those neighbors. The arrangement of nodes connected by doors forms a continuous graph that represents the entire world map. This node system evolved over time from its original goal of maintaining FPU precision to become the primary method of efficiently subdividing space, and the root of countless optimizations.

In order to encapsulate the concept of a 3D position relative to a specific node, the traditional (x,y,z) vector had to be augmented with a node ID (x,y,z,node) and represent an offset from the origin of a specific node instead. This 4-tuple is encapsulated as a Siege Node Position, or SiegePos. Later on, we added a SiegeRot (quaternion,node) in order to handle comparisons between orientations across nodes.

The phrase “there is no world space” became a mantra to the team, although it literally took years for everyone to fully grok what it meant.

So I'm already getting the distance of the camera from the sun, which lies in the origin (0,0,0) all I have to do now is offsetting camera and solarsystem say every Astronomical unit by the cameras distance and vector from the origin (1 AU = 149 598 000km = 1495.98 irrlicht units).
Hard labour birth but I think I'm getting there...

Edit3, btw:
in that case I'd be having something like spherical sectors, which aren't really sectors just offsets to keep track of once the camera distance from origin exeeds a certain distance. But in the end I wont even have to keep track of them at all.
It's more like periodically resetting the whole world including the camera in a in a mannor that maintains an acceptable distance between camera and origin. From each reset position continue moving the camera away from origin until it reaches its reset distance again.

zillion42 · Post by **zillion42** » Mon Jun 08, 2009 12:41 pm

ok, I'm totally lost again... I added another emptySceneNode called world, which holds everything now excluding the cameras...

Code: Select all

world
	^
	|
	planetNode		= is driven by solar.cpp and pushed into array<scene::ISceneNode*> planets
	|
	|--->planet		= is rotated according to sideral rotation period and pushed into array<scene::ISceneNode*> planetsR
	|	 |--->atmo
	|	 |--->ring
	|
	|---->moonNode	= is rotated according to lunar orbital period and pushed into array<scene::ISceneNode*> moons
		 |--->moon	= is rotated according to moons sideral rotation period and pushed into array<scene::ISceneNode*> moonsR

In any case, getPosition() and getAbsolutePosition() make a huge difference now, and my code is littered with both. I'm really having a hard time re-reading and re-understanding everything. Also I keep on forgetting what, where and how things get determined. Just missing a pipeline really, or in other words there is one but I never planned it, thought it through or am particulary aware of it. Just poor mans code... gosh, might aswell just start over... Ok, sorry had to vent it out somehow...