Isogeometric segmentation. Part II: On the segmentability of contractible solids with non-convex edges

Motivated by the discretization problem in isogeometric analysis, we consider the challenge of segmenting a contractible boundary-represented solid into a small number of topological hexahedra. A satisfactory segmentation of a solid must eliminate non-convex edges because they prevent regular parameterizations. Our method works by searching a sufficiently connected edge graph of the solid for a cycle of vertices, called a cutting loop, which can be used to decompose the solid into two new solids with fewer non-convex edges. This can require the addition of auxiliary vertices to the edge graph. We provide theoretical justification for our approach by characterizing the cutting loops that can be used to segment the solid, and proving that the algorithm terminates. We select the cutting loop using a cost function. For this cost function we propose terms which help to select geometrically and combinatorially favorable cutting loops. We demonstrate the effects of these terms using a suite of examples.