Java-Gaming.org Hi !
 Featured games (90) games approved by the League of Dukes Games in Showcase (739) Games in Android Showcase (224) games submitted by our members Games in WIP (820) games currently in development
 News: Read the Java Gaming Resources, or peek at the official Java tutorials
 Home Help Search Login Register
Pages: [1]
 ignore  |  Print
 Having problems implementing SAT (Separating Axis Theorem)  (Read 3149 times) 0 Members and 1 Guest are viewing this topic.
kingAree

Senior Newbie

Exp: 4-6 months

 « Posted 2017-04-15 13:59:11 »

I have tried to follow a few guides explaining the theory behind Sat but this implementation is not working for me, Could I get some help?

here is my class with my SAT code, its part of the DevEntity class, every object that I want to implement SAT extends this class, and the vertex points are set in those classes.

 1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26  27  28  29  30  31  32  33  34  35  36  37  38  39  40  41  42  43  44  45  46  47  48  49  50  51  52  53  54  55  56  57  58  59  60  61  62  63  64  65  66  67  68  69  70  71  72  73 `      protected Vector2[] axis;        public void obtainEdges(){      axis  = new Vector2[vertices.length];      for(int i = 0; i < vertices.length; i++){                  Vector2 e1 = vertices[i];                  Vector2 e2 = vertices[i + 1 == vertices.length ? 0 : i + 1];                  Vector2 edge = e1.subtract(e2);                  Vector2 perp = edge.perp(edge);         axis[i] = perp;      }   }      public Vector2 projectAxis(Vector2 axis){      float min = axis.dot(vertices[0]);      float max = min;            for(int i = 1; i < vertices.length; i++){         float proj = axis.dot(new Vector2(x + vertices[i].x, y + vertices[i].y));                  if(proj < min){            min = proj;         }                  if(proj > max){            max = proj;         }      }            return new Vector2(min, max);   }      public boolean separatingAxisTheorem(){      obtainEdges();      for(DevEntity e : handler.getDevWorld().getDevM().getDevEntities()){         Vector2[] axes1 = axis;         Vector2[] axes2 = e.axis;                        if(e.equals(this))            return false;         for(int i = 0; i < axes1.length; i++){            Vector2 axis = axes1[i];                        Vector2 p1 = projectAxis(axis);            Vector2 p2 = e.projectAxis(axis);                        if(!p1.overlap(p2)){               return false;            }         }                  for(int i = 0; i < axes2.length; i++){            Vector2 axis = axes2[i];                        Vector2 p1 = projectAxis(axis);            Vector2 p2 = e.projectAxis(axis);                        if(!p1.overlap(p2)){               return false;            }         }               }      return true;   }`

here's my Vector Class

 1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26  27  28  29  30  31  32  33  34  35  36  37  38  39  40  41  42  43  44  45  46  47  48  49  50  51  52 `package shapegame.engine;import java.util.Vector;public class Vector2 {      public float x, y;         public Vector2(float x, float y){      this.x = x;      this.y = y;   }      public Vector2(Vector2 vec){      this.x = vec.x;      this.y = vec.y;   }      public float dot(Vector2 b){      return x * b.x + y * b.y;   }      public Vector2 normalize(Vector2 vec){      float mag = (float) Math.sqrt(vec.x * vec.x + vec.y * vec.y);      Vector2 b = new Vector2(vec.x/mag, vec.y/mag);      return b;   }      public Vector2 subtract(Vector2 vec){      return new Vector2(x - vec.x, y - vec.y);   }      public Vector2 perp(Vector2 vec){      Vector2 p = new Vector2(-vec.y, vec.x);      return p;   }      public boolean overlap(Vector2 vec){         if(y < vec.x || vec.y < x){            return false;         }      return true;   }   }`

bmanmcfly
 « Reply #1 - Posted 2017-04-17 16:59:56 »

I had struggled with implementing a SAT algorithm, some time ago, I wound up using the algorithm supplied by libgdx (intersector)... and even once I got the premade algorithm there were still issues.

Without scrutinizing the specific code you laid out, beyond that it seems correct, even with the SAT algorithm, what I found I had to do to get it to work without tunneling was:
- copy the current position
- get the new position
- run the sat on the new position
- test the MTV to ensure that it's going to send you to the right edge
- if that test fails, then from each point on the first object make a line from each point + the movement vector and test that line for intersection.
- move the object to the coordinates of the shortest line that intersected

