I'm trying to implement 3D collision detection using SAT. It works really well when colliding with a single object and even most circumstances with multiple objects simultaneously. One problem I have found is that if a cube is moving along a bunch of square planes with gravity applied, it will get caught on the squares. Here's a picture to demonstrate:




The cube cannot move from its position. From what I understand, the reason is that SAT is pushing it to the side because the downward force is greater than the speed that the cube is moving horizontally.
So my question is, is there a way to get around this? This scenario is quite critical for my game, otherwise I wouldn't have asked.
Thanks.

OK, I think I've found my problem more specifically, so I'll try to simplify my question:

Assume square A collides with square B and C simultaneously like in the following picture:

I am expecting square A to move to the following location:

But, the way my algorithm works is that it evaluates square B and the square C individually, meaning it is placed like this:

This is obviously incorrect. So what is the best way to handle collision in this scenario?

Cheers.

This comes up a lot in relation to platformer movement/physics; the solutions seem to be either some sort of preprocessing (i.e identify the shared edges between the ground boxes and flag them, so that your collision model is a flat/smooth/continuous surface rather than a bunch of boxes), or some sort of logic to filter out or order the collisions.

If your dynamic object is a sphere, you can repeatedly push the sphere out of the single closest point on the world, this should correctly avoid bumping into seams; for a box, I'm not sure if there's something similar you can do. In your example, solving the deepest penetration first would work, but I don't think this works in general.

@Postie: I suggested this, but it doesn't work in general, only for that specific diagram.

As I mentioned, "deepest penetration first" does work for spheres, but for boxes it fails; depending on the speed of horizontal movement, the amount of gravity, and the particular time that the frame is sampled, the penetration with the "wall" can be deeper than that of the "floor".

One solution used in old platformers is to decompose A's movement into a series of axial movements, i.e first slide A along x,z then slide it along y.

OTOH you could solve this by trying every combination of collision ordering (i.e collect all collisions, then solve them in every order) and compare the results to see which lets you move A as far in the player-specified-direction as possible. If there are only a handful of collisions this may be feasible, otherwise the possible permutations will explode.

Or you could try caching the previous contact direction and solving collisions with that collision normal first. If this only happens with floors, you could also just solve collisions in order of decreasing y component in the contact normal, so that you solve "floor" collisions first.

All of these solutions involve first detecting ALL collisions, then selecting one, rather than the simpler approach of detecting and solving each collision one at a time.

I think most games solve this by using smooth triangle meshes as collision shapes; sadly this is a very static/pre-made solution and rules out a lot of interesting dynamic movement of the world.

OTOH you could solve this by trying every combination of collision ordering (i.e collect all collisions, then solve them in every order) and compare the results to see which lets you move A as far in the player-specified-direction as possible. If there are only a handful of collisions this may be feasible, otherwise the possible permutations will explode.

I tried something like this and it worked perfectly. Unfortunately, it only ran at 4 FPS, which is far from sufficient for me.

I'm thinking of applying something more specific to my game. ie There will be different states for movement, such as airborne (gravity will be applied) and grounded (no gravity but collision will be checked for ground below). I'm thinking this might be the best approach.

You could try using raycasts (or, AABB-sweeps) from slightly "above" the box's position each frame, sort of how FPSs handle stepping up small steps. This is getting further away from a "physics-based" approach though, but maybe that's not really important?

@stu_pidd_cow: Re: 4 fps, are you performing a broadphase collision detection pass first to reduce the number of collision tests?

I just added a broadphase pass and it boosted the FPS up to about 10-40 (depending on the amount of objects colliding).
The way I'm doing it is by finding all of the possible resolutions for a collision, then checking each of these resolutions for collisions, etc. After doing this 2 or 3 times, I find all of the resolutions that didn't have any collisions, and find which of these is the shortest.