Sign in to follow this  
Aph3x

Huge world size

Recommended Posts

Hi all, I currently use floats for my WorldPosn class, but have realised that I need a much larger world than I have now (probably want upwards of ~500k a side) and floats have nasty lumpy properties at these sort of distances from the origin :( Has anyone here implemented a huge size world in their engine, and what was your approach? I'm currently attempting a fixed-point approach using int64's, which is giving me headaches. I thought possibly using doubles, but this would be similar changes but without the predictable precision of the int approach..?

Share this post


Link to post
Share on other sites
You could use int or int64 for positions, which is better than float or double as they are uniformly distributed. You probably want to know the position of anything with the same accuracy regardless of where it is.

For all kinds of calculations you could first transform all needed positions into local coordinates (origin at object x), calculate the result using floats and transform them back into (int or int64) global coordinates. No need for fixed-point arithmetic.

Share this post


Link to post
Share on other sites
@Motorherp: It's the word 'simply' that puts me off ;) There's a section in GPG4 describing this approach, and it looks horrendously complex, especially when e.g. measuring distances across sectors?

@Puppet: Yer... seems to be using a sector (node) and offset approach from what I can gather?

Quote:
Original post by Trap
For all kinds of calculations you could first transform all needed positions into local coordinates (origin at object x), calculate the result using floats and transform them back into (int or int64) global coordinates. No need for fixed-point arithmetic.


I'm trying an int64 approach now, but as my float units are ~ 1.0 = 1 foot, how would I avoid the fixed point bit? I have an fp multiplier of 1024, giving about 0.29mm accuracy according to my calcs.

It all falls down a bit when for instance I want to draw the whole world map!

Share this post


Link to post
Share on other sites
Lets fill in some numbers: Earth is around 40,000 km in circumference. Using a int64 to store the location gives you around 0.001 nm per value. I think thats a bit to accurate.
Using a 32-bit int gives you one point each 1 cm. Which should be good enough for most purposes.

Using floats only makes a difference if you zoom in very far. If you use floats in locale coordinates for every object the error will be very small, way smaller than 1mm. If you use floats in global coordinates the error can be huge, at least 1 m. But that doesn't make any differece if you draw the whole world.

Share this post


Link to post
Share on other sites
Well, some of the movement constants for my vehicles are down to very small fractions. For instance the acceleration on my large vehicles is 0.00006 ft per ms. Admittedly my physics ticks are set to 20 ms, but any smaller and I'd get quantisation or truncation to zero? In fact looking at this I may need to increase my 1024 FP multiplier!

Share this post


Link to post
Share on other sites
doubles would be good enough too. They essentially are 53 bit integers, while floats are only 24 bit integers. The remaining bits are used for automatic scaling which is of no use in storing absolute positions.

If your world is small enough that worldsize/(2^32) is tiny in comparison to anything you calculate you can use int for position like this:
//Euler
float a = stuff()
float v = v + a*dt;
int pos = pos + (int)(v*dt);

For drawing you would use locale coordinates of the camera. float drawpos = (float)(pos-camerapos);
For doubles it would be the same thing. You need to send locale coordinates to the graphics hardware. Else the additional precision will be thrown away before rendering.

I don't know if doubles or ints are faster if used this way.

Share this post


Link to post
Share on other sites
Quote:
Original post by Trap
int pos = pos + (int)(v*dt);


And there lies my problem: with small position increments the int cast truncates to zero. So from what I can see, using int's will require the fixed-point manipulations I've been doing :-/

I do the relative camera thing for rendering so that the gfx api receives only 'well-conditioned' floats (i.e. near enough to the origin to be accurate enough for my purposes)

Well... I'm in the middle of totally encapsulating my WorldPosition so hopefully I can interchange the underlying types more easily in the future.

Share this post


Link to post
Share on other sites
In Game Programming Gems 4 there's an article about solving accuracy problems in large world coordinates (presenting "far positions"), with the basic idea of decoupling position to a segment and a local offset inside the segment.

Share this post


Link to post
Share on other sites
Quote:
Original post by Aph3x
Quote:
Original post by Trap
int pos = pos + (int)(v*dt);


And there lies my problem: with small position increments the int cast truncates to zero. So from what I can see, using int's will require the fixed-point manipulations I've been doing :-/

Sure it does truncate to 0. But floats truncate there too: bigfloat+tinyfloat==bigfloat
This truncation problem is 256 times smaller with ints than it is with floats. Try it!

If you need even finer position resolution you can use double with 53 bit resolution or int64 with 64 bit resolution.

If the smallest size a single pixel ever is is 0.1 mm than you can use ints without truncation problem up to world sizes up to around 400 km.

Share this post


Link to post
Share on other sites
@Jetro: yer I mentioned how nasty that looks to Motoherp.

@Dragon:
I'm working on this.
The low accel is for a ~20,000 ton ship, currently 'feels about right' with 0.00006 ft/ms accel.
I have spatial partitioning/culling based on using each island as a locality, defined by a Delaunay triangulation.

@Trap: Hmmm... I'll see what happens when I finally get it to build again!

Share this post


Link to post
Share on other sites
well, Trap's idea very good for continuous worlds, especially when implemented with graphics hardware (which internally only uses floating point precision). And it is very simple to implement.

The problem is as Aph3x says that when rendering the entire map, you get problems. But actually who wants to map the entire floating point plane to the screen? Talk about a "anti-injective" map...

regards

Share this post


Link to post
Share on other sites
Acceleration to velocity doesn't truncate, as both can be stored as floats regardless of how you store your position.
Velocity to position truncates. If you have something that should move 1mm/s it will not move at all if your positions are 0.1 mm apart and each step is smaller than 100 ms. You could use accumulation of the (+v*dt)-terms over several steps to reduce this but choosing a bigger datatype should both be easier and faster.

You could use doubles for position and be done with it. You can then store every position on earth on a grid of 4 nm...

Share this post


Link to post
Share on other sites
If you understand the IEEE 754 standard very well, you can easilly see how to mix the best of both worlds :
- a fixed precision, so that no jerks appear in the rendering (through the matrix combos) when the camera moves.
- have the flexible accuracy required by the physics when small values (derivatives) are combined and then added to bigger ones (positions)

I made a demo of a huge terrain in the past (65*65kms, could have been bigger), stable precision for rendered details, that also worked well with typical physics.

To solve rendering unstabilities, I simply biased the vertex positions by a huge power of two, just higher than the size of the world (say 2^16). This worked in theory up to the limits I mentionned.

Next to do that on a really big scale you must combine the ideas of clustering and biased floats. To have the most stable coordinates, according to the integer representation of the floating points, simply choose power of two sizes for your chunks. It's a worthy constraint.

Once done, this will have the effect to clamp the precision of your floating points as if they were of a constant metric precision, as if you used fixed points. They will not be less precise when far from your center (the biased origin). And then you are left with floating points only, which are far more practical to use and code than fixed point.
- because you don't need fixed point classes.
- because most libs prefer it (physics, geometry)
- because the CPU is faster with them
- because the GPU prefers them

Depending on your requirements you can apply these ideas to 32bits floats (24 bits mantissa) or 64 bits floats (53 bits mantissa). And also make something hybrid, for instance store positions as double floats, velocities as (single) floats.

Share this post


Link to post
Share on other sites
Quote:
Original post by Puppet
Check out the article "the continious world of dungeon seige".

It's worth checking out only to see how you would overengineer a solution to the problem. I'd stay away from that approach if I were, well, anyone. Seriously.

A more practical solution to the problem involves using integers (or fixed point numbers, same thing) for world positions and using floating-point numbers for vectors. Per Vognsen gave a good description here:

http://www.flipcode.com/cgi-bin/fcmsg.cgi?thread_show=11105

There are several other variations of the same theme, but they all amount to essentially the same thing (integer positions, float vectors).

Share this post


Link to post
Share on other sites
@Charles: I keep attempting to read "What every computer scientist should know about floats etc"... but its *such* hard going ;)

