Sign in to follow this  
EduardoMoura

SAT, something is wrong I just don't know what....

Recommended Posts

I have implement this algorithm numerous times before, and it worked flawlessly everytime, right this is giving me trouble, and after rewritting this 3 times already I give up trying to find the error, maybe a set of new eyes can pinpoint it to me?

My problem is that it is detecting collisions where it shouldn't, and I can't seem to find out why.

 

 

public static class SAT
    {

        public class MTV
        {
            public Vector2 Axis;
            public float Magnitude;
            public bool Collided = true;
        }

        public static Vector2[] GetAxes(Vertices vert)
        {
            Vector2[] axes = new Vector2[vert.Count];
            // loop over the vertices
            for (int i = 0; i < vert.Count; i++)
            {
                // get the current vertex
                Vector2 p1 = vert[i];
                // get the next vertex
                Vector2 p2 = vert[vert.NextIndex(i)];
                // subtract the two to get the edge vector
                Vector2 edge = p1 - (p2);
                // get either perpendicular vector
                Vector2 normal = new Vector2(edge.Y, -edge.X);
                // the perp method is just (x, y) => (-y, x) or (y, -x)
                axes[i] = normal;
                axes[i].Normalize();
            }
            return axes;
        }


        public static MTV CheckCollision(Vertices polygon1,Vertices polygon2)
        {
            float overlap = float.PositiveInfinity;// really large value;
            MTV MTV = new SAT.MTV();
            MTV.Collided = false;
            Vector2 smallest = Vector2.Zero;
            Vector2[] axes1 = GetAxes(polygon1);
            Vector2[] axes2 = GetAxes(polygon2);
            // loop over the axes1
            for (int i = 0; i < axes1.Length; i++)
            {
                Vector2 axis = axes2[i];
                float min, max, min2, max2;
                // project both shapes onto the axis
                polygon1.ProjectToAxis(ref axis, out min, out max);
                polygon2.ProjectToAxis(ref axis, out min2, out max2);
                // do the projections overlap?
                float d1, d2;
                d1 = min - max2;
                d2 = min2 - max;
                if (d1 > 0 || d2 > 0) //no intersection
                {
                    // then we can guarantee that the shapes do not overlap
                    return MTV;
                }
                else
                {
                    // get the overlap
                    float o = d1 - d2;
                    // check for minimum
                    if (o < overlap)
                    {
                        // then set this one as the smallest
                        overlap = o;
                        smallest = axis;
                    }
                }
            }
            // loop over the axes2
            for (int i = 0; i < axes2.Length; i++)
            {
                Vector2 axis = axes2[i];
                float min, max, min2, max2;
                // project both shapes onto the axis
                polygon1.ProjectToAxis(ref axis,out min, out max );
                polygon2.ProjectToAxis(ref axis, out min2, out max2);
                // do the projections overlap?
                float d1, d2;
                d1 = min - max2;
                d2 = min2 - max;
                if ( d1 > 0 || d2 > 0 ) //no intersection
                {
                    // then we can guarantee that the shapes do not overlap
                    return MTV;
                }
                else
                {
                    // get the overlap
                    float o = d1 - d2;
                    // check for minimum
                    if (o < overlap)
                    {
                        // then set this one as the smallest
                        overlap = o;
                        smallest = axis;
                    }
                }
            }
            MTV.Collided = true;
            MTV.Axis = smallest;
            MTV.Magnitude = overlap;

            return MTV;


        }
    }

 

 

If anyone asked here is the Project to Axis from Vertices( its just List) :

 

public void ProjectToAxis(ref Vector2 axis, out float min, out float max)        {            // To project a point on an axis use the dot product            float dotProduct = Vector2.Dot(axis, this[0]);            min = dotProduct;            max = dotProduct;             for (int i = 0; i < Count; i++)            {                dotProduct = Vector2.Dot(this[i], axis);                if (dotProduct < min)                {                    min = dotProduct;                }                else                {                    if (dotProduct > max)                    {                        max = dotProduct;                    }                }            }        }

 

 

 

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this