Let S be a rational projective surface given by means of a projective rational parametrization whose base locus satisfies a mild assumption. In this paper we present an algorithm that provides three rational maps such that the union of the three images covers S. As a consequence, we present a second algorithm that generates two rational maps , such that the union of its images covers the affine surface . In the affine case, the number of rational maps involved in the cover is in general optimal.