XNA Creators Club Online
Page 1 of 1 (2 items)
Sort Posts: Previous Next

SAT question... sorry

Last post 24/04/2009 22:01 by crabby. 1 replies.
  • 24/04/2009 2:22

    SAT question... sorry

    I know these kinds of questions have been asked numerous times and I really have been doing a ton of searching and testing on this topic. It's just that I'm stuck on this one bug, and I need some help.

    Here's the sitrep. I'm trying to maek a 2d collision system using SAT. I've started off with CheezCB's AA triangles example and I've been adding to it and changing it as I try to understand SAT. I think I've got a basic understanding of it now, but obviously not enough or I wouldn't be having this problem. Right now I'm testing with a AABB against a diamond shaped rectangle. It works for the most part, except when you collide from the top slopes which causes the AABB to skip through the diamond. I've been looking at the vectors I calculated to get out of the diamond, and the values are right, but their signs are the opposite of what I would need to move out of a collision. So it'll tell me to move +1 to the right, when I should move -1. It seems like it should be an easy enough fix, but I can't figure out what to do.

    Here's the main collision code. I know it's a mess of needless declaration and excessive lists. I figure I'll clean up when I have something that works properly. There are a couple functions called that I didn't add the code for. GetBoundingBoxCollisions() just returns a list of InteractibleObjs that fail a simple boundingbox test. GetPolygonVertices() returns a vector2 list with all the vertices for the AABB and the diamond(4 each). Caller is the AABB, Candidate is the diamond. the first thing this code does is go through each polygon and subtract one point from the one in front to figure out all the axes I need to project on. Then it projects each polygon onto each axis adn finds a minimum and max value. For axes that aren't horizontal or vertical,  I do some calculations to find out how much to rotate the projected point to fit it onto a horizontal or vertical axis. That's why I only grab the value of .X when I do a vector2.Transform() in hte projection code. After the projection code I do some tests to see if the projections overlap.

    As I have said, I'm pretty sure I'm getting the right values and the rotation of non-vertical and non-horizontal projections seems to work accurately when I inset breakpoints and check what the projection points are. I jsut get the wrong positive and negatives so that I move into the diamond instead of out.

    Here's a link to the project(60kb)
    http://host-a.net/killerdhawk/SAT%20collision%20tests.rar

      List<InteractibleObj> lBBoxes = new List<InteractibleObj>(); 
     
                //*********************TESTING 
                List<Vector2> rotatedcaller = new List<Vector2>(); 
                List<Vector2> rotatedcandidate = new List<Vector2>(); 
                //****************************/TESTING 
     
                //jsut check for the first iObj(palyer ) right now 
                if(true
                { 
                    InteractibleObj caller = iObjs[0]; 
                    lBBoxes = GetBoundingBoxCollisions(caller); 
     
                    foreach (InteractibleObj intbbox in lBBoxes) 
                        if (intbbox != null
                        { 
                            int edges; int foundAxes; 
                            List<Vector2> lProjectionAxes = new List<Vector2>(); 
                            List<Vector2> lCallerPolyVertices = caller.GetPolygonVertices(); 
                            List<Vector2> lCandidatePolyVertices = intbbox.GetPolygonVertices(); 
                            Vector2 workVec, flippedWorkVec; 
                    #region Get projection axes 
                            //Get projection axes for calling interactibleobj 
                            edges = lCallerPolyVertices.Count; 
     
                            for (int i = 0; i < edges ; ++i) 
                            { 
                                workVec = lCallerPolyVertices[(i + 1) % edges] - lCallerPolyVertices[i]; 
                                workVec.Normalize(); 
                                flippedWorkVec = new Vector2(-workVec.X, -workVec.Y); 
     
                                for (int j = 0; j < lProjectionAxes.Count; ++j) 
                                    if (workVec == lProjectionAxes[j] || flippedWorkVec == lProjectionAxes[j]) 
                                    { 
                                        workVec = Vector2.Zero; 
                                        break
                                    } 
                                 
                                if(workVec != Vector2.Zero) 
                                    lProjectionAxes.Add(workVec); 
     
                            } 
     
                            foundAxes = lProjectionAxes.Count-1; 
                            //Get projection axes for colliding interactibleobj 
                            edges = lCandidatePolyVertices.Count; 
     
     
     
                            for (int i = 0; i < edges; ++i) 
                            { 
                                workVec = lCandidatePolyVertices[(i + 1) % edges] - lCandidatePolyVertices[i]; 
                                workVec.Normalize(); 
                                flippedWorkVec = new Vector2(-workVec.X, -workVec.Y); 
     
                                for (int j = 0; j < lProjectionAxes.Count; ++j) 
                                    if (workVec == lProjectionAxes[j] || flippedWorkVec == lProjectionAxes[j]) 
                                    { 
                                        workVec = Vector2.Zero; 
                                        break
                                    } 
                                 
                                if(workVec != Vector2.Zero) 
                                    lProjectionAxes.Add(workVec); 
                            } 
                    #endregion 
                    #region Project polygon onto each axes and test for collisions 
     
                            float candidateDP, callerDP; 
                            double axisRotationAmount; 
                            Vector2 callerPolyProj, candidatePolyProj, tempVector, tempVector2; 
     
                            List< Vector2> callerProjectionOut = new List<Vector2>(); 
                            List<Vector2> lTest = new List<Vector2>(); 
     
                            //Project each poloygon onto each axis and then check if they overlap. 
                            foreach (Vector2 pAxes in lProjectionAxes) 
                            { 
                                callerPolyProj = new Vector2(10000000000, -100000); 
                                candidatePolyProj = callerPolyProj; 
     
                                //Axes that are not 0,1 or 1,0 need their points rotated onto these axis.  
                                tempVector = (Vector2.Dot(lCallerPolyVertices[0], pAxes) * pAxes); 
                                tempVector2 = tempVector - (Vector2.Dot(lCandidatePolyVertices[0], pAxes) * pAxes); 
                                axisRotationAmount = Math.PI - Math.Atan2(tempVector2.Y, tempVector2.X) + Math.PI; 
     
     
     
                                //project caller onto the current axis 
                                for (int i = 0; i < lCallerPolyVertices.Count; ++i) 
                                { 
                                    callerDP = Vector2.Dot(lCallerPolyVertices[i], pAxes); 
     
                                    if (pAxes != Vector2.UnitX && pAxes != Vector2.UnitY) 
                                    { 
                                        tempVector = callerDP * pAxes; 
                                        rotatedcaller.Add(tempVector); 
                                        callerDP = Vector2.Transform(tempVector, Matrix.CreateRotationZ((float)axisRotationAmount)).X; 

                                    } 
     
     
                                    if (callerDP < callerPolyProj.X) 
                                        callerPolyProj.X = callerDP; 
                                    if (callerDP > callerPolyProj.Y) 
                                        callerPolyProj.Y = callerDP; 
                                } 
     
                                //project candidate onto the current axis 
                                for (int i = 0; i < lCandidatePolyVertices.Count; ++i) 
                                { 
                                    candidateDP = Vector2.Dot(lCandidatePolyVertices[i], pAxes); 
     
                                    if (pAxes != Vector2.UnitX && pAxes != Vector2.UnitY) 
                                    { 
                                        tempVector = candidateDP * pAxes; 
                                        rotatedcandidate.Add(tempVector); 
                                        candidateDP = Vector2.Transform(tempVector, Matrix.CreateRotationZ((float)axisRotationAmount)).X; 
                                    } 
     
     
                                    if (candidateDP < candidatePolyProj.X) 
                                        candidatePolyProj.X = candidateDP; 
                                    if (candidateDP > candidatePolyProj.Y) 
                                        candidatePolyProj.Y = candidateDP; 
                                } 
     
     
     
     
                                //Comparison check to see if the projections overlap 
                                if (callerPolyProj.X < callerPolyProj.Y && callerPolyProj.Y < candidatePolyProj.X 
                                 || 
                                  candidatePolyProj.X < candidatePolyProj.Y && candidatePolyProj.Y < callerPolyProj.X) 
                                { 
                                    //No overlap, meaning no collision, so exit loop 
                                    callerProjectionOut.Clear(); 
                                    callerProjectionOut.Add(Vector2.Zero); 
                                    break
     
                                } 
                                else //calculate vector to get caller unstuck 
                                { 
                                    if (callerPolyProj.X <= candidatePolyProj.X) 
                                    { 
                                        callerProjectionOut.Add((candidatePolyProj.X - callerPolyProj.Y) * pAxes); 
                                    } 
                                    if (candidatePolyProj.X <= callerPolyProj.X) 
                                    { 
                                         
                                        callerProjectionOut.Add((candidatePolyProj.Y - callerPolyProj.X) * pAxes); 
                                    } 
                                     
     
                                    //callerProjectionOut.Clear(); 
                                    //callerProjectionOut.Add(new Vector2(-mx,-my)); 
     
     
                                } 
     
     
     
     
                            } 
                    #endregion 
     
     
                            callerProjectionOut.Sort(intbbox.vecCom); 
                            caller.CurrPosition += callerProjectionOut[0]; 
     
                        } 
                     
     
                     
                } 


  • 24/04/2009 22:01 In reply to

    Re: SAT question... sorry

    EDIT: I'm an idiot. Scrap everything from tempVector down and replace with the below. I don't know why I didn't realise the projection axes should be used to rotate the projections onto a horizontal plane. Oh well, at least it's working with non axis aligned shapes. Jsut tried a hexagon and it works pretty well, although it is treating certain pointy parts like they were a flat edge, that might just be the resolution. It should be good enough for my next step, adding rotation to my polygon class.
                                axisRotationAmount = (2 * Math.PI - Math.Atan2(pAxes.Y, pAxes.X));                               



    Found a fix that works works for AABB against the diamond, but not so great for AA triangles. I think the problem has a lot to do with the angle I'm calculating for axisRotationAmount.

    Here's the code I added/modified for the curious. It goes right after the foreach Vector2 pAxes in lProjectionAxes. Time to go look over the metanet tutorials again, sigh.
                                callerPolyProj = new Vector2(10000000000, -100000); 
                                candidatePolyProj = callerPolyProj; 
     
                                //Axes that are not 0,1 or 1,0 need their points rotated onto these axis.  
                                tempVector =  (Vector2.Dot(caller.poly.Center, pAxes) * pAxes); 
                                tempVector2 = tempVector - (Vector2.Dot(lCandidatePolyVertices[0], pAxes) * pAxes); 
     
                                axisRotationAmount = (2 * Math.PI - Math.Atan2(tempVector2.Y, tempVector2.X)); 
                                 
                                if (MathHelper.ToDegrees((float)axisRotationAmount) % 360 < 180) 
                                { 
                                    tempVector = (Vector2.Dot(lCandidatePolyVertices[0], pAxes) * pAxes); 
                                    tempVector2 = tempVector - (Vector2.Dot(caller.poly.Center, pAxes) * pAxes); 
     
                                    axisRotationAmount = (2 * Math.PI - Math.Atan2(tempVector2.Y, tempVector2.X)); 
                                } 

Page 1 of 1 (2 items) Previous Next