Re: SAT question... sorry

crabby — Fri, 24 Apr 2009 22:01:40 GMT

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)); 
        
                                        }

SAT question... sorry

crabby — Fri, 24 Apr 2009 02:22:00 GMT

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]; 
        
                                } 
        
                        }

Game Algorithms

Re: SAT question... sorry

SAT question... sorry