I am keeping up experimenting and finding new breakages.

If you do the following:
1) add a default cube, size 2x2x2
2) add the Remesh modifier like this:

mo = ob.modifiers.new('tmp','REMESH')
mo.mode = 'BLOCKS'
mo.octree_depth = 5
mo.scale = .625
mo.remove_disconnected_pieces = False

3) the cube voxelization is broken...

From my "reverse engineering" the voxel_size is calculated as follows:
voxel_size = max(ob.dimensions) / mo.scale / 2 ** mo.octree_depth

In this case: voxel_size = .10
and 2 / .10 = 20 voxels per side.

After long experimenting, we discover that an even subdivision of object sides breaks the voxelization algorithm.
This breakage is different and indipendent from the previous, that happens in L shaped objects.

This second breakage can be easily solved by changing the way the voxelization domain is defined, while conserving precision and dependability of the results.
It's a low hanging fruit; please, ask me if you want further precisions on that.

Emanuele

I spent all the morning investigating. Now I clearly identified the problem.

The bug is indeed one only.
I attach a screenshot and the related blender file.

The objects on the back line are the original ones.
The objects on the front line are duplicate objects, but with the remesh modifier applied.

All the objects have:

ob.dimensions = 2.5, 1.5, 2.5

The remesh modifier has always the following parameters:

max(ob.dimensions) = 2.5
mo.octree_depth = 3
mo.scale = .625
mo.mode = 'BLOCKS'

So the voxel_size is always:

voxel_size = max(ob.dimensions) / mo.scale / 2 ** mo.octree_depth
voxel_size = .5

The L-shaped objects top surface height grows from left to right in steps of .125 in z direction:
.500, .625, .750, .825...

The remesh modifier fails when any face (internal or on the boundary) of the object contains a voxel center point.
The problem is more evident when the faces are perpendicular to any of the reference system axis.

Let me add something more from the usability point of view:

1) I suggest adding "mo.voxel_size" property to the remesh modifier.
scale and octree_depth can then be calculated like this:

dimension = max(ob.dimensions)
for octree_depth in range(1,16):
scale = dimension / mo.voxel_size / 2 ** octree_depth
if 0.001 < scale < 0.990: break
mo.scale = scale
mo.octree_depth = octree_depth

It would be much easier for the user!

2) I also suggest that the object origin should become the reference point for the voxelization, in other words: one voxel center always lies at the origin.
With current remesh code, when I move the object origin outside the bounding box of the object, something happens that I still cannot understand.

3) It would be wonderful if I could apply the modifier in global coordinates and referring to the global origin.
But I can circumvent this with Python.

Hope this helps!
Best regards,
Emanuele

I can't upload, the blender site replies "missing parameter".
Here are the two files I mentioned:
https://docs.google.com/open?id=0B1pDkwoG1cNqbWRnN2d6QUF1VXc
https://docs.google.com/open?id=0B1pDkwoG1cNqOXIwV3R3Nm5PUFU

Emanuele

Committed potential fix in r46484. I'm still considering the other suggestions made here, leaving open for now.

Original bug reporter has confirmed this as fixed. For now I am not adding the new properties suggested above. For this specific case they can be handled from Python.

Closing, thanks to Emanuele for his patience in getting this resolved.

Thanks go to you Nicholas, it was a pleasure.
Emanuele