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

Question

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)?

Answer 1

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.

Answer 2

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.