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<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 | } |
| 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<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.
]]>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?
]]>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.