• Advertisement
Sign in to follow this  

3D collision response with more than one plane.

This topic is 3224 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
Quote:
Original post by Erik Rufelt
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).


I have updated the code so that it now checks through all possible collisions to find the closest collision:



private Plane? RayPlaneCollision(Ray ray, out float rayLength)
{
rayLength = 0;
int distanceIndex = 0;
float[] rayDistances = new float[5000];
Plane[] trianglePlanes = new Plane[5000];

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))
{
// Store all Ray Intersections
rayDistances[distanceIndex] = distanceAlongRay;
trianglePlanes[distanceIndex] = trianglePlane;

distanceIndex++;
}
}

// If Ray has intersected a Triangle (distanceIndex will have incremented from 0)
if (distanceIndex != 0)
{
int index;

// Find Shortest Ray Distance
float shortestRayDistance = FindMinValue(rayDistances, out index);
rayLength = shortestRayDistance;

//Console.WriteLine("Shortest Ray Distance: " + shortestRayDistance);

return trianglePlanes[index];
}
else
{
return null;
}
}

float FindMinValue(float[] array, out int index)
{
float min = float.MaxValue;
int i = 0;
index = 0;
foreach (int value in array)
{
i++;
if (value < min && value != 0)
{
min = value;
index = i;
}
}
return min;
}



The camera still bounces between walls at 90 degrees or less with the following code:



public void CollisionDetection(Camera 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 startPosition = camera.Position; // Camera Position
Vector3 endPosition = startPosition; // Position we want to move to

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

Plane? collisionResult = RayPlaneCollision(ray, out rayLength);
while (collisionResult.HasValue)
{
startPosition = endPosition;

// Collision with solid wall
Vector3 collisionSurfaceNormal = collisionResult.Value.Normal;

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

// Update End
endPosition += collisionSurfaceNormal * (-dot - collisionResult.Value.D - (rayLength - float.Epsilon)); // (if D is -ve then it will be (-dot + D)

ray = new Ray(startPosition, startPosition - endPosition);
collisionResult = RayPlaneCollision(ray, out rayLength);

// [DEBUGGING]
i++;
Console.WriteLine("Collision" + i);
}

camera.Position = endPosition;
}



Thanks for your patience with this so far.

Share this post


Link to post
Share on other sites
You still seem to have your rays in the wrong direction, which will probably make the closest collision the furthest instead, and the other way around. For example
Ray ray = new Ray(startPosition, startPosition - camera.LastPosition);
If it's Ray(position, movement), then you are creating a ray moving from startPosition but in the direction away from the last camera position. It should probably be Ray(lastPosition, ...). Same with
ray = new Ray(startPosition, startPosition - endPosition);
Here you create a Ray with start position.. and then the direction is _away_ from endPosition, it should be endPosition-startPosition, going towards end.
Make sure startPosition is always the current camera position, and endPosition is always the target position you want to move to, and that all rays are in the correct direction.
Then you probably also have to update startPosition when you have a collision. If you hit a wall at point 'p', updating endPosition += ...., then also set startPosition = p, or perhaps (p + normal * smallOffset). This is however where you might break collisions in sharper corners, with smaller angles than 90 degrees.
It's hard to find a good solution that works for all corners, which can require more advanced methods. For example if you hit two planes in the same frame, calculate the line of intersection between these two planes, and move along that. The method you use now should work fine for most planes though..

Share this post


Link to post
Share on other sites
I have updated all my Rays so that they are going in the right direction (a noob mistake on my behalf) but the collision response is now still bouncing.

Have I setup the start position correctly as you suggested in the last post and a previous post. I presumed "p" would be the endPosition, is that correct?



public void CollisionDetection(Camera camera)
{
Vector3 startPosition = camera.Position; // Camera Position
Vector3 endPosition = startPosition; // Position we want to move to

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

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 Start Position (is "p" or point of collision the endPosition in this case?)
startPosition = endPosition - ((endPosition - startPosition) * float.Epsilon);

// Update End
endPosition += collisionSurfaceNormal * (-dot - collisionResult.Value.D - float.Epsilon); // (if D is -ve then it will be (-dot + D)

ray = new Ray(startPosition, endPosition - startPosition);
collisionResult = RayPlaneCollision(ray, out rayLength);

// [DEBUGGING]
i++;
Console.WriteLine("Collision" + i);
}

