0
\$\begingroup\$

I have a 3D grid of voxels in my game. Entities walk around with simple physics that represents them as an axis aligned bounding box with velocity, mass and acceleration. The way I'm doing collision resolution is fairly simple. Here's some pseudocode:

function ResolveCollisions()
    // For each voxel that could intersect the bounding box...
    foreach (Voxel neighbor in VoxelGrid.GetVoxelsIntersecting(this.bounds))
        // Check a collision between the voxel and the bounding box
        if (neighbor.Collides(this.bounds))
            ResolveCollision(neighbor, bounds);

function ResolveCollision(Voxel neighbor, BoundingBox bounds)
     // Compute the contact normal and penetration distance between the two
     // boxes.
     [Vector3 norm, float dist] = ComputeMinPenetration(neighbor, bounds);
     // Snap the position so its no longer colliding
     this.position += norm * dist;
     // Reflect the velocity over the normal to perform an elastic collision.
     this.velocity = this.Restitution * Vector3.Reflect(this.velocity, norm);

This works pretty well for instantaneous collisions and bouncing, but fails for sliding contact. If an entity is sliding across a flat plane of voxels, for instance, it will rapidly bounce, and will sometimes end up colliding with the sides of the voxels instead of the top.

How do I get realistic sliding contact between the bounding box and a voxel grid, without bouncing or "toe stubbing?"

\$\endgroup\$
1
\$\begingroup\$

The problem with resolving collisions of an entity with voxels in an arbitrary order is that a collision with a voxel edge may be detected before a collision with a face which would have happened earlier.

In this diagram a sphere is sliding along a voxel floor (right to left). Its velocity vector (blue) has a downwards component due to gravity. If collision against voxel A is checked first, the resolution vector (red) will cause the sphere to kick up. This is obviously undesirable because that edge doesn't really exist. If voxel B had been tested and the collision resolved first (green vector) then the erroneous collision with A would never had happened.

Sliding sphere

So the solution is to check the voxels which share a face with the voxel containing the sphere's center first, then those voxels which share an edge, then those which share just a corner. This ensures that e.g. moving across a flat floor the entity will always be pushed up before it collides with the hidden edges of voxels making up the floor.

If this seems like an arbitrary hack, ask yourself if it is possible for a sphere to collide with the corner or an edge before it collided with a face of a neighboring voxel.

Your pseudocode above should work if you add a step to sort the voxels found in GetVoxelsIntersecting by Manhattan distance from the voxel containing the entity's center.

\$\endgroup\$
  • \$\begingroup\$ Interesting. Can you elaborate on how you did this? Thanks. \$\endgroup\$ – mklingen Feb 12 '15 at 17:39
  • \$\begingroup\$ I remember now it isn't quite as simple as I had remembered. I'll edit my answer a bit later when I have some time. How are you modelling your entities? Mine were spheres slightly smaller than the size of a voxel, with several 'glued together' for larger entities. The complication with the larger entities is that you cannot consider each sphere independently; you have to resolve the earliest collision first. \$\endgroup\$ – GuyRT Feb 12 '15 at 17:51
  • \$\begingroup\$ Most of my boxes are at most 0.75 times the size of a voxel, so I shouldn't have a problem with that. Thanks for your time. \$\endgroup\$ – mklingen Feb 12 '15 at 20:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.