# Subdividing a mesh into convex subvolumes and tagging faces

This question has two parts

1. Is there an automatic way in blender (perhaps an addon) of subdividing a mesh into convex subvolumes
2. 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.

• Rather, two faces may be shared by the same object. It is like subdivision, but on mesh level instead of face level. Commented Jun 6, 2015 at 9:07
• What is your final goal for this? Is your example a simplification of more complex cases? Commented Jun 6, 2015 at 16:49

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

• bmesh convex hull OPERATOR not modifier in answer 2b is what I meant to say. The operator returns new bmesh geometry and informs you what geometry in the convex hull was part of the original mesh, and what faces and edges were not. Sorry that needed clarification. Commented Jun 6, 2015 at 14:51