Farseer Physics Engine 3.3 discussion

Coordinator
Feb 6, 2011 at 12:22 AM

Helge, Matthew, David, Kwame and myself are still developing features for Farseer Physics Engine 3.3. Just to give you some idea of what is happening, I've written a list of things that we are working on:

  • Samples, YuPeng clipper (Helge)
  • Marching squares (Matthew)
  • Texture to vertices (David)
  • Buoyancy (Kwame)
  • Cloning, WP7 performance, serialization (Ian)

If you have any questions regarding any of those features, or have any code that you would like to contribute, let us know.
I would like to start off the discussion with the following question:

What do you say I restructure the whole engine so that FixtureFactory would become BodyFactory, that instead of returning single fixtures, it would return a single body. At the moment, creating a body with multiple fixtures is done like this:

List<Fixture> compund = FixtureFactory.CreateCompoundPolygon(World, BayazitDecomposer.ConvexPartition(verts), 1);
compund[0].Body.BodyType = BodyType.Dynamic;
compund[0].Body.Position = new Vector2(0, 20);

What I propose, is this:

Body compund = BodyFactory.CreateCompound(World, BayazitDecomposer.ConvexPartition(verts), 1);
compund.BodyType = BodyType.Dynamic;
compund.Position = new Vector2(0, 20);

Changing friction, restitution and other fixture based properties would have to be done in a loop like this:

for (int i = 0; i < body.FixtureList.Count; i++)
{
    Fixture fixture = body.FixtureList[0];
    fixture.Restitution = 0.5f;
}

The second part of my proposal, is to move properties like friction and restitution into the body class, and when you change them, it automatically change it on all attached fixtures. Then it would be like this:

body.Friction = 0.2f;

Is that something you would like in FPE 3.3?

Feb 6, 2011 at 2:08 AM

The BodyFactory idea sounds great, but I think that friction and restitution should remain per-fixture.

I think having a method such as Body.SetFriction(float val) is a better idea, as this will prevent the confusion of which value to return if there are multiple different fixtures, and still allow the ease of your original idea.

What do u think?

Coordinator
Feb 6, 2011 at 2:23 AM

I did write move, but what I meant was wrapping. Body.Friction would simply set the friction on all fixtures - you would still be able to set the friction on each fixture as you can now.

Developer
Feb 6, 2011 at 3:08 AM

This is a very good direction for the API to take.

I would like everyone to take a look at my Marching Squares API and Marching Squares Terrain API and let me know if there is any improvements/additions that I can make to make it better.

Developer
Feb 6, 2011 at 5:21 AM

Fairly new to Farseer myself but I have already noticed the usability issue with the list of fixtures. I was thinking something along these lines  (Body.CreateCompound) would make sense.

I have some other thoughts that may be completely off base being only a little familiar with Farseer but I figured I should mention them in case someone finds them useful. They could be terrible suggestions but here they are. Again, please keep in mind I am new to Farseer so please feel free to point out any errors or incorrect assumptions on my part.

 

I'm always interested in keeping live object counts and references to other objects at a minimum in order to minimize the GC's work. I can't help but wonder if the Fixture and related objects could be modified to reduce both of these with minimal impact to the public API's. With fixtures being so widely used in Farseer it seems like this might be a worthwhile thing to consider.

For instance the CollisionFilter has a reference to the owning Fixture, and the Fixture has a reference to the CollisionFilter but the collision filters are private. The CollisionFilter is only set privately by the Fixture - a quick scan of the code referencing the CollisionFilter suggests this class could perhaps be collapsed into a base class for the Fixture to save two references as well as an actual object on the heap (the CollisionFilter). Another possible improvement is for the CollisionFilter to just store the fixture id; it looks like all uses of CollisionFilter._fixture except for FilterChanged() could be trivially modified to use the fixture id instead of the reference - still being new to Farseer I'm not sure if there's an easy way to find filters by filter id in that method.. if not, the reference could in theory just be passed down from the callers. Anything to reduce reference & live object count would be a good thing imho. If there are objects that track Fixture references that only rarely use them, perhaps a static Dictionary<fixtureId, Fixture> would be a useful thing to have to reduce the reference counts in general by looking up the fixture when it is occasionally needed.

Also, the CollisionFilter always sets up a dictionary even if it's not known to be needed - perhaps these dictionaries could be created/released when needed instead of always being set. To be honest I think an ignore table per fixture is too much for this class. I would prefer to do collision filters using callbacks instead of pre-emptively building tables of things to ignore - it's that much more stuff to clean up if an ignored fixture gets removed because there might be dictionaries still tracking the fixture id indefinitely with no benefit. If the caller wants to implement a dictionary for managing ignores, fine, but to me it doesn't seem like a universal need of the users of this class and it makes more sense to make the callbacks do that if they want that functionality and not make every fixture pay the price in live (or even null references to) dictionary objects.

On the subject of callbacks, I suspect many if not most fixtures do not have any callbacks set up for them at all (such as static game map fixtures and just a few actors moving around). If the callbacks for a fixture were hosted in another object (such as "interface IFixtureCallbacks") then, if my suspicion is correct, there would be a net gain of at least 3 references per fixture. If the interfaces were methods actually performing the callback logic (and not returning delegates) then the number of callback related references could actually go down to one (the reference to the interface).

Something I noticed while reviewing the CollisionFilter is that the various properties that check _fixture.Body == null before storing a value and it seems like perhaps they should store the value regardless of a body being present in case there are unexpected order of operations that occur with these properties. The _fixture.Body check could possibly just be done inside the FilterChanged() method.

The fixture proxies array could be tracked in a separate static Dictionary<fixtureId, FixtureProxy[]> to eliminate references on fixtures that aren't currently associated with Active bodies. I have a lot of inactive Fixture objects that will never use this reference. The existing public Proxy and ProxyCount fields could be changed to refer to this (possibly private) static dictionary.

 

Thanks for reading-

Coordinator
Feb 6, 2011 at 12:52 PM

@Matthew:

Would it be a good idea to move the flattening of the texture array into the DetectSquares itself? That way we supply the raw texture data directly into the method, just like the TextureConverter class.
Also, I've never seen a sample that uses different width and height for the cells, if it is supported, could we implement it in a test?

I guess a lot of the code in the Testbed test could be wrapped in an API as they are common functions.

@Eric:

So basically you want to keep the number of live objects down to a minimum? The library is a balance between maintainability, usability and performance. It is hard to turn up one of those factors without affecting (turning down) the other two. The points you made are valid, but some of the code you mentioned is simply to make it easier for new users. Let me explain some of them:

- CollisionFilter used to be collapsed with Fixture, but all the methods that "should" make it easier to add collision categories clutter up the general API of the fixture, so it was moved to a class by itself. Perhaps it should be changed to a structure to keep it off the heap?

- FixtureIDs are an implementation detail and will probably be set to private at some point.

- The body null checks are there as a leftover from refactoring.

----------------------------

Having all your suggestions in the back of my head, I think this is what needs to be done:

1. Remove collision filter convenience methods (programmers need to learn bitwise manipulation at some point - and good comments/documentation can help with that)
2. Collapse CollisionFilter into Fixture
3. Remove body null checks from all methods. (Will change Fixture constructors so that we can always expect a fixture to have a body)
4. Only instantiate _collisionIgnores when it is needed

A couple of questions:

1. I was under the impression that when the delegates are not subscribed to, they don't store any reference. How would an interface improve on the live object count compared to using delegates?

2. You also suggested that Fixture and FixtureProxy classes should be stored in a Dictionary using IDs instead of references (If I understood it correctly). Would that not just cause the references to be stored in the Dictionary instead of the classes themselves? It also would require the code to clean up the Dictionary when objects are removed.

Developer
Feb 6, 2011 at 7:45 PM
Edited Feb 6, 2011 at 8:05 PM

@GenBox

I like the list of things you feel need to be done. Thanks for considering my post. Finding the right balance between usability and performance is always hard but I think the changes 1..4 you listed are good for everyone. I think new people are better served by seeing optimal code instead of convenience functions that encourage suboptimal usage so I'm glad to hear you agree about removing the convenience functions. A demo can show how to do the same thing if people really wanted to take that approach to filtering.

To answer your questions,

1) The interface suggestion isn't so much about reducing live object count, its mainly intended to reduce the GC's routine work of evaluating every reference member of every live object. The unused callbacks are still reference types that have to be evaluated by the GC to see if they have to be marked for retention and evaluated further. Its not a huge cost but if the majority of objects don't require it, which in my case is true, merging all the callbacks to a single reference to an interface type would be optimal. An alternative would be a change to a class that stored delegate references, provided public methods that wrapped calls to these delegates with null checks. That would reduce the reference usage down quite a bit, but I think that an interface approach would be easier to use and would avoid the need for null checks. With the interface technique, when a need for callbacks was found, the user (coder) would just implement the interface and use essentially empty methods that returned default values/behavior if they didn't need that particular callback. This would be about the same runtime cost as a wrapper class that does branch on a null check, but with the interface approach the user would usually use visual studio's implement interface refactor tool which adds the method stubs and they just fill them out (probably by doing nothing other than return true in most cases). I think this would be pretty user-friendly and performance wise helps keep the GC work at a minimum. There would be only a single reference to the interface type tracked by the fixture even in the worst case where every callback is required, and there would be no additional GC work for evaluating the usually-null callback references during the mark phase.

