Next: Mesh Generation Up: Reconstruction of Limit Surface Previous: Reconstruction of Limit Surface


Evaluation and Derivative Masks for Limit Surface

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

(6)


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

(7)


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 a linear combination of these right eigenvectors . Then Eg. (7) may be rearranged as

(8)


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

(9)


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

(10)


where is vector with all entries equal to one. It was proved [1] 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. (9) except the first one vanishes and the limit position yields

(11)


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

(12)


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

(13)


where the entries of the first (dominant) left eigenvector define the coefficients of that linear combination and form 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 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 [8] that a sufficient condition for subdivision scheme to be continuous is that the largest eigenvalue of 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. (5)) which exhibit only continuity. Thus the limit surface based on the modified Butterfly scheme is therefore smooth enough (generally continuous) to enable its differentiation.

A tangent vector at surface node can be approximated by

(14)


where is one of nodes connected to node , and location of which can be expressed according to Eq. (8) as

(15)


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

(16)


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

(17)


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

(18)


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

(19)


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



Next: Mesh Generation Up: Reconstruction of Limit Surface Previous: Reconstruction of Limit Surface

Daniel Rypl
2005-12-03