Farseer Physics Engine 3.0 Update (July)

Coordinator
Jul 31, 2010 at 4:52 PM

Time for a much needed update.

It has been some time since the last update. I apologize for that, but I have had some serious financial problems lately. Currently hijacking some wireless internet from McDonald, I'm able to write this update. :)

Farseer Physics Engine 3.0 came a long way and was almost finished when I discovered a bug somewhere in the engine that caused the simulation to be different from that of Box2D. I tried reverting to earlier versions of the engine to find the bug, but it seemed that it has been present for a long time. After weeks of deep code inspection without finding anything but unrelated bugs, I reverted the whole codebase back to that of Box2D.XNA.

So far everything is running fine again. We have a couple of bugs related to the Path Factory and Controllers, but everything else should work fine. I will make some small changes to the engine in the next couple of days and remove everything that does not work 100%. Then I will see about the release of version 3.0. It is about time we get the engine out the door and into the community.

Thanks to all of you who have helped out with contributions and bug reporting. Keep up the good job and hopefully we will have 3.0 out the door soon.

Jul 31, 2010 at 10:22 PM

Great work man, keep it up :)

Aug 1, 2010 at 1:38 PM

All the progress sounds great!

Has anyone looked into seeing if this will work just as well with XnaTouch on iPhone?

My initial tests with version 2.x were quite promising, so hopefully 3.0 will be just as good.

Keep up the great work!

Aug 1, 2010 at 8:19 PM

Good luck, man! FarseerPhysics is hope of indy game development :)

Aug 2, 2010 at 4:51 PM
Edited Aug 2, 2010 at 4:55 PM

Good to hear news about the engine, but not so good about your financial probles, I wish there would be something that could help you out (anyway this should motivate us, the users to make a donation, even if it proably isn't a definitive solution, but still to show support).

Anyway, a small question, are you planning to reintroduce the OnCollision event to the fixtures? (just to know if I should move some code to the presolve method) Plus, now the shape constructor for the fixtures don't use a density, this means that I should assign the mass manually?

Thanks again

Coordinator
Aug 3, 2010 at 4:58 PM
Edited Aug 3, 2010 at 5:04 PM
I still need to implement a few changes such as the OnCollision and OnSeparation delegates. As for the density, you supply it to the Body.CreateFixture() method and everything should be calculated as before. I'm not sure if I will move the density back to the Shape constructor again. It seemed more logical to me, but I would like Erin to change it in Box2D first. (created a bug report with the change) Donations are always welcome. If the project is used in a commercial game, it would be great if the developers showed their support to the project by donating small amount. Anyone can show their support by donating, but commercial games get some out of it financially and thus should be more inclined to donate :)
Aug 3, 2010 at 8:21 PM

Thanks for the update Genbox. I'll wait for the delegates before update the engine to the latest build. Also I noticed some changes in the fixture lists (now it seems to be a linked list instead of a "regular" list), and the world.remove method has been replaced by a world.destroyjoint/body/controller method, am I right?

And if I finally finish my (commercial) game, you can bet that something will go to the engine fundings (besides an occasional donation, of course) :)

Aug 5, 2010 at 4:27 PM

Great update! Thanks.

Just another question about it, though. There doesn't seem to be a way to get the vertices for a fixture shape anymore. I was using that for debugging and other things. (i.e. Fixture.Shape.GetVertices is now missing)

Thanks again!

Coordinator
Aug 6, 2010 at 1:29 PM
Edited Aug 6, 2010 at 1:36 PM

@Pnikosis: I will update the delegates today when the TFS is up again.

@Mindcrime: I used that for the fluid drag controller because it gave an approximation of circles. You can still get the vertices of a shape by casting it to an polygon shape first.

Coordinator
Aug 6, 2010 at 9:50 PM

Phew, it was a hassle to get Team Explorer 2008 to work with the new upgraded Codeplex server (They now have TFS 2010).

@Pnikosis: I've updated the build with the OnCollision and OnSeparation delegates. If there are anything else, let me know. And to answer your question: Yes, there is a AddBody, RemoveBody, AddJoint, RemoveJoint method now. Can't simply call them Add() and Remove() anymore because AddBody() takes no argument (Body is not truly decoupled from the engine like it was in 2.x)

Coordinator
Aug 6, 2010 at 9:59 PM

Update:

