Object only follows the same path from second iteration?

Discuss any questions about BEPUphysics or problems encountered.
Post Reply
Spankenstein
Posts: 249
Joined: Wed Nov 17, 2010 1:49 pm

Object only follows the same path from second iteration?

Post by Spankenstein »

I have created a scenario that drops a yellow ball from a specific location. The ball will reset to that same location once it comes into contact with a green box.

On the first iteration the yellow ball follows a path that is different to all the subsequent iterations, which all follow the same path.

The entity is reset each time it touches the green box by setting the following properties:

position = (0, 10, 0)
orientation = (0,0,0)
angularvelocity = (0,0,0)
linearvelocity = (0,0,0)

I have checked the first frame of each iteration and the properties of the entity are always identical. The permutation index is always the same for each iteration also.

Why would the first iteration not follow the same path as the subsequent ones?

I have uploaded a video to demonstrate this problem: http://youtu.be/2NlBYLdd8Ak
Norbo
Site Admin
Posts: 4929
Joined: Tue Jul 04, 2006 4:45 am

Re: Object only follows the same path from second iteration?

Post by Norbo »

Since there's only ever one collision at any time, things like the permutation index and multithreading shouldn't interfere. Pretty much all nondeterminism comes from the order in which stuff gets updated, so I'm not sure why this would happen with just one object. While I have some theories, they fail to predict subsequent iterations being identical.

Could you reproduce it in the BEPUphysicsDemos for me to look at?
Spankenstein
Posts: 249
Joined: Wed Nov 17, 2010 1:49 pm

Re: Object only follows the same path from second iteration?

Post by Spankenstein »

Sure. I'll get something together over the weekend and post it here.
Spankenstein
Posts: 249
Joined: Wed Nov 17, 2010 1:49 pm

Re: Object only follows the same path from second iteration?

Post by Spankenstein »

So far so good. Will need to delve further:

Code: Select all

    public class IterationProblemDemo : StandardDemo
    {
        Sphere ball;
        Vector3 ballStartingPosition = new Vector3(0.1f, 10.5f, 0f);

        public IterationProblemDemo(DemosGame game)
            : base(game)
        {
            BEPUphysics.Settings.CollisionDetectionSettings.DefaultMargin = 0.04f;
            
            BEPUphysics.Settings.CollisionResponseSettings.BouncinessVelocityThreshold = 1f;
            BEPUphysics.Settings.CollisionResponseSettings.MaximumPenetrationRecoverySpeed = 10f;
            BEPUphysics.Settings.CollisionResponseSettings.PenetrationRecoveryStiffness = 0.2f;

            BEPUphysics.Settings.MotionSettings.CoreShapeScaling = 0.99f;

            Space.ForceUpdater.Gravity = new BEPUutilities.Vector3(0f, -20f, 0f);
            Space.TimeStepSettings.TimeStepDuration = 1f / 60f;
            Space.BufferedStates.Enabled = false;
            Space.Solver.IterationLimit = 20;

            game.Camera.Position = new Vector3(5, 0, 30);
            game.Camera.ViewDirection = new Vector3(0, 0, -1);

            for (int x = -9; x <= 9; x += 3)
            {
                for (int y = -9; y <= 9; y += 3)
                {
                    var peg = new Cylinder(new Vector3(x, y, 0), 1f, 0.5f);               
                    peg.Orientation = Quaternion.CreateFromYawPitchRoll(MathHelper.PiOver2, 0, 0);
                    peg.Material.Bounciness = 0.828f;
                    Space.Add(peg);
                }
            }

            ball = new Sphere(ballStartingPosition, 0.5f, 1f);
            ball.Material.Bounciness = 0.828f;
            Space.Add(ball);
        }

        public override void Update(float dt)
        {
            if (ball.Position.Y < -22f)
            {
                ball.AngularVelocity = Vector3.Zero;
                ball.LinearVelocity = Vector3.Zero;
                ball.Orientation = Quaternion.Identity;
                ball.Position = ballStartingPosition;
            }

            base.Update(dt);
        }

        public override string Name
        {
            get { return "Iteration Problem"; }
        }
    }
Spankenstein
Posts: 249
Joined: Wed Nov 17, 2010 1:49 pm

Re: Object only follows the same path from second iteration?

Post by Spankenstein »

Replacing the sphere with a capsule demonstrates non-repeatable iterations:

