Ok, I have been recently pondering how to hold position data in large-scale games (really big arena areas). At first, I had always assumed that I would store positions of entities in type float or double. However, the use of non-fixed precision has always bothered me. Tell me if I have this wrong, but a float value is essentially binary scientific notation (3.15*10^2 = 315). This specifically means that smaller values are just as accurate (relatively) compared to large values (ie: with 3 digit precision, both 2.15 and 215 are valid, but 215.15 is rounded to 215). This means that decimal precision decreases for large values (near the origin, a 0.1f value between to points is preserved, while far from the origin, a 0.1f distance between to points is not preserved). I feel like the right way to do things is to either use a fixed-precision value for absolute positions, or use type long, but convert to float for all relative distance calculations. I then looked through the source engine's vector code, and they appear to be using simple float values. Is there something I am missing? Is their some way to set float values to be fixed-precision? [Edited by - generaleskimo on November 7, 2007 3:42:32 PM]

Quote:Original post by mossmoss
Yes, as the magnitude of your floating-point numbers increase, the precision decreases.

I am not sure what engine you were looking at... It may be using only floats because it is not intended for large-scale where the precision loss would matter. Or the engine authors, if they intended for such a large-scale, didn't understand this issue.

In any case, here are a couple suggestions.

First, keep this document handy, something everyone coding should know: http://www.physics.ohio-state.edu/~dws/grouplinks/floating_point_math.pdf

Second, determine if the loss of precision is at all important. What are your numbers going to represent? What units? (Inches, meters, miles...?) What is the set of values you need to represent? (For example, you might say, "My world needs to be 100 kilometers wide and I need per-meter precision.")

Third, once you break it down to what a delta of 1.0 means (and 0.1, 0.001, etc)... you should be able to determine whether you can keep your precisions at the outskirts. If you can, or can live with the error, might as well just use floats.

However, if your precision requirements are such that floating-point alone is going to lose more precision than you'd like, you have a couple of options...

Go all fixed-point, use 32- or 64-bits. Get a good fixed-point library or write your own (not all operations trivial, though).

Do some combination of fixed-point and floating-point. Use fixed-point for the gross (ie. large), more global portion and use floating-point for the finer (ie. smaller), more localized portion.

Well, I was using Valve's Source Engine as a reference, because I have a feeling they put a lot of thought into a decision like this. However, I may be mistaken about some bits. I know that their vector class uses only float values, and the vector is used to refer to all positions and relative positions (as far as I can tell), but maybe it is different for when they refer to entity locations on a lower-level. My engine will be dealing with things in the now-typical first-person prospective, so for all practical purposes you can consider it a shooter.

Ok, I have to go, but I will be back soon.

As far as I know, the maximum size of a single level in Valve's Source engine is -16384 to +16384, in 3 dimensions. Given that this is only a tiny fraction of the entire range of a float, they're unlikely to run into precision problems.

I think they also chose to use this limited range because they convert floating-point into fixed-point during network transmission.

If they were doing a planet simulation or something they might be in precision trouble ;)

However, if you have really big worlds, like The Continuous World of Dungeon Siege, you can still get away with using floats as long as you do everything in relative coordinates, not absolute coordinates.

[Edited by - Hodgman on November 8, 2007 6:55:46 PM]

Anyways...

You see, it is not so much the loss of precision that bothers me, as I can obviously use whatever unit I want. It is the difference in precision. I feel like that one day, when using float, I will reach the problem that I need to account for a 3-centimeter precision for one place in a level, while I have an unnecessary 0.1mm precision at a place closer to the origin. When looking at other games, I feel like there must be something I am not understanding.

I will return to Valve's Source Engine as a reference, as the game DLL's are open-source for modding, and the design seems very well thought-out. I'd guess that the position of an entity in the game (NPC, physics prop, static model) is accurate to 1 centimeter, meaning the smallest increment an entity can move would be 1cm. There is really no need for it to be any smaller, and if it were any larger, a small bit of movement of a wooden box on the ground would begin to look like more of a "lurch", as the object would pop over 4 or 5cm. However, it may be that the renderer fills in these gaps by just lerp'ing the model's position. Anyways, I can just assume that I am not far off on this assumption. If Valve does, in fact, use float values to store entity positions, it seems that objects farther from the level's center would be less accurate than ones which are closer. This would mean that an object's movement would become more jerky in certain areas, which is a problem the player does not want to see, and the level designer should never have to deal with. It may be that such constraints are only seen when levels grow extremely massive, but this does not seem true.

From what I can tell, using any un-fixed precision unit for absolute position seems wasteful, as it gives overly-accurate positions near the origin, and extremely inaccurate positions far from the origin. However, I must be missing something, because it seems that Valve has used simple float values with amazing success. Either I am reading their code incorrectly (and there must be some other system, maybe something splitting the absolute positions into a larger integer grid), or I am really not understanding something very important.

So, for the sake of simplicity, lets say my average level size is 1 square kilometer. Not massive, but by no means small. And, for the sake of simplicity again, I choose to have the lowest delta be 1cm. If I commonly have position values exceeding 1cm in accuracy, then I am wasting storage space. If I commonly have position values with accuracy of less than 1cm, then level spaces are inconstant, which is just begging for a bunch of design problems. Maybe far from the origin, a little car slowly moves away from the origin. However, it is so far that its velocity is less than the precision at that position. This means every second, when the object is displaced a distance equal to its velocity, the absolute position of the car will not change, because:
Really really big number (with resulting low precision) + Really small number (with unnecessarily high precision) = the same really really big number
Such an event seems entirely unacceptable to me, but it is obvious that there is something I am not understanding.

Quote:Original post by alvaro
Your thinking is qualitatively correct, but floats have precision to spare for a situation like the one you just presented. If your scene is 1Kmx1Km and you represent coordinates in meters, a float will allow you to represent steps of around 6.10352e-05 m on the far edge. Yes, it's wasteful, since you claim to only need 1 cm precision, but where are you going to find a 17-bit integer type to not waste anything? Well, even then you would be wasting around 0.39 bits of information per number.

Your machine has hardware that deals with 32-bit floating point numbers very well. The resolution that they offer is more than enough for your purposes. You will need numbers for other things than positions in your game (normal vectors, camera orientation, light intensity...) and some of those may have scales that are quite different from your positions. If you use floats, you don't have to think about these issues of scale.

Unless your cars move less than 61 micrometers per frame, you shouldn't have much trouble with floats. :)

Well, that calms me quite a bit. Now the trouble is that I really don't know how accurate I really want it to be. For a first-person game, is 1cm precision enough? I was thinking that obviously vertexes inside a model need to be more accurate than 1cm relative to one another, but I always assumed that when the model is transformed into screen space to be rendered, the model's interior precision would work out, because if it is off by 0.5cm, then the whole model will be off by 0.5cm, not just individual vertexes. Tell me if I am wrong about that, but I don't think that a vertex inside a model is also going to be rounded to the precision of the model's world-space position.

However, do people often get away with less precision? I mean, I could see how a first person engine could be accurate to 3cm, and the renderer would just interpolate between model positions for the frames in between the game's "think" logic. However, for really slow objects, this doesn't seem like it would work. I am just trying to get a handle on what is standard, and why. If I was wrong about that, then how precise do most engines need? I will go and look at Valve's Source Engine again, but it seems like at some point they must have decided what the lowest acceptable precision was, and capped it near there.