Jump to content
  • Advertisement
Seer

Polygons and the Separating Axis Theorem

Recommended Posts

I have programmed an implementation of the Separating Axis Theorem to handle collisions between 2D convex polygons. It is written in Processing and can be viewed on Github here. There are a couple of issues with it that I would like some help in resolving.

In the construction of Polygon objects, you specify the width and height of the polygon and the initial rotation offset by which the vertices will be placed around the polygon. If the rotation offset is 0, the first vertex is placed directly to the right of the object. If higher or lower, the first vertex is placed clockwise or counter-clockwise, respectively, around the circumference of the object by the rotation amount. The rest of the vertices follow by a consistent offset of TWO_PI / number of vertices. While this places the vertices at the correct angle around the polygon, the problem is that if the rotation is anything other than 0, the width and height of the polygon are no longer the values specified. They are reduced because the vertices are placed around the polygon using the sin and cos functions, which often return values other than 1 or -1. Of course, when the half width and half height are multiplied by a sin or cos value other than 1 or -1, they are reduced. This is my issue. How can I place an arbitrary number of vertices at an arbitrary rotation around the polygon, while maintaining both the intended shape specified by the number of vertices (triangle, hexagon, octagon), and the intended width and height of the polygon as specified by the parameter values in the constructor?

The Polygon code:

class Polygon
{
  PVector position;
  PShape shape;
  int w, h, halfW, halfH;
  color c;
  ArrayList<PVector> vertexOffsets;
  
  Polygon(PVector position, int numVertices, int w, int h, float rotation)
  {
    this.position = position;
    this.w = w;
    this.h = h;
    this.halfW = w / 2;
    this.halfH = h / 2;
    this.c = color(255);
    vertexOffsets = new ArrayList<PVector>();
    
    if(numVertices < 3) numVertices = 3;
    
    shape = createShape();
    shape.beginShape();
    shape.fill(255);
    shape.stroke(255);
    for(int i = 0; i < numVertices; ++i)
    {
      PVector vertex = new PVector(position.x + cos(rotation) * halfW, position.y + sin(rotation) * halfH);
      shape.vertex(vertex.x, vertex.y);
      rotation += TWO_PI / numVertices;
      
      PVector vertexOffset = vertex.sub(position);
      vertexOffsets.add(vertexOffset);
    }
    shape.endShape(CLOSE);
  }
  
  void move(float x, float y)
  {
    position.set(x, y);
    
    for(int i = 0; i < shape.getVertexCount(); ++i)
    {
      PVector vertexOffset = vertexOffsets.get(i);
      shape.setVertex(i, position.x + vertexOffset.x, position.y + vertexOffset.y);
    }
  }
  
  void rotate(float angle)
  {
    for(int i = 0; i < shape.getVertexCount(); ++i)
    {
      PVector vertexOffset = vertexOffsets.get(i);
      vertexOffset.rotate(angle);
      shape.setVertex(i, position.x + vertexOffset.x, position.y + vertexOffset.y);
    }
  }
  
  void setColour(color c)
  {
    this.c = c;
  }
  
  void render()
  {
    shape.setFill(c);
    shape(shape);
  }
}

 

My other issue is that when two polygons with three vertices each collide, they are not always moved out of collision smoothly by the Minimum Translation Vector returned by the SAT algorithm. The polygon moved out of collision by the MTV does not rest against the other polygon as it should, it instead jumps back a small distance. I find this very strange as I have been unable to replicate this behaviour when resolving collisions between polygons of other vertex quantities and I cannot find the flaw in the implementation, though it must be there. What could be causing this incorrect collision resolution, which from my testing appears to only occur between polygons of three vertices?

Any help you can provide on these issues would be greatly appreciated. Thank you.

Share this post


Link to post
Share on other sites
Advertisement

I'd like to help but I have trouble understanding what you need help with. Maybe you can try asking a more specific question as opposed to some paragraphs, and also if you can post a video/gif showing your problem that helps a lot as well.

Share this post


Link to post
Share on other sites

Here are two videos showing the collision handling between polygons. The collisions between the hexagon and the triangle are resolved as you would expect, with the hexagon being moved back by the MTV such that it is resting against the triangle. The collisions between the two triangles however are not resolved correctly, with the moving triangle jumping back a small distance upon collision resolution. I would like some help understanding why this happens and how it might be resolved.

