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

Polygon operations

Topics: Developer Forum, User Forum
Sep 20, 2009 at 3:07 AM

Hi again,

I am having abit of trouble with beforementioned Centroids when performing a union, subtraction or intersection of arbitrary polygons. How it can be achieved so that when doing any of those operations the position of the body remains so that, for example, when doing a union of Polygon1 and Polygon2, the resultant polygon vertices are unmodified by the damn centroid? A simple example: Having one rectangle and another and doing a union on them, the vertices of both of them remain where they were before the union - how it can be achieved? Same question for subtraction, where vertices of left operand stay where they were.



Sep 20, 2009 at 8:06 AM

Just a quick idea to put out there (I'm sure there are better ways): say you're doing a union. You could keep track of the world position of a specific vertex (say, the topleftmost vertex) and see how far it shifts from the union. Then you can translate the whole geom by that much (geom.Position -= offset;).

Sep 20, 2009 at 9:51 AM

The problem is that after I perform the union, all original vertices are gone and there is no way of knowing which vertice I was referring to. The idea is nice, though, I will definitely have to give it more thought, thanks!

Sep 20, 2009 at 11:53 AM
Edited Sep 20, 2009 at 11:55 AM

Hi dpr

I am also modifying polygons in my editor. I am doing it the way LittleBigPlanet does it, using shapes like a cookie-cutter or paintbrush.

I am using the GPC Polygon Clipping Library for the clipping though, as the Farseer union/subtract functions sometimes gave me bad results on complicated polygons, like those with holes. The GPC library also does really good triangulation, which I use a lot.

When I last used the Farseer functions I don't think that using Union/Subtract actually centered the vertices, that you had to do it yourself. This was the first 2.1 release, so it might have changed. If it was added later you can probably go into the Vertices class and take that out.

After that you just get the centroid of the new new shape, and then offset the new Body's position by that. (like what Cowdozer said)

I tried to find my old code for you, but I think it's lost. Sorry! :(

I hope I helped a bit anyway.

Sep 20, 2009 at 11:56 AM

My guess is that you draw the textures using the centroid (or body.Position)?

When you union two sets of polygons and create a new set of polygons - the centroid of the polygons will shift to a new location. You can prevent it by resetting the position of the centroid to the old location, but that will reduce the accuracy of the physics engine (Imagine a long iron bar with a centroid to the right of the bar - gravity is applied to the centroid and thus it will fall with the right end first).

A good solution is to save the centroid (the body's position is set to the centroid of the vertices: body.Position = vertices.GetCentroid) and when you union the polygons, simply extract the new centroid and add it to an offset variable. Also, if you call Vertices vertices = new Vertices(oldVertices) you will effectivly clone the old vertices into a new collection.

Sep 20, 2009 at 11:57 AM

Hey how have you being using that GPC Polygon Clipping Library?

Do you have any code you could share that shows how to get it working with farseer?

Sep 20, 2009 at 5:33 PM

robertdodd, thanks for the link. That looks like a very good library!

genbox, will that really work? When performing a union, some of the area which was previously counted twice (because the geoms have to overlap) is now only counted once, so I don't think the resulting centroid is necessarily somewhere along the line of the existing centroids. Maybe I'm just not understanding what you're saying, and maybe we have similar ideas.

dpr, I understand that you lose track of the specific vertices after the union, but that is why I suggested you work with an easy-to-find vertex. If you're only performing a union, the topleftmost vertex of the two geoms before the union will be the "same" vertex of the topleftmost vertex of the resultant geom. So if you take the topleftmost of the result and subtract the topleftmost of the originals, you'll get the offset by which the topleftmost vertex moved.


Sep 20, 2009 at 10:05 PM

@robertdodd: I used the GCP library some time ago and I had a look at it again when we added the clipping functionality to Farseer. My guess is that they still run with the wrapper and no native C# library. For 3.0 I want to have more tools inside the vertices class and I've been thinking on porting over some of the GCP code. I have little experience with advanced clipping algorithms, but that might change while porting the code.

@Cowdozer: The centroid is calculated on the body once you create the body (using CreatePolygonBody()) - having the old centroid (before editing the vertices) as a reference point of drawing, you should be able to offset the new body using the old centroid.

I edited Demo7 in the advanced samples to show how you can create a stationary geometry and edit it without changing its position. (using polygonbrush)

Sep 23, 2009 at 6:03 AM

@danthekiller: It's pretty simple. Download the C# wrapper from their website, and look at the example program. You just have to modify the wrapper to accept "Vector2" instead of "Point". The only difficult thing after that is putting the vertexes in the right order after performing the clipping: It gives you separate polygons for holes and not-holes, and you have to piece them into a single polygon to create a geom. I can give you my code for that though.

@genbox: Correct, you need to use a wrapper for C#. Also, one thing you should note is that it doesn't correctly set the "hole" flags after a clipping operation. I get around this by examining the winding order of the polys it returns, but thats a bit of a hack, and sometimes gives bad results.

Sep 23, 2009 at 6:32 AM

I would love to see the code you have for putting them back into a single polygon to create a geom.
Also how exactly do wrappers work? obveosly the code is still in c++ so does a wrapper just link to the c++ dll underneath?