# Should I always be checking every neighbor when building voxel meshes?

I've been playing around with Unity3d, seeing if I can make a voxel-based engine out of it (a la Castle Story, or Minecraft).

I've dynamically built a mesh from a volume of cubes, and now I'm looking into reducing the number of vertices built into each mesh, as right now, I'm "rendering" vertices and triangles for cubes that are fully hidden within the larger voxel volume.

The simple solution is to check each of the 6 directions for each cube, and only add the face to the mesh if the neighboring voxel in that direction is "empty". Parsing a voxel volume is BigO(N^3), and checking the 6 neighbors keeps it BigO(7*N^3)->BigO(N^3).

The one thing this results in is a lot of redundant calls, as the same voxel will be polled up to 7 times, just to build the mesh.

My question, then, is:

Is there a way to parse a cubic volume (and find which faces have neighbors) with fewer redundant calls? And perhaps more importantly, does it matter (as BigO complexity is the same in both cases)?

Yes, you can make fewer calls. You can give each voxel data containing it's face information. Then go through and set the face data of all the voxels. The simple solid or not situation produces 4 cases:

for each voxel
for each face not set
if thisVoxel is solid
if oppositeVoxel is solid
// both voxels are solid and touching, no faces
set thisFace to zero
set oppositeVoxelFace to zero
else
// this voxel is solid, other is not, this voxel has a face
set thisFace to one
set oppositeVoxelFace to zero
else
if oppositeVoxel is solid
// this voxel is not solid, other is, other has face
set thisFace to zero
set oppositeVoxelFace to one
else
// both voxels are not solid no faces
set thisFace to zero
set oppositeVoxleFace to zero


As you can see, you'll cut out at least one check for the opposite voxel by setting both at the same time. Ensure that you only loop over faces not set. This will reduce the number of checks you need to do.

Additionally, when rebuilding the mesh, you can reuse almost all the face data. When a voxel is added or removed, reset it's face data and the face data of those voxels surrounding it.

You probably realize that this is a trade off. You either get faster execution, or more memory usage. This will take more memory.

• That's a very good point about rebuilding the mesh! Commented Oct 17, 2012 at 15:49

I made some progress in my marching cube implementation where I kept the previous slice of the YZ plane to prevent needing to resample a value twice, but this was to reduce the number of calls when using perlin noise and similar. If your voxel data is stored as an array I doubt there is much you can do to reduce the number of queries.

I suggest you go ahead with the simplest solution that works, and then after its made simply measure how long it really takes to make the mesh. This is not something you will be doing every frame after all, and creating the mesh can be done in a separate thread to prevent stalling the game when you need to recreate a mesh, or load a new section.