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

Daniel Mlakar^1,2 Martin Winter² Pascal Stadlbauer¹      Hans-Peter Seidel¹   Markus Steinberger²   Rhaleb Zayer¹  

¹Max Planck Institute for Informatics, Saarland Informatics Campus    ²Graz University of Technology

  

Abstract

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 abstracted 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 abstraction underlying our work is further demonstrated by extension to other schemes such as √3 and Loop subdivision.

 

Downloads

Article (PDF, 1.7MB)

Video (MP4, 57MB)

code

Conference Talk

Watch at EG'20

 

Citation

Mlakar, D., Winter, M., Stadlbauer, P., Seidel, H.-P., Steinberger, M. and Zayer, R. (2020), Subdivision Specialized Linear Algebra Kernels for Static and Dynamic Mesh Connectivity on the GPU. Computer Graphics Forum, 39: 335-349.

@article{mesh_matrix_subdivision,
  author    = {Daniel Mlakar and Martin Winter and Pascal Stadlbauer and Hans{-}Peter Seidel and Markus Steinberger and Rhaleb Zayer},
  title     = {Subdivision-Specialized Linear Algebra Kernels for Static and Dynamic
               Mesh Connectivity on the {GPU}},
  journal   = {Comput. Graph. Forum},
  volume    = {39},
  number    = {2},
  pages     = {335--349},
  year      = {2020},
  url       = {https://doi.org/10.1111/cgf.13934},
  doi       = {10.1111/cgf.13934},
}