Subdivision‐Specialized Linear Algebra Kernels for Static and Dynamic Mesh Connectivity on the GPU

• Published in: Computer graphics forum 2020-05, Vol.39 (2), p.335-349
• Main Authors: Mlakar, D., Winter, M., Stadlbauer, P., Seidel, H.‐P., Steinberger, M., Zayer, R.
• Format: Article
• Language: English
• Subjects: Animation; CCS Concepts; Computing methodologies → Shape modeling; Data structures; Finite element method; Hardware; Kernels; Linear algebra; Massively parallel algorithms; Matrix methods; Multiplication; Rendering; Sparse matrices; Topology
• ISSN: 0167-7055; 1467-8659
• DOI: 10.1111/cgf.13934

Subdivision surfaces have become an invaluable asset in production environments. While progress over the last years has allowed the use of graphics hardware to meet performance demands during animation and rendering, high‐performance is limited to immutable mesh connectivity scenarios. Motivated by recent progress in mesh data structures, we show how the complete Catmull‐Clark subdivision scheme can be ed in the language of linear algebra. While this high‐level formulation allows for a fully parallel implementation with significant performance gains, the underlying algebraic operations require further specialization for modern parallel hardware. Integrating domain knowledge about the mesh matrix data structure, we replace costly general linear algebra operations like matrix‐matrix multiplication by specialized kernels. By further considering innate properties of Catmull‐Clark subdivision, like the quad‐only structure after refinement, we achieve an additional order of magnitude in performance and significantly reduce memory footprints. Our approach can be adapted seamlessly for different use cases, such as regular subdivision of dynamic meshes, fast evaluation for immutable topology and feature‐adaptive subdivision for efficient rendering of animated models. In this way, patchwork solutions are avoided in favor of a streamlined solution with consistent performance gains throughout the production pipeline. The versatility of the sparse matrix linear algebra ion underlying our work is further demonstrated by extension to other schemes such as and Loop subdivision.