This project has moved and is read-only. For the latest updates, please go here.

Union Error

Topics: Developer Forum, Project Management Forum, User Forum
Dec 22, 2009 at 4:40 AM

Hi, all I'm trying to do is loop through the GeomList and do a union on all geoms with a certain tag type: tile.


here's an example of some vertices going in



{X:-301.5 Y:-81} {X:-301.5 Y:-61} {X:-301.5 Y:-41} {X:-301.5 Y:-21} {X:-301.5 Y:-1} {X:-251.25 Y:-1} {X:-201 Y:-1} {X:-150.75 Y:-1} {X:-100.5 Y:-1} {X:-100.5 Y:-21} {X:-100.5 Y:-41} {X:-100.5 Y:-61} {X:-100.5 Y:-81} {X:-150.75 Y:-81} {X:-201 Y:-81} {X:-251.25 Y:-81}
{X:-301.5 Y:-122} {X:-301.5 Y:-102} {X:-301.5 Y:-82} {X:-301.5 Y:-62} {X:-301.5 Y:-42} {X:-251.25 Y:-42} {X:-201 Y:-42} {X:-150.75 Y:-42} {X:-100.5 Y:-42} {X:-100.5 Y:-62} {X:-100.5 Y:-82} {X:-100.5 Y:-102} {X:-100.5 Y:-122} {X:-150.75 Y:-122} {X:-201 Y:-122} {X:-251.25 Y:-122}se


{X:-301.5 Y:-81} {X:-301.5 Y:-61} {X:-301.5 Y:-41} {X:-301.5 Y:-21} {X:-301.5 Y:-1} {X:-251.25 Y:-1} {X:-201 Y:-1} {X:-150.75 Y:-1} {X:-100.5 Y:-1} {X:-100.5 Y:-21} {X:-100.5 Y:-41} {X:-100.5 Y:-61} {X:-100.5 Y:-81} {X:-150.75 Y:-81} {X:-201 Y:-81} {X:-251.25 Y:-81}



{X:-301.5 Y:-122} {X:-301.5 Y:-102} {X:-301.5 Y:-82} {X:-301.5 Y:-62} {X:-301.5 Y:-42} {X:-251.25 Y:-42} {X:-201 Y:-42} {X:-150.75 Y:-42} {X:-100.5 Y:-42} {X:-100.5 Y:-62} {X:-100.5 Y:-82} {X:-100.5 Y:-102} {X:-100.5 Y:-122} {X:-150.75 Y:-122} {X:-201 Y:-122} {X:-251.25 Y:-122}



why is it 


 Vertices union = Vertices.Union(poly1, poly2, out error);

Vertices union2 = Vertices.Union(poly2, poly1, out error);



give me to different sets of vertices?


union gives me 34 vertices

union2 gives me 17 vertices...




here is my method







      for (int i = 0; i < Farseer.Instance.GeomList.Count; i++)


                for (int j = 0; j < Farseer.Instance.GeomList.Count; j++)


                    Geom geomOne = Farseer.Instance.GeomList[i];

                    Geom geomTwo = Farseer.Instance.GeomList[j];

                    if (geomOne != geomTwo && 

                        geomOne != null &&

                        geomTwo !=null &&

                        geomTwo.Body.Tag.GetType() == typeof (Tile)

                        && geomOne.Body.Tag.GetType() == typeof(Tile)

                        && geomOne.CollisionCategories == geomTwo.CollisionCategories)


                        if (AABB.Intersect(ref geomOne.AABB, ref geomTwo.AABB))


                            Tile tile = (Tile) geomOne.Body.Tag;

                            Vertices poly1 = new Vertices(geomOne.WorldVertices);

                            int currentlayer = tile.CurrentLayer;

                            // Get the world coordinates for the right Geometry

                            Vertices poly2 = new Vertices(geomTwo.WorldVertices);


                            // Do the union

                            PolyUnionError error;

                            Vertices union = Vertices.Union(poly1, poly2, out error);

                            Vertices union2 = Vertices.Union(poly2, poly1, out error);


//                                union = Vertices.Simplify(union);















                            geomTwo = null;

                            geomOne = null;



                            Body body = BodyFactory.Instance.CreatePolygonBody(Farseer.Instance, union, 1);

                            body.IsStatic = true;

                            body.Tag = tile;


                            tile.Geom = GeomFactory.Instance.CreatePolygonGeom(Farseer.Instance, body, union, 0);


                            tile.CurrentLayer = currentlayer;


                            i = 0;

                            j = -1;











Dec 28, 2009 at 5:01 AM

No one can clarify  this bug for me?

Dec 28, 2009 at 6:15 PM

The polygon modification functionalities was a contribution to Farseer Physics and I have a hard time fixing bugs and the like in implementations outside of the Farseer Physics core. I'm not sure how the union algorithm works, but it seems weird to me that the order of the polygons give different results. Maybe that is just a part of the algorithm.

If you get a good result, I'd say that it is not a bug, but just the way the algorithm works.

By the way: You should combine the vertices before making them geometries. If it is a level editor or something like that, work on vertice lists instead of geometries. Then you combine the vertices using the union method and then create a geometry out of it. This gives a lot better performance since the overhead of creating the geometry (for each tile) is skipped.

Dec 28, 2009 at 7:34 PM

The map maker creates tiles which need to have their geoms so that objects also created will land on them correctly.


when the maps are PLAYED all their geoms need to be merged, I merge the vertices of all geoms using the union method and like I said I'm getting different results based on the order.



Thanks a lot for replying it's really worrying when i get no response!


Do you know who would be able to help me with this?


Who contributed this? Is there an e-mail?

Dec 28, 2009 at 7:45 PM

DrDeth was the one who kindly contributed the union code. You can find him on Codeplex under that name.

Jan 19, 2010 at 9:58 AM

Hi guys.

Sorry I havent been around in a while. I moved on to other things, so my knowledge about the union code is a little sketchy, but I'll try to help if I can.

The basic premise is rather simple. The code finds a vertex on poly1 that is not inside poly2. Using this point as the starting point, the code 'traces' around the polygon. When an intersection is reached, the tracer switches polygons. Repeat, until the starting vertex is reached. You can replicate this process with a piece of paper and a pencil.

There are situations where this approach wont work, however. Logically, if there are an uneven amount of intersection points (though I'm not sure this could ever happen?), the starting vertex may never be reached and the result will be strange. I assume this is what is happening in this instance where you recieve different vertices back - You can check the PolyUnionError value in this case to see if its found an InfiniteLoop. In this case I still return the 'union' for debug purposes so you can sort of see whats going wrong (now that you know how its meant to work).

I wouldn't rule out the possibility that not all situations have been catered for with the union code. I'd add the source to your project and step through the union code to see where it's going wrong.

Hope this helps.



Jan 19, 2010 at 11:05 AM

Hi DrDeth,

I actually have a question for you; the rounding you have from float to int, is that to prevent floating point inaccuracies and how would that affect the solution? Now that we have meters as the simulation unit instead of pixels, the range of units can be 0-30 and there is a big different between 1.5 and 2.