In segmentation for reverse engineering, an input triangular mesh is usually split into segments for each of which a parametric surface is generated. The segment boundaries must be smooth for fine surfaces to be generated, but today's segmentation methods cannot necessarily generate a sufficient level of smoothness. The authors of this paper were inspired by the work reported in, and here try to extend it to efficiently segment a mesh obtained by scanning an object. Fuzzy boundary curves between two neighboring regions are globally rectified using a graph cut approach in which new energy functions are constructed. However, some curves are still not smooth since there are no straight lines around them in the original scanned mesh models, although the corresponding physical curves are smooth. To achieve further smoothing, we split some triangles by adding points and edges based on virtual triangle subdivision and the graph cut approach. As a result, significant further straightening of boundaries is achieved with simple straightest geodesics.