Huge positions and strange behaviour

Discuss any questions about BEPUphysics or problems encountered.
Post Reply
kelthar
Posts: 13
Joined: Thu Nov 20, 2014 10:20 pm

Huge positions and strange behaviour

Post by kelthar »

I have a sphere that I'm pushing around a heightmap. When I get to position x/z 4000000 and up, I can't seem to push it in certain angles (135 degrees is one of them). Is it because I reach such a high position? I set the LinearVelocity for the speed and the sphere has it's TensorInverse set to Matrix.Zero.

Otherwise, thanks for a damn good physics engine.
Norbo
Site Admin
Posts: 4929
Joined: Tue Jul 04, 2006 4:45 am

Re: Huge positions and strange behaviour

Post by Norbo »

Is it because I reach such a high position?
Most likely, yup.

For a single precision float, the next value higher than 4000000 is 4000000.25. That means there would have to be a per frame displacement of over 0.125 units in order to jump to a new value. At 60hz, that would require a velocity of over 7.5 units per second. Anything less wouldn't change the value.

Handling extremely large spaces generally requires one of two things:
1) Keep the simulation somewhat near the origin. This could involve recentering the simulation over time, or having multiple simulations that have their own area of effect (with complicated transition behavior), or similar strategies. In one of my projects that has a large open world, I keep individual simulation sectors within a volume of around -10000 to 10000 along each axis, and do some complicated handoffs to manage transitions (which have to exist anyway due to its distributed nature). That size gives ~0.001 unit accuracy for positions in the worst case, which I've found to be totally sufficient for physical simulation.
2) Switch all the math (or just the positions) to higher precision representations like doubles or 64 bit fixed point. This will have a small performance impact in v1.4.0.

Given that it will be more painful to do #2 in BEPUphysics v2 due to the extensive planned use of SIMD, I would recommend doing something like #1 if possible.
JusTiCe8
Posts: 52
Joined: Mon Jun 01, 2015 9:02 am

Re: Huge positions and strange behaviour

Post by JusTiCe8 »

Hi Norbo,
Norbo wrote: 1) Keep the simulation somewhat near the origin. This could involve recentering the simulation over time, or having multiple simulations that have their own area of effect (with complicated transition behavior), or similar strategies. In one of my projects that has a large open world, I keep individual simulation sectors within a volume of around -10000 to 10000 along each axis, and do some complicated handoffs to manage transitions (which have to exist anyway due to its distributed nature).
Funny you talk about this way as I saw this old thread, and could you give a working example (as another "hidden" demo maybe, like the reverse trike or solid pyramid) of it please ?

I've also meet the "deadly" limit of float type with one of my project (weird behavior the first time: position didn't increase as fast as before over 100000 units, speed need to be higher to move the object, then it only increase by 10 units at a time) and I'm really interested to see how to address this as most efficiently and cleanly as possible as I haven't figured out yet how to deal with spaces transition and position management.
Example on a vertical stack of spaces (ex: 5: 0-50000, 50001-100000, ...) how an object can be considered to be 50000 units high then 50001 on the new space ?

Maybe I would need two values: actual position and local position, so at 75000 units altitude, it would be AP=75000.00, LP=24999.00, with AP a double (or even an array/struct of doubles to keep the position really precisely for huge distance, like in space), and set up new spaces with global values (ex: AP as altitude to use to compute current gravity).

Maybe a 2x2x2 or 3x3x3 grid of spaces with a working transition between them using either player location of camera location as reference would be great, with also how to put entities to sleep and how to wake them up when needed.

Thanks.
Norbo
Site Admin
Posts: 4929
Joined: Tue Jul 04, 2006 4:45 am

Re: Huge positions and strange behaviour

Post by Norbo »

