1

Closed

Suggestion: Implement loose QuadTree to improve performance

description

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): http://www.tulrich.com/geekstuff/partitioning.html
 
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): http://donar.umiacs.umd.edu/quadtree/rectangles/loosequad.html
 
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.

file attachments

Closed Jul 2, 2013 at 7:09 PM by genbox
no longer applies as the quad tree has been removed from 3.5

comments

vvnurmi wrote May 27, 2012 at 11:14 AM

Here's a comparison of the old QuadTree with the new loose QuadTree in action. Tree nodes are colour coded by the number of fixtures that are stored in them. The white object in the middle consists of about 150-200 smallish triangular fixtures. You can see that the old QuadTree stores a large number of fixtures in the quadtree root. The loose QuadTree implementation manages to keep all large tree nodes empty or with an acceptable amount of fixtures. Only small nodes overflow some.

genbox wrote Oct 22, 2012 at 2:25 PM

I will surely take a look at this and see if we gain some improvements in regards to performance.

genbox wrote Dec 30, 2012 at 1:48 AM

I implemented the loose quadtree, but overall performance dropped in my testcases. This is perhaps the fat and thin AABBs are generated all the time.