I still need to get the final touches in place and there is a huge amount of documentation that needs to be done (in code).

I have 2 guys on different tasks now:

Colton is working on the boolean tools and the associated test
Robert is working on the consistency of the joints. (local anchors versus world anchors)

Once the engine itself is in place, I need to reattach the samples framework that Matthew created and get started on the individual samples.

Coordinator
Aug 7, 2010 at 1:17 AM

Update:

Been up all night doing the last refactorings, comment improvements and I also got to implement a small set of features. Here is a list of what needs to be done:

- JointFactory needs to be created
- Boolean tools needs to be fixed
- Performance enhancements to large datastructures (I need a paid Xbox Live account to performance test on Xbox360. Can I borrow someones account for this?)
- SimpleSamples and DemoBaseXNA needs to be finished
- Debugview for WPF?
- WPF samples?
- Hello world application
- Documentation on how to use the FPE 3.0 tools
- List with description of new features in FPE 3.0

When those items are finished, the engine will be released.

Aug 9, 2010 at 3:48 AM

genbox sent you a msg about xna creators club membership

Developer
Aug 9, 2010 at 7:37 PM
Edited Aug 9, 2010 at 9:58 PM

Hi genbox,

I probably should start a new thread for this, but most of this is related to the Boolean tools. I have been working on my own Boolean tools, since the current implementation seems to be quite broken.

While working on the Boolean tools I found a bug in "LineTools.cs". Within the method "LineIntersect" on line 215 the check for coincidence has to be "if (ua != 0f || ub != 0f)" instead of "if (ua != 0f && ub != 0f)". The line (segments) are only coincident if _both_ numerators are 0. Otherwise you miss intersections were one line (segments) goes through the starting point of the other line (segment).

Regarding the Boolean tools:

First I tried to implement the Greiner Hormann algorithm (http://portal.acm.org/citation.cfm?id=274364), but I couldn't get it to perform well with degenerate cases (where polygon edges are coincident). "An Extension of Polygon Clipping To Resolve Degenerate Cases" describes how these issues can be fixed, but I pretty much gave up on that as the description (for me at least) was very vague.

Instead I started over and implemented "A new algorithm for Boolean operations on general polygons" available here: http://liama.ia.ac.cn/wiki/_media/user:dong:dong_cg_05.pdf

I have it up and running and it handles intersections between general polygons (concave and convex) without self-intersections. Coincident edges and intersection at polygon vertices are no problem and if an operation produces holes it can cope with that as well. So far holes are just dropped, since there is no reasonable representation for holes in Farseer yet and in my opinion it doesn't make much sense to change that. Im thinking about building some postprocessing routine though, which cuts a polygon in two pieces at a hole, so that the resulting two polygons represent the contour of one polygon with a hole. My solution still has minor bugs with duplicated edges for the "union" and "difference" operations, but hopefully I can fix that within the next few days. So I have no idea what the status of your Boolean tools is right now, but maybe you would like to have a look at my solution. It certainly still needs some serious testing and is not yet very optimized. But im also working on an extensive testbed test and a sweepline solution for speeding up the process of searching for intersections points between two polygons.

Im not sure, what the best method of providing my code to you guys would be though :/

Sry for my confused english... not a native speaker ;)

Coordinator
Aug 9, 2010 at 10:13 PM
Edited Aug 10, 2010 at 12:27 PM

Hi Elsch, First of all, nice job on hunting down the bugs. I'll create a bug report and get it fixed as soon as possible. I'm not really informed on the different algorithms in the field of boolean tools, so I trust you did your homework and found a solution that would work for most of our users.

The current solution is broken, but I have the original contributer DrDeth looking at it at the moment and if he comes up with a fix, I would like to keep the current implementation in the engine. That being said, I can't see a reason to not include your implementation too. I would be happy to take a look at your implementation together with the testbed.

The best way of contributing is to either send me an email with the code or upload an patch under the Source Control tab here on Codeplex. If you change some of the FPE classes, I would prefer a patch that contains the changes. If you use your own classes or only have minimal changes to the existing classes, you can also send the whole solution to me and I'll make sure to transfer over the changes. Make sure to document your implementation to tell both me and our users how you are supposed to use the library (edge cases, results can contain holes and so on).

Coordinator
Aug 10, 2010 at 1:09 PM

Update:

