This paper proposes a Delaunay-type mesh generation algorithm governed by a metric map. The classical method is briefly established and then the different steps it involves are extended. It will be shown that the proposed method applies in three dimensions. The work is divided in two parts. Part I, i.e. the present paper, is devoted to the algorithmical aspects while Part II will present numerous application examples in the context of finite element computations.