Monday, April 18, 2011

Farseer inactive object optimizations and other minor features

I'm about to submit a patch for the optimizations I mentioned in my previous post. The description field on CodePlex has a size limit which doesn't allow me to put all my notes in there so I'm putting a copy here for people to reference.

I've been running with these optimizations for almost two weeks now and everything seems to be working correctly both in our next game and in all the Farseer testbed examples. Hopefully I didn't overlook anything :)


Here's the full notes:
--------------------


This commit contains a number of optimizations primarily related to the overhead of inactive objects. By request this includes all my other recent changes in a single patch including fixes to joint math and a few other small features. Inactive objects now have very little overhead, and fixtures can be selective about when CCD is performed between objects.

There are #defines to control the new features to help with testing their behavior against the unoptimized (previous) version of the logic they control. I considered removing them for the submit but I thought given the complexity of the various optimizations that it might be best to leave both code paths in place for the time being and we can remove the slower code path in a subsequent commit. Also, it helps to show what optimization each code change is related to given this is a large commit with what are for the most part unrelated changes. The #defines are currently in the .cs files, sometimes #defined in multiple files as needed to keep code in sync.

This commit also includes ports of Box2D rev 167 which has joint related fixes.

The #defines are:
USE_AWAKE_BODY_SET - Reduces iteration costs to only the bodies that are awake.
USE_ACTIVE_CONTACT_SET - Reduces iteration costs to only the contacts that are active.
USE_IGNORE_CCD_CATEGORIES - Allows content to define fixtures that ignore CCD with only a subset of objects. This allows for the selective use of CCD where it has value instead of the all-or-nothing setting previously available.
USE_ISLAND_SET - Reduces iteration costs for island logic to only bodies that are determined to be in an active island.
OPTIMIZE_TOI - Reduces iteration costs of CCD logic to only the bodies participating in CCD.

Body changes:
* Body has been optimized to use "Awake Body Sets" which causes various iterators to only evaluate active objects.
* Body.Body no longer forces new bodies to Awake.
* Body.BodyType now sets Awake=false if the body type is set to Static, and wakes the body otherwise.
* Body.Awake.set now updates contacts when the body is set to Awake.
* Body.Awake.set now adds or removes the body from the AwakeBodySet as needed.
* Body.Awake.get now returns false if the body type is Static.
* Added bool Body.InWorld, which tracks if the Body has been added to the world or not.
* Added Category Body.IgnoreCCDWith. Existing behavior is unchanged if unset. This can be useful for reducing CCD overhead. Note this is a setter only, and that it propogates the value down to fixtures the same way that the existing CollidesWith and similar setters do.

ContactManager changes:
* Added ContactManager.ActiveContacts which is used to limit which contacts are evaluated during updates.
* ContactManager.Destroy(Contact contact) updated to perform active contact management.
* ContactManager.Collide now iterates only the contacts found in the active contact set, adding/removing members as needed.
* Added ContactManager.UpdateContacts(ContactEdge, contactEdge, bool value) which is used by Body objects when their Awake status changes.
* Added ContactManager.RemoveActiveContact(Contact contact) which is used by Contact.Destroy() to ensure the active contact set is properly updated.

Other contact related changes:
* Contact.Destroy() now calls ContactManager.RemoveActiveContact(this).
* ContactSolver.InitializeVelocityConstraints() now sets k_maxConditionNumber = 1000.0f to match Box2D rev 167.

Fixture changes:
* Added Category Fixture.IgnoreCCDWith which allows specific fixtures to ignore CCD with specific categories of objects. This allows fixture to be configured to ignore CCD with objects that aren't a penetration problem due to the way content has been prepared, such as slow moving fixtures that usually only iteract with static objects but occasionally need to react to bullets.
* Fixture.Fixture now sets _collisionCategories = Settings.DefaultFixtureCollisionCategories and _collidesWith = Settings.DefaultFixtureCollidesWith, allowing apps to configure default values in the settings.
* Fixture.Fixture sets IgnoreCCDWith to Settings.DefaultFixtureIgnoreCCDWith.
* Added Fixture.UserBits, which is a long value for use by the application. This is unused by Farseer, but it is Cloned and used by CompareTo as expected.

