Java-Gaming.org Hi !
Featured games (90)
games approved by the League of Dukes
Games in Showcase (726)
Games in Android Showcase (216)
games submitted by our members
Games in WIP (796)
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 1206 times)
0 Members and 1 Guest are viewing this topic.
Offline 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;
   }

   

}


Offline 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.

Offline 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!
Legends of Yore - The Casual Retro Roguelike
Offline 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.
Offline 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.
Offline 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.
Offline 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.
Offline 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).

Offline kingAree

Senior Newbie


Exp: 4-6 months



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

Bump, still can't figure it out
Offline KaiHH

JGO Kernel


Medals: 409



« 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!
Legends of Yore - The Casual Retro Roguelike
Offline 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.

Offline 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?
Offline 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.
Offline KaiHH

JGO Kernel


Medals: 409



« 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;
}
Offline kingAree

Senior Newbie


Exp: 4-6 months



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

Thanks for the edit!
Offline 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.
Offline KaiHH

JGO Kernel


Medals: 409



« 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.
Offline 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 = axes1[i];
           
            p3 = new Vector2(projectAxis(axis));
            p4 = new Vector2(e.projectAxis(axis));
            if(!p3.overlap(p4)){
               return false;
            }
         }
      }
      }
      return true;
   }
Pages: [1]
  ignore  |  Print  
 
 

 
Archive (284 views)
2017-04-27 17:45:51

buddyBro (474 views)
2017-04-05 03:38:00

CopyableCougar4 (923 views)
2017-03-24 15:39:42

theagentd (935 views)
2017-03-24 15:32:08

Rule (948 views)
2017-03-19 12:43:22

Rule (916 views)
2017-03-19 12:42:17

Rule (918 views)
2017-03-19 12:36:21

theagentd (965 views)
2017-03-16 05:07:07

theagentd (891 views)
2017-03-15 22:37:06

theagentd (687 views)
2017-03-15 22:32:18
List of Learning Resources
by elect
2017-03-13 14:05:44

List of Learning Resources
by elect
2017-03-13 14:04:45

SF/X Libraries
by philfrei
2017-03-02 08:45:19

SF/X Libraries
by philfrei
2017-03-02 08:44:05

SF/X Libraries
by SkyAphid
2017-03-02 06:38:56

SF/X Libraries
by SkyAphid
2017-03-02 06:38:32

SF/X Libraries
by SkyAphid
2017-03-02 06:38:05

SF/X Libraries
by SkyAphid
2017-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
Powered by MySQL Powered by PHP Powered by SMF 1.1.18 | SMF © 2013, Simple Machines | Managed by Enhanced Four Valid XHTML 1.0! Valid CSS!