TriangulatePolygon result of YuPengClipper.Difference

Topics: Developer Forum, User Forum
Nov 23, 2010 at 7:03 AM

Is this possible?  I have the following verticies.  Its basically a smaller square within a larger square (but could be quite complex of a smaller square, concave, but no holes/circles/rounded edges).  What I want is triangles of the difference.  Specifically, think of taking the larger square (vertsA) and cutting out vertsB from it with scissors, and then taking that result and triangulating it, then that result can be used for my game objects to bounce off of, appearing to the player that game objects bounce around within vertsB and bouncing off of vertsA, vertsA being used in Farseer.  If there is some other way great, however, the game changes dynamically and I constantly need to change the game world (hence needing the Difference).  vertsB will always be 100% inside vertsA.  YuPengClipper.Difference gives me the following two shapes.  When used as a path in WP7, sure enough, It looks correct, buts thats a Path and not triangles.   Hmmm, maybe theres a PathGeometry to triangles code out there?  

Shape 1  = " L1,1 L100,1 L100,100 L1,100"
Shape 2 = " L90,11 L11,11 L11,90 L90,90"

 

            var vertsA = new Vertices();
            var vertsB = new Vertices();

            vertsA.Add(new Vector2(1, 1));
            vertsA.Add(new Vector2(100, 1));
            vertsA.Add(new Vector2(100, 100));
            vertsA.Add(new Vector2(1, 100));
            vertsA.Add(new Vector2(1, 1));

            vertsB.Add(new Vector2(11, 11));
            vertsB.Add(new Vector2(90, 11));
            vertsB.Add(new Vector2(90, 90));
            vertsB.Add(new Vector2(11, 90));
            vertsB.Add(new Vector2(11, 11));

Nov 23, 2010 at 7:10 AM

FYI, here is the result of the YuPengClipper.Difference as a Silverlight path...
<Path x:Name="PATHA_SymDiff" Data="M1,1 L100,1 L100,100 L1,100 z   M90,11 L11,11 L11,90 L90,90 z" Fill="#FF1515C2" Margin="0" Stretch="None" Stroke="Black"   UseLayoutRounding="False"/>

And vertsA and vertsB as paths (note the .5 for each point)
<Path x:Name="PathA" Data="M0.5,0.5 L99.5,0.5 L99.5,99.5 L0.5,99.5 z" Fill="#FF3CE41A" Height="100" Stretch="Fill" Stroke="Black" Width="100" d:IsHidden="True"/>
<Path x:Name="PathB" Data="M0.5,0.5 L79.5,0.5 L79.5,79.5 L0.5,79.5 z" Fill="#FFE4481A" Height="80" Canvas.Left="8" Stretch="Fill" Stroke="Black" Canvas.Top="8" Width="80" d:IsHidden="True" />

You can clearly see how these three paths match up to what I'm trying to achieve in my first post.  Ideally PATHA_SymDiff needs to be triangulated.

 

Nov 23, 2010 at 7:58 AM

A bit more work on this, I think I got it (yet with questionable reliability).  The problem is BayazitDecomposer.ConvexPartition doesn't officially support holes according to the documentation, but, it does work in this case. I'm open to hearing of a reliable alternative.

//two shapes, box B within box A
            var vertsA = new Vertices();
            var vertsB = new Vertices();
            vertsA.Add(new Vector2(1, 1));
            vertsA.Add(new Vector2(100, 1));
            vertsA.Add(new Vector2(100, 100));
            vertsA.Add(new Vector2(1, 100));
            vertsA.Add(new Vector2(1, 1));
            vertsB.Add(new Vector2(11, 11));
            vertsB.Add(new Vector2(90, 11));
            vertsB.Add(new Vector2(90, 90));
            vertsB.Add(new Vector2(11, 90));
            vertsB.Add(new Vector2(11, 11));

//combine the two shapes, make sure to add second shape in opposite order so it appears as a hole for BayazitDecomposer
            Vertices verts = new Vertices();
            foreach (Vector2 v in vertsA)
                verts .Add(v);
            for (int x = vertsB.Count - 1; x >= 0; x--)
                verts .Add(vertsB[x]);
            var result = BayazitDecomposer.ConvexPartition(verts);

//var result contains 4 list's of verticies, each of these is a 4 sided poly representing the difference of A and B.... (that is vertsB subtracted from vertsA

Developer
Nov 23, 2010 at 1:48 PM

Hey there,

as you probably already figured out, the clipper returns "solid" geometry in counterclockwise order while holes are returned as vertices in clockwise order. For triangulation you could use some external library. I think there exist a c# port of Poly2Tri, but i dont know if it supports holes. Under c++ i achieved excellent results with Triangle (http://cs.cmu.edu/~quake/triangle.html), that would however require some work to incorporate into c#.

Have you thought about using edges or loopshapes for your geometry? That might eliminate your problem to triangulate all together :)

HTH at least a bit...

Best regards

Helge

Coordinator
Nov 23, 2010 at 4:01 PM

@Elsch:

I've already incorporated the CDT algorithm from Poly2Tri (The C# port) into FPE 3.2. It does support holes and I'm thinking about if I should keep support for seiner points or not.

I've also done 95% of the work on porting the Seidel algorithm from Poly2Tri (from Scala and Python) to C#, but there is a bug somewhere I can't seem to find. If someone here knows Scala or Python and would like to help me out a bit, you are welcome to contact me.

As for Triangle, it is a great library and I would really like to have it in C# as I think it is one of the most robust triangulation libraries out there.

Nov 23, 2010 at 4:53 PM
Edited Nov 23, 2010 at 5:34 PM

@Elsch, I just tried Edges and a Loopshape, didn't see those in there at first.  Loopshape does exactly what I need and will integrate the quickest into what I already have.  This is fantastic.

@Genbox, great, I just tried out CDT, you guys rock! :)

Developer
Nov 23, 2010 at 6:34 PM

@Genbox

I started porting Triangle to C# as i think the kind of triangulation it provides is perfect for breakable bodies and stuff like that ...and i wanted to build a worms like game with destructable environments. I pretty much gave up on that with the release of Worms Reloaded and the realization that Worms in my memories was somehow funnier than it actually is *MEH*

Afterwards i stalled all the work on my Triangle port, as i have no clue if it could be integrated into Farseer due to licensing issues. Maybe i'll have a look at it over the holidays if i find the time.

Coordinator
Nov 23, 2010 at 8:17 PM

@Elsch:

Sounds great! I think the breakable bodies in FPE can be improved a lot, but it requires some good triangulation algorithms and a mesh generator. I'm thinking of something like this, but with different joints (weld joint, distance joint) and even without joints. A check for force could be done to each of the fixtures and if it is over a userdefined limit, it will break off.

Be sure to let me know of your progress Elsch. If you need anything, such as a source source control, I can add you to ours.