Performance Comparison and Workload Analysis of Mesh Untangling and Smoothing Algorithms

This paper compares methods for simultaneous mesh untangling and quality improvement that are based on repositioning the vertices. The execution times of these algorithms vary widely, usually with a trade-off between different parameters. Thus, computer performance and workloads are used to make comparisons. A range of algorithms in terms of quality metric, approach and formulation of the objective function, and optimization solver are considered. Among them, two new objective function formulations are proposed. Triangle and tetrahedral meshes and three processors architectures are also used in this study. We found that the execution time of vertex repositioning algorithms is more directly proportional to a new workload measure called mesh element evaluations than other workload measures such as mesh size or objective function evaluations. The comparisons are employed to propose a performance model for sequential algorithms. Using this model, the workload required by each mesh vertex is studied. Finally, the effects of processor architecture on performance are also analyzed.