We present a high-order accurate boundary-based solver for three-dimensional (3D) frequency-domain scattering from a doubly-periodic grating of smooth axisymmetric sound-hard or transmission obstacles. We build the one-obstacle solution operator using separation into P azimuthal modes via the FFT, the method of fundamental solutions (with N proxy points lying on a curve), and dense direct least-squares solves; the effort is O((NP)-P-3) with a small constant. Periodizing then combines fast multipole summation of nearest neighbors with an auxiliary global Helmholtz basis expansion to represent the distant contributions, and enforcing quasiperiodicity and radiation conditions on the unit cell walls. Eliminating the auxiliary coefficients, and preconditioning with the one-obstacle solution operator, leaves a well-conditioned square linear system that is solved iteratively. The solution time per incident wave is then O(NP) at fixed frequency. Our scheme avoids singular quadratures, periodic Green's functions, and lattice sums, and its convergence rate is unaffected by resonances within obstacles. We include numerical examples such as scattering from a grating of period 13 lambda x 13 lambda comprising highly-resonant sound-hard "cups" each needing NP = 64800 surface unknowns, to 10-digit accuracy, in half an hour on a desktop. (C) 2016 Elsevier Inc. All rights reserved.