Joint changes:
* DistanceJoint has had some comments pulled over from Box2d.
* FixedRevoluteJoint.LimitEnabled only wakes the body if the limit changed and sets _impulse.Z to zero as part of Box2D rev 167.
* FixedRevoluteJoint.LowerLimit only wakes the body if the limit changed and sets _impulse.Z to zero as part of Box2D rev 167.
* FixedRevoluteJoint.UpperLimit only wakes the body if the limit changed and sets _impulse.Z to zero as part of Box2D rev 167.
* Added FixedRevoluteJoint.SetLimits(float lower, float upper) to match Box2D.
* Renamed FixedRevoluteJoint.MotorTorque to MotorImpulse to correctly reflect what it returns.
* Added FixedRevoluteJoint.GetMotorTorque(float inv_dt) to match Box2D.
* FixedRevoluteJoint.SolveVelocityConstraints has been updated to match Box2D rev 167, which has various mass related math fixes.
* PrismaticJoint.LowerLimit, .UpperLimit, .SetLimits, .MotorForce->.MotorImpulse, .GetMotorForce have been updated in similar ways to FixedRevoluteJoint for Box2D rev 167.
* Added RevoluteJoint.RevoluteJoint(Body bodyA, Body bodyB, Vector2 worldAnchor), which simply calculates the local anchors for both bodies.
* RevoluteJoint.LowerLimit, .UpperLimit, .SetLimits, .MotorTorque->.MotorImpulse, .GetMotorTorque and .SolveVelocityConstraints have been updated in similar ways to FixedRevoluteJoint for Box2D rev 167.

