How do I determine which voxels to test for collision against the player?

Question

I've implemented Minkowski subtraction to test whether (and where) two AABBs collide, independent of framerate/time-step, in my Minecraft-like game.

But since there may be tens of thousands of voxels, I'm realizing I can't just test everyone of them. Is there an alternative to just scanning for nearby voxels? I worry that if I just do collision for voxels within a fixed range, then I've undone the framerate independence that I had sought.

Answer 1

First of all, minkowski sum is overkill for this, since the blocks are static. Go a bit simpler and use swept AABB.

Secondly if you can, break the world into chunks, then only check blocks inside chunks the player collides with. This reduces the amount of blocks you need to check from hundreds of thousands to a couple thousand (if we assume a chunk size of 10 x 100 x 10, then it' around 90000). Chunks are basically big blocks and if the player doesn't go very fast (very fast in this context means faster, than 1 chunk per frame), then you only need to check the chunk the player is standing in and the 8 neighbouring ones.

Answer 2

This post is a bit old, but it got bumped, so I'll followup with the solution I implemented.

I used the players velocity (multiplied by the framerate) to compute a simple 3D cartesian range of voxels that the player could collide with.

When moving diagonally, it tests more voxels than is required (as crudely sketched below):

However, at typical FPS & velocity, only about a dozen voxels are tested per frame (regardless of the size of the world). So I'm quite happy with it.

Seems so obvious now; can't believe I asked, lol.