0
\$\begingroup\$

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>();
        points1.Add( bl_r );
        points1.Add( br_r );
        points1.Add( tl_r );
        points1.Add( tr_r );

        FixedList512<float2> points2 = new FixedList512<float2>();
        points2.Add( bl_r2 );
        points2.Add( br_r2 );
        points2.Add( tl_r2 );
        points2.Add( tr_r2 );

        bool intersects = true;

        for ( int shape = 0; shape < 2; shape++ )
        {
            if ( shape == 1 )
            {
                var temp = new FixedList512<float2>();
                temp.Add( bl_r );
                temp.Add( br_r );
                temp.Add( tl_r );
                temp.Add( tr_r );

                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" );
        }
```
\$\endgroup\$
2
  • \$\begingroup\$ 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. \$\endgroup\$ – DMGregory Mar 27 at 13:03
  • \$\begingroup\$ Thank you for catching that! \$\endgroup\$ – Tree3708 Mar 27 at 20:08
0
\$\begingroup\$

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
            axes.Add( projectionAxis );
        }

        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 );
            axes.Add( projectionAxis );
        }

        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 );
    }
```
\$\endgroup\$
1
  • \$\begingroup\$ Don't forget to mark this answer as Accepted if it solved your problem. \$\endgroup\$ – DMGregory May 4 at 11:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.