# Patent

## Title
Subdivision surface-based geometric modeling system

## Abstract

A method for surface modeling of images to produce realistic images or to provide simulations with accurate surface information is provided. More particularly, the present invention relates to a new subdivision depth computation technique and to an improved label-driven adaptive subdivision technique for use in Catmull-Clark subdivision surface modeling systems. The method comprises computing a subdivision depth to determine the number of recursive subdivisions which may be performed on a control mesh to generate a plurality of finer mesh elements while preserving a predetermined error tolerance, and using the computed subdivision depth to construct an adaptively refined mesh that is substantially similar to the control mesh within the predetermined error tolerance. Limit control surfaces with and without extraordinary vertices may be analysed using the method of the invention. In another aspect, a software program for accomplishing the method of the present invention is provided.

## Background
This application claims the benefit of U.S. Provisional Patent Application Ser. No. 60/388,637 filed Jun. 14, 2002. This invention was made with Government support under NSF Grant No. DMI-9912069. The Government may have certain rights in this invention.


TECHNICAL FIELD
The present invention relates to the art of surface modeling of images to produce realistic images or to provide simulations with accurate surface information. More particularly, the present invention relates to a new subdivision depth computation technique and to an improved label-driven adaptive subdivision technique for use in Catmull-Clark subdivision surface modeling systems.
BACKGROUND OF THE INVENTION
Subdivision surfaces have become popular recently in graphical modeling, animation, and CAD/CAM because of their stability in numerical computation, simplicity in coding, and most importantly their capability in modeling/representing complex shape of arbitrary topology. Given a control mesh and a set of mesh refining rules, a user may obtain a limit surface by recursively cutting off corners of the control mesh. The limit surface is referred to as a subdivision surface because the corner cutting/mesh refining process is a generalization of the uniform B-spline surface subdivision technique. Subdivision surfaces include uniform B-spline surfaces and piecewise Bézier surfaces as special cases. It is also known in the art that subdivision surfaces may include non-uniform B-spline surfaces and NURBS surfaces as special cases. Subdivision surfaces can model/represent complex shape of arbitrary topology because there is no limit on the shape and topology of the control mesh of a subdivision surface. It is also known that subdivision surfaces cover both parametric forms and discrete forms. Since parametric forms are useful for design and representation and discrete forms are useful for machining and tessellation (including FE mesh generation), a representation is provided which is suitable for all graphics and CAD/CAM applications.
The prior art in subdivision surfaces has focused on the areas of surface trimming, boolean operations, and mesh editing. However, there are presently few suitable methods for dealing with precision/error control in subdivision surfaces, and in “smart” tessellation of subdivision surfaces. Given a predetermined error tolerance, it is necessary to determine how many levels of recursive Catmull-Clark subdivision should be performed on the initial control mesh such that the distance between the resultant control mesh and the limit surface is less than the predetermined error tolerance. It is also desirable to improve efficiency of tessellation based applications and data communication by generating a refined mesh within the required approximation precision of the limit surface with significantly fewer faces than the uniformly refined mesh. To date, efforts to reduce the number of faces in a mesh have focused on: (1) mesh simplification, i.e. removing over-sampled vertices and producing approximate meshes with various levels of detail; (2) approximating the limit surface by known surfaces, such as displaced subdivision surface or NURBS patches; and (3) application of adaptive refinement schemes to subdivision surfaces.
Accordingly, a need is identified for an improved method for subdivision surface modeling. The subdivision depth computation technique provided by the present invention provides precision/error control tools in subdivision surface trimming, finite element mesh generation, boolean operations, and surface tessellation for rendering processes. The label-driven adaptive subdivision technique of the invention improves efficiency of the above by generating an adaptively refined mesh that is within the required approximation precision of the limit surface, but with significantly fewer quadrilateral faces than prior art uniformly refined mesh techniques. The invention provides a subdivision depth computation technique for a Catmull-Clark subdivision surface (CCSS) patch, and provides also a label-driven adaptive subdivision technique for a CCSS based on subdivision depths calculated for its patches. A novel greedy algorithm is used to eliminate illegal vertex labels in the initial mesh.
Advantageously, the methods of the present invention provide a novel and efficient error control tool which is suitable for all tessellation-based applications of subdivision surfaces, and significantly reduce the number of faces in an adaptively refined quadrilateral mesh in a few subdivision steps, thereby improving efficiency of all tessellation-based applications and data communication of subdivision surfaces.
SUMMARY OF THE INVENTION
In accordance with a first aspect of the invention, a method for modeling or representing a surface or shape having an arbitrary topology which may be represented by a control mesh comprising at least one discrete Catmull-Clark Subdivision Surface (CCSS) patch defined by a set of control points is provided, comprising the steps of computing a subdivision depth determining the number of recursive subdivisions which may be performed on the control mesh to generate a plurality of finer mesh elements, whereby a distance between each finer mesh element and the corresponding limit surface patch is less than a predetermined error tolerance ε. Next is the step of using the computed subdivision depth to construct an adaptively refined mesh that is substantially similar to the control mesh within the range of the predetermined error tolerance ε. Each face of the recursively subdivided control mesh is a quadrilateral, and may contain up to one extraordinary vertex.
The method of the present invention is suitable for computing the subdivision depth, or the number of recursive subdivisions which may be performed on a surface patch while maintaining the predetermined error tolerance, for both surface patches which are not adjacent to an extraordinary vertex, and for surface patches which are adjacent to an extraordinary vertex.
For surface patches which are not adjacent to an extraordinary vertex, it will be appreciated that the surface patch will be a uniform bicubic B-spline surface patch which may be designated as S(u,v). In the absence of an extraordinary vertex, the next step is calculating a subdivision depth k defined as k levels of recursive subdivision performed on the control points of the surface patch S(u,v) to generate a level k control mesh, wherein k is defined as k≧┌log4 (M0/3ε) ┐, where M0 is the second order norm of S(u,v) and the distance between S(u,v) and the level k control mesh is less than ε.
If an extraordinary vertex is present in the patch being considered, the initial step is subdividing the surface patch at least twice to define at least one standard uniform bicubic B-spline surface subpatch and up to one extraordinary subpatch that is not a standard uniform bicubic B-spline subpatch, the extraordinary subpatch containing a limit point of up to one extraordinary vertex. Next, a subdivision depth nε for the extraordinary subpatch is computed, defined as n levels of recursive subdivision performed on the extraordinary subpatch to generate a level n extraordinary subpatch control mesh, wherein nε is defined as




  
    
      η
      ε
    
    ≡
    
      ⌈
      
        
          log
          δ
        
        ⁡
        
          (
          
            
              7
              ⁢
              
                G
                0
              
            
            
              2
              ⁢
              
                
              
              ⁢
              ε
            
          
          )
        
      
      ⌉
    
  
  ,
  
    
  
  ⁢
  
    δ
    =
    
      {
      
        
          
            
              
                4
                3
              
              ,
            
          
          
            
              
                if
                ⁢
                
                  
                
                ⁢
                N
              
              =
              3
            
          
        
        
          
            
              
                98
                85
              
              ,
            
          
          
            
              
                if
                ⁢
                
                  
                
                ⁢
                N
              
              ⁢
              
                >
                _
              
              ⁢
              5
            
          
        
      
    
  




where G0 is the first order norm of Π00, Π00 is a level-0 control point defined as {Vi|1≦i≦2N+8}, Vi is an extraordinary vertex with valence N, and the distance between the level n extraordinary subpatch control mesh and a corresponding bilinear plane defined in the extraordinary subpatch is less than or equal to ε if n≧nε.

For the remaining patches not containing the extraordinary vertex (after the initial subdivision step described above), next is the step of computing a subdivision depth D by performing D recursive subdivisions on each standard uniform bicubic B-spline subpatch to define a level D control mesh, wherein D is defined as the maximum number of recursive subdivisions which may be performed such that the distance between the standard uniform bicubic B-spline subpatch and the level D control mesh is less than ε.
In another aspect, the present invention provides a label-driven method of subdividing a Catmull-Clark subdivision surface patch derived as described above, comprising the steps of defining a mesh for which subdivision depths have been computed, the mesh comprising a plurality of quadrilateral faces containing up to one extraordinary vertex and having at least one interior face not adjacent a boundary of the control mesh and at least one exterior face adjacent a boundary of the control mesh, and defining an initial label of the interior face as a non-zero integer k wherein k is the subdivision depth of its corresponding surface patch with respect to ε. The method also includes the step of defining an initial label of the exterior face as zero.
Next is the step of establishing a consistent condition for each face whereby no two adjacent vertices thereof have non-zero labels and no two adjacent vertices thereof have zero labels and further wherein the number of zero labels is maximized. The consistent condition is established by defining a connection supporting graph Gb whose vertices are those of the faces having two adjacent vertices whose labels are zero, selecting a vertex from Gb, redefining the selected vertex label to 1, updating Gb, and repeating the process until the connection supporting graph contains no further vertices. For any face having two or more nonzero vertex labels, a balanced Catmull-Clark subdivision step is performed. For any face having only one vertex with zero label, an unbalance Catmull-Clark subdivision step is performed. Last is the step of computing new vertices from the results of the balanced and unbalanced Catmull-Clark subdivision steps to generate at least one new face defining the adaptively refined mesh structure.
In another aspect of the present invention, a computer software program for subdivision surface modeling is provided, wherein the software performs the steps as described above.



BRIEF DESCRIPTION OF THE DRAWING
FIG. 1 schematically depicts the ordering of control points for a CCSS patch with an extraordinary vertex;
FIG. 2 schematically depicts a representative population of control point sets;
FIG. 3 schematically depicts the subdivision of a surface patch having an extraordinary vertex into a plurality of standard uniform bicubic B-spline surface subpatches and a single extraordinary subpatch that is not a standard uniform bicubic B-spline subpatch which contains the limit point of the extraordinary vertex;
FIG. 4 schematically depicts FIG. 4 (a–b) schematically depicts the balanced Catmull-Clark subdivision of one of the standard uniform bicubic B-spline surface subpatches of FIG. 3;
FIG. 5 schematically depicts FIG. 5 (a–c) schematically depicts the unbalanced Catmull-Clark subdivision of the extraordinary subpatch of FIG. 3;
FIG. 6 (a–c) depicts the distance and subdivision depth computation for a CCSS patch having: (a) no extraordinary vertex; (b) an extraordinary vertex of valence 5; and (c) an extraordinary vertex of valence 8;
FIG. 7 graphically depicts a rocker FIG. 7 (a–d) graphically depicts a rocker arm, showing: (a) a control mesh therefor; (b) a limit surface therefor; (c) the result of performing a conventional uniform subdivision process; and (d) the result of performing the adaptive subdivision method of the present invention;
FIG. 8 (a–d) depicts the distance a ventilation controller component, showing: (a) a control mesh therefor; (b) a limit surface therefor; (c) the result of performing a conventional uniform subdivision process; and (d) the result of performing the adaptive subdivision method of the present invention; and
FIG. 9 (a–d) graphically depicts a marker cap, showing: (a) a control mesh therefor; (b) a limit surface therefor; (c) the result of performing a conventional uniform subdivision process; and (d) the result of performing the adaptive subdivision method of the present invention.



DETAILED DESCRIPTION OF THE INVENTION
The present invention provides a method and computer program, which may conveniently be disposed on a computer readable medium, for calculating a subdivision depth for a Catmull-Clark subdivision surface (CCSS) patch, and provides also a label-driven adaptive subdivision technique for a CCSS based on subdivision depths calculated for its patches.
Subdivision Depth Computation for Patches not Near an Extraordinary Vertex.
The first step is computation of a subdivision depth for a desired surface. Let V0, V1, V2, and V3 be the control points of a uniform cubic B-spline curve segment C(t) whose parameter space is [0,1]. If the middle leg of the control polygon is parametrized as follows: L(t)=V1+(V2−V1)t, 0≦t≦1, then the maximum of ∥L(t)−C(t)∥ is the distance between the curve segment and its control polygon. Thus:




  
    
      
        
          
          
            
              L
              ⁡
              
                (
                t
                )
              
            
            -
            
              C
              ⁡
              
                (
                t
                )
              
            
          
          
        
        =
        
          
            
            
              
                
                  
                    
                      (
                      
                        1
                        -
                        t
                      
                      )
                    
                    3
                  
                  6
                
                ⁢
                
                  (
                  
                    
                      2
                      ⁢
                      
                        V
                        1
                      
                    
                    -
                    
                      V
                      0
                    
                    -
                    
                      V
                      2
                    
                  
                  )
                
              
              +
              
                
                  
                    t
                    3
                  
                  6
                
                ⁢
                
                  (
                  
                    
                      2
                      ⁢
                      
                        V
                        2
                      
                    
                    -
                    
                      V
                      1
                    
                    -
                    
                      V
                      3
                    
                  
                  )
                
              
            
            
          
          ⁢
          
            <
            _
          
          ⁢
          
            
              1
              6
            
            ⁢
            max
            ⁢
            
              
                {
                
                  
                    
                    
                      
                        2
                        ⁢
                        
                          V
                          i
                        
                      
                      -
                      
                        V
                        0
                      
                      -
                      
                        V
                        2
                      
                    
                    
                  
                  ,
                  
                    
                    
                      
                        2
                        ⁢
                        
                          V
                          2
                        
                      
                      -
                      
                        V
                        1
                      
                      -
                      
                        V
                        3
                      
                    
                    
                  
                
                }
              
              .
            
          
        
      
    
    
      
        (
        1
        )
      
    
  




Since (2V1−V0−V2)/6 and (2V2−V1−V3)/6 are the values of L(t)−C(t) at t=0 and t=1, the following lemma results:

Lemma 1: The maximum of ∥L(t)−C(t)∥ occurs at the endpoints of the curve segment and may be expressed as





  
    
      
        
          
            max
            
              0
              ⁢
              
                <
                _
              
              ⁢
              t
              ⁢
              
                <
                _
              
              ⁢
              1
            
          
          ⁢
          
            
            
              
                L
                ⁡
                
                  (
                  t
                  )
                
              
              -
              
                C
                ⁡
                
                  (
                  t
                  )
                
              
            
            
          
        
        =
        
          
            1
            6
          
          ⁢
          max
          ⁢
          
            {
            
              
                
                
                  
                    2
                    ⁢
                    
                      V
                      1
                    
                  
                  -
                  
                    V
                    0
                  
                  -
                  
                    V
                    2
                  
                
                
              
              ,
              
                
                
                  
                    2
                    ⁢
                    
                      V
                      2
                    
                  
                  -
                  
                    V
                    1
                  
                  -
                  
                    V
                    3
                  
                
                
              
            
            }
          
        
      
    
    
      
        (
        2
        )
      
    
  




Next is the step of defining the distance between a uniform bicubic B-spline surface patch and its control mesh. Let Vi,j, 0≦i,j≦3, be the control points of a uniform bicubic B-spline surface patch S(u,v) with parameter space [0,1]×[0,1]. If the central mesh face {V1,1, V2,1, V1,2, V2,2} is parametrized as follows:

L(u,v)=(1−u)[(1−u)V1,1+uV2,1]+v[(1−u)V1,2+uV1,2],0≦u,v≦1

then the maximum of ∥L(u,v)−S(u,v)∥ is called the distance between S(u,v) and its control mesh. Defining Qu,k, Qv,k, Qu,k, and Qv,k as follows:





  
    
      
        
          Q
          
            u
            ,
            k
          
        
        ≡
        
          
            
              (
              
                1
                -
                u
              
              )
            
            ⁢
            
              V
              
                1
                ,
                k
              
            
          
          +
          
            uV
            
              2
              ,
              k
              ,
            
          
        
      
    
    
      
        
          Q
          
            v
            ,
            k
          
        
        ≡
        
          
            
              (
              
                1
                -
                υ
              
              )
            
            ⁢
            
              V
              
                k
                ,
                1
              
            
          
          +
          
            υ
            ⁢
            
              
            
            ⁢
            
              V
              
                k
                ,
                2
                ,
              
            
          
        
      
    
  
  
    
      
        
          
            Q
            _
          
          
            u
            ,
            k
          
        
        ≡
        
          
            ∑
            
              i
              =
              0
            
            3
          
          ⁢
          
            
          
          ⁢
          
            
              
                N
                
                  i
                  ,
                  3
                
              
              ⁡
              
                (
                u
                )
              
            
            ⁢
            
              V
              
                i
                ,
                k
                ,
              
            
          
        
      
    
    
      
        
          
            Q
            _
          
          
            υ
            ,
            k
          
        
        ≡
        
          
            ∑
            
              j
              =
              0
            
            3
          
          ⁢
          
            
          
          ⁢
          
            
              
                N
                
                  j
                  ,
                  3
                
              
              ⁡
              
                (
                υ
                )
              
            
            ⁢
            
              V
              
                k
                ,
                j
              
            
          
        
      
    
  




where Ni,3(t) are standard uniform B-spline basis functions of degree 3 results in:





  
    
      
        
          
          
            
              L
              ⁡
              
                (
                
                  u
                  ,
                  υ
                
                )
              
            
            -
            
              S
              ⁡
              
                (
                
                  u
                  ,
                  υ
                
                )
              
            
          
          
        
        <
        
          
            
              (
              
                1
                -
                υ
              
              )
            
            ⁢
            
              
              
                
                  Q
                  
                    u
                    ,
                    1
                  
                
                -
                
                  
                    Q
                    _
                  
                  
                    u
                    ,
                    1
                  
                
              
              
            
          
          +
          
            υ
            ⁢
            
              
              
                
                  Q
                  
                    u
                    ,
                    2
                  
                
                -
                
                  
                    Q
                    _
                  
                  
                    u
                    ,
                    2
                  
                
              
              
            
          
          +
          
            
              ∑
              
                i
                =
                0
              
              3
            
            ⁢
            
              
            
            ⁢
            
              
                
                  N
                  
                    i
                    ,
                    3
                  
                
                ⁡
                
                  (
                  u
                  )
                
              
              ⁢
              
                
                  
                  
                    
                      Q
                      
                        υ
                        ,
                        i
                      
                    
                    -
                    
                      
                        Q
                        _
                      
                      
                        υ
                        ,
                        i
                      
                    
                  
                  
                
                .
              
            
          
        
      
    
    
      
        (
        3
        )
      
    
  




Application of Lemma 1 on ∥Qu,1− Qu,1∥, ∥Qu,2− Qu,2∥ and ∥Qv,i− Qv,i∥, =1,2,3, and by defining M0 as the maximum norm of the second order forward differences of the control points of S(u,v), we have





  
    
    
      
        L
        ⁡
        
          (
          
            u
            ,
            υ
          
          )
        
      
      -
      
        S
        ⁡
        
          (
          
            u
            ,
            υ
          
          )
        
      
    
    
  
  ⁢
  
    <
    _
  
  ⁢
  
    
      1
      6
    
    ⁡
    
      [
      
        
          
            (
            
              1
              -
              υ
            
            )
          
          ⁢
          
            M
            0
          
        
        +
        
          υ
          ⁢
          
            
          
          ⁢
          
            M
            0
          
        
        +
        
          
            ∑
            
              i
              =
              0
            
            3
          
          ⁢
          
            
          
          ⁢
          
            
              
                N
                
                  i
                  ,
                  3
                
              
              ⁡
              
                (
                u
                )
              
            
            ⁢
            
              M
              0
            
          
        
      
      ]
    
  
  ⁢
  
    <
    _
  
  ⁢
  
    
      1
      3
    
    ⁢
    
      
        M
        0
      
      .
    
  




M0 is called the second order norm of S(u,v). From this, the following lemma is derived:

Lemma 2: The maximum of ∥L(u,v)−S(u,v)∥ satisfies the following inequality





  
    
      
        
          
            max
            
              
                0
                ⁢
                
                  <
                  _
                
                ⁢
                u
              
              ,
              
                υ
                ⁢
                
                  <
                  _
                
                ⁢
                1
              
            
          
          ⁢
          
            
            
              
                L
                ⁡
                
                  (
                  
                    u
                    ,
                    υ
                  
                  )
                
              
              -
              
                S
                ⁡
                
                  (
                  
                    u
                    ,
                    υ
                  
                  )
                
              
            
            
          
        
        ⁢
        
          <
          _
        
        ⁢
        
          
            1
            3
          
          ⁢
          
            M
            0
          
        
      
    
    
      
        (
        4
        )
      
    
  




where M0 is the second order norm of S(u, v).

It should be noted that even though the maximum of ∥L(t)−C(t)∥ occurs at the end points of the curve segment C(t), the maximum of ∥L(u, v)−S(u,v)∥ for a surface patch usually does not occur at the corners of S(u,v). Based on the foregoing, the method for subdivision depth computation for surface patches not adjacent to an extraordinary vertex will now be presented.
Let Vi,j, 0≦i,j≦3, be the control points of a uniform bicubic B-spline surface patch S(u,v). We use Vki,j, 0≦i,j≦3+2k−1, to represent the new control points of the surface patch after k levels of recursive subdivision. The indexing of the new control points follows the convention that Vk0,0 is always the face point of the mesh face {Vk−10,0, Vk−11,0, Vk−10,1, Vk−11,1}. The new control points Vki,j will be called the level-k control points of S(u,v) and the new control mesh will be called the level-k control mesh of S(u,v).
Note that if the parameter space of the surface patch is divided into 4k regions as follows:




  
    
      
        
          
            Ω
            
              m
              ,
              n
            
            k
          
          =
          
            
              [
              
                
                  m
                  
                    2
                    k
                  
                
                ,
                
                  
                    m
                    +
                    1
                  
                  
                    2
                    k
                  
                
              
              ]
            
            ×
            
              [
              
                
                  n
                  
                    2
                    k
                  
                
                ,
                
                  
                    n
                    +
                    1
                  
                  
                    2
                    k
                  
                
              
              ]
            
          
        
        ,
      
    
    
      
        (
        5
        )
      
    
  




where 0≦m,n≦2k−1 and let the corresponding subpatches be denoted Skm,n(u,v), then each Skm,n(u,v) is a uniform bicubic B-spline surface patch defined by the level-k control point set {Vkp,q|m≦p≦m+3,n≦q≦n+3}. Skm,n(u,v) is called a level-k subpatch of S(u,v). One can define a level-k bilinear plane Lkm,n on {Vkp,q|p=m+1, m+1; q=n+1, n+2} and measure the distance between Lkm,n(u,v) and Skm,n(u,v). It can be said that the distance between S(u,v) and the level-k control mesh is smaller than ε if the distance between each level-k subpatch Skm,n(u, v) and the corresponding level-k bilinear plane Lkm,n(u,v), 0≦m,n≦2k−1, is smaller than ε. Next will be demonstrated how to calculate a subdivision depth k for a given ε so that the distance between S(u,v) and the level-k control mesh is smaller than ε after k levels of recursive subdivision. The following lemma is needed in the derivation of the computation process. If we use Mkm,n to represent the second order norm of Skm,n (u, v), i.e. the maximum norm of the second order forward differences of the control points of Skm,n (u,v), then the lemma shows the second order norm of Skm,n (u, v) converges at a rate of 1/4 of the level-(k−1) second order norm. The proof of this lemma is provided in Appendix A.

Lemma 3: If Mkm,n is the second order norm of Skm,n (u,v), then we have





  
    
      
        
          M
          
            m
            ,
            n
          
          k
        
        ⁢
        
          <
          _
        
        ⁢
        
          
            
              (
              
                1
                4
              
              )
            
            k
          
          ⁢
          
            M
            0
          
        
      
    
    
      
        (
        6
        )
      
    
  




where M0 is the second order norm of S(u,v).

With lemmas 2 and 3, it is easy to see that, for any 0≦m,n≦2k−1, we have




  
    
      max
      
        
          0
          ≤
          u
        
        ,
        
          v
          ≤
          1
        
      
    
    ⁢
    
      
      
        
          
            L
            
              m
              ,
              n
            
            k
          
          ⁡
          
            (
            
              u
              ,
              v
            
            )
          
        
        -
        
          
            S
            
              m
              ,
              n
            
            k
          
          ⁡
          
            (
            
              u
              ,
              v
            
            )
          
        
      
      
    
  
  ≤
  
    
      1
      3
    
    ⁢
    
      M
      
        m
        ,
        n
      
      k
    
  
  ≤
  
    
      1
      3
    
    ⁢
    
      
        (
        
          1
          4
        
        )
      
      k
    
    ⁢
    
      
        M
        0
      
      .
    
  




Hence, if k is large enough to make the right side of (7) smaller than ε, we have





  
    
      max
      
        
          0
          ≤
          u
        
        ,
        
          v
          ≤
          1
        
      
    
    ⁢
    
      
      
        
          
            L
            
              m
              ,
              n
            
            k
          
          ⁡
          
            (
            
              u
              ,
              v
            
            )
          
        
        -
        
          
            S
            
              m
              ,
              n
            
            k
          
          ⁡
          
            (
            
              u
              ,
              v
            
            )
          
        
      
      
    
  
  ≤
  ε




for every 0≦m,n≦2k−1. This leads to the following:

Theorem 4: Let Vi,j, 0≦i,j≦3, be the control points of a uniform bicubic B-spline surface patch S(u,v). For any given ε>0, if





  
    
      
        k
        ≥
        
          ⌈
          
            
              log
              4
            
            ⁡
            
              (
              
                
                  M
                  0
                
                
                  3
                  ⁢
                  ε
                
              
              )
            
          
          ⌉
        
      
    
    
      
        (
        8
        )
      
    
  




levels of recursive subdivision are performed on the control points of S(u,v), then the distance between S(u,v) and the level-k control mesh is smaller than ε where M0 is the second order norm of S(u,v).

Subdivision Depth Computation for Patches Near an Extraordinary Vertex.

A different analysis is required for computation of subdivision depth for surface patches near extraordinary vertices, necessitated by the fact that one does not have a uniform B-spline surface patch representation and cannot use the analysis of Theorem 4 directly. The method of the present invention dictates making the size of such a vicinity as small as possible, thereby reducing such size to a degree that is tolerable (i.e., within the given error tolerance) and use the analysis of Theorem 4 to analyze the remaining portion of the surface patch. A subdivision depth computation based on this concept for a CCSS patch near an extraordinary vertex is presented below. It is assumed that the initial mesh has been subdivided at least twice such that each mesh face is a quadrilateral and contains at most one extraordinary vertex.
Let Π00={Vi|1≦i≦2N+8} be a level-0 control point set that influences the shape of a surface patch S(u,v) (=S00(u,v). V1 is an extraordinary vertex with valence N. The control vertices are ordered following Stam's fashion (Stam, J. 1998. Exact Evaluation of Catmull-Clark Subdivision Surfaces at Arbitrary Parameter Values. In Proceedings of SIGGRAPH 1998, 395–404, incorporated herein by reference) as schematically depicted in FIG. 1.
Using Vni to represent the level-n control vertices generated after n levels of recursive Catmull-Clark subdivision, and use Sn0, Sn1, Sn2 and Sn3 to represent the subpatches of Sn−10 defined over the tiles




  
    
      
        
          
            Ω
            0
            n
          
          =
          
            
              [
              
                0
                ,
                
                  1
                  
                    2
                    n
                  
                
              
              ]
            
            ×
            
              [
              
                0
                ,
                
                  1
                  
                    2
                    n
                  
                
              
              ]
            
          
        
        ,
      
    
    
      
        
          
            Ω
            1
            n
          
          =
          
            
              [
              
                
                  1
                  
                    2
                    n
                  
                
                ,
                
                  1
                  
                    2
                    
                      n
                      -
                      1
                    
                  
                
              
              ]
            
            ×
            
              [
              
                0
                ,
                
                  1
                  
                    2
                    n
                  
                
              
              ]
            
          
        
        ,
      
    
  
  
    
      
        
          
            Ω
            2
            n
          
          =
          
            
              [
              
                
                  1
                  
                    2
                    n
                  
                
                ,
                
                  1
                  
                    2
                    
                      n
                      -
                      1
                    
                  
                
              
              ]
            
            ×
            
              [
              
                
                  1
                  
                    2
                    n
                  
                
                ,
                
                  1
                  
                    2
                    
                      n
                      -
                      1
                    
                  
                
              
              ]
            
          
        
        ,
      
    
    
      
        
          
            Ω
            3
            n
          
          =
          
            
              [
              
                0
                ,
                
                  1
                  
                    2
                    n
                  
                
              
              ]
            
            ×
            
              [
              
                
                  1
                  
                    2
                    n
                  
                
                ,
                
                  1
                  
                    2
                    
                      n
                      -
                      1
                    
                  
                
              
              ]
            
          
        
        ,
      
    
  




respectively, then the shape of Sn0, Sn1, Sn2 and Sn3 are influenced by the level-n control point sets Πn0, Πn1, Πn2, and Πn3 are depicted in FIG. 2.

Π0n={Vin|1≦i≦2N+8}

Sn1, Sn2 and Sn3 are standard uniform bicubic B-spline surface patches because their control meshes satisfy a 4-by-4 structure. Hence, the technique described in Theorem 4 can be used to compute a subdivision depth for each of them. Sn0 is not a standard uniform bicubic B-spline surface patch. Hence, Theorem 4 can not be used to compute a subdivision depth for Sn0 directly. For convenience Sn0 may be called a level-n extraordinary subpatch of S(u,v) because it contains the limit point of the extraordinary points (see below). Note that if H0 and Hn are column vector representations of the control points of Π00 and Πn0, respectively,

H0≡(V0,V1, . . . ,V2N+8)t,Hn≡(V0n,V1n, . . . ,V2N+8n)t 

where (X, X, . . . , X)t represents the transpose of the row vector (X, X, . . . , X) then we have

Hn=(T)nH0  (9)

where T is the (2N+8)×(2N+8) (extended) subdivision matrix defined as follows:





  
    
      
        T
        ≡
        
          (
          
            
              
                
                  T
                  _
                
              
              
                0
              
            
            
              
                
                  
                    T
                    _
                  
                  
                    1
                    ,
                    1
                  
                
              
              
                
                  
                    T
                    _
                  
                  
                    1
                    ,
                    2
                  
                
              
            
          
          )
        
      
    
    
      
        (
        10
        )
      
    
  




with





  
    
      
        
          
            T
            _
          
          =
          
            (
            
              
                
                  
                    a
                    N
                  
                
                
                  
                    b
                    N
                  
                
                
                  
                    c
                    N
                  
                
                
                  
                    b
                    N
                  
                
                
                  
                    c
                    N
                  
                
                
                  
                    b
                    N
                  
                
                
                  ⋯
                
                
                  
                    b
                    N
                  
                
                
                  
                    c
                    N
                  
                
              
              
                
                  d
                
                
                  d
                
                
                  e
                
                
                  e
                
                
                  0
                
                
                  0
                
                
                  ⋯
                
                
                  e
                
                
                  e
                
              
              
                
                  f
                
                
                  f
                
                
                  f
                
                
                  f
                
                
                  0
                
                
                  0
                
                
                  ⋯
                
                
                  0
                
                
                  0
                
              
              
                
                  d
                
                
                  e
                
                
                  e
                
                
                  d
                
                
                  e
                
                
                  e
                
                
                  ⋯
                
                
                  0
                
                
                  0
                
              
              
                
                  f
                
                
                  0
                
                
                  0
                
                
                  f
                
                
                  f
                
                
                  f
                
                
                  ⋯
                
                
                  0
                
                
                  0
                
              
              
                
                  
                    
                  
                
                
                  
                    
                  
                
                
                  ⋮
                
                
                  
                    
                  
                
                
                  
                    
                  
                
                
                  
                    
                  
                
                
                  ⋰
                
                
                  ⋮
                
                
                  
                    
                  
                
              
              
                
                  d
                
                
                  e
                
                
                  0
                
                
                  0
                
                
                  0
                
                
                  0
                
                
                  ⋯
                
                
                  d
                
                
                  e
                
              
              
                
                  f
                
                
                  f
                
                
                  0
                
                
                  0
                
                
                  0
                
                
                  0
                
                
                  ⋯
                
                
                  f
                
                
                  f
                
              
            
            )
          
        
        ,
      
    
    
      
        (
        11
        )
      
    
  








  
    
      
        
          
            
              T
              _
            
            
              1
              ,
              1
            
          
          =
          
            (
            
              
                
                  c
                
                
                  0
                
                
                  0
                
                
                  b
                
                
                  a
                
                
                  b
                
                
                  0
                
                
                  0
                
                
                  0
                
              
              
                
                  e
                
                
                  0
                
                
                  0
                
                
                  e
                
                
                  d
                
                
                  d
                
                
                  0
                
                
                  0
                
                
                  0
                
              
              
                
                  b
                
                
                  0
                
                
                  0
                
                
                  c
                
                
                  b
                
                
                  a
                
                
                  b
                
                
                  c
                
                
                  0
                
              
              
                
                  e
                
                
                  0
                
                
                  0
                
                
                  0
                
                
                  0
                
                
                  d
                
                
                  d
                
                
                  e
                
                
                  0
                
              
              
                
                  e
                
                
                  0
                
                
                  0
                
                
                  d
                
                
                  d
                
                
                  e
                
                
                  0
                
                
                  0
                
                
                  0
                
              
              
                
                  b
                
                
                  c
                
                
                  b
                
                
                  a
                
                
                  b
                
                
                  c
                
                
                  0
                
                
                  0
                
                
                  0
                
              
              
                
                  e
                
                
                  e
                
                
                  d
                
                
                  d
                
                
                  0
                
                
                  0
                
                
                  0
                
                
                  0
                
                
                  0
                
              
            
            )
          
        
        ,
      
    
    
      
        (
        12
        )
      
    
  








  
    
      
        
          
            T
            _
          
          
            1
            ,
            2
          
        
        =
        
          (
          
            
              
                c
              
              
                b
              
              
                c
              
              
                0
              
              
                b
              
              
                c
              
              
                0
              
            
            
              
                0
              
              
                e
              
              
                e
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
            
            
              
                0
              
              
                c
              
              
                b
              
              
                c
              
              
                0
              
              
                0
              
              
                0
              
            
            
              
                0
              
              
                0
              
              
                e
              
              
                e
              
              
                0
              
              
                0
              
              
                0
              
            
            
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                e
              
              
                e
              
              
                0
              
            
            
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                c
              
              
                b
              
              
                c
              
            
            
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                0
              
              
                e
              
              
                e
              
            
          
          )
        
      
    
    
      
        (
        13
        )
      
    
  




and





  
    
      a
      N
    
    =
    
      1
      -
      
        7
        
          4
          ⁢
          N
        
      
    
  
  ,
  
    
      b
      N
    
    =
    
      3
      
        2
        ⁢
        
          N
          2
        
      
    
  
  ,
  
    
      c
      N
    
    =
    
      1
      
        4
        ⁢
        
          N
          2
        
      
    
  
  ,
  
    a
    =
    
      9
      16
    
  
  ,
  
    b
    =
    
      3
      32
    
  
  ,
  
    c
    =
    
      1
      64
    
  
  ,
  
    d
    =
    
      3
      8
    
  
  ,
  
    e
    =
    
      1
      16
    
  
  ,
  
    f
    =
    
      
        1
        4
      
      .
    
  




Subdivision Depth Computation for a Vicinity of the Extraordinary Vertex.

The goal is to find an integer nε for a given ε>0 so that if n (≧nε) recursive subdivisions are performed on Π00, then the control set point of the level-n extraordinary subpatch Sn0 of S(u,v), Πn0={Vni|1≦i≦2N+8}, is contained in the sphere B(Vn+15, ε/2) with center Vn+15≡(Vn1+Vn4+Vn5+Vn6)/4 and radius ε/2. Note that if the (2N+8)-point control mesh is contained in the then the level-n extraordinary subpatch Sn0 is contained in the sphere B(Vn+15, ε/2) as well. This follows from the fact that Sn0, as the limit surface of Πn0, is contained in the convex hull of Πn0 and the convex hull of Πn0 is contained in the sphere B(Vn+15, ε/2). Then, we have

max∥S0n(u,v)−L0n(u,v)∥<ε  (14)

where Ln0(u,v) is a bilinear plane defined on the level-n mesh face {Vn1+Vn4+Vn5+Vn6}. The construction of such an nε depends on several properties of the (extended) subdivision matrix T and the control point sets {Πn0}.

First note that since all the entries of the extended subdivision matrix T are non-negative and the sum of each row equals one, the extended subdivision matrix is a transition probability matrix of a (2N+8)-state Markov chain. In particular, the (2N+1)×(2N+1) block T* of T is a transition probability matrix of a (2N+1)-state Markov chain. The entries in the first row and first column of T* are all non-zero. Therefore, the matrix T* is irreducible because ( T*)2 has no zero entries and, consequently, all the states are accessible to each other. On the other hand, since all the diagonal entries of T* are non-zero and entries of ( T*)n are non-zero for all n≧2, it follows that all the states of T* are aperiodic and positive recurrent. Consequently, the Markov chain is irreducible and ergodic. By the well-known theorem of Markov chain, Theorem 4), ( T*)n converges to a limit matrix T* whose rows are identical. More precisely




  
    
      
        
          
            lim
            
              n
              ->
              ∞
            
          
          ⁢
          
            
              (
              
                T
                _
              
              )
            
            n
          
        
        =
        
          
            
              T
              _
            
            *
          
          ≡
          
            (
            
              
                
                  
                    Δ
                    1
                  
                
                
                  
                    Δ
                    2
                  
                
                
                  ⋯
                
                
                  
                    Δ
                    
                      
                        2
                        ⁢
                        N
                      
                      +
                      1
                    
                  
                
              
              
                
                  
                    Δ
                    1
                  
                
                
                  
                    Δ
                    2
                  
                
                
                  ⋯
                
                
                  
                    Δ
                    
                      
                        2
                        ⁢
                        N
                      
                      +
                      1
                    
                  
                
              
              
                
                  ⋮
                
                
                  ⋮
                
                
                  ⋰
                
                
                  ⋮
                
              
              
                
                  
                    Δ
                    1
                  
                
                
                  
                    Δ
                    2
                  
                
                
                  ⋯
                
                
                  
                    Δ
                    
                      
                        2
                        ⁢
                        N
                      
                      +
                      1
                    
                  
                
              
            
            )
          
        
      
    
    
      
        (
        15
        )
      
    
  




where Δi are the unique non-negative solution of





  
    
      
        
          
            
              
                Δ
                j
              
              =
              
                
                  ∑
                  
                    i
                    =
                    1
                  
                  
                    
                      2
                      ⁢
                      N
                    
                    +
                    1
                  
                
                ⁢
                
                  
                
                ⁢
                
                  
                    Δ
                    i
                  
                  ⁢
                  
                    
                      t
                      _
                    
                    
                      i
                      ,
                      j
                      ,
                    
                  
                
              
            
          
          
            
              
                j
                =
                1
              
              ,
              2
              ,
              ⋯
              ,
              
                
                  2
                  ⁢
                  N
                
                +
                1
              
            
          
        
        
          
            
              
                
                  ∑
                  
                    j
                    =
                    1
                  
                  
                    
                      2
                      ⁢
                      N
                    
                    +
                    1
                  
                
                ⁢
                
                  
                
                ⁢
                
                  Δ
                  j
                
              
              =
              1
            
          
          
            
              
            
          
        
      
    
    
      
        (
        16
        )
      
    
  




with ti,j being the entries of T*. One can easily get the following observations.

    
    
        The vector (Δ1, Δ2, . . . , Δ2N+1) satisfies the following properties:
    
    






  
    
      
        
          Δ
          1
        
        =
        
          N
          
            N
            +
            5
          
        
      
    
  
  
    
      
        
          Δ
          2
        
        =
        
          
            Δ
            4
          
          =
          
            ⋯
            =
            
              
                Δ
                
                  2
                  ⁢
                  N
                
              
              =
              
                4
                
                  N
                  ⁡
                  
                    (
                    
                      N
                      +
                      5
                    
                    )
                  
                
              
            
          
        
      
    
  
  
    
      
        
          Δ
          3
        
        =
        
          
            Δ
            5
          
          =
          
            ⋯
            =
            
              
                Δ
                
                  
                    2
                    ⁢
                    N
                  
                  +
                  1
                
              
              =
              
                1
                
                  N
                  ⁡
                  
                    (
                    
                      N
                      +
                      5
                    
                    )
                  
                
              
            
          
        
      
    
  




    
    
        The matrix T* is an idempotent matrix, i.e. T* T*= T*. Hence, T* has two eigenvalues, 1 and 0 (with multiplicity 2N).
         T* has 1 as an eigenvalue and all the other 2N eigenvalues of T* have a magnitude smaller than one.
        As is well known, the limit point of {Vn1} is

V*1≡Δ1V1+Δ2V2+ . . . Δ2N+1V2N+1.

But V*1 is actually the limit point of all Vnj, j=1, 2, . . . , 2N+8. Therefore, the convex hull of {Vn1, Vn2, . . . , Vn2N+8} converges to V*1 when n tends to infinity and, consequently, V*1=S(0,0). The fact that V*1 is the limit point of {Vn1, Vn2, . . . , Vn2N+1} follows from (9) and (15). The fact that V*1 is also the limit point of {Vn2N+2, Vn2N+3, . . . , Vn2N+8} is demonstrated in Appendix B.

    
    


The last observation is important because it shows that




  
    
      
        
          max
          
            V
            ⁢
            
              
            
            ⁢
            
              εΠ
              0
              n
            
          
        
        ⁢
        
          
          
            
              V
              5
              
                n
                +
                1
              
            
            -
            V
          
          
        
      
    
    
      
        (
        17
        )
      
    
  




converges. Therefore, it is possible to reduce the size of Sn0 to a degree that is tolerable if n is large enough. For a given ε>0 we will find an nε so that if n≧nε then the level-n control point set Πn0 is contained in the sphere B(Vn+15, ε/2). To do this, we need to know how fast (17) converges.

Referring to FIG. 3, let Φk0, Φk1, Φk2, and Φk3, be subsets of Πk0 defined as follows:

Φ0k={Vjk|j=1,2, . . . ,2N+1},

Φ1k={Vjk|j=1,4,5, . . . ,8,2N+3,2N+4,2N+5},

Φ2k={Vjk|j=1,4,5,6,2N+2,2N+3,2N+4,2N+6,2N+7},

Φ3k={Vjk|j=1,2, . . . ,6,2N+6,2N+7,2N+8}  (18)

(Vk8 in Φk1 should be replaced with Vk2 if N=3) and define Gk0, Gk1, Gk2, and Gk3 as follows:

G0k=maxVεφ0k∥V1k−V∥, G1k=maxVεφ1k∥V6k−V∥, G2k=maxVεφ2k∥V5k−V∥, G3k=maxVεφ3k∥V4k−V∥.   (19)

Gki is called the first order norm of Φki, i=0, 1, 2, 3. We need the following lemma for the construction of nε. The proof is shown in Appendix C.

Lemma 5: If Φki and Gki are defined as above, then for i=0, 1, 2, 3, we have





  
    
      
        
          G
          i
          k
        
        ≤
        
          {
          
            
              
                
                  
                    
                      
                        (
                        
                          3
                          4
                        
                        )
                      
                      k
                    
                    ⁢
                    
                      G
                      0
                    
                  
                  ,
                
              
              
                
                  
                    if
                    ⁢
                    
                      
                    
                    ⁢
                    N
                  
                  =
                  3
                
              
            
            
              
                
                  
                    
                      
                        (
                        
                          
                            3
                            4
                          
                          +
                          
                            7
                            
                              4
                              ⁢
                              N
                            
                          
                          -
                          
                            13
                            
                              2
                              ⁢
                              
                                N
                                2
                              
                            
                          
                        
                        )
                      
                      k
                    
                    ⁢
                    
                      G
                      0
                    
                  
                  ,
                
              
              
                
                  
                    if
                    ⁢
                    
                      
                    
                    ⁢
                    N
                  
                  ≥
                  5
                
              
            
          
        
      
    
    
      
        (
        20
        )
      
    
  




where G0≡max {G00, G01, G02, G03}. G0 is called the first order norm of Π00.

To construct nε, note that if VεΠn0 and VεΦn0, we have

∥V5n+1−V∥≦1⁄4∥V4n−V1n∥+1⁄4∥V5n−V1n∥+1⁄4∥V6n−V1n∥+∥V1n−V∥≦ 7/4G0n.

It is easy to prove that similar inequalities hold for Φn1, Φn2, and Φn3 as well. Hence, for each VεΠn0, by Lemma 5 we have





  
    
      
        
          
          
            
              V
              5
              
                n
                +
                1
              
            
            -
            V
          
          
        
        ≤
        
          {
          
            
              
                
                  
                    
                      7
                      4
                    
                    ⁢
                    
                      
                        (
                        
                          3
                          4
                        
                        )
                      
                      n
                    
                    ⁢
                    
                      G
                      0
                    
                  
                  ,
                
              
              
                
                  
                    if
                    ⁢
                    
                      
                    
                    ⁢
                    N
                  
                  =
                  3
                
              
            
            
              
                
                  
                    
                      7
                      4
                    
                    ⁢
                    
                      
                        (
                        
                          
                            3
                            4
                          
                          +
                          
                            7
                            
                              4
                              ⁢
                              N
                            
                          
                          -
                          
                            13
                            
                              2
                              ⁢
                              
                                N
                                2
                              
                            
                          
                        
                        )
                      
                      n
                    
                    ⁢
                    
                      G
                      0
                    
                  
                  ,
                
              
              
                
                  
                    if
                    ⁢
                    
                      
                    
                    ⁢
                    N
                  
                  ≥
                  5
                
              
            
          
        
      
    
    
      
        (
        21
        )
      
    
  




Since the maximum of 3⁄4+ 7/4N− 13/2N2 occurs at N=7, (21) can be simplified as





  
    
      
        
          
          
            
              V
              5
              
                n
                +
                1
              
            
            -
            V
          
          
        
        ≤
        
          
            7
            4
          
          ⁢
          
            
              (
              
                1
                
                  δ
                  ⁢
                  
                    
                  
                
              
              )
            
            n
          
          ⁢
          
            G
            0
          
        
      
    
    
      
        (
        22
        )
      
    
  




where





  
    
      
        δ
        =
        
          {
          
            
              
                
                  
                    
                      4
                      3
                    
                    ,
                  
                
                
                  
                    
                      if
                      ⁢
                      
                        
                      
                      ⁢
                      N
                    
                    =
                    3
                  
                
              
              
                
                  
                    
                      98
                      85
                    
                    ,
                  
                
                
                  
                    
                      if
                      ⁢
                      
                        
                      
                      ⁢
                      N
                    
                    ≥
                    5
                  
                
              
            
            .
          
        
      
    
    
      
        (
        23
        )
      
    
  




Hence, ∥Vn+15−V∥ is smaller than ε/2 if n is large enough to make the right hand side of (22) smaller than or equal to ε/2. Consequently, we have the following theorem.

Theorem 6: Let Π00={Vi|1≦i≦2N+8} be a level-0 control point set that influences the shape of a CCSS patch S(u,v) (=S00(u,v)). V1 is an extraordinary vertex with valence N. The control vertices are ordered following Stam's fashion. For a given ε>0, if nε is defined as follows:





  
    
      
        
          
            n
            ε
          
          ≡
          
            ⌈
            
              
                log
                δ
              
              ⁡
              
                (
                
                  
                    7
                    ⁢
                    
                      G
                      0
                    
                  
                  
                    2
                    ⁢
                    
                      
                    
                    ⁢
                    ε
                  
                
                )
              
            
            ⌉
          
        
        ,
        
          
        
        ⁢
        
          δ
          =
          
            {
            
              
                
                  
                    
                      
                        4
                        3
                      
                      ,
                    
                  
                  
                    
                      
                        if
                        ⁢
                        
                          
                        
                        ⁢
                        N
                      
                      =
                      3
                    
                  
                
                
                  
                    
                      
                        98
                        85
                      
                      ,
                    
                  
                  
                    
                      
                        if
                        ⁢
                        
                          
                        
                        ⁢
                        N
                      
                      ≥
                      5
                    
                  
                
              
              .
            
          
        
      
    
    
      
        (
        24
        )
      
    
  




where G0 is the first order norm of Π00, then the distance between the level-n extraordinary subpatch Sn0(u,v) and the corresponding bilinear plane Ln0(u,v) is smaller than or equal to ε if n≧nε. Theorem 6 shows that the rate of convergence of the control mesh in the vicinity of an extraordinary vertex is fastest when valence of the extraordinary vertex is three.

Subdivision Depth Computation for the Remaining Part.

It is desired, for each k between 1 and nε, to determine a subdivision depth Dk (≧nε) so that if Dk recursive subdivisions are performed on the control mesh Π00 of S(u,v), then the distance between the level-Dk control mesh and the subpatches Ski, i=1, 2, 3, is smaller than ε. Consequently, if we define D to be the maximum of these Dk(i.e. D=max {Dk|1≦k≦nε}), then after D recursive subdivisions, the distance between the level-D control mesh and the subpatches Ski, i=1, 2, 3, would be smaller than ε for all 1≦k≦nε. Note that the distance between the level-D control mesh and the subpatches Sk1, Sk2, and Sk3 for nε+1≦k≦D, and the distance between the level-D control mesh and the level-D extraordinary subpatch SD0 would be smaller than ε as well. This is because these subpatches are subpatches of Snε0 and the distance between Snε0 and the level-nε control mesh is already smaller than ε. Hence, the key here is the construction of Dk. We will show the construction of Dk for Sk3 (u,v). This Dk works for Sk1 (u,v) and Sk2 (u,v) as well.
For 0≦u, v≦1, define a bilinear plane Lk3 (u, v) on the mesh face {Vk4, Vk5, Vk2N+7, Vk2N+6} as follows:

L3k(u,v)=(1−v)[(1−u)V4k+uV4k]+v[(1−u)V2N+7k+uV2N+6k].  (25)

Since Sk3(u, v) is a uniform bicubic B-spline surface patch with control mesh Πk3, we have, by Lemma 2,

∥L3k(u,v)−S3k(u,v)∥≦1⁄3Z3k  (26)

where Zk3 is the second order norm of Sk3(u,v). If we define Zi0 to be the second order norm of Si0(u,v), we have

Z3k≦WZ0k−1≦(W)kZ00  (27)

where





  
    
      
        W
        =
        
          {
          
            
          
          ⁢
          
            
              
                
                  
                    
                      2
                      3
                    
                    ,
                  
                
                
                  
                    
                      if
                      ⁢
                      
                        
                      
                      ⁢
                      N
                    
                    =
                    3
                  
                
                
                  
                    
                  
                
              
              
                
                  
                    
                      
                        1
                        2
                      
                      +
                      
                        1
                        
                          4
                          ⁢
                          N
                        
                      
                      +
                      
                        21
                        
                          4
                          ⁢
                          
                            N
                            2
                          
                        
                      
                    
                    ,
                  
                
                
                  
                    
                      if
                      ⁢
                      
                        
                      
                      ⁢
                      N
                    
                    =
                    5
                  
                
                
                  
                    
                  
                
              
              
                
                  
                    
                      
                        3
                        4
                      
                      +
                      
                        2
                        N
                      
                      -
                      
                        21
                        
                          2
                          ⁢
                          
                            N
                            2
                          
                        
                      
                    
                    ,
                  
                
                
                  
                    
                      if
                      ⁢
                      
                        
                      
                      ⁢
                      N
                    
                    >
                    5
                  
                
                
                  
                    
                  
                
              
            
            .
          
          ⁢
          
            
          
        
      
    
    
      
        (
        28
        )
      
    
  




The proof of (27) is shown in Appendix D. Hence, by combining the above results, we have

Lemma 7 The maximum distance between Sk3 and Lk3 satisfies the following inequality

max∥L3k(u,v)−S3k(u,v)∥≦1⁄3(W)kZ00  (29)

where W is defined in (28) and Z00 is the second order norm of S(u,v).

It should be pointed out that when defining Zi0, only the following items are needed for second order forward differences involving Vi1:

∥2V1i−V2ji−V2[(j+2)%N]∥,j=1,2, . . . ,N. 

Lemma 7 shows that if 1⁄3(W)k Z00≦ε then the distance between Sk3 and Lk3 is already smaller than ε. However, since nε subdivisions have to be performed on Π00 to get Snε0 anyway, Dk for Sk3 in this case is set to nε. This condition holds for Sk1 and Sk2 as well.
If 1⁄3(W)k Z00>ε, further subdivisions are needed on Πki, i=1, 2, 3, to make the distance between Ski, i=1, 2, 3, and the corresponding mesh faces smaller than ε. Considering Sk3 again, Sk3 is a uniform bicubic B-spline surface patch with control mesh Πk3. Therefore, if lk recursive subdivisions are performed on the control mesh Πk3, by Lemma 2 and Lemma 3 we would have

∥L3lk(u,v)−S3k(u,v)∥≦1⁄3(1⁄4)lkZ3k  (30)

where Llk3(u,v) is a level-lk control mesh relative to Πk3 and Zk3 is the second order norm of Sk3(u, v). Therefore, by combining the above result with 27), we have

∥L3lk(u,v)−S3k(u,v)∥≦1⁄3(1⁄4)lk(W)kZ00  (31)

We get the following Lemma by setting the right hand side of (31) smaller than or equal to ε.

Lemma 8 In Lemma 7, if the distance between Sk3 and Lk3 is not smaller than ε, then one needs to perform lk





  
    
      
        
          l
          k
        
        =
        
          ⌈
          
            
              log
              4
            
            ⁡
            
              (
              
                
                  
                    
                      (
                      W
                      )
                    
                    k
                  
                  ⁢
                  
                    Z
                    0
                    0
                  
                
                
                  3
                  ⁢
                  
                    
                  
                  ⁢
                  ε
                
              
              )
            
          
          ⌉
        
      
    
    
      
        (
        32
        )
      
    
  




more recursive subdivisions on the level-k control mesh Πk3 of Sk3 to make the distance between Sk3 and the level-(k+lk) control mesh smaller than ε.

This result works for for Sk1 and Sk2 as well. Note that the value of (W)k Z00 is already computed in Lemma 7 and W hs to be computed only once. Therefore, the subdivision depth Dk for Sk1, Sk2, and Sk3 is defined as follows:




  
    
      
        
          D
          k
        
        =
        
          max
          ⁢
          
            {
            
              
                n
                ε
              
              ,
              
                k
                +
                
                  ⌈
                  
                    
                      log
                      4
                    
                    ⁡
                    
                      (
                      
                        
                          
                            
                              (
                              W
                              )
                            
                            k
                          
                          ⁢
                          
                            Z
                            0
                            0
                          
                        
                        
                          3
                          ⁢
                          
                            
                          
                          ⁢
                          ε
                        
                      
                      )
                    
                  
                  ⌉
                
              
            
            }
          
        
      
    
    
      
        (
        33
        )
      
    
  




Consequently, we have the following main theorem:

Theorem 9 Let Π00={Vi|1≦i≦2N+8} be the control mesh of a CCSS patch S(u,v). The control points are ordered following Stam's fashion with V1 being an extraordinary vertex of valence N (see FIG. 1). For a given ε>0, if we compute nε as in (24) and D as follows:

D=max {Dk|1≦k≦nε}  (34)

where Dk is defined in (33) then after D recursive subdivisions, the distance between S(u,v) and the level-D control mesh is smaller than ε.

Label-Driven Adaptive Subdivision

Given a control mesh of arbitrary topology and an error tolerance ε>0, the next step is to construct an adaptively refined mesh that is close to within ε to the CCSS of the given control mesh, but with significantly fewer faces than are derived from the traditional Catmull-Clark subdivision process. The mesh refining process is driven by labels of mesh vertices.
The given control mesh will be referred to as Σ0 with the assumption that all the faces are quadrilaterals and each face contains at most one extraordinary vertex (as described supra). The limit surface of Σ0 will be referred to as F. For each positive integer k, Σk refers to the result of applying k levels of recursive Catmull-Clark subdivision on Σ0. A face of Σk is called an interior face if it is not adjacent to the boundary of the mesh. Otherwise, it is called an exterior face. All the faces of a closed control mesh are interior faces. Each interior face f of Σk has a corresponding surface patch in F, denoted Sf. The interior faces and their corresponding surface patches are parametrized using the techniques presented by Stam. The distance between f and the limit surface F is defined as the distance between f and the corresponding surface patch Sf.
The initial label of an interior face f in Σ0, denoted Lf(f), is set to k if k is the subdivision depth of the corresponding surface patch Sf with respect to ε. The label of an exterior face is set to zero. The label of a vertex V in Σ0 is defined as the maximum of labels of adjacent faces, i.e.,

Lv(V)=max {Lf(f)|fεΣ0 and V is a vertex of f}.  (35)

The adaptive refinement procedure requires vertex labels of Σ0 to satisfy the consistent condition (Cheng, F. et al., 1989. A Parallel Mesh Generation Algorithm Based on the Vertex Label Assignment Scheme. International Journal for Numerical Methods in Engineering 28, 1429–1448, incorporated herein by reference). A face of Σ0 is said to be an illegal face if two adjacent vertices have non-zero labels and two adjacent vertices have zero labels. The vertex labels of Σ0 are said to satisfy the consistent condition if Σ0 contains no illegal faces. The consistent condition ensures that the adaptively refined meshes are crack-free. Usually, Σ0 does not satisfy the consistent condition. The easiest way to make Σ0 satisfy the consistent condition is to set all the zero labels to 1. However, this would unnecessarily increase the number of faces generated in the resulting meshes since the number of faces in the refined meshes is determined by the labels of the vertices. A better way is to construct an extension function Ev(V) of Lv(V),




  
    
      
        
          
            E
            v
          
          ⁡
          
            (
            V
            )
          
        
        =
        
          {
          
            
              
                
                  
                    
                      L
                      υ
                    
                    ⁡
                    
                      (
                      V
                      )
                    
                  
                  ,
                
              
              
                
                  
                    
                      if
                      ⁢
                      
                        
                      
                      ⁢
                      
                        
                          L
                          υ
                        
                        ⁡
                        
                          (
                          V
                          )
                        
                      
                    
                    >
                    0
                  
                  ;
                
              
            
            
              
                
                  
                    0
                    ⁢
                    
                      
                    
                    ⁢
                    or
                    ⁢
                    
                      
                    
                    ⁢
                    1
                  
                  ,
                
              
              
                
                  
                    
                      if
                      ⁢
                      
                        
                      
                      ⁢
                      
                        
                          L
                          υ
                        
                        ⁡
                        
                          (
                          V
                          )
                        
                      
                    
                    =
                    0
                  
                  ,
                
              
            
          
        
      
    
    
      
        (
        36
        )
      
    
  




which satisfies the consistent condition but with as many zero labels as possible.

A greedy algorithm for the construction of Ev(V) via a connection supporting graph Gb is therefore presented herein. The vertices of Gb are those of the illegal faces whose labels are zero. The edges of Gb are those of Σ0 that connect vertices of Gb. The extension function Ev(V) is constructed by repeatedly selecting a vertex from Gb, changing its label to 1 and then updating Gb accordingly. This process continues until Gb is empty. The complexity of this process is that changing the label of a vertex from 0 to 1 changes the status of adjacent faces: an illegal face might become legal and a legal face might become illegal. Therefore, after changing the label of a selected vertex from 0 to 1, one needs to remove some old vertices and edges from Gb while adding some new vertices and edges into Gb. Obviously, the greedy algorithm should remove as many old vertices from Gb and add as few new vertices into Gb as possible during each selection and changing cycle. This is achieved by using the following rule in selecting a vertex from Gb to change label. Let D(V) denote the degree of V in Gb and let N(V) be the number of new vertices introduced into Gb if the label of V is changed from 0 to 1. If the number of D(V)=1 vertices is not zero then, in the pool of vertices which are adjacent to a D(V)=1 vertex, select any one with a minimum N(V) among those with a maximum D(V). Otherwise, select any vertex with a minimum N(V) among the vertices of Gb with a maximum D(V).
The adaptive subdivision process is driven by vertex labels and is performed on individual mesh faces independently. After each subdivision step, labels are assigned to the newly generated vertices so they can drive the next subdivision step. The resulting meshes are crack free. The assumption is made that labels of the vertices of Σ0 are defined by an extension function Ev even though the extension function might be the same as the original label function Lv. In the following, Σk, k=1, 2, . . . , stand for the meshes generated by the adaptive refinement process. Also, variables without a bar refer to elements in Σk−1, and variables with a bar refer to elements in Σk.
The adaptive subdivision of Σk−1, k≧1, is performed as follows. If a face has two or more nonzero vertex labels, a balanced Catmull-Clark subdivision is performed on that face (see FIG. 4). A balanced Catmull-Clark subdivision is a standard Catmull-Clark subdivision. However, coordinates of the new vertices are not yet computed. The new vertices are marked for updating. Labels of the new vertices are defined as follows. For each new vertex point, Ēv( Vi)=max {0, Ev(Vi)−1}, i=1, 2, 3, 4. For each new edge point, Ēv( Vi) is the minimum of labels of the new vertex points adjacent to Vi, i=5, 6, 7, 8. For the new face point,




  
    
      
        
          E
          _
        
        υ
      
      ⁡
      
        (
        
          V
          _
        
        )
      
    
    9
  
  =
  
    {
    
      
        
          
            0
            ,
            
              
            
            ⁢
            
              
                
                  if
                  ⁢
                  
                    
                  
                  ⁢
                  
                    
                      
                        
                          E
                          _
                        
                        υ
                      
                      ⁡
                      
                        (
                        
                          V
                          _
                        
                        )
                      
                    
                    5
                  
                
                =
                
                  
                    
                      
                        E
                        _
                      
                      υ
                    
                    ⁡
                    
                      (
                      
                        
                          V
                          _
                        
                        6
                      
                      )
                    
                  
                  =
                  
                    
                      
                        
                          
                            E
                            _
                          
                          υ
                        
                        ⁡
                        
                          (
                          
                            V
                            _
                          
                          )
                        
                      
                      7
                    
                    =
                    
                      
                        
                          
                            E
                            _
                          
                          υ
                        
                        ⁡
                        
                          (
                          
                            
                              V
                              _
                            
                            8
                          
                          )
                        
                      
                      =
                      0
                    
                  
                
              
              ;
            
          
        
      
      
        
          
            1
            ,
            
              
            
            ⁢
            
              
                if
                ⁢
                
                  
                
                ⁢
                some
                ⁢
                
                  
                
                ⁢
                but
                ⁢
                
                  
                
                ⁢
                not
                ⁢
                
                  
                
                ⁢
                all
                ⁢
                
                  
                
                ⁢
                of
                ⁢
                
                  
                
                ⁢
                
                  {
                  
                    
                      
                        
                          E
                          _
                        
                        υ
                      
                      ⁡
                      
                        (
                        
                          
                            V
                            _
                          
                          5
                        
                        )
                      
                    
                    ,
                    
                      
                        
                          E
                          _
                        
                        υ
                      
                      ⁡
                      
                        (
                        
                          
                            V
                            _
                          
                          6
                        
                        )
                      
                    
                    ,
                    
                      
                        
                          E
                          _
                        
                        υ
                      
                      ⁡
                      
                        (
                        
                          
                            V
                            _
                          
                          7
                        
                        )
                      
                    
                    ,
                    
                      
                        
                          E
                          _
                        
                        υ
                      
                      ⁡
                      
                        (
                        
                          
                            V
                            _
                          
                          8
                        
                        )
                      
                    
                  
                  }
                
                ⁢
                are
                ⁢
                
                  
                
                ⁢
                zero
              
              ;
            
          
        
      
      
        
          
            
              min
              ⁢
              
                {
                
                  
                    
                      
                        E
                        _
                      
                      υ
                    
                    ⁡
                    
                      (
                      
                        V
                        _
                      
                      )
                    
                  
                  |
                  
                    
                      V
                      _
                    
                    ⁢
                    
                      
                    
                    ⁢
                    ε
                    ⁢
                    
                      {
                      
                        
                          
                            V
                            _
                          
                          5
                        
                        ,
                        
                          
                            V
                            _
                          
                          6
                        
                        ,
                        
                          
                            V
                            _
                          
                          7
                        
                        ,
                        
                          
                            V
                            _
                          
                          8
                        
                      
                      }
                    
                  
                
                }
              
            
            ,
            
              
            
            ⁢
            
              otherwise
              .
            
          
        
      
    
  




If a face has only one vertex with nonzero label, an unbalanced Catmull-Clark subdivision with respect to that vertex is performed (see FIG. 5). An unbalanced Catmull-Clark subdivision generates three new faces only, as shown in FIG. 5c. However, V8, V9 and the auxiliary structure shown in FIG. 5b are computed and recorded for use in the computation of the vertices of Σk+1. Again, coordinates of the new vertices are not computed until a later point. The vertices, except V3, are marked for updating and later evaluation. The labels of the new points are set to zero except V1 which is defined as Ēv( V1)=Ev(Vi)−1. The faces without non-zero vertex labels are not further adaptively subdivided, but are inherited topologically.
After all the faces of Σk−1 are processed, vertices marked for updating in Σk are computed using the Catmull-Clark subdivision scheme to find their coordinates in Σk. Note that the vertices of Σk−1 required in the computation process for the new vertices are available because they were stored with the auxiliary structure (see FIG. 5b) even though not output. Other vertices (vertices marked for updating) of Σk are inherited from Σk−1 directly. Keeping an “update” status for some of the vertices in the adaptive subdivision process is necessary because whether a vertex should be inherited or updated depends on its adjacent faces. The adaptive refinement process stops when labels of all the new vertices are zero.
Other aspects of the present invention will become apparent to those skilled in this art from the following description wherein there is shown and described a preferred embodiment of this invention, simply by way of illustration of one of the modes best suited to carry out the invention. As it will be realized, this invention is capable of other different embodiments and its several details are capable of modification in various, obvious aspects all without departing from the intended scope of the invention. Accordingly, the descriptions and examples herein will be regarded as illustrative in nature and not as restrictive.
EXAMPLE 1
Referring to FIG. 6, distance and subdivision depth computation for a CCSS patch was calculated for several surfaces. The distances between the faces of the control meshes and the corresponding limit surface patches for each mesh face were 0.034 (FIG. 6a), 0.25 (FIG. 6b), and 0.15 (FIG. 6c). For an error tolerance of 0.01, the subdivision depths computed for each mesh face was 1 (FIG. 6a), 24 (FIG. 6b), and 22 (FIG. 6c). The calculated subdivision depths for the mesh faces shown in FIGS. 6b and 6c were greater because each surface has an extraordinary vertex. For the mesh face shown in FIG. 6b, subdivision depths for error tolerances 0.25, 0.2, 0.1, 0.01, 0.001, and 0.0001 were 1, 3, 9, 24, 40, and 56, respectively.
EXAMPLE 2
FIGS. 7, 8, and 9 compare conventional uniform Catmull-Clark subdivision with the adaptive subdivision method of the present invention. Referring to FIG. 7 showing a rocker arm, uniform Catmull-Clark subdivision resulted in 22,656 vertices, 45,312 edges, and 22,656 faces (FIG. 7c) for an error of 0.25. In contrast, the adaptive subdivision method of the present invention (FIG. 7d) generated 2,706 vertices, 5,412 edges, and 2,706 faces, i.e. only 3/25 of the total vertices, edges, and faces required for conventional Catmull-Clark subdivision. Lowering the error tolerance to 0.2 resulted in a maximum subdivision depth of 4. In this latter case, uniform Catmull-Clark subdivision generated 362,496 vertices, 724,992 edges, and 362,496 faces. In comparison, the label-driven adaptive subdivision method of this invention generated only 9,022 vertices, 18,044 edges, and 9,022 faces, or a 40× improvement on the total number of vertices, faces, and edges.
FIG. 8 depicts a ventilation controller component. For an error tolerance of 0.15, the maximum subdivision depth of the mesh faces in the input control mesh was 3. Uniform Catmull-Clark subdivision (FIG. 8c) generated 388,068 vertices, 776,192 edges, and 388,096 faces. In contrast, the method of the present invention required only 9814 vertices, 19,684 edges, and 9,842 faces. The reason that adaptive subdivision was performed in some of the flatter regions was that those regions contained extraordinary vertices.
A marker cap is depicted in FIG. 9. For an error tolerance of 0.1, the maximum subdivision depth of the mesh faces was 3. Uniform Catmull-Clark subdivision generated 273,398 vertices, 546,816 edges, and 273,408 faces (FIG. 9c). FIG. 9d shows that the label-driven adaptive subdivision method of the present invention generated only 15,086 vertices, 30,192 edges, and 15096 faces, an 18× improvement over the conventional method. Because the control mesh of the marker cap included more extraordinary vertices, and therefore required additional subdivision in the regions containing the extraordinary vertices, the savings was less than that shown in FIGS. 7 and 8. Notwithstanding, the present method represents an extraordinary savings in the number of vertices, edges, and faces required (compared to conventional Catmull-Clark subdivision) regardless of the complexity of the surface.
Accordingly, the present invention provides a significant improvement over conventional subdivision surface methodology. The subdivision depth computation step provides a precision/error control tool for all tessellation-based applications of subdivision surfaces. The label-driven adaptive subdivision step improves efficiency of all tessellation-based applications and data communication by significantly reducing the number of faces in the resultant mesh while satisfying the desired precision requirement.
Appendix A: Proof of Lemma 3
It is sufficient to show that, for each positive integer i, one has

M0,0i+1≦1⁄4M0,0i.  (37)

The sixteen second order forward differences involved in Mi+10,0 can be classified into four categories: (C-1) F-E-F, (C-2) E-F-E, (C-3) E-V-E, and (C-4) V-E-V, based on the type of the vertices. For instance, a second order forward difference is said to be in the first category if an edge vertex is sandwiched by two face vertices, such as 2Vi+11,0−Vi+10,0−Vi+12,0. Each category consists of four second order forward differences. We need to show that all these categories satisfy (37). In the following, we prove (37) for one item of each category. The proof of the other items is similar.





  
    
      
        
          (
          
            F
            -
            E
            -
            F
          
          )
        
        :
        
          
            consider
            ⁢
            
              
            
            ⁢
            2
            ⁢
            
              V
              
                0
                ,
                1
              
              
                i
                +
                1
              
            
          
          -
          
            V
            
              0
              ,
              2
            
            
              i
              +
              1
            
          
          -
          
            
              V
              
                0
                ,
                0
              
              
                i
                +
                1
              
            
            .
            
              

            
            ⁢
            
              
                
                  
                    
                      
                      
                        
                          2
                          ⁢
                          
                            V
                            
                              0
                              ,
                              1
                            
                            
                              i
                              +
                              1
                            
                          
                        
                        -
                        
                          V
                          
                            0
                            ,
                            2
                          
                          
                            i
                            +
                            1
                          
                        
                        -
                        
                          V
                          
                            0
                            ,
                            0
                          
                          
                            i
                            +
                            1
                          
                        
                      
                      
                    
                    =
                    
                    ⁢
                    
                      
                      
                        
                          
                            1
                            8
                          
                          ⁢
                          
                            (
                            
                              
                                2
                                ⁢
                                
                                  V
                                  
                                    0
                                    ,
                                    1
                                  
                                  i
                                
                              
                              -
                              
                                V
                                
                                  0
                                  ,
                                  2
                                
                                i
                              
                              -
                              
                                V
                                
                                  0
                                  ,
                                  0
                                
                                i
                              
                            
                            )
                          
                        
                        +
                      
                    
                  
                
              
              
                
                  
                    
                      
                      ⁢
                      
                        
                          1
                          8
                        
                        ⁢
                        
                          (
                          
                            
                              2
                              ⁢
                              
                                V
                                
                                  1
                                  ,
                                  1
                                
                                i
                              
                            
                            -
                            
                              V
                              
                                1
                                ,
                                2
                              
                              i
                            
                            -
                            
                              V
                              
                                1
                                ,
                                0
                              
                              i
                            
                          
                          )
                        
                      
                      
                    
                    ≤
                  
                
              
              
                
                  
                    
                    ⁢
                    
                      
                        
                          
                            1
                            8
                          
                          ⁢
                          
                            M
                            
                              0
                              ,
                              0
                            
                            i
                          
                        
                        +
                        
                          
                            1
                            8
                          
                          ⁢
                          
                            M
                            
                              0
                              ,
                              0
                            
                            i
                          
                        
                      
                      =
                      
                        
                          1
                          4
                        
                        ⁢
                        
                          
                            M
                            
                              0
                              ,
                              0
                            
                            i
                          
                          .
                        
                      
                    
                  
                
              
            
          
        
      
    
    
      
        (
        38
        )
      
    
  




Case 1





  
    
      
        
          (
          
            E
            -
            F
            -
            E
          
          )
        
        :
        
          
            consider
            ⁢
            
              
            
            ⁢
            2
            ⁢
            
              V
              
                0
                ,
                2
              
              
                i
                +
                1
              
            
          
          -
          
            V
            
              0
              ,
              3
            
            
              i
              +
              1
            
          
          -
          
            
              V
              
                0
                ,
                1
              
              
                i
                +
                1
              
            
            .
            
              

            
            ⁢
            
              
                
                  
                    
                      
                      
                        
                          2
                          ⁢
                          
                            V
                            
                              0
                              ,
                              2
                            
                            
                              i
                              +
                              1
                            
                          
                        
                        -
                        
                          V
                          
                            0
                            ,
                            3
                          
                          
                            i
                            +
                            1
                          
                        
                        -
                        
                          V
                          
                            0
                            ,
                            1
                          
                          
                            i
                            +
                            1
                          
                        
                      
                      
                    
                    =
                    
                    ⁢
                    
                      
                      
                        
                          1
                          16
                        
                        ⁢
                        
                          (
                          
                            
                              2
                              ⁢
                              
                                V
                                
                                  0
                                  ,
                                  2
                                
                                i
                              
                            
                            -
                            
                              V
                              
                                0
                                ,
                                3
                              
                              i
                            
                            -
                            
                              V
                              
                                0
                                ,
                                1
                              
                              i
                            
                            +
                            
                              2
                              ⁢
                              
                                V
                                
                                  0
                                  ,
                                  1
                                
                                i
                              
                            
                            -
                            
                              V
                              
                                0
                                ,
                                2
                              
                              i
                            
                            -
                            
                              V
                              
                                0
                                ,
                                0
                              
                              i
                            
                            +
                          
                        
                      
                    
                  
                
              
              
                
                  
                    
                      
                        
                        ⁢
                        
                          
                            2
                            ⁢
                            
                              V
                              
                                1
                                ,
                                2
                              
                              i
                            
                          
                          -
                          
                            V
                            
                              1
                              ,
                              3
                            
                            i
                          
                          -
                          
                            V
                            
                              1
                              ,
                              1
                            
                            i
                          
                          +
                          
                            2
                            ⁢
                            
                              V
                              
                                1
                                ,
                                1
                              
                              i
                            
                          
                          -
                          
                            V
                            
                              1
                              ,
                              2
                            
                            i
                          
                          -
                          
                            V
                            
                              1
                              ,
                              0
                            
                            i
                          
                        
                        )
                      
                      
                    
                    ≤
                  
                
              
              
                
                  
                    
                    ⁢
                    
                      
                        
                          
                            1
                            16
                          
                          ⁢
                          
                            M
                            
                              0
                              ,
                              0
                            
                            i
                          
                        
                        +
                        
                          
                            1
                            16
                          
                          ⁢
                          
                            M
                            
                              0
                              ,
                              0
                            
                            i
                          
                        
                        +
                        
                          
                            1
                            16
                          
                          ⁢
                          
                            M
                            
                              0
                              ,
                              0
                            
                            i
                          
                        
                        +
                        
                          
                            1
                            16
                          
                          ⁢
                          
                            M
                            
                              0
                              ,
                              0
                            
                            i
                          
                        
                      
                      =
                      
                        
                          1
                          4
                        
                        ⁢
                        
                          
                            M
                            
                              0
                              ,
                              0
                            
                            i
                          
                          .
                        
                      
                    
                  
                
              
            
          
        
      
    
    
      
        (
        39
        )
      
    
  




Case 2





  
    
      
        
          (
          
            E
            -
            V
            -
            E
          
          )
        
        :
        
          
            consider
            ⁢
            
              
            
            ⁢
            2
            ⁢
            
              V
              
                1
                ,
                1
              
              
                i
                +
                1
              
            
          
          -
          
            V
            
              1
              ,
              2
            
            
              i
              +
              1
            
          
          -
          
            
              V
              
                1
                ,
                0
              
              
                i
                +
                1
              
            
            .
            
              

            
            ⁢
            
              
                
                  
                    
                      
                      
                        
                          2
                          ⁢
                          
                            V
                            
                              1
                              ,
                              1
                            
                            
                              i
                              +
                              1
                            
                          
                        
                        -
                        
                          V
                          
                            1
                            ,
                            2
                          
                          
                            i
                            +
                            1
                          
                        
                        -
                        
                          V
                          
                            1
                            ,
                            0
                          
                          
                            i
                            +
                            1
                          
                        
                      
                      
                    
                    =
                    
                    ⁢
                    
                      
                      
                        
                          
                            1
                            32
                          
                          ⁢
                          
                            (
                            
                              
                                2
                                ⁢
                                
                                  V
                                  
                                    0
                                    ,
                                    1
                                  
                                  i
                                
                              
                              -
                              
                                V
                                
                                  0
                                  ,
                                  2
                                
                                i
                              
                              -
                              
                                V
                                
                                  0
                                  ,
                                  0
                                
                                i
                              
                            
                            )
                          
                        
                        +
                      
                    
                  
                
              
              
                
                  
                    
                    ⁢
                    
                      
                        
                          3
                          15
                        
                        ⁢
                        
                          (
                          
                            
                              2
                              ⁢
                              
                                V
                                
                                  1
                                  ,
                                  1
                                
                                i
                              
                            
                            -
                            
                              V
                              
                                1
                                ,
                                2
                              
                              i
                            
                            -
                            
                              V
                              
                                1
                                ,
                                0
                              
                              i
                            
                          
                          )
                        
                      
                      +
                    
                  
                
              
              
                
                  
                    
                      
                      ⁢
                      
                        
                          1
                          32
                        
                        ⁢
                        
                          (
                          
                            
                              2
                              ⁢
                              
                                V
                                
                                  2
                                  ,
                                  1
                                
                                i
                              
                            
                            -
                            
                              V
                              
                                2
                                ,
                                2
                              
                              i
                            
                            -
                            
                              V
                              
                                2
                                ,
                                0
                              
                              i
                            
                          
                          )
                        
                      
                      
                    
                    ≤
                  
                
              
              
                
                  
                    
                    ⁢
                    
                      
                        
                          
                            1
                            32
                          
                          ⁢
                          
                            M
                            
                              0
                              ,
                              0
                            
                            i
                          
                        
                        +
                        
                          
                            3
                            16
                          
                          ⁢
                          
                            M
                            
                              0
                              ,
                              0
                            
                            i
                          
                        
                        +
                        
                          
                            1
                            32
                          
                          ⁢
                          
                            M
                            
                              0
                              ,
                              0
                            
                            i
                          
                        
                      
                      =
                      
                        
                          1
                          4
                        
                        ⁢
                        
                          
                            M
                            
                              0
                              ,
                              0
                            
                            i
                          
                          .
                        
                      
                    
                  
                
              
            
          
        
      
    
    
      
        (
        40
        )
      
    
  




Case 3





  
    
      
        
          (
          
            V
            -
            E
            -
            V
          
          )
        
        :
        
          
            consider
            ⁢
            
              
            
            ⁢
            2
            ⁢
            
              V
              
                1
                ,
                2
              
              
                i
                +
                1
              
            
          
          -
          
            V
            
              1
              ,
              3
            
            
              i
              +
              1
            
          
          -
          
            
              V
              
                1
                ,
                1
              
              
                i
                +
                1
              
            
            .
            
              

            
            ⁢
            
              
                
                  
                    
                      
                      
                        
                          2
                          ⁢
                          
                            V
                            
                              1
                              ,
                              2
                            
                            
                              i
                              +
                              1
                            
                          
                        
                        -
                        
                          V
                          
                            1
                            ,
                            3
                          
                          
                            i
                            +
                            1
                          
                        
                        -
                        
                          V
                          
                            1
                            ,
                            1
                          
                          
                            i
                            +
                            1
                          
                        
                      
                      
                    
                    =
                    
                    ⁢
                    
                      
                      
                        
                          1
                          64
                        
                        ⁢
                        
                          (
                          
                            
                              2
                              ⁢
                              
                                V
                                
                                  0
                                  ,
                                  2
                                
                                i
                              
                            
                            -
                            
                              V
                              
                                0
                                ,
                                3
                              
                              i
                            
                            -
                            
                              V
                              
                                0
                                ,
                                1
                              
                              i
                            
                            +
                            
                              2
                              ⁢
                              
                                V
                                
                                  0
                                  ,
                                  1
                                
                                i
                              
                            
                            -
                            
                              V
                              
                                0
                                ,
                                2
                              
                              i
                            
                            -
                          
                        
                      
                    
                  
                
              
              
                
                  
                    
                      
                      ⁢
                      
                        V
                        
                          0
                          ,
                          0
                        
                      
                      )
                    
                    +
                    
                      
                        3
                        32
                      
                      ⁢
                      
                        (
                        
                          
                            2
                            ⁢
                            
                              V
                              
                                1
                                ,
                                2
                              
                              i
                            
                          
                          -
                          
                            V
                            
                              1
                              ,
                              3
                            
                            i
                          
                          -
                          
                            V
                            
                              1
                              ,
                              1
                            
                            i
                          
                          +
                          
                            2
                            ⁢
                            
                              V
                              
                                1
                                ,
                                1
                              
                              i
                            
                          
                          -
                        
                      
                    
                  
                
              
              
                
                  
                    
                      
                      ⁢
                      
                        
                          V
                          
                            1
                            ,
                            2
                          
                          i
                        
                        -
                        
                          V
                          
                            1
                            ,
                            0
                          
                          i
                        
                      
                      )
                    
                    +
                    
                      
                        1
                        64
                      
                      ⁢
                      
                        (
                        
                          
                            2
                            ⁢
                            
                              V
                              
                                2
                                ,
                                2
                              
                              i
                            
                          
                          -
                          
                            V
                            
                              2
                              ,
                              3
                            
                            i
                          
                          -
                          
                            V
                            
                              2
                              ,
                              1
                            
                            i
                          
                          +
                        
                      
                    
                  
                
              
              
                
                  
                    
                      
                        
                        ⁢
                        
                          
                            2
                            ⁢
                            
                              V
                              
                                2
                                ,
                                1
                              
                              i
                            
                          
                          -
                          
                            V
                            
                              2
                              ,
                              2
                            
                            i
                          
                          -
                          
                            V
                            
                              2
                              ,
                              0
                            
                            i
                          
                        
                        )
                      
                      
                    
                    ≤
                    
                      (
                      
                        
                          1
                          64
                        
                        +
                        
                          1
                          64
                        
                        +
                        
                          3
                          32
                        
                        +
                      
                    
                  
                
              
              
                
                  
                    
                      
                        
                        ⁢
                        
                          
                            3
                            32
                          
                          +
                          
                            1
                            64
                          
                          +
                          
                            1
                            64
                          
                        
                        )
                      
                      ⁢
                      
                        M
                        
                          0
                          ,
                          0
                        
                        i
                      
                    
                    =
                    
                      
                        1
                        4
                      
                      ⁢
                      
                        
                          M
                          
                            0
                            ,
                            0
                          
                          i
                        
                        .
                      
                    
                  
                
              
            
          
        
      
    
    
      
        (
        41
        )
      
    
  




Case 4

This completes the proof of the lemma.

Appendix B: Convergence of Vn2N+2, . . . , Vn2N+8 

Note that if one can prove that





  
    
      
        
          
            lim
            
              n
              →
              ∞
            
          
          ⁢
          
            
              (
              T
              )
            
            n
          
        
        =
        
          
            
              lim
              
                n
                →
                ∞
              
            
            ⁢
            
              
                (
                
                  
                    
                      
                        T
                        _
                      
                    
                    
                      0
                    
                  
                  
                    
                      
                        
                          T
                          _
                        
                        
                          1
                          ,
                          1
                        
                      
                    
                    
                      
                        
                          T
                          _
                        
                        
                          1
                          ,
                          2
                        
                      
                    
                  
                
                )
              
              n
            
          
          =
          
            
              T
              *
            
            ≡
            
              (
              
                
                  
                    
                      
                        T
                        _
                      
                      *
                    
                  
                  
                    0
                  
                
                
                  
                    
                      
                        T
                        _
                      
                      
                        1
                        ,
                        1
                      
                      *
                    
                  
                  
                    0
                  
                
              
              )
            
          
        
      
    
    
      
        (
        42
        )
      
    
  




where T* is defined in (15) and T*1,1 is a 7×(2N+1) version of T*, i.e.





  
    
      
        
          
            
              T
              _
            
            
              1
              ,
              1
            
            *
          
          =
          
            
              (
              
                
              
              ⁢
              
                
                  
                    
                      Δ
                      1
                    
                  
                  
                    
                      Δ
                      2
                    
                  
                  
                    ⋯
                  
                  
                    
                      Δ
                      
                        
                          2
                          ⁢
                          N
                        
                        +
                        1
                      
                    
                  
                
                
                  
                    
                      Δ
                      1
                    
                  
                  
                    
                      Δ
                      2
                    
                  
                  
                    ⋯
                  
                  
                    
                      Δ
                      
                        
                          2
                          ⁢
                          N
                        
                        +
                        1
                      
                    
                  
                
                
                  
                    ⋮
                  
                  
                    ⋮
                  
                  
                    ⋰
                  
                  
                    ⋮
                  
                
                
                  
                    
                      Δ
                      1
                    
                  
                  
                    
                      Δ
                      2
                    
                  
                  
                    ⋯
                  
                  
                    
                      Δ
                      
                        
                          2
                          ⁢
                          N
                        
                        +
                        1
                      
                    
                  
                
              
              ⁢
              
                
              
              )
            
            
              7
              ×
              
                (
                
                  
                    2
                    ⁢
                    N
                  
                  +
                  1
                
                )
              
            
          
        
        ,
      
    
    
      
        (
        43
        )
      
    
  




then, by (9) we have

Vjn→V1*≡Δ1V1+Δ2V2+ . . . +Δ2N+1V2N+1 

for j=2N+2, 2N+3, . . . , 2N+8. Hence, to prove that Vn2N+2, . . . , Vn2N+8 converge to V*1, it is sufficient to show that (42) is true, or, equivalently, to show that (i) ( T1,2)n converges to a 7×7 zero matrix when n tends to infinity, and (ii) the lower-left 7×(2N+1) block of (T)2n converges to T*1,1. (I) is obvious because T1,2 contains non-negative entries and the sum of each row is smaller than one. To prove (ii), note that the sum of each row of (7)n is one and, from (i),

( T1,2)n→0.

Therefore, for each of the last 7 rows of (T)n, the sum of the first 2N+1 entries is close to one when n is large. On the other hand, when n is large, (15) is true, i.e. each column of ( T)n has almost identical entries. Hence, computing an entry of the lower-left 7×(2N+1) block of (T)2n=(T)n(T)n is like multiplying 2N+1 almost identical entries (in the same column of the upper-left (2N+1)×(2N+1) block of the second (T)n by 2N+1 non-negative numbers whose sum is close to one (in the same row of the lower-left 7×(2N+1) block of the first (T)n. Consequently the value of that entry in the lower-left 7×(2N+1) block of (T)2n=(T)n (T)n is close to the first 2N+1 almost identical entries in the same column of the second (T)n and this completes the proof of (ii).

Appendix C: Rate of Convergence of Φkj 

In this appendix we prove Lemma 5. Since Φkj is symmetric to Φk3, we only need to consider Gk0, Gk2, and Gk3 for the lemma.
(i) Gk0. For an edge point such as Vi+14, we have




  
    
      
        
          
            
              
                
                
                  
                    V
                    1
                    
                      i
                      +
                      1
                    
                  
                  -
                  
                    V
                    4
                    
                      i
                      +
                      1
                    
                  
                
                
              
              =
              
              ⁢
              
                
                
                  
                    
                      ∑
                      
                        j
                        =
                        4
                      
                      N
                    
                    ⁢
                    
                      
                    
                    ⁢
                    
                      
                        3
                        
                          2
                          ⁢
                          
                            N
                            2
                          
                        
                      
                      ⁢
                      
                        (
                        
                          
                            V
                            
                              2
                              ⁢
                              j
                            
                            i
                          
                          -
                          
                            V
                            1
                            i
                          
                        
                        )
                      
                    
                  
                  +
                  
                    
                      ∑
                      
                        j
                        =
                        3
                      
                      N
                    
                    ⁢
                    
                      
                    
                    ⁢
                    
                      
                        1
                        
                          4
                          ⁢
                          
                            N
                            2
                          
                        
                      
                      ⁢
                      
                        (
                        
                          
                            V
                            
                              
                                2
                                ⁢
                                j
                              
                              +
                              1
                            
                            i
                          
                          -
                        
                      
                    
                  
                
              
            
          
        
        
          
            
              
                
                ⁢
                
                  V
                  1
                  i
                
                )
              
              +
              
                
                  (
                  
                    
                      3
                      
                        2
                        ⁢
                        
                          N
                          2
                        
                      
                    
                    -
                    
                      1
                      16
                    
                  
                  )
                
                ⁢
                
                  (
                  
                    
                      V
                      2
                      i
                    
                    -
                    
                      V
                      1
                      i
                    
                  
                  )
                
              
              +
              
                (
                
                  
                    1
                    
                      4
                      ⁢
                      
                        N
                        2
                      
                    
                  
                  -
                
              
            
          
        
        
          
            
              
                
                  
                  ⁢
                  
                    1
                    16
                  
                  )
                
                ⁢
                
                  (
                  
                    
                      V
                      3
                      i
                    
                    -
                    
                      V
                      1
                      i
                    
                  
                  )
                
              
              +
              
                
                  (
                  
                    
                      3
                      
                        2
                        ⁢
                        
                          N
                          2
                        
                      
                    
                    -
                    
                      3
                      8
                    
                  
                  )
                
                ⁢
                
                  (
                  
                    
                      V
                      4
                      i
                    
                    -
                    
                      V
                      1
                      i
                    
                  
                  )
                
              
              +
            
          
        
        
          
            
              
              ⁢
              
                
                  
                    (
                    
                      
                        1
                        
                          4
                          ⁢
                          
                            N
                            2
                          
                        
                      
                      -
                      
                        1
                        16
                      
                    
                    )
                  
                  ⁢
                  
                    (
                    
                      
                        V
                        5
                        i
                      
                      -
                      
                        V
                        1
                        i
                      
                    
                    )
                  
                
                +
                
                  
                    (
                    
                      
                        3
                        
                          2
                          ⁢
                          
                            N
                            2
                          
                        
                      
                      -
                      
                        1
                        16
                      
                    
                    )
                  
                  ⁢
                  
                    (
                    
                      
                        V
                        6
                        i
                      
                      -
                    
                  
                
              
            
          
        
        
          
            
              
                
                ⁢
                
                  V
                  1
                  i
                
                
              
              ≤
              
                [
                
                  
                    
                      ∑
                      
                        j
                        =
                        4
                      
                      N
                    
                    ⁢
                    
                      3
                      
                        2
                        ⁢
                        
                          N
                          2
                        
                      
                    
                  
                  +
                  
                    
                      ∑
                      
                        j
                        =
                        3
                      
                      N
                    
                    ⁢
                    
                      
                    
                    ⁢
                    
                      1
                      
                        4
                        ⁢
                        
                          N
                          2
                        
                      
                    
                  
                  +
                  
                    
                    
                      2
                      ⁢
                      
                        (
                        
                          
                            3
                            
                              2
                              ⁢
                              
                                N
                                2
                              
                            
                          
                          -
                        
                      
                    
                  
                
              
            
          
        
        
          
            
              
                
                  
                    
                      
                      ⁢
                      
                        1
                        16
                      
                      )
                    
                    
                  
                  +
                  
                    (
                    
                      
                        3
                        8
                      
                      -
                      
                        3
                        
                          2
                          ⁢
                          
                            N
                            2
                          
                        
                      
                    
                    )
                  
                  +
                  
                    2
                    ⁢
                    
                      (
                      
                        
                          1
                          16
                        
                        -
                        
                          1
                          
                            4
                            ⁢
                            
                              N
                              2
                            
                          
                        
                      
                      )
                    
                  
                
                ]
              
              ⁢
              
                G
                0
                i
              
            
          
        
        
          
            
              =
              
              ⁢
              
                {
                
                  
                    
                      
                        
                          
                            (
                            
                              
                                3
                                8
                              
                              +
                              
                                7
                                
                                  4
                                  ⁢
                                  N
                                
                              
                              -
                              
                                4
                                
                                  N
                                  2
                                
                              
                            
                            )
                          
                          ⁢
                          
                            G
                            0
                            i
                          
                        
                        ,
                        
                          
                        
                        ⁢
                        
                          
                            if
                            ⁢
                            
                              
                            
                            ⁢
                            N
                          
                          =
                          3
                        
                      
                    
                  
                  
                    
                      
                        
                          
                            (
                            
                              
                                5
                                8
                              
                              +
                              
                                7
                                
                                  4
                                  ⁢
                                  N
                                
                              
                              -
                              
                                10
                                
                                  N
                                  2
                                
                              
                            
                            )
                          
                          ⁢
                          
                            G
                            0
                            i
                          
                        
                        ,
                        
                          
                        
                        ⁢
                        
                          
                            if
                            ⁢
                            
                              
                            
                            ⁢
                            N
                          
                          ≥
                          5
                        
                      
                    
                  
                
              
            
          
        
      
    
    
      
        (
        44
        )
      
    
  




where Gi0 is defined in (20).

For a face point such as Vi+13, we have




  
    
      
        
          
          
            
              V
              1
              
                i
                +
                1
              
            
            -
            
              V
              3
              
                i
                +
                1
              
            
          
          
        
        =
        
          
          
            
          
          ⁢
          
            
              
                
                  
                    
                      ∑
                      
                        j
                        =
                        3
                      
                      N
                    
                    ⁢
                    
                      
                    
                    ⁢
                    
                      
                        3
                        
                          2
                          ⁢
                          
                            
                          
                          ⁢
                          
                            N
                            2
                          
                        
                      
                      ⁢
                      
                        (
                        
                          
                            V
                            
                              2
                              ⁢
                              
                                
                              
                              ⁢
                              j
                            
                            i
                          
                          -
                          
                            V
                            1
                            i
                          
                        
                        )
                      
                    
                  
                  +
                  
                    
                      ∑
                      
                        j
                        =
                        3
                      
                      N
                    
                    ⁢
                    
                      
                    
                    ⁢
                    
                      
                        1
                        
                          4
                          ⁢
                          
                            
                          
                          ⁢
                          
                            N
                            2
                          
                        
                      
                      ⁢
                      
                        (
                        
                          
                            V
                            
                              
                                2
                                ⁢
                                
                                  
                                
                                ⁢
                                j
                              
                              +
                              1
                            
                            i
                          
                          -
                          
                            V
                            1
                            i
                          
                        
                        )
                      
                    
                  
                  +
                  
                    
                      (
                      
                        
                          3
                          
                            2
                            ⁢
                            
                              
                            
                            ⁢
                            
                              N
                              2
                            
                          
                        
                        -
                        
                          1
                          4
                        
                      
                      )
                    
                    ⁢
                    
                      (
                      
                        
                          V
                          2
                          i
                        
                        -
                        
                          V
                          1
                          i
                        
                      
                      )
                    
                  
                  +
                  
                    
                      (
                      
                        
                          1
                          
                            4
                            ⁢
                            
                              
                            
                            ⁢
                            
                              N
                              2
                            
                          
                        
                        -
                        
                          1
                          4
                        
                      
                      )
                    
                    ⁢
                    
                      (
                      
                        
                          V
                          3
                          i
                        
                        -
                        
                          V
                          1
                          i
                        
                      
                      )
                    
                  
                  +
                  
                    
                      (
                      
                        
                          3
                          
                            2
                            ⁢
                            
                              
                            
                            ⁢
                            
                              N
                              2
                            
                          
                        
                        -
                        
                          1
                          4
                        
                      
                      )
                    
                    ⁢
                    
                      (
                      
                        
                          V
                          4
                          i
                        
                        -
                        
                          V
                          1
                          i
                        
                      
                      )
                    
                  
                
                ≤
                
                  
                    [
                    
                      
                    
                    ⁢
                    
                      
                        
                          ∑
                          
                            j
                            =
                            3
                          
                          N
                        
                        ⁢
                        
                          
                        
                        ⁢
                        
                          3
                          
                            2
                            ⁢
                            
                              
                            
                            ⁢
                            
                              N
                              2
                            
                          
                        
                      
                      +
                      
                        
                          ∑
                          
                            j
                            =
                            2
                          
                          N
                        
                        ⁢
                        
                          
                        
                        ⁢
                        
                          1
                          
                            4
                            ⁢
                            
                              
                            
                            ⁢
                            
                              N
                              2
                            
                          
                        
                      
                      +
                      
                        2
                        ⁢
                        
                          (
                          
                            
                              1
                              4
                            
                            -
                            
                              3
                              
                                2
                                ⁢
                                
                                  
                                
                                ⁢
                                
                                  N
                                  2
                                
                              
                            
                          
                          )
                        
                      
                      +
                      
                        1
                        4
                      
                      -
                      
                        1
                        
                          4
                          ⁢
                          
                            
                          
                          ⁢
                          
                            N
                            2
                          
                        
                      
                    
                    ]
                  
                  ⁢
                  
                    G
                    0
                    i
                  
                
              
              =
              
                
                  (
                  
                    
                      3
                      4
                    
                    +
                    
                      7
                      
                        4
                        ⁢
                        
                          
                        
                        ⁢
                        N
                      
                    
                    -
                    
                      13
                      
                        2
                        ⁢
                        
                          
                        
                        ⁢
                        
                          N
                          2
                        
                      
                    
                  
                  )
                
                ⁢
                
                  G
                  0
                  i
                
              
            
            ,
            
              
            
            ⁢
            
              N
              =
              
                
                  3
                  ⁢
                  
                    
                  
                  ⁢
                  or
                  ⁢
                  
                    
                  
                  ⁢
                  N
                
                ≥
                5.
              
            
          
        
      
    
    
      
        (
        45
        )
      
    
  




The other cases are similar to (44) or (45). Hence, we have the following inequality for N=3 or N≧5:





  
    
      
        
          G
          0
          
            i
            +
            1
          
        
        ≤
        
          
            (
            
              
                3
                4
              
              +
              
                7
                
                  4
                  ⁢
                  
                    
                  
                  ⁢
                  N
                
              
              -
              
                13
                
                  2
                  ⁢
                  
                    
                  
                  ⁢
                  
                    N
                    2
                  
                
              
            
            )
          
          ⁢
          
            G
            0
            i
          
        
        ≤
        
          
            
              (
              
                
                  3
                  4
                
                +
                
                  7
                  
                    4
                    ⁢
                    
                      
                    
                    ⁢
                    N
                  
                
                -
                
                  13
                  
                    2
                    ⁢
                    
                      
                    
                    ⁢
                    
                      N
                      2
                    
                  
                
              
              )
            
            
              i
              +
              1
            
          
          ⁢
          
            
              G
              0
              0
            
            .
          
        
      
    
    
      
        (
        46
        )
      
    
  




(ii) Gk3. For an edge point such as Vi+12N+8, we have





  
    
      
        
          
          
            
              V
              4
              
                i
                +
                1
              
            
            -
            
              V
              
                
                  2
                  ⁢
                  
                    
                  
                  ⁢
                  N
                
                +
                8
              
              
                i
                +
                1
              
            
          
          
        
        =
        
          
            
            
              
                
                  1
                  16
                
                ⁢
                
                  (
                  
                    
                      V
                      
                        
                          2
                          ⁢
                          
                            
                          
                          ⁢
                          N
                        
                        +
                        8
                      
                      i
                    
                    +
                    
                      V
                      
                        
                          2
                          ⁢
                          
                            
                          
                          ⁢
                          N
                        
                        +
                        7
                      
                      i
                    
                    -
                    
                      V
                      6
                      i
                    
                    -
                    
                      V
                      5
                      i
                    
                  
                  )
                
              
              +
              
                
                  5
                  16
                
                ⁢
                
                  (
                  
                    
                      V
                      3
                      i
                    
                    -
                    
                      V
                      1
                      i
                    
                  
                  )
                
              
            
            
          
          ≤
          
            
            
              
                
                  1
                  16
                
                ⁢
                
                  (
                  
                    
                      V
                      
                        
                          2
                          ⁢
                          
                            
                          
                          ⁢
                          N
                        
                        +
                        8
                      
                      i
                    
                    -
                    
                      V
                      4
                      i
                    
                  
                  )
                
              
              +
              
                
                  1
                  16
                
                ⁢
                
                  (
                  
                    
                      V
                      
                        
                          2
                          ⁢
                          
                            
                          
                          ⁢
                          N
                        
                        +
                        7
                      
                      i
                    
                    -
                    
                      V
                      4
                      i
                    
                  
                  )
                
              
              +
              
                
                  1
                  16
                
                ⁢
                
                  (
                  
                    
                      V
                      4
                      i
                    
                    -
                    
                      V
                      6
                      i
                    
                  
                  )
                
              
              +
              
                
                  1
                  16
                
                ⁢
                
                  (
                  
                    
                      V
                      4
                      i
                    
                    -
                    
                      V
                      5
                      i
                    
                  
                  )
                
              
              +
              
                
                  5
                  16
                
                ⁢
                
                  (
                  
                    
                      V
                      3
                      i
                    
                    -
                    
                      V
                      1
                      i
                    
                  
                  )
                
              
            
            
          
          ≤
          
            
              9
              16
            
            ⁢
            max
            ⁢
            
              {
              
                
                  G
                  0
                  i
                
                ,
                
                  G
                  3
                  i
                
              
              }
            
          
        
      
    
    
      
        (
        47
        )
      
    
  




where Gi0 and Gi3 are defined in (20).

For a face point such as Vi+13, we have




  
    
      
        
          
          
            
              V
              4
              
                i
                +
                1
              
            
            -
            
              V
              3
              
                i
                +
                1
              
            
          
          
        
        =
        
          
            
            
              
                
                  3
                  16
                
                ⁢
                
                  (
                  
                    
                      V
                      2
                      i
                    
                    +
                    
                      V
                      3
                      i
                    
                  
                  )
                
              
              -
              
                
                  1
                  16
                
                ⁢
                
                  (
                  
                    
                      V
                      6
                      i
                    
                    +
                    
                      V
                      5
                      i
                    
                  
                  )
                
              
              -
              
                
                  1
                  8
                
                ⁢
                
                  (
                  
                    
                      V
                      1
                      i
                    
                    +
                    
                      V
                      4
                      i
                    
                  
                  )
                
              
            
            
          
          ≤
          
            
            
              
                
                  3
                  16
                
                ⁢
                
                  (
                  
                    
                      V
                      2
                      i
                    
                    -
                    
                      V
                      1
                      i
                    
                  
                  )
                
              
              +
              
                
                  3
                  16
                
                ⁢
                
                  (
                  
                    
                      V
                      3
                      i
                    
                    -
                    
                      V
                      4
                      i
                    
                  
                  )
                
              
              +
              
                
                  1
                  16
                
                ⁢
                
                  (
                  
                    
                      V
                      1
                      i
                    
                    -
                    
                      V
                      6
                      i
                    
                  
                  )
                
              
              +
              
                
                  1
                  16
                
                ⁢
                
                  (
                  
                    
                      V
                      4
                      i
                    
                    -
                    
                      V
                      5
                      i
                    
                  
                  )
                
              
            
            
          
          ≤
          
            
              1
              2
            
            ⁢
            max
            ⁢
            
              
                {
                
                  
                    G
                    0
                    i
                  
                  ,
                  
                    G
                    3
                    i
                  
                
                }
              
              .
            
          
        
      
    
    
      
        (
        48
        )
      
    
  




For a vertex point such as Vi+12N+7, we have




  
    
      
        
          
          
            
              V
              4
              
                i
                +
                1
              
            
            -
            
              V
              
                
                  2
                  ⁢
                  
                    
                  
                  ⁢
                  N
                
                +
                7
              
              
                i
                +
                1
              
            
          
          
        
        =
        
          
          
            
              
                3
                16
              
              ⁢
              
                (
                
                  
                    V
                    4
                    i
                  
                  -
                  
                    
                      9
                      32
                    
                    ⁢
                    
                      V
                      1
                      i
                    
                  
                  +
                  
                    
                      1
                      32
                    
                    ⁢
                    
                      (
                      
                        
                          V
                          3
                          i
                        
                        +
                        
                          V
                          5
                          i
                        
                      
                      )
                    
                  
                  +
                  
                    
                      3
                      32
                    
                    ⁢
                    
                      V
                      
                        
                          2
                          ⁢
                          
                            
                          
                          ⁢
                          N
                        
                        +
                        7
                      
                      i
                    
                  
                  -
                  
                    
                      3
                      64
                    
                    ⁢
                    
                      (
                      
                        
                          V
                          6
                          i
                        
                        +
                        
                          V
                          2
                          i
                        
                      
                      )
                    
                  
                  +
                  
                    
                      1
                      64
                    
                    ⁢
                    
                      (
                      
                        
                          V
                          
                            
                              2
                              ⁢
                              
                                
                              
                              ⁢
                              N
                            
                            +
                            8
                          
                          i
                        
                        +
                        
                          V
                          
                            
                              2
                              ⁢
                              
                                
                              
                              ⁢
                              N
                            
                            +
                            6
                          
                          i
                        
                      
                      )
                    
                  
                
                
              
            
            ≤
            
              
              
                
                  
                    
                      1
                      64
                    
                    ⁢
                    
                      (
                      
                        
                          V
                          
                            
                              2
                              ⁢
                              
                                
                              
                              ⁢
                              N
                            
                            +
                            8
                          
                          i
                        
                        -
                        
                          V
                          4
                          i
                        
                      
                      )
                    
                  
                  +
                  
                    
                      3
                      32
                    
                    ⁢
                    
                      (
                      
                        
                          V
                          
                            
                              2
                              ⁢
                              
                                
                              
                              ⁢
                              N
                            
                            +
                            7
                          
                          i
                        
                        -
                        
                          V
                          4
                          i
                        
                      
                      )
                    
                  
                  +
                  
                    
                      1
                      64
                    
                    ⁢
                    
                      (
                      
                        
                          V
                          
                            
                              2
                              ⁢
                              
                                
                              
                              ⁢
                              N
                            
                            +
                            6
                          
                          i
                        
                        -
                        
                          V
                          4
                          i
                        
                      
                      )
                    
                  
                  +
                  
                    
                      9
                      32
                    
                    ⁢
                    
                      (
                      
                        
                          V
                          4
                          i
                        
                        -
                        
                          V
                          1
                          i
                        
                      
                      )
                    
                  
                  +
                  
                    
                      3
                      64
                    
                    ⁢
                    
                      (
                      
                        
                          V
                          1
                          i
                        
                        -
                        
                          V
                          6
                          i
                        
                      
                      )
                    
                  
                  +
                  
                    
                      3
                      64
                    
                    ⁢
                    
                      (
                      
                        
                          V
                          1
                          i
                        
                        -
                        
                          V
                          2
                          i
                        
                      
                      )
                    
                  
                  +
                  
                    
                      1
                      32
                    
                    ⁢
                    
                      (
                      
                        
                          V
                          3
                          i
                        
                        -
                        
                          V
                          1
                          i
                        
                      
                      )
                    
                  
                  +
                  
                    
                      1
                      32
                    
                    ⁢
                    
                      (
                      
                        
                          V
                          5
                          i
                        
                        -
                        
                          V
                          1
                          i
                        
                      
                      )
                    
                  
                
                ⪯
                
                  
                    9
                    16
                  
                  ⁢
                  max
                  ⁢
                  
                    
                      {
                      
                        
                          G
                          0
                          i
                        
                        ,
                        
                          G
                          3
                          i
                        
                      
                      }
                    
                    .
                  
                
              
            
          
        
      
    
    
      
        (
        49
        )
      
    
  




The other cases are similar to these cases. Hence, by combining the results of (47), (48), and (49), we have





  
    
      
        
          G
          3
          
            i
            +
            3
          
        
        ≤
        
          
            9
            16
          
          ⁢
          max
          ⁢
          
            {
            
              
                G
                0
                i
              
              ,
              
                G
                3
                i
              
            
            }
          
        
        ≤
        
          
            9
            16
          
          ⁢
          
            
              (
              
                
                  3
                  4
                
                +
                
                  7
                  
                    4
                    ⁢
                    
                      
                    
                    ⁢
                    N
                  
                
                -
                
                  13
                  
                    2
                    ⁢
                    
                      
                    
                    ⁢
                    
                      N
                      2
                    
                  
                
              
              )
            
            i
          
          ⁢
          max
          ⁢
          
            
              {
              
                
                  G
                  0
                  0
                
                ,
                
                  G
                  3
                  0
                
              
              }
            
            .
          
        
      
    
    
      
        (
        50
        )
      
    
  




The second inequality of (50) follows from (46). (50) works for N=3 or N≧5.

(iii) Gk2. For an edge point such as Vi+12N+6, we have





  
    
      
        
          
          
            
              V
              
                
                  2
                  ⁢
                  
                    
                  
                  ⁢
                  N
                
                +
                6
              
              
                i
                +
                1
              
            
            -
            
              V
              5
              
                i
                +
                1
              
            
          
          
        
        =
        
          
            
            
              
                
                  -
                  
                    3
                    16
                  
                
                ⁢
                
                  (
                  
                    
                      V
                      1
                      i
                    
                    +
                    
                      V
                      6
                      i
                    
                  
                  )
                
              
              +
              
                
                  1
                  8
                
                ⁢
                
                  (
                  
                    
                      V
                      4
                      i
                    
                    +
                    
                      V
                      5
                      i
                    
                  
                  )
                
              
              +
              
                
                  1
                  16
                
                ⁢
                
                  (
                  
                    
                      V
                      
                        
                          2
                          ⁢
                          
                            
                          
                          ⁢
                          N
                        
                        +
                        7
                      
                      i
                    
                    +
                    
                      V
                      
                        
                          2
                          ⁢
                          
                            
                          
                          ⁢
                          N
                        
                        +
                        6
                      
                      i
                    
                  
                  )
                
              
            
            
          
          =
          
            
              
              
                
                  
                    3
                    16
                  
                  ⁢
                  
                    (
                    
                      
                        V
                        4
                        i
                      
                      -
                      
                        V
                        1
                        i
                      
                    
                    )
                  
                
                +
                
                  
                    3
                    16
                  
                  ⁢
                  
                    (
                    
                      
                        V
                        5
                        i
                      
                      -
                      
                        V
                        6
                        i
                      
                    
                    )
                  
                
                +
                
                  
                    1
                    16
                  
                  ⁢
                  
                    (
                    
                      
                        V
                        
                          
                            2
                            ⁢
                            
                              
                            
                            ⁢
                            N
                          
                          +
                          7
                        
                        i
                      
                      -
                      
                        V
                        4
                        i
                      
                    
                    )
                  
                
                +
                
                  
                    1
                    16
                  
                  ⁢
                  
                    (
                    
                      
                        V
                        
                          
                            2
                            ⁢
                            
                              
                            
                            ⁢
                            N
                          
                          +
                          6
                        
                        i
                      
                      -
                      
                        V
                        5
                        i
                      
                    
                    )
                  
                
              
              
            
            ≤
            
              
                1
                2
              
              ⁢
              max
              ⁢
              
                
                  {
                  
                    
                      G
                      1
                      i
                    
                    ,
                    
                      G
                      2
                      i
                    
                    ,
                    
                      G
                      3
                      i
                    
                  
                  }
                
                .
              
            
          
        
      
    
    
      
        (
        51
        )
      
    
  




For a vertex point such as Vi+12N+2, we have




  
    
      
        
          
          
            
              V
              
                
                  2
                  ⁢
                  
                    
                  
                  ⁢
                  N
                
                +
                2
              
              
                i
                +
                1
              
            
            -
            
              V
              5
              
                i
                +
                1
              
            
          
          
        
        =
        
          
            
            
              
                
                  3
                  32
                
                ⁢
                
                  (
                  
                    
                      V
                      
                        
                          2
                          ⁢
                          
                            
                          
                          ⁢
                          N
                        
                        +
                        6
                      
                      i
                    
                    -
                    
                      V
                      5
                      i
                    
                  
                  )
                
              
              -
              
                
                  1
                  64
                
                ⁢
                
                  (
                  
                    
                      V
                      
                        
                          2
                          ⁢
                          
                            
                          
                          ⁢
                          N
                        
                        +
                        2
                      
                      i
                    
                    -
                    
                      V
                      5
                      i
                    
                  
                  )
                
              
              -
              
                
                  3
                  32
                
                ⁢
                
                  (
                  
                    
                      V
                      
                        
                          2
                          ⁢
                          
                            
                          
                          ⁢
                          N
                        
                        +
                        3
                      
                      i
                    
                    +
                    
                      V
                      5
                      i
                    
                  
                  )
                
              
              +
              
                
                  1
                  64
                
                ⁢
                
                  (
                  
                    
                      V
                      
                        
                          2
                          ⁢
                          
                            
                          
                          ⁢
                          N
                        
                        +
                        4
                      
                      i
                    
                    -
                    
                      V
                      6
                      i
                    
                  
                  )
                
              
              +
              
                
                  1
                  64
                
                ⁢
                
                  (
                  
                    
                      V
                      
                        
                          2
                          ⁢
                          
                            
                          
                          ⁢
                          N
                        
                        +
                        7
                      
                      i
                    
                    -
                    
                      V
                      4
                      i
                    
                  
                  )
                
              
              +
              
                
                  9
                  64
                
                ⁢
                
                  (
                  
                    
                      V
                      5
                      i
                    
                    -
                    
                      V
                      6
                      i
                    
                  
                  )
                
              
              +
              
                
                  9
                  64
                
                ⁢
                
                  (
                  
                    
                      V
                      5
                      i
                    
                    -
                    
                      V
                      4
                      i
                    
                  
                  )
                
              
              +
              
                
                  15
                  64
                
                ⁢
                
                  (
                  
                    
                      V
                      5
                      i
                    
                    -
                    
                      V
                      1
                      i
                    
                  
                  )
                
              
            
            
          
          ≤
          
            
              3
              4
            
            ⁢
            max
            ⁢
            
              
                {
                
                  
                    G
                    1
                    i
                  
                  ,
                  
                    G
                    2
                    i
                  
                  ,
                  
                    G
                    3
                    i
                  
                
                }
              
              .
            
          
        
      
    
    
      
        (
        52
        )
      
    
  




The other cases are similar to these two cases. Hence, by combining the results of (51), (52), (46), and (50), we have





  
    
      
        
          
            
              
                G
                2
                
                  i
                  +
                  1
                
              
              ≤
              
              ⁢
              
                
                  3
                  4
                
                ⁢
                max
                ⁢
                
                  {
                  
                    
                      G
                      1
                      i
                    
                    ,
                    
                      G
                      2
                      i
                    
                    ,
                    
                      G
                      3
                      i
                    
                  
                  }
                
              
            
          
        
        
          
            
              ≤
              
              ⁢
              
                {
                
                  
                
                ⁢
                
                  
                    
                      
                        
                          
                            
                              (
                              
                                3
                                4
                              
                              )
                            
                            
                              i
                              +
                              1
                            
                          
                          ⁢
                          
                            G
                            0
                          
                        
                        ,
                      
                    
                    
                      
                        
                          if
                          ⁢
                          
                            
                          
                          ⁢
                          N
                        
                        =
                        3
                      
                    
                  
                  
                    
                      
                        
                          
                            (
                            
                              3
                              4
                            
                            )
                          
                          ⁢
                          
                            
                              (
                              
                                
                                  
                                    3
                                    ⁢
                                    
                                      
                                    
                                    ⁢
                                    
                                      N
                                      2
                                    
                                  
                                  +
                                  
                                    7
                                    ⁢
                                    
                                      
                                    
                                    ⁢
                                    N
                                  
                                  -
                                  26
                                
                                
                                  4
                                  ⁢
                                  
                                    
                                  
                                  ⁢
                                  
                                    N
                                    2
                                  
                                
                              
                              )
                            
                            i
                          
                          ⁢
                          
                            G
                            0
                          
                        
                        ,
                      
                    
                    
                      
                        
                          if
                          ⁢
                          
                            
                          
                          ⁢
                          N
                        
                        ≥
                        5
                      
                    
                  
                
                ⁢
                
                  
                
              
            
          
        
      
    
    
      
        (
        53
        )
      
    
  




where G0=max {G00, G01, G02, G03}. The lemma now follows from (46), (50), and (53).

Appendix D: Proof of (27)

The proof of Lemma 3 shows that the norms of most of the second order forward differences of the control points of Πk3 satisfy the inequality

∥2A−B−C∥≦1⁄4Z0k−1 

except 2Vk1−Vk2−Vk6, 2Vk6−Vk1−Vk2N+4, and 2Vk4−Vk1−Vk2N+7. The last two cases are similar. Hence, we only need consider the first two cases.

In the second case, we have




  
    
      
      
        
          2
          ⁢
          
            
          
          ⁢
          
            V
            6
            
              i
              +
              1
            
          
        
        -
        
          V
          1
          
            i
            +
            1
          
        
        -
        
          V
          
            
              2
              ⁢
              
                
              
              ⁢
              N
            
            +
            4
          
          
            i
            +
            1
          
        
      
      
    
    =
    
      
        
        
          
            1
            
              64
              ⁢
              
                
              
              ⁢
              
                N
                2
              
            
          
          ⁢
          
            {
            
              
                
                  N
                  2
                
                ⁡
                
                  (
                  
                    
                      2
                      ⁢
                      
                        
                      
                      ⁢
                      
                        V
                        7
                        i
                      
                    
                    -
                    
                      V
                      8
                      i
                    
                    -
                    
                      V
                      
                        
                          2
                          ⁢
                          
                            
                          
                          ⁢
                          N
                        
                        +
                        5
                      
                      i
                    
                  
                  )
                
              
              +
              
                
                  N
                  2
                
                ⁡
                
                  (
                  
                    
                      2
                      ⁢
                      
                        
                      
                      ⁢
                      
                        V
                        5
                        i
                      
                    
                    -
                    
                      V
                      
                        
                          2
                          ⁢
                          
                            
                          
                          ⁢
                          N
                        
                        +
                        3
                      
                      i
                    
                    -
                    
                      V
                      4
                      i
                    
                  
                  )
                
              
              +
              
                6
                ⁢
                
                  
                
                ⁢
                
                  
                    N
                    2
                  
                  (
                  
                    
                  
                  ⁢
                  
                    
                      2
                      ⁢
                      
                        
                      
                      ⁢
                      
                        V
                        6
                        i
                      
                    
                    -
                    
                      V
                      1
                      i
                    
                    -
                    
                      V
                      
                        
                          2
                          ⁢
                          
                            
                          
                          ⁢
                          N
                        
                        +
                        4
                      
                      i
                    
                  
                  )
                
              
              +
              
                8
                ⁢
                
                  
                    ∑
                    
                      j
                      =
                      1
                    
                    N
                  
                  ⁢
                  
                    
                  
                  ⁢
                  
                    (
                    
                      
                        2
                        ⁢
                        
                          
                        
                        ⁢
                        
                          V
                          
                            2
                            ⁡
                            
                              [
                              
                                
                                  j
                                  ⁢
                                  %
                                  ⁢
                                  N
                                
                                +
                                1
                              
                              ]
                            
                          
                          i
                        
                      
                      -
                      
                        V
                        
                          
                            2
                            ⁢
                            
                              
                            
                            ⁢
                            j
                          
                          +
                          1
                        
                        i
                      
                      -
                      
                        V
                        
                          2
                          ⁡
                          
                            [
                            
                              
                                j
                                ⁢
                                %
                                ⁢
                                N
                              
                              +
                              1
                            
                            ]
                          
                        
                        i
                      
                    
                    )
                  
                
              
              +
              
                
                  (
                  
                    
                      8
                      ⁢
                      
                        
                      
                      ⁢
                      
                        N
                        2
                      
                    
                    -
                    56
                  
                  )
                
                ⁢
                
                  (
                  
                    
                      
                        -
                        2
                      
                      ⁢
                      
                        
                      
                      ⁢
                      
                        V
                        1
                        i
                      
                    
                    +
                    
                      V
                      4
                      i
                    
                    +
                    
                      V
                      8
                      i
                    
                  
                  )
                
              
              +
              
                56
                ⁢
                
                  
                    ∑
                    
                      j
                      =
                      3
                    
                    
                      N
                      +
                      1
                    
                  
                  ⁢
                  
                    
                  
                  ⁢
                  
                    (
                    
                      
                        2
                        ⁢
                        
                          
                        
                        ⁢
                        
                          V
                          1
                          i
                        
                      
                      -
                      
                        V
                        
                          2
                          ⁡
                          
                            [
                            
                              
                                
                                  (
                                  
                                    j
                                    -
                                    1
                                  
                                  )
                                
                                ⁢
                                %
                                ⁢
                                
                                  
                                
                                ⁢
                                N
                              
                              +
                              1
                            
                            ]
                          
                        
                        i
                      
                      -
                      
                        V
                        
                          2
                          ⁡
                          
                            [
                            
                              
                                
                                  (
                                  
                                    j
                                    +
                                    1
                                  
                                  )
                                
                                ⁢
                                %
                                ⁢
                                
                                  
                                
                                ⁢
                                N
                              
                              +
                              1
                            
                            ]
                          
                        
                        i
                      
                    
                    )
                  
                
              
            
            }
          
        
        
      
      ≤
      
        
          (
          
            
              1
              4
            
            +
            
              1
              N
            
            -
            
              7
              
                4
                ⁢
                
                  
                
                ⁢
                
                  N
                  2
                
              
            
          
          )
        
        ⁢
        
          Z
          0
          i
        
      
    
  
  ,
  
    
  
  ⁢
  
    N
    =
    
      
        3
        ⁢
        
          
        
        ⁢
        or
        ⁢
        
          
        
        ⁢
        N
      
      ≥
      
        
      
      ⁢
      5
    
  




where Zi0 is the second order norm of Si0. In the above derivation, Vi8 should be replaced with Vi2 when N=3.

In the first case, when N≧5, we have




  
    
    
      
        2
        ⁢
        
          
        
        ⁢
        
          V
          1
          
            i
            +
            1
          
        
      
      -
      
        V
        2
        
          i
          +
          1
        
      
      -
      
        V
        6
        
          i
          +
          1
        
      
    
    
  
  =
  
    
      
        1
        
          16
          ⁢
          
            
          
          ⁢
          
            N
            2
          
        
      
      ⁢
      
        
        
          
            
              ∑
              
                j
                =
                1
              
              N
            
            ⁢
            
              
            
            ⁢
            
              4
              ⁢
              
                (
                
                  
                    V
                    
                      
                        2
                        ⁢
                        
                          
                        
                        ⁢
                        j
                      
                      -
                      1
                    
                    i
                  
                  -
                  
                    2
                    ⁢
                    
                      
                    
                    ⁢
                    
                      V
                      
                        2
                        ⁢
                        
                          
                        
                        ⁢
                        j
                      
                      i
                    
                  
                  +
                  
                    V
                    
                      
                        2
                        ⁢
                        
                          
                        
                        ⁢
                        j
                      
                      +
                      1
                    
                    i
                  
                
                )
              
            
          
          +
          
            
              N
              2
            
            ⁡
            
              (
              
                
                  2
                  ⁢
                  
                    
                  
                  ⁢
                  
                    V
                    2
                    i
                  
                
                -
                
                  V
                  
                    
                      2
                      ⁢
                      
                        
                      
                      ⁢
                      N
                    
                    +
                    1
                  
                  i
                
                -
                
                  V
                  3
                  i
                
              
              )
            
          
          +
          
            
              N
              2
            
            ⁡
            
              (
              
                
                  2
                  ⁢
                  
                    
                  
                  ⁢
                  
                    V
                    6
                    i
                  
                
                -
                
                  V
                  7
                  i
                
                -
                
                  V
                  5
                  i
                
              
              )
            
          
          +
          
            
              (
              
                
                  N
                  2
                
                -
                28
              
              )
            
            ⁢
            
              (
              
                
                  2
                  ⁢
                  
                    
                  
                  ⁢
                  
                    V
                    1
                    i
                  
                
                -
                
                  V
                  4
                  i
                
                -
                
                  V
                  
                    2
                    ⁢
                    
                      
                    
                    ⁢
                    N
                  
                  i
                
              
              )
            
          
          +
          
            
              (
              
                
                  N
                  2
                
                -
                28
              
              )
            
            ⁢
            
              (
              
                
                  2
                  ⁢
                  
                    
                  
                  ⁢
                  
                    V
                    1
                    i
                  
                
                -
                
                  V
                  4
                  i
                
                -
                
                  V
                  8
                  i
                
              
              )
            
          
          -
          
            
              ∑
              
                j
                =
                5
              
              
                N
                -
                1
              
            
            ⁢
            
              
            
            ⁢
            
              28
              ⁢
              
                (
                
                  
                    2
                    ⁢
                    
                      
                    
                    ⁢
                    
                      V
                      1
                      i
                    
                  
                  -
                  
                    V
                    
                      2
                      ⁢
                      
                        
                      
                      ⁢
                      j
                    
                    i
                  
                  -
                  
                    V
                    
                      2
                      ⁢
                      
                        (
                        
                          j
                          -
                          2
                        
                        )
                      
                    
                    i
                  
                
                )
              
            
          
          -
          
            28
            ⁢
            
              (
              
                
                  2
                  ⁢
                  
                    
                  
                  ⁢
                  
                    V
                    1
                    i
                  
                
                -
                
                  V
                  
                    
                      2
                      ⁢
                      
                        
                      
                      ⁢
                      N
                    
                    -
                    4
                  
                  i
                
                -
                
                  V
                  
                    2
                    ⁢
                    
                      
                    
                    ⁢
                    N
                  
                  i
                
              
              )
            
          
          -
          
            28
            ⁢
            
              (
              
                
                  2
                  ⁢
                  
                    
                  
                  ⁢
                  
                    V
                    1
                    i
                  
                
                -
                
                  V
                  
                    
                      2
                      ⁢
                      
                        
                      
                      ⁢
                      N
                    
                    -
                    2
                  
                  i
                
                -
                
                  V
                  2
                  i
                
              
              )
            
          
          +
          
            
              (
              
                
                  8
                  ⁢
                  
                    
                  
                  ⁢
                  
                    N
                    2
                  
                
                -
                28
              
              )
            
            ⁢
            
              (
              
                
                  2
                  ⁢
                  
                    
                  
                  ⁢
                  
                    V
                    1
                    i
                  
                
                -
                
                  V
                  2
                  i
                
                -
                
                  V
                  6
                  i
                
              
              )
            
          
        
        
      
    
    ≤
    
      {
      
        
      
      ⁢
      
        
          
            
              
                
                  (
                  
                    
                      1
                      2
                    
                    +
                    
                      1
                      
                        4
                        ⁢
                        
                          
                        
                        ⁢
                        N
                      
                    
                    +
                    
                      21
                      
                        4
                        ⁢
                        
                          
                        
                        ⁢
                        
                          N
                          2
                        
                      
                    
                  
                  )
                
                ⁢
                
                  Z
                  0
                  i
                
              
              ,
            
          
          
            
              
                if
                ⁢
                
                  
                
                ⁢
                N
              
              =
              5
            
          
        
        
          
            
              
                
                  (
                  
                    
                      3
                      4
                    
                    +
                    
                      2
                      
                        4
                        ⁢
                        
                          
                        
                        ⁢
                        N
                      
                    
                    -
                    
                      21
                      
                        2
                        ⁢
                        
                          
                        
                        ⁢
                        
                          N
                          2
                        
                      
                    
                  
                  )
                
                ⁢
                
                  Z
                  0
                  i
                
              
              ,
            
          
          
            
              
                if
                ⁢
                
                  
                
                ⁢
                N
              
              >
              5.
            
          
        
      
      ⁢
      
        
      
    
  




In the first summation, one should use Vi2N+1 for Vi2j+1 when j=1. The difference between the case N=5 and N≧6 comes from the fact that (N2−28) is negative when N=5. When N=3, we have





  
    
      
      
        
          2
          ⁢
          
            
          
          ⁢
          
            V
            1
            
              i
              +
              1
            
          
        
        -
        
          V
          2
          
            i
            +
            1
          
        
        -
        
          V
          6
          
            i
            +
            1
          
        
      
      
    
    =
    
      
        
          1
          144
        
        ⁢
        
          
          
            
              5
              ⁢
              
                (
                
                  
                    2
                    ⁢
                    
                      
                    
                    ⁢
                    
                      V
                      2
                      i
                    
                  
                  -
                  
                    V
                    3
                    i
                  
                  -
                  
                    V
                    7
                    i
                  
                
                )
              
            
            +
            
              5
              ⁢
              
                (
                
                  
                    2
                    ⁢
                    
                      
                    
                    ⁢
                    
                      V
                      6
                      i
                    
                  
                  -
                  
                    V
                    7
                    i
                  
                  -
                  
                    V
                    5
                    i
                  
                
                )
              
            
            -
            
              4
              ⁢
              
                (
                
                  
                    2
                    ⁢
                    
                      
                    
                    ⁢
                    
                      V
                      4
                      i
                    
                  
                  -
                  
                    V
                    3
                    i
                  
                  -
                  
                    V
                    5
                    i
                  
                
                )
              
            
            -
            
              19
              ⁢
              
                (
                
                  
                    2
                    ⁢
                    
                      
                    
                    ⁢
                    
                      V
                      1
                      i
                    
                  
                  -
                  
                    V
                    4
                    i
                  
                  -
                  
                    V
                    2
                    i
                  
                
                )
              
            
            -
            
              19
              ⁢
              
                (
                
                  
                    2
                    ⁢
                    
                      
                    
                    ⁢
                    
                      V
                      1
                      i
                    
                  
                  -
                  
                    V
                    4
                    i
                  
                  -
                  
                    V
                    6
                    i
                  
                
                )
              
            
            +
            
              44
              ⁢
              
                (
                
                  
                    2
                    ⁢
                    
                      
                    
                    ⁢
                    
                      V
                      1
                      i
                    
                  
                  -
                  
                    V
                    2
                    i
                  
                  -
                  
                    V
                    6
                    i
                  
                
                )
              
            
          
          
        
      
      ≤
      
        
          2
          3
        
        ⁢
        
          Z
          0
          i
        
      
    
  
  ,
  
    
  
  ⁢
  
    
      when
      ⁢
      
        
      
      ⁢
      N
    
    =
    3
  




Consequently, from the above results we have the first part of (27). The second part of (27) follows from the observation that the norms of second order forward differences similar to 2Vi+11−Vi+12−Vi+16 dominates the other second order forward differences in all subsequent norm computation.

The foregoing description is presented for purposes of illustration and description of the various aspects of the invention. The descriptions are not intended to be exhaustive or to limit the invention to the precise form disclosed. The embodiments described above were chosen to provide the best illustration of the principles of the invention and its practical application to thereby enable one of ordinary skill in the art to utilize the invention in various embodiments and with various modifications as are suited to the particular use contemplated. All such modifications and variations are within the scope of the invention as determined by the appended claims when interpreted in accordance with the breadth to which they are fairly, legally and equitably entitled.

## Claims

1. A method for modeling or representing a surface or shape having an arbitrary topology which may be represented by a control mesh comprising at least one discrete Catmull-Clark Subdivision Surface (CCSS) patch defined by a set of control points, comprising the steps of:
computing a subdivision depth determining the number of recursive subdivisions which may be performed on the control mesh to generate a plurality of finer mesh elements, whereby a distance between each finer mesh element and a corresponding limit surface patch is less than a predetermined error tolerance ε; and
using the computed subdivision depth to construct an adaptively refined mesh that is substantially similar to the control mesh within the range of said predetermined error tolerance ε;
wherein each face of the recursively subdivided control mesh is a quadrilateral and contains up to one extraordinary vertex.

2. The method of claim 1, wherein the limit surface patch is not adjacent to an extraordinary vertex.

3. The method of claim 1, wherein the limit surface patch is adjacent to an extraordinary vertex.

4. The method of claim 2, wherein the limit surface patch is a uniform bicubic B-spline surface patch designated S(u,v).

5. The method of claim 4, including the step of calculating a subdivision depth k defined as k levels of recursive subdivision performed on the control points of the limit surface patch S(u, v) to generate a level k control mesh, wherein k is defined as k≧┌ log4 (M0/3ε)┐, where M0 is the second order norm of S(u,v) and the distance between S(u,v) and the level k control mesh is less than ε.

6. The method of claim 3, including the initial step of subdividing the limit surface patch at least twice to define at least one standard uniform bicubic B-spline surface subpatch and up to one extraordinary subpatch that is not a standard uniform bicubic B-spline subpatch, said extraordinary subpatch containing a limit point of up to one extraordinary vertex.

7. The method of claim 6, further including the step of computing a subdivision depth nε for the extraordinary subpatch, defined as n levels of recursive subdivision performed on the extraordinary subpatch to generate a level n extraordinary subpatch control mesh, wherein nε is defined as




  
    
      n
      ε
    
    ≡
    
      ⌈
      
        
          log
          δ
        
        ⁡
        
          (
          
            
              7
              ⁢
              
                
              
              ⁢
              
                G
                0
              
            
            
              2
              ⁢
              
                
              
              ⁢
              ε
            
          
          )
        
      
      ⌉
    
  
  ,
  
    
  
  ⁢
  
    δ
    =
    
      {
      
        
      
      ⁢
      
        
          
            
              
                4
                3
              
              ,
            
          
          
            
              
                if
                ⁢
                
                  
                
                ⁢
                N
              
              =
              3
            
          
        
        
          
            
              
                98
                85
              
              ,
            
          
          
            
              
                if
                ⁢
                
                  
                
                ⁢
                N
              
              ≥
              5
            
          
        
      
    
  




where G0 is the first order norm of Π00, Π00 is a level-0 control point defined as {Vi|1≦i≦2N+8}, Vi is an extraordinary vertex with valence N, and the distance between the level n extraordinary subpatch control mesh and a corresponding bilinear plane defined in the extraordinary subpatch is less than or equal to ε if n≧nε.

8. The method of claim 7, further including the step of computing a subdivision depth D by performing D recursive subdivisions on each standard uniform bicubic B-spline subpatch to define a level D control mesh, wherein D is defined as the maximum number of recursive subdivisions which may be performed such that the distance between the standard uniform bicubic B-spline subpatch and the level D control mesh is less than ε.

9. The method of claim 1, wherein the step of constructing an adaptively refined mesh comprises the steps of:
defining a mesh for which subdivision depths have been computed, said mesh comprising a plurality of quadrilateral faces containing up to one extraordinary vertex and having at least one interior face not adjacent a boundary of the control mesh and at least one exterior face adjacent a boundary of the control mesh;
defining an initial label of the interior face as a non-zero integer k wherein k is the subdivision depth of its corresponding surface patch with respect to ε,
defining an initial label of the exterior face as zero;
establishing a consistent condition for each face whereby no two adjacent vertices thereof have non-zero labels and no two adjacent vertices thereof have zero labels and further wherein the number of zero labels is maximized, the consistent condition being established by defining a connection supporting graph Gb whose vertices are those of the faces having two adjacent vertices whose labels are zero, selecting a vertex from Gb, redefining the selected vertex label to 1, updating Gb, and repeating the process until the connection supporting graph contains no further vertices;
performing a balanced Catmull-Clark subdivision step on any face having two or more nonzero vertex labels;
performing an unbalanced Catmull-Clark subdivision step on any face having only one vertex with zero label; and
computing new vertices from the results of the balanced and unbalanced Catmull-Clark subdivision steps to generate at least one new face defining the adaptively refined mesh structure.

10. A computer-readable medium having computer-executable instructions for modeling or representing a surface or shape having an arbitrary topology which may be represented by a control mesh comprising at least one discrete Catmull-Clark Subdivision Surface (CCSS) patch defined by a set of control points, by the steps of:
computing a subdivision depth determining the number of recursive subdivisions which may be performed on the control mesh to generate a plurality of finer mesh elements, whereby a distance between each finer mesh element and a corresponding limit surface patch is less than a predetermined error tolerance ε; and
using the computed subdivision depth to construct an adaptively refined mesh that is substantially similar to the control mesh within the range of said predetermined error tolerance ε;
wherein each face of the recursively subdivided control mesh is a quadrilateral and contains up to one extraordinary vertex.

11. The computer-readable medium of claim 10, wherein the limit surface patch is not adjacent to an extraordinary vertex.

12. The computer-readable medium of claim 10, wherein the limit surface patch is adjacent to an extraordinary vertex.

13. The computer-readable medium of claim 11, wherein the limit surface patch is a uniform bicubic B-spline surface patch designated S(u,v).

14. The computer-readable medium of claim 13, wherein the computer-readable medium performs the further step of calculating a subdivision depth k defined as k levels of recursive subdivision performed on the control points of the limit surface patch S(u, v) to generate a level k control mesh, wherein k is defined as k≧┌ log4 (M0/3ε) ┐, where M0 is the second order norm of S(u,v) and the distance between S(u,v) and the level k control mesh is less than ε.

15. The computer-readable medium of claim 12, wherein the computer-readable medium performs the initial step of subdividing the limit surface patch at least twice to define at least one standard uniform bicubic B-spline surface subpatch and up to one extraordinary subpatch that is not a standard uniform bicubic B-spline subpatch, said extraordinary subpatch containing a limit point of up to one extraordinary vertex.

16. The computer-readable medium of claim 15, wherein the computer-readable medium performs the further step of computing a subdivision depth nε for the extraordinary subpatch, defined as n levels of recursive subdivision performed on the extraordinary subpatch to generate a level n extraordinary subpatch control mesh, wherein nε is defined as




  
    
  
  ⁢
  
    
      
        n
        ε
      
      ≡
      
        ⌈
        
          
            log
            δ
          
          ⁡
          
            (
            
              
                7
                ⁢
                
                  
                
                ⁢
                
                  G
                  0
                
              
              
                2
                ⁢
                
                  
                
                ⁢
                ε
              
            
            )
          
        
        ⌉
      
    
    ,
    
      
    
    ⁢
    
      δ
      =
      
        {
        
          
        
        ⁢
        
          
            
              
                
                  4
                  3
                
                ,
              
            
            
              
                
                  if
                  ⁢
                  
                    
                  
                  ⁢
                  N
                
                =
                3
              
            
          
          
            
              
                
                  98
                  85
                
                ,
              
            
            
              
                
                  if
                  ⁢
                  
                    
                  
                  ⁢
                  N
                
                ≥
                5
              
            
          
        
      
    
  




where G0 is the first order norm of Π00, Π00 is a level-0 control point defined as {Vi|1≦i≦2N+8}, Vi is an extraordinary vertex with valence N, and the distance between the level n extraordinary subpatch control mesh and a corresponding bilinear plane defined in the extraordinary subpatch is less than or equal to ε if n≧nε.

17. The computer-readable medium of claim 16, wherein the computer-readable medium further performs the step of computing a subdivision depth D by performing D recursive subdivisions on each standard uniform bicubic B-spline subpatch to define a level D control mesh, wherein D is defined as the maximum number of recursive subdivisions which may be performed such that the distance between the standard uniform bicubic B-spline subpatch and the level D control mesh is less than ε.

18. The computer-readable medium of claim 10, wherein the computer-readable medium constructs an adaptively refined mesh by performing the steps of:
defining a mesh for which subdivision depths have been computed, said mesh comprising a plurality of quadrilateral faces containing up to one extraordinary vertex and having at least one interior face not adjacent a boundary of the control mesh and at least one exterior face adjacent a boundary of the control mesh;
defining an initial label of the interior face as a non-zero integer k wherein k is the subdivision depth of its corresponding surface patch with respect to ε,
defining an initial label of the exterior face as zero;
establishing a consistent condition for each face whereby no two adjacent vertices thereof have non-zero labels and no two adjacent vertices thereof have zero labels and further wherein the number of zero labels is maximized, the consistent condition being established by defining a connection supporting graph Gb whose vertices are those of the faces having two adjacent vertices whose labels are zero, selecting a vertex from Gb, redefining the selected vertex label to 1, updating Gb, and repeating the process until the connection supporting graph contains no further vertices;
performing a balanced Catmull-Clark subdivision step on any face having two or more nonzero vertex labels;
performing an unbalanced Catmull-Clark subdivision step on any face having only one vertex with zero label; and
computing new vertices from the results of the balanced and unbalanced Catmull-Clark subdivision steps to generate at least one new face defining the adaptively refined mesh structure.

19. A method for modeling or representing a surface or shape having an arbitrary topology which may be represented by a control mesh comprising at least one discrete Catmull-Clark Subdivision Surface (CCSS) patch defined by a set of control points, comprising the steps of:
computing a subdivision depth determining the number of recursive subdivisions which may be performed on the control mesh to generate a plurality of finer mesh elements, whereby a distance between each finer mesh element and a corresponding limit surface patch that is a uniform bicubic B-spline surface patch S(u,v) is less than a predetermined error tolerance ε;
wherein the subdivision depth is calculated as subdivision depth k defined as k levels of recursive subdivision performed on the control points of the limit surface patch S(u,v) to generate a level k control mesh, wherein k is defined as k≧┌ log4 (M0/3ε) ┐, where M0 is the second order norm of S(u,v) and the distance between S(u,v) and the level k control mesh is less than ε; and
using the computed subdivision depth to construct an adaptively refined mesh that is substantially similar to the control mesh within the range of said predetermined error tolerance ε;
wherein each face of the recursively subdivided control mesh is a quadrilateral and contains up to one extraordinary vertex.

20. The method of claim 19, wherein the limit surface patch is not adjacent to an extraordinary vertex.

21. The method of claim 19, wherein the limit surface patch is adjacent to an extraordinary vertex.

22. The method of claim 21, including the initial step of subdividing the limit surface patch at least twice to define at least one standard uniform bicubic B-spline surface subpatch and up to one extraordinary subpatch that is not a standard uniform bicubic B-spline subpatch, said extraordinary subpatch containing a limit point of up to one extraordinary vertex.

23. The method of claim 22, further including the step of computing a subdivision depth nε for the extraordinary subpatch, defined as n levels of recursive subdivision performed on the extraordinary subpatch to generate a level n extraordinary subpatch control mesh, wherein nε is defined as




  
    
      n
      ε
    
    ≡
    
      ⌈
      
        
          log
          δ
        
        ⁡
        
          (
          
            
              7
              ⁢
              
                
              
              ⁢
              
                G
                0
              
            
            
              2
              ⁢
              
                
              
              ⁢
              ε
            
          
          )
        
      
      ⌉
    
  
  ,
  
    
  
  ⁢
  
    δ
    =
    
      {
      
        
      
      ⁢
      
        
          
            
              
                4
                3
              
              ,
            
          
          
            
              
                if
                ⁢
                
                  
                
                ⁢
                N
              
              =
              3
            
          
        
        
          
            
              
                98
                85
              
              ,
            
          
          
            
              
                if
                ⁢
                
                  
                
                ⁢
                N
              
              ≥
              5
            
          
        
      
    
  




where G0 is the first order norm of Π00, Π00 is a level-0 control point defined as {Vi|1≦i≦2N+8}, Vi is an extraordinary vertex with valence N, and the distance between the level n extraordinary subpatch control mesh and a corresponding bilinear plane defined in the extraordinary subpatch is less than or equal to ε if n≧nε.

24. The method of claim 23, further including the step of computing a subdivision depth D by performing D recursive subdivisions on each standard uniform bicubic B-spline subpatch to define a level D control mesh, wherein D is defined as the maximum number of recursive subdivisions which may be performed such that the distance between the standard uniform bicubic B-spline subpatch and the level D control mesh is less than ε.

25. The method of claim 19, wherein the step of constructing an adaptively refined mesh comprises the steps of:
defining a mesh for which subdivision depths have been computed, said mesh comprising a plurality of quadrilateral faces containing up to one extraordinary vertex and having at least one interior face not adjacent a boundary of the control mesh and at least one exterior face adjacent a boundary of the control mesh;
defining an initial label of the interior face as a non-zero integer k wherein k is the subdivision depth of its corresponding surface patch with respect to ε,
defining an initial label of the exterior face as zero;
establishing a consistent condition for each face whereby no two adjacent vertices thereof have non-zero labels and no two adjacent vertices thereof have zero labels and further wherein the number of zero labels is maximized, the consistent condition being established by defining a connection supporting graph Gb whose vertices are those of the faces having two adjacent vertices whose labels are zero, selecting a vertex from Gb, redefining the selected vertex label to 1, updating Gb, and repeating the process until the connection supporting graph contains no further vertices;
performing a balanced Catmull-Clark subdivision step on any face having two or more nonzero vertex labels;
performing an unbalanced Catmull-Clark subdivision step on any face having only one vertex with zero label; and
computing new vertices from the results of the balanced and unbalanced Catmull-Clark subdivision steps to generate at least one new face defining the adaptively refined mesh structure.