Image Source: Provably Robust Directional Vertex Relaxation

Directional Vertex Relaxation (DVR) is a mesh optimization algorithm introduced by Rangarajan et al. in the paper - Provably Robust Directional Vertex Relaxation for Geometric Mesh Optimization. A parallel version of the DVR algorithm has been introduced using OpenMP. This project involved improving the performance and scalability of parallel DVR. Performance bottlenecks were analyzed using profiling and large scale mesh optimization was performed. This work was conducted under the guidance of Prof. Ramsharan Rangarajan at the Mechanics and Computation Lab, Department of Mechanical Engineering, Indian Institute of Science.

Some results are listed below -

  • The parallel execution time was reduced by 47.4%.
  • 100% scalability was ensured in all 2D and 3D meshes which translated to a 40x speedup.

  • Meshing software such as CGAL, Hypermesh and Tetgen were used to prepare large scale meshes that demonstrate parallel optimization.
  • The mesh 'Nefertiti' with 14,315,330 elements and 2,953,326 nodes was relaxed by 40 threads in 1.33 mins as opposed to a single thread execution of 52.16 mins.

Parallel Directional Vertex Relaxation

Top to bottom: Image of the mesh followed by the quality vector plot and a plot of 'Speedup v/s Threads' demonstrating 100% scalability in parallel DVR

Quality v/s Quality Vector Index (q-00: input, q-25: dvr)

Quality v/s Quality Vector Index (q-00: input, q-25: dvr)

Speedup v/s Threads

Speedup v/s Threads

Improvement in Scalability

Initial scalability tests [left] for parallel DVR yielded a 20x speedup for 30 threads beyond which there was no improvement. The results we obtained after our performance and scalability analysis yielded a 47.4% reduction in parallel execution time and a 40x speedup (100% scalability).

Large Scale Mesh Optimization Results

Large-scale meshes were generated using CGAL, Hypermesh and Tetgen to extract maximum parallel performance from the algorithm. For instance, the mesh Nefertiti [left] with 14,315,330 elements and 2,953,326 nodes was relaxed by 40 threads in 1.33 mins as opposed to a single thread execution of 52.16 mins.

To view a slice of this mesh during relaxation, click here.

MESH OPTIMIZATION VISUALIZATION

Click on examples below to visualize the mesh relaxation -

  • Delaunay Triangulation (2D) optimized here.
  • A slice of the mesh 'Hand' being relaxed here.
  • A slice of the mesh 'PMDC' being relaxed here.