Polygon Intersection fails, collision "size" too big

Question

OK, so I'm trying to make a simple asteroids clone. Everything works fine, except for the collision detection.

I have two different versions, the first one uses java.awt.geom.Area:

// polygon is a java.awt.Polygon and p is the other one
final Area intersect = new Area();
intersect.add(new Area(polygon));
intersect.intersect(new Area(p.polygon));
return !intersect.isEmpty();

This works like a charm... if you don't care about 40% CPU for only 120 asteroids :(

So I searched the net for the famous separating axis theorem, since I'm not thaaaaaat good a the math I took the implementation from here and converted it to fit my Java needs:

public double dotProduct(double x, double y, double dx, double dy) {
     return x * dx + y * dy;
    }

    public double IntervalDistance(double minA, double maxA, double minB,
      double maxB) {
     if (minA < minB) {
      return minB - maxA;
     } else {
      return minA - maxB;
     }
    }

    public double[] ProjectPolygon(double ax, double ay, int p, int[] x, int[] y) {
     double dotProduct = dotProduct(ax, ay, x[0], y[0]);
     double min = dotProduct;
     double max = dotProduct;
     for (int i = 0; i < p; i++) {
      dotProduct = dotProduct(x[i], y[i], ax, ay);
      if (dotProduct < min) {
       min = dotProduct;
      } else if (dotProduct > max) {
       max = dotProduct;
      }
     }
     return new double[] { min, max };
    }

    public boolean PolygonCollision(Asteroid ast) {
     int edgeCountA = points;
     int edgeCountB = ast.points;
     double edgeX;
     double edgeY;

     for (int edgeIndex = 0; edgeIndex < edgeCountA + edgeCountB; edgeIndex++) {
      if (edgeIndex < edgeCountA) {
       edgeX = xp[edgeIndex] * 0.9;
       edgeY = yp[edgeIndex] * 0.9;
      } else {
       edgeX = ast.xp[edgeIndex - edgeCountA] * 0.9;
       edgeY = ast.yp[edgeIndex - edgeCountA] * 0.9;
      }

      final double x = -edgeY;
      final double y = edgeX;
      final double len = Math.sqrt(x * x + y * y);
      final double axisX = x / len;
      final double axisY = y / len;

      final double[] minMaxA = ProjectPolygon(axisX, axisY, points, xp,
        yp);
      final double[] minMaxB = ProjectPolygon(axisX, axisY, ast.points,
        ast.xp, ast.yp);

      if (IntervalDistance(minMaxA[0], minMaxA[1], minMaxB[0], minMaxB[1]) > 0) {
       return false;
      }
     }
     return true;
    }

It works... kinda. Actually it seems that the "collision hull" of the asteroids is too big when using this code, it's like 1.2 times the size of the asteroid. And I don't have any clue why.

Here are two pictures for comparison:
http://www.spielecast.de/stuff/asteroids1.png
http://www.spielecast.de/stuff/asteroids2.png

As you can hopefully see, the asteroids in picture one are much denser than the ones in picture 2 where is use the SAT code.

So any ideas? Or does anyone knows a Polygon implementation for Java featuring intersection tests that I could use?

Answer 1

It looks like your second result is doing collision detection as if the polygons were circles with their radius set to the most distant point of the polygon from the center. Most collision detection stuff I've seen creates a simple bounding box (either a circle or rectangle) into which the polygon can fit. Only if two bounding boxes intersect (a far simpler calculation) do you continue on to the more detailed detection. Perhaps the appropriated algorithm is only intended as a bounding box calculator?

EDIT: Also, from wikipedia

The theorem does not apply if one of the bodies is not convex.

Many of the asteroids in your image have concave surfaces.