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.