Efficient collision detection for destructible environment

[Ragzouken]

Hi, as part of a University group project to make a computer game, we're trying to use bullet to perform efficient collision detection of a destructible environment; a tower composed of discrete non-cube blocks. It's roughly like Minecraft polar co-ordinates (diagrams/screenshots can be found at the end of the post).

Up until now, for the blocks we've been using a btDiscreteDynamicsWorld and adding a rigid body per block with btConvexShape defined by the 8 points of a block, and stepping the dynamicsWorld simulation once ever 1/100th of a second. This works as far as offering us the information we need to implement the gameplay, but becomes incredibly slow for anything more than a small number of blocks.

What we actually need from the world is:

• Being able to check if an oriented cylinder/capsule/something is colliding with anything (i.e if a rocket has hit something)
• Being able to check if a vertical cylinder/capsule/something is colliding with static floor geometry or any blocks of the tower (i.e we need to be able to do a kinematic character controller)
• Being able to determine which tower blocks are colliding/contained-within a sphere (i.e we need to know which blocks to remove from the tower when an explosion happens)
• Being able to add/remove blocks from the tower's physics representation quite frequently (i.e for removing blocks after explosions, and regenerating them later)
• Hopefully support this for around 65,000 blocks

Should we be using a btCollisionWorld instead of a btDynamicsWorld? Should we be using RigidBodies or something else?

I've done some reading around, and an idea came up that we could batch chunks of blocks up into btBvhTriangleMeshShapes and rebuild the relevant batches when blocks change. This is essentially what we're doing on the graphics side, so it seems sensible, but alone it doesn't seem to support working out which blocks to remove during an explosion because it seems that it only tell you which chunks are colliding with an explosion rather than which blocks specifically.

Is btBvhTriangleMeshShape a sensible direction to go in at all? Does btBvhTriangleMeshShape actually have a mechanism for detecting collision of subshapes within it that I haven't realised? If not, could some auxillary collision shapes/checking be performed on the fly for more fine grained information, but that would not have a negative performance benefit when no explosions collisions are being calculated?

We'd all be really grateful for any advice on what we may be doing naively, if this is possible to do efficiently within bullet, and any pointers in whatever direction may be needed to get this to work.

Thanks!

Diagrams
This is a diagram of a cross-section of our tower:


Here are some screen shots of the tower from a first person perspective, with the btConvexHullShapes drawn over the blocks:
http://you.mongle.me/tower/screenshots/010.png
http://you.mongle.me/tower/screenshots/011.png
http://you.mongle.me/tower/screenshots/012.png

Eventually we'd like to get the tower looking like this:
http://you.mongle.me/tower/circles/9,18 ... ,72,72.png
Where every vertical slice has the same layout, every ring is composed of the same shape (but sometimes that shape has 9 faces), and going from the centre each ring has either the same number or twice as many segments as the last.

[Karrok]

btCollisionWorld only does the collision checking. So unless you mean to implement all the collision handling yourself you should just stick with using the Bullet Dynamics Lib for that.

If you do have a world where you only require the low level information on collisions, then btCollisionWorld is sufficient.
However, a btCollisionWorld does not have gravity, constraints (like hinges) and does not solve collisions for you, so keep that in mind.

[Johan Gidlund]

I am not familiar with the details of Bullet but from a general point of view you should try to use one rigid body with a list of shapes. Having a rigid body per block is insane and will never work for the amount of pieces you are targeting.
For the large amount of pieces you are targeting it is probably also wise to have some kind of bounding volume tree on top of the list to make queries for shapes faster.

[Ragzouken]

Thanks for the advice guys, it did prove somewhat useful. Maybe this information about how we have chosen to solve the problem will be interesting and/or useful to people reading

The biggest problem was firstly that we were not performance testing in Release mode! Rookie error!

We have gone for the BvhTriangleMesh approach, with the environment split up into equally sized chunks that can be changed independently (trying to balance the benefit of the bvh against the time taken to rebuild it when the terrain changes -- I think I am actually being quite dumb about it at the moment, we rebuild the entire bvh mesh when the blocks change, but I see it has a method to refit to new triangles, so I will try that out at some point)

For actually determining which blocks to destroy we've implemented a bespoke collision algorithm, since we can make better assumptions than bullet about our structure.

For anyone interested, here is a prototype of the collision checking for blocks: