performance of collisions of 'voxel' shapes

[kerno]

Hi,
I have some rigid bodies each with collision shape consisting of many cubes (in compound shape) looking like, say, chunks of Minecraft-like ground.
When these objects start to collide I get heavy performance drops (below 1FPS). This happens even when there are only a few (<10) such objects (though they consists of hundreds of cubes, each).
Is this expected or is it likely I'm making some errors in the world configuration? I understand that my scenario implies lots of contact points (each of the cubes generates a contact point) and it's possibly an issue but on the other hand I have only on order of thousands of cubes altogether, all grouped in compound shapes in just a 10-20 objects.
What would be the recommended configuration of the collision dispatcher/broadphase/solver for such scenario?
I'm using bullet 2.87 (bundled by default with libgdx 1.9..

A test scenario (debug draw enabled temporarily): 9 "pillars" ~100x5x5 falling down, colliding on each other and then ground:
While the shapes below are pretty simple (could be single cubes), I cannot optimize the shapes in my 'real' scenario as they are usually are pretty irregular.

stone_forest_falling_scaled.png (258.89 KiB) Viewed 969 times

stone_forest_downed_scaled.png (433.33 KiB) Viewed 969 times

Thanks & regards

[drleviathan]

I've noticed the same performance problem: a medium number of btCompoundShapes, each with a medium number of subshapes all colliding together can slow down the stepSimulation() call. As I recall my example was only about 20 objects, each with about 18 subshapes. It didn't slow down to 2Hz, but the simulation rate was still unacceptably low. I don't have much advice on how to get around it except the following:

(1) Make sure you're using Bullet-2.87 or higher. I think there was an optimization that went in about using an internal hierarchy wrapper by default around the btCompoundShape subshapes. If you're already on 2.87 or higher then I don't think it is going to get much better than what you've got.... if you keep the shapes that complicated.

(2) The simpler the shape the better. Coalesce nearby cubes into larger boxes to make an optimized btCompoundShape with fewer subshapes but the same contour. The code to do this shouldn't be too complicated and I would expect smart algorithms could perform it at run-time. Alternatively you could use something like the V-HACD library, which for shapes made of aligned cubes would be overkiill, I think. In any case, the payoff will be worth any CPU cycles you can spare doing an optimization pass before building the shape.

[kerno]

Hi,
thanks for suggestions. Yes, i'll definitely optimize the shapes. However I would expect the number of shapes to go lower a couple of times only, at least with the naive implementation of optimization that I'll be able to come up with.
Still, it's puzzling for me that with as little cubes as I have (thousands) the performance is so low (I still hope I'm making some error).
For reference, the profiler output below.
Regards

profiler_output.png (103.2 KiB) Viewed 869 times

[drleviathan]

BTW, are you sharing one btBoxShape instance for all of the subshapes? Or are you creating a new instance for each?

I've never not shared and am curious to know how noticeable would be the performance difference between the two cases.

[niad]

My recommendation is to create a new shape type(VoxShape) that stores the voxel grid internally.


This is what I do, and I have no such performance issues, even with many voxels colliding.

[kerno]

There's only a single unit-sized cube shape reused everywhere. Once I make a proper benchmark I can compare any possible effect it can have.

Now the "VoxShape" sounds interesting.

I've found the "Voxels collision" topic on this forum: viewtopic.php?t=11358 but as I understand the last post by Erwin Coumans the compound shape with box shapes is the suggested solution (unless "add each voxel as a btBoxShape directly into the world/broadphase" is not what I actually do).

Before, I had a version where I was making the btBvhTriangleMeshShape for the voxels' visible walls but IIRC the conclusions were consistent with that thread that it's slow and behaves worse than the boxes when other bodies collide at higher velocities. This slowness was pretty visible I as my shapes are both pretty irregular and dynamic (with user being able to add/remove the voxels to existing shapes and separating parts of the shapes produces independent shapes).

There are some possible unrelated issues with my solution that I need time to investigate still but I'd gladly try other approaches as well.
Currently my compound shapes have 3 levels of nesting, first level is a shape for the centre-of-mass transform (changes as cubes are added/removed) the second level shape groups all "chunks" then the last level are shapes for each 16x16x16 "chunk". The depth of this compound shapes may be one potential source of performance issues but I think I'll be able to reduce it to no less than 2 levels (I believe I need at least a shape level for centre of mass transforms and a level/shape for each chunk so as when a single cube is changed somewhere it's not the whole shape with all cubes that I need to rebuild everything).
Also, now I'm creating only the "outer shell" of boxes for a larger shapes if that may matter (the boxes adjacent to empty space).

Can you provide more direction for search on your approach? What classes to extend/links to read?

[niad]

If you can get Erwins method to work well I'd stick with that, the approach I use is more complicated etc

Looking at the profile result you posted, it spends pretty much all of the time in the nearphase callback.

Some of that overhead is because it assumes each node has its own transform(not true for a voxel grid).
With a custom version you could remove much of the overhead in btCompoundCompoundLeafCallback::Process etc.

Does that method generate more than 4 contacts between btCompoundShapes? If so that would seem like an issue.



As for my VoxShape:

The algorithm I use is loosely based on this paper:
Six Degree-of-Freedom Haptic Rendering Using Voxel Sampling http://citeseerx.ist.psu.edu/viewdoc/do ... 1&type=pdf