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\$
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).

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ You have the indices labeled last and prev which is confusing. Better to call them cur and prev. \$\endgroup\$ – Nathan Reed Oct 8 '13 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 '13 at 9:41
  • \$\begingroup\$ @Tordin That's why I stated the assumption is a convex polygon. \$\endgroup\$ – RandyGaul Oct 8 '13 at 15:53
  • \$\begingroup\$ Oh, yeah my misstake there. i missed that part :) \$\endgroup\$ – Tordin Oct 9 '13 at 6:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.