Thanks to Zach Aller I now have an Xbox Live account to develop on. Thanks a lot Zach!

I wrote an email to Red-Gate asking them to support our project. They have replied back that they would like to donate a free ANTS Performance Profiler licence. That is terrific news and I hope it will come in handy when I'm optimizing the engine.

 

Aug 10, 2010 at 1:22 PM

Wow nice. ANTS is expensive :)

 

Even my job wouldn't dish out the money for it, heh.

Coordinator
Aug 10, 2010 at 3:36 PM

Indeed. It is very nice of them to support our project.

Developer
Aug 10, 2010 at 4:30 PM
Edited Aug 10, 2010 at 4:35 PM

Hey everybody,

I just uploaded a patch with alternative Boolean tools. I also added a testbed test. As long as the supplied polygons are simple it should work fine. There is still a minor bug, which returns polygons with two points in some cases. Currently looking into that, but as a workaround those polygons can be easily filtered out of the returned result. I would appreciate any feedback on bugs.

The test should hopefully be pretty much self-explanatory :) Except for a little bug fix within the LineTools, the rest of the code is unchanged. The fix needs to be applied however, for the Boolean tools to work properly.

While being at it I noticed that PolygonTools.CreateGear() creates self-intersections within the output, which are not detected by Vertices.IsSimple(). PolygonTools.CreateGear() creates twice the amount of points needed with many colinear edges, if Im not missing something. Have not yet looked into it though.

Aug 10, 2010 at 7:13 PM

Hey all...new to Farseer and new to these forums, but very interested in the engine.

I was wondering if there is a list of features planned for the 3.0 release?  I'm not sure what the differences are between 2.1.3 (which I have currently) and the 3.0 version.  I'm about to begin integrating the engine with Torque X 2D, and I'm not sure if I should begin the implementation with 2.1.3 or if 3.0 will feature appreciable enhancements and perhaps I'd be better off just waiting for it to be released.

Will the update mainly be bug fixes and performance enhancements, or will there be changes to the use paradigms and/or new features?

Thanks

Ron

Coordinator
Aug 10, 2010 at 9:08 PM
I will put up a list of differences when 3.0 is finished. The current version of the engine in the source control is stable. The API should not change from now on, so it is safe to implement.
Developer
Aug 11, 2010 at 11:55 PM

Okay i found the issues with Vertices.IsSimple() and PolygonTools.CreateGear().

Vertices.IsSimple() detects self-intersections, but not if two points are at the same position. Thus polygon edges with a length of zero are not covered by the test. I think that should qualify as a self-intersection too.

The problem with PolygonTools.CreateGear() arises when the tipPercentage is zero and many duplicated points are inserted into the polygon. Also i noticed that CreateGear() is used with values from 0-100 for tipPercentage within the testbed. It actually expects that value to be between 0 and 1. I uploaded a patch which fixes the duplicate points issue and expects the tipPercentage to be between 0 and 100. Also I modified CreateCirle(), CreateEllipse() and CreateGear() so that the polygons returned are in counterclockwise order, as the engine expects that anyway if I understand it correctly.

Another thing which is not really a bug but pretty inconsistent: CreateCapsule() and CreateRoundedRectangle() decompose the returned polygons into convex shapes. Should this not be done by the programmer if needed or at least happen somewhere during fixture creation instead of within the polygon creation function?

Another bug i noticed is within the SimplifyTools. Within the ReduceByDistance() method on line 289 it has to be: "distance *= distance" instead of "distance *= 2" as this value is later checked against Vector2.LengthSquared().

And last but not least I uploaded a new version of my polygonClipper. It is now robust regarding floating point rounding errors and has proper error handling. So it does not freeze the whole application anymore, when an error occurs. Also tweaked the testbed test a bit. It now uses a PointInPolygon test for accurately selecting the polygons instead of the approximation via the polygons bounding box. As far as im concerned the Clipper is working and somewhat final, until anyone finds a bug in it. It has now been tested quite extensivly and so far performs well without any (unhandled) errors.

Maybe it would be worthwhile to add the PointInPolygon test to the other Common routines. The implemenation is robust, exact, and only relies on multiplications and additions. So it is pretty fast.

Coordinator
Aug 12, 2010 at 3:30 PM

Excellent job Elsch!

