Quick Post

Alright.

Quadtrees using proxy indicies are too slow (because if you don;t define them carefully, AKA if you don;t enforce data always being in the leaves, well, it goes to hell. Draw it out to see what happens.)

Quadtrees using leaved index lists seem to do OK, however, their performance is not that good. It certainly costs a lot of memory and speed to handle space, and they are conformal space limiting.

Thus, we are required to develop a better, more efficient structure. In this case, I choose a interval list. However, you immediately scream "O(n)!" and to that, I say "Balanced Binary Tree"

Of course, you mutter about "2 log2(n)" but you;d be right for deletions. Additions are worst case log2(n).

Actually, if you think about it, given a random set of any data, the absolute fastest way to sort and store that list IS clamped at a maximum of log2(n). You might think that hashtables can beat it, but come on peoples, hashtables are application specific optimization. Sure, if you know your inputs are bounded you can hashup your memory and get a hashlist of B-Trees, but is that step actually going to save much? And besides, looks like you still HAVE TO MAKE THE GODDAMN TREE!

In summary, this is the current problem. If you think you are smart, solve this problem. When you find out you're an idiot, don't complain to me:

Given a random set of intervals (minimum (float32) and size (float32), create a data structure that can store these intervals sorted by the minimum value, and be able to quickly determine interval queries, AKA stabbing queries. The structure should have as minimum a memory footprint as possible, and you can assume you have Alloc, Realloc, Free working properly. Also, the structure cannot use hidden operations internally (No OOP or C++ tricksies internally), however externally it may operate as a class interface. It must support insert( proxy ), remove( proxy ), and get( float min, float size. ProxyList & ). A proxy contains at least unsigned int user, which contains the user data for what the proxy is in user memory. It cannot leak memory. It must work in practice and be implemented.

Practical application? Pretend you are building a 2D game that uses edges for level collisions, which can be added and removed every frame, on the fly. (in the editor) Once the user is happy with their setup, obviously we use a static BVH for static data.

Good Luck!

-Z