iDevGames Forums
Breaking down a concave mesh into convex pieces - Printable Version

+- iDevGames Forums (http://www.idevgames.com/forums)
+-- Forum: Development Zone (/forum-3.html)
+--- Forum: Graphics & Audio Programming (/forum-9.html)
+--- Thread: Breaking down a concave mesh into convex pieces (/thread-2472.html)



Breaking down a concave mesh into convex pieces - Willem - Aug 10, 2008 02:52 AM

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?


Breaking down a concave mesh into convex pieces - Willem - Aug 10, 2008 03:16 AM

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.


Breaking down a concave mesh into convex pieces - Fenris - Aug 10, 2008 03:36 AM

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?


Breaking down a concave mesh into convex pieces - Willem - Aug 10, 2008 04:09 AM

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).


Breaking down a concave mesh into convex pieces - OneSadCookie - Aug 10, 2008 04:55 AM

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


Breaking down a concave mesh into convex pieces - Willem - Aug 10, 2008 05:49 AM

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