@Christer: Nice link - in fact that appears to be the exact way I'm now trying. Encapsulated fixed-point int64's in a WorldPosition, and e.g. a method RelativeTo(const WorldPosition& aOrigin) that returns a 'well-conditioned' vector3 of floats being the difference between positions.
Also a method ApproxVector() that returns a float vector version of the world positions.

Moving the code over is proving to be one hell of a refactoring session!! :(

Share this post


Link to post
Share on other sites
Quote:

but its *such* hard going ;)
...
Moving the code over is proving to be one hell of a refactoring session!! :(


So you see, you should not avoid this dilemna :

- "increase my knowledge" : take a bit more time to understand the inner format of the floating points which is pretty well standardized. Then possibly only add a few translations here and there in your code, at some strategic points. It's really not that hard to understand.

Imagine that I discovered it by myself a long time ago, wondering how floats looked like in memory. I found fantastic opportunities on how to exploit it, exciting perspectives in the times of software rendering. So with some docs on the www, that should be ez. Or else as I did, learn empirically, make a small C console program to watch how the integer representation of the floats behaves (use a bitfield) when you + * / etc ... And when you understand such things as the "Carmack" rsqrt tricks, you are done with it, and you'll find many opportunities to exploit that many times in the future ;)

- "let's do it now" : refactor your code the way you described it here.

which do you think will take the least time for you ? I can not answer for you. But since you wrote a "hell" ...

Share this post


Link to post
Share on other sites
Ooh cosmic karma... I bought an excellent book called "Realtime Collision Detection" the other day. And look who should turn up and help me out ;)