camera.Position = endPosition;
}



I'm not sure why, but now even the single plane collisions are bouncing the camera back.

Apologies again, but I am certainly keen to learn from my mistakes.

Share this post


Link to post
Share on other sites
What I mean with startPosition and endPosition is that start is where you are at before, and end is where you want to move to. You seem to treat them as where the target point is.. perhaps we have misunderstood each other. =)

What I mean is:

startPosition = camera.LastPosition;
endPosition = camera.Position;

ray = Ray(startPosition, endPosition-startPosition);

while(has collsion) {
// Update end to slide along the plane
endPosition += normal * (...);

// Update start so that the new ray (start -> end) is along the plane, not towards the plane (should counteract bouncing, you can also try without this)
startPosition = collisionPoint - (collisionPoint - startPosition) * Epsilon;
}

You could also use collisionSurfaceNormal * eps when offseting the new startPosition. The purpose of that is just the same as with the endPosition, to make sure it doesn't accidently get stuck inside the plane.

Make careful note of that startPosition is updated to 'collisionPoint', not the end position or something else. 'collisionPoint' is the actual point of intersection between the ray and the plane, somewhere in between start and end. You can usually get this from:

collisionPoint = startPosition + (endPosition - startPosition) * t

Where 't' is the intersection time you calculate.

Share this post


Link to post
Share on other sites
Quote:
Original post by Spa8nky
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?


"t" should actually be the time of collision. If you think of the movement ray in terms of time at the start position t would be 0, at the end position, t would be 1, if you get a t less than 0 or greater than 1 there is no collision, to calculate t you divide the length of the ray from the start to the collision between the length of the full movement vector from start to end. By the way, if you multiply the original movement vector by t, you should get the point of collision.

Share this post


Link to post
Share on other sites
I only skimmed the thread, so this may be irrelevant and/or a repeat of what's already been said, but...

I put together a 'swept ellipsoid' collision detection system (based on Kasper Faurby's paper) a few years back, and with some work managed to get it working perfectly, more or less.

Unfortunately, getting perfect behavior with respect to corners was less than straightforward (as I recall at least); I don't think a 'naive' implementation (that is, one that doesn't handle corners as special cases) will give you this.

The key turned out to be to detect when, in one timestep, the object hit the same surface more than once, and also to identify 'creases' and 'crease directions' (where a crease is basically an interior corner where two surfaces meet). If the object is found to be in a crease (a corner, essentially), you compute the crease direction as the cross product of the normals of the two surfaces, and restrict the object's motion to be parallel to that direction.

Using this method, I was finally able to eliminate any bouncing, getting stuck, or otherwise undesirable behavior. (I haven't studied the Quake engine collision detection code carefully, but I think it deals with corners in a similar way.)

I've thought about trying to dig up this code and make it available, but honestly, at this point I recommend just using (e.g.) PhysX for this sort of thing. Getting the behavior exactly right is non-trivial, so using an existing solution that is known to work correctly is likely to be a win in terms of time spent developing and debugging.

Share this post


Link to post
Share on other sites
Quote:
Original post by jyk
(I haven't studied the Quake engine collision detection code carefully, but I think it deals with corners in a similar way.)


Quake 3 does a lot of things, lots of special cases I mean, there is no special case specifically for corners, but there is for tight situations when more than one plane is in the way.

They keep a list of plane normals, which they call clip planes, these are used to clip the movement, the list is rather short, set to a fixed 5 maximum planes, one spot is always given to the normalized velocity ray, to prevent the movement to end up bouncing back too far I guess, and if there is a ground normal (the normal of the plane the player is standing on) it gets a spot as well.

The other three or four spots are filled by tracing the start and start+velocity positions against the planes (that's where convex brushes come into play), if the number of colliding planes exceeds the fixed maximum, the velocity is set to zero (IE: no movement), otherwise... well a lot of stuff happens, but in essence, the velocity is clipped and its direction changed so it either parallels or doesn't point against any of the clipping planes, if that's not possible, then again, velocity is set to zero.

There is also a limit (4) of how many "bumps" are allowed when clipping the velocity.

Its all in the PM_SlideMove function if you want to look it up, but it gets complex, and then there is a PM_StepSlideMove which is even more computations on top of PM_SlideMove, and so on.

Share this post


Link to post
Share on other sites
OK so after spending a couple of days on this, I am once again stuck (in game as well as out).

Using the suggestion of starting with camera.LastPosition will get the game code stuck in a while loop permanently before the game displays:


public void CollisionDetection(FirstPersonCamera 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 startPosition = camera.LastPosition; // Camera Position
Vector3 endPosition = camera.Position; // Position we want to move to

Ray ray = new Ray(startPosition, endPosition - startPosition);
float rayLength;
float i = 0;

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); // (if D is -ve then it will be (-dot + D)

// Update Start Position
float t = rayLength / (endPosition - startPosition).Length(); // Time(t) = Distance/Speed
Vector3 collisionPoint = startPosition + (endPosition - startPosition) * t;
startPosition = collisionPoint - (collisionPoint - startPosition) * float.Epsilon;

ray = new Ray(startPosition, endPosition - startPosition);
collisionResult = RayPlaneCollision(ray, out rayLength);

// [DEBUGGING]
i++;
Console.WriteLine("Collision" + i);
}

camera.Position = endPosition;
}


I presume that my calculation for t is now correct? (I hope it is)

What could be possibly going wrong with the above code, I just can't figure it out.

Share this post


Link to post
Share on other sites
It's kind of funny that this thread should appear now (at least to me) I've been working on this same problem with my collision detector for the last couple of days. I also started out with Kasper Faurby's code but now it has all been rewritten. For instance if the sphere collides with a face I don’t have to check it’s edges (same as KFs code) however since an edge is shared I keep track of this for the adjacent polygon so I don't check the edge again. The same goes for nodes, which end up getting shared in 6 polygons for my landscape implementation.

There are a bunch of other little hiccups which I have solved and some that I have yet to solve. I'm currently working on the multi-plane/line/point collision myself. I think I might have one solution that will work but I want to test it out before I post anything. If it ends up working I'll post my solution on this thread.

Share this post


Link to post
Share on other sites
That's what is usually done, you start the trace from the last safe position, and trace towards where you want to go.

As explained, there are lots of problems caused by floating point innacuracies, so you need to add extra safety margins to make the loop terminate.

it's all ad-hoc solutions really, it's a pain in the a** but unnavoidable.

Share this post


Link to post
Share on other sites
You update' end' before you calculate the collision-point. Your code 't = rayLength / (end - start).length()' will no longer be valid once you have changed 'end' to be different from the ray you used to calculate rayLength.

In addition, for exactness, change your start-position update to something like:

t = rayLength / (end-start).length();
t -= eps;

// It is possible with a very close collision that we move backwards, so clamp to zero
if(t < 0.0f)
t = 0.0f;

collisionPoint = start + (end - start) * t;
start = collisionPoint;


Also, exactly how small is float.Epsilon?
It might be too small. Pick a value that is small enough to not be very visible, but large enough to avoid problems. Usually I add the equivalent of 1/1000 of some visible unit. If your player is 1.0 high for example, add 0.001, see if it makes a difference.

And put in a max-loop count, and just stop at the collision point if you loop too many times. Like:

while(...) {
do collisions

if(loopCount++ > 50) {
end = start (new collision point start);
break;
}
}


EDIT: Another thing you can do to avoid looping too many times is to decrease the movement length each time you get a collision, before you check for a new collision. Just like you move back the new start position, but further. Pick a value of for example 0.1 * original movement length. That way, in ten loops, your move vector will actually be zero and you stop.

float len = (end-start).length();
float newLen = len - 0.1;
if(newLen <= 0) {
end = start;
break;
}

end = start + (end - start) * newLen / len;


[Edited by - Erik Rufelt on April 23, 2009 9:49:21 AM]

Share this post


Link to post
Share on other sites
Quote:
I presume that my calculation for t is now correct? (I hope it is)


As Erik pointed out there seems still to be still some issues. Here is what I would do for the center of your loop. This is just kind of psudo code. For some reason the plus sign doesn't come out for me on this forum so I'll just write "plus" instead.



// Get attempted travel vector
vecRay = ptEndPos-ptStartPos
// Get attempted travel distance perpendicular to collision plane
fPerpDist = -dot(vecRay,vecColSurfNormal)
// Calculate fraction of distance traveled before collision (not sure about the signs here depends on how you store D)
fT = (-dot(ptStartPos,vecColSurfNormal) – fColPlaneD) / fPerpDist
// Generate backoff vector so we don’t get stuck
vecBackOff = normalize(vecRay) * -fBackOffDist
// Get new staring position (i.e. collision point plus backoff)
ptStartPos plus= vecRay * fT plus vecBackOff
// calculate new ending position
ptEndPos plus= vecColSurNormal * (fPerpDist * (1.0 - fT)) plus vecBackOff


Again for multi-plane it's sort of a special case or rather a generalization. Here's what I'm thinking of doing: 1) Generate possible new vectors for each plane & each pair of planes (cross products of normals). 2) Eliminate all vectors that oppose other contact plane normals. 3) Of the remaing vectors find the path of least resistance (i.e. the one that is closest to the direction of travel)

Share this post


Link to post
Share on other sites
Hi folks.

So I'm still playing around with this collision algorithm and have come across some strange behaviour that leads me to think I have done something fundamentally wrong here. I would be happy if anyone could point out what :)

After reading your responses I have taken things back to basics and created one plane for the camera to collide with...should be simple right?

The plane is made up from the following points:


Plane trianglePlane = new Plane(new Vector3(0,0,0), new Vector3(0,10,0), new Vector3(100,0,0));


The z co-ordinates never change, so why is it when I return the collision point from the following equation, the z coordinate of collision changes:


Vector3 collisionPoint = startPosition + (endPosition - startPosition) * t;
startPosition = collisionPoint;

Console.WriteLine("Collision Point: " + collisionPoint.Z);


I think t is working correctly as it will go from +inf to 0 as I move closer to the plane.


distanceTravelled = (endPosition - startPosition).Length();
t = rayLength / distanceTravelled; // Time(t) = Distance/Speed
t -= EPSILON;


So I have decided to create the wall sliding effect when the camera is near the wall (i.e. t is small), however the wall sliding response never happens and the camera passes through the plane.

Something is very wrong here folks, but I can't figure out what:



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

//Console.WriteLine("Last Pos: " + startPosition);
//Console.WriteLine("Current Pos: " + endPosition);

Ray ray = new Ray(startPosition, endPosition - startPosition);
float rayLength;
float t;
float distanceTravelled;
float i = 0;

Plane? collisionResult = RayPlaneCollision(ray, out rayLength);
while (collisionResult.HasValue)
{
Plane collisionPlane = collisionResult.Value;

// Update Start Position
distanceTravelled = (endPosition - startPosition).Length();
//if (distanceTravelled - 0.1 <= 0)
//{
// endPosition = startPosition;
// break;
//}

distanceTravelled = (endPosition - startPosition).Length();
t = rayLength / distanceTravelled; // Time(t) = Distance/Speed
t -= EPSILON;

Console.WriteLine(t);

// Stop movement backwards by clamping value to 0 (-ve direction)
if (t > 0.0f && t <= 20.0f)
{
Vector3 collisionPoint = startPosition + (endPosition - startPosition) * t;
startPosition = collisionPoint;

Console.WriteLine("Collision Point: " + collisionPoint.Z);

// Collision with solid wall
Vector3 collisionSurfaceNormal = collisionPlane.Normal;
float dot = Vector3.Dot(collisionSurfaceNormal, startPosition); // Find right angle between Collision Surface Normal and Collision Point

// Update End
endPosition += collisionSurfaceNormal * (-dot - collisionPlane.D); // (if D is -ve then it will be (-dot + D)

ray = new Ray(startPosition, endPosition - startPosition);
collisionResult = RayPlaneCollision(ray, out rayLength);
//t = 0.0f;
}
else
{
break;
}
}


I look forward to your thoughts on the matter. Thanks.

Share this post


Link to post
Share on other sites
I would like to point out that if this is for your typical game where the camera follows a character you may not want to use a sliding response. All you really need to do is project a line backwards from your character to the point of the camera and then place the camera in front of at point if there is a collision. You can get fancy if you want but this is the only collision you really need. If you are running along a wall your camera will act like it's sliding anyway.

If you treat the camera like a character for the purposes of collision you will end up with a lot of problems. For instance, if your character goes around a quick wall your camera might be stuck on the other side.

However if you are treating this like a pure first person situation where you are controlling the camera or character) directly, none of what I said above applies. However in that case you might want to have a bounding sphere (or ellipse) around your character so he doesn't end up half in walls. The thing is, to do this you not only have to check planes but also edges and points. But again if it's only a camera plane and simple you don't need to worry about this either.

