Polygon Collision

Polygon Collision

GrantG

Member #8,173

December 2006

I'm working on a game which needs polygon collision detection, so I wrote some code with the help of a tutorial, but it doesn't quite work. Depending on the sides of the polygon it overcalculates the collision.

Here is the collision code

1class CVec2D
2{
3public:
float x, y;
float magnitude;
6 
CVec2D() {}
CVec2D(float xPos, float yPos) : x(xPos), y(yPos) {}
~CVec2D() {}
float Magnitude() {return sqrt(x * x + y * y);}
void Normalize() {x = x / Magnitude(); y = y / Magnitude();}
float DotProduct(CVec2D vec) {return x * vec.x + y * vec.y;}
13};
14 
15struct CollisionResult
16{
bool collided, willCollide;
CVec2D translateVec;
19};
20 
21class CPoly
22{
23private:
vector<CVec2D> m_points, m_sides;
float m_radius;
26 
void ProjectPoly(CVec2D axis, CPoly &poly, float &min, float &max)
{
  // project all the polygon's points onto the axis using the dot product
  float dp = axis.DotProduct(poly.GetPoint(0));
  min = dp;
  max = dp;
  for(int i = 0; i < poly.PointAmount(); i++)
  {
    dp = poly.GetPoint(i).DotProduct(axis);
    if(dp < min) min = dp;
    else if(dp > max) max = dp;
  }
}
float IntervalDist(float min, float max, float min2, float max2)
{
  if(min < min2) return min2 - max;
  else return min - max2;
}
45public:
CPoly() {}
~CPoly() {}
48 
void AddPoint(float x, float y) {m_points.push_back(CVec2D(x, y));}
void Clear() {m_points.clear();}
int PointAmount() {return m_points.size();}
int SideAmount() {return m_sides.size();}
CVec2D GetPoint(int index) {return m_points[index];}
CVec2D GetSide(int index) {return m_sides[index];}
void BuildSides()
{
  CVec2D v1, v2;
  m_sides.clear();
  for(int i = 0; i < m_points.size(); i++)
  {
    v1 = m_points<i>;
    if(i + 1 < m_points.size()) v2 = m_points[i + 1];
    else v2 = m_points[0];
    m_sides.push_back(CVec2D(v2.x - v1.x, v2.y - v1.y));
  }
  // find the minimum radius that surrounds the polygon
  float currentMax = 574969476.0;
  CVec2D cen = Center();
  for(int i = 0; i < m_points.size(); i++)
  {
    float side1, side2;
    side1 = fabs(m_points<i>.x - cen.x);
    side2 = fabs(m_points<i>.y - cen.y);
    float dist = sqrt(side1 * side1 + side2 * side2);
    if(dist > currentMax) currentMax = dist;
  }
  m_radius = currentMax;
}
void Draw(BITMAP *buf)
{
  for(int i = 0; i < m_points.size(); i++)
  {
    if(i + 1 < m_points.size()) line(buf, m_points<i>.x, m_points<i>.y, m_points[i + 1].x, m_points[i + 1].y, makecol(255, 255, 255));
    else line(buf, m_points<i>.x, m_points<i>.y, m_points[0].x, m_points[0].y, makecol(255, 255, 255));
  }
}
void Move(float xAmount, float yAmount)
{
  for(int i = 0; i < m_points.size(); i++)
  {
    m_points<i>.x += xAmount;
    m_points<i>.y += yAmount;
  }
}
CVec2D Center()
{
  // find the center
  float xTotal = 0, yTotal = 0;
  for(int i = 0; i < m_points.size(); i++)
  {
    xTotal += m_points<i>.x;
    yTotal += m_points<i>.y;
  }
  float xCenter = xTotal / m_points.size();
  float yCenter = yTotal / m_points.size();
  return CVec2D(xCenter, yCenter);
}
float Radius() {return m_radius;}
CollisionResult Collision(CPoly &poly, CVec2D velocity)
{
  CollisionResult result;
  result.collided = true;
  result.willCollide = true;
  result.translateVec = CVec2D(0, 0);
              // do circle collision first to check if they are in the same area
  CVec2D cen1 = Center(), cen2 = poly.Center();
  if(pow(cen1.x - cen2.x, 2) + pow(cen1.y - cen2.y, 2) > pow(Radius() + poly.Radius(), 2))
  {
    result.collided = false;
    result.willCollide = false;
    return result;
  }
  float minIntervalDist = 4294967295;
  CVec2D translationAxis(0, 0);
  CVec2D side(0, 0), transAxis(0, 0);
  // loop through all the sides
  for(int i = 0; i < m_sides.size() + poly.PointAmount(); i++)
  {
    if(i < m_sides.size()) side = m_sides<i>;
    else side = poly.GetSide(i - m_sides.size());
131 
    // find the sides normal
    CVec2D axis = CVec2D(-side.y, side.x);
    axis.Normalize();
135 
    float min = 0, max = 0, min2 = 0, max2 = 0;
    ProjectPoly(axis, *this, min, max);
    ProjectPoly(axis, poly, min2, max2);
139 
    if(IntervalDist(min, max, min2, max2) > 0) result.collided = false;
141 
    // check if the polygons will collide
    float velocityProj = axis.DotProduct(velocity);
144 
    if(velocityProj < 0) min += velocityProj;
    else max += velocityProj;
147 
    float intervalDist = IntervalDist(min, max, min2, max2);
    if(intervalDist > 0) result.willCollide = false;
150 
    // nothing collides
    if(!result.collided && !result.willCollide) break;
153 
    intervalDist = abs(intervalDist);
    if(intervalDist < minIntervalDist)
    {
      minIntervalDist = intervalDist;
      translationAxis = axis;
      CVec2D vec(Center().x - poly.Center().x, Center().y - poly.Center().y);
      if(vec.DotProduct(translationAxis) < 0)
      {
        translationAxis.x = -translationAxis.x;
        translationAxis.y = -translationAxis.y;
      }
    }
  }
  if(result.willCollide)
  {
    // calc the translate vector for the polygon
    CVec2D translateVec(translationAxis.x * minIntervalDist, translationAxis.y * minIntervalDist);
    result.translateVec = translateVec;
  }
  return result;
}
175};