in that way I prevented tunneling even when movement was pushed to absurd speeds.

Good luck.

kingAree

Senior Newbie

Exp: 4-6 months

 « Reply #2 - Posted 2017-04-18 14:10:29 »

Thanks for the reply, I guess I'll have to do way more testing in general as the SAT method is boolean and it won't change from false no matter what I seem to do, tunnelling isn't a problem for me yet.
 Games published by our own members! Check 'em out!
bmanmcfly
 « Reply #3 - Posted 2017-04-18 21:27:00 »

Thanks for the reply, I guess I'll have to do way more testing in general as the SAT method is boolean and it won't change from false no matter what I seem to do, tunnelling isn't a problem for me yet.

Unfortunately, when I tried to write the SAT algorithm for myself, it did not go well... this was the one that finally worked, but even that took some work.

https://github.com/libgdx/libgdx/blob/master/gdx/src/com/badlogic/gdx/math/Intersector.java

Unfortunately, I'm a bit too much of a noob to offer much better advice than to go through the process of drawing the lines and stepping through.

What I can do is bring up some of the factors that were holding me back:
- I was not using translated polygons, so, while I was drawing the polygons correctly, the actual polygons were at a different position.
- I was not properly calculating the projection vector, this was tricky and I didn't realize it until I started drawing all the results (that was right before I gave up on writing my own, because I realized I was just working the math wrong)
- Once I got the algorithm, I had trouble calculating the MTV, which was partly because while I was adding the speed I wasn't scaling to deltaT for the MTV calculation...

There's a lot of things that can go wrong, and I do wish I could offer better help, but I also remember how there weren't many implementations of SAT that people would share, except in c# or c++, that I could find online.  At least with the example, you can compare code that definitely does work with what you have... good luck.
kingAree

Senior Newbie

Exp: 4-6 months

 « Reply #4 - Posted 2017-04-20 15:45:59 »

I think drawing my axes and projections onto the screen will be the best way to help me figure this out, I definitely think that visualising these problems is one of the best ways of dealing with this, currently I am not using Polygon's, instead my shapes are just classes with the vertices defined in an array, I then draw the image/shape to the screen.

I'll have a good browse through your code, thanks for posting it.
bmanmcfly
 « Reply #5 - Posted 2017-04-20 17:59:10 »

I think drawing my axes and projections onto the screen will be the best way to help me figure this out, I definitely think that visualising these problems is one of the best ways of dealing with this, currently I am not using Polygon's, instead my shapes are just classes with the vertices defined in an array, I then draw the image/shape to the screen.

I'll have a good browse through your code, thanks for posting it.

Since a polygon is just an array of vertices either way, that shouldn't be an issue...

Just to be clear, that's not code that I've written, that is the intersector class that is included in libgdx.  Part of why I didn't want to risk troubleshooting the code you supplied at the top, it looks similar, and the process sounds the same, but since I struggled with the same even after having code that works, I didn't want to take many chances there.

Let us know how the visualizations work out, I suspect it will help to highlight the part that's not working.
kingAree

Senior Newbie

Exp: 4-6 months

 « Reply #6 - Posted 2017-04-21 09:09:34 »

I was wondering why you said you were a noob! that code was impressive, I'll post my findings back here for sure.

and true about the Polygons just being vertices although it seems creating an actual Polygon object has benefits due to being able to use AffineTransforms.
bmanmcfly
 « Reply #7 - Posted 2017-04-21 15:50:15 »

I was wondering why you said you were a noob! that code was impressive, I'll post my findings back here for sure.

and true about the Polygons just being vertices although it seems creating an actual Polygon object has benefits due to being able to use AffineTransforms.

I wish I could take credit for that one... I had nothing to do with it.

No, that was the people who contributed to libgdx that wrote all that, I just put it up for you because I know it's a working class and made use of it for a project I've yet to finish (even to a point where putting it as a WIP would not be embarrassing).

kingAree

Senior Newbie

Exp: 4-6 months

 « Reply #8 - Posted 2017-05-12 11:23:24 »

Bump, still can't figure it out
KaiHH

JGO Kernel

Medals: 446

 « Reply #9 - Posted 2017-05-12 11:43:08 »

