Collision filtering techniques

Question

I was wondering what efficient techniques are out there for mapping collision filtering between various bodies, sub-bodies, and so forth.
I'm working on a physics engine and I need ways for a user to easily specify some complex relationships between bodies (what should/shouldn't collide), and ways to organize that filtering data so that it's easily attainable / memory-efficient. One part of my engine that could also be taken advantage is what my 'bodies' actually are. They're like folders that you can put convex shapes, and other bodies in as to organize the parts of a complex rigid body.

I'm familiar with the simple idea of having different layers of 2D bodies, but this is not sufficient for more complex mapping:

EXAMPLE:
(Think of having sub-bodies of a body, such as limbs, collide with each other by placing them on the same layer, and then wanting to only have the limbs collide with the ground but not the body)
- I don't see how a user could accomplish the above example with just a bunch of different layers... The body must collide with the ground and therefore be in the same layer, but the limbs must also be in the same layer as the ground, causing unwanted collision between the body and the limbs.

This can be solved with a multidimensional layer setup, but I would probably end up just creating more and more layers to the point where the simplicity and efficiency of layer filtering would be gone.

Are there any more complex filtering techniques that would solve complex situations such as the example? And even more possibly complex situations?

Answer 1

First you'll want to do some sort of spatial partitioning like a grid or quad tree. After that you should do like bummzack said and use bitwise operations. Assuming you are already doing spatial partitioning this is how I'd recommend going about filtering.

Step 1

Create an enumeration of collision categories. We will call this Category. This will be (up to) 32 named constants of type integer. Each of these values needs to be a power of two (e.g., 0, 1, 2, 4, 8 and so on). Assign the name None to 0, you can give the rest whatever names suit your needs. Using your example Legs could be 1, Arms 2 and Ground 4. Aside from None the names are completely arbitrary.

Step 2

Any body that can collide with another body now needs two properties. If you have some sort of base Entity class that would be the place to add these.

1. collidesWith
2. collisionCategories

Both of these properties will be populated with values from Category. collidesWith indicates the categories the current body will collide with. collisionCategories is the list of categories the current body belongs to. You can assign multiple categories using bitwise operations. Again, using your example:

// Arms collide with other arms and legs
// See [http://en.wikipedia.org/wiki/Bitwise_operation#OR][2]
// for more in-depth discussion
arm.collidesWith = Category.Arms | Category.Legs;
arm.collisionCategories = Category.Arms;

// Legs collide with arms, other legs and the ground
leg.collidesWith = Category.Arms | Category.Legs | Category.Ground;
leg.collisionCategories = Category.Leg;

// The ground collides with nothing since we won't 
// be directly testing it
ground.collidesWith = Category.None;
ground.collisionCategories = Category.Ground;

Step 3

This is where we do the actual filtering. In your collision handling code you will, at some point, be looping over a list of bodies that are colliding or potentially colliding with the current body. This is where you apply the bitwise filter. It works like this:

if ((other.collisionCategories & this.collidesWith) != Category.None)
{
    // Bodies are colliding
    // Do collision code
}
else
{
    // Bodies are not colliding
    // Filtered
}

The above is asking, "Does this other object belong to any of the categories my body collides with?" The Wikipedia article on bitwise AND will explain this with more detail.

---

The benefits of this approach are that bitwise operations are really, really fast and we can pack a lot of information into a small bit of memory. It's also very flexible.

The downside is that it's not the most straightforward, easy to grasp approach (but it's not really all that hard either). You could also run into problems if you require more than 32 collision categories but that seems unlikely.

Answer 2

You could use Octrees

http://en.wikipedia.org/wiki/Octree

Have each layer as a different depth into the screen in the octree.

Answer 3

Back in the day, I started using Box2D before they had any kind of collision culling. Used to be (on core 2 duo 2.4Ghz), I could have a maximum of 50 colliding boxes before the simulation started lagging severely due to the lack of culling.

I modified the Box2D source to include axis aligned bounding boxes, which allowed me to get round-abouts 500 colliding boxes before it started lagging, and went on to add a Quad Tree (seeing as how this is 2D, and not 3D, octrees are pointless). After the Quad Tree implementation, I was able to get about 1000 colliding boxes before is started lagging. Keep in mind, these boxes were all sitting on top of each other, actively colliding and applying forces upon one another, slowly stabilizing.

I think I also added some logic to prevent sleeping boxes to from colliding with other boxes... therefore only active (moving) boxes could collide with non-moving boxes. This way, sleeping boxes wouldn't get tested against other sleeping boxes (if neither of them are moving, then how can they collide?).

Since then, Box2D has implemented all of those features... Sadly, I never submitted those changes, so I can't claim anything for that.

All in all, it was a pretty educational experience.

TLDR;

• Cull body-body collisions based on range or axis aligned bounding boxes.
• Cull body-body collisions if both are sleeping.
• Cull large counts of bodies by implementing a quad tree.