Okay, so the small mesh is a cube of whatever unit-size you're using to measure volume, right? And you'll basically check a 3D grid of these cubes against the object you're considering?

Here's a bit of a thought: You have a 3D-array of bits (inside and outside), all set to "outside" (0 or 1, doesn't really matter). Go through the vertices of the big model, and at each one find the nearest point in the array behind the normal. Set it to "inside", and put the indices of each of those "inside" bits in a list. For the next stage you'll repeatedly go through the list, and each point will run a function for each of its "children", where each child is an "outside" bit adjacent to this point, that goes through all the polygons in the big mesh and sees if any of them separate a child from its parent. If none separate the child from its parent, the child is set to "inside" and added to the list. When each "parent" is done, it is removed from the list. This is repeated until the list is empty -- that is, no more points have access to empty points.

You now have a volumetric representation of the mesh (which most be closed, obviously, for this to work). For each bit you add, also increase a counter by 1 to get instant access to the volume of the mesh.

Something like a sword with polygons pressed up against each other could be trouble -- you could end up with an outside bit being called "inside", and that means everything will be considered inside. To prevent this, for each bit you set to "inside" in the first stage, first make sure it isn't right in front of the normal of any polygons in the mesh.

I hope that makes sense, and I haven't overlooked something silly

Jibb