Next: Discrete Surface Meshing Up: Reconstruction of Limit Surface Previous: Recursive Interpolating Subdivision


Evaluation and Derivative Masks

The properties of the limit surface (and curve as well) can been derived by the standard examination of the eigenstructure of the local subdivision matrix corresponding to the adopted subdivision scheme [42]. The local subdivision matrix defines the relation between the set of nodes on subdivision level forming the smallest neighbourhood of a given surface node used to calculate the position of new nodes on the next level connected to node and the similar set of nodes on level around node . This relation may be expressed as

(95)


If a stationary scheme is considered, Eq. (95) can be rewritten as

(96)


where superscript relates to the original control grid. Assuming that the subdivision matrix is not defective, its right eigenvectors form a basis and the vector can be expressed as the linear combination of the right eigenvectors. Then Eg. (96) may be rearranged as

(97)


where are the coefficients of the linear combination, stands for the eigenvalues of , and denotes the number of nodes in the set associated with node . Thus after the infinite number of refinements the limit position of the set is given by

(98)


Since the subdivision scheme is affine invariant (points in set are affine combination of points ), each row of sums to one, which can be written as

(99)


where is the vector with all entries equal to one. It was proved [72] that for modified butterfly subdivision scheme, is the first right eigenvector corresponding to the dominant eigenvalue with multiplicity 1. Since all remaining eigenvalues are less than , all summation terms in Eq. (98) except the first one vanishes and the limit position yields

(100)


Considering that all entries of the first right eigenvector are equal to (revealing that after the infinite number of refinements, all nodes in the set are coincident with node , as expected) and that the coefficients of the linear combination can be evaluated as

(101)


where denotes left eigenvectors of (note that ), the limit position of node can be finally written simply as the linear combination of nodes of the corresponding set in the original control grid

(102)


where the entries of the first (dominant) left eigenvector define the coefficients of that linear combination and form the so called evaluation mask. In other words, the limit position of node is obtained in a closed form by averaging the initial set of nodes associated with node using the evaluation mask.

However, this observation is relevant only for approximating schemes. In the case of interpolating schemes, the dominant left eigenvector of has all entries equal to  except the one corresponding to the position of node in the set which is equal to . Thus the limit position of node is identical with its initial position in the control grid, which only confirms the fact that once a new node is introduced in the interpolating scheme, it is not moved any more.

A similar approach may be adopted to derive the so called derivative mask for differentiating the limit surface (and consequently for calculating the limit surface normal), provided the limit surface is sufficiently smooth. The smoothness of the limit surface can be quantified according to the spectrum of the local subdivision matrix . It was shown in [59] that a sufficient condition for a subdivision scheme to be continuous is that the -th largest eigenvalue of the local subdivision matrix has multiplicity and equals to for . The eigenanalysis of the local subdivision matrix of the modified butterfly scheme reveals that this scheme is continuous except for nodes of valence 3 and 4 (see Eq. 94) which exhibit only continuity. Thus the limit surface based on the modified butterfly scheme is therefore smooth enough (generally continuous) to enable its differentiating.

A tangent vector at surface node of the original control grid can be approximated by

(103)


where is one of the nodes connected to node , and location of which can be expressed according to Eq. 97 as

(104)


where subscript in indicates that only the entry of corresponding to is used. In the limit case, the tangent vector to the limit surface, given by

(105)


tends to zero as approaches infinity and therefore it is convenient to use the normalized expression in the form

(106)


Taking into account that the limit surface is at least continuous, which implies , the normalized tangent vector may be written as

(107)


Thus the normal to the limit surface at limit node can be calculated in the closed form as the normalized cross product of two tangent vectors evaluated using derivative masks defined by two left eigenvectors corresponding to the second largest eigenvalue of the local subdivision matrix according to the following formula

(108)


This can be generalized for a node on the -th level of the subdivision, thus

(109)


However in practice, the above formula is further modified to

(110)


The reason for this modification consists in the fact that the nodes surrounding node on the next level are always regular surface nodes, which guarantees the stationarity that has been initially assumed.

Since the calculation of derivative masks is rather expensive (standard eigenvalue problem with unsymmetric and positively semidefinite matrix has to be solved), all the masks have been precomputed6 for different values of nodal valence.



Footnotes

... precomputed6
The eigenvalue problems were solved by an EISPACK routine that firstly transforms the subdivision matrix to the Hessenberg matrix which is then subjected to QR-decomposition.


Next: Discrete Surface Meshing Up: Reconstruction of Limit Surface Previous: Recursive Interpolating Subdivision

Daniel Rypl
2005-12-07