While working on a 2D particle physics terrain system similar to that in Worms or Cortex Command (which isn’t finished enough to have a page here yet), I needed a way to speed up the whole system in general. The obvious answer to this was to implement a quadtree for the particles.
I could have simply written a specialized quadtree for the particles which would have worked fine. However, using the knowledge of templates I gained while working on Versus the Internet, I decided to write a reusable C++ template quadtree.
The quadtree template holds a structure for each object, containing a pointer to the object itself and an included rectangle class for the outer bounds of the object for sorting it in the quadtree.
Other than that it works like any standard quadtree with elements being retrieved based on a rectangle of the area to retrieve from.
Using this implementation increased performance for insertion and removal in my terrain system around 20,000%. That is not an exaggeration, framerate increased from 0.1 fps using an STL Vector to hold the particles in the terrain to 2000+ fps using my quadtree.
I plan to make this quadtree system open source on Github with a permissive license so that anyone may use it after adding a few more comments to help those who do not fully understand quadtrees.