Maybe I would need two values: actual position and local position, so at 75000 units altitude, it would be AP=75000.00, LP=24999.00, with AP a double (or even an array/struct of doubles to keep the position really precisely for huge distance, like in space), and set up new spaces with global values (ex: AP as altitude to use to compute current gravity).
Something like this could work. One of the simplest options is to give each simulation sector a spatial index, like (0,3,1) would be the 3 sectors up along Y and 1 along Z. If you know each sector is exactly 20000 units across, then you know the exact position of the sector in 'global' space even if it can't be represented in a float. All objects within that sector's space would be handled in terms of sector-local coordinates.

This also lets you avoid continuous tracking of global position on a per-object basis when it's not needed. For example, transitions don't need global positions- it can all be handled through local coordinates of the two adjacent sectors. General simulation doesn't care about global positions, either. Things like gravity could benefit from a global position, but you can compute that on demand.

If you used 32 bit integers for spatial indices, that would give you a 'global' space 85 trillion units across. For comparison, if a unit is a meter, that's 110,000 times further than jupiter from the sun. And you could always use 64 bit integers instead :P

The really hard part is doing the transitions well, since physical objects can't belong to two different simulations at once. The most common solution is for a sector to maintain 'authority' over a set of objects which is managed by heuristics. A sector can be authoritative over things which aren't exactly the set of objects inside the sector's volume (e.g. a character briefly walked across the edge). For a near-border object, the adjacent sector maintains a proxy that follows the physical state of the authoritative simulation. So, if an object under the authority of sector X collides with an object under the authority of sector Y, something-not-entirely-unreasonable will happen because both can see each other's proxies. However, it's best to avoid that sort of thing. The authority heuristics choose when to move an object from one sector's authority to another, and part of their logic includes 'is this thing probably going to interact with objects of a different authority'.

However, keep in mind that maintaining more than one of these sectors is only necessary if the simulation continues when the player isn't nearby. For truly enormous worlds (e.g. infinite procedural universes), simulating everything is just impossible, so there's not much point in going through the effort of handling transitions between different spaces.

Instead, the simulation could just be periodically recentered. When the player wanders too far out from the space's current origin, everything in the space just teleports to keep the player in the center. Remove anything which is too far away to matter after the teleport. No transitions between spaces or anything complicated.

As for an example, I may create one... someday. I wouldn't wait on it, though :) If I did make one, it would probably be of the much simpler recentering-without-transitions. The persistent-sectors-with-transitions version is quite a bit more complicated and the implementation is best game-specific. (My implementation, for example, is tied strongly into the distributed networking model and wouldn't easily compress down to a demo.)
kelthar
Posts: 13
Joined: Thu Nov 20, 2014 10:20 pm

Re: Huge positions and strange behaviour

Post by kelthar »

This is all very interesting! =)

I already recenter my meshes, as I found out what those high positions do with the depth buffer. So I figured I ran into something which is similar.
I have a pretty big world. I estimated that it takes about 750 real years to go from one end to the other.

Anyways. I'll do as you say, I'll simulate an area for each player. Not sure how big. Maybe 2000-4000 units. And when two players meet, I'll join them into a bigger one. That, however, might introduce problems when there are enough players spaced over more than 10000 units. Your solution seems very complicated and I'm very lazy. Maybe it'll be good enough. The areas could dynamically adapt and split to envelop the players with a sufficient border around them. That way, it's only the non-playing entities that will suffer strange behaviour. And they can't complain, can they?

When you say recenter, you mean modify the position of each entity in the simulation?
Norbo
Site Admin
Posts: 4929
Joined: Tue Jul 04, 2006 4:45 am

Re: Huge positions and strange behaviour

Post by Norbo »

Anyways. I'll do as you say, I'll simulate an area for each player. Not sure how big. Maybe 2000-4000 units. And when two players meet, I'll join them into a bigger one. That, however, might introduce problems when there are enough players spaced over more than 10000 units. Your solution seems very complicated and I'm very lazy. Maybe it'll be good enough. The areas could dynamically adapt and split to envelop the players with a sufficient border around them. That way, it's only the non-playing entities that will suffer strange behaviour. And they can't complain, can they?
I suspect that'll work fine. That sort of approach only really hits issues when people actively try to break it, and it would take a lot of dedicated people (probably hundreds) to create a situation with unavoidable noticeable issues for human players.
When you say recenter, you mean modify the position of each entity in the simulation?
Yup. And anything else with a transform, like StaticMeshes.
kelthar
Posts: 13
Joined: Thu Nov 20, 2014 10:20 pm

