Hello. I am trying to implement my collision engine for a 2d platformer. I want it to support vector geometry, such as polygons and slopes of different angles and shapes. For a pair of two polygons i use Separating axis theorem to find the minimum translation vector that is needed to be added to the body position to separate them. However, i've ran into following problems:

At first, i dont know how to handle collisions with multiple bodies. If i translete the moving body by every minimum translation vector i found by colliding it with each static polygon, the total translation result may appear to be too long or too short.

The second problem appears in some situations when i alter the velocity of the moving body accordingly to the collision data. For example, in such situations, as shown in the picture below.

The body (blue rectangle) is moving with velocity V and penertates into a wall composed out of two red rectangles. While processing collision with the leftmost red rectangle, the normal is found by smallest penetration axis, it points up. I subtract the normal, multipled by the dot product of normal end velocity, from the body velocity vector. This is OK. However, in the case of rightmost red rectangle, the horisontal penetration (X) appears to be smaller than vertical penetration (Y) and the collision normal is considered to be horisontal. It makes the body to stop, while it had to slide along the wall.

I found several solutions to this problem, such as:

- Make the world out of line segment loops without inner edges.

- Make the corners of the moving bodies, static obstacles or both, smooth and round.

I also tried continuous collision detection, but ran into a similar problem where bodies were colliding with the corners of static obstacles.

Although i can solve this problem by rounding the moving shapes, i still wonder how the similar problem is solved in modern 3D physics engines and other 2D games.

I also still dont know, how to move the body out to solve its penetration into multiple obstacles.

Thank you if you can help.

You could try to just move the blue backwards along its velocity until it no longer collides with anything like you are doing now but only alter the blue velocity in the last collision. you also could define a minimum Y penetration(could even be a variable inside blue) so that if the Y penetration is smaller than that then even if X penetration is smaller than Y you still take the Y one. You should get pretty satisfactory results if you do both of these.

You could try to just move the blue backwards along its velocity until it no longer collides with anything like you are doing now but only alter the blue velocity in the last collision. you also could define a minimum Y penetration(could even be a variable inside blue) so that if the Y penetration is smaller than that then even if X penetration is smaller than Y you still take the Y one. You should get pretty satisfactory results if you do both of these.

Calculating how far to push body along its velocity is not that simple, as finding its minimal separation vector, but is almost the same as finding exact collision time in continuous collision algorithm. As i already said, continuos collisions involve more problems like corner-corner collisions, which i also dont know how to solve.

Your second advice, probably, will not work correct in any collision conditions. For example, it would work very ugly, if there was no left red rectangle and the blue one penetrated more on vertical axis. Also notice, that if there was no right red rectangle, resolving the collision on the horisontal axis would be fine. So, i think, i must somehow consider all the collisions at one time, but must not resolve them pairwise.

Maybe i should use a completely different collision resolving approach, but i know only those two (continuos collison and penetration - based). Maybe i also could use continuous collision with kind of fix for corner-corner collisions. I dont know how to fix it.

Well, probably it was just vertices welding problem in continous collision.

You could try to just move the blue backwards along its velocity until it no longer collides with anything like you are doing now but only alter the blue velocity in the last collision. you also could define a minimum Y penetration(could even be a variable inside blue) so that if the Y penetration is smaller than that then even if X penetration is smaller than Y you still take the Y one. You should get pretty satisfactory results if you do both of these.

Calculating how far to push body along its velocity is not that simple, as finding its minimal separation vector, but is almost the same as finding exact collision time in continuous collision algorithm. As i already said, continuos collisions involve more problems like corner-corner collisions, which i also dont know how to solve.

It is relativily simple. Just rotate both velocity and surfacepenetration the same amount so that the surface vector is upright(x==0). Then multiply the original velocity vector by vel.y/surface.y and thats it. I assume you already have the distance blue has penetrated along the surface normal. And you may need to use vel.y/-surface.y if your surfacepenetration vector goes from surface to inside instead of from inside to surface. Also if you store the percentages of velocity used(the vel.y/surface.y part) you can then after the last collision has been processed move the character again by velocity*(-sumofstoredvalues) as to make it move more physically accurately.

As for the second approach. It is actually quite common in platformers as it makes characters able to climb stairs and slopes and run over small gaps without having to make complicated code to detect those special cases.

You could try to just move the blue backwards along its velocity until it no longer collides with anything like you are doing now but only alter the blue velocity in the last collision. you also could define a minimum Y penetration(could even be a variable inside blue) so that if the Y penetration is smaller than that then even if X penetration is smaller than Y you still take the Y one. You should get pretty satisfactory results if you do both of these.

Calculating how far to push body along its velocity is not that simple, as finding its minimal separation vector, but is almost the same as finding exact collision time in continuous collision algorithm. As i already said, continuos collisions involve more problems like corner-corner collisions, which i also dont know how to solve.

It is relativily simple. Just rotate both velocity and surfacepenetration the same amount so that the surface vector is upright(x==0). Then multiply the original velocity vector by vel.y/surface.y and thats it. I assume you already have the distance blue has penetrated along the surface normal. And you may need to use vel.y/-surface.y if your surfacepenetration vector goes from surface to inside instead of from inside to surface. Also if you store the percentages of velocity used(the vel.y/surface.y part) you can then after the last collision has been processed move the character again by velocity*(-sumofstoredvalues) as to make it move more physically accurately.

As for the second approach. It is actually quite common in platformers as it makes characters able to climb stairs and slopes and run over small gaps without having to make complicated code to detect those special cases.

I cant understand properly your solution. Could you explain it better or give a pseudocode example, please? Also, notice that im using different polygons in my engine, not only AABBs.

