Quote Originally Posted by kiranraj View Post
So,in the average case searching here takes O(1)-constant time right??-faster than O(log n) algo.
The problem is not finding an item but finding all items colliding with another item (in other words finding all items occuping fragments of the scene occupied by a particular item). If you wouldn't have any caching/heuristic mechanism, you'd have to do a linear search through all the items. With BSP you simply check the nodes occupied by an item (so checking is probably O(1), but moving the item in the tree is O(lgn) which is greater than O(1) so the overall cost of manipulating the tree is O(lgn)).

Not going into details - run the 40000 chips demo from Qt4, but change the number of items to 1E+6. Check memory usage and usability. Then do the same with QCanvas and Qt3. Again check memory usage and application responsiveness.