Advertisement

The theory behind collision response and sliding

Started by November 27, 2021 09:18 PM
14 comments, last by Gnollrunner 2 years, 11 months ago

Detecting stuff in 3d is not as easy as in 2d. I have managed to detect the collision but I am stuck trying to get the correct collision response. It seems that there is no good information online, so I might aswell ask it here. Note im trying to check collision against a voxel.

Here is my collision function which 100% works

bool collision(glm::vec3 block_position)

{

int x = block_position.x;

int y = block_position.y;

int z = block_position.z;

auto x1 = camera.position.x > x - 0.5f && camera.position.x < x + 0.5f; // 0.5 half block size

auto y1 = camera.position.y > y - 0.5f && camera.position.y < y + 0.5f;

auto z1 = camera.position.z > z - 0.5f && camera.position.z < z + 0.5f;

return x1 && y1 && z1; // this function works

}

But my collision response function I have not really managed to put together. Can someone explain.

void collision_response(glm::vec3 block_position)

{

int x = block_position.x;

int y = block_position.y;

int z = block_position.z;

auto dx = camera.position.x - x;

auto dy = camera.position.y - y;

if(!dx && !dy)

{

camera.position.x = prevPos.x;

camera.position.y = prevPos.y;

return;

}

auto angle = abs(atan2(dy, dx) + PI / 4);

if (angle >= -1*(PI) / 2 && angle <= 0) camera.position.x = prevPos.x;

if (angle >= 0 && angle <= PI / 2) camera.position.y = prevPos.y;

}

It seems all you do to resolve collisions is to set certain coordinates back to the previous state. This can't work well, because:
It assumes your previous state would be correct, which likely is not the case in difficult situations.
It's not how physics work.

There are usually two options to do it right:
1. Prevent penetration by finding position (and eventually time) of collision, projecting velocity so it will slide on or bounce off the surface (depending on a given material property ‘coefficient of restitution’). Can be done using raytracing along velocity.
2. Allow and resolve penetration by projecting the point to the closest point on the surface of the voxel. That's often easier and probably what you tried to do. Velocity can be adjusted as above.

There is no need for trigonometry here. To find the closest surface of a point in a cube, you could just project the point to all 6 faces and use the one causing the least displacement.
We can reduce this to 3 faces if we look at which side from the center the point is, and displacement is always axis aligned if the cube is, so that's some opportunity to simplify and optimize.

Moving the camera to the surface then would give you the expected sliding, but cameras at zero distance to a surface cause artifacts, so using something like a sphere instead a point would be the next step.

To give some code review, your functions would end up more useful if you would give the colliding point as parameter instead using a global variable of camera position.
And the use of auto makes it hard to guess if we work with float or int, but maybe that's just me.

Advertisement

@undefined I really appreciate your answer. So the way to go is to try every normal of the cube and then relosve my position by calculating the projecting? What i dont understand is how I should seperate the different 6 calculation so i know which one i should go with?

ocry said:
So the way to go is to try every normal of the cube and then relosve my position by calculating the projecting?

Yes.

ocry said:
What i dont understand is how I should seperate the different 6 calculation so i know which one i should go with?

You choose the one which causes the least displacement from the penetrating point to the projection on the surface. Or in other words you move to the closest of all potential solutions, so energy is minimized like real world behaves.

If you are are just sweeping a point, you should be able to just take the position it would have ended up at if it hadn't collided, and project it back to the collision plane. You can find the distance it is from the plane using a dot product of a couple vectors (see scalar projection). One would be the collision plane normal, and the other can be a vector from any point on the plane (for instance the point you collided at or just a corner of your voxel) to the point your checking the distance from. Then you can just offset non collided point by the normal times the distance to the plane, taking the signs into account. This gives you your final response location.

The problem you might have is two plane collisions. This can happen if our are colliding in a corner created by a couple voxels next to each other. For that you might have to take the cross product of your two collision planes to get a new response direction. This worked for me and I was doing a general mesh collision so I'm sure it's fine for the more restrictive case of voxels, although with voxels there might be some better optimization you can do. It's even possible to hit 3 planes which tends to mean you stop cold. This all works for any mesh not just those generated by voxels. However finding the collision planes is probably a lot easier with voxels since they give you a natural way to find your collision plane.

