Finite element method (FEM) is commonly used for deformable image registration. However, there is no existing literature studying how the superimposed mesh structure would influence the image registration process. We study this problem in this paper, and propose a dynamic meshing strategy to generate mesh structure for image registration. To construct such a dynamic mesh during image registration, three steps are performed. Firstly, a density field that measures the importance of a pixel/voxel’s displacement to the registration process is computed. Secondly, an efficient contraction–optimization scheme is applied to compute a discrete Centroidal Voronoi Tessellation of the density field. Thirdly, the final mesh structure is constructed by its dual triangulation, with some post-processing to preserve the image boundary. In each iteration of the deformable image registration, the mesh structure is efficiently updated with GPU-based parallel implementation. We conduct experiments of the new dynamic mesh-guided registration framework on both synthetic and real medical images, and compare our results with the other state-of-the-art FEM-based image registration methods. •We study how the superimposed mesh structure would influence the Finite Element Method (FEM)-based image registration process.•We propose a mesh generation algorithm based on how the mesh will influence the registration process, using the discrete Centroidal Voronoi Tessellation idea.•We present a parallel algorithm to compute and update the mesh structure efficiently during image registration.