Harrison, CyrusChilds, HankGaither, Kelly P.Torsten Kuhlen and Renato Pajarola and Kun Zhou2014-01-262014-01-262011978-3-905674-32-31727-348Xhttps://doi.org/10.2312/EGPGV/EGPGV11/131-140We present a data-parallel algorithm for identifying and labeling the connected sub-meshes within a domaindecomposed 3D mesh. The identification task is challenging in a distributed-memory parallel setting because connectivity is transitive and the cells composing each sub-mesh may span many or all processors. Our algorithm employs a multi-stage application of the Union-find algorithm and a spatial partitioning scheme to efficiently merge information across processors and produce a global labeling of connected sub-meshes. Marking each vertex with its corresponding sub-mesh label allows us to isolate mesh features based on topology, enabling new analysis capabilities. We briefly discuss two specific applications of the algorithm and present results from a weak scaling study. We demonstrate the algorithm at concurrency levels up to 2197 cores and analyze meshes containing up to 68 billion cells.Categories and Subject Descriptors (according to ACM CCS): I.3.5 [Computational Geometry and Object Modeling]: Geometric algorithms, languages, and systems