You can also do a sphere or capsule with voxels which you may need at some point for a character. This is a bit more complex as you also have to check edges of voxels and corners of voxels. You do plane, edge, point in that order.

@gnollrunner

Gnollrunner said:

One would be the collision plane normal, and the other can be a vector from any point on the plane (for instance the point you collided at or just a corner of your voxel) to the point your checking the distance from.

If i take the corner of the voxel that wont give me a correct sliding right?

Advertisement

ocry said:

If i take the corner of the voxel that wont give me a correct sliding right?

Let me reiterate. Say you collide with a voxel. The first step is to figure out which face you collided with. There are 6 possibilities. Once you find the right face, it has four corners and a normal associated with the plane that it's on. Now you also have a “target” point, a point that you would have arrived at if you hadn't collided. If you subtract the target from any corner point of your face, you will get a vector . Now if you do a dot product of that vector and the plane normal (which should be length one) you will get a value which is the distance from the plane (you might have to flip the sign around depending on which way your normals go). So now you have a distance from your target point to the plane that you collided with. You can multiply your plane normal by that distance and get some value to offset your target by, that will put it back on the plane that you just collided with. This is basically the response.

So if you collide at 90 degrees there is no sliding at all. However the more shallow your collision is the more you slide along the face.

The next thing to figure out is what to do when the response pushes you into yet another collision. That's a 2 plane collision. The way I solve that is with a cross product of the two plane normals. This part I figured out myself, so I'm not really sure if it's the standard solution, but it does work. In any case that gives you the direction you want to go, and you kind of have to project the remainder of your movement back on that line. You can do that with the appropriate dot product again.

So the full thing is kind of iterative. You collide with a plane, find the new response point. However the path from your collision point to your response point can in fact create a new collision. so in that case you do it again. In practice with slow speeds you won't get much more than 2 iterations. But it will work for high speeds and you will never get stuck in your geometry.

ocry said:
If i take the corner of the voxel that wont give me a correct sliding right?

Notice working with edges and vertices becomes necessary when replacing a simple point with a sphere or capsule as Gnollrunner said, or if we want to prevent penetrations like i said. Replacing our point with a sphere means we still work with a center point, but we also ensure to keep a distance to the surface, given by the sphere radius:

You see the point penetrating the square never moves out of it by moving towards a corner vertex. It always moves towards an edge in axis aligned directions, because those are closer.
But the circle outside the square can either collide with an edge so moving in axis aligned directions as well, but it can also collide with a corner vertex and then moving along the angled line between corner and circle center.
With 'moving' i mean the direction of resolving the penetration. Any other motion tangent to this direction can remain (sliding) or slow down (friction).
A very simple model to do this could look like this:

vec3 contactNormal (0,1,0); // assuming we penetrate an upwards face of a voxel, but could be also normalize(curPos - voxelCorner) if we collide with a corner for example.
float penetration = 0.05f; // assuming our sphere pentrates the face that much
vec3 velocity = (curPos - prevPos) / timestep;

// decompose velocity into tangent (sliding) and normal (resolving penetration) parts:
vec3 normVel = velocity - contactNormal * dot(contactNormal, velocity); // project to the normal plane
vec3 tangVel = velocity - normVel; // subtracting this gives us the tangent part

// model how collision affects velocity
normVel *= -0.1f; // we want a little bouncing off the surface
tangVel *= 0.95f; // some friction slows down sliding
vec3 newVelocity = normVel + tangVel;

// update
vec3 resolvedPos = curPos + contactNormal * penetration;
vec3 nextPosition = resolvedPos + newVelocity * timestep;

So beside resolving collisions, you also might want to model how material interaction affects further behavior.
Notice how this clearly separates handling penetration and sliding friction. Dot product enables this for any direction, so it does not matter if we are axis aligned or not.

One thing I'll add is you can do it without the dot products if everything is aligned with X, Y and Z. However it's really not much harder doing it the general way and if you ever want to introduce things like ramp voxels and 45 degree voxels, your collision will still work.

@gnollrunner @joej thanks for the help. i will come back if i don't understand something

This topic is closed to new replies.

Advertisement