FAR Positions - Solving Accuracy Problems in Large World...

[Van]

I don't know if Ogre has this concept implemented in one fasion or another - I can't seem to find it so I thought I would put in request for it.

Referring to book:
Title: Game Programming Gems 4
Chapter: 2.3 - Solving Accuracy Problems in Large World Coordinates
Page: 157
ISBN: 1-58450-295-9

In this chapter, the author (Peter Freeze, NCsoft Core) uses a method to solve large world coordinate problems by implement a concept called Far Positions which is a hybrid between fixed-point (segments) and floating-point (offset) numbers. Here is an example:

Code: Select all

class FarPosition
{
private:
  FarSegment m_segment;
  Vector3 m_offset;
  static float m_segmentSize;
};

union FarSegment
{
  struct
  {
    int16 x, z;
  };
  int32 xz;

  matFarSegment() {};
  matFarSegment( ZeroType ) : xz(0) {};
};

Well, we attempted to implement this but the author did warn us of, and we did stumble into, the fact that the entire engine pipeline has has be use this concept or it won't work properly. When we try to convert back to a standard Ogre::Vector3 we loose precision - even if we set the Ogre::Real to a double.

It would be nice if Ogre would someday support something similar to this ( or if it does, please tell us).

[:wumpus:]

Setting Ogre::Real to double makes it use the IEEE double format for all its operations. This is a 64 bit floating point format with 53 mantissa bits. This has an incredible range and should be enough for any situation. It can represent magnitude differences of 10^21 to 1. For comparison, this is almost the radius of the solar system (approx 10^12 meters) to the radius of one water molecule (approx 10^-10 meters).

I can honestly not think of any non-scientific application in which this is not enough. Also, your "fake" floats have no hardware support making them inconvenient for realtime uses. If you really want to use them in Ogre, make an overloaded C++ type implementing the needed operatiions and typedef it as Ogre::Real instead.

[Chris Jones]

this is almost the radius of the solar system (approx 10^12 meters) to the radius of one water molecule (approx 10^-10 meters).

i never realise just how big the values of these types can go, just like another thread about the frames being counted and why isnt it being wrapped around etc

altho, how would you go about making a map bigger than the solar system? or is it the case of waiting until 128bit CPUs come out and have Ogre::Real as a 128bit variable?

[:wumpus:]

Making a map bigger than the solar system? I don't think you realise just how big our solar system is. There is no way you can represent all the matter (up to molecular level) of even a little stone anyway given the memory and disk space available

So the logical way would be to use a unit like kilometer or lightyear (instead of angstrom ) for representing large distances. That way, you can have much much larger distances.

Also be aware I am on talking about the accuracy here. The full range of the double type is from 10^-380 to 10^380 (same for negative numbers). This is so crazily huge that I can't think of an example here.

[steven]

I think the first step is to identifiy why you have an accuracy problem.
You could be interested by these links :

http://en.wikipedia.org/wiki/IEEE_Float ... t_Standard
http://en.wikipedia.org/wiki/Floating_point

More complex :
http://docs.sun.com/source/806-3568/ncg_goldberg.html

@:wumpus: If you want an unique coordinate system for a "game" with several solar systems separated by hundered of light-years containing inside each solar system objects whose locations are in cm (i.e. persons inside a base), I think you will need such a concept as FarPosition.
Even cm is probably not enough, a physical engine will probably not give good result with units in cm (but I may be wrong on this.)

Another solution would be to have each solar systems with its own coordinates system (each sun position = <0, 0, 0>) and travel between systems through portals.

[:wumpus:]

Another solution would be to have each solar systems with its own coordinates system (each sun position = <0, 0, 0>) and travel between systems through portals.

Right, or star trek warp speed, which twists space around you instead of traveling yourself

For purposes of a science fiction game it makes no sense to actually simulate all the empty space between the solar systems. Only complete fools would try to fly from one solar system to another using sublight speeds.

[Azatoth]

For purposes of a science fiction game it makes no sense to actually simulate all the empty space between the solar systems. Only complete fools would try to fly from one solar system to another using sublight speeds.