Code: Select all

    public class IterationProblemDemo : StandardDemo
    {
        Capsule capsule;
        Vector3 ballStartingPosition = new Vector3(0.1f, 11.5f, 0f);

        public IterationProblemDemo(DemosGame game)
            : base(game)
        {
            BEPUphysics.Settings.CollisionDetectionSettings.DefaultMargin = 0.04f;
            
            BEPUphysics.Settings.CollisionResponseSettings.BouncinessVelocityThreshold = 1f;
            BEPUphysics.Settings.CollisionResponseSettings.MaximumPenetrationRecoverySpeed = 10f;
            BEPUphysics.Settings.CollisionResponseSettings.PenetrationRecoveryStiffness = 0.2f;

            BEPUphysics.Settings.MotionSettings.CoreShapeScaling = 0.99f;

            Space.ForceUpdater.Gravity = new BEPUutilities.Vector3(0f, -20f, 0f);
            Space.TimeStepSettings.TimeStepDuration = 1f / 60f;
            Space.BufferedStates.Enabled = false;
            Space.Solver.IterationLimit = 20;

            game.Camera.Position = new Vector3(5, 0, 30);
            game.Camera.ViewDirection = new Vector3(0, 0, -1);

            for (int x = -9; x <= 9; x += 3)
            {
                for (int y = -9; y <= 9; y += 3)
                {
                    var peg = new Cylinder(new Vector3(x, y, 0), 1f, 0.5f);               
                    peg.Orientation = Quaternion.CreateFromYawPitchRoll(MathHelper.PiOver2, 0, 0);
                    peg.Material.Bounciness = 0.828f;
                    Space.Add(peg);
                }
            }

            capsule = new Capsule(ballStartingPosition, 1f, 0.5f, 1f);
            capsule.Material.Bounciness = 0.828f;
            Space.Add(capsule);
        }

        public override void Update(float dt)
        {
            if (capsule.Position.Y < -22f)
            {
                capsule.AngularVelocity = Vector3.Zero;
                capsule.LinearVelocity = Vector3.Zero;
                capsule.Orientation = Quaternion.Identity;
                capsule.Position = ballStartingPosition;
            }

            base.Update(dt);
        }

        public override string Name
        {
            get { return "Iteration Problem"; }
        }
    }
How can this be made deterministic?
Norbo
Site Admin
Posts: 4929
Joined: Tue Jul 04, 2006 4:45 am

Re: Object only follows the same path from second iteration?

Post by Norbo »

How can this be made deterministic?
It looks like (at least part of) the issue is that the broad phase isn't being reset fully. It uses a temporally coherent algorithm, so the previous frame influences how the current frame's broad phase is built. Unfortunately, this can mean a collision pair is generated in a different order- that is, collidables A and B are swapped.

In collision detection, that difference in order can cause extremely small numerical differences. This is visible in the capsule's behavior, but it actually affects the sphere, too. The capsule just magnifies the effect due to its shape and more chaotic rotational behavior.

Here's two runs with a sphere:

Code: Select all

Frame 60: {0.8438894, 9.768148, -2.930157E-07}
Frame 120: {0.9153587, 7.004002, -9.766839E-07}
Frame 180: {1.166141, -0.6381797, -1.793709E-06}
Frame 240: {-3.461467, -2.013655, -3.395803E-06}
Frame 300: {-4.945804, -3.165692, -4.950115E-06}
Frame 360: {-3.452583, -20.23316, -6.366693E-06}
______
Frame 60: {0.8438894, 9.768148, -2.930157E-07}
Frame 120: {0.9153587, 7.004002, -9.766839E-07}
Frame 180: {1.166141, -0.6381797, -1.705321E-06}
Frame 240: {-3.461468, -2.013655, -3.310864E-06}
Frame 300: {-4.945806, -3.165688, -5.269535E-06}
Frame 360: {-3.452558, -20.23312, -7.225222E-06}
Here's four runs with the capsule:

Code: Select all

Frame 60: {0.649253, 10.35287, -2.569535E-06}
Frame 120: {1.902411, 6.274374, -3.512889E-05}
Frame 180: {1.959954, 0.8124294, 0.0007307164}
Frame 240: {1.457408, -5.673208, 0.002140395}
Frame 300: {1.184698, -10.45159, 0.002349531}
______
Frame 60: {0.649253, 10.35287, -2.569535E-06}
Frame 120: {1.902413, 6.274392, -3.698204E-05}
Frame 180: {2.012538, 0.7155204, -5.153625E-06}
Frame 240: {1.324261, -5.094629, -0.0008429385}
Frame 300: {0.8184211, -14.33493, -0.002961804}
______
Frame 60: {0.649253, 10.35287, -2.569535E-06}
Frame 120: {1.902413, 6.274392, -3.698204E-05}
Frame 180: {2.012538, 0.7155204, -5.153625E-06}
Frame 240: {1.324261, -5.094629, -0.0008429385}
Frame 300: {0.8184211, -14.33493, -0.002961804}
______
Frame 60: {0.649253, 10.35287, -2.569535E-06}
Frame 120: {1.902413, 6.274392, -3.513639E-05}
Frame 180: {1.956183, 0.8201287, 0.0007421858}
Frame 240: {1.569756, -5.83865, 0.001030846}
Frame 300: {3.530511, -14.99275, 0.001144263}
The two middle runs actually happen to be identical, courtesy of the pair orders lining up by chance.

