CutHoleInShape doesn't seem to work right

Sep 24, 2009 at 7:13 PM

So I'm trying to use triangulator in a non-gaming setting, but I've been using the DemoApp to try slicing up some different scenarios.  I've got the following code that attempts to put two holes into a rectangle and then triangulate it.  The demo app draws it quite unexpectedly.

Note, you could just drop this into Game1.cs in replacement of the existing code at the start of CreateGeometry.

            // create or load in some vertices
            Vector2[] sourceVertices = new Vector2[]
            {
                new Vector2(0, 80),
                new Vector2(80, 0),
                new Vector2(200, 120),
                new Vector2(120, 200)
            };

            //create our hole vertices
            Vector2[] holeVertices = new Vector2[]
            {
                new Vector2(40, 60),
                new Vector2(80, 20),
                new Vector2(100, 40),
                new Vector2(60, 80),
            };

            // cut the hole out of the source vertices
            sourceVertices = Triangulator.Triangulator.CutHoleInShape(sourceVertices, holeVertices);


            var holeVertices2 = new Vector2[]
            {
                new Vector2(80, 100),
                new Vector2(100, 80),
                new Vector2(140, 120),
                new Vector2(120, 140),
            };

            // cut the hole out of the source vertices
            sourceVertices = Triangulator.Triangulator.CutHoleInShape(sourceVertices, holeVertices2);

Should this work?

Apr 14, 2010 at 6:41 PM

Ok, I guess it's a bit late but basically, the CutHoleInShape method is forcing all sourceVertices to counter-clockwise winding order before adding the holeVertices. So adding a second hole will probably have the first one messed up since the already-added hole vertices' winding order will be reversed. I guess it could be fixed by not forcing any winding order and assuming the caller did it's job and has correctly wound the sourceVertices on its own.

Apr 28, 2010 at 11:50 PM

I ended up making some progress on this later by reading the paper on Eberly's ear clipping algorithm.  In section 5 (page 10), it reads:

Given multiple inner polygons,  the one containing the vertex of maximum x-value of all inner polygon vertices is the one chosen to combine with the outer polygon.  The process is then repeated with the new outer polygon and the remaining inner polygons.

Based on this, I changed my algorithm to sort my holes so that they would be sorted by the highest x-value in each hole, in descending order.