QuadTree suffers from poor performance when there are fixtures lying over the boundaries of the children of the root node. This is a feature of quad trees in general.
The performance hit can be bad -- if, say, 100 small fixtures are located at the center of World, they will all be stored in the root of the QuadTree. Then every Query and every RayCast will loop through those 100 small fixtures even if the queried area is
nowhere near the center of World.
To significantly improve performance in this situation, I modified QuadTree to become a "loose quad tree".
Here is an introduction to loose quadtrees (he speaks about octrees, but the idea is the same):
Here is a live demo of loose quadtrees (for comparison, you can click on "Data Structures" and choose MX-CIF Quadtree which seems to be the closest alternative to Farseer QuadTree):
The idea is that each QuadTree node spans over an extended area. I settled for a 50 % increase in each of the four directions which suited my case well. Tree nodes will overlap. As before, fixtures are added to the smallest node that completely contains the
fixture. If there are many such nodes, choose the one where the fixture is the farthest from the node borders.
When splitting tree nodes, I consider the unextended node area, split it into four non-overlapping quadrants and then extend them by 50 %. Children must be extended to make them overlap, that is key to good performance). I reduce the parent node area to make
the nodes reduce in size regardless of how large an extension you choose.
In the World constructor, I expand the world area by 50 % and create the root node for that size. This is essential for performance. If I don't extend the root, then its children won't cover the borders of the world area, which results in poor performance.
I have attached a ZIP with my modifications and the original Farseer 3.3.1 files for comparison. I wanted to include a patch but couldn't find any decent patch program for Windows :-(. The changes are quite few. You can also recover the original QuadTree behaviour
even after these modifications if you set the extension to 0 % from Settings.
The most essential change is of course in QuadTree.cs. Affected methods are Partition and AddNode. Partition finds the correct subnode for an AABB by computing how well each subnode contains the AABB. AddNode is modified only for the part where a node is split
into four subnodes.
Also affected is QuadTreeBroadPhase.cs. In the constructor I extend the world area to avoid possible performance problems at world borders, as mentioned above.
Collision.cs contains three helpers. New AABB properties Fattened and Thinned can be used to add and remove the quad tree node extension. A new method AABB.ContainmentDistance(AABB) is used like AABB.Contains(AABB) except that it returns a float denoting the
distance the provided AABB can move to any direction while staying contained in this AABB. It returns a negative number of the given AABB is not contained in this AABB.
Finally, Settings.cs contains a new constant, QuadTreeLooseness, which is the extension ratio of quadtree nodes. I settled for 0.5 which gives 50 % extension to each direction. Setting this to 0 would give the old QuadTree behaviour with its performance penalties.