Jump to content

  • Log In with Google      Sign In   
  • Create Account

About fixed points


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
14 replies to this topic

#1 chrisendymion   Members   -  Reputation: 188

Like
0Likes
Like

Posted 21 April 2014 - 07:31 AM

Hello,
 
I'm in an optimization step for my little procedural engine.
For now, I worked with floats for a full planet coordinates. So, there was some artifacts in very high LOD, caused by float precision.
After reading a lot of threads and articles on the net, I came to think about using fixed points (fractional integer) instead of float.
I never worked with fixed points, and so, there are some (lot of) concepts I didn't understand !
 
Where to start using them and.. when to stop ?
 
1- I want to choose freely the planet's radius, let say 5629 kilometers 194 meters 29 centimeters. 
Using a 16 bits whole part and 16 bits fractional part, the fixed radius number will be 368914876 (5629.19429 * 65536), right ?
But in the first place, it will be a float => 5629.19429 in the code (much readable), so I must convert it before sending it to the shader ?
 
2- My planet is quadtree based LOD (cube with 6 grids). Does the grids have integer coordinates ? How to scale them on the radius ?
I imagine I must choose a power of 2 radius for quadtree divisions ?
 
3- If the coordinates of point.x is 368914876, it's a big number in the shader (with far/near frustum, Z buffer, etc.), so what to do ? Convert it to float again ?
I must scale somewhere... ? Buf if 1 equals 1 centimeter.. It will be very very big ?!
 
4- In the shaders, what happens when I use the world, view, projection matrices ? Is there a moment when fixed points are no more working ?
 
It must be something I didn't see/understand.. 
Hope I was readable because it's very coufuse to me and my poor english did not help ;)
 
Thank you,
 
Chris

Edited by chrisendymion, 21 April 2014 - 07:33 AM.


Sponsor:

#2 frob   Moderators   -  Reputation: 21335

Like
4Likes
Like

Posted 21 April 2014 - 08:32 AM

Mixing numbers like that is going to be a problem when you try to convert between the two.

 

A float has 24 bits, or about six decimal digits of precision. Your representation has 32 significant bits, with 16 of them below the decimal point. If your first half goes above eight bits you will be unable to accurately convert between a float and back.

 

I'm not aware of any space game that uses real life scales for planets, stars, and other objects. Space is mind-boggling huge.


Check out my personal indie blog at bryanwagstaff.com.

#3 Stainless   Members   -  Reputation: 941

Like
3Likes
Like

Posted 21 April 2014 - 09:37 AM

Space games often use a 64 bit integer for positions. Or even more.

 

