A novel algorithm to generate a structural mesh model in the shape optimization analysis is proposed in this study. The entire domain for the shape optimization problems is defined by a regular hexahedral elements, and the evolution of the designed domain is obtained by moving the level-set function along a velocity field using a Hamilton-Jacobi equation. Instead of using the density-based mapping or immersed boundary methods to represent the physical/structural domain, the explicit type of shape representation for the structural analysis based on a hexahedral-dominant mesh generation, named a level set based polyhedral mesh generation (LSPM), is used. In the LSPM, the hexahedral elements crossed by the interface of a level set function are automatically cut into polyhedral elements to capture the shapes of the structural model, while most of regular hexahedral elements remain in the interior domain. Through the numerical results, the LSPM not only provides an efficient and flexible tool for meshing but also attain a high accuracy in the shape optimization problems.