Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

I'd like to be able to decompose a concave mesh into a set of convex meshes for 2 reasons:

  1. Transparent rendering
  2. Physics shapes

Is there an algorithm that takes a set of triangles (concave) as input and outputs a number of sets of triangles (convex)? I'd like it to not fill in the holes between parts of the original mesh.

I've already come across a small idea: find all the concave edges, and split the meshes along the edge loops. Am I on the right track? How could I implement this?

share|improve this question
    
What is "concave/convex" mesh? If mesh means triangle network, then it is just a set of triangles, which are convex. Or are you talking about the volume of 3D objects? Maybe polyhedrons? –  Ivan Kuckir Apr 1 '13 at 20:53
    
@IvanKuckir Meshes, or polyhedra, can be concave/convex too, and the definition is pretty much the same. For example, no straight line will intersect the interior of the polyhedron more than once. –  congusbongus Apr 2 '13 at 0:06
    

2 Answers 2

I'd say you are on the right track, but coming up with an optimal and/or efficient algorithm is another matter: it's a difficult problem. However, unless your interest is academic, a good-enough solution may suffice.

First, if you are not interested in coming up with your own solution, CGAL contains an algorithm for convex polyhedra decomposition already: http://doc.cgal.org/latest/Convex_decomposition_3/index.html

Now for the method; like many problems in 3D, it's often helpful to consider the 2D problem which is easier to understand. For 2D, the task is to identify reflex vertices, and split the polygon into two by creating a new edge (and possibly new vertices) from that reflex vertex, and continuing until you are left with no reflex vertices (and hence all-convex polygons).

reflex vertices

Polygon Decomposition by J. Mark Keil contains the following algorithm (in unoptimised form):

diags = decomp(poly)
    min, tmp : EdgeList
    ndiags : Integer
    for each reflex vertex i
        for every other vertex j
            if i can see j
                left = the polygon given by vertices i to j
                right = the polygon given by vertices j to i
                tmp = decomp(left) + decomp(right)
                if(tmp.size < ndiags)
                    min = tmp
                    ndiags = tmp.size
                    min += the diagonal i to j
    return min

Basically it exhaustively compares all possible partitions, and returns the one with the least diagonals produced. In this sense it is somewhat brute-force and optimal as well.

If you want "nicer looking" decompositions, that is ones that produce more compact shapes rather than elongated ones, you could also consider this one produced by Mark Bayazit, which is greedy (hence much faster) and looks nicer but has a few shortcomings. It basically works by trying to connect reflex vertices to the best one opposite to it, typically to another reflex vertex:

bayazit new vertex bayazit connect to another reflex vertex

One of the shortcomings is that it ignores "better" decompositions by creating Steiner points (points that do not exist on an existing edge):

clover decomposition using two steiner points

The problem in 3D can be similar; instead of reflex vertices, you identify "notch edges". A naive implementation would be to identify notch edges, and perform plane cuts on the polyhedron repeatedly until all polyhedra are convex. Check out "Convex Partitions of Polyhedra: a Lower Bound and Worst-Case Optimal Algorithm" by Bernard Chazelle for more details.

polyhedron with notch

Note that this approach could produce worst case an exponential number of sub-polyhedra. This is because you could have degenerate cases like this:

many notched polyhedron

But if you have a non-trivial mesh (think bumpy surface), you'll get poor results anyway. It's very likely that you'll want to do a lot of simplification beforehand, if you ever need to use this for complex meshes.

share|improve this answer

Computing an exact convex decomposition of a surface S is an NP-hard problem and usually produces a high number of clusters. To overcome these limitations, the exact convexity constraint may be relaxed and an approximate convex decomposition of S is instead computed. Here, the goal is to determine a partition of the mesh triangles with a minimal number of clusters, while ensuring that each cluster has a concavity lower than a user defined threshold.

Exact convex decomposition vs. approximate convex decomposition

Check out the following approximate convex decomposition libraries: https://code.google.com/p/v-hacd/ http://sourceforge.net/projects/hacd/

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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