Sign in to follow this  
SiS-Shadowman

Physics with a huge scene

Recommended Posts

SiS-Shadowman    359
How do you deal with the deficiencies of floating point numbers when you have a really large range of numbers? Let's suppose I want to simulate an entire solar system, which is (in our case) roughly about 50au ~= 7.5x10^9km = 7.5x10^12m. Seems pretty impossible, even if I only wanted to achieve a precision of 1m, since 32bit floating point numbers roughly grant a precision of 7 decimals: The simulation would become unstable when it's far away from the origin.

My problem arises from using a 3rd party physics engine which is limited to 32bit precision (it seems that most are).
One solution would be to shift the origin every now and then, but I would have to restrict the most important action around this origin and also never can have action in 2 places (separated by a great distance) at once. I've thought about creating separate scenes (of different origins), but I can't come up with a general solution to moving objects from one scene to the other (what about objects overlapping the scene?).
Does anyone have a solution to my problem that allows me to continue using a 3rd party physics engine?

The second possibility is to create my own number class (probably fixed point) and only implementing the physics I need (which is only collision detection, but it's still a lot of work). I'm sure I can implement that, but I have no clue how this would affect performance (probably in a bad way). Do you have any experience in this sort of thing? It is probably really time consuming, since in the end, I have to reimplement alot of basic mathematical functions as well (most notably square root and trigonometric functions).

Share this post


Link to post
Share on other sites
Noggs    141
Use doubles!

Firstly I don't know of any physics middleware solutions which will model a solar system, or galaxies. Plus you probably don't want planets colliding with each other to act like rigid bodies :)

So I would assume that you are going to be simulating the galactic scale stuff yourself, and that you might want the physics middleware to handle... the ships and asteroids etc? If that's the case you probably only want to simulate that stuff when it's near to the camera so chances are you won't come up against floating point inaccuracies anyway. Anything further away could be approximated.

By the way if you are only simulating planets and other spherical objects then the collision detection will be super simple and cheap, and should be easy to implement yourself.

Am I close?

Share this post


Link to post
Share on other sites
zerothrillz    152
Quote:
Does anyone have a solution to my problem that allows me to continue using a 3rd party physics engine?

I think it's unlikely to find such a thing without going into the realm of academia. Sorry, didn't go into detail in your post, but if you're interested in putting galactic forces into a game you're better off faking it in some way.

Share this post


Link to post
Share on other sites
SiS-Shadowman    359
Thanks for your answers :)

Quote:
Original post by Noggs
Use doubles!

Firstly I don't know of any physics middleware solutions which will model a solar system, or galaxies. Plus you probably don't want planets colliding with each other to act like rigid bodies :)

So I would assume that you are going to be simulating the galactic scale stuff yourself, and that you might want the physics middleware to handle... the ships and asteroids etc? If that's the case you probably only want to simulate that stuff when it's near to the camera so chances are you won't come up against floating point inaccuracies anyway. Anything further away could be approximated.


You're right, I only plan to use the physis middleware for ships and projectiles. Currently I'm working with bulletsharp compiled against xna, uses all of XNAs primitives and thus is bound to single precision.

However your idea could work: I would have to "move" the physics simulation with the player: Every now and then I would then set a new origin for the physics simulation, adjust all coordinates and remove those objects that are too far to be simulated this way. Movement of the latter will then be simulated by a cheaper method than a full physics simulation.

Quote:

By the way if you are only simulating planets and other spherical objects then the collision detection will be super simple and cheap, and should be easy to implement yourself.

Am I close?


Unfortunately I need collision detection with other bodies as well, at least OBBs. There are plenty tutorials around the web, but I don't want to reimplement the wheel if I don't have to.

Share this post


Link to post
Share on other sites
voguemaster    183
Hi,

May I suggest a hybrid scheme ? You would definitely need to simulate "islands" (is that the common name ?) or in simple language - every group of entities in your game that are close to one another need to be simulated in the same coordinate system.