See "Real-Time Collision Detection" chapter 5.2.1 ff.

EDIT: If you simply need a boolean test without any other information, then here is a small working implementation I just wrote from scratch:
 1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26  27  28  29  30  31 `private static boolean separatingAxis(Vector2d[] v1s, Vector2d[] v2s, double dx, double dy) {    double axisX = dy, axisY = -dx;    double minA = Double.POSITIVE_INFINITY, maxA = Double.NEGATIVE_INFINITY;    double minB = Double.POSITIVE_INFINITY, maxB = Double.NEGATIVE_INFINITY;    /* Project first polygon on axis */    for (int k = 0; k < v1s.length; k++) {        double d = v1s[k].x * axisX + v1s[k].y * axisY;        minA = Math.min(minA, d);        maxA = Math.max(maxA, d);    }    /* Project second polygon on axis */    for (int k = 0; k < v2s.length; k++) {        double d = v2s[k].x * axisX + v2s[k].y * axisY;        minB = Math.min(minB, d);        maxB = Math.max(maxB, d);    }    /* Check if intervals overlap */    return minA > maxB || minB > maxA; }public static boolean testPolygonPolygon(Vector2d[] v1s, Vector2d[] v2s) {    int len1 = v1s.length, len2 = v2s.length;    /* Try to find a separating axis using the first polygon's edges */    for (int i = 0, j = len1 - 1; i < len1; j = i, i++)        if (separatingAxis(v1s, v2s, v1s[i].x - v1s[j].x, v1s[i].y - v1s[j].y))            return false;     /* Try to find a separating axis using the second polygon's edges */    for (int i = 0, j = len2 - 1; i < len2; j = i, i++)        if (separatingAxis(v1s, v2s, v2s[i].x - v2s[j].x, v2s[i].y - v2s[j].y))            return false;     return true;}`

Entry point is testPolygonPolygon(...)
 Games published by our own members! Check 'em out!
kingAree

Senior Newbie

Exp: 4-6 months

 « Reply #10 - Posted 2017-05-12 14:04:36 »

Wow thanks for this, that link looks incredibly useful too! I'll try to use your code to figure out where I'm going wrong As I do think I'm close to getting my implementation working.

bmanmcfly
 « Reply #11 - Posted 2017-05-12 15:38:21 »

Oh ya, one thing I forgot about SAT is that you ALSO need to be consistent in how you "wrap" the polygons...

It might be different, but with libgdx, it only started working when I wrapped the polygons clockwise from the start point... any deviation from that and things broke.

I'm not sure how it will be with what you're working with, but if I'm correct it's an opengl thing.

I'm more or less noob still too but want to help.

what's it doing?  is it just not registering collisions?
kingAree

Senior Newbie

Exp: 4-6 months

 « Reply #12 - Posted 2017-05-12 15:49:10 »

Hi again, I've changed a few things and fixed a few problems during the past couple of weeks, but yeah still no sign of collision at all, the vertices are something I have been confused about, my player class has vertices defined like this:

vertices[0] = (0, 0)
vertices[1] = (64, 0)
vertices[2] = (64, 64)
vertices[3] = (0, 64)

But I'm not sure if I should add the position of the player to these e.g. I'm thinking it doesn't even matter until we get to the projections.

vertices[0] = (0 + x, 0 + y)
vertices[1] = (64 + x, 0 + y)
vertices[2] = (64 + x, 64 + y)
vertices[3] = (0 + x, 64 + y)

Also the vertices are being defined in a clockwise rotation although I think this is wrong in java and has to be counter-clockwise, I tried drawing the projections onto the screen to help me visualise what's going on but It didn't make much sense to me.
KaiHH

JGO Kernel

Medals: 446

 « Reply #13 - Posted 2017-05-12 16:10:52 »

The winding order does not matter. The two polygons can even have differing winding orders.
It just changes the direction of the axes you compute, which does not matter, since you always just project the vertices of both polygons onto the same axis.

