分离轴定理：绕质心旋转

Question

问题出现在函数中：

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是一个类型为Matrix22的对象，它是一个2x2矩阵。
polygon.points是填充有向量的std::vector<Vector2D>。
polygon.body是指向Object实例的指针。在本例中，它仅用于获取位置。
polygon.body->position是包含X和Y坐标的Vector2D实例。
Vector2D polygon.body->GetPosition()返回一个体的位置向量。

它的工作正常，唯一的问题是旋转是围绕[0, 0]点进行的，但应该围绕质心旋转。

我知道，可以像这样围绕一个点进行旋转：

rotationMatrix * (vertex - point) + point

在渲染多边形时，它可以正常工作。但在碰撞检测中则不行。

在这种情况下，如何围绕某个点旋转向量？

编辑：以下是我目前的进展

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();
    n.x = p2.y - p1.y;
    n.y = -(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;
}

现在我不太关心优化。问题仍然存在：当围绕中心旋转时，碰撞检测无法正常进行。但是，如果中心点是[0,0]或者根本没有使用，则碰撞检测可以正常工作，但旋转仍然会出现错误。

编辑：即使在碰撞检测之前进行旋转，我也遇到了同样的问题。 目前为止最好的方法是将多边形平移，使其质心位于[0, 0]，但在某些角度下无法检测到碰撞。现在不知道该怎么办了。

编辑：截图（这里的多边形被平移到它们的重心始终在[0,0]，在这种情况下，多边形是矩形） 碰撞检测在这里运作不良 这里碰撞检测也无法正常工作 碰撞检测在这里正常工作 编辑：我添加了Rectangle类。

- ivknv

---

@uitty400 没有。一切都是定制的。您是在寻找某个函数或类的实现吗？ - ivknv

你需要澄清你正在做什么。这看起来不像是两个多边形的交集代码。points是什么，它从哪里来？polygon.GetSupport()是什么？polygon.body和它的.position是什么？ - Nico Schertler

@SPython 那个旋转是在哪里完成的？ - Kyle

@Kyle 我已经用 //ROTATION 注释标记了旋转操作的行数。 - ivknv

你不能将模型的质心转换到原点的原因是什么？ - Johnny Cage

Answer 1

这应该可以工作，无论多边形原点是否与重心对齐。我将从最重要的内容开始，以支持已更改的支持方法结束。

编辑：修订实现。

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;
}

使用案例，

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;
}

支持，

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;
}

注意：此版本将翻译向量反转以符合 - 似乎是 - 标准。

- Johnny Cage