I'm trying to get around the rule of only being able to form convex shapes in the SFML C++ library.

To do this I'm planning on testing given vertices, and if concave, splitting the vertices into groups, testing each groups' concaveness, and repeating until a full set of convex shapes results that look just like the original shape when put together

What I would like to know is...

  • What the equation for testing a shapes concaveness is: what is it and how does it work?

  • How would I split up the vertices of the concave shape so in the end the shape is formed out of as few convex shapes as possible?

  • Whats the best practice for achieving my goal?



Rather than a top down approach, try a bottom up one. I.e., grow convex regions out of sets of vertices (starting with a tetrahedron), then grow these by adding adjacent (in terms of triangle connectivity). When you cannot find another vertex to add, find an unadded tetrahedron (easily started from 2 adjacent triangles with non-reflexive angle on the interior shared edge), and repeat.

Detecting if adding the vertex will maintain convexity is relatively easy (note that you are not just adding to a convex hull - effectively, if adding a vertex to the convex hull you are growing results in one of the surface vertices becoming interior to the hull, it is not a valid point to add). The tricky bit is determining which vertices should be added to minimize the number of convex volumes. In practice this is a hard optimization problem, and heuristics are likely good enough to get a "good enough" decomposition.

Incidentally, if you want to read up more on this, the term you want to search for is "3D Convex Decomposition". FYI, a BSP tree will also give you a convex decomposition of a non-convex object, but it will be far from minimal.

  • \$\begingroup\$ Is htis faster than my other answer? or less memory-hogging? \$\endgroup\$ – Griffin Jul 14 '11 at 6:08
  • \$\begingroup\$ Also could you look at the questions i posted as comments under the other answer? \$\endgroup\$ – Griffin Jul 14 '11 at 6:08
  • \$\begingroup\$ The other approach is close to working, but the convex decomposition can be really bad and won't handle some cases. Consider two disjoint spheres: First, the capsule enclosing both spheres is found, then half of each sphere becomes its own object: so far so good, but then the next step will find two disjoint, possibly coplanar sets (failure case, since no volume is found). Bottom up approach: the region will grow to one sphere, then stop when it cannot grow to the other sphere. Then it will grow a tetrahedron from the other sphere, and finish correctly, with an optimal subdivision. \$\endgroup\$ – Crowley9 Jul 14 '11 at 6:26

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