Polygon Operations - Feedback / Progress

Topics: Developer Forum, User Forum
Oct 27, 2008 at 8:59 AM
Edited Dec 8, 2008 at 3:59 PM
I've begun work on the Polygon functions for inclusion in a later release of FarSeer Physics. To avoid uneccesary bloat, I am implementing this functionality as extension methods to the Vertices classes.I've created a test application to visualise the polygons and test operations.

Current extensions:
  • Vertices.Offset
  • Vertices.Union
  • Vertices.Subtract
  • Vertices.Intersect
  • Vertices.Simplify
You can find the latest code and test project here: Download v1.2

Q,W, E = Create Circles
A, S, D = Create Rectangles
Left-Mouse  = Drag
Space = Union
Enter = Intersect
Backspace = Subtract
Tab = Simplify
Escape = Exit

Oct 28, 2008 at 3:22 PM
One of the major problems I have found with the code is that it is returning far more intersections than it should, but these are merely duplications of the intersection points. The reason for this (i think) is because the EdgeIntersection method is doing line intersections, as opposed to line segment intersections. So, every edge in a straight line (which occurs a lot with rectangles cut into segments by the collision grid) returns the same intersect point (as long as at least one of those segments does in fact intersect).

So, I'm off to find a line segment algorithm - any suggestions?

I've been looking through the Vertices, Geom and Grid classes, but I'm not sure that the engine itself even does/needs to do edge intersections to determine collisions.
Oct 28, 2008 at 5:55 PM
Good work DrDeth, keep it up.

Have a look inside the CollisionHelper class, there are some line intersection stuff that might be of use. I'm not too sure though.

Have you contacted the original poster of the code? Stuff such as the timeout in the ToArray() method seems a little odd to me. It also seems it tries to emulate the behavior of a linked list (the LList and VNode stuff) but there might be a reason for it, have not looked into it in details.
Oct 29, 2008 at 9:09 AM
Thanks genbox! The CollisionHelper is a huge help!

The original code does a lot of wierd stuff that I'm not sure about. Yes, it replicates a linked list, probably because the .NET linked list classes dont allow you to modify the nodes directly - or more accurately, because it was a direct port of some C code.

At this stage I'm leaning towards writing these functions from scratch, now that I have a better understanding of how it works, using more of the existing FarSeer code (such as the CollisionHelper) and not re-inventing the wheel, ie. using existing .NET lists.
Nov 12, 2008 at 8:47 PM
Edited Nov 12, 2008 at 9:59 PM
I've finally found some time to make some progress! We have our first successful polygon unions!!

Out of all of the scenarios I thought up - which you can have a look at here - only one isnt working. I understand why, I just need to think about how to change my code to cater for this situation.

If anyone is interested in testing this out, let me know.
Nov 12, 2008 at 10:31 PM
@DrDeth - I am interested as I am in the process of making a 3D visualizer for Farseer and I want to be able to define a Geometry to an arbitrary 3D model. Sort of like Little Big Planet and Bionic Commando Reloaded. Right now my idea is to project the model in an orthographic method, render it as a solid color then use the Texture to Geom functions to create my Geometry. This is all good and while I haven't tested it yet I'm sure it will work. But it would be nice if I could just project it flat and then combine all the triangles into one polygon. I am also looking to find a way to create real-time geomety in Farseer. I think I will have to replace near phase collision code with somthing like SAT (Separating Axis Threom) so no distance table has to be created.
Nov 13, 2008 at 7:50 AM
Very nice DrDeth.

Great to see that you did some progress. Do you think that you are able to clip out polygons too?

Nice visualizaion by the way.
Nov 13, 2008 at 8:05 AM
@mattbettcher - it should work to combine the triangles, as long as you can work through them making sure that they do touch or overlap. I still have to cater for the above problem, as well as cases where either polygon is inside of the other. I doubt that the union functions, at this stage, would be quick enough to do this on a massive scale in real-time. I'm focusing on getting it working right now, before I get stuck into optomisations.

@genbox - I'm not sure what you mean by 'clip out'. It would definitely be possible to use most of what I've done to do Intersect and Subtract functions too.

The visualisation is just the PhysicsSimulatorView - I cant take credit for that. ;)
Nov 14, 2008 at 11:07 PM
The fix for the last scenario I had was actually quite a small change to get working. I am now happy that polygon unions work for simple polygons. That is, I have created simple rectangles, circles and simple convex polygons, all of which are correctly merged. I just want to tidy up my test application a little bit as an example / demo before I let you guys play with it.

From there, its on to more complex [read: concave] polygons, and performance enhancements.
Nov 14, 2008 at 11:09 PM
@DrDeth: Seems like you are getting the hang of it. Looking forward to see what you have come up with.
Nov 20, 2008 at 11:40 AM
I found a place where I was referencing a 'dirty' original vertices of a polygon instead of the 'cleaned' vertices. This was what was causing problems with more complex polygons, and why I was getting infinite loops (which I check for, just in case). Now that thats fixed, it all looks to be working rather well. So, I've uploaded my code and test application for you to play with.

Q,W and E create 'circles' with a different number of sides (8, 16, and 32).
A creates a square.
S creates a wide rectangle.
D creates a high rectangle.
Use the mouse to drag polygons around and position them.
Space performs the polygon union.

