| In this paper, we discuss the multi-band subdivision algorithm based on bivariate box spline. The algorithm is the generalization of the binary Loop subdivision algorithm. Based on the conclusion of Reif, We deduced the M-band subdivision rules and the C1continuity sufficient condition by analyzing the subdivision matrix and the characteristic map. We constructed and analyzed the quaternary subdivision algorithm, and proved that the subdivision surface generate by the algorithm is C1continuous while3≤n≤20. We used the Computer algebra system and proved that the subdivision surface of ternary Loop subdivision algorithm is C1continuous. Meanwhile, we gave a range of the subdominant eigenvalue of the subdivision matrix, and proved that the subdivision surface of ternary Loop subdivision algorithm is C1continuous while subdominant eigenvalue within the range. The conclusion will not only lay a foundation for forming a complete theory of multi-band subdivision, but also expand the range of application of the subdivision algorithm based on triangular mesh. In the practical application, we will no longer limit to the binary subdivision algorithm but have flexible choices of the subdivision band according to actual needs.This paper consists of five parts. In chapter one, we introduce the development situation of subdivision algorithm, some basic knowledge, the arrangement of this paper, and the innovation points of this paper. Chapter two, chapter three, chapter four and chapter five give the main result of our research (i.e. the part1-4, in this abstract). In chapter two, we deduced the M-band subdivision masks of the Box spline Q(x, y) of bivariate spline space S42(Δ) from its refinement equation in Fourier transform. Meanwhile, we confirmed that every new generated point in a triangle is the linear combination of the vertices of the first triangle ring around the triangle. In chapter three, we used the generating function to obtain the M-band subdivision masks of Q(x, y), and gave the relation between masks of different band subdivision. We also introduced a simple method to obtain the M-band subdivision masks. In chapter four, we generalized the algorithm to arbitrary triangulation Mesh. By the construction and the analysis of subdivision matrix and characteristic map, we deduced the C1continuity sufficient condition of the subdivision surface. We constructed and analyzed the quaternary subdivision algorithm, and proved that the subdivision surface generate by the algorithm is C1continuous while3≤n≤20. We used the Computer algebra system and proved that the subdivision surface of ternary Loop subdivision algorithm is C1continuous. We also gave a range of the subdominant eigenvalue of the subdivision matrix, and proved that the subdivision surface of ternary Loop subdivision algorithm is C1continuous while the subdominant eigenvalue within the range. Further, we presented a simpler method to calculate the ternary Loop subdivision algorithm masks by which the generation of subdivision surfaces near extraordinary points of valence4and5are faster. The method is easy for generalization. We also obtained the M-band subdivision rule of the B-spline basis function of space S74(Δ), and gave the binary subdivision masks of the ordinary vertex-vertices and edge-vertices. In chapter five, we presented a set of M-band subdivision masks for operation and some example surfaces generated by the masks.1. First, we used the Fourier inverse transformation to get the M-band subdivision masks of the B-spline basis function Q(x, y) of bivariate spline space S42(Δ), and proved that every new generated point in a triangle is the linear combination of the three vertices of the triangle and the vertices of the first ring around the triangle.In the prophase work, we have got the refinement equation of Q(x, y) in Fourier transformation form:Theorem1:Let M>2be integer, then Q(x, y) satisfies the following M-band refinement equation: where it is required that the odevity of11and12be the same and By the Fourier inverse transformation, we have the odevity of11and12be the same and and so do13and14.Denoting the new points after a subdivision step by the linear representation of the old points, we have By discussion of11、12、13and14within their value rang, it can be concluded that(1) the mask of the new vertex-vertex (with subscript (0,0)) is d0,0=c0,0d0,0+c2,0d-2,0+c1,1d-1,-1+c-1,1d1,-1+c-2,0d2,0+c-1,-1d1,1+c1,-1d-1,1(5)(2) the mask of the new edge-vertex (with subscript (2/M,0) is(3) the masks of the new edge-vertices (with subscript (k/M,0),4≤k≤M) are (4) the mask of the new face-vertex (with subscript (3/M,1/M), in the first adjacent edge to the edge of the new edge-vertices) is(5)the masks of the rest new face-vertices (with subscript5≤k≤M, in the first edge adjacent to the edge of the new edge-vertices) are(6)the masks of the rest new face-vertices (with subscript r and s are of the same odivity,5≤r≤M,2≤s≤M/3, r≥3s, in the rest edges to the edge of the new edge-vertices) areTheorem2:Applying the M-band triangular subdivision algorithm, every new generated point in a triangle is the linear combination of the vertices of the first triangle ring around the triangle. The combination formulae are (5) to (10).2. Secondly, we used the generating function to obtain the M-band subdivision masks of Q(x, y), and introduced a simple method to obtain the M-band subdivision masks.Consider the relation of the Fourier transformations of Q(x, y) and of the box spline N(2,2,2)(x1,x2), then the generating function of [G(ξ1,ξ2)]2 and we have the relationship between the coefficients of the masks and the coefficients of the generating function: Next, we deduced the formulae to calculate the coefficients b(p,q) of the generating function, and form (11), we got the M-band subdivision masks of Q(x, y). The masks are the same of (5) to (10).We also gave the relation between masks of different band subdivision. Let RM1(Δ) represents the lth M-band subdivision of the initial regular mesh Δ, then we haveTheorem3:If M=M1·M2, thenCorollary1:let M=M1·M2……Mk, thenFurther, we introduced a simple method to obtain the M-band subdivision masks. That is:evenly take2M-1points in every edge of a hexagon and form a partition in three directions. Place all the coefficients of the generating function on the vertices of the hexagon according to the rule that the degrees of x and y are increasing in turn. By translating a special vertex for M-unit and for2times along six directions, we can simply get the corresponding subdivision mask.3. By the construction and the analysis of subdivision matrix and characteristic map, we deduced the C1continuity sufficient condition of the subdivision surface. We constructed and analyzed the quaternary subdivision algorithm, and proved that the subdivision surface generate by the algorithm is C1continuous while3≤n≤20. We used the Computer algebra system and proved that the subdivision surface of ternary Loop subdivision algorithm is C1continuous while3≤n≤20. We also gave a range of the subdominant eigenvalue of the subdivision matrix, and proved that the subdivision surface of ternary Loop subdivision algorithm is C1continuous while the subdominant eigenvalue within the range. Further, we presented a simpler method to calculate the ternary Loop subdivision algorithm masks by which the generation of subdivision surfaces near extraordinary points of valence4and5are faster. The method is easy for generalization. We also obtained the M-band subdivision rule of the B-spline basis function of space S74(Δ), and gave the binary subdivision masks of the ordinary vertex-vertices and edge-vertices.(1) C1continuity sufficient condition of subdivision surfaceTheorem4:Suppose the masks of the n-valence extraordinary point and the nearest edge-vertex are defined corresponding to α and γ i=0,…,n-1. Then the subdominant eigenvalue of the subdivision matrix is a real double eigenvalue and is the eigenvalue of A1(j=1,n-1) is equivalent to that the masks of the subdivision algorithm satisfy the following conditionsCorollary2:Suppose the masks of the n-valence extraordinary point and the nearest edge-vertex are defined corresponding to α and γi i=0,…,n-1. If the characteristic map of the subdivision algorithm is regular and injective and the subdivision masks satisfy the following conditions then the limiting surface is a C1continuous for almost all initial control nets.(2)Construction and analysis of the subdivision matrix and the characteristic map of ternary Loop subdivision algorithmConstruct the subdivision matrix A which has a block-circulant structure:Thus A is unitary similar to a block-diagonal matrix A. The union of the eigenvalues of the diagonal blocks Aj, j=0,…,n-1of A give the lln eigenvalues of A WhereA has a real subdominant eigenvalue λ1with geometric multiplicity2, thusWe used the Computer algebra system Mathematica8.0to calculate the11order complex eigenvector v of A1corresponding to λ1, and obtain Construct the lln order eigenvector v of A1corresponding to λ1. Let v is the conjugate vector of v, and we look upon the real part and the imaginary part of v as the coordinates of the lln control points of the characteristic map x. Next, construct the81Bezier points bj, j=l,…,81corresponding to the segment x0of x. Normalize the Bezier points b, j=1,…,81to obtain bj, j=1,…,81. Calculate bv,k0, k=1,…,49which are the49Bezier points of xv0by the normalized Bezier points bj, j=1,…,81. All bv,k0are functions of λ1and n. At last, we examine bv,k0>0componentwise. Let α=5/9, while3≤n≤20, we have the following conclusions.1)The choice of LoopLet λ=1/3,the conclusion is: for3≤n≤20,by symbolic computation, bv,k0>0componentwise. Thus the subdivision surface of ternary Loop subdivision is C1continuous.For n=3, if λ1=1/9,by symbolic computation, bv,k0are nonnegative componentwise with some components equal to zero.If λ1>1/9,by symbolic computation, bv,k0>0componentwise. so we suggest that λ1should be wmthin interval(1/9,1/3],for example λ1=1/6.2)Our choice of λ1 Theorem5:Suppose λ1with geometric multiplicity2is the subdominant eigenvalue of the subdivision matrix of ternary Loop subdivision, and For4≤n≤20, if λ1∈(1/9,1/2], then the limiting surface is a C continuous for almost all initial control nets.The upper bound of λ1is optimal. In practical, we suggest that for normaln, λ1∈(1/9,1/3]to ensure the C1continuity of the limiting surface.(3)Formula of edge-vertex of ternary Loop subdivision Define Formula of mask coefficients {γ1}: Formula of corresponding eigenvalues:The formula of the masks we present here are coincides with that of ternary Loop subdivision at regular points. In practice, the valences of extraordinary points are mostly4or5. At this moment, The formulas of the masks we present here are faster and can generate C1continuous limiting surfaces.(4) The construction of quaternary subdivision algorithmApply the regular subdivision rules at regular areas. Near the extraordinary point, the masks of the points on the second ring of the extraordinary point are regular. We constructed the characteristic polynomial and used the inverse Fourier transform to obtain the masks of the points on the first ring of the extraordinary point and its own. The masks are constructed by following steps:New vertex-vertex:weight of extraordinary point is α, weights of the first ring around extraordinary point are1-α/n. The reference value isNew first edge-vertex:weight of extraordinary point is β(1), weights of the first ring around extraordinary point are γk(1),k=0,1,2,...,n-1.While3≤n≤5, we construct the characteristic polynomial: and letThe reference value is β(1=120/256=15/32. The corresponding eigenvalues are While n≥6, let andThe reference values are β(1)=15/32,μ=1/4.New second edge-vertex:weight of extraordinary point is β(2), weights of the second ring around extraordinary point are regular,weights of the first ring around extraordinary point are γk(2), k=0,1,2,...,n-1.We construct the characteristic polynomial: and let The reference value is β(2)=87/256·New face-vertex:weight of extraordinary point is β(3), weights of the second ring around extraordinary point are regular, weights of the first ring around extraordinary point are γk(3), k=0,1,2,...,n-1.We construct the characteristic polynomial: and let where The reference value is We used the Computer algebra system Mathematica8.0and find that the subdivision surface of the quaternary subdivision algorithm which we construct is C1continuous while3≤n≤20.4. At last, we presented a set of operate masks which satisfy the C1continuity condition and some example surfaces generated by the masks.We gave a set of M-band subdivision masks that satisfy the C1continuity condition, the convex hull property, the symmetry property and the mask coefficients monotone property.The masks of the ordinary points are given by (5) to (10).At the extraordinary points, we have(1) For the new vertex-vertex, the mask is(2)For the new edge-vertex nearest to the vertex-vertex, the mask is If n=3, then Ifn=4, thenIfn=5, thenIfn≥7, then (3) For the rest new edge-vertices and new face-vertices, we take points P00, P10, P20, P30, Pn-20, Pn-10as six points around V0, thus we consider V0as an ordinary point, and apply the new edge-vertices masks and the new face-vertices masks of the ordinary point to generate new edge-vertices and new face-vertices. |
PDF Full Text Request