I've been working on my replay code, in which the physics object is set to an older position, and a history of its update information is used as the world steps forward.
I'm noticing however that doing an identical world step twice can result in very different results. I know most physics engines are not deterministic, but what in the engine would cause an object to not perform the same each time when the same input parameters (velocity, acceleration etc.) are inputted?
Determinism?
Re: Determinism?
The most obvious one is multithreading. The multithreaded solver does not use deterministic batching; the solving order will vary based on how fast the threads progress.
However, even without any multithreading, there are lots of possible sources of nondeterminism. Most arise from the massive amount of state that persists from frame to frame. Here's a few in no particular order:
1) Batched deactivation. Only a subset of all deactivation candidates are processed each frame. If the bookkeeping isn't totally reinitialized, objects could go to sleep at different times.
2) Space object Add/remove order. Different input orders will change the pair generation order of the BroadPhase. Different pair orders will result in different solving orders. This will also affect continuous collision detection.
3) Cached data. Related to #2, simply moving objects and velocities back to an earlier frame will not produce the same order of collision pairs of that earlier frame. This is because there's already a set of persistent collision pairs; some collision pairs will already exist, while others will be added or removed.
4) Solver permutation generator. If the seed is different (Space.Solver.PermutationIndex), the solving order will be different.
5) Different processors. Not all floating point implementations will result in bitwise identical results.
I'm probably missing some others. Some of these can be dealt with pretty easily (solver permutations), but fully addressing pair orders and everything else is a huge pain. If determinism is required across different processors, you're practically stuck with fixed point math (or a software implementation of floating point numbers...). Even if a hardware floating point implementation coincidentally happened to be deterministic across two different architectures, the JIT could decide to pull the rug out from under you later.
To avoid that big mess, I usually just recommend keyframe/recording based approaches with nonsimulated animation-style playback.
However, even without any multithreading, there are lots of possible sources of nondeterminism. Most arise from the massive amount of state that persists from frame to frame. Here's a few in no particular order:
1) Batched deactivation. Only a subset of all deactivation candidates are processed each frame. If the bookkeeping isn't totally reinitialized, objects could go to sleep at different times.
2) Space object Add/remove order. Different input orders will change the pair generation order of the BroadPhase. Different pair orders will result in different solving orders. This will also affect continuous collision detection.
3) Cached data. Related to #2, simply moving objects and velocities back to an earlier frame will not produce the same order of collision pairs of that earlier frame. This is because there's already a set of persistent collision pairs; some collision pairs will already exist, while others will be added or removed.
4) Solver permutation generator. If the seed is different (Space.Solver.PermutationIndex), the solving order will be different.
5) Different processors. Not all floating point implementations will result in bitwise identical results.
I'm probably missing some others. Some of these can be dealt with pretty easily (solver permutations), but fully addressing pair orders and everything else is a huge pain. If determinism is required across different processors, you're practically stuck with fixed point math (or a software implementation of floating point numbers...). Even if a hardware floating point implementation coincidentally happened to be deterministic across two different architectures, the JIT could decide to pull the rug out from under you later.
To avoid that big mess, I usually just recommend keyframe/recording based approaches with nonsimulated animation-style playback.
-
- Posts: 249
- Joined: Wed Nov 17, 2010 1:49 pm
Re: Determinism?
This is interesting.
I'm looking to make BEPU as deterministic as possible by changing available properties.
How often do I have to set the PermutationIndex? Once per physics update when the solver starts?
Oddly enough if I set it to 1 during initialisation then to 1 each time the Solver_Starting method is called the value accumulates and becomes 2?
Besides the Space.Solver.PermutationIndex, is there anything else I can alter?
I'm looking to make BEPU as deterministic as possible by changing available properties.
How often do I have to set the PermutationIndex? Once per physics update when the solver starts?
Code: Select all
space.Solver.Starting += new Action(Solver_Starting);
Besides the Space.Solver.PermutationIndex, is there anything else I can alter?
Re: Determinism?
One time at initialization. From then on, it will increment itself each frame deterministically.How often do I have to set the PermutationIndex? Once per physics update when the solver starts?
The stuff in my previous post pretty much covers it. I'm not sure you'll see any significant benefit from partially eliminating sources of nondeterminism. Each of the causes in isolation could potentially result in basically complete nondeterminism.Besides the Space.Solver.PermutationIndex, is there anything else I can alter?
If you aren't already using it, I would recommend switching to the latest dependency free version. I fixed a bug a little while back which was introducing extra unnecessary nondeterminism and generally bad behavior.
-
- Posts: 249
- Joined: Wed Nov 17, 2010 1:49 pm
Re: Determinism?
The default value is 0, how does specifically setting it to 0 during initialisation ensure a deterministic simulation?One time at initialization. From then on, it will increment itself each frame deterministically.
Using the dependency free version will require determining the source of all instances of such as Vector3, Matrix and other XNA classes.
If I use:
Code: Select all
using Vector3 = BEPUutilities.Vector3;
Likewise:
Code: Select all
using Vector3 = Microsoft.Xna.Framework.Vector3;
How would you suggest handling this?
Re: Determinism?
It only helps when the simulation is restarting from some other point- like replaying a subset of the simulation. Setting it to the matching value at the start of that replay matters since the replay doesn't necessarily begin at space initialization.The default value is 0, how does specifically setting it to 0 during initialisation ensure a deterministic simulation?
A common low-effort approach is to put some implicit casts in the BEPUutilities math types. Another option is to use explicit conversion functions like the MathConverter in the BEPUphysicsDemos.How would you suggest handling this?
In my projects, I just use the BEPUutilities math everywhere, all the way down to GPU buffer interaction. This might not work for everyone, but it keeps everything pretty clean.
-
- Posts: 249
- Joined: Wed Nov 17, 2010 1:49 pm
Re: Determinism?
Thanks for the advice Norbo, I'll use casting for the time being.
Is there anything wrong with setting the PermutationIndex to 1 each time the solver starts? I have a loop that remains deterministic when doing this but does not if I only set it during initialisation.
Is there anything wrong with setting the PermutationIndex to 1 each time the solver starts? I have a loop that remains deterministic when doing this but does not if I only set it during initialisation.
Re: Determinism?
Solver quality will suffer slightly compared to the optimal case of setting the permutation index to the appropriate value at the appropriate time. Rotating the permutation helps avoid behavior issues in corner cases where the solver order could otherwise line up in a pathologically bad way. The difference may be too small to worry about.Is there anything wrong with setting the PermutationIndex to 1 each time the solver starts? I have a loop that remains deterministic when doing this but does not if I only set it during initialisation.
-
- Posts: 249
- Joined: Wed Nov 17, 2010 1:49 pm
Re: Determinism?
Excellent. I believe it is worth doing in this case.
Thanks again.
Thanks again.