精灵的凸多边形化

Question

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

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

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

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

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

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

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

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

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

如你所见，我也'crop'角（不知道怎么说）。

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

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

提前致谢。

编辑-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 方法上，对于我的第一张图片，它将 return 为真。

编辑 2

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

Answer 1

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

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

(0, 0), (0, 1), (1, 1), (1, 0)

检查您的算法以测试顶点是否是 ear again. If you you are using the clockwise manner a vertex v[i]=(x[i], y[i]) is an ear if the signed area of the vertices v[i-1]=(x[i-1], y[i-1])), v[i], v[i+1]=(x[i+1], y[i+1])) is positive and no point of the polygon is in the interior of 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};
    }
}

精灵的凸多边形化

Convex polygonisation of sprite

c++

algorithm

2d

triangulation

c++11