Michael Driscoll

EECS Department, University of California, Berkeley

Technical Report No. UCB/EECS-2014-231

December 19, 2014

http://www2.eecs.berkeley.edu/Pubs/TechRpts/2014/EECS-2014-231.pdf

We present an interpretation of subdivision surface evaluation in the language of linear algebra. Specifically, the vector of surface points can be computed by left-multiplying the vector of control points by a sparse subdivision matrix. This “matrix-driven” interpretation applies to any level of subdivision, holds for many common subdivision schemes (including Catmull-Clark and Loop), supports limit surface evaluation, allows semi-sharp creases, and complements feature-adaptive optimizations. It is primarily applicable to static meshes undergoing deformation (i.e. animation), in which case the subdivision matrix is invariant over time and the surface can be evaluated at each frame with a single sparse matrix-vector multiplication (SpMV). We describe techniques for building subdivision matrices on-the-fly using the recursive definition of the subdivision scheme and sparse matrix-matrix multiplication (SpMM) routines. The performance of our approach thus reduces to that of SpMV and SpMM, both of which have been studied extensively and are available in common packages for numerical linear algebra. We implemented our approach as an extension to Pixar’s OpenSubdiv library using routines from Intel’s Math Kernel Library and Nvidia’s CUSPARSE library to target multicore CPUs and GPUs, respectively. We present performance results from off-the-shelf routines and our own “SpMV-like” routines that achieve 1.7-4.8x better performance than existing techniques on both platforms.We conclude by describing two major limitations of matrix-driven evaluation, namely difficulty computing vertex normals and complications in the presence of hierarchical edits, and suggest workarounds for both.

Advisors: Katherine A. Yelick and Armando Fox

---

BibTeX citation:

@mastersthesis{Driscoll:EECS-2014-231,
    Author= {Driscoll, Michael},
    Editor= {Yelick, Katherine A. and Fox, Armando},
    Title= {Subdivision Surface Evaluation as Sparse Matrix-Vector Multiplication},
    School= {EECS Department, University of California, Berkeley},
    Year= {2014},
    Month= {Dec},
    Url= {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2014/EECS-2014-231.html},
    Number= {UCB/EECS-2014-231},
    Abstract= {We present an interpretation of subdivision surface evaluation in the language of linear algebra. Specifically, the vector of surface points can be computed by left-multiplying the vector of control points by a sparse subdivision matrix. This “matrix-driven” interpretation applies to any level of subdivision, holds for many common subdivision schemes (including Catmull-Clark and Loop), supports limit surface evaluation, allows semi-sharp creases, and complements feature-adaptive optimizations. It is primarily applicable to static meshes undergoing deformation (i.e. animation), in which case the subdivision matrix is invariant over time and the surface can be evaluated at each frame with a single sparse matrix-vector multiplication (SpMV). We describe techniques for building subdivision matrices on-the-fly using the recursive definition of the subdivision scheme and sparse matrix-matrix multiplication (SpMM) routines. The performance of our approach thus reduces to that of SpMV and SpMM, both of which have been studied extensively and are available in common packages for numerical linear algebra. We implemented our approach as an extension to Pixar’s OpenSubdiv library using routines from Intel’s Math Kernel Library and Nvidia’s CUSPARSE library to target multicore CPUs and GPUs, respectively. We present performance results from off-the-shelf routines and our own “SpMV-like” routines that achieve 1.7-4.8x better performance than existing techniques on both platforms.We conclude by describing two major limitations of matrix-driven evaluation, namely difficulty computing vertex normals and complications in the presence of hierarchical edits, and suggest workarounds for both.},
}

EndNote citation:

%0 Thesis
%A Driscoll, Michael 
%E Yelick, Katherine A. 
%E Fox, Armando 
%T Subdivision Surface Evaluation as Sparse Matrix-Vector Multiplication
%I EECS Department, University of California, Berkeley
%D 2014
%8 December 19
%@ UCB/EECS-2014-231
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2014/EECS-2014-231.html
%F Driscoll:EECS-2014-231