Surface segmentation for polycube construction based on generalized centroidal Voronoi tessellation

Centroidal Voronoi tessellation (CVT) has been employed to construct polycubes using the normal space of the input surface. In this paper, we develop a new two-step surface segmentation scheme for polycube construction using generalized CVT (gCVT). In the first step, eigenfunctions of the secondary Laplace operator (SLO) are coupled with the harmonic boundary-enhanced CVT (HBECVT) model to classify vertices of the surface into several components based on concave creases and convex ridges of an object. Neighbouring vertex information is incorporated into the clustering energy function to avoid over-segmentation, jaggy boundaries and noise effect. For each segmented component, in the second step we apply the skeleton information to define local coordinates and include them into the HBECVT model to further segment it into several patches, which are revised using predefined geometric constraints for valid polycube construction. Our skeleton-based CVT algorithm is suitable for slim cylindrical objects and can reduce unnecessary singularities with compact polycube structures. Based on the constructed polycube, we generate quality all-hexahedral meshes and volumetric T-meshes via parametric mapping. Several examples are presented in this paper to show the robustness of our scheme.