it is already fast, 3 ms for 1.000.000 object insertion

Are you sure about these numbers? They look incredibly high. It's like ~12 cpu cycles per object. Can you give more details about your benchmark? It's really interesting.

Are you sure about these numbers? They look incredibly high. It's like ~12 cpu cycles per object. Can you give more details about your benchmark? It's really interesting.

Uh, I'm not so sure, seeing what I wrote in another thread, I probably meant 30 ms, which should sound more reasonable. Here you can also find the implementation of my octree. As I said there, the "max extents" function for the AABB-class is unoptimized, this makes the insert time finally be about 20 ms, for 1 mio objects.

I'm curious as to how Julian was indexing his 1D array of octants? My implementation was breaking a 32-bit integer into groups of 3-bits that represented each depth, which maxed out at 10 depths with about 4GB of memory minimum with no data.

I didn't use the 1D-array approach at all, as you can see in the thread I linked to above, I have each node store its child nodes. 10 depths is completely unreasonable IMHO, like you said it will take about 4 GB of RAM just for the array of 8^10 entries. Such a tree would subdivide an area of 1 km size into 0,97 m sized cubes on the lowest level. You aren't likely going to need that much precision, or that large of a scene anyway. Also, with such a high depth, the tree will easily become a bottleneck, since you have to traverse all 10 levels. So you should probably don't go deeper than 6 levels.

Juliean, you're doing insertion into std::map on every InsertData() method call in your implementation. That alone will severely limit performance of your octree insertions. In fact, putting 1000000 sequential integers (from loop counter) to std::map<int, int> takes about 220 ms on my i5 2400 (both in VS2012 and MinGW, release builds under 32-bit Win 7). And putting 1000000 random integers (as keys and values, from array that is prepared beforehand) takes about 500 ms. So i'm very interested about how you got your numbers.