Jump to content
  • Advertisement
Sign in to follow this  
Deliverance

Swept SAT problem (code inside)

This topic is 3339 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

I'm trying to implement SWEPT Separating Axis Theorem in 2D by tracking the first and last time the objects are not separated. It seems to work for static tests and even swept tests for rectangle vs rectangle but for other shapes i get false negatives. Here is the relevant code:
	float t0 = 0;
	float t1 = 1000000.0f;				
	float tMax = 1.0f;
	
	for (i=0; i<axes.size(); i++)
	{
		float min1,max1,min2,max2,overlapMin,overlapMax;
		getProjectionInterval(poly1, pos1, axes, min1, max1);
		getProjectionInterval(poly2, pos2, axes, min2, max2);
		
		float speed = dot(axes, relativeVel);
		//printf("speed is: %f %d\n", speed, axes.size());

		if ( max1 < min2 ) 
		{ 
			if (speed<=0.0f)
				return false;
			
		//	printf("max1 min2 %d\n", i);
			float t = (min2 - max1) / speed;
			t0 = MAX(t, t0);
			
			if (t0 > tMax)
				return false;
			
			t = (max2 - min1) / speed;
			t1 = MIN(t, t1);
			
		//	printf("%f %f\n", t0, t1);
			
			if (t0 > t1)
				return false;
		}else
		if ( max2 < min1 ) 
		{ 
			if (speed>=0.0f)
				return false;
			
		//	printf("max2 min1 %d\n", i);
			float t = (-min1 + max2) / speed;
			t0 = MAX(t, t0);
			
			if (t0 > tMax)
				return false;			
			
			t = (-max1 + min2) / speed;
			t1 = MIN(t, t1);
			
			if (t0 > t1)
				return false;
			
		//	printf("%f %f\n", t0, t1);			
		}					
		else
		{
			if ( speed > 0 ) 
			{ 
				float t = (max1 - min2)/speed; 
				t1 = MIN(t, t1);
				
				if (t0 > t1)
					return false;
			} 
			else if ( speed < 0 ) 
			{ 
				float t = (min1 - max2)/speed;
				
				t1 = MIN(t, t1);
				
				if (t0 > t1)
					return false;				
			}		
		}
	}

Can anyone spot any obvious problem?

Share this post


Link to post
Share on other sites
Advertisement
maybe because your axes are your edge directions, instead of being the edge normals. for rectangles, since the edges are all perpendicular, it sort of works, but for other shapes, use the normal to edges.

otherwise, maybe here

Quote:

else
{
if ( speed > 0 )
{
float t = (max1 - min2)/speed;
t1 = MIN(t, t1);

if (t0 > t1)
return false;
}
else if ( speed < 0 )
{
float t = (min1 - max2)/speed;

t1 = MIN(t, t1);

if (t0 > t1)
return false;
}
}


You dont seem to try to estimate t0 in that case. I'm not sure that's correct (could be).

if it is false negatives, it should be easy to track down. Just breakpoint where it returns false, and check if the values for t0 and t1 make sense. You can always render the shapes at t0 and t1 and double check by hand.

Share this post


Link to post
Share on other sites
Quote:
Original post by oliii
maybe because your axes are your edge directions, instead of being the edge normals. for rectangles, since the edges are all perpendicular, it sort of works, but for other shapes, use the normal to edges.

otherwise, maybe here

Quote:

else
{
if ( speed > 0 )
{
float t = (max1 - min2)/speed;
t1 = MIN(t, t1);

if (t0 > t1)
return false;
}
else if ( speed < 0 )
{
float t = (min1 - max2)/speed;

t1 = MIN(t, t1);

if (t0 > t1)
return false;
}
}


You dont seem to try to estimate t0 in that case. I'm not sure that's correct (could be).

if it is false negatives, it should be easy to track down. Just breakpoint where it returns false, and check if the values for t0 and t1 make sense. You can always render the shapes at t0 and t1 and double check by hand.


Yeah i do use normals, here's the relevant code:

unsigned int i;
for (i=0; i<poly1.size(); i++)
{
// calculate edge vector
Vector3 edgeVector = poly1[(i + 1) % poly1.size()] - poly1;

// this returns a perpendicular vector onto the edge
Vector3 axis = Vector3(-edgeVector.y, edgeVector.x, 0.0f);

axis.normalize();

axes.push_back(axis);
}

// next check axes perpendicular tu poly2 edges
for (i=0; i<poly2.size(); i++)
{
// calculate edge vector
Vector3 edgeVector = poly2[(i + 1) % poly2.size()] - poly2;

// this returns a perpendicular vector onto the edge
Vector3 axis = Vector3(-edgeVector.y, edgeVector.x, 0.0f);

axis.normalize();

axes.push_back(axis);
}




I guess i'll try to find a case and test it by hand , although i get false negatives on roughly approximated circles and ellipsoids and there are a lot of axes to test :D.(i know there are better ways but this is just for testing purposes).

When the intervals are not disjoint then it means that they are intersected and consider the intersection time t0current=0.0f, but i always take the maximum from the t0 minimum's so that why there is no need for code there .

Share this post


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

  • Advertisement
×

Important Information

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

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!