Problems with polygon subtraction

Topics: Developer Forum, User Forum
Oct 21, 2009 at 4:50 PM

I love how Farseer has an inbuilt texture-to-polygon function and polygon subtraction and union, and have had some success in using these to make a Worms/Lemmings-style deformable-scenery system (after a lot of fiddling)

In my current test-setup, I have one static background body with multiple pieces of geometry attached to it, and a button-press generates a subtractive circle around the player-controlled spaceship.

 

The subtraction works up to a point, but could do with providing two extra functions - providing for full-geometry subtraction, and outputting multiple polygons when a subtraction splits a geometry.

I think these should be fixed in Farseer, but I've not been coding in C# long enough to do a decent job and contribute a fix myself :(

 

At the moment, if the subtractee geom is within the subtracted geom (ie. a small piece of background geom completely enclosed by an explosion) there doesn't appear to be any way of knowing; the output is null, and the error is "NoIntersections", as none of the edges are intersecting.  I can't find an inbuilt function for finding geometry that overlaps in this way, so I guess I'll have to do a distance-test on all the subtractee's verts for now.

This ought to provide an empty vert-list instead of just Null.

 

If the middle of a long piece geometry is subtracted, only one side of the long geometry is retained, as only one vert-list is provided.  I think the subtraction-function (or a new extended more-functional one) is required that will output a list of vert-lists instead just a vert-list.

 

Can anyone think of a simple way to achieve these things with what's currently in the engine?  I don't want to look too complainy if I've missed something obvious ;)

Coordinator
Oct 21, 2009 at 7:07 PM

The polygon manipulation code together with the texture-to-polygon code was both user contributions. I'm in no position of maintaining them since I have no experience with the algorithms and implementations used.

Farseer support both convex and concave polygons and thus the problem of cutting a polygon becomes a little harder. Most cutting algorithms works on convex polygons only and thus you will have to reduce your concave polygons into two or more convex polygons and run the algorithm. Most simple cutting algorithms are also very inefficient on large geometries.

Anyway, I've seen an implementation in C++ written for Box2D that should be easy to translate to C#: http://box2d.org/forum/viewtopic.php?f=3&t=1473

It works great on convex polygons with low point count.

Dec 12, 2009 at 9:53 AM

Your problem about "full-geometry subtraction" should be easily changeable in the Farseer code if you want to change it yourself to return an empty list of vertices. You want to look at Vertices.cs:1678

case PolyUnionError.Poly1InsidePoly2:
                        return null;

Simply change that "return null" into "return new Vertices();"

Although I do agree (philosophically) about returning an empty set of vertices, I think it makes sense performance-wise to just return null. My reasoning is that if you are going to substract polygons in your game, you probably first already checked for collisions. Given that you know the polygons collided, if Subtract returns null, then you know one polygon is completely enclosed by the other.

About your second problem, have you thought/coded a solution? I'd be interested in an implementation of the Subtract function that returns a 2 polygons (after they have been "split" by the subtraction).