Determinism?

Discuss any questions about BEPUphysics or problems encountered.
Post Reply
vendetta
Posts: 18
Joined: Sat Dec 31, 2011 7:49 pm

Determinism?

Post by vendetta »

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?
Norbo
Site Admin
Posts: 4929
Joined: Tue Jul 04, 2006 4:45 am

Re: Determinism?

Post by Norbo »

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. :)
Spankenstein
Posts: 249
Joined: Wed Nov 17, 2010 1:49 pm

Re: Determinism?

Post by Spankenstein »

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?

Code: Select all

space.Solver.Starting += new Action(Solver_Starting);
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?
Norbo
Site Admin
Posts: 4929
Joined: Tue Jul 04, 2006 4:45 am

Re: Determinism?

Post by Norbo »

How often do I have to set the PermutationIndex? Once per physics update when the solver starts?
One time at initialization. From then on, it will increment itself each frame deterministically.
Besides the Space.Solver.PermutationIndex, is there anything else I can alter?
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.

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.
Spankenstein
Posts: 249
Joined: Wed Nov 17, 2010 1:49 pm

Re: Determinism?

Post by Spankenstein »

One time at initialization. From then on, it will increment itself each frame deterministically.
The default value is 0, how does specifically setting it to 0 during initialisation ensure a deterministic simulation?

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;
then XNA classes complain.

Likewise:

Code: Select all

using Vector3 = Microsoft.Xna.Framework.Vector3;
will cause BEPU to complain.

How would you suggest handling this?
Norbo
Site Admin
Posts: 4929
Joined: Tue Jul 04, 2006 4:45 am

Re: Determinism?

Post by Norbo »

The default value is 0, how does specifically setting it to 0 during initialisation ensure a deterministic simulation?
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.
How would you suggest handling this?
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.

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.
Spankenstein
Posts: 249
Joined: Wed Nov 17, 2010 1:49 pm

Re: Determinism?

Post by Spankenstein »

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.
Norbo
Site Admin
Posts: 4929
Joined: Tue Jul 04, 2006 4:45 am

Re: Determinism?

Post by Norbo »

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.
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.
Spankenstein
Posts: 249
Joined: Wed Nov 17, 2010 1:49 pm

Re: Determinism?

Post by Spankenstein »

Excellent. I believe it is worth doing in this case.

Thanks again. :)
Post Reply