Java-Gaming.org    
Featured games (79)
games approved by the League of Dukes
Games in Showcase (477)
Games in Android Showcase (107)
games submitted by our members
Games in WIP (535)
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  
  SAT collision detection - handling parallel edges  (Read 1824 times)
0 Members and 1 Guest are viewing this topic.
Offline Danik

Junior Newbie





« Posted 2010-04-23 23:27:01 »

Hi
I have a problem with a collision detection method I have written. I use the separating axis theorem to detect collisions and the detection is working well.
The problem is that the minimum translation vector I get from the method is sometimes wrong if there are parallel edges in the polygons.

Parallel edges, although in opposite directions, give the same overlap distance, so it's just a matter of chance if the returned vector will point in the right direction.

How would I go about to fix this?


My code:
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  
74  
75  
76  
77  
78  
79  
80  
81  
82  
83  
84  
85  
86  
87  
88  
89  
90  
91  
92  
93  
94  
95  
96  
97  
98  
99  
100  
101  
   /**
    * Checks to see it there is a collision between two convex polygons.
    * If there is a collision it returns a vector representing the minimal
    * translation necessary to move 'a' so that it is not overlapping 'b',
    * else a vector with x and y equal to 0.
    *
    * The returned vector is pointing towards the first polygon 'a'.
    *
    * Uses the separating axis theorem for convex polygons.
    *
    * @param a The first polygon
    * @param b The second polygon
    * @return The minimum translation vector directed towards the first
    * polygon, or a Vector with (x,y)==(0,0) if there is no overlap.
    */

   Vector getCollisionSAT(Polygon a, Polygon b) {

      ArrayList<Vector> aVerts = new ArrayList<Vector>(a.getVertices());
      ArrayList<Vector> bVerts = new ArrayList<Vector>(b.getVertices());
     
      ArrayList<Vector> normals = new ArrayList<Vector>();
     
      // Add normals of a to the list of normals
     for (int i = 0; i < aVerts.size(); i++) {  
         Vector p1, p2;
         
         p1 = aVerts.get(i);
         p2 = aVerts.get((i + 1 == aVerts.size()) ? 0 : i + 1);
         
         Vector normal = p2.subtract(p1).perpendicularCCW();
         normal = normal.normalize();
         
         normals.add(normal);
         
      }
     
      // Add normals of b to the list normals
     for (int i = 0; i < bVerts.size(); i++) {  
         Vector p1, p2;
         
         p1 = bVerts.get(i);
         p2 = bVerts.get((i + 1 == bVerts.size()) ? 0 : i + 1);
         
         Vector normal = p2.subtract(p1).perpendicularCW();
         normal = normal.normalize();
         
         normals.add(normal);
         
      }
     
      Vector minOverlapVector = null;
      double minOverlap = Double.MAX_VALUE;
     
      for (Vector normal : normals) {
         
         double aMin = aVerts.get(0).dotProduct(normal); // some value in the range
        double aMax = aMin;
         
         // Project each vertex of a onto the current normal and save the min and max value
        for (Vector v : aVerts) {
            double dot = v.dotProduct(normal);
            if (dot < aMin) {
               aMin = dot;
            }
            else if (dot > aMax) {
               aMax = dot;
            }
         }
         
         double bMin = bVerts.get(0).dotProduct(normal); // some value in the range
        double bMax = bMin;
         
         // Do the same for b
        for (Vector v : bVerts) {
            double dot = v.dotProduct(normal);
            if (dot < bMin) {
               bMin = dot;
            }
            if (dot > bMax) {
               bMax = dot;
            }
         }
         
         
         // Compare min and max values to see if there is an overlap
        if (aMin > bMax || bMin > aMax) {
            return new Vector(0,0); // no overlap - no collision
        }
         
         else {
            double overlap = Math.min(aMax - bMin, bMax - aMin);
            if (overlap <= minOverlap) {
               minOverlap = overlap;
               minOverlapVector = normal.scalarMultiplication(overlap);
            }
         }  
      }
     
      return minOverlapVector;
     
   }
Offline Danik

Junior Newbie





« Reply #1 - Posted 2010-04-24 18:32:12 »

I have solved the problem with the following code right before the "return minOverlapVector".
It checks if the vector between the two polygons is pointing in the opposite direction from the translation vector and if so reverses it.
It's a bit of a hack though, so if anyone has any insight on how to do it properly I would appreciate it.

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
      // The following is not optimal but is used to find the correct 
     // direction of minOverlapVector until a better solution is found.
     Vector aMidPoint = new Vector();
      Vector bMidPoint = new Vector();
      for ( Vector v : aVerts) {
         aMidPoint = aMidPoint.add(v);
      }
      for ( Vector v : bVerts) {
         bMidPoint = bMidPoint.add(v);
      }
      aMidPoint = aMidPoint.scalarDivision(aVerts.size());
      bMidPoint = bMidPoint.scalarDivision(bVerts.size());
     
      Vector ba = aMidPoint.subtract(bMidPoint);
     
      if (ba.dotProduct(minOverlapVector) < 0) {
         minOverlapVector = minOverlapVector.scalarMultiplication(-1);
         System.out.println("switch");
      }
     
Pages: [1]
  ignore  |  Print  
 
 
You cannot reply to this message, because it is very, very old.

 

Add your game by posting it in the WIP section,
or publish it in Showcase.

The first screenshot will be displayed as a thumbnail.

Riven (6 views)
2014-07-29 12:53:52

Dwinin (7 views)
2014-07-29 10:59:34

E.R. Fleming (21 views)
2014-07-29 03:07:13

E.R. Fleming (8 views)
2014-07-29 03:06:25

pw (39 views)
2014-07-24 01:59:36

Riven (39 views)
2014-07-23 21:16:32

Riven (26 views)
2014-07-23 21:07:15

Riven (28 views)
2014-07-23 20:56:16

ctomni231 (59 views)
2014-07-18 06:55:21

Zero Volt (51 views)
2014-07-17 23:47:54
HotSpot Options
by dleskov
2014-07-08 03:59:08

Java and Game Development Tutorials
by SwordsMiner
2014-06-14 00:58:24

Java and Game Development Tutorials
by SwordsMiner
2014-06-14 00:47:22

How do I start Java Game Development?
by ra4king
2014-05-17 11:13:37

HotSpot Options
by Roquen
2014-05-15 09:59:54

HotSpot Options
by Roquen
2014-05-06 15:03:10

Escape Analysis
by Roquen
2014-04-29 22:16:43

Experimental Toys
by Roquen
2014-04-28 13:24:22
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!