Jump to content
  • Advertisement
Sign in to follow this  
evilsanta

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.

If you intended to correct an error in the post then please contact us.

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]

Share this post


Link to post
Share on other sites
Advertisement
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!