Huge world size

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.

Check out the article "the continious world of dungeon seige".

Why not simply divide your world up into sectors and have distance measured relative to the current sector's origin.

@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!

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.

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!

You only need ints for positions, anything else can be floats.

Hmmm I must be approaching this the wrong way then.
How would you apply acceleration to a vehicle (and hence change its position)?

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.

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.

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.

Hi,

just a few things.
What are you working on?
Why do you need things that have an so low accel?
What is your accel base on? (per sec?)

If you do the section stuff you can incooparete stuff like culling.

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.

@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!

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

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...

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.

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).

@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!! :(