It's probably just a math error or something I'm not catching, so hopefully someone else will.

Thomas Harte

Member #33

April 2000

I haven't fully read the code, because I'm sort of on the run, but some general comments:
axis.Normalize();
This is unnecessary. You'd want to normalise if you were using the distances for something else, if you're just comparing them then it makes no difference.
check if the polygons will collide
It seems that for every frame you're checking where the polygons are at the start of frame and where they are at the end of the frame? If I've understood your code then where they are at the end of one frame is where they are at the start of the next frame, so this is just doubling your work!

  float IntervalDist(float min, float max, float min2, float max2)
  {
    if(min < min2) return min2 - max;
    else return min - max2;

This is the main bit I don't get. Either it assumes that both intervals are the same length, or it doesn't do what I think it does. What should it return, for example, if one interval completely encloses the other?

[My site] [Tetrominoes]

GrantG

Member #8,173

December 2006

Thomas Harte said:

It seems that for every frame you're checking where the polygons are at the start of frame and where they are at the end of the frame? If I've understood your code then where they are at the end of one frame is where they are at the start of the next frame, so this is just doubling your work!

Yeah you're right, I got that part right out of a tutorial and didn't think about that at the time.

Heh, what a coincidence, I also did not understand

float IntervalDist(float min, float max, float min2, float max2)

I'll try looking through the tutorial again and see if the guy explains it anywhere.

EDIT:
I used this tutorial by the way.

EDIT:
Removing axis.Normalize(); fixed the collision, but now when the two polygons touch the one gets moved about 3000 pixels away instantly.