In an engine I wrote (but didn't finish) I had the concept of spatial cells. Each cell, conceptually, is a micro-cosmos and has its own coordinate system. Objects
in the game that enter the cell live within its coordinate system.
Its like having several "world transforms" or just several worlds.

The laws governing how and when objects pass from cell to cell can be whatever you want them to be.

So basically, action in two different places in your solar system will be modeled by having two different cells, i.e: two different origins. It works really well and can be used with streaming algorithms to create the illusion of a fluid giant world.

Now, for the representation of the solar bodies themselves. You may recall (or not) that the conic motion paths that are defined by Kepler's laws can be scaled without a problem. So you can have the simulation of the bodies run in a much smaller scale.

You next worries would be to:

1. Determine how and when solar objects may interact with any spatial cell (or origin).

2. How do you scale everything down so that you can properly render everything, assuming its even possible to view everything with one camera (I doubt it).

Just make sure you have a very decent skybox for the background and you'll be fine :-)

Share this post


Link to post
Share on other sites
SiS-Shadowman    359
Quote:
Original post by voguemaster
Hi,

May I suggest a hybrid scheme ? You would definitely need to simulate "islands" (is that the common name ?) or in simple language - every group of entities in your game that are close to one another need to be simulated in the same coordinate system.

In an engine I wrote (but didn't finish) I had the concept of spatial cells. Each cell, conceptually, is a micro-cosmos and has its own coordinate system. Objects
in the game that enter the cell live within its coordinate system.
Its like having several "world transforms" or just several worlds.

The laws governing how and when objects pass from cell to cell can be whatever you want them to be.

So basically, action in two different places in your solar system will be modeled by having two different cells, i.e: two different origins. It works really well and can be used with streaming algorithms to create the illusion of a fluid giant world.


I like the idea, but I see several problems with that approach. Imagine 2 objects in 2 different cells, flying towards each other. If they were to collide right at the border, there's a point when the bounding boxes overlap the border and still don't collide with each other, since they're in 2 separate simulations. It might be solved by adding those objects in both simulations and try to keep them in sync (applying forces etc...).

The second problem is the performance drop if there's action at adjacent planes (2 cells), borders (4 cells) or vertices (8 cells). It would involve a lot of transitions between those scenes.

I'm not sure if those problems can be overcome that easily.

Quote:

Now, for the representation of the solar bodies themselves. You may recall (or not) that the conic motion paths that are defined by Kepler's laws can be scaled without a problem. So you can have the simulation of the bodies run in a much smaller scale.

Yep, that was my idea as well.

Quote:

You next worries would be to:

1. Determine how and when solar objects may interact with any spatial cell (or origin).
2. How do you scale everything down so that you can properly render everything, assuming its even possible to view everything with one camera (I doubt it).

Just make sure you have a very decent skybox for the background and you'll be fine :-)


1. That's a tough one. I haven't really thought about that one yet.
2. Since space is already partitioned by those cells, I could use that for culling as well.

With so many problems to face, I'm just glad I already got that skybox :)

Share this post


Link to post
Share on other sites
Quote:
Original post by Noggs
Use doubles!
Provocative, but nevertheless interesting read.

While I don't wholly agree with the blanket statements made in the article (there are some applications for double, and not everyone using them is automatically an idiot), there is a lot of truth in it nevertheless. Fixed point is the way to go in this case.

Share this post


Link to post
Share on other sites
SiS-Shadowman    359
I've heard that rule before and he may be right.
The point is, implementing fixed point math seems quite easy, but it involves writing physics from scraps if you don't have the source code or a generic solution at hand. On the other hand, some physics middleware already support double precision (bullet for itself, not the XNA port) so I understand how it's easy to simply use double precision instead of reinventing the wheel.

But I'm really curios, why did floating point math become sooo popular? All physics middleware I know of uses floating point math (I've heard some consoles only support fixed point, so my point may only be valid to desktop games).
Floating point math is much harder to grasp than fixed point, and when applied to games, makes testing a real pain in the rear end. Your math might work until you're x units away from the origin. Then all kind of creepy stuff happens.

Share this post


Link to post
Share on other sites
Noggs    141
[Warning what follows is total guesswork - maybe someone who knows more about this can explain correctly]

CPU manufacturers are building general purpose processors, and for that purpose floating-point is a good fit. It handles really small numbers and really big numbers. If they went with fixed point then they would need to arbitrarily fix how many bits to assign to each part of the number. Some applications would work really well with the arbitrary number they chose, lots of other apps would be forced to write their own floating point layer to handle their range of numbers that fall outside of the fixed point range!

You have to work with the hardware available to your target system. If you can afford to take the performance hit and work with your own fixed point format then that's fine. If you're using XNA then personally I would stick with floating point and XNAmath which allows you to leverage SIMD functionality and the FPU registers and units of the CPU. This will involve centering your simulation close to the origin to get maximum accuracy.

Share this post


Link to post
Share on other sites
cgrant    1825
Although precision is an issue, I assume that you may eventually want to visualize your universe sometime. If this is the case, you are going to be constraint on how far you can 'see'. So why would you waste time simulating stuff that is no where near your field of view?

Share this post


Link to post
Share on other sites
SiS-Shadowman    359
Quote:
Original post by cgrant
Although precision is an issue, I assume that you may eventually want to visualize your universe sometime. If this is the case, you are going to be constraint on how far you can 'see'. So why would you waste time simulating stuff that is no where near your field of view?


There are two reasons: First, the player should have multiple ships which shall not be constrained by "don't move your ships too far away from each other". The second reasons is that I'm concerned with floating point precision for a "single" scene. I'll have to do further tests, but if I only have 7 decimals of precision and I want to achieve a useful resolution, like 1 cm (1.0f being 1 meter) I can simulate up to 10km and that's it, which ain't that much in space.

Quote:
Original post by AndyPandyV2
Bullet does apparently build in double precision mode, you could try that.


I just visited the site again and you're right. I didn't notice the double precision build for c# before. Thanks for the hint: It's just what I needed.

*edit*
Quote:
Original post by Noggs
[Warning what follows is total guesswork - maybe someone who knows more about this can explain correctly]

CPU manufacturers are building general purpose processors, and for that purpose floating-point is a good fit. It handles really small numbers and really big numbers. If they went with fixed point then they would need to arbitrarily fix how many bits to assign to each part of the number. Some applications would work really well with the arbitrary number they chose, lots of other apps would be forced to write their own floating point layer to handle their range of numbers that fall outside of the fixed point range!


I almost forgot to answer your post. Your explanation seems reasonable. I was probably thinking too much about this particular problem which would profit from the benefits of fixed point math, but not suffer from it's deficiencies.

[Edited by - SiS-Shadowman on November 18, 2010 2:44:19 AM]

Share this post


Link to post
Share on other sites
voguemaster    183
Hi,

Regarding floating point usage - I guess the most prevalent reason for using floats is that its because of the hardware. CPUs were 32-bit for a long time now and floats (4 bytes) work really well with those registers, and the ST registers.

Now imagine the development of libraries such as DirectX and OpenGL at that time and its only natural that float would be the type everyone uses. Then middleware game engines are written using that tech and that dictates some of the requirements of the engine (but not always as some calculation spaces can happen with more than 32-bit, take for example 3D studio MAX's color space which should be 48-bit if I recall).

Now, floating point are very useful and easy to grasp, conceptually. The problems arise with implementations. The fact that round-off errors exist and the problem with accurately representing numbers that are far from the origin.

For most cases, floats work really well. Even in your example it would probably work well.

Think about a spatial cell as the immediate surroundings of a group of entities. You won't want to model a system of entities that interact with one another at a distance of 10,000 Km. If you need to render them and perform collision detection and physics stuff then they are VERY close to one another.

Are you going to display a "spatial cell" as we called it that contains entities at distances of 10,000 KM from one another ? What's the point ?

Suppose you want to have a map view of the neighboring entities but they are that far away from one another. The system can still scale down quite easily, depending on the zoom factor - from how far you're viewing them:

1. If the typical diameter of the volume all entities are in is ~10K Km, you need to scale everything down so 1.0f != 1m, but more likely 1.0f is around 1 Km (BTW, there are a LOT of floating point numbers between 0.0f and 1.0f so that is good in general).

2. If the view zooms in to view the action of several ships fighting, for example, the scale is much smaller of course as the diameter of the volume they occupy is maybe a few kilometers at most.


Now, regarding one of the issues you've mentioned - the problem of spatial cells and how objects interact with them, I think you got me wrong.

You might be tempted to thinking in terms of an octree or quadtree but that's not what I was talking about.

A good example would be a dungeon in an RPG game (or God of War or any other :-)). Rooms, or sets of rooms can be spatial cells. Corridors or other areas that connect sets of rooms can be the "conduit" that connects the spatial cells.
Or, the corridor can be a spatial cell as well but that introduces the problems you're referring to.

In the context of your design - spatial cells are completely separate. One cell can depict a space fight between ships near planet A, while another cell can depict an entirely different space battle.

Ships can't move easily from cell to cell. Maybe with special means such as warp travel. Maybe if the cells are relatively close and ships are allowed to move between them you take an entity from cell 1 and an entity from cell 2 and put them both in a temp cell (or not temp, depends) and they can both interact.

Its a very fluid system but don't think about them as adjacent cells in a grid because that is a simplification that doesn't necessarily work in every context.

Share this post


Link to post
Share on other sites
SiS-Shadowman    359
Thanks for the lengthy and detailed post :)

