c++ - una - teorema de steiner ejemplos

Teorema del eje separador: rotación alrededor del centro de masa

Question

El problema está en 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 es un objeto de tipo Matrix22 que es una matriz de 2x2.
polygon.points es std::vector<Vector2D> lleno de vectores.
polygon.body es un puntero a una instancia de Object . En este caso, solo se usa para obtener posición.
polygon.body->position es una instancia de Vector2D contiene coordenadas X e Y
Vector2D polygon.body->GetPosition() devuelve el vector de posición de un cuerpo.

Funciona bien, excepto que la rotación se realiza alrededor del punto [0, 0] , pero se supone que gira alrededor del centro de masa.

Sé que la rotación alrededor de un punto se puede hacer así:

rotationMatrix * (vertex - point) + point

Y funciona bien cuando se renderizan polígonos. Pero no en la detección de colisiones.

¿Cómo giro los vectores alrededor de cierto punto en este caso?

EDITAR: Esto es lo que tengo hasta ahora

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

En este momento, realmente no me importan las optimizaciones. Hasta el mismo problema. Al girar alrededor del centro, las colisiones no se detectan correctamente. Sin embargo, si el centro es [0, 0] o no se utiliza, la detección de colisión funciona correctamente, pero nuevamente la rotación se realiza de forma incorrecta.

Editar: Incluso cuando se rota antes de la detección de colisiones, aparece el mismo problema. El mejor enfoque hasta ahora fue traducir el polígono de modo que su centro estuviera en [0, 0] , pero en algunos ángulos las colisiones no se detectan. No tengo idea de qué hacer ahora.

Editar: capturas de pantalla (los polígonos se están traduciendo para que sus centros de masa estén siempre en [0, 0] , los polígonos son rectángulos en este caso) La detección de colisión no funcionó bien aquí

La detección de colisiones no funcionó bien aquí también

Detección de colisiones funcionó bien aquí

Editar: agregué la clase Rectangle .

Answer 1

Esto debería funcionar ya sea que el origen del polígono esté alineado o no con el centro de gravedad. Comenzaré con las cosas más importantes y terminaré con los métodos de apoyo que han cambiado.

Editar: Implementación revisada.

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

Caso de uso,

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

Apoyo,

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

Nota: Esta versión invierte el vector de traducción para cumplir con lo que parece ser el estándar.