Game Development Stack Exchange is a question and answer site for professional and independent game developers. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?


share|improve this question

closed as off topic by Tetrad Aug 17 '11 at 15:46

Questions on Game Development Stack Exchange are expected to relate to game development within the scope defined by the community. Consider editing the question or leaving comments for improvement if you believe the question can be reworded to fit within the scope. Read more about reopening questions here.If this question can be reworded to fit the rules in the help center, please edit the question.

User posted this same question to stackoverflow. Answer is already there:… – Trevor Powell Jul 14 '11 at 0:39
yeah should i leave this question here on gamedev since it pertains to that to (for futur users) or delete this? – Griffin Jul 14 '11 at 4:21
Related:… – bummzack Jul 14 '11 at 8:04
up vote 0 down vote accepted

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.

share|improve this answer
Is htis faster than my other answer? or less memory-hogging? – Griffin Jul 14 '11 at 6:08
Also could you look at the questions i posted as comments under the other answer? – Griffin Jul 14 '11 at 6:08
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. – Crowley9 Jul 14 '11 at 6:26

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