Subdividing a mesh into convex subvolumes and tagging faces This question has two parts


Is there an automatic way in blender (perhaps an addon) of subdividing a mesh into convex subvolumes
Given that a subdivision has been made, is it possible to associate a front and back subvolume with a face, or at least mark the faces that faces two subvolumes? In the figure, I have done (1) manually, and I want to give the selected faces a tag, so I know that these faces actually face another subvolume (this object is hidden to not cover the selected faces). The reason for including the open face is that the body will be mirrored in the yz-plane.




The reason I need this is that I want convex volumes for hit-testing that relies on the normal projection method. An alternative is to relax on the convexity assumption, but then I need another algorithm perhaps involving testing a surface integral for equality to 4pi, which seems numerically unstable.
1a.  The technique you are looking for is called Convex Decomposition and there is a fair amount of research on it.  It's good for skeletonizing meshes for rigging, and I'm sure many other useful things.

http://masc.cs.gmu.edu/wiki/ACD

1b.  I do not believe there is any way to do this automatically in blender natively.

1c.  There is an addon to do this volume decomposition in blender, it relies on external code library and is more targetdd at the game engine however you may be able to tailor it's results to your needs.  This is an approximate decomposition.
http://blenderartists.org/forum/showthread.php?357513-Volumetric-Hierarchical-Approximate-Convex-Decomposition-%28e-g-for-BGE-Physics%29

2a. If your method is actually going to create interior geometry in the same mesh, then finding the non manifold edges and then interior faces is not a big deal. However my answer above is going to create approximate new objects

2b.  If you are able to split your mesh into groups of verts, using the bmesh convex hull modifier will tell you what new geomtry it creates.  By the definitition of your problem, all the new geometry will be the