I have just posted a tutorial on super-fast instant-insert quadtrees here. Efficient Instant-Insertion Quadtrees
The downsides of typical implementations of quadtrees is related to caching and searching (which compounds the caching problem) when objects are inserted into it.
Here, I explain 2 ways to improve the cache:
- Insert objects into the tree instantly, without a search.
- Store all the tree nodes together in one large pool of nodes.
I use bit hacks to instantly determine how deep into the tree an object is, and then I store the nodes at each level in a grid-like order so that I can instantly convert the object’s X and Y coordinates to the X and Y indices of the node to which it will be inserted.
The results are quite drastic. I can update, move, and re-insert 30,000 objects into this quadtree at 60 FPS on an iPad 3.
So read it for yourselves!
L. Spiro