Polygon Collision
GrantG

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:
4 float x, y;
5 float magnitude;
6 
7 CVec2D() {}
8 CVec2D(float xPos, float yPos) : x(xPos), y(yPos) {}
9 ~CVec2D() {}
10 float Magnitude() {return sqrt(x * x + y * y);}
11 void Normalize() {x = x / Magnitude(); y = y / Magnitude();}
12 float DotProduct(CVec2D vec) {return x * vec.x + y * vec.y;}
13};
14 
15struct CollisionResult
16{
17 bool collided, willCollide;
18 CVec2D translateVec;
19};
20 
21class CPoly
22{
23private:
24 vector<CVec2D> m_points, m_sides;
25 float m_radius;
26 
27 void ProjectPoly(CVec2D axis, CPoly &poly, float &min, float &max)
28 {
29 // project all the polygon's points onto the axis using the dot product
30 float dp = axis.DotProduct(poly.GetPoint(0));
31 min = dp;
32 max = dp;
33 for(int i = 0; i < poly.PointAmount(); i++)
34 {
35 dp = poly.GetPoint(i).DotProduct(axis);
36 if(dp < min) min = dp;
37 else if(dp > max) max = dp;
38 }
39 }
40 float IntervalDist(float min, float max, float min2, float max2)
41 {
42 if(min < min2) return min2 - max;
43 else return min - max2;
44 }
45public:
46 CPoly() {}
47 ~CPoly() {}
48 
49 void AddPoint(float x, float y) {m_points.push_back(CVec2D(x, y));}
50 void Clear() {m_points.clear();}
51 int PointAmount() {return m_points.size();}
52 int SideAmount() {return m_sides.size();}
53 CVec2D GetPoint(int index) {return m_points[index];}
54 CVec2D GetSide(int index) {return m_sides[index];}
55 void BuildSides()
56 {
57 CVec2D v1, v2;
58 m_sides.clear();
59 for(int i = 0; i < m_points.size(); i++)
60 {
61 v1 = m_points<i>;
62 if(i + 1 < m_points.size()) v2 = m_points[i + 1];
63 else v2 = m_points[0];
64 m_sides.push_back(CVec2D(v2.x - v1.x, v2.y - v1.y));
65 }
66 // find the minimum radius that surrounds the polygon
67 float currentMax = 574969476.0;
68 CVec2D cen = Center();
69 for(int i = 0; i < m_points.size(); i++)
70 {
71 float side1, side2;
72 side1 = fabs(m_points<i>.x - cen.x);
73 side2 = fabs(m_points<i>.y - cen.y);
74 float dist = sqrt(side1 * side1 + side2 * side2);
75 if(dist > currentMax) currentMax = dist;
76 }
77 m_radius = currentMax;
78 }
79 void Draw(BITMAP *buf)
80 {
81 for(int i = 0; i < m_points.size(); i++)
82 {
83 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));
84 else line(buf, m_points<i>.x, m_points<i>.y, m_points[0].x, m_points[0].y, makecol(255, 255, 255));
85 }
86 }
87 void Move(float xAmount, float yAmount)
88 {
89 for(int i = 0; i < m_points.size(); i++)
90 {
91 m_points<i>.x += xAmount;
92 m_points<i>.y += yAmount;
93 }
94 }
95 CVec2D Center()
96 {
97 // find the center
98 float xTotal = 0, yTotal = 0;
99 for(int i = 0; i < m_points.size(); i++)
100 {
101 xTotal += m_points<i>.x;
102 yTotal += m_points<i>.y;
103 }
104 float xCenter = xTotal / m_points.size();
105 float yCenter = yTotal / m_points.size();
106 return CVec2D(xCenter, yCenter);
107 }
108 float Radius() {return m_radius;}
109 CollisionResult Collision(CPoly &poly, CVec2D velocity)
110 {
111 CollisionResult result;
112 result.collided = true;
113 result.willCollide = true;
114 result.translateVec = CVec2D(0, 0);
115 // do circle collision first to check if they are in the same area
116 CVec2D cen1 = Center(), cen2 = poly.Center();
117 if(pow(cen1.x - cen2.x, 2) + pow(cen1.y - cen2.y, 2) > pow(Radius() + poly.Radius(), 2))
118 {
119 result.collided = false;
120 result.willCollide = false;
121 return result;
122 }
123 float minIntervalDist = 4294967295;
124 CVec2D translationAxis(0, 0);
125 CVec2D side(0, 0), transAxis(0, 0);
126 // loop through all the sides
127 for(int i = 0; i < m_sides.size() + poly.PointAmount(); i++)
128 {
129 if(i < m_sides.size()) side = m_sides<i>;
130 else side = poly.GetSide(i - m_sides.size());
131 
132 // find the sides normal
133 CVec2D axis = CVec2D(-side.y, side.x);
134 axis.Normalize();
135 
136 float min = 0, max = 0, min2 = 0, max2 = 0;
137 ProjectPoly(axis, *this, min, max);
138 ProjectPoly(axis, poly, min2, max2);
139 
140 if(IntervalDist(min, max, min2, max2) > 0) result.collided = false;
141 
142 // check if the polygons will collide
143 float velocityProj = axis.DotProduct(velocity);
144 
145 if(velocityProj < 0) min += velocityProj;
146 else max += velocityProj;
147 
148 float intervalDist = IntervalDist(min, max, min2, max2);
149 if(intervalDist > 0) result.willCollide = false;
150 
151 // nothing collides
152 if(!result.collided && !result.willCollide) break;
153 
154 intervalDist = abs(intervalDist);
155 if(intervalDist < minIntervalDist)
156 {
157 minIntervalDist = intervalDist;
158 translationAxis = axis;
159 CVec2D vec(Center().x - poly.Center().x, Center().y - poly.Center().y);
160 if(vec.DotProduct(translationAxis) < 0)
161 {
162 translationAxis.x = -translationAxis.x;
163 translationAxis.y = -translationAxis.y;
164 }
165 }
166 }
167 if(result.willCollide)
168 {
169 // calc the translate vector for the polygon
170 CVec2D translateVec(translationAxis.x * minIntervalDist, translationAxis.y * minIntervalDist);
171 result.translateVec = translateVec;
172 }
173 return result;
174 }
175};

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

Thomas Harte

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?

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

Thread #590817. Printed from Allegro.cc