6
\$\begingroup\$

I am creating a game engine using the JBox2D physics engine. It only allows you to create polygon fixtures up to 8 vertices, To create a body with more than 8 vertices, you need to create multiple fixtures for the body.

My question is, How can I split the polygons a user creates into smaller polygons for JBox2D?

Also, what topology should I use when splitting the polygons and why? (If JBox2D can have up to 8 vertices, why not split polygons into 8 per polygon)

\$\endgroup\$
2

1 Answer 1

5
\$\begingroup\$

This simple algorithm assumes you're working with a convex polygon (in the case of physics engines you definitely should be):

Loop over the polygon with two indices, one called next and one called last. This is also known as a format called "Triangle Fan". Here's a demo image:

enter image description here

You set up these two indices and loop something like this:

TriVertexList TriangleFan( int vCount, Vec2[] v )
{
  int start = 0;
  int last = 1;
  int prev = 0;
  TriVertexList out;

  while(start != last)
  {
    out.push( v[start], v[last], v[prev] );
    prev = last;
    last = last + 1 == vCount ? 0 : last + 1;
  }

  return out;
}

This algorithm can easily be extended to 3D (which I currently use to triangulate my 3D meshes).

\$\endgroup\$
4
  • \$\begingroup\$ You have the indices labeled last and prev which is confusing. Better to call them cur and prev. \$\endgroup\$ Oct 8, 2013 at 1:40
  • \$\begingroup\$ And this will create artifacts on more complex shapes. Imagine a U or a A. If you always assume that the 0 is the first index to have as your start point your going to get alot of artifacts. \$\endgroup\$
    – Tordin
    Oct 8, 2013 at 9:41
  • \$\begingroup\$ @Tordin That's why I stated the assumption is a convex polygon. \$\endgroup\$
    – RandyGaul
    Oct 8, 2013 at 15:53
  • \$\begingroup\$ Oh, yeah my misstake there. i missed that part :) \$\endgroup\$
    – Tordin
    Oct 9, 2013 at 6:28

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .