A new algorithm for the generation of very high-quality staggered unstructured grids for multi-resolution ocean and atmospheric modelling is described. Through use of unstructured triangulation and grid-optimisation techniques, it is shown that meshes satisfying a number of important a priori grid-quality constraints can be constructed. This new algorithm is expected to be of interest to both developers and users of unstructured general circulation models.