# Finding the MTD when using the Separating Axis Theorem

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

## Recommended Posts

EDIT: It would seem that my problem is a sign issue, if I return just smallest (as opposed to smallest *-1) then scenarios where it doesn't work do, and scenarios where it used to no longer do. So I just need a way to determine the sign on the returned vector. I currently have a function that uses the SAT which allows me to check for intersection of rectangles and triangles. I am currently attempting to modify it to return the MTD (minimum translation distance) of the intersection. As it's implemented right now it works in some cases. However many triangles that I pass to the function do not give a correct MTD. It does however detect the overlap correctly. The key point of the code is currently the following.
	Vector2d smallest = axisAll[0] * overlap[0];
for(int x=1; x<5; x++)
{
if((axisAll[x]*overlap[x]).magnitude() < smallest.magnitude())
smallest = axisAll[x] * overlap[x];
}

return (smallest*-1);


Where axisAll is an array of vectors containing all the axis that were used for projection, and overlap is a scalar of the overlap of the 1D lines on the axis. If anyone could tell me how I'm supposed to go about doing this, or what I might be missing I would appreciate it... here is the full code if anyone needs it. I have an idea that it may be because there are multiple things that are the smallest and so it's taking the first one it encounters. However I do not know how to separate out which smallest is the correct one.
Vector2d triRectOverlapV(Vector2d v1, Vector2d v2, Vector2d v3, Vector2d rectPos, Vector2d size)
{
int overlap[5]; Vector2d axisAll[5]; //Used for finding the penetration vector.
Vector2d tri[3]; Vector2d triLines[3];
Vector2d rect[4]; Vector2d rectLines[2];
float minRect, maxRect, minTri, maxTri;

//Setup the triangles verticies in an array.
tri[0] = v1;
tri[1] = v2;
tri[2] = v3;

//Setup the rectangles verticies in an array.
rect[0] = Vector2d(rectPos.x - size.x/2, rectPos.y - size.y/2); //Up Left
rect[1] = Vector2d(rectPos.x - size.x/2, rectPos.y + size.y/2); //Down Left
rect[2] = Vector2d(rectPos.x + size.x/2, rectPos.y - size.y/2); //Up Right
rect[3] = Vector2d(rectPos.x + size.x/2, rectPos.y + size.y/2); //Down Right

//Create the lines that make up the triangle.
triLines[0] = v1-v2;
triLines[1] = v2-v3;
triLines[2] = v3-v1;

//Get the normals of the lines.
triLines[0] = Vector2d(-triLines[0].y, triLines[0].x);
triLines[1] = Vector2d(-triLines[1].y, triLines[1].x);
triLines[2] = Vector2d(-triLines[2].y, triLines[2].x);

//Normalize the lines.
triLines[0] = triLines[0].normalize();
triLines[1] = triLines[1].normalize();
triLines[2] = triLines[2].normalize();

//Since the rectangles are axis aligned the axis are simply the following.
rectLines[0] = Vector2d(1, 0);
rectLines[1] = Vector2d(0, 1);

//Check the rectangles axis.
for(int i = 0; i < 2; i ++)
{
Vector2d axis = rectLines;

//Project the rectangle.
float z = rect[0].dotProduct(axis);
minRect = z; maxRect = z;
for(int e=1; e<4; e++)
{
z = rect[e].dotProduct(axis);
if(z < minRect)
minRect = z;
if(z > maxRect)
maxRect = z;
}

//Project the triangle.
z = tri[0].dotProduct(axis);
minTri = z; maxTri = z;
for(int e=1; e<3; e++)
{
float z = tri[e].dotProduct(axis);
if(z < minTri)
minTri = z;
if(z > maxTri)
maxTri = z;
}

//Store axis for later use. Determine overlap of projected lines.
axisAll = axis;
overlap = 0;
if(minRect < maxTri && maxTri <= maxRect)
overlap = maxTri - minRect;
if(minTri < maxRect && maxRect <= maxTri)
overlap = maxRect - minTri;

//Check if they are not overlapping on the current axis.
if(minTri > maxRect || maxTri < minRect)
return Vector2d(0,0);
}

//Check the triangles axis.
for (int i=0; i<3; i++)
{
Vector2d axis = triLines;

//Project the rectangle.
float z = rect[0].dotProduct(axis);
minRect = z; maxRect = z;
for(int e=1; e<4; e++)
{
z = rect[e].dotProduct(axis);
if(z < minRect)
minRect = z;
if(z > maxRect)
maxRect = z;
}

//Project the triangle.
z = tri[0].dotProduct(axis);
minTri = z; maxTri = z;
for(int e=1; e<3; e++)
{
z = tri[e].dotProduct(axis);
if(z < minTri)
minTri = z;
if(z > maxTri)
maxTri = z;
}

//Store axis for later use. Determine overlap of projected lines.
axisAll[i+2] = axis;
overlap[i+2] = 0;
if(minRect < maxTri && maxTri <= maxRect)
overlap[i+2] = maxTri - minRect;
if(minTri < maxRect && maxRect <= maxTri)
overlap[i+2] = maxRect - minTri;

//Check if they are not overlapping on the current axis.
if(minTri > maxRect || maxTri < minRect)
return Vector2d(0,0);
}

//Find smallest penetration vector.
Vector2d smallest = axisAll[0] * overlap[0];
for(int x=1; x<5; x++)
{
if((axisAll[x]*overlap[x]).magnitude() < smallest.magnitude())
smallest = axisAll[x] * overlap[x];
}

return (smallest*-1);
}


[Edited by - evilsanta on November 1, 2009 10:34:10 AM]

1. 1
2. 2
3. 3
4. 4
frob
14
5. 5

• 16
• 12
• 20
• 12
• 19
• ### Forum Statistics

• Total Topics
632168
• Total Posts
3004529

×