EDIT: BTW, here is an optimization which inverts the test whether both projected polygon intervals intersect to allow fast early-out without testing all polygon vertices, which can dramatically reduce runtime for "large" polygons (ca. > 32 vertices):
 1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26  27  28  29  30  31  32  33  34  35  36 `private static boolean separatingAxis(Vector2f[] v1s, Vector2f[] v2s, float dx, float dy) {    float axisX = dy, axisY = -dx;    float minA = Float.POSITIVE_INFINITY, maxA = Float.NEGATIVE_INFINITY;    float minB = Float.POSITIVE_INFINITY, maxB = Float.NEGATIVE_INFINITY;    int maxLen = Math.max(v1s.length, v2s.length);    /* Project both polygons on axis */    for (int k = 0; k < maxLen; k++) {        if (k < v1s.length) {            float d = v1s[k].x * axisX + v1s[k].y * axisY;            if (d < minA) minA = d;            if (d > maxA) maxA = d;        }        if (k < v2s.length) {            float d = v2s[k].x * axisX + v2s[k].y * axisY;            if (d < minB) minB = d;            if (d > maxB) maxB = d;        }        /* Early-out if overlap found */        if (minA <= maxB && minB <= maxA) {            return false;        }    }    return true;}public static boolean testPolygonPolygon(Vector2f[] v1s, Vector2f[] v2s) {    int len1 = v1s.length, len2 = v2s.length;    /* Try to find a separating axis using the first polygon's edges */    for (int i = 0, j = len1 - 1; i < len1; j = i, i++)        if (separatingAxis(v1s, v2s, v1s[i].x - v1s[j].x, v1s[i].y - v1s[j].y))            return false;     /* Try to find a separating axis using the second polygon's edges */    for (int i = 0, j = len2 - 1; i < len2; j = i, i++)        if (separatingAxis(v1s, v2s, v2s[i].x - v2s[j].x, v2s[i].y - v2s[j].y))            return false;     return true;}`
kingAree

Senior Newbie

Exp: 4-6 months

 « Reply #14 - Posted 2017-05-12 16:28:59 »

Thanks for the edit!
bmanmcfly
 « Reply #15 - Posted 2017-05-12 16:41:03 »

The winding order does not matter. The two polygons can even have differing winding orders.
It just changes the direction of the axes you compute, which does not matter, since you always just project the vertices of both polygons onto the same axis.

EDIT: BTW, here is an optimization which inverts the test whether both projected polygon intervals intersect to allow fast early-out without testing all polygon vertices:
 1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26  27  28  29  30  31  32  33  34  35  36 `private static boolean separatingAxis(Vector2f[] v1s, Vector2f[] v2s, float dx, float dy) {    float axisX = dy, axisY = -dx;    float minA = Float.POSITIVE_INFINITY, maxA = Float.NEGATIVE_INFINITY;    float minB = Float.POSITIVE_INFINITY, maxB = Float.NEGATIVE_INFINITY;    int maxLen = Math.max(v1s.length, v2s.length);    /* Project both polygons on axis */    for (int k = 0; k < maxLen; k++) {        if (k < v1s.length) {            float d = v1s[k].x * axisX + v1s[k].y * axisY;            minA = Math.min(minA, d);            maxA = Math.max(maxA, d);        }        if (k < v2s.length) {            float d = v2s[k].x * axisX + v2s[k].y * axisY;            minB = Math.min(minB, d);            maxB = Math.max(maxB, d);        }        /* Early-out if overlap found */        if (minA <= maxB && minB <= maxA) {            return false;        }    }    return true;}public static boolean testPolygonPolygon(Vector2f[] v1s, Vector2f[] v2s) {    int len1 = v1s.length, len2 = v2s.length;    /* Try to find a separating axis using the first polygon's edges */    for (int i = 0, j = len1 - 1; i < len2; j = i, i++)        if (separatingAxis(v1s, v2s, v1s[i].x - v1s[j].x, v1s[i].y - v1s[j].y))            return false;     /* Try to find a separating axis using the second polygon's edges */    for (int i = 0, j = len1 - 1; i < len2; j = i, i++)        if (separatingAxis(v1s, v2s, v2s[i].x - v2s[j].x, v2s[i].y - v2s[j].y))            return false;     return true;}`

Maybe you are right that the order doesn't matter, but it does have to be wrapped, correct?  As in, start with one line and then continue along connecting lines, right?

Maybe that's a libgdx thing, but I remember that did solve some issues.

The other issue I had was using the vertex coordinates as opposed to the vertex world coordinates.

I just remember that even having a working algorithm getting the data setup incorrectly can cause issues.
KaiHH

JGO Kernel

Medals: 446

 « Reply #16 - Posted 2017-05-12 19:13:03 »

