Sign in to follow this  

Collision response problem

This topic is 4715 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

Hello all! I've been fighting with a rather disturbing problem: my collision response routines do not work properly with 'non-convex' sets of polygons. I've put up an image illustrating the problem, take a look: In the top image, an AABB moves along the blue vector and collision detection routine (CD) detects that it comes into contact with the two polygons drawn in red. Collision response is invoked and these polygons are passed to the routine. Now, my collision response routines solves this problem by moving the AABB along the colliding polygon's normal until it no longer intersects with the polygon. Once that's done, we perform the 'wall sliding' along polygon's surface. The problem is that sometimes the polygon whose normal points 'up' in the image gets tested first before the polygon whose normal points 'right' (bottom-left image). This induces 'screen shaking' because so long distance needs to covered when the AABB is moved (in this case, the distance could be anything between 0 and height of the AABB). Bottom-right image shows the desired behavior. The AABB is moved right a bit until it no longer is in contact with either of the two polygons. My question is, is there any criterion to sort the polygons passed to the collision response routine in such way that polygons like the right-facing one in our case ends up tested first? My polygon data is organized into convex sets by using a BSP tree, if that's of any help. By looking at the image, I can't come up with any sort criterion that would work in all situations. First I thought about calculating the dot product between inverted movement vector (blue) and each polygon normal in turn and using it as the sort criterion, but I figured it doesn't work reliably in all situations. TIA.

Share this post


Link to post
Share on other sites
Go to this link to see the picture. I added the pic to the index.htm file:
http://www.angelfire.com/alt/arkion

To oliii:
Yes, I think it's a sweep test. The algorithm is implemented as per paper called
Real-Time Collision Detection and Response with AABB by Fabio Policarpo et al.

This is how I do it: I construct a super-AABB that encloses entire move, i.e. AABBs at both start and end position of the move. Then I intersect this super-AABB with the BSP tree and collect all polygons intersected by it. This is where the problem is - polygons are in random order and problems like this occur.

Seems this is an obvious flaw in the algorithm presented in the paper.

Share this post


Link to post
Share on other sites
the method is all right, although too complicated and too much code, but I think what you failed to do is to sort your collisions and take the earliest.



bool collide(Poly* axPolys, int iNumPolys)
{
bool bColliding;

do
{
bColliding = false;
float tcoll;
Vector Ncoll;
for(int i = 0; i < iNumPolys; i ++)
{
float tpoly;
Vector Npoly;
// earliest collision (or first detected collision)
if (Collide(axPolysd[i], tpoly, Npoly))
{
if (bColliding == false || tpoly < tcoll)
{
tcoll = tpoly;
Ncoll = Npoly;
bColliding = true;
}
}
}

// found something to collide with
if (bColliding)
{
RespondToCollision(tcoll, Ncoll);
}
}
while(bColliding);
}



try that first.

Share this post


Link to post
Share on other sites
I recently made a little collision engine, which handles such situation by finding penetration depth for all the collided primitives and using the smallest one found. That is for finding collision projection vector for a discrete position in time.

For a sweep collision check, you should find the earliest time of contact point in the movement direction instead of projecting the object out from the collision at result position at end of the time step.

Share this post


Link to post
Share on other sites
Thank you for your replies!

Quote:

the method is all right, although too complicated and too much code, but I think what you failed to do is to sort your collisions and take the earliest.


That's exactly what I'm trying to do... but the problem is, in case of the two red polygons shown in the image, my CD routine (TraceHull) makes no distinction between them - both are exactly the same distance from the AABB.

Here's my code. I've commented the problem spots:


Vector Game::MobjResolveCollisions(Mobj_t *mo, Vector p0, Vector p1)
{
TraceResult tr;
Vector dir, dir_n, dir_t;
float len;

while(true)
{
dir = p1 - p0;
len = dir.Length();

// Sweep AABB from position p0 to position p1
// NOTE: returns exactly the same result for both red polygons.
TraceHull(p0, p1, mo->bbox, false, mo, &tr);

if(tr.fraction == 1.0) // No collisions detected
break;

// Collision! Move as close to the collision plane as we can.
p0 = tr.vecEnd;

// Calculate reflection vector to slide along the colliding polygon
//
// NOTE: THIS IS WHERE IT GOES WRONG!
// Occassionally, tr.plane is the 'up'-facing polygon, while it <strong>should</strong> be the
// 'right' facing polygon - the result: the AABB is slid along
// wrong polygon, usually forcing it to pass through the 'right'-facing polygon.
dir.Normalize();

dir_n = tr.plane.normal * (Vector::DotProduct(tr.plane.normal, dir));
dir_t = dir - dir_n;
dir = dir_t * 0.95 - dir_n * 0.1;

if(dir.Length() < 1e-8)
{
gConsole.Printf("len too small!\n");
p1 = p0;
break;
}

// NOTE: AABB ends up inside solid
p1 = p0 + dir;
}

return p1;
}


Share this post


Link to post
Share on other sites
your pics still doesn't work for me. so I'm not 100% sure of what you mean.

so, it's a simultaneous collision. YOu have two planes, both colliding at the same time, then probably collide with the plane made of the sum of the two notmals, or something similar.

you can also process them one at a time. Visually, it won't matter if it collides first with one instead of the other, because the collision is simultaneous (a very small change in direction would make one wall hit before the other, and you won't notice the difference anyway).

Share this post


Link to post
Share on other sites
Seems there's something wrong with Angelfire service. I uploaded the image to another web host - hopefully it works now as it should:

Image Hosted by IUploads.com - Free Image Hosting

Yes, simultaneous collision is the right word. You see, getting proper collision plane to slide along is the problem.

Share this post


Link to post
Share on other sites
you could try using the polygon whose normal dotted with the vector of the Box is the negatively greatest, because when it comes to collision response, that normal would produce the most impulse on the box

Yratelev

Share this post


Link to post
Share on other sites

This topic is 4715 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.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this