Convex polygonisation of sprite

Question

I'm developing a collision system for my game and I want it to be generic. Also I want to make objects bounce between themselves, so the shape of the sprite is important. My problem is that I need to convert my sprite shape into a polygon / polygons.

My final question will be: Do you know a way to do it that will be more easy than mine or a way to make mine work ?

Now, here are the details of what I've currently done:

I implemented the axis separating algorithm to detect intersections between my polygons.

To create the polygons I first implemented the marching square algorithm to get the contour of the internal shape, then I convert it into segments.

I now have a polygon, but it can be concave, that's why I need to find a way to split it into multiple convex polygons.

I tried to implement the ear clipping algorithm but there are some cases where is fails. Also I've read somewhere that it doesn't work when the polygon self intersects.

Bellow some bad visuals of my problem:

Also, bellow is the skeleton I generated for that sprite, sorry it's a draw, but it's just to give you more visual information:

As you can see I also 'crop' the corners (don't know how to say it).

Ok, so should the ear clipping algorithm work on that polygon and the problem comes from my implementation or is it not supposed to work ?

Also my next goal was to merge the triangles while the were still forming a convex polygon. I'm also looking for an easier way to do it if you know one.

Thanks in advance.

EDIT-1

Code of my implementation of the triangulation:

#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, {}};
}

My points are in counterClockwise order, the problem comes from the isConvex method where, for my first image, it will return true.

EDIT 2

Thank you @svs for the notes, I updated the code in EDIT 1 for the others to see, bellow is my bad drawing of the obtained result:

Answer 1

The ear clipping algorithm should be able to triangulate this polygon without a problem so I think you have a problem with the implementation. Here are couple of things you could check so that you ensure that you've implemented it correctly:

• make sure you input the polygon vertices in a consistent manner - either clockwise or counterclockwise. For example, if you have a square with vertices (0, 0), (1, 1), (1, 0), (0, 1) you should input the polygon as vertices (0, 0), (0, 1), (1, 1), (1, 0) if you use the counterclockwise manner

• check your algorithm for testing if a vertex is an 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 is a formula for signed area.

Seeing your code you should move the deleting statement of a vertex outside the polygon vertex loop. The psedocode of the algorithm is:

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

The problem is that you delete the vertex while you check if there exist a vertex of the polygon in the triangle. Update your code to:

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