Concave polygons not supported: what are pros/cons of for this?

[louis-langholtz]

Is it worth supporting concave shapes? Can all concave shapes already be supported via multiple fixtures having convex polygons? Is there a more efficient way to do concave shapes?

I believe that at least part of the problem of supporting concave polygons is supporting inside corners. This seems to have some implementation already in chain/edge shapes.

If nothing else, is there an algorithm for constructing any concave polygon out of convex polygons? Can this be conveyed more easily to users?

[Genbox]

I can weigh in on this. I'm the creator of Velcro Physics (formerly Farseer Physics Engine) which is based on Box2D and I built support for concave polygons into the engine. Due to the engine design, it was rather easy substituting the SAT narrow phase with another implementation that supported concave polygons. After trying a couple of different implementations, which all had their own issues, I finally settled on just using tessellation. Since Box2D supported multiple shapes bound together (fixtures) it seemed like an easy solution. While it does work, there are definitely collision issues due to the fact that often, there will be many points on the polygons straight lines.

If you use some of the more simple triangulation algorithms like Ear Clipping, you will end up with a good result, but one that also removes holes. (Polygon on the left, ear clipped polygon on the right)

If you use something like Bayazit (by Mark Bayazit), you will get holes, but also very narrow polygons which Box2D does not like.

In summary, there are ups and downs to every solution. The simplest is to do triangulation, the best solution is a narrow phase collision algorithm that supports concave polygons, which can be switched out at a moments notice.

[Genbox]

I just remembered that I wrote about this on my blog back in 2009. Nevermind the formatting on the blog, it looks a lot different now than back then.

[louis-langholtz]

@Genbox Thanks for chiming in on this!

I've seen a lot of references to Open Source software that breaks apart concave shapes into collections of convex ones. Conceptually speaking I'm attracted to using non-friend non-member functions to compute the set of convex-sets and then implement those basically using collections of the existing Box2D Shape objects.

A benefit to having something like a ConcaveShape however is its reusability thanks to Shapes being used as shared ownership objects (std::shared_ptr<const Shape>). Are there other benefits? Is this enough of a benefit? I'm not convinced.

I've ripped out most of original Box2D distance and manifold code and left behind only code that deals with DistanceProxy child objects for all shapes. I really like how that feels to me: way cleaner! Everything else can come from that. So that's why I wonder how much use having child aggregating shapes are (like ChainShape or like ConcaveShape would be). These seem like aggregates of aggregates then which could be achieved just by adding more fixtures to a body.

Anyways, that's just some of my thoughts on this.

[Genbox]

Conceptually speaking I'm attracted to using non-friend non-member functions to compute the set of convex-sets and then implement those basically using collections of the existing Box2D Shape objects.

That is the solution I went with. I implemented a couple of different polygon decomposition algorithms (Seidel, Earclip etc.) and made them accessible in a "factory". The factory is just a simple API for creating polygons of all shapes and sizes. Should the user decide to give a concave polygon, I decompose it into multiple convex polygon shapes and attach them with fixtures.

It is not pretty but it seems to work fine. I've also implemented a few simplification algorithms to make sure that user input polygons have as few points as possible before doing the decomposition to make a better result.

[louis-langholtz]

This issue was moved to louis-langholtz/PlayRho#11