Carr, Nathan A.Hart, John C.Roberto Scopigno and Denis Zorin2014-01-292014-01-2920043-905673-13-41727-8384https://doi.org/10.2312/SGP/SGP04/229-240Numerous mesh algorithms such as parametrization, radiosity, and collision detection require the decomposition of meshes into a series of clusters. In this paper we present two novel approaches for maintaining mesh clusterings on dynamically deforming meshes. The first approach maintains a complete face cluster tree hierarchy using a randomized data structure. The second algorithm maintains a mesh decomposition for a fixed set of clusters. With both algorithms we are able to maintain clusterings on dynamically deforming surfaces of over 100K faces in fractions of a second.Categories and Subject Descriptors (according to ACM CCS): I.3.3 [Computer Graphics]: Geometric algorithms