Irregular voxel terrain collisions

[jazzprogramming]

Hi,

I'm working on a low poly terrain and would like to add collisions between the terrain and the player capsule.

In the example image, highlighted in red is a cell (a convex polyhedron) and so are the other ones delimited by the grey borders. Potentially, there can be many cells (which make up the terrain), from a few hundred up to 20-30 thousands. The MeshShape class seems well suited for modelling the terrain part.

The problem is, the cells can be deleted, modified or new ones inserted and so changing the underlying triangles.
I'm thinking about extending AABBTreeBuilder to support insertions, deletions and updates (and rebalancing I guess) and caching it in MeshShape as in to only update the affected triangles when a cell changes.
But I need your help on this.

What do you think? Would that work?
What would be the best way to solve this in your opinion, performance wise?

Thank you for your thoughts.

[jrouwe]

The MeshShape really wasn't made to be updated at run time.

I would probably divide the terrain in a regular grid and create a StaticCompoundShape per tile consisting of the polyhedrons (pick e.g. the center of mass of the shape to classify which tile it is in). StaticCompoundShapes are fairly cheap to create at run-time, so if the terrain changes you can create a new StaticCompoundShape for the affected tile. If the terrain changes very often, you can use a MutableCompoundShape instead of a StaticCompoundShape but then you're trading rebuild speed for query performance. The size of the grid is something to determine experimentally by profiling, you want a balance between the query cost (more shapes per tile is better) and rebuild time (less shapes per tile is better).

[jazzprogramming]

I think I understand the broad picture of what you said, but I'm trying to wrap my head around the details.

This is what I understood so far:
Let's say, we have a terrain block (a big cube containing hundreds of cells) that is further broken down, just for a concrete example, into a 4x4x4 cubic grid. Then we have 64 3D tiles (little cubes) in the big cube and so each cell is assigned to one of the tiles by its centroid position, resulting in 64 static or mutable compound shapes, one for each tile.
So now, when a cell changes, only the shape of the tile containing that cell (and any shapes of affected neighbor tiles) needs to be replaced/updated instead of the whole big cube.

Here is the part I don't understand:
What shape types do the compound shapes contain?

As the cells are made up of faces and each face is a list of triangles, I can't find anything better than a MeshShape to represent them in Jolt. Only two ways of doing this come to mind:
I can either create a MeshShape for each cell, resulting in a lot of MeshShapes and duplicate triangles, or a MeshShape for each tile, containing only the visible triangles of the cells making up that tile.
In the latter case it seems the compound shapes are not really needed after all. The big cube would be split into 64 MeshShapes, one for each tile, and each MeshShape would be recreated when any of its cells changed.

Would this work or have I misunderstood your advice?
And if so, can you please explain in more detail what you had in mind, when you have the time?

Thank you.

[jrouwe]

What shape types do the compound shapes contain?

You mentioned that your shapes were 'a convex polyhedron' so I assumed that the terrain was built out of these shapes and that is what I proposed to put in the StaticCompoundShape.

If you want to do hidden surface removal then you would indeed need to create a MeshShape per cube, but then obviously you're creating (smaller) MeshShapes on the fly. I can't predict if that is going to be fast enough. Some effort was made to make the creation faster, but it was always meant to be an offline process as it tries to optimize the resulting shape for a balance between speed and memory usage and it bit packs all data in a single memory block.

Doing the hidden surface removal (if you start with convex polyhedrons) may also not be faster at all, as for many collision tests 1 triangle vs a shape is the same code as 1 convex polyhedron vs a shape (the latter would probably be a little bit slower but not much). Using compounds of polyhedrons does have 1 disadvantage: If your simulated bodies move fast enough to tunnel through more than half of the polyhedron, they may be pushed inside solid rather than out (but you can solve that by setting the motion quality to LinearCast).

Finally, you can also create your own custom shape to wrap your data structure (but this is quite a bit of work).

[jazzprogramming]

Yeah, maybe I should have mentioned this right from the start to give you a better context.
The polyhedrons are 3D Voronoi cells, if you're familiar with Voronoi diagrams. So changing a seed's position changes the shape of its cell (its volume) and its neighboring cells, resulting in the strange requirements.

Anyway, I think I should have enough information now to start experimenting and find out what works best and I'd rather not take up any more of your time with this issue.

Thank you for helping me out with my questions,
Răzvan