Spatial Data Structures for moving objects?

Question

I was wondering what is the best data structure to deal with a lot of moving objects(spheres, triangles, boxes, points, etc)? I'm trying to answer two questions, Nearest Neighbor and Collsion detection.

I do realize that traditionally, data structures like R trees are used for nearest neighbor queries and Oct/Kd/BSP are used for collision detection problems dealing with static objects, or with very few moving objects.

I'm just hoping that there is something else out there that is better.

I appreciate all the help.

Answer 1

1. You can partition the scene in an octree and utilize scene coherence. Your moving object that you are testing is going to be in a specific node of the tree for a specific amount of frames depending on its speed. This means you can assume it will be in the node and therefore quickly cut out a lot of objects that are not in the node. Of course the tricky bit is when your object is close to the edge of your partition, you would have to make sure you update which node the object is in.

2. A moving object has a direction and a speed. You can easily divide the scene in two sections by using a perpendicular division from your objects direction of movement. Any object on the wrong side of this division do not need to be checked. Of course compensate for the other object's velocity. So if the other object is reasonable slow, you can easily cut it out from further checks.

3. Always simplify whatever shape you are testing with something like an axis aligned bounding box. An initial collision test

4. You can take the distance between your object and another moving object plus the velocities. If the other moving object is moving in the same general direction at a faster velocity, you can eliminate it from your check.

5. There are many other optimizations depending on the object's shape. Circles or squares or more complex shapes all have specific optimizations you can do while moving.

6. Assuming some objects do stop or can stop moving, you can keep track of objects that stop. these objects can than be treated like static objects and therefore the checks are faster and you can apply all the static optimization techniques to them.

7. I know of more but can't think of any off the top of my head. Haven't done this in a while.

Now of course this depends on how you are doing the collision detection. Are you incrementally updating the object's position based on velocity and checking as though it is static. Or are you compensating for velocity by extruding the shape and figuring out initial collision points. The former needs a small step for fast moving object. The latter is more complicated and costly but gives better results. Also if you are going to have rotating objects then things get a little more tricky.

Answer 2

Bounding Spheres probably would help you with many moving objects; you calculate the radius squared of the object, and track it from it's center. If the squared distance between the centers of two objects is less than the sum of the squared radii of the two objects, then you have a potential collision. Everything done with squared distances; no square roots.

You can sort nearest neighbors by the minimum squared distance between your objects. Collision detection can get complex, of course, and with non-spherically shaped objects, Bounding Spheres won't necessarily get you collision information, but it can prune your tree of objects you need to compare for collision quite nicely.

You'll need, of course, to track the CENTER of your object; and ideally you'd like for each object to be rigid, to avoid having to recalculate bounding sphere sizes (although the recalculation isn't particularly tough, particularly if you use a tree of rigid objects each with their own bounding sphere for the objects which are non-rigid; but it gets complicated).

Basically, to answer your question about data structures, you can keep all of your objects in a master array; I'd have a set of "region" arrays which consist of references to the objects in the master array that you can sort the objects into quickly based upon their cartesian coordinates; the "region' arrays should have an overlap defined of at least 2x the largest object radius in your master object array (if that's feasible; a question of object bounding sphere scaling vs. number of objects obviously comes up).

Once you've got that, you can do a quick collision test by comparing distances of all objects within a region to each other; again, this is where region definition becomes important, because you're doing a significant tradeoff of number of regions to number of comparisons. However, it's a little simpler just because your distance comparisons come down to simple subtractions (and abs() operations, of course).

Of course, then you have to do actual collision detection between your non-spherical objects, and that can be non-trivial, but you've reduced the number of potential comparisons very dramatically at that point.

Basically, it's a two-tiered system; the first is the region array, whereby you do a rough sort on your scene. Second, you have your intra-region distance comparison; wherein you're going to do your basic collision detection and collision flagging on the objects which have collided.

There probably is room in this sort of algorithm for use of trees in dynamic region determination to even out your region sizes to assure that your region size doesn't grow too rapidly with "crowded" regions; that sort of thing, though, is non-trivial, because with objects of differing sizes, your sort on density becomes... complex, to say the least.

Answer 3

One interesting method for doing collision detection is to use axially aligned bounding boxes (AABB's) organised within a special octree structure. The AABB's help because they make the coarse collision computations very quick to do because you only need to perform up to 6 comparisons.

There are a couple of tricks you should use with the octree structure:

1) The bounding area which a node occupies should be twice as large as it would be for a normal octree (where the octree partitions the space without overlap). As each node should overlap half of the area of its adjacent nodes. Since the AABB can belong to only one node this extra size and overlap allows it to remain in the one node for a longer period of time.

2) Also in each node - and probably in each level of the hierarchy - you keep links to the node's neighbours. This will involve a lot of extra code but it will allow you to move elements between nodes in close to O(1) time rather than O(2logn) time.

If the octree is taking up too much memory you could change it to use a sparse octree structure, only keeping the tree for the parts of the game world that actually contained entities. However this would mean that you'd have to perform more computations for each frame when entities move through the world.

Some other ideas you might want to try instead of an octree is to use a kd-tree (I believe that's the correct name), or use AABB's to build the structure from the bottom up.

KD trees (from memory) partition the space using axially aligned planes, thus they are a good fit for use with AABB.

The other idea is instead of forcing the octree generation from the top down (starting with a box envoloping the whole world), you build it up from the base entities and construct bigger AABB's that grow until the biggest one encompasses the whole world. Though I'm unsure of how it would work with many fast moving entities.

(It's been a while since I've done this kind of spatial game development coding.)

Answer 4

RDC may be of use, especially if your objects are sparse (not many intersections).