What is the best data structure for an AABB collision checking physics engine?

Question

I need an engine which consists of a world populated with axis-aligned bounding boxes (AABBs). A continuous loop will be executed, doing the following:

for box_a in world
    box_a = do_something(box_a)
    for box_b in world
        if (box_a!=box_b and collides(box_a, box_b))
            collide(box_a, box_b)
            collide(box_b, box_a)

The problem with that is, obviously, that this is O(n^2). I have managed to make this loop much faster partitioning the space in chunks, so this became:

for box_a in world
    box_a = do_something(box_a)
    for chunk in box_a.neighbor_chunks
        for box_b in chunk
            if (box_a!=box_b and collides(box_a, box_b))
                collide(box_a, box_b)
                collide(box_b, box_a)

This is much faster but a little crude. Given that there is such a faster algorithm with not a lot of effort, I'd bet there is a data structure I'm not aware of that generalizes what I've done here, providing much better scalability for this algorithm.

So, my question is: what is the name of this problem and what are the optimal algorithms and data-structures to implement it?

Answer 1

this is indeed a generic problem of computer science : space partitionning.

its used in raytracing, path tracing, raster rendering, physics, IA, games, and pretty sure in HPC, databases, matrix maths, whatever science (molecules, pharmacy....), and I bet thousands of other stuff.

there is no 1 best structure, I have a friend who did his master on an algorithm to tesselate a point of cloud coming out of a laser scanner (billions of data) and in his case the best data structure was to mix a collection of uniforms 3D grids with some octree.

For other people kd-tree is the best, for other people, BVH trees are the best.

I like the grid system but it cannot work if the space is too wide because all cells has to exist.

One day I even implemented a sparse grid system using a hash map, it worked, I didn't bother to profile or investigate the performance so I wouldn't know if its an excellent way, I know its one way though.

To do that, you make a KEY class which is basically a 3D position vector hasher, first you apply an integer division on the coordinates to define the size of one grid cell. Then you stupidely hash all coordinates into one hash and provide a hash_value method or friend method. an equality operator and then its usable in a hash map.

You can use a google::sparse_map or something along these lines. I personally used boost::unordered and it was enough in my case.

Then the thing to consider is the presence of AABB into more than one cell. You can store a reference in every cell covered by your AABB, its just something to be aware of in every algorithm : "there is no 1-1 relationship between cell references and AABB." that's all.

good luck