Sign in to follow this  

Collision Layers

This topic is 3775 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

For my physics engine, I am going to add support for different "layers" of collision. This could be used to simplify collision detection in a game such as to have certain projectiles collide with the player but not the enemies, or to have certain objects not collide with each other, like the player and vegitation. Each layer will have a boolean parameter which specifies whether or not two objects of that same layer collide (if there are internal collisions). This could be used for particle systems where internal collision aren't wanted but collision with the world and other objects is allowed. This speeds up collision detection drastically because one can do many quick rejection tests and only callback collisions that are important to gameplay. ---------------------------------------- My question is this - what do you think would be the best way to implement this system? I know that I need some sort of adjacency graph whose vertices are the layers and whose edges denote that layers collide with each other. I think a hash map might be a good data structure to use for this. The problems comes in the API representation and it's subsequent integration with the underlying system. When a user creates an object, should he set what layer it is in right then and there by calling something like setCollisionLayer(CollisionLayer layer), or should the object have a default collision layer, and then the user must add/remove that object from whatever layer it is in such that the object doesn't know that it is in a layer, only the layer knows. Essentially, should collision layers have objects or should objects have collision layers? The former is easier to implement and to use at runtime, but the later is more correct from an OO programming design standpoint and allows an object to be in more than one layer, which adds flexibility. ---------------------------------------- On top of these problems, what about the way in which this is integrated into the broadphase collision detection system? Should I for every pair of objects test to see if their layers collide by querying the hash map and then if they do, perform the necessary narrow-phase collision detection, or should I have separate spatial partioning data structures for each completely connected subgraph of the layer adjacency graph, such as to avoid this step? This might be faster in some ways, but would require much more memory usage as well as requiring some objects to be repositioned in their data structure (octree, spatial hash, etc.) more than once. My main worry is that doing 10000+ hash map contains(layer,layer) queries a frame could get expensive, despite the fact that they are O(1). Which way do you think would be better to do this? new ideas are also welcome.

Share this post


Link to post
Share on other sites
Quote:
When a user creates an object, should he set what layer it is in right then and there by calling something like setCollisionLayer(CollisionLayer layer), or should the object have a default collision layer, and then the user must add/remove that object from whatever layer it is in such that the object doesn't know that it is in a layer, only the layer knows. Essentially, should collision layers have objects or should objects have collision layers?


Can an object be in more than one layer at the same time? If not, then the solution is somewhat trivial.

You have two sets: Objects you're testing (ST), and objects you're testing against (SA).

Unlike usual collision detection, your ST is not a part of SA.

Your collision detection would then look something like this:


class Object
{
// test this object against all objects in 'against'
// append collisions into 'result'
void test( Layer * against, CollisionEvents *result )
{
if ( against == l && !l->internal_collision_allowed ) {
// we do not collide with our own layer
return;
}
// do collision test of this against all in 'against'
}
Layer *l;
}



The CollisionEvents can then be, if needed, keyed by object pairs:

class CollisionEvents {
// o1, o2, collision time
std::map< std::pair< Object *, Object * >, float> collisions;
}



To perform collision detection, you then test every in-world object against all layers (n * m * O(collision detection) ) complexity.

You can also structure the CollisionEvents differently. You can treat each layer separately, include layer information along with events, or similar.

The concern of 10000 map queries becomes meaningless - if you have 10,000 collision each frame you're in trouble anyway, since callbacks will become the problem.

The overhead of this approach is two pointers per object (1 in object, 1 in layer - you need bi-directional lookup, so that you can perform the test in layer).

Share this post


Link to post
Share on other sites
I think that ODE (Open Dynamics Engine, an open source physics engine) has a collision system that handles these issues nicely.

It allows the user to create collision spaces and then add objects to these spaces. The collision spaces can use different types of spatial partitioning. ODE has a multiresolution hash table, a quadtree (useful for heightmaps), and a type of space that doesn't do any culling. Spaces can be contained in other spaces, and they compute their AABB based on the objects inside of them. There are functions to collide all the objects within a space, to collide the objects in one space against the objects in another, and to collide two non-space objects against each other. The functions that collide spaces call a callback function when they find a pair that might be colliding.

Each object can be contained in at most one space, and the object keeps a reference to that space while the space has references to all the objects it contains. This allows for cleanup when objects (including spaces) are removed and moved between spaces.

In addition, every object has two 32 bit words that are used as another check to see if two objects can collide. The words are called category and collide, and some bitwise operations are done to check that at least one object's collide word contains a set bit that corresponds with a set category bit in the other. This mechanism doesn't replace the broad-phase collision detection, but it allows for some additional fine tuning without the memory cost of another spatial data structure. It's also probably useful to put all the spaces within one master space, and then recursively do the collision checking. Each space would correspond to one of your layers, and the category and collide words can be set on the spaces to control which collisions are allowed.

It's an extremely flexible and efficient system. For some particular uses, some parts of the system are probably redundant or unnecessary, but they allow for tradeoffs between creating additional structures and using flags to detect pairs that are not allowed to collide when all the objects are put in one structure.

Share this post


Link to post
Share on other sites

This topic is 3775 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this