Convex decomposition w/ Holes

Oct 21, 2013 at 7:08 AM
Edited Oct 21, 2013 at 7:09 AM
Hey guys,

I've got some tile maps for my game I need to break down into solid body shapes. Been using Borders for the past few years and I get weird bugs where bullets clip through walls, which doesn't cut it for me. So I'm trying now to decompose my level into convex shapes while also supporting holes.

Tiny image. Walls are black pixels, space is white. White is contiguous, black is not. Image

I've spent a few weekends on this and I've had success when there isn't a hole in the shape... Any ideas of how to get this to work with holes?

Screeny: Image
Oct 21, 2013 at 1:33 PM
I read your question a couple times, but I couldn't figure out what you are exactly trying to accomplish. Are you trying to make a shape as in the Farseer advanced samples "Texture to vertices"? If you haven't seen it yet, you can download it here obviously and take a look.

Or maybe try to clarify it some more?
Oct 21, 2013 at 5:56 PM
That was at 11pm after many hours of code. I'll see if I can describe the problem better.

When you do TextureToVertices, you get a bunch of vertices that you then have to decompose into convex polygons. So you need to use something like the BayazitDecomposer or other convex decomposition algorithms for that. The issue is, none of the ones that come with Farseer support 'holes'. So that's really what my question is, how to take a list of vertices with a hole in the middle and return something useful. Currently it just returns a solid square, which I can't fly around in.
You can ignore floating parts inside as I can generate those separately.
Oct 21, 2013 at 9:00 PM
Doesn't the CDT decomposer support holes?
Oct 21, 2013 at 9:04 PM
Edited Oct 21, 2013 at 9:33 PM
HAL_9000 wrote:
Doesn't the CDT decomposer support holes?
I couldn't find that anywhere in the docs. Can you link me something that show that? Wish there were more docs on each algorithm and it's use. The marching squares one seems pretty awesome but I don't know how to use it!
Oct 21, 2013 at 9:56 PM
Wouldn't it be easier to simply test the supposition?

Have a look in the source code. Find the CDT decomposer class and it has comments that will tell you what it can do. I'm pretty sure I've used it for hole detection.
Oct 21, 2013 at 10:16 PM
HAL_9000 wrote:
Wouldn't it be easier to simply test the supposition?

Have a look in the source code. Find the CDT decomposer class and it has comments that will tell you what it can do. I'm pretty sure I've used it for hole detection.
    /// <summary>
    /// 2D constrained Delaunay triangulation algorithm.
    /// Based on the paper "Sweep-line algorithm for constrained Delaunay triangulation" by V. Domiter and and B. Zalik
    /// 
    /// Properties:
    /// - Creates triangles with a large interior angle.
    /// - Supports holes
    /// - Generate a lot of garbage due to incapsulation of the Poly2Tri library.
    /// - Running time is O(n^2), n = number of vertices.
    /// - Does not care about winding order.
    /// 
    /// Source: http://code.google.com/p/poly2tri/
    /// </summary>
Looks like you were right! I'll give this a go when I get home. Thanks for the find!
Dec 22, 2013 at 4:43 PM
I have the same problem. You have solved it?

Here is my texture:
Image