I cant understand properly your solution. Could you explain it better or give a pseudocode example, please? Also, notice that im using different polygons in my engine, not only AABBs.

Ok let me try.

All of this should work with any size and shape polygons and the image has axis aligned rectangles only because I was using mspaint.

[attachment=26235:figurea.png]

First we need to find a corner from blue polygon that is inside red polygon and call it corner A. Then find the surface in red wich is the closest one to corner A that is between corner A and an adjacent corner from blue and call it surface B.

In order to move the blue outside of the red polygon we need a vector from corner A to surface B and call it surfacepenetration.

Then we calculate the angle between surfacepenetration and a vector(0,1) and call it surfacenormalrotation.

Then make a new vector called rotatedvelocity by copying and rotating the original velocity by surfacenormalrotation.

Now we take the length of surfacepenetration and divide it by the Y component of rotatedvelocity.

This gives us a float t between 0 and 1. This is the precentage of velocity you need to move blue one backwards to make corner A be outside of red polygon.

Here is a pseudocode for the moving blue backwards part.

float angle=findangle(surfacepenetration,upvector)
vector2d rotatedvelocity=blue.velocity.copy
rotatevector(rotatedvelocity,angle)
float t=abs(surfacepenetration.length/rotatedvelocity.y)
blue.pos-=blue.velocity*t

.

When we enter the collision handling we repeat this until blue is not inside any red polygons. Then we process what happens to blue based only on the last collision that was detected this way as that is collision would have happened first if your simulation steps were small enough. In your first example picture it would always be the collision with the left red rectangle and the blue stops because of hitting the right red rectangle horizontally never happens.

Also if we store the percentages of velocity we moved blue backwards we know how many percent of "frametime" blue actually moved and we can then move blue again with the remaining percent after the collision has been resolved and blues velocity has been updated. This way no "frametime" is lost when collisions happen and the simulation looks smoother.

In a case where red corner is inside blue polygon you can use the same method. Corner A just comes from red and surface B comes from blue.

We still need to solve the case where the right red polygon is a tiny bit higher than the left and blue moves along the surface from left to right. When it hits the right polygon its going to hit it horizontally again and again and never get past it. That is why we need a variable to override the behaviour. When we search the closest surface if we find a surface that is less than minypenetration away and the resulting surfacepenetration vector would be mostly vertical we need to choose that one. And in this case we also don't move blue backwards but upwards instead to avoid getting stuck. If you don't do this then your seams must be perfect or you get "wierd stops" when you hit the seams from the lower side.

Edit: Ohsnap I had the vectors in the calculation of t wrong way around.

I found several solutions to this problem, such as:

- Make the world out of line segment loops without inner edges.

I think too that you should detect edges of surfaces that cannot be penetrated. Collect all your edges penetrations without considering unsurfaced edges, find out paralel edges (if you detect penetration vector length it should be trivial for you as well), filter from penetration collection the "unreachable" edge's penetrators, and consider what you have left only, ordered by size as well. Should work like a charm as I think of it

I cant understand properly your solution. Could you explain it better or give a pseudocode example, please? Also, notice that im using different polygons in my engine, not only AABBs.

Ok let me try.
All of this should work with any size and shape polygons and the image has axis aligned rectangles only because I was using mspaint.
figurea.png
First we need to find a corner from blue polygon that is inside red polygon and call it corner A. Then find the surface in red wich is the closest one to corner A that is between corner A and an adjacent corner from blue and call it surface B.
In order to move the blue outside of the red polygon we need a vector from corner A to surface B and call it surfacepenetration.
Then we calculate the angle between surfacepenetration and a vector(0,1) and call it surfacenormalrotation.
Then make a new vector called rotatedvelocity by copying and rotating the original velocity by surfacenormalrotation.
Now we take the Y component of rotatedvelocity and divide it by the length of surfacepenetration vector.
This gives us a float t between 0 and 1. This is the precentage of velocity you need to move blue one backwards to make corner A be outside of red polygon.

Here is a pseudocode for the moving blue backwards part.

float angle=findangle(surfacepenetration,upvector)vector2d rotatedvelocity=blue.velocity.copyrotatevector(rotatedvelocity,angle)float t=abs(rotatedvelocity.y/surfacepenetration.length)blue.pos-=blue.velocity*t

.

When we enter the collision handling we repeat this until blue is not inside any red polygons. Then we process what happens to blue based only on the last collision that was detected this way as that is collision would have happened first if your simulation steps were small enough. In your first example picture it would always be the collision with the left red rectangle and the blue stops because of hitting the right red rectangle horizontally never happens.

Also if we store the percentages of velocity we moved blue backwards we know how many percent of "frametime" blue actually moved and we can then move blue again with the remaining percent after the collision has been resolved and blues velocity has been updated. This way no "frametime" is lost when collisions happen and the simulation looks smoother.

In a case where red corner is inside blue polygon you can use the same method. Corner A just comes from red and surface B comes from blue.


We still need to solve the case where the right red polygon is a tiny bit higher than the left and blue moves along the surface from left to right. When it hits the right polygon its going to hit it horizontally again and again and never get past it. That is why we need a variable to override the behaviour. When we search the closest surface if we find a surface that is less than minypenetration away and the resulting surfacepenetration vector would be mostly vertical we need to choose that one. And in this case we also don't move blue backwards but upwards instead to avoid getting stuck. If you don't do this then your seams must be perfect or you get "wierd stops" when you hit the seams from the lower side.

Thank you a lot, but how and why did you chose the vector(0, 1)? Should i change it, if we are sliding along the vertical or any other angle wall? Do i need a way to determine this vector for every collision?