I've been stuck on this problem for quite a while now. I'm writing a Quake level editor called ToeTag (http://wantonhubris.com/toetag/ToeTag.html) and I want to add a feature where the user can import concave meshes which ToeTag will then break down into convex pieces as it writes out the MAP file for Quake to compile.

I've tried many different methods but I have yet to find one that doesn't generate as many problems as it solves. I've probably tried 5 different rewrites over the course of the last few months and I can't arrive at a decent solution.

Has anyone done this before and be willing to give me a push in the right direction? Even giving me the correct terms to Google for would be great. I can't find anything on the net about this and I'm positive I can't be the first person in history to attempt this. Obviously.

Any thoughts?

As is always the way, as soon as I post this I discover through a random Google search that the term I'm looking for is "decomposition". However, I would still love any input that anyone may have to offer here. I'm terrible at understanding white papers.

I implemented triangulation of arbitrary 2D polygons into triangles three days ago, but I guess you're working in 3D and need convex bodies, not just the triangulation?

Yeah, I'm looking to break down arbitary 3D concave meshes into 3D convex chunks.

If it makes things easier, I can impose limitations like the mesh has to be sealed (no open edges).

You may find http://www.cgal.org/ interesting, or overwhelming. I can't decide which camp I'm in.

Thanks! That site is definitely overwhelming but I'll give it a once over...