Hi
Say i have like 5000 quads all over the game map. And i want to place another one and check to see if it overlaps another quad. The quad can be any orientation, i was wondering what is fast way to find any quads that it might overlap.
I can do a quad overlap check easily, but finding which ones to test against how ever is not so easy. And i am looking for a really performant way to do it. Any suggestions on the most efficient way to do it ?
Use some spatial partition so you do not need to check all 5000 quads.
The simplest way is a regular grid. Each grid cell has a list. You add each quad to each cell list it overlaps, and to check for collisions you iterate the lists for potential overlapping existing quads.
Downside: Quads will be contained in multiple lists, and the maximum required list size is unknown. This can be prevented with the idea known as 'loose' quadtree: Each quad links to only one node, so you can use a single pointer per node and quad instead the list. (node -> firstQuad-> secondQuad etc.)
Notice the same idea also works for multiresolution grids. This is easy to implement and fast. A tree might be necessary if you have very small objects and large fine grids would take too much memory.
Other options are a BVH (tree with flexible bounds), or spatial hashing (similar issues as with regular grid).
13 hours ago, CelticSir said:thank you, quad tree seems like the ideal solution
Consider BVH as well.
Historically, gamedevs are so used to quad/octrees - it's always the first thing comes into mind (including myself - my bad is i should have talked more about BVH from the beginning).
BVH advantages:
Other than for quadtree you can keep and refit lower branches of a tree instead to rebuild or update the whole tree each frame for dynamic scenes. (E.g. a ragdoll can keep its hierarchy all the time, just the bounds need to be refited per frame. Only the top level hierarchy that connects all ragdolls needs to be rebuild from scratch.)
It's easier to leverage cache miss cost of node traversal against work efficiency: BVH can have more children and content, sou you can iterate over linear memory for longer than with quad / octree. Even if you do more work, this will be faster and you can tune the ratio, while loose quad/octree has alignment constraints that prevent this.
It's easier to implement as well.