Quote:
Original post by voguemaster
Hi,

Regarding floating point usage - I guess the most prevalent reason for using floats is that its because of the hardware. CPUs were 32-bit for a long time now and floats (4 bytes) work really well with those registers, and the ST registers.

Now imagine the development of libraries such as DirectX and OpenGL at that time and its only natural that float would be the type everyone uses. Then middleware game engines are written using that tech and that dictates some of the requirements of the engine (but not always as some calculation spaces can happen with more than 32-bit, take for example 3D studio MAX's color space which should be 48-bit if I recall).

Now, floating point are very useful and easy to grasp, conceptually. The problems arise with implementations. The fact that round-off errors exist and the problem with accurately representing numbers that are far from the origin.

For most cases, floats work really well. Even in your example it would probably work well.


I was about to experiment with a fixed point implementation and that's when I grasped some of the problems that come with fixed point which are no problem at all when using a floating point format. There are pros and cons to both formats, but floating point seems to do a better job when nothing specific is known about the range of values that is needed.

Quote:

Think about a spatial cell as the immediate surroundings of a group of entities. You won't want to model a system of entities that interact with one another at a distance of 10,000 Km. If you need to render them and perform collision detection and physics stuff then they are VERY close to one another.

Are you going to display a "spatial cell" as we called it that contains entities at distances of 10,000 KM from one another ? What's the point ?


It's not displaying those units I'm worried about, but rather the transition between units. There's no point in rendering a space ship that is 10km away, maybe I'll visualize it as an icon. However your cell approach doesn't quite fit into my design of a totally seamless world.

Quote:

1. If the typical diameter of the volume all entities are in is ~10K Km, you need to scale everything down so 1.0f != 1m, but more likely 1.0f is around 1 Km (BTW, there are a LOT of floating point numbers between 0.0f and 1.0f so that is good in general).

2. If the view zooms in to view the action of several ships fighting, for example, the scale is much smaller of course as the diameter of the volume they occupy is maybe a few kilometers at most.


That's really useful information. I was never really sure which unit 1.0f should represent. I picked the SI unit since I feared a precision loss if it's more than that. However since about 7 decimals of precision are guaranteed, 1km doesn't seem that bad.

Quote:

Now, regarding one of the issues you've mentioned - the problem of spatial cells and how objects interact with them, I think you got me wrong.

You might be tempted to thinking in terms of an octree or quadtree but that's not what I was talking about.

A good example would be a dungeon in an RPG game (or God of War or any other :-)). Rooms, or sets of rooms can be spatial cells. Corridors or other areas that connect sets of rooms can be the "conduit" that connects the spatial cells.
Or, the corridor can be a spatial cell as well but that introduces the problems you're referring to.

