c++ - Sprite 的凸多边形化

Question

我正在为我的游戏开发一个碰撞系统，我希望它是通用的。我还想让物体在它们之间反弹，所以 Sprite 的形状很重要。我的问题是我需要将 Sprite 形状转换为多边形。

我的最后一个问题是:您是否知道一种比我的方法更容易的方法或使我的方法起作用的方法？

现在，这是我目前所做工作的详细信息:

我实现了轴分离算法来检测多边形之间的交点。

为了创建多边形，我首先实现了行进方形算法来获取内部形状的轮廓，然后将其转换为线段。

我现在有一个多边形，但它可以是凹的，这就是为什么我需要找到一种方法将它分割成多个凸多边形。

我尝试实现耳朵剪裁算法，但在某些情况下会失败。另外我在某处读到，当多边形自相交时它不起作用。

下面是我的问题的一些糟糕的视觉效果:

另外，下面是我为那个 Sprite 生成的骨架，抱歉这是一个平局，但这只是为了给你更多的视觉信息:

如你所见，我还“裁剪”了边角(不知道怎么说)。

好吧，耳朵剪裁算法应该在那个多边形上工作吗？问题来 self 的实现，还是它不应该工作？

另外，我的下一个目标是在三角形仍形成凸多边形时合并它们。如果您知道的话，我也在寻找一种更简单的方法。

提前致谢。

编辑-1

我实现三角剖分的代码:

#include "Triangulation.hh"

bool Triangulation::isConvex(const Position &a, const Position &b,
                             const Position &c) const {
  float crossp = (c.x - a.x) * (b.y - a.y) - (c.y - a.y) * (b.x - a.x);
  return (crossp >= 0 ? true : false);
}

bool Triangulation::inTriangle(const Position &a, const Position &b,
                               const Position &c, const Position &x) const {
  std::array<float, 3> barCoef = {0, 0, 0};

  barCoef[0] = ((b.y - c.y) * (x.x - c.x) + (c.x - b.x) * (x.y - c.y)) /
               (((b.y - c.y) * (a.x - c.x) + (c.x - b.x) * (a.y - c.y)));
  barCoef[1] = ((c.y - a.y) * (x.x - c.x) + (a.x - c.x) * (x.y - c.y)) /
               (((b.y - c.y) * (a.x - c.x) + (c.x - b.x) * (a.y - c.y)));
  barCoef[2] = 1.f - barCoef[0] - barCoef[1];

  for (float coef : barCoef) {
    if (coef >= 1 || coef <= 0)
      return false;
  }
  return true;
}

std::pair<bool, std::array<Position, 3>>
Triangulation::getEar(std::vector<Position> &polygon) const {
  int size = polygon.size();
  bool triTest = false;
  std::array<Position, 3> triangle;

  if (size < 3)
    return {false, triangle};
  else if (size == 3) {
    triangle = {polygon[0], polygon[1], polygon[2]};
    polygon.clear();
    return {true, triangle};
  } else {
    for (int i = 0; i < size; ++i) {
      triTest = false;
      triangle[0] = polygon[(i + size - 1) % size];
      triangle[1] = polygon[i];
      triangle[2] = polygon[(i + 1) % size];
      if (this->isConvex(triangle[0], triangle[1], triangle[2])) {
        for (const Position &point : polygon) {
          auto it = std::find(triangle.begin(), triangle.end(), point);

          if (it != triangle.end())
            continue;
          if (this->inTriangle(triangle[0], triangle[1], triangle[2], point)) {
            triTest = true;
            break;
          }
        }
        if (triTest == false) {
          polygon.erase(polygon.begin() + i);
          return {true, triangle};
        }
      }
    }
  }
  return {false, {}};
}

我的观点是逆时针顺序的，问题出在 isConvex 方法上，对于我的第一张图片，它会返回 true。

编辑 2

感谢@svs 的注释，我更新了 EDIT 1 中的代码供其他人查看，下面是我对获得结果的错误绘制:

Answer 1

剪耳算法应该能够毫无问题地对该多边形进行三角剖分，所以我认为您的实现有问题。以下是您可以检查的几项内容，以确保您已正确实现它:

• 确保以一致的方式输入多边形顶点 - 顺时针或逆时针。例如，如果您有一个顶点为 (0, 0), (1, 1), (1, 0), (0, 1) 的正方形，您应该输入多边形作为顶点 (0, 0), (0, 1), (1, 1), (1, 0)如果使用逆时针方式

• 检查您的算法以测试顶点是否为 ear再次。如果你使用顺时针方式，顶点 v[i]=(x[i], y[i]) 是一个耳朵，如果顶点 v[i- 1]=(x[i-1], y[i-1])), v[i], v[i+1]=(x[i+1], y[i+1])) 为正，多边形的任何点都不在 v[i-1], v[i], v[i+1] 的内部。 Here是有符号面积的公式。

查看您的代码，您应该将顶点的删除语句移到多边形顶点循环之外。该算法的伪代码为:

for each vertex v[i] of the polygon:
    if v[i] is an ear:
        if there is no polygon vertex in triangle v[i-1], v[i], v[i+1]:
            delete vertex v[i] from the polygon

问题是您在检查三角形中是否存在多边形的顶点时删除了顶点。将您的代码更新为:

if (this->isConvex(triangle[0], triangle[1], triangle[2])) {
    for (const Position &point : polygon) {
        auto it = std::find(triangle.begin(), triangle.end(), point);

        if (it == triangle.end())
            continue;
        if (this->inTriangle(triangle[0], triangle[1], triangle[2], point)) {
            triTest = true;
            break;
        }
    }
    if (triTest == false) {
        polygon.erase(polygon.begin() + i);
        return {true, triangle};
    }
}