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?

  • \$\begingroup\$ 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? \$\endgroup\$ Commented Apr 1, 2013 at 20:53
  • \$\begingroup\$ @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. \$\endgroup\$ Commented Apr 2, 2013 at 0:06
  • \$\begingroup\$ mathoverflow.net/questions/41647/… \$\endgroup\$ Commented Apr 2, 2013 at 0:29

3 Answers 3


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.


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/


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

  • 1
    \$\begingroup\$ Hi Masked Rebel, link-only answers are discouraged here. If the URL ever changes or the resource becomes unavailable, it can leave answers that depended wholly on the link completely empty of solutions for future users. It's great to provide links for credit & further reading, as long as your answer can still stand on its own and provide a guide to solving the problem even before the reader clicks deeper. Please consider editing this answer to include at least a broad outline of how the solution you're linking to works. \$\endgroup\$
    – DMGregory
    Commented May 27, 2018 at 17:17
  • \$\begingroup\$ @DMGregory Please delete the answer I can't myself. \$\endgroup\$
    – user116458
    Commented May 27, 2018 at 18:35
  • \$\begingroup\$ The answer isn't necessarily in need of deletion. Just editing it to include some more information could make it a great answer. \$\endgroup\$
    – DMGregory
    Commented May 27, 2018 at 18:37
  • \$\begingroup\$ @DMGregory but then it'll be a duplicate of another answer on this post. I'll just edit the other answer and put my info there. \$\endgroup\$
    – user116458
    Commented May 27, 2018 at 18:42
  • \$\begingroup\$ I presume you felt you had something new to add when you shared this answer in the first place. I don't doubt that you can explain the code you've linked in a way that's not a carbon copy of an existing answer. If you'd prefer to delete it though, the link to do so is available to you on the desktop version of the site. \$\endgroup\$
    – DMGregory
    Commented May 27, 2018 at 18:45

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .