We address the problem of fast relabeling of deformable Delaunay tetrahedral meshes using a compact uniform grid, with CPU parallelization through OpenMP. This problem is important in visualizing the simulation of deformable objects and arises in scientific visualization, games, computer vision, and motion picture production. Many existing software tools and APIs have the ability to manipulate 3D virtual objects. Prior mesh-based representations either allow topology changes or are fast. We aim for both. Specifically, we improve the efficiency of the relabeling step in the Delaunay deformable mesh invented by Pons and Boissonnat and improved by Tychonievich and Jones. The relabeling step assigns material types to deformed meshes and accounts for 70% of the computation time of Tychonievich and Jones' algorithm. We have designed a deformable mesh algorithm using a Delaunay triangulation and a compact uniform grid with CPU parallelization to obtain greater speed than other methods that support topology changes. On average, over all our experiments and with various 3D objects, the serial implementation of the relabeling step of our work reports a speedup of 2.145 over the previous fastest method, including one outlier whose speedup was 3.934. When running in parallel on 4 cores, on average the relabeling step of our work achieves a speedup of 3.979, with an outlier at 7.63. The average speedup of our parallel relabeling step over our own serial relabeling step is 1.841.Simulation results show that the resulting mesh supports topology changes.