Voxel terrain collision detection with AABBs

I'm working on implementing collision detection on voxel terrain (Like Minecraft) with AABBS.

Right now, I have it so I can tell if a point is within a voxel or not, I do this by having a 2D byte array of active voxels. If a byte at any index is 0, the voxel is air. If its 1, its solid. Right now I'm just testing to see if the voxel at the player's position vector is solid or not.

My problem is, I now wish to implement AABBs to get more precise detection, but I have no idea how to do it without checking if all the voxels within the AABB are solid. That might now be a problem for games like Minecraft, where there would only have to be about 1 extra voxel check, but the voxels in my game are much smaller (The player's dimensions are about 4x10x4), so I would have to check a lot of voxels.

Ive seen one or two other people having a issue similar, but I didn't find the answers they got clear enough, and so I come here asking for your help.

Thanks.

Answer

Checking all the voxels should not be that bad - modern CPUs can often do brute force processing faster than 'clever' solutions because those clever solutions often contain a lot of branching and jumping around in memory which is very costly compared to simple arithmetic or iterating over an array.

If youre using a low level enough language, you can try optimizing the brute force method to be cache friendly (linear access order, get rid of indirection, dont store unneeded 'cold' data interleaved with 'hot' data you need).

Other than that, I can suggest some optimizations:

1. 
   

   Instead of checking the entire AABB volume for intersections, only check for intersections against the AABB faces, and only in the directions where the AABB is moving (dot product of face normal and velocity direction > 0). Add multiple iterations to the physics to prevent the AABB from moving more than a single voxel-width per frame so it wont tunnel through stuff.

   
   


2. 
   

   Only check those face intersections when the particular face has transitioned to a different 2 dimensional plane of voxels on its axis (since only then will it intersect a different set of voxels than last frame)

   
   
   


3. 
   

   If you have massive AABBs, you can add a hierarchial data structure like an octree to quickly skip checking large empty areas of voxels (usually only the bottom part of the AABB will be colliding and rest will be air, so skipping all that air would be a speedup)

   
   

You can go much further by caching some information about the collisions but it will start affecting your ability to easily implement other game features that depend on collision checking so Im not going to suggest anything. Go with the brute force approach if performance is not a problem - its the least restricting one IMO.