World changes:
* Added World.AwakeBodySet which tracks all active bodies.
* Added World.AwakeBodyList which is a short term list used during updates.
* Added World.IslandSet which is a temporary set used during World.Solve.
* Added World.TOISet which is a temporary set containing objects participating in CCD.
* World.World now initializes the AwakeBodySet, AwakeBodyList, IslandSet and TOISet.
* World.RemoveBody removes the body from the AwakeBodySet if needed.
* World.ProcessChanges asserts that all bodies in the AwakeBodySet are in the BodyList (#if DEBUG only)
* World.ProcessAddedBodies adds/removes bodies from the AwakeBodySet as needed, and sets Body.InWorld to true for all added bodies.
* World.ProcessRemovedBodies asserts the AwakeBodySet doesn't contain the body being removed, since that would indicate an earlier failure to maintain lists correctly. This is checked again at the end because callbacks could (and have) re-added objects incorrectly by indirectly causing Body.Awake to be set to true.
* World.ProcessRemovedBodies sets body.InWorld to false.
* Added World.SetIsland(Body body), which is used for keeping track of all bodies that are in an island.

World.Solve changes:
* Iterates only the active contacts to clear the ContactFlags.Island flag.
* Iterates only the active bodies during the main solve loop.
* Adds each nonstatic body to the IslandSet during the main solve loop to help with fixture update loops (below)
* World.Solve fixture update loop changes:
* Iterates only the bodies in the Island set to update their fixtures (instead of all bodies in the world).
* No longer expects BodyType.Static objects, and asserts if it finds any because they shouldn't be moving and thus shouldn't be in the island update set.
* Adds all bodies in the IslandSet to the TOISet which is used later to optimize SolveTOI. Note the TOISet is not necessarly empty, and this is not just a copy of the IslandSet.

World.SolveTOI changes:
* Only clear BodyFlags.Island and init Sweep.Alpha0 for bodies in the TOISet (instead of all bodies in the world).
* Invalidate the TOI only for active contacts (instead of all contacts in the world).
* Find TOI events only for active contacts (instead of all contacts in the world).
* Add support for Fixture.IgnoreCCDWith.
* After determining two bodies need to interact, if the TOI step is complete, for both bodies if they aren't yet in the TOISet clear the BodyFlags.Island and init Sweep.Alpha0.
* Clear the TOISet if the call to World.SolveTOI was the last iteration.

FarseerPhysics:Settings changes:
* Added public static Category DefaultFixtureCollisionCategories = Category.Cat1. This is used by the Fixture constructor as the default value for Fixture.CollisionCategories member.
* Added public static Category DefaultFixtureCollidesWith = Category.All. This is used by the Fixture constructor as the default value for Fixture.CollidesWith member.
* Added public static Category DefaultFixtureIgnoreCCDWith = Category.None. This is used by the Fixture constructor as the default value for Fixture.IgnoreCCDWith member.

Misc changes:
* GameSettings now has float Hz, used in place of hard coded 30hz(phone) / 60hz (pc/xbox) used by various tests.
* RevoluteTest.RevoluteTest has been updated to match Box2d rev 167.
* SliderCrankTest.Update now uses GetMotorTorque(settings.Hz)
* DynamicTree.Rebalance has been removed (Erin Catto confirmed this is no longer required).
* DynamicTreeBroadPhase.UpdatePairs no longer calls DynamicTree.Rebalance.
* HashSet<T>.CopyTo has been implemented.

Tuesday, April 5, 2011

Recent Farseer optimizations

We're working hard on our next game right now and one thing I've been focusing on is the performance of the Farseer Physics Engine. It's a great engine but I have seen a few things that could use some improvements so I spent some time recently doing just that.

A few days ago, I made some changes for which I submitted Farseer patch #9000 to Codeplex.The original motive was to fix some revolute joint bugs by bringing over some fixes from the Box2D engine which Farseer is based upon. To my pleasant surprise, the update also resulted in a nice performance boost thanks to the code no longer needing to rebalance a tree structure all the time. At first I was nervous about seeing that change, but I checked with the Box2D forum where Erin Catto (the admin/author of Box2D) was kind enough to confirm this is a valid change. Check out the comparison shots (the optimized version is on top):

So that was pretty nice performance bonus that came along with the revolute joint fixes. I've been using these changes locally for a few days now and it seems to be working fine so I hope to see them applied to Farseer at some point.

While looking into all this I saw a few things I could do to improve performance further, so I did. I added four different optimizations, listed in order of gain:

  1. Active Contact sets. The world no longer iterates every Contact during World.Solve(), World.SolveTOI() and ContactManager.Collide(); it instead maintains a set of contacts that are active and reduces how many objects it has to evaluate. In some cases where scenes are mostly inactive, this can provide a dramatic improvement and should allow Farseer games to be much more heavily populated with inactive objects.
  2. Awake Body sets. The world no longer iterates every Body during World.Solve(); it maintains a set of Body objects which are active. This is enough information for the Solve code to perform collision island processing while iterating the minimum number of Body objects.
  3. Island Body sets. This last optimization allows the World.Solve() to track all the Body objects that had been processed by the island code so they may have the appropriate secondary logic applied to them (synchronizing fixtures). This avoids another iteration of every body in the world. 
  4. Body.Awake never returns true if the body is static, allowing various bits of code to do less work. I haven't yet seen a reason why a static body would ever need to be reported as Awake, and I haven't seen any side effects from this change. The main benefit of this is to make the above optimizations more effective since the related code no longer iterates static objects except as a byproduct of the island logic.
With these three changes, it seems most of the "iterate everything" logic in the core solvers is no longer happening for objects that aren't awake. This means sleeping objects have had their per-frame recurring overhead reduced to less than 20% of its original amount. Sleeping objects are so low on the radar at this point that I don't think I'll be concerned about loading up scenes with more objects so long as I can ensure they don't all activate at once. This was actually an issue with Moonlander because the original design was to make a fairly large map and leave it resident. I wound up having to add/remove terrain chunks as you fly around due to the surprisingly large overhead that having a bunch of bodies in the world will incur.


Here's a screenshot of before/after:

The contact management was the lions share of the optimization here, pulling about 85% of the gains. The awake body logic was about 10% and the island set was a pretty minor one at around 5%. Those numbers are approximates, I didn't take notes. A quick glance at the branch of Box2D I have here suggests it could benefit from a port of these changes, fwiw.

I've tested these changes against all the TestBed samples and our game and everything seems fine but I'm going to wait a little longer before building a patch for Codeplex because I just want to let it cook a bit just in case something pops up. There's also a chance I may be able to reduce that CCD time.

These changes are looking promising right now. Hopefully I'll be able to put a patch up in a week or so once I've become more comfortable with the changes and wrapped up any other related optimizations.