Surface description accuracy is of paramount importance when modelling contact problems. However, most FEM researchers still resort to polyhedral models to describe contact surfaces, which can oversimplify the original system by neglecting the curvature. To try to bridge this gap between CAD and CAE models, Nagata (2005) proposed a simple algorithm for interpolating discretized surfaces and recover the original geometry. In this work the Nagata patches algorithms are applied to interpolate polyhedral meshes of simple geometries (cylinder, sphere and torus), using the normal vector provided by the analytical functions to each node. The use of triangular or quadrilateral Nagata patches is compared, both in terms of algorithm efficiency and robustness. The interpolation algorithms are also applied using different normal vectors approximations, to analyse the influence of the normal vector accuracy in the Nagata interpolation accuracy. Tools for Nagata patch visualization and qualitative and quantitative analysis are also presented. Finally, some guidelines for polyhedral mesh generation are proposed, in order to render accurate Nagata patch interpolations.