Jump to content
  • Advertisement
Sign in to follow this  
Spa8nky

3D collision response with more than one plane.

This topic is 3494 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I have a ray plane intersection test for my 3D collision detection and a "wall sliding" response to the collision: public void CollisionDetection(Camera camera) { //------[Collision Detection & Wall Slide]------ //Wall Slide Equation: //Vt += Ni * (-dot(Ni,Vt)-Nd) //Where: //Vt = Desired Target or Destination of Player //Ni = Normal to the plane of impact //Nd = The "D" of the hit poly's "plane equation" Vector3 position = camera.Position; Ray ray = new Ray(position, position - camera.LastPosition); float rayLength; Plane? collisionResult = RayPlaneCollision(ray, out rayLength); if (collisionResult.HasValue) { // Collision with object Vector3 collisionSurfaceNormal = collisionResult.Value.Normal; float dot = Vector3.Dot(collisionSurfaceNormal, position); position += collisionSurfaceNormal * (-dot - collisionResult.Value.D - (camera.cameraBoundingSphere.Radius - EPSILON)); } camera.Position = position; } The problem occurs when I have the camera at the intersection of 2 planes (e.g. in a corner). The camera will bounce/stutter between each plane rather than behaving as a normal FPS shooter camera would in a corner. How can I adapt the code to allow the collision repsonse to behave correctly when colliding with more than one plane and therefore not bounce between each plane? Thank you.

Share this post


Link to post
Share on other sites
Advertisement
One option is to subdivide the timestep if you get a collision. First find the time of the earliest collision. If that's within the timestep then move all objects forward to that time, and adjust direction / speed as appropriate. Repeat until the time step is complete.

Just be careful of floating point inaccuracies when you do that or you may find you get objects intersecting each other by tiny distances - you'll want to stop objects slightly short of the actual collision point to avoid that.

Share this post


Link to post
Share on other sites
You could possibly build a combined projection vector from all intersections before moving the camera. i.e. iterate through each plane you're checking for collisions against, and if you intersect it, add the minimum distance/force necessary to escape the plane to an aggregated displacement vector. After your iteration, move the camera by the displacement vector.

Share this post


Link to post
Share on other sites
I also suggest what Adam_42 said. I'll expand a bit.

A nice way to do it is something like the following:

Vector3 start;// Camera position
Vector3 end;// Position we want to move to

while(findFirstCollision(start, end)) {
// You don't have to update start, you could try with and without this to see what gives best results
start = collisionPoint - ((collisionPoint - start) * EPS);

// Update end
end += normal * (.....);
}

camera = end;

findFirstCollision() needs to try to collide with every plane, and return the collision that occured closest to the starting point. You might want to move 'end' a small distance towards 'start' every time there is a collision too (as in my example for updating start to the collision point). This can avoid an infinite loop where you bounce back and forth between two planes, or similar inaccuracy problems.

Share this post


Link to post
Share on other sites
Thank you for your responses.

I have been working hard trying to get this to work correctly using your suggestions but with no success. Am I missing the point of what you are saying with this method:

Vector3 startPosition = camera.Position; // Camera Position
Vector3 endPosition = startPosition; // Position we want to move to

Ray ray = new Ray(startPosition, startPosition - camera.LastPosition);
float rayLength;

Plane? collisionResult = RayPlaneCollision(ray, out rayLength);
while (collisionResult.HasValue)
{
// Collision with solid wall
Vector3 collisionSurfaceNormal = collisionResult.Value.Normal;

float dot = Vector3.Dot(collisionSurfaceNormal, startPosition);

// Update End
endPosition += collisionSurfaceNormal * (-dot - collisionResult.Value.D - (camera.cameraBoundingSphere.Radius - float.Epsilon));

// Update the ray until there is no collision with any plane
ray = new Ray(endPosition, endPosition - startPosition);
collisionResult = RayPlaneCollision(ray, out rayLength);
}

camera.Position = endPosition;

Using a while loop will subdivide the timesteps until a collision is no longer found, right?

So why am I getting the same problem with the above idea?

What am I doing wrong here...and apologies for being a noob.

Share this post


Link to post
Share on other sites
It seems to me that you try to move from the end-position to the start-position, not the other way around as you should. Though perhaps it won't matter.. especially if it kinda works but you get some bouncing. What does the RayPlaneCollision function do, does it return the closest collision from all planes?

Also, when you paste your code into the post, do it like the following:
[code]
code here..
[/code]

Or if it's a lot of code use [source] instead, to get it in a separate text-box.

EDIT: At what angle do your planes intersect?
If the angle is greater than 90 degrees you will always get the bouncing behavior with a simple algorithm. I remember this was noticeable in Quake 3 for example. 90 degree corners should be fine though, but greater angles will cause problems, and smaller angles might get you stuck if you don't decrease the move vector magnitude with each collision.

[Edited by - Erik Rufelt on April 20, 2009 5:06:51 PM]

Share this post


Link to post
Share on other sites
The angles are either 90 degrees or less.

The code for the interection test is as follows:



private Plane? RayPlaneCollision(Ray ray, out float rayLength)
{
foreach (Triangle tri in Game1.levelTriangleList)
{
Plane trianglePlane = new Plane(tri.P0, tri.P1, tri.P2);

float distanceAlongRay; // Distance along Ray to intersection point
float u; // x Coordinate of intersection (Good for positioning decals)
float v; // y Coordinate of intersection (Good for positioning decals)

if (RayTriangleIntersect(ray.Position, ray.Direction, tri.Points, out distanceAlongRay, out u, out v, false))
{
// Only return a plane if the intersection point along ray is of a certain length
if (distanceAlongRay > 0.5f && distanceAlongRay < 1.5f)
{
rayLength = distanceAlongRay;
//Console.WriteLine("collision" + distanceAlongRay);
return trianglePlane;
}
}
}

rayLength = 0;
return null;
}



and for the Ray Triangle intersection:



private static bool RayTriangleIntersect(Vector3 origin, Vector3 direction, Vector3[] triangle, out float t, out float u, out float v, bool testCull)
{
return TestForIntersection(origin, direction, triangle[0], triangle[1], triangle[2], out t, out u, out v, testCull);
}

private static bool TestForIntersection(Vector3 origin, Vector3 direction, Vector3 vert0, Vector3 vert1, Vector3 vert2, out float t, out float u, out float v, bool testCull)
{
// Make sure the "out" params are set.
t = 0; u = 0; v = 0;

// Get vectors for the two edges that share vert0
Vector3 edge1 = vert1 - vert0;
Vector3 edge2 = vert2 - vert0;

Vector3 tvec, pvec, qvec;
float det, inv_det;

// Begin calculating determinant
pvec = Vector3.Cross(direction, edge2);

// If the determinant is near zero, ray lies in plane of triangle
det = Vector3.Dot(edge1, pvec);

if (testCull)
{
if (det < EPSILON)
return false;

tvec = origin - vert0;

u = Vector3.Dot(tvec, pvec);
if (u < 0.0 || u > det)
return false;

qvec = Vector3.Cross(tvec, edge1);

v = Vector3.Dot(direction, qvec);
if (v < 0.0f || u + v > det)
return false;

t = Vector3.Dot(edge2, qvec);
inv_det = 1.0f / det;
t *= inv_det;
u *= inv_det;
v *= inv_det;
}
else
{
// Account for Float rounding errors / inaccuracies.
if (det > -EPSILON && det < EPSILON)
return false;

// Get the inverse determinant
inv_det = 1.0f / det;

// Calculate distance from vert0 to ray origin
tvec = origin - vert0;

// Calculate U parameter and test bounds
u = Vector3.Dot(tvec, pvec) * inv_det;
if (u < 0.0f || u > 1.0f)
return false;

// Prepare for v
qvec = Vector3.Cross(tvec, edge1);

// Calculate V parameter and test bounds
v = Vector3.Dot(direction, qvec) * inv_det;
if (v < 0.0f || u + v > 1.0f)
return false;

// Calculate t, ray intersects triangle.
t = Vector3.Dot(edge2, qvec) * inv_det;
}

return true;
}

Share this post


Link to post
Share on other sites
Should be simple, test the movement ray against all planes, save the "t" (time of collision) for each, take the plane with the lowest "t" value and project the endpoint onto that plane, now you have a new movement ray from the point of the first collision to the projected endpoint, repeat until there is no more collisions, this will give you the wall sliding action FPS have.

Share this post


Link to post
Share on other sites
The "t" in the equation would be the length of each ray which would equate to time in a sense but....

If I were to take the lowest value of "t" then the I would collide with a plane even if I were a long distance from it and if no other plane was closer?

It doesn't make sense as to why I would want to do that, can you please explain?

Share this post


Link to post
Share on other sites
You seem to still return the first collision you find, not the closest collision. If you have two triangles in the list, the second tested can result in a closer collision than the first. You must save the closest collision so far in your loop, and keep looping until you have checked all the triangles, updating the closest collision when you find one closer than the previous. Then after the loop, return the closest collision (if there has been at least one collision).

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!