To fully eliminate this sort of problem, the space should basically be reconstructed from scratch on each iteration. All elements must be inserted in exactly the same order as they were originally. Assuming multithreading is off, that should produce a deterministic result.

Indeed, if the space is created and recreated using this function in the given demo:

Code: Select all

        private void CreateSpace()
        {
            Space = new BEPUphysics.Space();
            Space.Solver.PermutationMapper.PermutationIndex = 0;
            BEPUphysics.Settings.CollisionDetectionSettings.DefaultMargin = 0.04f;

            BEPUphysics.Settings.CollisionResponseSettings.BouncinessVelocityThreshold = 1f;
            BEPUphysics.Settings.CollisionResponseSettings.MaximumPenetrationRecoverySpeed = 10f;
            BEPUphysics.Settings.CollisionResponseSettings.PenetrationRecoveryStiffness = 0.2f;

            BEPUphysics.Settings.MotionSettings.CoreShapeScaling = 0.99f;

            Space.ForceUpdater.Gravity = new Vector3(0f, -20f, 0f);
            Space.TimeStepSettings.TimeStepDuration = 1f / 60f;
            Space.BufferedStates.Enabled = false;
            Space.Solver.IterationLimit = 20;

            for (int x = -9; x <= 9; x += 3)
            {
                for (int y = -9; y <= 9; y += 3)
                {
                    var peg = new Cylinder(new Vector3(x, y, 0), 1f, 0.5f);
                    peg.Orientation = Quaternion.CreateFromYawPitchRoll(MathHelper.PiOver2, 0, 0);
                    peg.Material.Bounciness = 0.828f;
                    Space.Add(peg);
                }
            }

            entity = new Capsule(ballStartingPosition, 1, 0.5f, 1f);
            //entity = new Sphere(ballStartingPosition, 0.5f, 1f);
            entity.Material.Bounciness = 0.828f;
            Space.Add(entity);
        }
The simulation becomes fully deterministic:

Code: Select all

Frame 60: {0.649253, 10.35287, -2.569535E-06}
Frame 120: {1.902411, 6.274374, -3.512889E-05}
Frame 180: {1.959954, 0.8124294, 0.0007307049}
Frame 240: {1.457395, -5.673295, 0.00213943}
Frame 300: {1.191184, -10.46338, 0.002350604}
______
Frame 60: {0.649253, 10.35287, -2.569535E-06}
Frame 120: {1.902411, 6.274374, -3.512889E-05}
Frame 180: {1.959954, 0.8124294, 0.0007307049}
Frame 240: {1.457395, -5.673295, 0.00213943}
Frame 300: {1.191184, -10.46338, 0.002350604}
______
Frame 60: {0.649253, 10.35287, -2.569535E-06}
Frame 120: {1.902411, 6.274374, -3.512889E-05}
Frame 180: {1.959954, 0.8124294, 0.0007307049}
Frame 240: {1.457395, -5.673295, 0.00213943}
Frame 300: {1.191184, -10.46338, 0.002350604}
______
Frame 60: {0.649253, 10.35287, -2.569535E-06}
Frame 120: {1.902411, 6.274374, -3.512889E-05}
Frame 180: {1.959954, 0.8124294, 0.0007307049}
Frame 240: {1.457395, -5.673295, 0.00213943}
Frame 300: {1.191184, -10.46338, 0.002350604}
______
Frame 60: {0.649253, 10.35287, -2.569535E-06}
Frame 120: {1.902411, 6.274374, -3.512889E-05}
Frame 180: {1.959954, 0.8124294, 0.0007307049}
Frame 240: {1.457395, -5.673295, 0.00213943}
Frame 300: {1.191184, -10.46338, 0.002350604}
______
Frame 60: {0.649253, 10.35287, -2.569535E-06}
Frame 120: {1.902411, 6.274374, -3.512889E-05}
Frame 180: {1.959954, 0.8124294, 0.0007307049}
Frame 240: {1.457395, -5.673295, 0.00213943}
Frame 300: {1.191184, -10.46338, 0.002350604}
______
Frame 60: {0.649253, 10.35287, -2.569535E-06}
Frame 120: {1.902411, 6.274374, -3.512889E-05}
Frame 180: {1.959954, 0.8124294, 0.0007307049}
Frame 240: {1.457395, -5.673295, 0.00213943}
Frame 300: {1.191184, -10.46338, 0.002350604}
Technically, recreating the entire Space and readding everything is the brute force approach, but trying to deal with every single piece of bookkeeping in the engine would be more work than it's worth.

