In this work we extend the CCBA to produce a parallel-iteratively mesh generator. The CCBA or Convex-Combination-Based-Algorithm (presented in ACSESS 2007) uses a mesh-size function and convex combinations on local polytopes to change the position of the nodes of an initial mesh. This process is repeated iteratively and stops when the max norm between two consecutives meshes is smaller than a given threshold. The parallelization is obtained by dividing the initial mesh into as many submeshes as processors available and dealing with each submesh in a different processor. This so-called mesh decomposition does not depend on the physical domain of the problem, which is the main difference and the main advantage over domain decomposition-like techniques for parallelization. We also present a way to reduce overhead while preserving the property of non-folding of the original sequential algorithm. Several examples of 2D meshes on complex domains show the potential of the technique for constructing non-uniform quad meshes.