  This paper, Part I in a two-part series, presents (i) A simple and highly
efficient algorithm for evaluation of quasi-periodic Green functions, as well
as (ii) An associated boundary-integral equation method for the numerical
solution of problems of scattering of waves by doubly periodic arrays of
scatterers in three-dimensional space. Except for certain "Wood frequencies" at
which the quasi-periodic Green function ceases to exist, the proposed approach,
which is based on use of smooth windowing functions, gives rise to lattice sums
which converge superalgebraically fast--that is, faster than any power of the
number of terms used--in sharp contrast with the extremely slow convergence
exhibited by the corresponding sums in absence of smooth windowing. (The
Wood-frequency problem is treated in Part II.) A proof presented in this paper
establishes rigorously the superalgebraic convergence of the windowed lattice
sums. A variety of numerical results demonstrate the practical efficiency of
the proposed approach.