In situations where perfect determinism is required (especially when it's required across different computers, due to floating point implementation differences), it's often better to record the motion and play it back as an animation rather than to rerun the simulation.
Spankenstein
Posts: 249
Joined: Wed Nov 17, 2010 1:49 pm

Re: Object only follows the same path from second iteration?

Post by Spankenstein »

Technically, recreating the entire Space and readding everything is the brute force approach, but trying to deal with every single piece of bookkeeping in the engine would be more work than it's worth.
That's frustrating.
To fully eliminate this sort of problem, the space should basically be reconstructed from scratch on each iteration.
How would this work if there were more than one dynamic object and all dynamic objects were required to remain deterministic despite reaching the reset point at different times?
It looks like (at least part of) the issue is that the broad phase isn't being reset fully.
Is this part of the bookkeeping approach?

If the brute force approach is not feasible for more than one object then I will need to go down this path.

Could you provide an overview of what I will need to do to the engine if this is the case? Can it be done with callbacks without touching the source?
Norbo
Site Admin
Posts: 4929
Joined: Tue Jul 04, 2006 4:45 am

Re: Object only follows the same path from second iteration?

Post by Norbo »

How would this work if there were more than one dynamic object and all dynamic objects were required to remain deterministic despite reaching the reset point at different times?
If the objects can interact, there's no way to do this. If the objects can interact, then they can bump into each other and they will not follow the same path in general.

Another way to put it: if the objects interact and are reset to the top at different times, the simulation isn't getting reset at all- it's just a continuation of the simulation, diverging further and further. This would be the case even if the physics were entirely deterministic.

If the objects do not interact, they could exist in their own spaces. They couldn't be in the same space since the temporally coherent broad phase would generate pairs in different orders. At this point, I'd probably recommend the record-replay approach.
Could you provide an overview of what I will need to do to the engine if this is the case? Can it be done with callbacks without touching the source?
Unfortunately, whenever I had to choose between performance and determinism, determinism lost. There are many parts of the engine which rely on persistent state. You can avoid worrying about some of them depending on the nature of the simulation, but in the worse case, all of these would need to be dealt with:

1) Disable multithreading on the BroadPhase, NarrowPhase, and Solver.
2) Set the solver's permutation index to the same value on each reset.
3) If you wanted to reset the simulation to a point which involved collisions, replicate all collision pair handler, contact manifold, collision pair tester, and constraint state exactly. This would require a deep dive into the source to address.
4) The broad phase state needs to be reset to the exact same state. If you have many objects in the same space each following their own noninteracting deterministic path, you would need to redesign the broad phase to not be temporally coherent. That is, regenerate from scratch without taking into account previous information for optimizations.
[If you can guarantee that it doesn't matter which order the set of pairs is produced in because an object is only ever in one collision at a time, you could implement some order which guarantees which objects A and B will be. For example, use the objects' ids to sort each individual pair's collidables. This would ensure that the choice of A and B would not change the results. This approach is based on a bunch of assumptions and so will likely be very flimsy.]

#1 and #2 are standard and pretty easy.

#3 should probably be considered impossible in practice. It's way too much work. You would need to be intimately familiar with the sprawling web of interconnections between pair handlers, manifolds, testers, constraints and how it all works together in the broad phase, narrow phase, and solver. It's gross enough down there that I generally avoid it and will likely end up rewriting the whole thing at some point. So... avoid resetting to a point involving collisions. :)

The noted flimsy version of #4 is pretty doable. The more general broad phase rewrite version of #4 would be difficult, and would likely hurt performance.

In summary, my recommendation would be: don't go down that road.
Spankenstein
Posts: 249
Joined: Wed Nov 17, 2010 1:49 pm

Re: Object only follows the same path from second iteration?

Post by Spankenstein »

That's a good deal of information which will come in handy for discussion during my viva. As it is only 3 weeks away I won't go diving into the engine's source code.

However, I can make it deterministic using a sphere and an immediate reset so that will work out just fine for one of my demonstrations.

Thanks for your help as always, Norbo.

EDIT: It's late here but would creating a new instance of space.BroadPhase each time the iteration starts have a positive effect?
Norbo
Site Admin
Posts: 4929
Joined: Tue Jul 04, 2006 4:45 am

Re: Object only follows the same path from second iteration?

Post by Norbo »

All the objects would need to be added back into it (in a consistent order). If you handled everything correctly, it would indeed stop the broad phase's previous state from being used.

I can't guarantee that you wouldn't run into some other issue that the brute force Space recreation avoids. The interlocked persistent states are complicated enough that I'm not comfortable saying "oh it'll work fine", even if I'm not currently aware of a reason it should fail :)
Post Reply