Page 179 - Geometric Modeling and Algebraic Geometry

10

Cube Decompositions by Eigenvectors of Quadratic
Multivariate Splines

Ioannis Ivrissimtzis and Hans-Peter Seidel 2
1
Durham University, UK
1
ioannis.ivrissimtzis@durham.ac.uk
MPI-Informatik, Saarbruecken, Germany
2
hpseidel@mpi-inf.mpg.de
Summary. A matrix is called G-circulant if its columns and rows are indexed by the elements
of a group G. When G is cyclic we obtain the usual circulant matrices, which appear in the
study of linear transformations of polygons. In this paper, we study linear transformations of
cubes and prisms using G-circulant matrices, where G is the direct product of cyclic groups.
As application, we study the evolution of a single cell of an n-dimensional grid under the
subdivision algorithm of the multivariate quadratic B-spline. Regarding the prism, we study
its evolution under a tensor extension of the Doo-Sabin subdivision scheme.

10.1 Introduction

Knot insertion, refinement and subdivision algorithms not only make splines a very
practical design tool but they also offer an insight into their mathematical properties.
In fact, such algorithms can even be seen as alternative definitions of the splines. The
latter has been proved a very fruitful approach leading to many generalizations, most
notably the subdivision surfaces, which generalize bivariate B-splines over polygonal
control meshes with arbitrary connectivity.
A subdivision surface is defined by an initial coarse polygonal mesh and a subdi-
vision rule which refines the mesh by adding new vertices and connecting them with
edges and faces creating a new denser mesh. Repetitive iterations of this process
yield in the limit a smooth surface, which depends on the initial coarse mesh and the
subdivision rule only.
Subdivision surfaces are studied locally, usually in the neighborhood of a vertex.
At each subdivision step the connectivity of the subdivision mesh becomes larger,
but, apart possibly from some initial steps, the local connectivity around the vertex
we study does not change. Instead, after a subdivision step the same local connectiv-
ity corresponds to a smaller neighborhood of the vertex.
After each subdivision step the positions of the new vertices are given as lin-
ear combinations of the old vertices, usually described in the form of a subdivision
matrix. The limit positions of the neighborhoods vertices are given by the limit of