The contact dynamics (CD) method is an ecient simulation technique of dense granular media where unilateral and frictional contact problems for a large number of rigid bodies have to be solved. In this paper, we present a modied version of the CD to generate homogeneous random packings of rigid grains. CD simulations are performed at constant external pressure, which allows the variation of the size of a periodically repeated cell. We follow the concept of the Andersen dynamics and show how it can be applied within the framework of the CD method. The main challenge here is to handle the interparticle interactions properly, which are based on constraint forces in CD. We implement the proposed algorithm, perform test simulations, and investigate the properties of the nal packings.