Original Post
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.
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.
