Segmenting meshes into natural regions is useful for patch-based mesh fitting. In this paper, we present a novel algorithm for segmenting meshes into characteristic patches and provide a corresponding geometric proxy for each patch. We extend the powerful optimization technique of variational shape approximation by allowing for several different primitives to represent the geometric proxy of a surface region. Our method has the particular advantage of robustness. As the principal curvatures of the surfaces become more equal, the returned results are become closer to the surfaces of geometry primitives, i.e. planes, cylinders, or cones, or rotating surface which are the most common patch types in the reverse engineering. The expected result that we recover surface structures more robustly and thus get better approximations, is validated and demonstrated on a number of examples.