Automatic Convex Decomposition

[Troid92]

There are three two age-old requirements for all polygons added with b2PolygonShape::Set(): they must be convex, they must be in counter-clockwise order, and they must have no more than b2_maxPolygonVertices vertices (8 by default). These allow the calculations to operate efficiently and behave correctly. For example, if two separate prongs of an object hit the ground at the same time, we would want each prong to be of a separate shape so they can create their own collision response (like dirt puffing up). Some of the rules (but not all?) if broken will result in a "convex hull" being generated instead.

I can relate to the possible reasoning for leaving out polygon partitioning / convex decomposition from the Box2D library. I am not sure if there is a precise mission statement somewhere, but on the surface it just feels like this general math problem would not thematically fit itself into a concise kernel of physics. There are multiple approaches and algorithms, each with slightly different behaviors and edge cases. It could quickly become a pain to maintain or guarantee its correctness with all possible polygons, so it is left as sort of an exercise for the reader, if you will.

However, I would like to argue that polygon partitioning is an essential part of a "kernel of physics", and that is should not be left out.

1. Those 3 2 rules for polygons are highly specific to the domain of physics and collision detection, and they would seem arbitrary in other contexts. In other words, exposing these requirements to the API means breaking the "black box" abstraction that a physics system is supposed to provide. It is like a sorting algorithm that requires the user to study how the sorting algorithm works in order to correctly pre-process their list of numbers first. Why not make them write the rest of the algorithm while they're at it? Leaving out a domain-specific step of a process goes against the purpose of automation.
2. Every developer who wishes to use polygons in Box2D must figure out, on their own, how to format their polygons into the well-mannered bite-size chunks that Box2D demands. This takes time, effort, and research, and my guess is there are dozens of unpublished solutions made in the last decade, from kids to students to developers to companies. All we need is one solution. Yes, there is one in the "Contributions" folder. Since it is unofficial, not everyone knows to look there, and it is not maintained or supported here through normal github means. Cleaning it up and promoting it to Box2D proper would save so many developers a lot of time.
3. The fact that there are multiple possible algorithms and implementations did not stop this physics library from existing in the first place. There are vastly different approaches to detecting and resolving collisions, with their own gnarly sets of edge cases and shortcomings, and we put our trust in the library developers to settle on a robust, well-balanced, reasonable approach to help us out in common circumstances. Secretly breaking down our complex polygons into their appropriate internal Box2D formatting would fall under this umbrella. It does not have to be perfect -- it just has to be good enough to handle most situations.
4. Adding this feature would not be taking anything away from what already exists. For those who have already produced correct CCW 8-vertex convex polygons, they can take advantage of the speed benefits of using some sort of "raw" function(s) with those requirements. Those who do not mind the extra processing time can use the non-"raw" function(s).

I get the sense that this has already been a long-time heated topic of discussion, but I hope it can be considered again. It was the first major obstacle I encountered in my earliest attempts to add Box2D to my games 10+ years ago, and I would not be surprised if other developers felt the same way. In my opinion this is one of this library's biggest and most immediate shortcomings and should absolutely find a home within Box2D. I am curious to hear what other people's thoughts are. Thanks.

[erincatto]

Some of those limitations haven't existed for a long time. See https://github.com/erincatto/Box2D/blob/master/Box2D/Collision/Shapes/b2PolygonShape.cpp#L120 This computes the convex hull automatically I agree that it would be useful to have convex decomposition as a supported feature. I don't think it should be the default approach because this may leave some simple optimizations on the table. In some cases people may have complex sprites that should just be wrapped in a box instead of being partitioned into several polygons.

[Troid92]

You're right -- I was mistaken about the winding order. The manual still warns about being careful that CCW might look like CW depending on your coordinate system, but this must be talking about if you are accessing the vertices after you've imported them already. The other requirements still seem to be there, if polygons are to be imported accurately. Thanks for taking a look at this.

[erincatto]

I wrote a blog post about this topic. https://box2d.org/posts/2020/04/stuck-inside/ The bottom line is that if I put a convex decomposition algorithm into Box2D it will be inferior to a human crafted collision. So then it becomes a question of priorities. Do I work on something that I know can directly improve Box2D (like performance) or do I work on something that I know will be inferior and buggy. I'm inclined to do the former.

[Troid92]

On choosing your time wisely: that makes total sense. I disagree that this would not directly improve Box2D (my original points 1 and 2), but I completely understand if you feel there are higher priorities right now.

On being an imperfect solution: I will still counter with my original point 3. As far as I know, the tools simply do not exist to manually craft these polygons myself. The results of an algorithm might fall flat against human-designed meshes, but I would rather have an inferior solution than no solution at all.

Maybe the reason I find this so important is that I am just out of the loop. Are there free tools that would let me manually partition my polygons in a visual editor? Is it easy to load the result into Box2D? I am genuinely curious how others handle this -- I had a hard enough time just getting any of my concave polygons up and running, regardless of how it was done.

[abakobo]

RUBE editor, which is not free(but cheap), has an integrated polygon decomposer, you can load exported scenes with this lib: https://github.com/iforce2d/b2dJson. It uses Bayazit's algorithm for polygon decomposition https://mpen.ca/406/bayazit. there is a download link at the end of the page.

[Troid92]

RUBE is amazing! As you say, it is not free (35 USD at the time of this post). I cannot require my users to purchase it in order to use concave polygons in my software.

Bayazit's algorithm does not account for holes or vertex limits, so RUBE also uses poly2tri in some cases. Right now Box2D users must reinvent this kind of hybrid system themselves in order to generate arbitrary polygons on the fly. Please correct me if I am wrong.

Automatic polygon decomposition is the first bolded item on RUBE's features page and is showcased early in the introductory video. Most of RUBE's screenshots and javascript demos include polygons which were automatically decomposed this way.

To me, this indicates how absolutely essential this bit of code is in interfacing with Box2D. The fact that advanced users can fine-tune their meshes for performance and behavior should not detract from the library's everyday usage.

[erincatto]

Current summary: this is a feature request for convex decomposition