http://www.codeproject.com/KB/GDI-plus/PolygonCollision.aspx?print=true I'm using the example given above as the main basis of my reading. In it, it shows the below psuedo code which is what I am following. For each edge of both polygons { Find the axis perpendicular to the current edge. Project both polygons on that axis. If these projections don't overlap, the polygons don't intersect (exit...) } I know how to find the axis perpendicular to the edge, however I am unsure how to project the polygons onto the axis. I've read that you just do a vector projection of each vertice on each polygon. The articles say to find the min and max values of the pojection for each polygon. If the min or max of one polygon is between the min and max of the other polygon then there is a possible collision. However, when I started thinking about it, a vector projection returns a vector, not a scalar. How then can you get a min and max value from the projection? I thought about scalar projections as well since it returns a scalar, however, when I checked the code provided at the link above it uses a vector projection. I know I could just use the code provided at CodeProject, but I would perfer to understand the reasoning behind everything.

You take only the size of the projection. To do it, you make a dotproduct of the axis vector and a vector pointing from [0,0] to a vertex of the polygon. It will give you a scalar. Then you iterate over all vertices of your polygon and take minimum and maximum of these scalars. It will determine an interval. Then you do the same thing with the second polygon and it will also give you an interval. If these intervals overlap, then these polygons overlap along this axis.

Looking at your link this is what they do, just look at the function ProjectPolygon.

You also might find useful other links to SAT: http://physics.hardwire.cz/index.php?action=show&parent_id=45&sortby=order

So then I just continue what I am doing and take the magnitude of the calculated projection vectors :) Thanks.

Quote:Original post by Trox
So then I just continue what I am doing and take the magnitude of the calculated projection vectors :) Thanks.

You don't need to take the magnitude of any vector; the projections themselves are already scalars.

Remember that the dot product (which is what we're using here) returns a scalar, which is exactly what we're looking for.

Can you post the bit of code that's causing you confusion?

Its the conversion from the algorithm to code. A vector projection does not return a scalar like you are saying.

If you project vector A onto vector B you use the formula:

[ A * (A dot B) ] / ( [ magnitute(A) ] ^ 2 )

In general its a vector times a scalar divided by a scalar which returns a vector. That is why I am confused. I know that a vector projection returns a vector. I also know that the vector projection formula isn't simply the dot product of two vectors. In all the code examples I've found the dot product is being used instead of the vector projection formula above. Why?

This is the code I am using, though its the thought process above that has confused me.

This is my implementation of the SAT

        /**          * Foreach edge of the polygons         * {         *     I)   Find the axis perpendicular to the edge         *          a) Take the left hand normal         *     II)  Project both polygons onto that axis         *          Instantiate min and max values for each polygon         *          Foreach polygon         *          {         *              Foreach vertice on the polygon         *              {         *                  a) Project the vertice onto the axis         *                  b) Take the length of the projection         *                  c) Compare the current min and max values to the length of the projection, keeping the better corresponding values         *                             *                        Overlap conditions         *          *                        _______    _______  Projection Shadow         *                        |-----|         *                                   |-----|  No Overlap         *                        A     B    C     D         *          *                        _______    _______  Projection Shadow         *                                   |-----|         *                        |-----|             No Overlap         *                        C     D    A     B         *          *                        __________________  Projection Shadow         *                        |----------|         *                              |----------|  Overlap         *                        A     C    B     D         *          *                        __________________  Projection Shadow         *                              |----------|         *                        |----------|        Overlap         *                        C     A    D     B         *              }         *          }         *     III) If the projections don't overlap, the polygons don't intersect (exit the loop)         *              a) If the min or max of one polygon is between the min and max of the other polygon, then a collision exists         * }         **/        private void SeparatingAxisTheorem(Polygon a, Polygon b)        {            bool exitLoops = false;            Polygon[] polygons = new Polygon[]{a, b};            foreach (Polygon p in polygons)            {                Vector[] edges = p.Edges;                foreach (Vector edge in edges)                {                    Vector axis = edge.LeftOrthogonal;                    const int numberOfPolygons = 2;                    float[] polygonMin = new float[numberOfPolygons];                    float[] polygonMax = new float[numberOfPolygons];                    for (int i = 0; i < numberOfPolygons; i++)                    {                        polygons.ProjectOnTo(axis, ref polygonMin, ref polygonMax);                    }                    /**                     * For the above examples                     *    A = polygonMin[0]                     *    B = polygonMax[0]                     *    C = polygonMin[1]                     *    D = polygonMax[1]                     **/                    System.Diagnostics.Debug.Print(polygonMin[0] + ", " + polygonMax[0] + " " + polygonMin[1] + ", " + polygonMax[1]);                    if (                        (polygonMin[0] < polygonMax[0] && polygonMax[0] < polygonMin[1] && polygonMin[1] < polygonMax[1])                        ||                        (polygonMin[1] < polygonMax[1] && polygonMax[1] < polygonMin[0] && polygonMin[0] < polygonMax[0])                        )                    {                        // No collision exists, exit the loop                        exitLoops = true;                        MessageBox.Show("Collision not found!");                    }                    if (exitLoops)                        break;                }                if (exitLoops)                    break;            }            // A collision was found!            MessageBox.Show("Collision found!");        }

Polygon helper functions used above

public void ProjectOnTo(Vector v, ref float min, ref float max)        {            min = 1f;            max = -1f;            if(needEdgeUpdate)                CreateEdges();            foreach (Vector vertice in m_Edges)            {                Vector projectedVector = vertice.VectorProjectOnto(v);                float projectedLength = projectedVector.Length;                if (projectedLength < min)                    min = projectedLength;                else if (projectedLength > max)                    max = projectedLength;            }        }

Vector helper functions used above

        public float Length        {            get { return (float)Math.Sqrt(m_X * m_X + m_Y * m_Y); }        }        public Vector LeftOrthogonal        {            get { return new Vector(-m_Y, m_X); }        }        public Vector VectorProjectOnto(Vector v)        {            return v.ScalarMultiply(this.DotProduct(v) / v.Length * v.Length);        }        public float DotProduct(Vector v)        {            return m_X * v.X + m_Y * v.Y;        }

Ok, I think it's just the terminology that's causing confusion here...

When I use the term 'projection' in the context of the SAT, I'm referring to the scalar projection of one vector onto another, which can be calculated using the dot product.

To illustrate, here's some pseudocode showing how to project a polygon onto an axis:

Range ProjectPolygon(Vector verts[], Vector axis){    float min = FLOAT_MAX;    float max = -FLOAT_MAX;    for (each Vector in verts) {        float dot = dot_product(vert, axis);        min = minimum(min, dot);        max = maximum(max, dot);    }    return Range(min, max);}

And that's really all there is to it.

'Hope that clears things up a bit.

That is exaclty what the confusion was. Thats why my first post mentioned the difference between the scalar and the vector projections. Thanks for the help.

Quote:Original post by Trox
That is exaclty what the confusion was. Thats why my first post mentioned the difference between the scalar and the vector projections. Thanks for the help.

Oops, sorry - by the time I got to the end of the thread I had forgotten the mention of scalar vs. vector projections in your original post :)