In the context of your design - spatial cells are completely separate. One cell can depict a space fight between ships near planet A, while another cell can depict an entirely different space battle.

Ships can't move easily from cell to cell. Maybe with special means such as warp travel. Maybe if the cells are relatively close and ships are allowed to move between them you take an entity from cell 1 and an entity from cell 2 and put them both in a temp cell (or not temp, depends) and they can both interact.

Its a very fluid system but don't think about them as adjacent cells in a grid because that is a simplification that doesn't necessarily work in every context.


I totally got you wrong. I was thinking about an octree when I wrote that post before. The system you're proposing should work very well, since those cells are completely separate. They've been used in several games like the X series or Eve: Online. I've played the latter for some hours and they did a really nice job on the transition between those cells: It creates the illusion of not being constrained at all.
The X-Series didn't disguise their approach at all and those games are totally awesome. However a sector having a diameter of ~50km still makes me laugh.
Maybe I'm aiming for something different, but I want a completely seamless world where I'm not constrained by "sectors/cells/whatever".
From what I understood so far, I could achieve at with floating point precision. However the player must keep it's ships together so they "fit" inside one scene. Things that move outside this scene get unloaded and new stuff gets loaded, once it's near enough.

Share this post


Link to post
Share on other sites
PrestoChung    334
I have a question on this:

Does the choice of OpenGL affect whether fixed point is possible to implement?

In OpenGL for many glVertex3fv(float*) type functions there are equivalent integer versions glVertex3iv(int*). Does 'fixed point' mean you would be using these instead? Or filling VBOs with integers?

I ran into the problem with jittering when moving to large coordinates (I think it became noticeable around 400,000 units out in OpenGL units. To solve it I just recenter the origin every 128 units (arbitrary, will correspond to sectors in game) and increment/decrement a stored 'offset' index.

It was fine for rendering out to millions of units (drawing from closest to furthest with several clearings of the zBuffer). The render functions were in immediate mode though and I want to re-do it as retained mode.

Is this offset method bad for retained mode?

Could I switch to this 'fixed point' alternative?


Share this post


Link to post
Share on other sites
JohnnyCode    1046
For positioning your object in a large big space use your own vector.

Like a vector of [long,long,long,float,float,float].
You will use last three components in all 32 float instructions, and use all 6 in scaled alghrotihms of yours.
A [0,0,0,x,y,z] vectors would be classic 32 floating space, a sphere centered at 0.
You would make theese spheres overlap, such that, if two objects from large space are closer to eachother than C, then they are in a same space.
You will have to decide yet wheather it is a space of object A or of object B
that they both lie in.

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