And yet, that's what Frontier did.
With the exception of a couple of well known bodies, the Milky Way was fractally/procedurally generated. So it was possible to take off from a hangar on one planet and indeed fly the whole stretch to another solar system and land in another hangar. All in sub-warp speed (with time acceleration).
It would be interesting to see how Braben did it. And all in assembler.

[steven]

... simulate all the empty space between the solar systems.

Humm...
It seems that this space contains much more than we thought previously : Oort cloud, Kuiper belt, etc.

http://en.wikipedia.org/wiki/Oort_cloud

Astronoms even found a new 10th planet WITH A MOON !

http://www.spaceref.com/news/viewpr.html?pid=17942

In fact space is empty around stars with some orbiting planets !

I know that it's a bit offtopic, I dont' want to hijack.

[Van]

For purposes of a science fiction game it makes no sense to actually simulate all the empty space between the solar systems. Only complete fools would try to fly from one solar system to another using sublight speeds.

Well, that may be your take on it. Our MMO focuses on an aspect that most games do not really touch upon: EXPLORATION. Yes, we have vasts amount of space. Yes, most of it is empty but our universe is dynamic. What was there a month ago may not be there now or vice versa (except for suns and planets). Yes we have the ability to FTL (faster than light travel).

Everything in our implementation is based on a meter. So, one Ogre Unit = One meter.

We have broken our universe up into Quadrant, Sectors and Position (all of which are Vector3). So, a player can be in Quadrant (57,3567, 93452), Sector (1435, 4568, 22), Position (0,0,0). We would like to have each sector to be 10,000,000 meters (or 10,000KM) accross (i.e. 5,000KM from center in all axis). However, we get artifacting when we cross the one million meter boundry. Perhaps we are doing something wrong and I will go back and look at it again.

[xavier]

Accuracy becomes a valid consideration when you use sub-meter granularity. I've read the GPG4 article more than once and it is a good solution to the problem if it arises.

[Van]

Accuracy becomes a valid consideration when you use sub-meter granularity. I've read the GPG4 article more than once and it is a good solution to the problem if it arises.

Yes, it would seem to solve our problem. But the entire graphics pipeline has to use it or you really gain nothing. That's why it may be nice to have something like this supported in Ogre. Perhaps someone with more knowledge and skill than I could write a SceneManager plug-in that would do this..

[Chris Jones]

Making a map bigger than the solar system? I don't think you realise just how big our solar system is. There is no way you can represent all the matter (up to molecular level) of even a little stone anyway given the memory and disk space available Smile

lol, i do, did astrophysics as part of physics ALevel

ok, this thread has now made me want 2 make a space simulator type program/game, space is just too facinating! anyway, must concentrate!

p.s. random fact: the universe is 13 billion years old, and is 156 billion light years accross, how screwed up is that

[xavier]

Accuracy becomes a valid consideration when you use sub-meter granularity. I've read the GPG4 article more than once and it is a good solution to the problem if it arises.

Yes, it would seem to solve our problem. But the entire graphics pipeline has to use it or you really gain nothing. That's why it may be nice to have something like this supported in Ogre. Perhaps someone with more knowledge and skill than I could write a SceneManager plug-in that would do this..

In terms of standard calculation error, like the article said, the problem is when the graphics hardware has only a certain processing accuracy. 128-bit internal processing seems common in commodity-level hardware now, but supporting older 32- and 64-bit cards could lead to noticeable accuracy at distances or after numerous transforms.

Valid concern that it is, you're talking about a serious upheaval in API and implementation, for what in the end is an extreme case: most games and simulations still work fine with single- and double-precision accuracy. The effort of implementing FAR locations in Ogre would probably be better spent on porting to 64-bit architectures, which might solve your problem in a different way.

[:wumpus:]

128 bit floating point processing on commodity hardware? Do you have a link?

Graphics hardware is still limited to 32 bit or even 24 bit in some cases on ATI. This is why APIs like D3D only use float32s.

We have broken our universe up into Quadrant, Sectors and Position (all of which are Vector3). So, a player can be in Quadrant (57,3567, 93452), Sector (1435, 4568, 22), Position (0,0,0). We would like to have each sector to be 10,000,000 meters (or 10,000KM) accross (i.e. 5,000KM from center in all axis). However, we get artifacting when we cross the one million meter boundry. Perhaps we are doing something wrong and I will go back and look at it again.

As I said, doubles can still count with values up to 10^21. That means that with a world size of 1 000 000 000 000 000 000 000 you can still represent 1 meter. 10,000,000 should be piece of cake.
If you have accuracy problems with 64 bit doubles you should blame your algorithm instead of machine precision

[xavier]

128 bit floating point processing on commodity hardware? Do you have a link?

That's what I get for not reading the specs that closely...

[Van]

As I said, doubles can still count with values up to 10^21. That means that with a world size of 1 000 000 000 000 000 000 000 you can still represent 1 meter. 10,000,000 should be piece of cake.
If you have accuracy problems with 64 bit doubles you should blame your algorithm instead of machine precision

I am not, nor do I claim to be, a math expert. However, I do know what we have tried and are accutely aware of the results.

First, as I understand it, that 10^21 is an illusion. 10^21 is the total number of numerics LEFT AND RIGHT of the decimal. So, you may be correct that a world size of 1 000 000 000 000 000 000 000 can represent 1 meter but what happens when I want to represent 0.0005 of a meter? I just reduced the size of my world by ^4. And, it appears that the further out from ZERO you go, the MORE precision you will require for smooth motion - at least that is our expierence. I read somewhere the magnitude of the vector plays a large roll in the precision. More precision (i.e. digits to the right of the decimal) reduces the amount of digits available to the left of the decimal (and vice versa).

For example:
(this is a pathetic example but illustrates the above point)

Ogre::Vector3( 4500000000000.123, 4500000000000.123, 4500000000000.123 ) + Ogre::Vector3(0.5, 0.5, 0.5)

does not appear to produce the same smooth motion results as

Ogre::Vector3( 45.123, 45.123, 45.123 ) + Ogre::Vector3(0.5, 0.5, 0.5)

From our experiements, it appears that you need a minimum of three decimal places to the right for smooth motion when your distance from zero to less than 1,000. Then, for every 1,000 ogre units (or meters) you move out from zero you need another decimal place for precision. As you can see, that 10^21 gets eaten up pretty quick.

[:wumpus:]

First, as I understand it, that 10^21 is an illusion. 10^21 is the total number of numerics LEFT AND RIGHT of the decimal.

Yes, the total number of digits can be 21. I don't see how this makes it an illusion?

So, you may be correct that a world size of 1 000 000 000 000 000 000 000 can represent 1 meter but what happens when I want to represent 0.0005 of a meter?

In that case, you can't. But then again, you will not have a world size of 1 000 000 000 000 000 000 000, as that's crazy. If you drop three digits before the decimal, thus 1 000 000 000 000 000 000 you can already represent 0.001 meter.

I just reduced the size of my world by ^4. And, it appears that the further out from ZERO you go, the MORE precision you will require for smooth motion

Sure, but that has to do with the ratio <highest number you want to represent>/<lowest number you want to represent>. That can't exceed 2^21.

zero to less than 1,000. Then, for every 1,000 ogre units (or meters) you move out from zero you need another decimal place for precision. As you can see, that 10^21 gets eaten up pretty quick.

Incorrect. How do you think every 1000 ogre units eat another decimal place. I generally count thousands like this: 1000,2000,3000,4000,5000,6000,7000,8000,9000,10000,110000... which means you need one extra decimal for the first 1000, then one extra for the 10th, then one extra for the 100th thousand.. .etc.. even when adding 1000 per millisecond you will not consume 2^21 in the lifetime of the sun.

[xavier]

His empirical data shows that is what happens. With the number of calculations potentially involved, and the amount of error therefore accumulated, it's quite reasonable to lose a decimal place's worth of accuracy per 1000 units.

[:wumpus:]

How is that reasonable, according to you? If he is losing precision that rapidly it means he has to re-order his operations, instead of using a wider type, because this would mean you burn 128 bits in twice the time you need to lose 64. A half time very rapid is still rapid.

[Van]

Wumpus is right, I miss-typed what I meant to say. Let me re-phrase: as you increase the decimal places on the left side of the decimal so must you increase them on the right side of the decimal.

So:

0 - 999 needs 3 to the right.
1000 - 9999 needs 4 to the right.
10000 - 99999 needs 5 to the right,
and so on.

So, when you break the equilibriam and one side of the decimal places suffers (usually the right side) then you start to get artifacting. At least that is what we gather from our expirence.

[alphageek]

You might be interested in numeric_limits::epsilon().

Basically part of the problem you have is called absorption, where for 32 bit floats:

Code: Select all

1e15 + 1 == 1e15

Definitely, the size of the existing value directly determines the largest value that will be absorbed in the above manner. To calculate this value for any number you can use numeric_limits::epsilon().

Simply multiply your current position by epsilon, and the result will be the maximum value absorbed.
So theoretically:

Code: Select all

some_float + (some_float * std::numeric_limits<float>::epsilon()) == some_float

The artefacts you are getting are likely because you have varying size timesteps, so I guess you initially encounter jerky motion? Some timesteps are large enough to produce a per step movement above epsilon, but smaller timesteps create movement that is absorbed by your current large position.

I don't know if anyone else has mentioned them, but there are also a series of excellent articles on gamasutra on some of the issues with creating a vast playing world.

I doubt very much there will ever be a scenemanager (and everything else) that magically makes this problem go away, so you'll have to solve it yourself.

In my game, I am solving this with separate coordinate systems. When the player jumps to FTL I put them (and everything else relevant) into a coordinate system based around 'Astronomical Units' (where distance from earth to sun ~= 39 Au). This wouldn't solve the absorption problem itself (if the player continued going at several hundred metres per second) except that player FTL speed is now represented in Au/time (rather than metres/time for local space). Whenever the player drops out of FTL, I create a metres-based coordinate system around them.

HTH

[steven]

Another current error is that with most floating-point implementations,
these numbers are not associative, nor distributive :

Code: Select all

 (1e100 - 1e100) + 1.0 = 1.0, 
 (1e100 + 1.0) - 1e100 = 0.0.

Errors in floating-point computation include also : rounding, absorption, cancellation, overflow, underflow, invalid operations and rounding errors.
This is why you should read the theory behind floating point number and identifiy where your error comes from.
See the links above.


@alphageek

'Astronomical Units' (where distance from earth to sun ~= 39 Au)

You are not using the normal unit : 1 AU = earth-sun distance ?
http://neo.jpl.nasa.gov/glossary/au.html

[alphageek]

You are not using the normal unit : 1 AU = earth-sun distance ?

Whoops, I was somehow confusing this with Pluto's average distance from the sun: 39 Au.
Thanks for the correction.

[Maleficus]

And yet, that's what Frontier did.
With the exception of a couple of well known bodies, the Milky Way was fractally/procedurally generated. So it was possible to take off from a hangar on one planet and indeed fly the whole stretch to another solar system and land in another hangar. All in sub-warp speed (with time acceleration).
It would be interesting to see how Braben did it. And all in assembler.

This is slightly off topic, but a correction: you didn't actually fly between stars in frontier. You flew within a realistic scale solar system with time acceleration, but used simple hyperspace jumps to get between solar systems.

*sigh* I still get nostalgic for that game now and then.

[Nerull]

In my experiance, graphics hardware tends to handle the solar system pretty easily, using 1.0 = 1 meter, with the orgin in the sun. While the 'double's used for the simulation state are still working, the floats used by the graphics hardware start to have accuracy errors - objects will start to jump around on screen. This happens well outside a solarsystem the size of Sol - a lightyear or two, IIRC.


I've solved this by transforming the sol centered coordinates, stored as doubles, into camera centered coordinates, then used these for drawing. This means your current position is always the most accurate.

The method proboby isn't the best, or fastest, but it worked fine for a few objects and a trip from Sol to Alpha Proxima.


Of course, eventually the doubles will run out of accuracy too, in which case you'll need some way to partition up space.