Best way to create compound shapes from concave polygons

help

#1

Hello! I’ve been working with the libraries for a while now, and have a need to add concave objects to the collision world. I’ve found that the best way to do that seems to be via Compound shapes created from a joined set of convex polygons. However, I’m unsure of the best way to go about doing that.

Is the most efficient method triangulation? It would certainly be possible to simply split the concave polygon into a set of triangles and then construct a Compound by joining all of them, but I feel like this would be very expensive to simulate and keep track of all of those (potentially very many) isometries for each of the components. Is there a better way to do this, or am I overestimating the cost of the triangulation approach?


#2

Hi! Sorry for the late answer, I was in vacation.
Depending on your needs several options are possible:

  • Represent your concave objects as polylines. In this case, only the boundary of the object will be seen by the collision world. This is often useful for representing terrains.
  • Represent your concave objects as a Compound where each part is a convex polygon. Those convex polygons can be obtained from a convex decomposition algorithm (or an approximate convex decomposition). In 3D, the HACD algorithm is implemented on ncollide. But nothing is available on ncollide for 2D convex decomposition.
  • (The option you propose) Represent your concave objects as a Compound where each part is a triangle. All the isometries will have a cost, but this cost will be lowered by the acceleration structures used by ncollide internally.

The first option (with polylines) is the most efficient one if you don’t care about the objects’ interior. Otherwise the second option will be the most efficient one (though you will have to implement a convex decomposition if you are working in 2D). The third option should still be good, but the performance and accuracy of various geometric queries may depend on the quality of your triangulation (which should for example avoid triangles that are simultaneously large and thin).


#3

Thank you very much for the reply! The polyline approach sounds like it should work fine for what I’m trying to do. I appreciate you listing off all of the options and explaining the pros/cons of each; it really helps!