Breaking down a concave mesh into convex pieces
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?
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).
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...
Possibly Related Threads...
Thread:  Author  Replies:  Views:  Last Post  
how to create a grid / 2D mesh  bfarah  1  5,179 
Oct 20, 2010 02:22 AM Last Post: iamflimflam1 

Boolean Mesh Operations and MeshBased CSG  Oddity007  2  6,640 
Feb 13, 2010 03:42 PM Last Post: Oddity007 

OpenGL and concave meshes  Ashford  3  4,970 
Nov 21, 2009 10:31 AM Last Post: AnotherJake 

OpenGL ES creating a 2D mesh  soulstorm  0  3,588 
May 20, 2009 02:37 AM Last Post: soulstorm 

Spherical Mesh.  dave05  8  7,332 
Oct 29, 2008 02:53 PM Last Post: mholg 