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:

1. Insert objects into the tree instantly, without a search.
2. 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

That's pretty damn slick - gotta love the bit-hacks.

Interesting stuff! I just made a simple quadtree program last week to refresh myself on the C++ language.

I may try making this quadtree as a challenge.

Great tutorial!

Wit this technique, are my world coordinates forced to be from 0 - 256? And objects will only be spatially sorted at a resolution of (1/256)?

That would make it very limited, wouldn't it? It's 256 in his example since it's easier to show how it works in 8 bits. You can use 16 or 32 bit types if you want, for a much larger area.

Wit this technique, are my world coordinates forced to be from 0 - 256?

No, you just need to apply a suitable conversion factor.

And objects will only be spatially sorted at a resolution of (1/256)?

Yes. That should be plenty to significantly speed up collision detection, or any other naive O(N^2) process.

You can use 16 or 32 bit types if you want, for a much larger area.

You will run out of memory - it's not feasible to preallocate enough storage. If you really need a quad-tree with depth greater than 8, then you need a sparse representation thereof.

You can use 16 or 32 bit types if you want, for a much larger area.

You will run out of memory - it's not feasible to preallocate enough storage. If you really need a quad-tree with depth greater than 8, then you need a sparse representation thereof.

Oh right, I mixed up the world coordinates for depth representations. I forgot for a moment that the 8-bit value represents the tree levels, not coordinates.

Converting the coordinates as you said makes more sense.

		// Now to the range from [0..255].
		a2Shifted.m_vMin.x *= m_fInvRadius;
		a2Shifted.m_vMin.y *= m_fInvRadius;
		a2Shifted.m_vMax.x *= m_fInvRadius;
		a2Shifted.m_vMax.y *= m_fInvRadius;