Allegro.cc Forums » Programming Questions » 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

 1 class CVec2D 2 { 3 public: 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 15 struct CollisionResult 16 { 17 bool collided, willCollide; 18 CVec2D translateVec; 19 }; 20 21 class CPoly 22 { 23 private: 24 vector 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 } 45 public: 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; 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.x - cen.x); 73 side2 = fabs(m_points.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.x, m_points.y, m_points[i + 1].x, m_points[i + 1].y, makecol(255, 255, 255)); 84 else line(buf, m_points.x, m_points.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.x += xAmount; 92 m_points.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.x; 102 yTotal += m_points.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; 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 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 collideIt 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 understandfloat 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.
 Go to: Allegro Development Installation, Setup & Configuration Allegro.cc Comments Off-Topic Ordeals The Depot Game Design & Concepts Programming Questions Recent Threads