Quote
it does have to be wrapped, correct?  As in, start with one line and then continue along connecting lines, right?
Throughout this thread the polygon is specified via its vertices (and not via its edges). This implies that the vertices form an edge loop which always follows along the vertices either clockwise or counter-clockwise around the polygon (which is assumed to be convex). There is no way that you could not have it this way, or else your mesh would be intersecting itself.

Another way: if you specify your polygon via its edges (so via pairs of vertices), then even having your edges in a random order would work with the general SAT algorithm. The algorithm has no notion of the "order" of vertices or edges.

Quote
The other issue I had was using the vertex coordinates as opposed to the vertex world coordinates.
Of course your computation has to be performed in the same space/coordinate system. No matter which one, it just has to be consistent.
kingAree

Senior Newbie

Exp: 4-6 months

 « Reply #17 - Posted 2017-05-23 17:10:13 »

So I finally got my original code to work, never give up! here's the final version:

 1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26  27  28  29  30  31  32  33  34  35  36  37  38  39  40  41  42  43  44  45  46  47  48  49  50  51  52  53  54  55  56  57  58  59  60  61  62  63  64  65  66  67  68  69  70  71  72 `   public void obtainEdges(){      axis = new Vector2[vertices.length];      for(int i = 0; i < vertices.length; i++){                  Vector2 e1 = vertices[i];                  Vector2 e2 = vertices[i + 1 == vertices.length ? 0 : i + 1];                  Vector2 edge = e1.subtract(e2);                  Vector2 perp = edge.perp(edge);         axis[i] = perp;      }   }      public Vector2 projectAxis(Vector2 axis){      Vector2 norm = axis.normalize(axis);            double min = norm.dot(vertices[0]);      double max = min;            for(int i = 1; i < vertices.length; i++){         double proj = norm.dot(vertices[i]);                  if(proj < min){            min = proj;         }         if(proj > max){            max = proj;         }      }               proj = new Vector2(min, max);      return proj;   }      public boolean separatingAxisTheorem(){            for(DevEntity e : handler.getDevWorld().getDevM().getDevEntities()){                     obtainEdges();                  if(!e.equals(this)){                        Vector2[] axes1 = axis;            Vector2[] axes2 = e.axis;         for(int i = 0; i < axes1.length; i++){            Vector2 axis = axes1[i];                        p1 = new Vector2(projectAxis(axis));            p2 = new Vector2(e.projectAxis(axis));                        if(!p1.overlap(p2)){               return false;            }         }                  for(int i = 0; i < axes2.length; i++){            Vector2 axis = axes2[i];                        p3 = new Vector2(projectAxis(axis));            p4 = new Vector2(e.projectAxis(axis));            if(!p3.overlap(p4)){               return false;            }         }      }      }      return true;   }`
Pages: [1]
 ignore  |  Print

 Ecumene (61 views) 2017-09-30 02:57:34 theagentd (82 views) 2017-09-26 18:23:31 cybrmynd (189 views) 2017-08-02 12:28:51 cybrmynd (190 views) 2017-08-02 12:19:43 cybrmynd (194 views) 2017-08-02 12:18:09 Sralse (207 views) 2017-07-25 17:13:48 Archive (770 views) 2017-04-27 17:45:51 buddyBro (904 views) 2017-04-05 03:38:00 CopyableCougar4 (1454 views) 2017-03-24 15:39:42 theagentd (1333 views) 2017-03-24 15:32:08
 Slyth2727 14x theagentd 13x Opiop 9x princec 8x philfrei 6x Emmsii 6x SteveSmith 5x gouessej 4x KaiHH 4x Riven 3x revers 3x KevinWorkman 3x orange451 3x 65K 3x CoDi^R 3x Gornova 3x
 List of Learning Resourcesby elect2017-03-13 14:05:44List of Learning Resourcesby elect2017-03-13 14:04:45SF/X Librariesby philfrei2017-03-02 08:45:19SF/X Librariesby philfrei2017-03-02 08:44:05SF/X Librariesby SkyAphid2017-03-02 06:38:56SF/X Librariesby SkyAphid2017-03-02 06:38:32SF/X Librariesby SkyAphid2017-03-02 06:38:05SF/X Librariesby SkyAphid2017-03-02 06:37:51
 java-gaming.org is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑gaming.org