Page 180 - Geometric Modeling and Algebraic Geometry

182 I. Ivrissimtzis and H.-P. Seidel
the mth power of the subdivision matrix, as m tends to infinity. That means that
the properties of the subdivision surface are related to the spectral properties of the
subdivision matrix.
The study of a subdivision surface through the study of the eigenstructure of
the subdivision matrix can be facilitated by exploiting patterns of the matrix arising
from the symmetries of the local connectivity. In the simplest example, the 1-ring
neighborhood of a triangle mesh vertex has rotational symmetry of order k, where k
is the valence of that vertex. This rotational symmetry is reflected in the rules of any
subdivision scheme with reasonable behavior, resulting in subdivision matrices with
circulant blocks.
Circulant matrices are simple patterned matrices with the property that each row
is the previous row cycled forward one step. Block-circulant matrices are a general-
ization of the circulant. They have the same cyclic pattern, but this time on matrix
blocks instead of single elements. An equivalent generalization is the circulant-block
matrix, which has circulant matrices as blocks. G-circulant matrices generalize the
circulant matrices into another direction. A matrix is called G-circulant if its columns
and rows are indexed by the elements of a group G. The simplest cases of G-circulant
matrices are those corresponding to abelian groups. As we will see below, such pat-
terned matrices arise in volume subdivision processes, reflecting the symmetries of
cubes and prisms.

10.1.1 Geometric decompositions to the eigenvectors of a patterned matrix

In this paper we study the geometric decompositions to the eigenvectors of patterned
matrices. By this we mean decompositions into geometric objects that are only scaled
by the patterned matrix. These geometric components can be seen as geometric
interpretations of the eigenvectors of the patterned matrix, with the real eigenvec-
tors corresponding to linear components and the complex eigenvectors giving planar
components. By embedding these components into a higher dimensional space, we
can use them to decompose higher dimensional objects, such as n-dimensional cubes
and prisms. When there is no room for ambiguity, we will refer to the components as
eigencomponents, or eigenvectors, or eigenpolygons, eigencubes and eigenprisms.
If a decomposition of a shape is given as

(10.1)
V 0 + V 1 + ··· + V n−1
and λ 0 ,λ 1 ,...,λ n−1 are the corresponding eigenvalues, then, after m consecutive
transformations by the matrix the shape is given by
m
m
λ V 0 + λ V 1 + ··· + λ m V (10.2)
n−1 n−1
0 1
We see that in the limit the shape is determined by the eigencomponents with the
largest eigenvalues.
The use of the eigenvalues and the eigenvectors of the subdivision matrix, in a
form similar to the one described by Eq. 10.2, is a standard tool in the study of sub-
division surfaces. We consider a set of independent and preferably real eigenvectors