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

[louis-langholtz]

From @louis-langholtz on January 12, 2017 15:12

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?

Copied from original issue: louis-langholtz/Box2D#7

[louis-langholtz]

From @Genbox on April 2, 2017 11:39

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.

[louis-langholtz]

From @Genbox on April 6, 2017 20:42

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.

[louis-langholtz]

From @Genbox on April 30, 2017 9:54

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]

I've added a MultiShape Shape subclass for this. Not sure how I feel about it conceptually though. As an advantage, since it's a Shape, it's a memory-wise sharable data-structure (via std::shared_ptr<const Shape>). I don't like that it sort of repeats the functionality that creating new fixtures does though. It's also a generalization in a sense of all the other shape subclasses suggesting that perhaps they serve no purpose with MultiShape being around. Using the other shape specific subclasses can be more memory efficient too though depending on how stuff is used.

Comments/feedback welcome!

[Hexlord]

The way to go for me is to use polyline simplification and folllow it up by GLU triangulation, and if there are still small triangles (area < 5 pixels or smth) you do not add them as fixtures to your body, you only render them (seperate body and renderable geometry). Simplification has major flows when working with holes, but there are workarounds to discuss.

This could be a part of release milestone, part of some playrho ImageToShape functionality, I could help with this one as I have some code drafts.

[louis-langholtz]

On a related note, there is the StackOverflow question "Box2d: Why not concave shapes?" and my response.

And I found the following related question on math exchange: Concave polygons overlapping test. The accepted answer references the sweep line algorithm as an efficient solution.

[Genbox]

Adding to what you wrote on StackOverflow. Back in 2007 Farseer Physics Engine used a grid based narrow phase solver (i forgot what it was called). Every object had a NxN grid and both convex and concave polygons were supported. However, you had to tune your grid-size to fit the polygon. Smaller grid sizes meant slower collisions and larger sizes meant imprecise collisions.

You could have ~100 concurrent objects on a single CPU core colliding before you went above 25 ms pr. loop. When I ported Box2D to use the SAT solver instead, we suddenly went to thousands of concurrent objects.

One of most effective collision detection algorithms is still SAT, so instead of trying to solve concave polygon collisions with an O(N^2) solver, Erin added support for fixtures, which is still fast enough.

[louis-langholtz]

@Hexlord I've opened issue #276 for moving forward with adding code to do unions, intersections and differences of shapes. I believe that will require the kinds of techniques you mentioned. If you're interested still, please read the issue specifics and give it a go! I'd like to be able to use the MultiShapeConf for the resulting shapes as it should be able to represent any convex or concave result.

I'm closing this issue since PlayRho has the MultiShapeConf which supports concave polygons.