Have a look for a library called vmath, (I'm working from memory here so I may be wrong. I apologise in advance if I am)

 

I seem to remember it used doubles for positions within a solar system them had 3 more coordinates (int's I think) for the rest of the coordinate system.

 

One simulator that used a similar system is Celestia.

 

http://sourceforge.net/projects/celestia/files/Celestia-source/1.6.1/

 

Hope this helps



#4 Vortez   Crossbones+   -  Reputation: 2698

Like
3Likes
Like

Posted 21 April 2014 - 07:05 PM

What about doubles instead of floats?



#5 chrisendymion   Members   -  Reputation: 188

Like
0Likes
Like

Posted 21 April 2014 - 11:13 PM

Thank you all for your answers !

 

Frob, you talk about mixing numbers. It's one of my doubts, do I need to convert the fixed point back to float ? Float to Integer => no loss.

If don't need to convert back, how will work the shaders, as the numbers will be to much big... 

I read, a lot of engine are using fixed points, there must be a solution.. 

 

Stainless, thank you for the links, I will read them now.

 

Vortez, I read that it's a bad solution to use double, I tried to get my idea about. There was too much loss of performances.



#6 Vortez   Crossbones+   -  Reputation: 2698

Like
2Likes
Like

Posted 22 April 2014 - 12:14 AM

By pure hazard, I've just read a very interesting article here, maybe this could help you.



#7 frob   Moderators   -  Reputation: 21335

Like
3Likes
Like

Posted 22 April 2014 - 01:31 AM

Frob, you talk about mixing numbers. It's one of my doubts, do I need to convert the fixed point back to float ? Float to Integer => no loss.
If don't need to convert back, how will work the shaders, as the numbers will be to much big...
I read, a lot of engine are using fixed points, there must be a solution..

There are many problems with it, not just conversion back and forth.

Lets say you are dealing with numbers in a region that is, just for sake of argument, all taking place around 60,000 units from the origin. That's nice that you can be there, but it means you only can go to about 0.1 units for anything before you run out of bits. Translating your models to the scale means any detail beyond 10 cm is at risk. You are guaranteed to be out of bits by the centimeter resolution, so your models are going to render like trash. Your camera's smallest step is also going to be several centimeters as you are out of bits, so don't expect anything to render well.

Or lets say a planet is 3 million units away. Your finest measure of unit will be about ten meter increments, since you have floated up to a higher magnitude. Anything less than ten meters is going to round to zero.

Then there is also the conversion problem. One has 32 significant digits, the other has 24. Your 16:16 fixed format means you will always have at least 16 bits of significant numbers, so the highest integer you can reach is 255. If your units are meters, a limit of 255 meters is not going to work out for you.

There are techniques to constantly re-center the world around the player, giving you lots of precision to work with, but it comes with significant complexity. It is one of those "if you have to ask how to do it, you probably aren't skilled enough to do it" scenarios.

It is certainly possible to have simulations with very large worlds and massive data sets. It just doesn't work well in "For Beginners". What you describe is a massive undertaking, not for someone who is just learning.


Now, fixed point all by itself, that is something you can learn. On hardware like the Nintendo DS, there were three main fixed-point numbers. There were two 16-bit formats (1.3.12 and 1.11.4 layouts), and the 32-bit 1.19.12 format. The choice on which one you used was based on the system you were using and the number of bits you need. These can be learned if you want, but if you aren't developing for fixed point hardware it is a lot of effort for little reward. Ultimately you will end up wrapping the fixed point numbers in a class, overloading all the operators, and then doing all your operations on them like you would with any other number system.
Check out my personal indie blog at bryanwagstaff.com.

#8 samoth   Crossbones+   -  Reputation: 4783

Like
5Likes
Like

Posted 22 April 2014 - 03:17 AM

First of all, you do not use fixed-point as optimization, but for correctness.

 

Using floating point for simulation (or procedural content) at planet scale is problematic for several reasons. First of all, floats are most densely packed around zero, with an exponential falloff the farther away from zero you are. Which, on a planet's surface, where all coordinates are pretty far away from the center, sucks big time. Your stuff isn't located where your precision lies.

But more, adding floats of different magnitudes will lose you some bits. Though, what makes them insidious, not always. It looks like it works just fine, but then it bites you when you don't expect it. 0.5 + 0.5 works just fine (since they're the same range), and even 2500.5 + 0.5 works fine (by coincidence, since they don't consume all digits), but 2500.125 + 0.0625 does not. Errors sum up the more operations you do, and they are not the same at different locations in your world. What looks fine and works fine at one end may not work (quite possibly will not work) at the other end.

Sometimes this just doesn't matter and you get away with it, but sometimes it will give you unacceptable artefacts. Emil Persson gives a better and more detailled explanation in his 2012 Siggraph presentation as well as in his Just Cause 2 chapter in the GPU Pro book (keywords: vertex snapping, jerky animations, shadow map jumping, jitter bug).

 

Fixed-point numbers are just integers, they are evenly distributed and don't lose bits. But on the downside, they have a very finite maximum range. You can do something like 16.16 but that isn't strictly necessary. You can just as well use any number of bits, or even any scale. The only thing that matters is that you must decide ahead of time what will be the biggest thing and the smallest thing that you wish to represent. For example, if you wish to represent detail up to 1mm, and you have 32bit integers, then that means the distance (or size) you can represent is about 4294 kilometers. If you want a planet 5629 kilometers 194 meters 29 centimeters, then you either must choose a coarser resolution, or use more bits, or you are out of luck. Floating point would "just work" if the planet is a little bigger, although unprecise, but fixed point simply won't.

 

With that in mind, and given "planetary scale", you should most definitively consider using 64-bit integers. These will give you a large enough range to represent an entire solar system at micrometer precision. Which basically means you can stop thinking/worrying about what's the right scale right now. On the other hand, this:

 

What about doubles instead of floats?

is not something I would recommend, since it does not address the issues of floating point, it only masquerades the problem so it occurs a bit later.

 

Where to start using them and.. when to stop ?

From the very beginning until... until... until then. Eventually, when passing vertices to a graphics API or at the very least in your shaders, you will have to convert to floats, one way or another (simply because the GPU works that way). Do that when you have no more distances to add/subtract. But start off with thinking of something that is 1.5 meters not in terms of 1.5 but in terms of 1500 (or e.g. 1536 if you prefer power-of-two scales, or any different scale, whatever you like).

 

If the coordinates of point.x is 368914876

 

It is not. It may be 368914876, but relative to an origin which is, say, 369000000, so it is really only 85124. You do translations relative to a local origin (close to your eye) in fixed-point, which is just adding/subtracting plain normal integers.

 

I imagine I must choose a power of 2 radius for quadtree divisions

As long as the boundary between halves is always the same (i.e. you are consistently truncating or rounding the same way), it doesn't really matter if one half if a little bigger than the other. We're talking about a millimeter or so here (or a micrometer even).



#9 Norman Barrows   Crossbones+   -  Reputation: 2138

Like
2Likes
Like

Posted 22 April 2014 - 08:43 AM


I'm not aware of any space game that uses real life scales for planets, stars, and other objects. Space is mind-boggling huge.

 

SIMSpace 8.0 of course! <g>  

 

Leave it to Rockland to do the insane!

 

Chris:

 

i just finished working out the world coordinate system for SIMSpace 8.0

 

you might want to try using an _int64 for decimeters. 

 

when its time to draw, pretend the camera is a 0,0,0.  so you subtract camera x,y,z from the x,y,z of all other objects, put the result in a float, then send it off to directx.

 

for objects past say 1 million d3d units, you do a multi-pass method. first you set your planes far, and draw everything farther than 1 million, but you draw them 1000 times smaller and closer (for example). then you reset your planes and zbuf to normal, and draw everything that's closer. 

 

this will get you accuracy of 0.1 meters, and a range of values from about -992 to 992 quadrillion meters. the diameter of the galaxy is about 100K light years ( 946,000 quadrillion meters).   

 

SIMSpace 8 doesn't map the entire galaxy, only a cube which is 200 quadrillion meters across. 

 

for truly intergalactic distances, you'll want to go with something like an _int64 decimeters, and an _int64 of Quadrilion meters. conversion to float for drawing remains similar to the single _int64 case.

 

as frob said, space is truly huge.   a light year is 9.46 quadrillion meters.     a parsec is  3.2616 light years.   and astronomers use units of kilo parsecs and mega parsecs for measuring the most distant heavenly bodies.

 

approximating the galaxy as a 100 light year diameter disc 200 light years thick, and using 200 billion for the number of stars, you get an average distance between stars of 18.8 quadrillion meters in all 3 dimensions.

 

figuring out an appropriate world coordinate system and how to draw very distant objects is the only really unusual part of building a space sim. from then on, its more or less like any other sim, just convert everything to camera relative coordinates before drawing.

 

you'll also want to code up some routines to add and subtract distances if you use two _int64s or something like that.

 

Note that _int64 decimeters is fixed point: IE  meters with 1 digit of fixed point accuracy.

 

fun fact: 1 warp number apparently equals 100 times the speed of light.


Edited by Norman Barrows, 22 April 2014 - 09:00 AM.

Norm Barrows

Rockland Software Productions

"Building PC games since 1988"

 

rocklandsoftware.net

 


#10 samoth   Crossbones+   -  Reputation: 4783

Like
3Likes
Like

Posted 22 April 2014 - 11:53 AM

space is truly huge. a light year is 9.46 quadrillion meters. a parsec is 3.2616 light years. and astronomers use units of kilo parsecs and mega parsecs for measuring the most distant heavenly bodies.

Luckily, these huge distances don't matter much.

 

If you look at a nearby stellar object (let's say Proxima Centauri, which is a mere 4.2 lightyears), it doesn't matter whether you measure the distance with micrometer or kilometer precision because you can't tell the difference. If you travel at "normal" speeds, then travelling for the entire duration of your life will bring you none closer to Proxima Centauri than about 4.2 light years. It is exactly the same in every respect.

 

On the other hand, if you have some form of "hyperdrive" (or any other fictional faster-than-light travel. wormholes or whatever) then you can reach Proxima Centauri no problem, but you still cannot tell the difference between a micrometer or a hundred thousand kilometers. There's no way you could hit the "stop starship" button fast enough to travel less than a hundred thousand kilometers, and there is nothing interesting but ... empty space... anyway. There is also no way of telling, after travelling 4.2 lightyears, whether that was really 4.2 lightyears or 4.2 lightyears, 33.7 kilometers and 20.0052 meters. Our sun is the same tiny spot when looked at from over 4 lightyears away whether or not it's a few kilometers off or not.

 

In other words, you can conveniently use a coarse coordinate system with a resolution of thousands (ten thousands, if you will) of kilometers to model the huge empty space between interesting things, which is convenient for modelling entire galaxies. And then again, use a different coordinate system at planet or solar-system scale (say, 64bit integers, micrometer precision) to model the "interesting stuff". Switch between them whenever you swich hyperdrive on/off.


Edited by samoth, 22 April 2014 - 11:54 AM.


#11 Ravyne   GDNet+   -  Reputation: 7409

Like
3Likes
Like

Posted 22 April 2014 - 12:21 PM

What about doubles instead of floats?

 

That may help, but it probably only kicks the can down the road a little further.

 

The fundamental problem you are facing is the way that floating point formats -- essentially a base-two form of scientific notation -- encode their magnitude. They're designed to represent very small measures with very high precision, and very large numbers with very low precision. If you're measuring the width of a human hair, you obviously need to be very precise, but if you're measuring the distance between planets, what's a few hundred kilometers error here and there? In fact, there's as many divisable units in a floating-point format between 0 and 1 as there are between 1 and the largest re presentable number. Unlike integral or fixed-point arithmetic, the divisible units are not equally-sized -- the space between them increases the further you get from 0.

 

In a space game I was involved with some time ago, there were similar problems -- planets in this game were actually held in their orbits by the gravity of their local sun, all based on physics. use of a single floating-point coordinate system would cause enough precision error in further-away solar systems that the physics would fall apart and planets would fall out of orbits that they should have maintained. The problem was solved by having multiple coordinate systems -- One that was used to describe the location solar systems themselves, and one local space for every solar system -- basically the suns/stars were in the 'universal' coordinate system, and each sun/star was also the center of its own local coordinate system.

 

Fixed-point could serve as the basis for a single universal coordinate system with uniform precision, but the trouble is that you need an awful lot of bits to represent the number of centimeters between here and Proxima Centauri.

 

Finally, bare in mind that when you work with floating-point, the scale you choose to work at has a great effect on precision over the range of values you encounter. Simply changing 1.0 to mean 1 kilometer instead of 1 meter would have a noticable impact on how the precision errors are manifested (though, I'm not proposing that this simple change would fix your problems).



#12 SeraphLance   Members   -  Reputation: 1411

Like
2Likes
Like

Posted 22 April 2014 - 08:12 PM

 

space is truly huge. a light year is 9.46 quadrillion meters. a parsec is 3.2616 light years. and astronomers use units of kilo parsecs and mega parsecs for measuring the most distant heavenly bodies.

Luckily, these huge distances don't matter much.

 

If you look at a nearby stellar object (let's say Proxima Centauri, which is a mere 4.2 lightyears), it doesn't matter whether you measure the distance with micrometer or kilometer precision because you can't tell the difference. If you travel at "normal" speeds, then travelling for the entire duration of your life will bring you none closer to Proxima Centauri than about 4.2 light years. It is exactly the same in every respect.

 

On the other hand, if you have some form of "hyperdrive" (or any other fictional faster-than-light travel. wormholes or whatever) then you can reach Proxima Centauri no problem, but you still cannot tell the difference between a micrometer or a hundred thousand kilometers. There's no way you could hit the "stop starship" button fast enough to travel less than a hundred thousand kilometers, and there is nothing interesting but ... empty space... anyway. There is also no way of telling, after travelling 4.2 lightyears, whether that was really 4.2 lightyears or 4.2 lightyears, 33.7 kilometers and 20.0052 meters. Our sun is the same tiny spot when looked at from over 4 lightyears away whether or not it's a few kilometers off or not.

 

In other words, you can conveniently use a coarse coordinate system with a resolution of thousands (ten thousands, if you will) of kilometers to model the huge empty space between interesting things, which is convenient for modelling entire galaxies. And then again, use a different coordinate system at planet or solar-system scale (say, 64bit integers, micrometer precision) to model the "interesting stuff". Switch between them whenever you swich hyperdrive on/off.

 

 

This.  Sometimes, your relative distances look like this*:

union distance
{
  int parsecs;
  int lightyears;
  int meters;
};

Rather than This:

UnGodlyHugeArbitraryPrecisionType distance;

Embrace the fact that not all scales of distance ever matter at the exact same time.  Treat units the same way scientists do; don't try to convert everything to a uniform metric.

 

*I'm not actually sure I'd use a union in this kind of situation.  That's just an example.


Edited by SeraphLance, 22 April 2014 - 08:13 PM.


#13 Norman Barrows   Crossbones+   -  Reputation: 2138

Like
1Likes
Like

Posted 22 April 2014 - 09:35 PM


In other words, you can conveniently use a coarse coordinate system with a resolution of thousands (ten thousands, if you will) of kilometers to model the huge empty space between interesting things, which is convenient for modelling entire galaxies. And then again, use a different coordinate system at planet or solar-system scale (say, 64bit integers, micrometer precision) to model the "interesting stuff". Switch between them whenever you swich hyperdrive on/off.

 

This is exactly the approach used in all previous versions of SIMTrek / SIMSpace. as you say it works just fine.

 

now the _int64 makes it possible to use world coordinate systems of light years and decimeters and cover the size of about 3 galaxies. this allows huge game worlds with high precision, and little muss and fuss about multiple coordinate systems, sector/quadrant stuff etc. just a simple "draw whats around the camera, relative to the camera" approach to things, with a little LOD thrown in. SIMSpace 8 will be the 6th title i've done with a game world so large it required world coordinates. and at last, i almost have data types big enough to store the positions etc without a lot of hassle.


Norm Barrows

Rockland Software Productions

"Building PC games since 1988"

 

rocklandsoftware.net

 


#14 Norman Barrows   Crossbones+   -  Reputation: 2138

Like
1Likes
Like

Posted 22 April 2014 - 09:40 PM


The problem was solved by having multiple coordinate systems -- One that was used to describe the location solar systems themselves, and one local space for every solar system -- basically the suns/stars were in the 'universal' coordinate system, and each sun/star was also the center of its own local coordinate system.

 

this is the precise method used by previous versions of SIMTrek / SIMSpace.


Norm Barrows

Rockland Software Productions

"Building PC games since 1988"

 

rocklandsoftware.net

 


#15 chrisendymion   Members   -  Reputation: 188

Like
1Likes
Like

Posted 23 April 2014 - 01:09 AM

Whoah ! Thank you all so much for all your help !
I start to understand. There is just some things to learn more...
 
For the moment, I will concentrate myself on only a planet, I will see later for solar system, galaxies, etc.
 
For very high precision, you say it's better to use int64. I think I need to create a class for converting it to better readable numbers (for coding) ?
If not, with micrometers precision, I will deal with very very big numbers (without digits as it's integer), not very convenient.. ? Some tips ?
 
I understand the concept of  using camera position as the center, for more precision when converting to float.
But subtracting the vertices x,y,z from the camera position in the CPU will be huge ?! There is lot of vertices in the node's grid (x 6 faces)...
Better to do that in the vertex shader, no ? But if I do that, how to send the coordinates to the shader ? 
As the max input is R32B32G32 and I will use 3 x int64... ?
 
My grids are allways the same, they are offseting and scaling in vertex shader based on node position and LOD.
 
In conclusion, when to convert to float and where ? What format to send to the shaders ? 
 
Again, thank you for all your help ;)
 
PS : I know it's a hard concept for a beginner, but I'm here for learning and not affraid to spend hours on that.

Edited by chrisendymion, 23 April 2014 - 01:10 AM.





Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS