Box falling through level geometry

[DoctorWhy]

Here is a video to show what exactly is happening:

http://youtu.be/WGRSoSlRnKY

As I said in the video, I am not at all sure why. Here is the code to create the level and box

Code: Select all

//levelModel is a loaded .fbx model
Vector3[] vertices;
int[] indices;
TriangleMesh.GetVerticesAndIndicesFromModel(levelModel, out vertices, out indices);
for (int i = 0; i < vertices.Length; i++)
{
        vertices[i] = vertices[i] * 10f;
}
StaticMesh mesh = new StaticMesh(vertices, indices, new AffineTransform(new Vector3(0, 0, 0)));
space.Add(mesh);

//Then, when the box is created
Box box = new Box(player.playerCamera.cameraPosition + player.playerCamera.forwardTranslated * 6, x, y, z, 10);
box.LinearVelocity += player.playerCamera.forwardTranslated * 100;
box.PositionUpdateMode = BEPUphysics.PositionUpdating.PositionUpdateMode.Continuous;
space.Add(box);

If you need any other code or other information, let me know. I hope we can figure out what the problem is, I have grown rather fond of BEPU and I don't wish to change the physics engine this late in the game.

Thank you for the help.

[Norbo]

It looks quite a bit like a scaling issue. The engine likes individual objects to be in the range of 0.5 to 10 units. Going out of this range is very doable, but once you start going significantly below 0.2 or above a hundred, the door opens further and further for odd effects to creep in. The small scale failures tend to happen more abruptly as they are mostly based on tuning factors, while the excess failures are usually caused by a more gradual lack of numerical precision.

If I was going only by what the video looked like, I would have assumed the boxes are extremely tiny (significantly below 0.2 units), since going that small interferes with contact invalidation and other persistent manifold systems.

Here's a few common failure modes of super-tiny shapes:

-Convex shapes make use of a margin when colliding with other shapes that require general case MPR/GJK collision detection. Boxes (and most other shapes) default to 0.04 unit margins. Boxes, spheres, capsules, and cylinders have 'internal' margins, which means that rather than expanding the shape outwards with the margin, the core dimensions are shrunk and then spherically expanded by the margin. The effect is a box with slightly rounded edges. When a box shape has dimensions less than 0.08, the default collision margin would cause it to invert. This has nasty and very noticeable effects on collision detection, unsurprisingly. Shrinking or removing the margin can help, but it's not a great solution; the margin is there to allow more efficient collision methods to be used.

-In persistent manifolds, contacts don't like to be created too close to each other. This is defined by the (configurable) CollisionDetectionSettings.ContactMinimumSeparationDistanceSquared. When a tiny object collides with the ground, it might need three or four contacts for a completely stable support. But the engine might decide that two contacts were a little too close, leaving it without an important contact for a frame. If the engine is too pushy or the object is too small relative to the threshold, quality can degrade quite a bit. Typically, a failure of this kind will result in an object rocking and rolling a bit more than it should. This should not cause falling through a mesh by itself; even if it came close, mesh-convex collisions have some extra bits to stop that (assuming the shape isn't inverted by its collision margin ).

-Another contact tuning factor is the CollisionDetectionSettings.ContactInvalidationLengthSquared. This removes contacts as the object slides around, invalidating old contacts. For small objects, the default value can be a bit high, causing contacts to stick around a bit longer than they should. This might make sliding off the edge of a cliff a bit awkward, or it might prevent a better contact from taking its place sooner. This is probably the least noticeable failure type.

However, that velocity they're being shot with would imply a significantly larger scale (unless forwardTranslated isn't a unit vector). But to get to that level of badness would require some very extreme size values- I've never actually tested any large values which produced that kind of result.

If this is actually a scale issue, the best option is usually to rescale the elements of the simulation. Retuning the various control pieces in the engine is technically an option for cases where the objects are too small, but it's usually more work to pick good values and get everything consistent again.

A couple of other other (less likely) possibilities:
-Extremely long time steps obscured by interpolated graphics. This would have required setting up internal time stepping, enabling the interpolated states buffer, and manually setting the time step settings TimeStepDuration to something like 1/10 (defaults to 1/60f).
-Extremely long, near-degenerate triangles crisscrossing the playfield. A convex object landing on the face of a triangle uses very robust planar collision detection, but when there's an edge collision, it has to fall back to GJK/MPR. While GJK and MPR are very robust under normal conditions, they are susceptible to extreme scales. If there were a bunch of 100000x0.1 triangles such that every collision had to fall back to edge testing and MPR/GJK couldn't return a precise contact, something like this might happen.

If none of these possibilities look right, I'll probably need a runnable/debuggable reproduction case to look at. A custom demo in the BEPUphysicsDemos project or just some separate standalone project would be great.

[DoctorWhy]

The scale of the objects wasn't the problem, per-say (each side of the cube was randomly chosen between 2 and 5). However, the plane I was throwing the blocks onto, with a high gravity, was only 2 (large) triangles. In relation to the plane, the blocks were tiny. We made the plane 200 triangles, which stopped them from falling through the floor, even with 10 velocity down. However, it still dips into the ground a bit and slowly pushes back up. I am guessing if we made the plane have a lot more triangles, this wouldn't happen. This is a bit frustrating considering we lose a lot of efficiency by making flat planes more than a few triangles.

[Norbo]

Collisions on the face of a triangle in a mesh should be able to manage immense sizes without any problem thanks to the special case it uses. Using smaller triangles should only be noticeable when there are edge collisions (you may find extra triangulation to be useful if you expect edge collisions).

The 'slow push out of the ground' effect is related to the scale interpretation. The maximum position correction speed is too low for the large penetrations in the simulation.

For example, here's a modified version of the StaticMeshDemo. I've used a 30000x30000 triangle for the ground with similar size boxes and a gravity of (0, -100, 0). I included a few modifications to tuning factors to show how to get the simulation to more smoothly handle the different scale interpretation. The added comments explain the changes.

Code: Select all

            //Load in mesh data and create the collision mesh.
            Vector3[] staticTriangleVertices;
            int[] staticTriangleIndices;
            staticTriangleVertices = new Vector3[] { new Vector3(-10000, 0, -10000), new Vector3(-10000, 0, 20000), new Vector3(20000, 0, -10000) };
            staticTriangleIndices = new int[] { 2, 1, 0 };
            var staticMesh = new StaticMesh(staticTriangleVertices, staticTriangleIndices, new AffineTransform(Matrix3X3.CreateFromAxisAngle(Vector3.Up, MathHelper.Pi), new Vector3(0, -10, 0)));
            staticMesh.Sidedness = TriangleSidedness.Counterclockwise;

            Space.Add(staticMesh);
            game.ModelDrawer.Add(staticMesh);

            //Since everything's pretty large, increase the gravity a whole bunch to make things fall fast.
            Space.ForceUpdater.Gravity = new Vector3(0, -100, 0);

            //Also, the default rate of position correction is designed for a smaller scale.  These big objects 'look' tiny because of the gravity.
            //Since the velocities are so high relative to their size, they tend to penetrate with the environment quite a bit.  The default position correction
            //rate of 2 units per second feels too gooey.
            CollisionResponseSettings.MaximumPositionCorrectionSpeed = 15;

            //Additionally, because the gravity is so high relative to the size of the involved objects, any contact jitter
            //becomes extremely noticeable.  When objects slide around, this would be a bit ugly.
            //Increase the invalidation length so that sliding-related jitter is smoothed out.
            CollisionDetectionSettings.ContactInvalidationLengthSquared = 1;

            //Go ahead and scale up the minimum distance separation, too.  This will keep contacts from being created too close together (wasting valuable manifold slots).
            //This shouldn't be much of an issue when dealing with a giant triangle; the contacts will almost always be created at corners of the box.
            CollisionDetectionSettings.ContactMinimumSeparationDistanceSquared = .2f;

            //You can prevent the system from getting rid of contacts too fast when objects separate a bit too.  This defaults to 0.1, which is a bit low for 
            //the scaled up simulation. This can help stop some types of jitter.
            CollisionDetectionSettings.MaximumContactDistance = .5f;

            //Don't forget the margin!  The default collision margin is 0.04- this is quite small relative to the scale interpretation, so it would result in MPR fallback quite a bit.
            //By scaling up the margin, the more efficient algorithm is used.  The triangle face collision detection system isn't affected much by the margin, but anything that uses
            //the general case collision detection system will benefit (most convex-convex type pairs, triangle mesh edge collision, etc.) 
            CollisionDetectionSettings.DefaultMargin = 0.2f;

            //We don't care about the tiny, tiny details as much due to the larger scale.  By allowing a bit more slop with penetration, jitter is reduced.
            CollisionDetectionSettings.AllowedPenetration = .05f;

            //If you have bouncy objects or rely on static friction, it's a good idea to scale up the relevant thresholds too.
            CollisionResponseSettings.BouncinessVelocityThreshold = 5;
            CollisionResponseSettings.StaticFrictionVelocityThreshold = 1;

            //Finally, when dealing with objects that generally have high velocities and accelerations relative to their size, having a shorter time step duration can boost quality
            //a whole lot.  Most of the remaining 'unsmoothness' in the simulation is due to a lack of temporal resolution; one discrete step can take an object from a valid state
            //to an unpleasing state due to the high rates of motion.  To simulate the same amount of time with a smaller time step duration requires taking more time steps.
            //This is a quality-performance tradeoff.  If you want to do this, set the time step duration like so:

            //Space.TimeStepSettings.TimeStepDuration = 1 / 120f;

            //And then, in the update, either call the Space.Update() method proportionally more often or use the Space.Update(dt) version, which takes as many timesteps are necessary to simulate dt time.
            //Watch out: when using the internal timestepping method, you may notice slight motion jitter since the number of updates per frame isn't fixed.  Interpolation buffers can be used
            //to address this; check the Asynchronous Update documentation for more information on using internal time stepping.  
            //[Asynchronously updating isn't required to use internal timestepping, but it is a common use case.]

            //Dump some boxes on top of it for fun.
            int numColumns = 8;
            int numRows = 8;
            int numHigh = 1;
            float separation = 8;
            Entity toAdd;
            for (int i = 0; i < numRows; i++)
                for (int j = 0; j < numColumns; j++)
                    for (int k = 0; k < numHigh; k++)
                    {
                        toAdd = new Box(
                            new Vector3(
                            separation * i - numRows * separation / 2,
                            30f + k * separation,
                            separation * j - numColumns * separation / 2),
                            2, 4, 6, 15);

                        Space.Add(toAdd);
                    }



            game.Camera.Position = new Vector3(0, 10, 40);

Some of the above changes can be rendered unnecessary by scaling down a bit, but the high rate of motion relative to the size of the objects will still pose difficulties unless a faster time step is used. Of course, the actual values of the tuning depends on the simulation details; the above might not perfectly match your situation.

[Norbo]

And I forgot one more thing: the default collision margin! By increasing it up proportionally with the scale, the faster algorithms can be used more often:

Code: Select all

            //Don't forget the margin!
            CollisionDetectionSettings.DefaultMargin = 0.2f;

This won't be a significant effect when it's just boxes on a giant triangle due to the special case collision detection involved. However, when the general case collision detection system is used (say, on an triangle edge collision or between convex hulls or something), it will help.

[Norbo]

One more thing: Allowed penetration!

Code: Select all

            //We don't care about the tiny, tiny details as much due to the larger scale.  By allowing a bit more slop with penetration, jitter is reduced.
            CollisionDetectionSettings.AllowedPenetration = .05f;

I'll go ahead an update the original post with these.

In summary (for anyone who might see this thread later), the relevant tuning factors for changing the scale interpretation are:
CollisionResponseSettings.MaximumPositionCorrectionSpeed
CollisionResponseSettings.BouncinessVelocityThreshold
CollisionResponseSettings.StaticFrictionVelocityThreshold
CollisionDetectionSettings.ContactInvalidationLengthSquared
CollisionDetectionSettings.ContactMinimumSeparationDistanceSquared
CollisionDetectionSettings.MaximumContactDistance
CollisionDetectionSettings.DefaultMargin
CollisionDetectionSettings.AllowedPenetration

And in any case where objects are moving or accelerating fast relative to their size, the time step matters.

I'll update these posts if I remember something else. I should probably bundle these factors up a bit and write up explanation in some documentation somewhere considering the fact that it took me FOUR attempts to get everything

This is why I generally advise sticking to the 'normal' scale, but my usual recommendation of 0.5 to 10 units really isn't sufficient since it doesn't capture the full concept of scale interpretations. A 10 unit (and far bigger) size box works absolutely perfectly fine at scale interpretations similar to the BEPUphysicsDemos, but it behaves like a very large object. A 10 unit size box which is interpreted as a very tiny object (high relative gravity) requires a much different configuration.

Edit: Added bounciness and static friction thresholds.

[Norbo]

The development fork now includes a ScaleDemo and the demos ConfigurationHelper now has an ApplyScale method to change all the relevant properties at once.