2) You are correct, it would cause the references to be tracked in the dictionary. The Fixture.Dispose() would need to do the dictionary cleanup. The idea here is that you could essentially make it possible to have anywhere a fixture is tracked with a reference swapped out for a new value type, the FixtureId. FixtureId would be a struct with a Lookup method that knows how to find the fixture in the dictionary and return it to the caller. (I'd recommend two methods, one 'Fixture Lookup()' that assumes the Fixture exists and returns the reference (toss an exception if not) and another 'bool TryLookup(out Fixture)' that returns a bool and sets an out Fixture using Dictionary.TryGetValue) Anywhere a fixture is typically tracked but only rarely used it would be encouraged to use a FixtureId struct instead of a Fixture reference - this could have a pretty big impact on the number of reference members the GC has to evaluate (potentially orders of magnitude). It might seem to defy logic that going through a dictionary to look up a reference by Id is better than just tracking a reference, and I can't promise it would help in this specific case but in my own projects I've found GC load to be the biggest problem and it really helped my stuff run faster to use value Id's whenever possible. Side note, I'd avoid making the lookup a casting operator to make it clear there is some small cost to doing the lookup and that if best performance is required the Fixture should be temporarily cached.

Ideally, instead of the Fixture objects being stored in a Dictionary<int, Fixture>, it would be best to use a handle system. This is where you use a fixed length array with each element being an object that stores a counter value and the reference to the object. The FixtureId struct would store the array index and the element's counter value as it was at the time the object was registered. The casting operator or method to retrieve the fixture would confirm the array's counter value was the same as the FixtureId's copy to detect when a slot had been released and reused and return null instead of an incorrect reference. This is a standard handle technique best described by Noel Llopis's article, http://gamesfromwithin.com/managing-data-relationships, except in C# the 'type' bits aren't necessary. Dictionaries are great for a lot of things but in this case a handle table like this would be optimal, reducing the cost of retrieving a Fixture from it's id down to an array lookup and an integer comparison which faster than a dictionary. You could even allow for a FastLookup that skips the comparison in situations where you know the fixture Ids are all valid.

The nice thing about moving in this direction is that it is a non-API breaking change. Once the Fixture is hooked into the handle system (or a Dictionary to start might be easier, swapping to handles can be done internally), the users (and the Farseer core itself) can transition to the new approach where appropriate and as time permits. People can continue to track Fixture references if they want to, or switch over to FixtureId if they want to reduce the GC costs.

Switching to handles should probably be considered in any other situation that might benefit from it, so making the HandleManager a generic type is a good idea. I don't yet know enough about Farseer to suggest what else might make sense for it though.

 

Coordinator
Feb 6, 2011 at 9:37 PM

@Eric:

I see what you mean, but it conflicts with a couple of things in my head:

1. As I understand it, the GC only tracks objects allocated on the heap, and not delegates/classes that have not been subscribed (or instantiated). In tests I have done, the number of managed objects only goes up when a delegate has been subscribed to.

2. I still don't understand why you would track the objects inside a Dictionary instead of just saving the references inside the objects. It might be because I completely miss the point here.

Would it be possible for you to implement your suggestion, test it and post the results? I'm interested in any way we can reduce the load on the GC, especially for WP7 and Xbox360 (.NET has generational GC for PC, I'm not too worried there). I will do the same with the other changes you suggested (1-4 in my previous post).

Developer
Feb 6, 2011 at 10:38 PM

@Genbox,

To exaggerate the issue to make a point, if you have a class that consists of 1000 references to other objects, I believe the GC has to evaluate each of those references even if they are null. This overhead is not a lot, and I'd bet most people don't even think about it but if there are a lot of these objects it can be relevant. That's the main point & reason for using value Id's instead of references. This isn't to say every case of a member object reference should necessarily be swapped for this kind of approach, but in situations where the references are only occasionally needed it can reduce the routine overhead of the GC system. There is an additional benefit of centralizing ownership of the reference which in complex situations can be nice to know when you Dispose it that it's more likely to actually be disposed since the number of places that have a strong reference to it can be reduced to one if desired.

I'll try to find some time to try this out to demonstrate the differences in performance in one of the Farseer samples, but I can't promise anything soon as I'm trying to get another project finished at the moment. Some numbers that validate what I'm suggesting would make sense to have.

I became aware of this performance issue from a post by Shawn Hargreaves that explains it pretty well and is where he suggests replacing references with handles when possible - http://blogs.msdn.com/b/shawnhar/archive/2007/07/02/twin-paths-to-garbage-collector-nirvana.aspx?wa=wsignin1.0

 

Coordinator
Feb 6, 2011 at 11:12 PM

Oh, I see. You are talking about the latency of checking the object tree. I would like to see how your implementation, so let me know when you have something working and I'll take a look at it. We have focused a lot on minimizing the amount of garbage generated by the engine at runtime, so the latency is not an issue at the moment. However, I would like to keep both the latency and the garbage collections to a minimum if possible.

Coordinator
Feb 7, 2011 at 10:20 PM

I've implemented the BodyFactory as I proposed in the first post. It seems to work well and simplifies the engine outer API a bit.

Friction, restitution, OnCollision and OnSeparation has been wrapped into Body.

@Matthew: The only test I could not convert to use the new BodyFactory was your MarchingSquares test. The reason being that I'm not sure how it works. It would be great if you could patch it up.