Voxel collider

[uben0]

I am creating a voxel game (like Minecraft), where the terrain is split into chunks of 32×32×32 blocks.

On my previous iteration of the project, I went with a home-made physic, but I spent too much time, only to obtain a buggy result. This time I want to use Avian.

I see two ways of adding physics to the game using Avian:

Cuboid colliders

First approach, is to spawn a cuboid collider for each block.

Optimization is done by:

• skipping unreachable block (when completely surrounded by others)
• cover several blocks with a single cuboid when possible

Advantages:

• simple to implement
• good physics

Problems:

• huge number of colliders (even with optimization)
• difficult to update colliders (when the terrain is altered)

Custom collider

Second approach is to create a custom collider.

Advantages:

• at most one collider per chunk (none when chunk is all air)
• could be very efficient to detect collisions (indexed nature of voxel)

Problems:

• implementing PointQuerry for a voxel shape could be very tricky
• the collider has to live behind an Arc<dyn Shape>

In order to have a custom collider, the provided type must implement Shape which requires PointQuery which requires to project an arbitrary point onto the surface of the shape. If my understanding is correct, it should be the shortest projection, in other words, the closest point.

For a voxel shape, the naïve way of finding the closest point, is to iterate over all blocks of the voxel and keep the minimum. It will return a correct result, but will have terrible performances. I got deep into this problem and I explore different algorithms. The conclusion is that there are no good optimization for it without sacrificing correctness. (Or is it? I hope to be proven wrong on that.) If I allow myself to return, sometime, points that are not the closest, then I have very efficient algorithm for it.

TL;DR

• Do I absolutely need to compute the nearest point when implementing PointQuerry? Or can I return an approximate result when there are no blocks near the provided point?

• What are the different options to implement a custom collider in Avian? Maybe providing an Arc<dyn Shape> is not the only way? Could I write a plugin that apply terrain physic without using colliders?