Breaking down a concave mesh into convex pieces

Apprentice
Posts: 11
Joined: 2007.02
Post: #1
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. Rasp Obviously.

Any thoughts?
Quote this message in a reply
Apprentice
Posts: 11
Joined: 2007.02
Post: #2
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.
Quote this message in a reply
Oldtimer
Posts: 834
Joined: 2002.09
Post: #3
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?
Quote this message in a reply
Apprentice
Posts: 11
Joined: 2007.02
Post: #4
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).
Quote this message in a reply
Luminary
Posts: 5,143
Joined: 2002.04
Post: #5
You may find http://www.cgal.org/ interesting, or overwhelming. I can't decide which camp I'm in.
Quote this message in a reply
Apprentice
Posts: 11
Joined: 2007.02
Post: #6
Thanks! That site is definitely overwhelming but I'll give it a once over...
Quote this message in a reply
Post Reply 

Possibly Related Threads...
Thread: Author Replies: Views: Last Post
  how to create a grid / 2D mesh bfarah 1 4,028 Oct 20, 2010 02:22 AM
Last Post: iamflimflam1
  Boolean Mesh Operations and Mesh-Based CSG Oddity007 2 5,627 Feb 13, 2010 03:42 PM
Last Post: Oddity007
  OpenGL and concave meshes Ashford 3 4,179 Nov 21, 2009 10:31 AM
Last Post: AnotherJake
  OpenGL ES creating a 2D mesh soulstorm 0 2,964 May 20, 2009 02:37 AM
Last Post: soulstorm
  Spherical Mesh. dave05 8 5,793 Oct 29, 2008 02:53 PM
Last Post: mholg