# Collision response problem

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

## 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 on other sites
image not working

##### Share on other sites
are you doing a 'swept' test? like analytically finding the time of collisions? If no, then you'd have to do it.

##### Share on other sites
This sounds like a solvable problem - can you get the picture to show up?

##### 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 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, 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 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 on other sites

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 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 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:

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

1. 1
Rutin
46
2. 2
3. 3
4. 4
5. 5

• 11
• 9
• 12
• 10
• 13
• ### Forum Statistics

• Total Topics
632987
• Total Posts
3009731
• ### Who's Online (See full list)

There are no registered users currently online

×