I wonder if there's a way to do something similar to Rectangular Surface Parameterization[1] with voxels. It would allow you to get pretty even-volumed voxels, and also simplify vertex identification (same three coordinates, nonlinear connection).

[1]: https://www.cs.cmu.edu/~kmcrane/Projects/RectangularSurfaceP...