Massively Parallel Adaptive Collapsing of Edges for Unstructured Tetrahedral Meshes

Abstract

Many tasks in computer graphics and engineering involve unstructured tetrahedral meshes. Numerical methods such as the finite element method (FEM) oftentimes use tetrahedral meshes to compute a solution for complex problems such as physicallybased simulation or shape deformation. As each tetrahedron costs computationally, coarsening tetrahedral meshes typically reduces the overhead of numerical methods, which is attractive for interactive applications. In order to enable reduction of the tetrahedron count, we present a quick adaptive coarsening method for unstructured tetrahedral meshes. Our method collapses edges using the massively parallel processing power of present day graphics processing units (GPU)s to achieve run times of up to one order of magnitude faster than sequential collapsing. For efficient exploitation of parallel processing power, we contribute a quick method for finding a compact set of conflict-free sub-meshes, which results in up to 59% fewer parallel collapsing iterations compared to the state of the art massively parallel conflict detection.