# Help finding bug in seperating axis theroem code

My collision detection is inconsistent. I am testing between 2 rectangles. When they are un-rotated, it says they are intersecting way before they touch, but when I rotate one, it works properly. I do not understand why.

When rect1 is rotated 0 or 180 degrees it starts saying collision detected about one rect width apart, but when its rotated at a non 90 degree angle, it works properly.

        // storing rotated points in lists for easy looping to avoid duplicate code
FixedList512<float2> points1 = new FixedList512<float2>();

FixedList512<float2> points2 = new FixedList512<float2>();

bool intersects = true;

for ( int shape = 0; shape < 2; shape++ )
{
if ( shape == 1 )
{
var temp = new FixedList512<float2>();

points1 = points2;
points2 = temp;
}

for ( int a = 0; a < points1.Length; a++ )
{
int b = ( a + 1 ) % points1.Length;
float2 axisProjection = new float2( -( points1[ b ].y - points1[ a ].y ) , points1[ b ].x - points1[ a ].x ); // invert points for normal to line segement

float minR1 = float.MaxValue;
float maxR1 = -float.MaxValue;

for ( int p = 0; p < points1.Length; p++ )
{
float q = points1[ p ].x * axisProjection.x + points1[ p ].y * axisProjection.y; // dot product of current point and axis of projection
minR1 = math.min( minR1 , q );
maxR1 = math.max( maxR1 , q );
}

float minR2 = float.MaxValue;
float maxR2 = -float.MaxValue;

for ( int p = 0; p < points2.Length; p++ )
{
float q = points2[ p ].x * axisProjection.x + points2[ p ].y * axisProjection.y; // dot product of current point and axis of projection
minR2 = math.min( minR2 , q );
maxR2 = math.max( maxR2 , q );
}

if ( !( maxR2 >= minR1 && maxR1 >= minR2 ) ) // break if points dont overlap as we dont have a collision
{
intersects = false;
break;
}
}
}

if ( intersects )
{
Debug.Log( "Intersects" );
}
$$$$

• Your code assumes your vertices are given clockwise or counterclockwise around your perimeter, but your lists appear to be in a Z or hourglass order instead. That alone wouldn't account for the symptoms you describe though. Mar 27, 2021 at 13:03
• Thank you for catching that! Mar 27, 2021 at 20:08

I ended up fixing the problem. Here is my implementation if anyone is interested. As dmgregory pointed out, I was ordering my vertices in z order fashion, silly mistake.

    private void PolygonPolygonSAT( List<float2> verts1 , List<float2> verts2 )
{
List<float2> axes = new List<float2>();
float smallestOverlap = float.MaxValue;
float2 MTVAxis = float2.zero;

for ( int i = 0; i < verts1.Count; i++ ) // collect the axes to project points on, these axes are the normals to each edge of each polygon
{
float2 v1 = verts1[ i ];
float2 v2 = verts1[ i + 1 == verts1.Count ? 0 : i + 1 ];

float2 projectionAxis = new float2( -( v2.y - v1.y ) , v2.x - v1.x ); // get the normal of the edge
}

for ( int i = 0; i < verts2.Count; i++ ) // repeat for polygon 2
{
float2 v1 = verts2[ i ];
float2 v2 = verts2[ i + 1 == verts2.Count ? 0 : i + 1 ];

float2 projectionAxis = new float2( -( v2.y - v1.y ) , v2.x - v1.x );
}

for ( int i = 0; i < axes.Count; i++ ) // now, loop through all projection axes and project each edge onto it
{
float2 axis = axes[ i ];

float min1 = float.MaxValue; // keep track of the minumum and maximum projected points
float max1 = float.MinValue;

for ( int p = 0; p < verts1.Count; p++ )
{
float q = verts1[ p ].x * axis.x + verts1[ p ].y * axis.y; // the projection is the dot product of the edge and the projection axis

min1 = math.min( min1 , q );
max1 = math.max( max1 , q );
}

float min2 = float.MaxValue;
float max2 = float.MinValue;

for ( int p = 0; p < verts2.Count; p++ )
{
float q = verts2[ p ].x * axis.x + verts2[ p ].y * axis.y;

min2 = math.min( min2 , q );
max2 = math.max( max2 , q );
}

float overlap = LineOverlap( min1 , min2 , max1 , max2 ); // return the amount of overlap

if ( overlap <= 0 ) // if there is no overlap then we know no intersection and break
return;

if ( overlap < smallestOverlap )
{
smallestOverlap = overlap;
MTVAxis = axis;
}
}

// now we get the direction of the MTV and multiply it my the overlap/2 to get the displacement for both shapes
float2 dir = new float2( polyPos2.x , polyPos2.z ) - new float2( polyPos1.x , polyPos1.z );
if ( math.dot( MTVAxis , dir ) <= 0 )
MTVAxis *= -1;

MTVAxis = math.normalize( MTVAxis );

float2 displacement1 = -( MTVAxis * smallestOverlap ) / 2;
float2 displacement2 = ( MTVAxis * smallestOverlap ) / 2;

polyPos1 = new float3( polyPos1.x + displacement1.x , polyPos1.y , polyPos1.z + displacement1.y );
polyPos2 = new float3( polyPos2.x + displacement2.x , polyPos2.y , polyPos2.z + displacement2.y );

Debug.Log( "Intersects" );

}
private float LineOverlap( float min1 , float min2 , float max1 , float max2 )
{
float _min1 = math.min( max1 , max2 );
float _max1 = math.max( min1 , min2 );
float diff = _min1 - _max1;

return math.max( 0 , diff );
}
$$$$

• Don't forget to mark this answer as Accepted if it solved your problem. May 4, 2021 at 11:37