I'll implement the changes later today. Thanks a lot for finding the bugs and fixing them. Does the PointInPolygon test work on concave and convex polygons? TestPoint inside PolygonShape is also a point in polygon test, but it works on convex polygons only.

Coordinator
Aug 12, 2010 at 4:20 PM

I have applied the changes in your patches and the boolean tools looks great. I also answered my question about concave versus convex polygons. I will include the PointInPolygon routine in the engine for others to use.

Thanks a lot Elsch. Can I include your name in the source as the contributor?

Coordinator
Aug 12, 2010 at 6:19 PM

Now I have also implemented the changes you mentioned in your previous post. Could you download the latest changeset (75414) and verify the changes?

Developer
Aug 13, 2010 at 1:37 PM
Edited Aug 13, 2010 at 1:38 PM

Wow you're fast...

Looks great! .. I guess :)

At least I couldn't get the clipper and polygon creation tools to produce any errors during testing and the rest seems fine as well.

Coordinator
Aug 13, 2010 at 2:40 PM
Update:

I've changed the engine (back) to using Lists<> instead of linked and doubly linked lists. This should make it a lot easier to work with the lists.
Another change is that I've swiched the PolygonShape (back) to using a Vertices list instead of Vector2 arrays. This way you no longer need to supply the number of vertices in your array.
If you are using the factories, nothing should change. But if you manually create shapes and traverse the world lists, then you need to change your code to reflect the changes.
Coordinator
Aug 16, 2010 at 10:58 PM

Update:

I've added the AngleJoint provided by Jeff Weber to the engine. Demo4 and Demo5 in SimpleSamples have been ported (written from scratch actually). I've also extended the FixtureFactory with overloads to CreateCircle() and CreateRectangle() so that you can give it an existing body. It will attach the fixture created to the supplied body.

I'm using the DebugViewXNA class to visualize the stuff in SimpleSamples. The purpose of the samples is to demonstrate the different features of the engine, and not to provide an extensive drawing framework. This makes the samples a little dull, I will try to figure out how we can make the samples a little more crisp, but for now, the engine itself comes first.

Coordinator
Aug 19, 2010 at 11:58 PM

Update:

We have done some good progress lately as seen here:

- JointFactory needs to be created - Done
- Boolean tools needs to be fixed
- Performance enhancements to large datastructures - Done
- SimpleSamples and DemoBaseXNA needs to be finished - Done
- Debugview for WPF?
- WPF samples?
- Hello world application - Done
- Documentation on how to use the FPE 3.0 tools
- List with description of new features in FPE 3.0 - In progress

There are also some new stuff in the engine:

- AngleJoint, FixedAngleJoint
- SliderJoint
- A new algorithm for boolean operations

We are very close to a release now. If you find any bugs, let us know by creating an issue in our issue tracker.

Coordinator
Aug 20, 2010 at 1:36 AM

I've just completed the following:

- List with description of new features in FPE 3.0 - Done

You can find it under the Documentation tab. Let me know if I forgot something.

I'm also removing the following from the list:

- Debugview for WPF?
- WPF samples?

They are low priority and will have to wait to the next update. That means only two things are left:

- Documentation on how to use the FPE 3.0 tools
- Boolean tools needs to be fixed

I'll have a look at the boolean tools in the next couple of days and I think I have a new guy that takes care of the tool documentation.

Coordinator
Aug 20, 2010 at 9:43 PM

Update:

Colton have updated the Ragdoll to have a better initial stage and I have updated the SimpleSamples to support commands from the Xbox360 controller. I've also done a general cleanup of the engine and some small performance improvements. I've also removed the TraceClipper since I don't have the time to take a look at it.

I thought it would be a good idea to see just how much we were getting out of the performance improvements, so I have put up a wiki page here where you can see just how much better performance FPE 3.0 has compared to Box2D.XNA. The tests are done in our own and their own test framework respectively. That makes the results unreliable, but I'm working on a more consistent tests that should give us a better idea of the performance of the two engines.

Aug 25, 2010 at 5:59 AM

Just a mention for anyone interested in decomposing shapes with holes, or handling holes with the BooleanTools:

http://github.com/MaulingMonkey/poly2tri-cs

Poly2Tri is a triangulation library, and it handles holes. I use it together with EarclipDecomposer.PolygonizeTriangles, and I get really good results.

It's a C# port of this C++ library, and I dont know if it will work on the XBOX.