Also attached is an image showing two rectangles, both specified as being of width 200 pixels and height 140 pixels. One is made using the Processing rect() function and the other is a Polygon object constructed as described in my last post. As you can see, there is a noticeable disparity between their respective dimensions, with the Polygon object having smaller width and height. I would like some help understanding how to create the polygon such that its width and height are those specified by the parameters of its constructor, regardless of initial vertex rotation. Thank you.

 

polygoncomparison.PNG

Share this post


Link to post
Share on other sites

It seems you are computing the penetration wrong which results in overshooting I guess. The SAT test is really simple in 2D. You only need the vertices (in some order - CCW or CW) and the transform (translation and rotation). How do you compute the MTV?

Share this post


Link to post
Share on other sites

If you would like to see the full picture (three .pde files), you can view the code at my GitHub repository here. If interested you can also run the program yourself if you have Processing installed. Here though is the code which implements the SAT to detect collisions and create the MTV. Please tell me if you see any mistakes.

class CollisionHandler
{
  PVector detectCollision(PShape shape1, PShape shape2)
  {
    float magnitude = 999999;
    PVector direction = new PVector();
    ArrayList<PVector> axes = new ArrayList<PVector>();
    axes.addAll(getAxes(shape1));
    axes.addAll(getAxes(shape2));
    
    for(int i = 0; i < axes.size(); ++i)
    {
      PVector axis = axes.get(i);
      
      PVector p1 = project(shape1, axis);
      PVector p2 = project(shape2, axis);
      
      if(isOverlap(p1, p2))
      {
        float overlap = getOverlap(p1, p2);
        
        if(overlap < magnitude)
        {
          magnitude = overlap;
          direction = axis;
        }
      }
      else
      {
        return null;
      }
    }
    
    return direction.mult(magnitude);
  }
  
  ArrayList<PVector> getAxes(PShape shape)
  {
    ArrayList<PVector> axes = new ArrayList<PVector>();
    
    for(int i = 0; i < shape.getVertexCount(); ++i)
    {
      PVector v1 = shape.getVertex(i);
      PVector v2 = shape.getVertex(i + 1 == shape.getVertexCount() ? 0 : i + 1);
      PVector edge = v2.sub(v1);
      PVector axis = new PVector(-edge.y, edge.x);
      axis.normalize();
      axes.add(axis);
    }
    
    return axes;
  }
  
  PVector project(PShape shape, PVector axis)
  {  
    float min = axis.dot(shape.getVertex(0));
    float max = min;
    
    for(int i = 1; i < shape.getVertexCount(); ++i)
    {
      float projection = axis.dot(shape.getVertex(i));
      
      if(projection < min)
      {
        min = projection;
      }
      else if(projection > max)
      {
        max = projection;
      }
    }
    
    return new PVector(min, max);
  }
  
  boolean isOverlap(PVector p1, PVector p2)
  {
    return p1.x < p2.y && p1.y > p2.x;
  }
  
  float getOverlap(PVector p1, PVector p2)
  {
    return p1.x < p2.y ? p1.y - p2.x : p2.y - p1.x;
  }
}

 

Share this post


Link to post
Share on other sites

The idea instead of computing min/max along an interval, you can use the concept of support points. This can reduce some redundancy in your code and potentially make it easier to pin-point the problem.

Share this post


Link to post
Share on other sites

Does anyone have any ideas as to how to fix the width and height of the polygons when their vertices are given an initial rotation?

Share this post


Link to post
Share on other sites

What is the width and height of an arbitrary polygon? Width an height make sense for a rectangle, but not arbitrary polygons.

Edited by Dirk Gregorius

Share this post


Link to post
Share on other sites

I suppose I'm thinking of the bounding rectangle of the polygon. When a polygon object is made, vertices are placed around the polygon according to the sin and cos of the rotation given and its half width and half height. I just want to make it so that no matter the rotation affecting the initial placement of the vertices, that the width and height of the polygon (along the X and Y axes) are the same as those given in the constructor. Can you see a way to do this?

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!