Re: Huge positions and strange behaviour

Post by kelthar »

Been thinking about this and I have three scenarios:

1. Put all entities into the same Space, but group them so they only collide with entities within the same "simulated area". Let this simulation work over multiple threads. Let's say one thread for each core available. When merging groups, change all positions so they fit into their new center.
2. Create a Space for each simulated area. Transfer entities, merge and split Spaces depending on proximity. Distribute the Space:s evenly over available cores.
3. Create a Space for each simulated area. Duplicate entities when they are shared over multiple Spaces. Distribute the Space:s evenly over available cores.

Which would be most performant? Is there any obvious caveats/problems/weaknesses with the different solutions?
The first scenario reduces the cost of moving entites back and forth between Spaces and is of course a lot easier to implement. I'm leaning towards it.

Scenario 3 is also easy to implement, but the amount of data it has to handle might be enormous. In one of these "sumilated areas", there will be about 1000-2000 static entities and 50-200 moving, not counting projectiles. I don't think it's viable at all.

Is there a lot of overhead when creating or disposing Spaces?
Norbo
Site Admin
Posts: 4929
Joined: Tue Jul 04, 2006 4:45 am

Re: Huge positions and strange behaviour

Post by Norbo »

1. Put all entities into the same Space, but group them so they only collide with entities within the same "simulated area". Let this simulation work over multiple threads. Let's say one thread for each core available. When merging groups, change all positions so they fit into their new center.
The broad phase won't know that these sets of objects can't actually collide until the end of a full traversal, so keeping everything in one space will add a lot of time to the broad phase. It may still be fast enough, though.
2. Create a Space for each simulated area. Transfer entities, merge and split Spaces depending on proximity. Distribute the Space:s evenly over available cores.
The heuristic used to split spaces in the worst case will be the trickiest part, since a pathological configuration may require a space boundary to end up uncomfortably close to a player. But other than that, this is a good solution if you don't care too much about the occasional weird behavior at the border.
3. Create a Space for each simulated area. Duplicate entities when they are shared over multiple Spaces. Distribute the Space:s evenly over available cores.
This gets into some authority-related difficulty. Since the two simulations can easily diverge, dynamic duplicates will need to be kept in sync. Depending on the desired degree of simulation quality, making this work could be difficult. Performance wise, I suspect it would still be okay in most cases. Note that static objects would not need to be duplicated- only anything that can potentially move.

In terms of simulation execution time, I would suspect that in the average case, 2 is faster than 3 is faster than 1.

As far as bookkeeping work, 2 will occasionally cause a framespike on split and merge. This could be mitigated by limiting the work per frame- if multiple splits or merges should occur, just do one per frame until done rather than all at once. Further, grouping static objects into StaticGroups will help both the broadphase times and bookkeeping times (since less objects need to be added/removed from spaces).

If occasional border weirdness is okay and you expect simulation performance to be a bottleneck, option 2 seems to be the best.
Is there a lot of overhead when creating or disposing Spaces?
The space object itself, no. Pretty much all the cost is in adding/removing stuff.
kelthar
Posts: 13
Joined: Thu Nov 20, 2014 10:20 pm

Re: Huge positions and strange behaviour

Post by kelthar »

I forgot to thank you for your replies. Very good stuff.

Now, a lot later, I realize that I could just change the position scale aswell to complement the system. Divide all positions by 1E20 or some other and still have enough precision probably. I wonder why I didn't think of this earlier. Do you think 1E20 is too much or do I have some headroom there. I think the minimum velocities used today are around 1f / second. Without being scaled down by 1E20. How does this affect other things like friction and such. Nothing at all?
Norbo
Site Admin
Posts: 4929
Joined: Tue Jul 04, 2006 4:45 am

Re: Huge positions and strange behaviour

Post by Norbo »

Keeping everything as single precision float values and scaling down wouldn't address the problem, unfortunately. At any scale, a single precision float only has about 7 decimal digits of precision. So you could do 1e-7f + 1 and get 1.00000012, or 1e-27f + 1e-20f and get 1.00000005e-20f, but adding 1e-27f to 1 gets you 1.

Scaling down would also require all the tuning constants to be adjusted with something like the demos ConfigurationHelper.ApplyScale.
kelthar
Posts: 13
Joined: Thu Nov 20, 2014 10:20 pm

Re: Huge positions and strange behaviour

Post by kelthar »

No, it doesn't remove the problem, it just extends my possible maximum simulation area, which is nice.
JusTiCe8
Posts: 52
Joined: Mon Jun 01, 2015 9:02 am

Re: Huge positions and strange behaviour

Post by JusTiCe8 »

I come back here as I'm in for now :roll: .

The thing that's bothers me right now is using "tiled-space" (space in its most general meaning, not a BEPU space) is just how to display it ! That's sounds obvious but:

there is two ways to do it, origin "space" centered at (0,0,0), so it's overlap the display space (usual things we use to display object on screen, whatever it is: DX, OpenGL, ...), stay in this origin space (think of a game like Far Cry, where we start usually easy missions near the starting location/safe house before going further away).
Display object in the origin is easy, coordinates are the same, + tiles coordinates are T(0,0,0) with T the triplet similar to the usual X,Y,Z coordinates, but for the tiled spaces.

Another choice is to arrange tiled spaces from 0,0,0 to SS, SS, SS for the first, 2* SS, 2* SS, 2* SS the 2nd, etc in all three direction, with SS=space size (10000 for example to be safe from floating point precision issue, this allow cm precision, quite enough). This one is easy for managed tiled space as a 3D array, 3D world origin is the "top right" corner of the first cell (discarding Y component). The same way to display a 2D grid on screen for example (chess/checker game).

Then, comes the main challenge: how to display objects in tile (Tx,Ty,Tz) on screen ? Especially, how to manage transition from tile N to tile N+1 (example origin to only T(1,0,0)), as 3D world coordinates will be (SS-1, whatever, whatever) then ? :?: (with the 10000 tile size it will be 9999-10000[boundary ]- -9999 ? but -9999 where ?
I guess we have to made something like a shift coordinates pass for one frame, we start back at 3D world origin.

I need to figure it out before moving on I guess.

To get back to BEPU itself, my own needs will be pretty kind with it as I won't need thousands of objects and a lot of potential collisions at boundaries to manage and it may be manageable the same way as display itself.

The "center physics space on the player" also bugs me a bit, because other entities velocities have to be "shifted" too (a thing moving away will in fact move at player.speed - thing.speed), but does this affect collision solving ? As collision calculations may not give the same result from two mobile objects colliding, like pool balls, and one moving and colliding another which doesn't move (does momentum and/or kinetic energy calculations differ ?)

Thanks.

Useful links:
- dungeon siege design paper
- a talk on the subject
Norbo
Site Admin
Posts: 4929
Joined: Tue Jul 04, 2006 4:45 am

Re: Huge positions and strange behaviour

Post by Norbo »

As far as display goes, conceptually consider the objects in a tile/chunk to have positions relative to the tile. The tile has its own high precision absolute world space position. The camera moves through tiles incrementally, so at any time, you can get an high precision absolute world space position of the camera. You can then compute the offset in high precision world space coordinates. Since the offset will be a small value anywhere near the camera, it can be converted to a regular single precision offset relative to the camera for rendering. That can be used to compute the relative rendering positions for the objects within the tile.

An implementation doesn't have to follow the above steps exactly, but the implementation should end up being equivalent in concept.
The "center physics space on the player" also bugs me a bit, because other entities velocities have to be "shifted" too
There's no need to modify the velocities of physics objects as the character moves around. Doing that would imply a reference frame in which the character has zero velocity at all times and the universe moves instead- that would be very annoying to implement. Just periodically shifting their positions to keep the area of interest within a numerically-good volume is sufficient.
JusTiCe8
Posts: 52
Joined: Mon Jun 01, 2015 9:02 am

Re: Huge positions and strange behaviour

Post by JusTiCe8 »

Just for the record and also for anyone willing to make a huge world (not related to BEPU at all for now), this is what I found.
As I'm just a beginner in this field, I may be wrong, so to anyone, don't hesitate to fix any mistake or wrong statement :).

The big "mind leap" is to figure out 3D world is ONLY seen through the lens(es) of the camera(s), so the only thing really matter is distance between the camera and the objects, no matter how these objects and camera(s) are located relative to the world origin. And it may be very close to the classic 2D big world trick of the scrolling (which I didn't really get trough it, unfortunately, I'm sure it would have been a good stuff to learn).

Basically, objects and camera coordinates are expressed relative to the "absolute" world origin: (0,0,0), so for example camera is at (10,50,-20) and the player is at (10,40,10) (for a camera following "behind" and above).
When player moves, it goes farer to the origin, farer, farer, like (10, 40, 1000) then (10, 40, 6000) ... but why keeping using absolute world coordinates so far away ?
The game don't care at all about everything located maybe 1000 units away from the player on Z axis (even less), so the idea is to have two sets of coordinates: absolute and relative.

Absolutes coords. will not be expressed as relative ones, as it doesn't help (FP precision issue will be there too), instead, they are expressed in "tile" coordinates.
For a tile size defined at TxTxT (which can be different values or equals, depending of the game needs), these coords will be like (0, 0, 0) for the 1st player coordinates above, then something like (0, 0, 6) for T=1000.

Inside this 1000 units wide "cube", relative coordinates could be (10, 50, 0) as world z=6000 = tile z=0
With Tiles coordinates inside [ -500, +500 ] interval, 6000 is in the 6th tiles on the Z axis (0=-500,500 1=500,1500 2=1500,2500 3=2500,3500 4=3500,4500 5=4500,5500 6=5500 6500), at the relative origin.
(In order to simplify, one unit is always duplicated, it should be more strictly [ -500, 500 ] [ 501, 1501 ] [ 1502, 2502 ] ...)

The camera will be at (10,40,-20). So both player & camera can be rendered in the world space with coordinates that does not suffer from FP precision issue.
With the tile coordinates, it is easy to calculate distance, for example ETA to a destination, as distance = tile coord difference * tilesize + relative coordinates difference .
Without forgetting tiles are centered on origin, so distances are -500,500 making all remaining coordinates inside a tile expressed minus 500.

Example:
player at (0, 0, 50) willing to go to (1578, 50, 89658), full coords are P( t(0,0,0) 0, 0, 50 ) Dest( t(2, 0, 90) -422, 50, -342) (the game will only know the last two sets)
422 = -500 + 178
342 = -500 + 158
tile 90 on Z because tile N hold absolute coords ( N * 1000 - 500, N * 1000 + 500) => tile 89 stand for [ 88500, 89500 ], tile 90 for [ 89500, 90500 ]
2 on X because Tile 0 = [ -500, 500 ] 1 = [ 500, 1500 ] 2 = [ 1500, 2500 ], with each tile always centered on world origin

The key point to remember is display doesn't care about physics at all, object have coordinates, period. They can moves accurately or more in an alleged UFO style, violating any or all of the Newton's laws. And it doesn't matter if they are near origin or 10^22 units away or even farer than that. But screen/camera cannot dsplay everything and anything that's not visible is not drawn for performance reason.

There is only the boundaries issues which need to be fully handled to avoid some issues (like camera in the "opposite side" of the tile, especially when direct conversion from game coordinates to world coordinates occurred, like on respawn or teleportation).

A similar concept could be use for BEPU Space itself, re-centering the space, using an array of spaces or anything that make your game as you need it to be. This will be the topic of another post ;).
Post Reply