A file 'union-log.txt' will be created/overwritten when the polygon union occurs and will contain the points of the two polygons, as well as the union output polygon.

Please give me some feedback, and obviously any bug reports.
Nov 20, 2008 at 1:32 PM
Very nice work DrDeth. I have noticed if you try to intersect a polygon that's completely inside another polygon it throws a null reference exception on line 296 in Game1.cs. Here's a snippet -

foreach (Vector2 vert in union)

Since no vertitces are found in the union the union is null. After putting a null check around this I found that polygons must intersect to be combined. Anyway best of luck. It's looking really good so far.
Nov 20, 2008 at 5:45 PM
Same thing happens when the polygons are not touching each other. I guess it's fixed the same way :)

@DrDeth: I'm very impressed with the functionality. I did manage to get create such a polygon that it exploded and warned me that an infinite loop was detected :)
I can see that you have worked a lot on the implementation - good job. If you manage to get a "cutting"/substraction method too, it would be great! I'll write this down for Farseer Physics 2.1, I'm sure a lot of people could use something like this.
Nov 25, 2008 at 1:32 PM
As you've said, but for other peoples benefit, the null reference is easily fixed by enclosing the foreach with an if statement to check if the union is null.
Like so:

            if (union != null)
                foreach (Vector2 vert in union)

I dont think Farseer supports polygons with 'disconnected' vertices, so naturally they would need to overlap / intersect in order to union them.

Do you think the function should behave differently? Should it return one or the other polygon?

Your polygon exploded? Thats cool! ;-)
If you still have it, could you send me the debug log file of that ?

Subtractions shouldn't be too hard using the existing code. I just need to make the inner loop work in reverse and invert the swap check when polygons intersect.

Nov 25, 2008 at 1:59 PM
@DrDeth: Hehe. Yeah, It blew up.

I don't have the logfile, I'll see if I can recreate it.
Would be greate to have substraction. Give it a try and see what you can work out.
Dec 5, 2008 at 3:16 PM
Polygon subtraction is in! I definitely need to give this code a lot more testing, and throw it at a lot of complex polygons but its in a working state at the moment.

The download link is up top...
Dec 5, 2008 at 3:23 PM
Great DrDeth! You are doing a good job. I will try and see if I can get some time this weekend to test it. Thanks.
Dec 5, 2008 at 7:24 PM
Could not wait... Simply had to test it :)

It's great. It works great.
Some notes:

1. Seems like you have some different solutions in your code. Solution 3 seems to not be used. What is the status on this?

2. When I joint or subtract 2 polygons just right, I can create a lot of redundant polygons.
case 1: Create a rectangle inside another (same height, but smaller width) and add them. This creates some redundant polygons to the original rectangle. (the new polygons have no use)
case 2. Add a lot of rectangles and circles together and you end up with a lot of redundant polygons.

A simple solution is to make a reduce function that removes the redundant polygons after a addition or subtraction. This should be disabled by default.
This function should also preserve the original polygons. Example:

You have a rectangle with 16 polygons (one each corner and 3 on each side) and you add another rectangle inside it (same height, smaller width) and add them. This would create a rectangle with 22 polygons (3 polygons added to top and bottom). The reduce function should see that the top and bottom now have 3 polygons too much and remove them.

This is not a requirement, just something handy. :)
Anyway, Thanks for all your hard work DrDeth. Seems like we are getting this kind of functionality after all.
Dec 8, 2008 at 8:03 AM
@genbox: By polygons, I assume you mean vertices?

1. The two different 'in polygon' functions work for different situations. I was trying out a few and settled on the current one being used, as it works in all the situations I need it to. I will do a cleanup soon and remove unused code.

2. Yes, that has been on my mind a lot lately. I need to do some research on simplifying polygons and put that in. For starters, I am thinking that I can do a simple 'is on line' check to remove all unecessary vertices that occur on a straight line and just keep the end-points. You could then run the simplified polygon though the SubDivideEdges routine if you wanted more complexity again.
I already remove duplicate vertices during the operations.

As an afterthought - I implemented Intersect too. You can now get the area where polygons intersect.

Dec 16, 2008 at 1:55 PM
Edited Dec 16, 2008 at 1:57 PM
Seems I forgot to post a reply when I updated my original post!

New version 1.2 has polygon simplification it it. You can set a 'threshold' for vertices distance too, which will combine vertices within this threshold. To be honest though, there was a reason why polygons created with the factories have 'extra' vertices in them - it helps with the collision detection (IIRC).

@genbox: What more do you need me to do to include this in Farseer 2.1 as an extra?

Dec 16, 2008 at 5:26 PM
Good work DrDeth. Great that you are so outgoing and helpful!

I will have a look at the new 1.2 version. As for the simplification, it might not be necessary, but it's good to have. Powerful vertices manipulation tools equals more flexible games :)
Dec 16, 2008 at 6:19 PM
It's great fun to play with :) The simplification is a little tricky though.

I created a lot of "e" circles in a cloud shape and pressed tab. The results are unusable :)
Anyway, keep the functionality and we will have a look at it when 2.1 is coming up.

Oh, forgot yo answer your question:
You have done a lot already. It's great to have people contributing like you. If it's okay with you, I will contact you near 2.1 planning and have a small chat about the functionality, documentation and the like.