Region processing is O(n) complexity

[stephanemagnenat]

In BroadPhase.update_aabbs, within complete_removals that is called if there is any out of bounds proxy, or in BroadPhase.find_pairs, the code iterates over all regions in an O(n) complexity (where n is the number of regions). So if there is a big world with a lot of regions with fully asleep proxies, which in principle would not need to be processed as their state does not change, they are all touched. It is probably a future optimisation, but I am wondering whether it would be helpful at some point to create a tree structure over the region hash map and track in each node whether that subtree needs any processing.

Originally discussed in https://github.com/dimforge/rapier/pull/30#discussion_r500802785

[robert-hrusecky]

I think we could get by with something even simpler than a tree: a queue perhaps, or maybe a second hashmap. The preupdate and predelete functions could enqueue region keys. This way we only process active regions.

[stephanemagnenat]

That's true, a tree is indeed not really needed!

[sebcrozet]

Yes, there is scalability issue here. The solution suggested by @robert-hrusecky should do the trick: enqueue regions in the preupdate and predelete functions. We just need to make sure that we don't enqueue the same region twice, by testing !self.need_update && self.to_insert.is_empty() before enqueuing for example.