I'd like to be able to decompose a concave mesh into a set of convex meshes for 2 reasons:
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?
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).
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:
One of the shortcomings is that it ignores "better" decompositions by creating Steiner points (points that do not exist on an existing edge):
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.
Note that this approach could produce worst case an exponential number of sub-polyhedra. This is because you could have degenerate cases like this:
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.
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.
Check out the following approximate convex decomposition libraries: https://code.google.com/p/v-hacd/ http://sourceforge.net/projects/hacd/
Here is some code that could help you. It is in java so you'll have to convert it to c++.
Here also is another article that can help you
