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, 2021 at 13:03
  • \$\begingroup\$ Thank you for catching that! \$\endgroup\$
    – Tree3708
    Mar 27, 2021 at 20:08

1 Answer 1

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, 2021 at 11:37

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .