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

Recommended Posts

Hello,

I'm currently programming a very simple physic engin but recently i've come to a problem i've put too many hours on.

I'm using the separating axis theorem to detect collision between 2 shape (usually a rotating rectangle and a static polygon).

I am calculating the minimum translation vector to resolve collisions.

Everything seems to be working except for one thing:

If an actor  (my rotating rectangle) is touching a slope (the static polygon) by only one pixel, the calculated MTV will be (-1,0) insteed of the expected (-1,-1). For everything else, it's working fine.

For the visuals, here is an image. I'm handling my physic this way: Horizontal first then vertical. Since this is an horizontal collision i would used the MTV (-1, -1) and move the actor Y position up by 1 pixel. The actor X is untouched at this point.

But since the returned MTV is (-1, 0), i can't move the actor up the slope the very first time he touche it.

Here is some of my code. If the lisibility is not acceptable, i will be glade to answers yours questions.

//////////////////////////////////////////////////////////////////////////
//Try to find if an Axis can disprove collision.
bool CMath::Sat(CPolygon *_a, CPolygon *_b, CVector &_mtv, int &_solid)
{
float overlap = 1000; //Large value.
CVector smallest(0,0); //MTV (Minimum translation vector). This is the resolving vector.
int numberofcollision = 0;
//For polygon A...
for (int i = 0; i < _a->n; i++)
{
// Get the direction vector
CVector axis = _a->edges[i].dir;

// Get the normal of the vector (90 degrees)
axis = Perp(axis);

// Find the projection of a and b onto axis
CVector p1 = Project(_a,axis), p2 = Project(_b,axis);

// If they do not overlap, then no collision
float o = 1000;
if (!Overlap(p1,p2, o))
return false;

//Update the MTV
else
{
if(o < overlap)
{
overlap = o;
smallest = axis;
}
}
}

// repeat for b
for (int i = 0; i < _b->n; i++)
{
CVector axis = _b->edges[i].dir;
axis = Perp(axis);
CVector p1 = Project(_a,axis), p2 = Project(_b,axis);

float o = 1000;
if (!Overlap(p1,p2, o))
return false;
else
{
if(o < overlap)
{
overlap = o;
smallest = axis;
}
}
}

//No Axis can prove the Polygon is not colliding, so it must be colliding.
//Calculate the MTV;
_solid = smallest.x == 0 || smallest.y == 0;
smallest = Normalize(smallest);
_mtv.x = smallest.x * (overlap +  1); //if we are touching something that is not a slope, always push the actor by 1 pixel.
_mtv.y = smallest.y * (overlap +  1);
return true;
}

//////////////////////////////////////////////////////////////////////////
//
bool CMath::Overlap(CVector _p1, CVector _p2, float &_overlap)
{
if (Contains(_p1,_p2, _overlap) ) return true;

return false;
}

//////////////////////////////////////////////////////////////////////////
//
bool CMath::Contains(CVector _range1, CVector _range2, float &_overlap)
{
_overlap = abs(_range1.y - _range2.x);
return (_range1.y >= _range2.x && _range1.x <= _range2.y);
}

Thank you very much for your time. I will continue searching on my ends and will post the solution if i finds it myself.

Ps. I appologize if my english is bad.

Share on other sites

This is a fundamental problem - the length of (-1, 0) is less than (-1, -1) and is an equally valid separating vector. Just finding the MTV won't help here. Presumably you are trying to implement moving up the slope? SAT alone won't be sufficient here. Sorry this isn't a solution post, but just to let you know you're frustration won't be solved by bugfixing a SAT approach,

Share on other sites

You probably need to do some kind of "step up" check where you check the new position and a sort of "ghost" position where the shape is translated up by the maximum step displacement, then if the new position collides but the "ghost" doesn't, you can manually increase the Y value. This will almost certainly also need to take into account the velocity for the step as well i.e. are we moving towards the slope, falling down onto it etc.

This stuff falls into the realms of character control, which is never neatly solved with conventional physics equations.

Share on other sites

Alright, Thank you. I will try that.

• Game Developer Survey We are looking for qualified game developers to participate in a 10-minute online survey. Qualified participants will be offered a \$15 incentive for your time and insights. Click here to start!

• 11
• 15
• 21
• 26
• 11