But let's get to your issue:

First off are you 100% sure TestForIntersection is working correctly? I mean I tend to store or generate the plane normal and then work off of that. I'm not saying that it isn't working but since it's done differently than I'm used too, I'm not real clear on it. If the lower level code doesn't work the rest isn't going to for sure so I would be doubly sure you have done everything right at the bottom end.

Minus some checks I basically wrote the whole pseudo code for a plane collision in my previous post. It shouldn't be this hard especially with a single point. Maybe you are trying to optimize too much up front. That's always a killer. Make sure you understand each and every line of code you are putting down and why it's there. Then if nothing else, you should be able to run through the debugger and find where you are going wrong.

Share this post


Link to post
Share on other sites
I would recommend to actually calculate how it works. Math don't lie, if you have the correct equation it will work as it's supposed to (except for numerical precision problems).
So for one plane it's very simple. Work it out on paper, and then write the code, and see that you get the same result. Then continue from there. Also, keep track of the winding of your triangles. What API are you using?
Your triangle in your last post is facing the negative z-axis, if the front-side is counter-clockwise.

This is how I usually do it:
Triangles are counter-clockwise viewed from the front.
Planes are 'ax + by + cz - d = 0', (a,b,c) is the normal for the plane. This makes 'd' the distance from (0,0,0) to the plane, in the direction of it's normal. This way a positive 'd' moves the triangle forward, which I think is the easiest way to see it.
To calculate the plane from three points in this case you do:
'normal = (a,b,c) = normalize(cross(p0-p1, p0-2))', where p0,p1,p2 are the points on the triangle (counter-clockwise viewed from the front in that order).
'd = dot(normal, p0)'

After that you have the distance to the plane from a point as 'dot(normal, point) - d'. This way you will get a positive distance when in front of the triangle, and a negative distance when behind the triangle.

Then for every collision, you check the distance from the plane to the start- and end-point, and if start is positive, and end is negative, then you have a collision.

If that is so, you move end out to just outside the plane, + epsilon, as usual.
'end += normal * (distance(plane, end) + eps)'
The distance is easily calculated as above with '(normal * end) - d'.

If you use exactly the winding and signs as I have doesn't matter, just make sure you know exactly which one you use, and always use the same one. It's easy to type + instead of - somewhere and break everything. That's why you need to decide how you represent your triangles and planes, and calculate it on paper, to make sure you really know it works. These things are far too complicated to just try and hack away at it until it works, you need to know it will work before you even run your code.

If you want to put start along the plane at a collision, you need the collision point. This is also easily obtainable with:
d0 = distance(start, plane)
d1 = distance(end, plane)
t = d0 / (d0-d1)
collisionPoint = start + (t * (end - start))

Again, remember your signs on distance etc. Calculate it on paper, and know that it works before you even run it.

Share this post


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

  • Advertisement