*ahem* anyway, just curious for an answer to Trap's last question... *bump* in other words...

Share this post


Link to post
Share on other sites
Quote:
Original post by Trap
@Charles B:
Why offset coordinates? I can't see how it reduces errors.

You are right it does not necessarilly reduce absolute metric errors. It will increase them in most cases.

Quote:

As far as i can tell it only reduces error differences.

But it will make them coherent, and decrease noticeable errors. That is as you rightly pointed the differences of accuracy that can bring nasty effects :
- graphical artefacts (black pixels)
- jerking vertices at short ranges.
- non reproductible physical behaviours.

This may sound like clutching at straws, but first, it's not any offset. It's a very precisely defined bias. Something like 2^n or 1.5*2^n. If the solution that mixes integers (or fixed points) for world coords and floating points for vectors works, then biasing the floats achieves exactly the same result, with more convenience and perfs because only floats are used.

So it's more generally a question of discretizing the coordinates of the static decor objects and avoid cracks at their junctions.
This reduces the number of low order bits and thus reduces dropped bits, that is precision losses.

Next the bias also constraints to more stable metric accuracies during the intermediate flops of the 3D transfos. Thus less spatial discontinuities (jerks, black pixels, etc...). But that's only evocated in the great lines.

So now, if one still wants to see in details what discretization brings, which artefacts it anihilates, in which conditions, one has to know it requires a very precise and tedious math demo, and many technological considerations to understand it fully. I could probably do it here if someone wants to go deeper on this track. I did refresh my my memory on paper, with graphics, matrices, comments on 3D APIs, etc.... So I am a bit too lazy to translate in ASCII and type all that stuff unless it really has some interest for someone.

The best I can say is first experiment the idea. Empirically see if produces some effects. It's a minimal reingeneering job for such a test. Use a macro, set the bias to 0 to get back and compare to the original version (?). Then if required understand the theory and tricks (come back here) much deeper to make the solution robust.

Share this post


Link to post
Share on other sites
Quote:
Original post by Charles B
If the solution that mixes integers (or fixed points) for world coords and floating points for vectors works, then biasing the floats achieves exactly the same result, with more convenience and perfs because only floats are used.


Nonsense. The range and precision of the two systems are greatly different, so biasing of floats most certainly does not achieve exactly the same result.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this