Dividing axis theorem: rotation around the center of mass

Question

Problem in Polygon::FindAxisLeastPenetration :

 double Polygon::FindAxisLeastPenetration(unsigned int *faceIndex, const Polygon &polygonA, const Polygon &polygonB) const { double bestDistance = -std::numeric_limits<double>::infinity(); unsigned int bestIndex; for (unsigned int i = 0; i < polygonA.points.size(); i++) { Vector2D n = polygonA.normals[i]; Vector2D nw = polygonA.rotationMatrix * n; //ROTATION Matrix22 buT = polygonB.rotationMatrix.Transposed(); n = buT * nw; //ROTATION Vector2D support = polygonB.points[polygonB.GetSupport(-n)]; Vector2D vertex = polygonA.points[i]; vertex = polygonA.rotationMatrix * vertex; //ROTATION vertex.Add(polygonA.body->GetPosition()); vertex.Subtract(polygonB.body->GetPosition()); vertex = buT * vertex; // ROTATION double distance = n.DotProduct(support - vertex); if (distance > bestDistance) { bestDistance = distance; bestIndex = i; } } *faceIndex = bestIndex; return bestDistance; } unsigned int Polygon::GetSupport(const Vector2D &dir) const { double bestProjection = -std::numeric_limits<double>::infinity(); unsigned int bestIndex = 0; for (unsigned int i = 0; i < points.size(); i++) { Vector2D vertex = points[i]; double projection = vertex.DotProduct(dir); if (projection > bestProjection) { bestProjection = projection; bestIndex = i; } } return bestIndex; } Manifold Polygon::CheckCollision(const Polygon &polygonA, const Polygon &polygonB) const { Manifold result; result.objectA = polygonA.body; result.objectB = polygonB.body; unsigned int indexA; double penetrationA = Polygon::FindAxisLeastPenetration(&indexA, polygonA, polygonB); if (penetrationA >= 0.0) { result.intersects = false; return result; } unsigned int indexB; double penetrationB = Polygon::FindAxisLeastPenetration(&indexB, polygonB, polygonA); if (penetrationB >= 0.0) { result.intersects = false; return result; } result.intersects = true; //... return result; Rectangle::Rectangle(double width, double height) : Polygon() { double hw = width / 2.0; double hh = height / 2.0; points.push_back(Vector2D(-hw, -hh)); points.push_back(Vector2D(hw, -hh)); points.push_back(Vector2D(hw, hh)); points.push_back(Vector2D(-hw, hh)); // points.push_back(Vector2D(0, 0)); // points.push_back(Vector2D(width, 0)); // points.push_back(Vector2D(width, height)); // points.push_back(Vector2D(0, height)); normals.push_back(Vector2D(0.0, -1.0)); normals.push_back(Vector2D(1.0, 0.0)); normals.push_back(Vector2D(0.0, 1.0)); normals.push_back(Vector2D(-1.0, 0.0)); center.x = 0; center.y = 0; 

}

polygon.rotationMatrix is an object of type Matrix22 , which is a 2x2 matrix.
polygon.points std::vector<Vector2D> filled with vectors.
polygon.body is a pointer to an instance of Object . In this case, it was used only to obtain a position.
polygon.body->position is an instance of Vector2D containing the X and Y coordinates.
Vector2D polygon.body->GetPosition() returns the position vector of the body.

It works fine, except that it rotates around the point [0, 0] but it should rotate around the center of mass.

I know that rotation around a point can be done as follows:

 rotationMatrix * (vertex - point) + point 

And it works great when rendering polygons. But not in collision detection.

How to rotate vectors around a certain point in this case?

EDIT: That's what I still have

 double Polygon::FindAxisLeastPenetration(unsigned int *faceIndex, const Polygon &polygonA, const Polygon &polygonB) const { double bestDistance = -std::numeric_limits<double>::infinity(); unsigned int bestIndex; for (unsigned int i = 0; i < polygonA.points.size(); i++) { // Calculate normal unsigned int j = i == points.size() ? 0 : i + 1; Vector2D n; // Rotate points Vector2D p1 = polygonA.rotationMatrix * (polygonA.points[i] - polygonA.Center()) + polygonA.Center(); Vector2D p2 = polygonA.rotationMatrix * (polygonA.points[j] - polygonA.Center()) + polygonA.Center(); nx = p2.y - p1.y; ny = -(p2.x - p1.x); n.Normalize(); Vector2D support = polygonB.points[polygonB.GetSupport(-n)]; support = polygonB.rotationMatrix * (support - polygonB.Center()) + polygonB.Center(); support.Add(polygonB.body->GetPosition()); Vector2D vertex = polygonA.points[i]; vertex = polygonA.rotationMatrix * (vertex - polygonA.Center()) + polygonA.Center(); //ROTATION vertex.Add(polygonA.body->GetPosition()); double distance = n.DotProduct(support - vertex); if (distance > bestDistance) { bestDistance = distance; bestIndex = i; } } *faceIndex = bestIndex; return bestDistance; } unsigned int Polygon::GetSupport(const Vector2D &dir) const { double bestProjection = -std::numeric_limits<double>::infinity(); unsigned int bestIndex = 0; for (unsigned int i = 0; i < points.size(); i++) { Vector2D vertex = rotationMatrix * (points[i] - center) + center; double projection = vertex.DotProduct(dir); if (projection > bestProjection) { bestProjection = projection; bestIndex = i; } } return bestIndex; } 

Now I don’t care about optimization. There is the same problem. When rotating around the center of the collisions are not detected properly. However, if the center is [0, 0] or it is not used, then the collision detection works correctly, but again the rotation is not performed correctly.

Edit: even when turning before collision detection, I get the same problem. The best approach so far has been to translate the polygon so that its center is at [0, 0] , but no collisions were detected at some angles. I don’t know what to do now.

Edit: screenshots (polygons are translated so that their centers of mass are always at [0, 0] , in this case polygons are rectangles) Collision detection does not work here

Collision detection also works poorly

Collision detection worked well here

Edit: I added a Rectangle class.

Answer 1

This should work regardless of whether the polygon is aligned with the center of gravity. I will start with the most important material and finish supporting methods that have changed.

Edit: Revised implementation.

 struct Response { Response() : overlap(std::numeric_limits<double>::max()) {} Vector2D axis; double overlap; }; bool FindAxisLeastPenetration(const Polygon& a, const Polygon& b, Response* response) { for ( unsigned long i = 0; i < a.points.size(); i++ ) { Vector2D axis = a.normals[i]; Vector2D support = b.GetSupport(-axis); double overlap = axis.DotProduct(a.points[i] - support); if (overlap <= 0.0) return false; if (overlap < response->overlap) { response->overlap = overlap; response->axis = axis; } } return true; } bool CheckCollisionLocal(const Polygon& a, const Polygon& b, Vector2D* min_translation) // @note assumes untransformed polygons. { Polygon worldA = a.ToWorld(); Polygon worldB = b.ToWorld(); Response responseA; Response responseB; if (!FindAxisLeastPenetration(worldA, worldB, &responseA)) return false; if (!FindAxisLeastPenetration(worldB, worldA, &responseB)) return false; if (responseA.overlap <= responseB.overlap) *min_translation = responseA.axis * responseA.overlap; else *min_translation = -responseB.axis * responseB.overlap; return true; } 

Use case

 bool HandleCollisionLocal(Polygon& a, Polygon& b) { Vector2D translation; if (!CheckCollisionLocal(a, b, &translation)) return false; if (MOVE_POLYGON_A) a.body.SetPosition(a.body.GetPosition() - translation); else b.body.SetPosition(b.body.GetPosition() + translation); return true; } 

Support,

 Polygon Polygon::ToWorld() const { Polygon result = *this; for ( auto& point : result.points ) { point = result.rotationMatrix * point; point.Add(result.body.GetPosition()); } for ( auto& normal : result.normals ) normal = result.rotationMatrix * normal; return result; } Vector2D Polygon::GetSupport(const Vector2D& direction) const { double best_projection = -std::numeric_limits<double>::max(); Vector2D best_point; for ( auto point : points ) { double projection = point.DotProduct(direction); if (projection > best_projection) { best_projection = projection; best_point = point; } } return best_point; } 

Note. . This version inverts the translation vector to fit - which seems standard.