# 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.

## 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 on other sites
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 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 .

1. 1
2. 2
3. 3
4. 4
Rutin
15
5. 5

• 13
• 26
• 10
• 11
• 9
• ### Forum Statistics

• Total Topics
633724
• Total Posts
3013556
×