[Bullet] Performance issues when adding lot of convex shapes to a RigidBody

[Maveyyl]

Godot version:
Godot_v3.2.3-rc3_win64

OS/device including version:
W10

Issue description:
I try to do a 3D voxel blocky game. Each grid of voxel is a rigidbody, each rigidbody is capable to move and collide with others. As a result I can't use concave shapes or height maps and I'm forced to create a lot of box shapes.

In a baby case scenario, I have 16x16x16 blocks per chunk, and 2x2x2 chunks. If I randomly add blocks 75% of the time I get an average of 600 shapes per chunks (optimized by merging boxes). It takes 13 seconds to populate everything. And then it takes 4 seconds to add a block in one of these chunks.

I've tried to use the CollisionObject API and the PhysicsServer API and both have this problem. The fastest solution so far is to have one shape owner per shape.

Once the calculations are done the engine isn't particularly struggling. So I figured there must be something wrong with the shape addition algorithms.

I'm open to suggestion if there's something better to do.

Thanks!

[Calinou]

This is most likely fixed by #39726 which has been merged in the master branch. (It won't be cherry-picked to the 3.2 branch due to the complexity of doing so, though.)

Also, are you sure you want to have that many RigidBodies? It could result in pathological performance if all of them are made active at the same time (e.g. by a large explosion).

[Zireael07]

Why are you making each voxel a separate rigidbody?! If you are using voxels, you shouldn't need complex physics, especially not for voxels you can't interact with (obstructed by other voxels, for example)
EDIT: Ninja'd by Calinou :P

[Maveyyl]

Sorry @Calinou and @Zireael07 if I am not clear, I don't have that many rigidbodies I have one rigidbody with many many many shapes.

Minecraft's world is basically a bunch of 16x16x256 chunks that are static bodies with concave shapes.

Now imagine I want to make a minecraft game with planets, asteroids and spaceships that can move, that all have their independent grid and chunk system, but the chunks and voxels are immobile toward each others in their parent body. So one independent entity is one rigidbody, and its collision shape formed by the voxels can't be a concave shape since it's not a static body, so it is divided in many many many convex shapes. I can't get a rigidbody per chunk either I'd have to maintain them stuck together all the time and I'm not sure if it's even possible.

The time necessary to add so a shape in one unique rigidbody seems proportional to how many shapes it has already, and since I have so many shapes to add it is extremely long and inefficient.

I guess I should test with the latest build then, thanks @Calinou :)

[Maveyyl]

I haven't succeeded in testing with the latest build, however by reading what the fix is about, doesn't seem to be of any help for my problem.

Note: the problem only seems to be happening with bullet physics, not godot physics. But then removing the shapes and updating makes the whole game freeze.

[Zireael07]

@Maveyyl: You saying that the problem is only with Bullet further points to the problem that #39726 fixes.

I can't get a rigidbody per chunk either I'd have to maintain them stuck together all the time and I'm not sure if it's even possible.

I don't understand what you wanted to say.

At any rate, since your bodies have to be convex, for physics purposes you could make a simplified mesh (take just the outlying vertices of the body). In 2D, Godot has a function to make a convex hull of points, I am not sure if there's a 3D equivalent? If there is none, you could write your own, or use the 2D version and 'extrude' it so to speak in the 3rd dimension (I am using a very similar trick to make a 3d mesh by 'extruding' a 2d polygon). That way, your physics body would only have a single convex shape instead of 600 shapes

Also again, why do you add shapes for voxels obstructed by others? if you just took the outlying layers - top, bottom, left, right, front, back - I imagine you would cut on the number of shapes by an order of magnitude, you don't need the rest since nothing will interact with those anyway because the other shapes will prevent interactions.

[Maveyyl]

@Zireael07

There's a function to generate a convex shape out of a concave shape, but that's really against the gameplay I want. Collisions no longer are accurate and removing/adding blocks becomes nonsensical.

I don't understand what you wanted to say.

Instead of having all chunks compute their shapes and give them to the master rigidbody, they are all rigidbody themselves, that would limit the amount of shapes per rigidbody to a small number and would speed up loading and updates (that's just a theory tho). The problem is the chunks are not supposed to move from each others, and I'm not sure it's doable in the physics engine to have rigidbodies that act as if they were stuck.

you don't need the rest since nothing will interact with those anyway because the other shapes will prevent interactions.

Hollow structures are part of the gameplay I want, I don't want to be making assumptions that would limit the gameplay tremendously. And that's really not an assumption any voxel game makes.

[briansemrau]

I did some performance testing (master 241e709, Bullet physics) and I can add 2000 CollisionShape3D nodes (each with a BoxShape3D) to one RigidBody3D in ~200ms, so either I'm missing something or I don't think this is where your performance is being bottlenecked.

I'm not sure it's doable in the physics engine to have rigidbodies that act as if they were stuck.

The only way to do this is using a PinJoint (if it works how I think it does), but I think this would produce undesirable effects such as wobbly structures and less robust physics. I'm sure someone else can speak more confidently on this though. Regardless, I don't think this is the best approach.

As for the talk about reducing geometry, I believe this diagram might help explain different methods of reducing shape count.

A:
Every block has a box shape. All the boxes on the inside are not really necessary and they add more performance cost when calculating collisions.

B:
Blocks that are not touching the outside are culled because they are not necessary.

C:

Also again, why do you add shapes for voxels obstructed by others? if you just took the outlying layers - top, bottom, left, right, front, back ...

I believe this is more inline with what Zireael07 was explaining. Instead of boxes, we add only the outward faces of the set of blocks.

D: This was not mentioned, but if your voxels are small (Look up the unreleased game Teardown) you might want to reduce jagged edges for smoother collisions when sliding. This shows what you might get by using the Marching Cubes method (marching squares in 2D) to figure out what geometry to add, where.

I personally believe C and D are the best options, depending on what you want.

[Maveyyl]

Thanks for your reply @briansemrau

I did some performance testing (master 241e709, Bullet physics) and I can add 2000 CollisionShape3D nodes (each with a BoxShape3D) to one RigidBody3D in ~200ms, so either I'm missing something or I don't think this is where your performance is being bottlenecked.

I have the problem in the official build. I tried master but couldn't make a baby project work with unofficial builds, they were too unstable and crashy. I was planning to try to compile it myself, but now you proved that @Zireael07 was right about the optimization present in master. :) I'll need to be patient for 4.0 but at least it gives me reasons to keep going.

The only way to do this is using a PinJoint

Good point, will give it a try and see if it yield wonky physics.

B:

That's actually a bad idea and probably inefficient to compute. But maybe that's what zireal meant and I didn't understand it that way. I do face culling for meshing though.

What I use is a greedy merging algorithm. In the example you're showing I'd fuse the 8 leftmost squares into a big quad, the group of 4 on the right into one quad. In the one I'd only have 3 shapes while B has 10. I have performances issues when you just generate lotta cubes that don't touch each others. A world generated à la minecraft wouldn't generate too many shapes but as soon as the player makes constructions i'd go very bad.

C:

That's a concave shape D:

D:

Marching cubes is cool, it could allow me to generate bigger convex shapes. But besides natural terrain it'd not benefit other types of voxels.