Abstract:
A method, computer readable storage, and apparatus for improving subdivision schemes for subdivision surfaces. The present method can correct distortion from the base mesh caused by prior art subdivision and smoothing schemes. In one embodiment, the method includes: (a) subdividing a curve having original vertices producing additional vertices; (b) smoothing the curve into smoothed vertices comprising smoothed original vertices and smoothed additional vertices; and (c) adjusting positions of the smoothed vertices.

Description:
CROSS-REFERENCE TO RELATED APPLICATION(S) 
     This Application incorporates by reference U.S. Pat. No. 6,587,105, entitled: “Method and Computer Program Product for Subdivision Generalizing Uniform B-spline Surfaces of Arbitrary Degree.” 
     BACKGROUND OF THE INVENTION 
     1. Field of the Invention 
     The present invention is directed to providing a general set of subdivision rules, which provides more control over the subdivision process. More particularly, the present invention provides a set of subdivision rules which blend approximating spline based schemes with interpolatory schemes, and allows any number of refinements to be performed in a single operation. The present invention also works for both triangles and quadrilaterals in the same mesh. The result is a subdivision scheme, which provides a more natural and desirable effect than existing rules. 
     2. Description of the Related Art 
     Subdivision surfaces are a popular modeling tool used in computer graphics. This is in part because these surfaces combine the benefits of both polygonal and NURBS (Non-Uniform Rational B-Spline) modeling. Subdivision surfaces, like NURBS, allow users to model smooth surfaces by manipulating a small set of control vertices. A subdivision scheme defines how a base mesh is iteratively divided until a “smooth” surface is produced. 
     Current subdivision rules, such as the Catmull-Clark algorithm, can result in a surface that is smaller than the base mesh. For example, see  FIG. 1 , which illustrates a prior art method of subdividing a base mesh  100 . The base mesh  100  is divided into a first subdivided surface  102 , the first subdivided surface  102  is further divided into a second subdivided surface  104 . The second subdivided surface  104  can be continuously divided, resulting in an approximation of a limit curve  106 . Note how the limit curve  106  is smaller than the original base mesh  100 . This “distortion” is a result of the subdivision and smoothing schemes used, and may not be what the user intended. Further, current subdivision schemes and smoothing schemes may produce unwanted effects. 
     Another limitation of the prior art is that a base shape, for example a square, can only be subdivided into a number of smaller pieces that is a power of 4. For example, a square can be subdivided into a 2×2 grid of 4 pieces, a 4×4 grid of 16 pieces, etc. However, the prior art subdivision schemes do not allow for a square to be subdivided into an arbitrary number of pieces, for example a 5×5 grid of 25 pieces. 
     The prior art also does not allow to mix triangles and quadrilaterals in the same base mesh. For example, the Catmull-Clark method works only with quadrilaterals, the Butterfly method only with triangles. What was generally done was to perform a first ad hoc subdivision step to transform general objects into triangles or quads only. The problem with this is that the resulting shape is then generally not very pleasing. 
     Therefore, what is needed, is a more flexible approach of creating improved subdivision surfaces. 
     SUMMARY OF THE INVENTION 
     It is an aspect of the present invention to provide an improved set subdivision rules, which provide users with more control over the subdivision process. 
     It is another aspect of the present invention to allow a mesh to be subdivided into an arbitrary number of faces. 
     It is a further aspect of the present invention to allow a mesh to contain both quadrilaterals and triangles before subdividing. 
     It is still a further aspect of the present invention to provide a subdivision scheme which blends both interpolation and approximation schemes. 
     It is yet another aspect of the present invention to provide a subdivision scheme which allows a user to set certain corrections which result in a more desirable effect. 
     The above aspects can be attained by a system that performs a method including: (a) determining displacements between subdivided points of a base mesh and corresponding smoothed points of a smoothed subdivided surface based on the base mesh; and (b) moving the smoothed points by an interpolated displacement based on distances between smoothed points and their corresponding subdivided points. 
     These together with other aspects and advantages which will be subsequently apparent, reside in the details of construction and operation as more fully hereinafter described and claimed, reference being had to the accompanying drawings forming a part hereof, wherein like numerals refer to like parts throughout. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         FIG. 1  illustrates a prior art method of how a base mesh is subdivided into a smooth surface; 
         FIG. 2  illustrates the subdividing process, according to an embodiment of the present invention; 
         FIG. 3  illustrates three segments comprising a polyline made of a B-spline curve, according to an embodiment of the present invention; 
         FIG. 4  illustrates the segments in  FIG. 3  linearly divided into a 6 segment polyline, according to an embodiment of the present invention; 
         FIG. 5  illustrates smoothing of the polyline, according to an embodiment of the present invention; 
         FIG. 6  illustrates a determination of displacement from the original points, according to an embodiment of the present invention; 
         FIG. 7  illustrates linear interpolation of the displacement, according to an embodiment of the present invention; 
         FIG. 8  illustrates moving points (or “push back”) to compensate for distortion during the smoothing; 
         FIG. 9  illustrates how the push back effect can be weighted by a volume parameter, according to an embodiment of the present invention; 
         FIGS. 10A ,  10 B, and  10 C illustrate the effects of changing a, according to an embodiment of the present invention; 
         FIG. 11  illustrates how the push back effect can also be weighted by a rounding parameter, according to an embodiment of the present invention; 
         FIG. 12  illustrates a flowchart of one possible implementation of the methods of the present invention, according to an embodiment of the present invention; 
         FIG. 13  illustrates linearly subdividing an original polyline by an odd number, particularly into d=5 pieces; 
         FIG. 14  illustrates using a smoothing mask on the subdivided pieces in the odd number subdivisions; 
         FIG. 15  illustrates linear interpolation of push back vectors for the odd number subdivisions; 
         FIGS. 16A and 16B  illustrate subdivisions of quadrilaterals and triangles, according to an embodiment of the present invention; 
         FIGS. 17A ,  17 B, and  17 C illustrate how meshes are deformed when β is increased, according to an embodiment of the present invention; 
         FIGS. 18A ,  18 B, and  18 C illustrate examples of vertex (or face) neighborhoods, according to an embodiment of the present invention; and 
         FIGS. 19A and 19B  illustrate Catmull-Clark correction weights of the first two operations, along the 
                     N   i     -   4       N   i       ⁢     (       V   i   ′     -     V   i       )           
vector, according to an embodiment of the present invention;
 
         FIG. 20A  illustrates the subdividing process of an n-sided polygon. 
         FIG. 20B  illustrates an example of the subdividing process of an n-sided polygon using the process illustrated in  FIG. 20A ; 
         FIG. 21A  illustrates the subdividing process of an n-sided polygon as applied to a square, with d=6. The three different colored shadings represent each different iteration of the process being applied; 
         FIG. 21B  illustrates the subdividing process of an n-sides polygon as applied to a pentagon, with d=4. The two different colored shadings represent each different iteration of the process being applied; 
         FIG. 21C  illustrates the subdividing process of an n-sides polygon as applied to a pentagon, with d=5. The two different colored shadings represent each different iteration of the process being applied; 
         FIG. 21D  illustrates the subdividing process of an n-sides polygon as applied to a hexagon, with d=6. The three different colored shadings represent each different iteration of the process being applied; 
         FIG. 22A  Illustrates a standard linear subdivision operation for cubes; 
         FIG. 22B  illustrates a standard linear subdivision operation for tetrahedra; 
         FIG. 23  illustrates an example of linear subdivision of a 3D polytope; and 
         FIG. 24  is a block diagram illustrating one example of a configuration of hardware used to implement the present invention. 
     
    
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS 
     The present invention can be described as a single parameterized scheme, which is a blend of an approximating and an interpolating scheme. This blend does a better job at preserving a silhouette and a volume of the meshes. When a surface is conventionally subdivided, the subdivided surface is then typically smoothed to maintain the shape of the base mesh. This smoothing nevertheless typically results in a distortion of the original shape. The present invention performs a push back of displaced vertices in order to compensate for this distortion. 
     The present invention performs the scheme in two operations: a linear subdivision, which increase the number of faces, vertices, edges; and then a smoothing operation, where the vertex positions are modified, regardless on how vertices were created. The prior art typically did everything in one operation. 
       FIG. 2  illustrates the subdividing process. A base mesh is comprised of a triangle  200  and a square  202 . The triangle  200  is divided into a subdivided triangle  204  with four pieces. The square  202  is divided into a subdivided square  206  with four pieces. A smoothing algorithm is then applied to the subdivided triangle  204  and the subdivided square  206  to produce a subdivided smooth surface  208 . This process can be repeated a preset number of times until the desired effect is achieved. Note that the present invention allows for both triangles and squares to be subdivided in the same surface. This can be accomplished using methods described later on. 
     Note that the iterative process described above may result in a surface smaller than the original mesh, as illustrated in  FIG. 1 . To compensate for this effect, a “push back” operation can be implemented which moves each original vertex back towards the vertex&#39;s original position (before smoothing) by an amount controlled by the user. The push back operation will now be described. 
       FIG. 3  illustrates three segments comprising a polyline made of a B-spline curve. Polyline  300  comprises vertices  302 ,  304 ,  306 , and  308 , which define segments  310 ,  312 , and  314 , respectively, 
       FIG. 4  illustrates the segments in  FIG. 3  linearly divided into a 6-segment polyline. This division is typically performed in a subdivision surface in order to increase the number of pieces of a segment (or surface) in order to produce smoother results. The polyline  400  comprises vertex  402  (corresponding to vertex  302 ), new vertex  404 , vertex  406  (corresponds to vertex  304 ), new vertex  408 , vertex  410  (corresponds to vertex  306 ), new vertex  412 , and vertex  414  (corresponds to vertex  308 ). The division can be performed in any conventional manner. 
       FIG. 5  illustrates smoothing of the polyline. The smoothing is typically performed so that the subdivided polyline is smoother and rounder. The original polyline  500  comprises points  502 ,  504 ,  506 ,  508 ,  510 ,  512  and  514 . The original polyline  514  can be smoothed into a smoothed polyline  516 , comprising points  518 ,  520 ,  522 ,  524 ,  526 ,  528 , and  530 . The smoothing can be performed using any conventional technique, such as smoothing with a [ 1   2   1 ] mask as illustrated. 
       FIG. 6  illustrates a determination of displacement from the original points. The displacement is determined so that it can be used to subsequently calculate an interpolated displacement, which is ultimately used to compensate for any distortion resulting from the smoothing. Subdivided original polyline  600  (before smoothing) comprises points  602 ,  604 ,  606 ,  608 ,  610 ,  612 , and  614 . The smoothed polyline  616  comprises points  618 ,  620 ,  622 ,  624 ,  626 ,  628 , and  630 . Displacement  632  is determined which is the distance between subdivided point  602  and its corresponding smoothed point  618 . Displacement  634  is determined which is the distance between subdivided point  606  and its corresponding smoothed point  622 . Displacement  632  is determined which is the distance between subdivided point  610  and its corresponding smoothed point  626 . Displacement  634  is determined which is the distance between subdivided point  614  and its corresponding smoothed point  630 . Displacements are only computed between original points ( 302 ,  304 ,  306 ,  308 ) and the corresponding ones in the subdivided and smoothed surface. The other displacements are not meaningful. Missing displacement vectors are interpolated as described in the paragraph below. 
       FIG. 7  illustrates linear interpolation of the displacement. The linear interpolation of the displacement is calculated so it can be subsequently used to compensate for any distortion resulting from the smoothing. Interpolated displacement vectors  700 ,  702 , and  704  are computed based on the displacements illustrated in  FIG. 6 . The interpolation can be performed by any conventional method, typically a linear method. 
       FIG. 8  illustrates moving points (or “push back”) to compensate for distortion during the smoothing. Subdivided polyline  800  comprises points  802 ,  804 ,  806 ,  808 ,  810 ,  812 , and  814 . The smoothed polyline  816  comprises points  818 ,  820 ,  822 ,  824 ,  826 ,  828 , and  830 . Displacements  832 ,  834 ,  836 , and  838  are determined based on distances between points on the original polyline and their corresponding smoothed subdivided points. Interpolated displacement vectors  838 ,  840 , and  842  are interpolated displacements based on the determined displacements. Points  844 ,  846 , and  848  correspond to points  804 ,  808 , and  812  after being moved by the corresponding interpolated displacement vector ( 838 ,  840 ,  842 ). Thus, the corrected polyline  850  after the push back operation comprises the points  802 ,  844 ,  806 ,  846 ,  810 ,  848 , and  814 . 
       FIG. 9  illustrates how the push back effect can be weighted by a volume parameter, herein defined as α. The volume parameter allows a user to specify how much “push-back effect” is desired. Generally, the greater the value used for α, the larger the volume of the resulting polyline. Polyline  900  (corresponding to polyline  816  from  FIG. 8 ) illustrates the case where α=0. In this case, no interpolation is reflected, as this is a pure approximation scheme. Polyline  902  (corresponding to polyline  850  from  FIG. 8 ) illustrates the case where α=1, whereas this is a pure interpolation scheme (in which the original vertices do not move). Polyline  904  illustrates the case where α=½, which comprises a “blended” interpolation and approximation scheme. Generally speaking, setting α=½ typically produces the best effects, although of course the user will want to adjust this parameter to suit his preferences. 
       FIGS. 10A ,  10 B, and  10 C illustrate the effects of changing α.  FIGS. 10A ,  10 B, and  10 C illustrate refinement operations  1 ,  2  and the limit curve, using degree three interpolation and a division value d-2. In  FIG. 10A , α=0. Note how the limit curve  1002  is smaller than the base mesh  1004 . In  FIG. 10B , α=½. Note how the limit curve  1006  more closely follows the base mesh  1008 . In  FIG. 10C , α=1. Note how the limit curve  1010  has a larger volume than the base mesh  1010 . Note that the present invention is equally beneficial for three-dimensional (or higher) surfaces as well. 
       FIG. 11  illustrates how the push back effect can also be weighted by a rounding parameter, herein defined as β. β is a parameter used to bulge flat areas around segment centers. Note that displacements  1100  and  1102  have a sharp angle between them, and an interpolated vector between them may not produce ideal results. An interpolated vector between two vectors with a very sharp angle between them may approach zero. Because of this, areas toward the ends of spherical surfaces may look “boxy” (see  FIG. 17A  for an example). Thus we introduce a rounding parameter β which weights (normalizes) the interpolation results when around segment centers.  1104  illustrates the interpolation result when β=0, while  1106  illustrates the interpolation result when β=1. More on the rounding parameter will be described below. 
       FIG. 12  illustrates a flowchart of one possible implementation of the methods of the present invention, according to an embodiment of the present invention. A computer implementing the method first subdivides  1200 . After subdividing, the computer smoothes  1202  the subdivided surface. The smoothing operation can be repeated n times, as set by the user. After the smoothing is performed, the computer computes  1204  displacement of the subdivided points and the smoothed points. The computer then interpolates  1206  the displacement between the original subdivided points and the smoothed points. The computer then pushes back  1208  points based on the interpolated displacement. Repeating N times can include either  1202  only as shown or all  1202 – 1208  operations. In the later case, the push back will be smoother, as it&#39;s done as many small adjustments, as opposed to one big adjustment at the end. This is generally preferable. Repeating only  1202  will be slightly faster to compute, but the surface typically will have a slightly lower quality. 
     Optionally, the user can set a push back weight (or volume parameter). The user can also optionally set a rounding (or bulging parameter). 
     The prior art limits a number of faces into which a surface can be subdivided. For example, the prior art allows a square to be subdivided into a grid of (n×n). Thus, a square can be divided into 2×2=4 faces, 4×4=16 faces, etc. The Prior art always subdivided a face into 4 pieces, whether for triangle or quadrilateral schemes. The present invention allows dividing into p×p pieces at each step, thus giving a total of (p×p) m . Continuous subdividing into faces of a power of 4 results in a growth which some users may consider too high. 
     In another embodiment of the present invention, a line (or surface) can be subdivided into an arbitrary number of pieces (or faces). A surface can be subdivided into an arbitrary number of pieces not limited to a power of four like the prior art. 
       FIG. 13  illustrates linearly subdividing an original polyline by an odd number, particularly into d=5 pieces. The top segment of polyline  1500  is divided into pieces  1502 ,  1504 ,  1506 ,  1508 , and  1510 . The center segment is needed for the subdivision operation. The smoothing needs the first neighbors too. 
       FIG. 14  illustrates using a smoothing mask on the subdivided pieces in the odd number subdivisions. A [ 1   2  . . . d . . .  2   1 ] smoothing mask is applied. Points along the polyline are numbered  1 - 1400 ,  2 - 1402 ,  3 - 1404 ,  4 - 1406 ,  5 - 1408 ,  4 - 1410 ,  3 - 1412 ,  2 - 1414 ,  1 - 1416 . The mask requires the position of some of the vertices from the next segments. There are more, but only the ones overlapping with the mask are drawn. 
       FIG. 15  illustrates linear interpolation of push back vectors for the odd number subdivisions. The linear interpolation can be performed by any conventional method as described herein or elsewhere. Points  1500 ,  1502 ,  1504 ,  1506 ,  1508 , and  1510  are the smoothed points corresponding to points  1404 ,  1406 ,  1408 ,  1410 ,  1412 , and  1414 . Thus, we have now subdivided the original polyline into 5 pieces ( 1512 ,  1514 ,  1516 ,  1518 ,  1520 ). The prior art only divided in 2, and explicitly defined the resulting position. 
     We will now elaborate on the above methods and describe their implementation in more detail. 
     One type of smoothing method is described in the Article titled “On Subdivision Schemes Generalizing Uniform B-Spline Surfaces of Arbitrary Degree,” by Jos Stam. B-splines of odd degree p can be subdivided by first linearly subdividing the control mesh and then performing 
             m   =       p   -   1     2           
smoothing operations. Each operation involves averaging a vertex with its immediate neighbors using the
 
             [       1   4     ⁢     1   2     ⁢     1   4       ]         
weights. The binomial coefficients are easily computed using Pascal&#39;s triangle:
 
     
       
         
           
             
               
                 
                   
                     1 
                     1 
                   
                   × 
                 
               
               
                 
                   
                     
                       1 
                     
                     
                       1 
                     
                   
                 
               
             
             
               
                 
                   
                     1 
                     2 
                   
                   × 
                 
               
               
                 
                   
                     
                       1 
                     
                     
                       2 
                     
                     
                       1 
                     
                   
                 
               
             
             
               
                 
                   
                     1 
                     4 
                   
                   × 
                 
               
               
                 
                   
                     
                       1 
                     
                     
                       3 
                     
                     
                       3 
                     
                     
                       1 
                     
                   
                 
               
             
             
               
                 
                   
                     1 
                     8 
                   
                   × 
                 
               
               
                 
                   
                     
                       1 
                     
                     
                       4 
                     
                     
                       6 
                     
                     
                       4 
                     
                     
                       1 
                     
                   
                 
               
             
           
         
       
     
     For example, from the last line we obtain the subdivision masks for B-spline curves of degree three. Every old vertex is updated using the 
             [       1   8     ⁢     6   8     ⁢     1   8       ]         
weights, while the new vertices are inserted between the old vertices using the
 
             [       4   8     ⁢     4   8       ]         
masks. The crucial observation is that these two masks are obtained by simply applying the
 
             [       1   4     ⁢     1   2     ⁢     1   4       ]         
mask to the second row, which corresponds to the subdivision rules of linear subdivision. In fact, this construction is easily generalized to any number of subdivisions d. In this case we generalize the Pascal triangle to take the advantage of the d elements in the row directly above it:
 
     
       
         
               
               
               
             
           
               
                   
               
             
             
               
                 1 
                 1 
                 1 
               
               
                 1 1 
                 1 1 1 
                 1 . . . 1 
               
               
                 1 2 1 
                 1 2 3 2 1 
                 1 2 . . . d . . . 2 1 
               
               
                   
               
             
          
         
       
     
     This allows us to compute the corresponding masks for these subdivision schemes. First, linearly subdivide each segment into d pieces, then smooth each vertex using the mask 
                 1     d   2       ⁡     [     1   ,   2   ,   …   ⁢           ,   d   ,   …   ⁢           ,   2   ,   1     ]       .         
In the limit this process generates B-spline curves of degree 2m+1 if the smoothing is applied m times. Note that any conventional smoothing method can be used to present invention
 
     We add the push back operation that updates the position of the vertices after smoothing, order to limit the amount of the shrinking characteristic of approximating subdivision schemes. Each original vertex is moved back towards its original position by an amount controlled by the user. Newly introduced vertices are also adjusted by linear interpolation of the adjusted original vertices. We denote by P j  the new vertices obtained by subdividing the original vertices 
               P   j   1     .         
Throughout the following description, “:=” denotes assignment, while “=” denotes a true equality of two quantities. In these notations, the first operation is (note that d=number of pieces, and k is a temporary variable representing a distance from the closest original vertex on the left.
 
     See Appendix, Equation 1 
     See Appendix, Equation 2 
     This operation is followed by a smoothing operation that modifies the vertices P i : 
     See Appendix, Equation 3 
     Finally, the smoothing operation is followed by a push-back of these new vertices: 
     See Appendix, Equation 4 
     See Appendix, Equation 5 
     See Appendix, Equation 6 
     Evaluations are done in parallel in a conventional “Jacobi manner” to avoid any side effects. In practice this requires the use of an intermediate array to store the vertices&#39; positions. The volume parameter a controls the transition from approximation to interpolation. When α=0 there is no push-back operation and the subdivision scheme produces uniform B-splines in the limit. On the other hand, when α=1 the scheme described herein is interpolatory.  FIG. 4  shows the influence of the parameter a on the subdivided control vertices after several refinements. 
     When the degree p is greater than three, the smoothing and push-back operations are repeated 
               p   -   1     2         
times. In particular, when p=3 and d=2, one smoothing and one push-back operation is performed. In this case we can explicitly write down the subdivision matrix applied to five consecutive control vertices:
 
     See Appendix, Equation 7 
     In particular, when α=1, the P 2i  are moved back exactly to their original position P i , and we obtain the well known four point interpolation scheme, with 
             [         -   1     16     ⁢     9   16     ⁢     9   16     ⁢       -   1     16       ]         
weights 4 .
 
     The surface case is similar to the curve one: we perform one bilinear subdivision operation followed by a smoothing operation. 
     We first define rules for binary subdivision schemes when d=2. We introduce the following notations. The number of elements in a set A is denoted by A#. The vertices of the mesh before a subdivision operation are denoted by v 1   i . During a subdivision operation these vertices are transformed into new vertices V i . At the same time new vertices E i  are introduced by splitting each edge, and new vertices F i  are introduced for each face as in  FIG. 5 . Let P be a vertex of the mesh, then Ε(P) is the set containing all the vertices sharing an edge with P. The set C(P) contains the “corner vertices:” the vertices sharing a face with P not in Ε(P). 
       FIGS. 16A and 16B  illustrate subdivisions of quadrilaterals and triangles.  FIG. 16A  illustrates an initial mesh  1600 .  FIG. 16B  illustrates a subdivided mesh  1602 , that is the mesh of  FIG. 16A  after one subdivision. Each subdivision produces V, E, and F vertex types. Faces with 5 and more vertices use the quadrilateral subdivision rule. To illustrate the above definitions refer to  FIGS. 16A and 16B , wherein Ε(V 2 )={E 2 ,E 3 ,E 5 }, and C(E 3 )={E 1 ,E 2 }. 
     We will now focus entirely on quadrilateral schemes. However, triangular schemes can be treated in a similar way, with the exception that there are no face vertices F i , and C(V) is always empty. The subdivision operation should distinguish between these two types of faces. 
     The Stam article previously mentioned provides different smoothing rules of the vertices that result in uniform B-spline surfaces in the limit on the regular part of the mesh. The simplest smoothing algorithm which corresponds to “repeated averaging” replaces each vertex by a weighted average of its direct neighbors: 
     See Appendix, Equation 8 
     See Appendix, Equation 9 
     Catmull-Clark surfaces are obtained with a different choice for the weights: 
     See Appendix, Equation 10 
     We observe that Formulae 9 and 10 are identical when N i =4. This comes as no surprise since both of these schemes produce uniform B-spline surfaces on regular meshes (N i =4 everywhere). We further observe that, when N i ≠4, the Catmull-Clark rule can be obtained by following Formula 9 with an adjustment of all the extraordinary vertices: 
     See Appendix, Equation 11 
     See Appendix, Equation 12 
     See Appendix, Equation 13 
     The parameter γ allows us to interpolate between the two schemes. Not only does this adjustment unify these two schemes, but it also simplifies the implementation of the Catmull-Clark subdivision: a simple smoothing followed by a vertex update operation. 
     Following the curve case, the simplest push-back operation is to compute the differences Δ i  between V i   1 , and V i , followed by a (bi-)linear interpolation of these differences for the new E i  and F i  vertices. 
     See Appendix, Equation 14 
     See Appendix, Equation 15 
     See Appendix, Equation 16 
     See Appendix, Equation 17 
     However, close to very sharp corners the scheme of the present invention tends to create flat areas around the face centers. The reason is that a bilinear interpolation of vectors of the same length with different angles produces smaller vectors at the center of the faces. This is a well known artifact of certain renderers, which do not renormalize vertex normals after interpolation, and consequently produce darker areas in the face centers. 
     We can fix this problem by introducing a renormalization operation for the interpolation of the Δ vectors. This is achieved by interpolating the length and direction of the Δ vectors separately. To smooth the transition between these new rules and the ones without the normalization, we introduce a rounding factor parameter β. 
     See Appendix, Equation 18 
     See Appendix, Equation 19 
     See Appendix, Equation 20 
     See Appendix, Equation 21 
     When β=0 there is no renormalization, while when β=1 the lengths of the Δ are exactly interpolated. In the case β≠0 these subdivision rules do not reproduce uniform B-splines on the regular part of the mesh in the limit. This doesn&#39;t matter since we do not use these rules to generate limit surfaces. 
       FIGS. 17A ,  17 B, and  17 C illustrate how meshes are deformed when β is increased.  FIG. 17A  illustrates a case where β=0. Note how the sphere  1700  has a square-like shape.  FIG. 17B  illustrates a case where β=½. Note how the sphere  1702  has a rounder shape.  FIG. 17C  illustrates a case where β=1. Note how the shape of the sphere  1704  is affected. For a cube, 
             β   =     1   2           
produces the most “rounded” meshes. Note that in this example we have γ=0 (no Catmull-Clark) to emphasize the flattening problem.
 
     The present invention allows for subdivision into an arbitrary number of pieces. For regular meshes the corresponding limited surfaces Σ(s,t) are equal to a tensor product of uniform B-spline curves. Therefore, the subdivision scheme for these surfaces is simply a linear subdivision operation followed by a smoothing operation with a mask equal to the tensor product of the mask 
               1     d   2       ⁡     [     1   ,   2   ,   …   ⁢           ,   d   ,   …   ⁢           ,   2   ,   1     ]           
derived in Section 3.1.1.
 
     These rules can be naturally extended to extraordinary regions. Ordinary regions are made either of triangles only, where all vertices have 6 neighbors; or made of quadrilaterals only, where all vertices have exactly 4 neighbors. In practice, it turns out that it is easier to decompose the smoothing operation into two simple averaging operations. The averaging operation is different depending on whether d is odd or even. In the odd case we replace each vertex by a simple average of its k-ring neighborhood, where, where 
             k   =         d   -   1     2     .           
When d is even, each averaging operation replaces each face with a vertex that is the average of the k-ring of vertices surrounding it, where
 
             k   =       d   2     .           
The new vertices after this operation form the dual of the initial mesh. In practice, however, the dual is never explicitly computed since the averaging operation is always performed twice (an even amount in general). After two dualizations the vertices are again “in place.”
 
     More formally, let V k (V i ) be the set of all vertices which can be reached from V i  by traversing at most k faces and let F k (V i ) denote the corresponding set of the faces traversed. 
       FIGS. 18A ,  18 B, and  18 C illustrate examples of vertex (or face) neighborhoods. Vertex (or face) neighborhoods V k [F k ] are defined by adding one more ring to the previous set. For some examples. We also define a set of face neighborhoods by V k (F i )=U VεFi V K (V). 
     Using these definitions we can explicitly state the smoothing operations. When d is odd, we apply the following rule p−1 times, where 
     
       
         
           
             k 
             = 
             
               
                 
                   d 
                   - 
                   1 
                 
                 2 
               
               : 
             
           
         
       
     
     See Appendix, Equation 22 
     When d is even the procedure typically only works for odd degrees p. We set the neighborhood to 
               k   =     d   2       ,         
and we apply the rule (23)
 
               p   -   1     2         
times followed by (24):
 
     See Appendix, Equation 23 
     See Appendix, Equation 24 
     In practice, we prefer odd degrees so that no constraint is necessary on the number of subdivisions d. 
     The Catmull-Clark correction operation defined by Formula 11 was introduced for the case d=2 and is typically applied to the extraordinary vertices of the mesh. For arbitrary divisions d we observe that this correction influences a small neighborhood around each extraordinary vertex. 
       FIGS. 19A and 19B  illustrate Catmull-Clark correction weights of the first two operations, along the 
                   N   i     -   4       N   i       ⁢     (       V   i   ′     -     V   i       )           
vector. Weights in the right image should be divided by 64. More precisely, this correction never propagates further than two rings of faces around the extraordinary vertex as shown in  FIGS. 19A and 19B .
 
     In addition, the corrections are only noticeable in the first couple of subdivision operations. The first subdivision operation produces the most visible change, which from Formula 11 is equal to 
               C   i     =           N   i     -   4       N   i       ⁢       (         V   i     ′     -     V   i       )     .             
Subsequent subdivisions produce changes, w i C i , which are proportional to the first one by a weight w i . It is possible to compute these weights exactly for the first couple of subdivision operations The Catmull-Clark result can be computed on a plane, with all points assigned a z value of 0, except for one. Then the rules described herein can be applied to the same plane, and the difference can be computed. This gives the contribution of that point. This operation can be repeated for each point in the plane. As all calculations are linear, the same weights apply to any objects. This is what was done in  FIGS. 19A and 19B . These sampled weights then define a piecewise bilinear function on the unit square that can be used to compute the corresponding weight values when d is a power of two. For more general d values the weights can be interpolated from this function.
 
     In practice, however, we found that a similar behavior can be achieved using the push-back operation described in the next section. The effect of the Catmull-Clark correction can be emulated by using a higher α value and by adjusting the β parameter. This is apparent in  FIG. 17B , where a value 
             β   =     1   2           
produces a “rounded” spherical shape despite the fact that γ=0.
 
     The push-back is similar to the d=2 case described above: we first compute the Δ values for the original vertices and then update the newly introduced vertices using bilinear interpolation. In a similar fashion we can use the normalized interpolation of the Δ values to keep the lengths equal. 
     For an even d, the push-back operation should be applied after Equations (23) and (24) have been applied. This is because it doesn&#39;t make sense to apply the push-back to the “intermediate” vertices F i , which are used temporarily to compute the new vertex positions. To make the algorithm consistent for every number of divisions d, we prefer the algorithm to perform the push-back for odd d when Equation (22) is applied twice. 
     After some experimentation with higher order interpolation schemes we concluded that the differences were likely too small to prefer a more expensive interplant. 
     The present invention provides users with a simple smoothing tool for polygonal meshes. The smoothing operation allows users to create refined versions of their models. Crucial to the success of such a model is that the transitions between the different resolutions of the meshes are almost imperceptible. 
     In practice, we found that the new subdivision scheme of the present invention works best when we used a push-back operation with 
               α   =     1   2       ,     β   =         1   2     ⁢           ⁢   and   ⁢           ⁢   γ     =   0.             
Of course, these parameters should typically be set by the artist, who can freely explore the effect of varying the parameters to meet particular needs. Although this might be tricky, it is a huge improvement over current practice, where artists sometimes have to adjust individual vertices at each level of refinement. With the present invention, on the other hand, artists only have to worry about setting a few parameters at each level.
 
     In another embodiment, the present methods described herein can also be applied to not just quadrilateral surfaces but also polygon surfaces with five sides or more. 
       FIG. 20A  illustrates the subdividing process of an n-sided polygon. This method works with n≧4. 
     First, the process subdivides  2000  edges of the polygon into d pieces. This creates new vertices along each edge. This can be accomplished by using any method, including ones described herein. 
     After the subdivide operation  2000 , then for each edge, the process joins the first vertices on the adjacent edges, creating new edges. 
     After the join operation  2002 , the process then connects  2004  the remaining vertices (not the first vertices) to the new edges. 
       FIG. 20B  illustrates an example of the subdividing process of an n-sided polygon using the process illustrated in  FIG. 20A . 
     Original polygon  2006  is a four sided polygon to which we will apply the subdividing process of  FIG. 20A . 
     After performing the subdividing operation  2000  (from  FIG. 20A ), the result is subdivided edge polygon  2008 . Note here we have divided each (or edge) into three pieces, as new vertices are created. 
     Next the joining operation  2002  (from  FIG. 20A ) is performed, which results in the joined edge polygon  2010 . Note for simplicity, only one edge is joined in  FIG. 20B , although typically all edges of the polygon will be joined. New edge  2011  is a newly created edge. 
     Next, the connecting operation  2004  (from  FIG. 20A ) is performed, which results in the connected edge polygon  2012 . Note that for simplicity, the connecting is only applied to one edge in  FIG. 20B , although typically the connecting operation  2004  applies to all edges. Note that newly created points a  2014  and b  2016  are created, which are then connected to the subdivided points  2018   2020  on the outside edge. Newly created points a  2014  and b  2016  can be calculated in any manner. One way would be to maintain a one to one correspondence with the original points  2018   2020  as shown here. If the new edge  2011  is not the same length as the original edge, then points a and b may be computed to maintain the same ratio along the new edge  2011  as original points  2018   2020  maintain along the original edge. Numerous other connecting methods exist which could determine points a and b, and any of these methods can be applied, 
     After the above-described operations are applied to all sides (edges) of a polygon, this leaves in the center an n-sided polygon (same n as original polygon) that should now be subdivided into d-2 pieces. Operations  2000 ,  2002 , and  2004  are repeated until d=1 or d=0. In the case of the quadrilateral shown in  FIG. 20   b , since d=3 pieces, and d-2=1, the method is considered complete and no repeating is necessary. 
       FIG. 21A  illustrates the subdividing process of an n-sided polygon as applied to a square, with d=6. An outside part  2100 , a middle part  2102 , and a center part  2104  represent each different iteration of the process being applied. 
       FIG. 21B  illustrates the subdividing process of an n-sides polygon as applied to a pentagon, with d=4. An outside part  2106  and a center part  2108  represent each different iteration of the process being applied. 
       FIG. 21C  illustrates the subdividing process of an n-sides polygon as applied to a pentagon, with d=5. An outside part  2110  and a center part  2112  represent each different iteration of the process being applied. 
       FIG. 21D  illustrates the subdividing process of an n-sides polygon as applied to a hexagon, with d=6. An outside part  2114 , a middle part  2116 , and a center part  2118  represent each different iteration of the process being applied. 
     In a further embodiment, the present methods can by applied to a collection of polytopes of arbitrary dimension. A polytope is a known math term and is a generalization of a polygonal mesh to arbitrary dimensions. For example in three dimensions, a polytope is a collection of closed polyhedra, where a polyhedron is a solid whose boundary is a closed polygonal mesh. In general, a k-dimensional polytope is defined recursively in terms of a collection of simple polytopes whose boundaries are (k-1)-dimensional closed polytopes. 
     In this embodiment, every polytope is first linearly subdivided into smaller polytopes and then smoothed as follows. Each vertex of the polytope is replaced by the centroid of the polytope defined by the centroids of the polytopes adjacent to the vertex. Alternatively, every polytope can be subdivided and then the vertices are smoothed by replacing them by the average of all centroids of the neighboring polytopes. The positions of the vertices of the polytopes can also be adjusted as described herein. Each of these individual operations applied to polytopes may be accomplished by conventional methods and/or using the methods described herein which can simply be applied to k-dimensional polytopes. 
       FIG. 22A  Illustrates a standard linear subdivision operation for cubes. Original cube  2200  is subdivided into a subdivided cube  2202 , which comprises 8 smaller cubes.  FIG. 22B  illustrates a standard linear subdivision operation for tetrahedra. Original tetrahedron  2204  is subdivided into a subdivided tetrahedron  2206 , which comprises 8 smaller tetrahedra. 
       FIG. 23  illustrates an example of linear subdivision of a 3D polytope. Original polytope  2300  is subdivided into a subdivided polytope  2302 . 
       FIG. 24  is a block diagram illustrating one example of a configuration of hardware used to implement the present invention. 
     A display monitor  2400  is connected to a computer  2402 . The computer performs the operational processes described herein based upon input from a keyboard  2406  and/or a mouse  2408 . A drawing tablet  2404  can also be connected to the computer  2402 . The computer  2402  has connected a ROM  2410 , a RAM  2412 , and a disk drive  2414 . In addition, a drawing pen  2416  and/or a puck  2418  can also be used as input devices for the tablet. Of course, any applicable configuration of hardware can be used to implement the present invention. 
     The system can also include any type of conventional peripherals, including permanent or removable storage, such as magnetic and optical discs, etc. Further, any storage used with the computer (disk drive, RAM, etc.) can store the process and data structures of the present invention. The processes can also be distributed via, for example, downloading over a network such as the Internet. 
     The present invention has been described with respect to a general set of subdivision rules, which provide users with more control over the subdivision process. 
     This Application incorporates by reference the Article entitled, “A Unified Subdivision Scheme for Polygonal Modeling,” by Jerome Maillot and Jos Stam, EUROGRAPHICS 2001, Volume 20 (2001), Number 3, published 9/2001. This Application also incorporates by reference the Article entitled, “On Subdivision Schemes Generalizing Uniform B-Spline Surfaces of Arbitrary Degree,” by Jos Stam, Computer Aided Geometric Design 18(5), published June 2001. 
     The many features and advantages of the invention are apparent from the detailed specification and, thus, it is intended by the appended claims to cover all such features and advantages of the invention that fall within the true spirit and scope of the invention. Further, since numerous modifications and changes will readily occur to those skilled in the art, it is not desired to limit the invention to the exact construction and operation illustrated and described, and accordingly all suitable modifications and equivalents may be resorted to, falling within the 
     
       
         
           
             
               
                 
                   
                     
                       P 
                       di 
                     
                     ∷ 
                   
                   = 
                   
                     P 
                     i 
                     l 
                   
                 
               
               
                 
                   ( 
                   1 
                   ) 
                 
               
             
             
               
                 
                   
                     
                       
                         P 
                         
                           di 
                           + 
                           k 
                         
                       
                       ∷ 
                     
                     = 
                     
                       
                         
                           
                             d 
                             - 
                             k 
                           
                           d 
                         
                         ⁢ 
                         
                           P 
                           i 
                           l 
                         
                       
                       + 
                       
                         
                           k 
                           d 
                         
                         ⁢ 
                         
                           P 
                           
                             i 
                             + 
                             1 
                           
                           l 
                         
                       
                     
                   
                   , 
                   
                     0 
                     &lt; 
                     k 
                     &lt; 
                     d 
                   
                 
               
               
                 
                   ( 
                   2 
                   ) 
                 
               
             
             
               
                 
                   
                     
                       P 
                       i 
                     
                     ∷ 
                   
                   = 
                   
                     
                       1 
                       
                         d 
                         2 
                       
                     
                     ⁢ 
                     
                       ( 
                       
                         
                           dP 
                           i 
                         
                         + 
                         
                           
                             ∑ 
                             
                               k 
                               = 
                               1 
                             
                             
                               k 
                               &lt; 
                               d 
                             
                           
                           ⁢ 
                           
                               
                           
                           ⁢ 
                           
                             
                               ( 
                               
                                 d 
                                 - 
                                 k 
                               
                               ) 
                             
                             ⁢ 
                             
                               ( 
                               
                                 
                                   P 
                                   
                                     i 
                                     - 
                                     k 
                                   
                                 
                                 + 
                                 
                                   P 
                                   
                                     i 
                                     + 
                                     k 
                                   
                                 
                               
                               ) 
                             
                           
                         
                       
                       ) 
                     
                   
                 
               
               
                 
                   ( 
                   3 
                   ) 
                 
               
             
             
               
                 
                   
                     
                       Δ 
                       i 
                     
                     ∷ 
                   
                   = 
                   
                     α 
                     ⁡ 
                     
                       ( 
                       
                         
                           P 
                           i 
                           l 
                         
                         - 
                         
                           P 
                           di 
                         
                       
                       ) 
                     
                   
                 
               
               
                 
                   ( 
                   4 
                   ) 
                 
               
             
             
               
                 
                   
                     
                       P 
                       di 
                     
                     ∷ 
                   
                   = 
                   
                     
                       P 
                       di 
                     
                     + 
                     
                       Δ 
                       i 
                     
                   
                 
               
               
                 
                   ( 
                   5 
                   ) 
                 
               
             
             
               
                 
                   
                     
                       P 
                       
                         di 
                         + 
                         k 
                       
                     
                     ∷ 
                   
                   = 
                   
                     
                       
                         P 
                         
                           di 
                           + 
                           k 
                         
                       
                       + 
                       
                         
                           
                             d 
                             - 
                             k 
                           
                           d 
                         
                         ⁢ 
                         
                           Δ 
                           i 
                         
                       
                       + 
                       
                         
                           k 
                           d 
                         
                         ⁢ 
                         
                           Δ 
                           
                             i 
                             + 
                             1 
                           
                         
                         ⁢ 
                         0 
                       
                     
                     &lt; 
                     k 
                     &lt; 
                     d 
                   
                 
               
               
                 
                   ( 
                   6 
                   ) 
                 
               
             
             
               
                 
                   M 
                   = 
                   
                     
                       
                         ( 
                         
                           
                             
                               
                                 2 
                                 - 
                                 
                                   2 
                                   ⁢ 
                                   α 
                                 
                               
                             
                             
                               
                                 4 
                                 ⁢ 
                                 
                                   ( 
                                   
                                     3 
                                     + 
                                     α 
                                   
                                   ) 
                                 
                               
                             
                             
                               
                                 2 
                                 - 
                                 
                                   2 
                                   ⁢ 
                                   α 
                                 
                               
                             
                             
                               0 
                             
                             
                               0 
                             
                           
                           
                             
                               
                                 - 
                                 α 
                               
                             
                             
                               
                                 8 
                                 + 
                                 α 
                               
                             
                             
                               
                                 8 
                                 + 
                                 α 
                               
                             
                             
                               
                                 - 
                                 α 
                               
                             
                             
                               0 
                             
                           
                           
                             
                               0 
                             
                             
                               
                                 2 
                                 - 
                                 
                                   2 
                                   ⁢ 
                                   α 
                                 
                               
                             
                             
                               
                                 4 
                                 ⁢ 
                                 
                                   ( 
                                   
                                     3 
                                     + 
                                     α 
                                   
                                   ) 
                                 
                               
                             
                             
                               
                                 2 
                                 - 
                                 
                                   2 
                                   ⁢ 
                                   α 
                                 
                               
                             
                             
                               0 
                             
                           
                           
                             
                               0 
                             
                             
                               
                                 - 
                                 α 
                               
                             
                             
                               
                                 8 
                                 + 
                                 α 
                               
                             
                             
                               
                                 8 
                                 + 
                                 α 
                               
                             
                             
                               
                                 - 
                                 α 
                               
                             
                           
                           
                             
                               0 
                             
                             
                               0 
                             
                             
                               
                                 2 
                                 - 
                                 
                                   2 
                                   ⁢ 
                                   α 
                                 
                               
                             
                             
                               
                                 4 
                                 ⁢ 
                                 
                                   ( 
                                   
                                     3 
                                     + 
                                     α 
                                   
                                   ) 
                                 
                               
                             
                             
                               
                                 2 
                                 - 
                                 
                                   2 
                                   ⁢ 
                                   α 
                                 
                               
                             
                           
                         
                         ) 
                       
                       ⁢ 
                       
                         ( 
                         
                           
                             
                               
                                 P 
                                 
                                   
                                     2 
                                     ⁢ 
                                     i 
                                   
                                   - 
                                   2 
                                 
                               
                             
                           
                           
                             
                               
                                 P 
                                 
                                   
                                     2 
                                     ⁢ 
                                     i 
                                   
                                   - 
                                   1 
                                 
                               
                             
                           
                           
                             
                               
                                 P 
                                 
                                   2 
                                   ⁢ 
                                   i 
                                 
                               
                             
                           
                           
                             
                               
                                 P 
                                 
                                   
                                     2 
                                     ⁢ 
                                     i 
                                   
                                   + 
                                   1 
                                 
                               
                             
                           
                           
                             
                               
                                 P 
                                 
                                   
                                     2 
                                     ⁢ 
                                     i 
                                   
                                   + 
                                   2 
                                 
                               
                             
                           
                         
                         ) 
                       
                     
                     = 
                     
                       
                         1 
                         16 
                       
                       ⁢ 
                       
                         M 
                         · 
                         
                           ( 
                           
                             
                               
                                 
                                   P 
                                   
                                     i 
                                     - 
                                     2 
                                   
                                   l 
                                 
                               
                             
                             
                               
                                 
                                   P 
                                   
                                     i 
                                     - 
                                     1 
                                   
                                   l 
                                 
                               
                             
                             
                               
                                 
                                   P 
                                   i 
                                   l 
                                 
                               
                             
                             
                               
                                 
                                   P 
                                   
                                     i 
                                     + 
                                     1 
                                   
                                   l 
                                 
                               
                             
                             
                               
                                 
                                   P 
                                   
                                     i 
                                     + 
                                     2 
                                   
                                   l 
                                 
                               
                             
                           
                           ) 
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   7 
                   ) 
                 
               
             
             
               
                 
                   
                     N 
                     i 
                   
                   = 
                   
                     
                       ɛ 
                       ⁡ 
                       
                         ( 
                         
                           V 
                           i 
                         
                         ) 
                       
                     
                     # 
                   
                 
               
               
                 
                   ( 
                   8 
                   ) 
                 
               
             
             
               
                 
                   
                     
                       V 
                       i 
                     
                     ∷ 
                   
                   = 
                   
                     
                       
                         1 
                         4 
                       
                       ⁢ 
                       
                         V 
                         i 
                       
                     
                     + 
                     
                       
                         1 
                         
                           2 
                           ⁢ 
                           
                             N 
                             i 
                           
                         
                       
                       ⁢ 
                       
                         
                           ∑ 
                           
                             P 
                             ∈ 
                             
                               ɛ 
                               ⁡ 
                               
                                 ( 
                                 
                                   V 
                                   i 
                                 
                                 ) 
                               
                             
                           
                         
                         ⁢ 
                         
                             
                         
                         ⁢ 
                         P 
                       
                     
                     + 
                     
                       
                         1 
                         
                           4 
                           ⁢ 
                           
                             N 
                             i 
                           
                         
                       
                       ⁢ 
                       
                         
                           ∑ 
                           
                             P 
                             ∈ 
                             
                               C 
                               ⁡ 
                               
                                 ( 
                                 
                                   V 
                                   i 
                                 
                                 ) 
                               
                             
                           
                         
                         ⁢ 
                         P 
                       
                     
                   
                 
               
               
                 
                   ( 
                   9 
                   ) 
                 
               
             
             
               
                 
                   
                     
                       V 
                       i 
                     
                     ∷ 
                   
                   = 
                   
                     
                       
                         
                           
                             N 
                             i 
                           
                           - 
                           3 
                         
                         
                           N 
                           i 
                         
                       
                       ⁢ 
                       
                         V 
                         i 
                       
                     
                     + 
                     
                       
                         2 
                         
                           N 
                           i 
                           2 
                         
                       
                       ⁢ 
                       
                         
                           ∑ 
                           
                             P 
                             ∈ 
                             
                               ɛ 
                               ⁡ 
                               
                                 ( 
                                 
                                   V 
                                   i 
                                 
                                 ) 
                               
                             
                           
                         
                         ⁢ 
                         P 
                       
                     
                     + 
                     
                       
                         1 
                         
                           N 
                           i 
                           2 
                         
                       
                       ⁢ 
                       
                         
                           ∑ 
                           
                             P 
                             ∈ 
                             
                               C 
                               ⁡ 
                               
                                 ( 
                                 
                                   V 
                                   i 
                                 
                                 ) 
                               
                             
                           
                         
                         ⁢ 
                         P 
                       
                     
                   
                 
               
               
                 
                   ( 
                   10 
                   ) 
                 
               
             
             
               
                 
                   
                     δ 
                     i 
                   
                   = 
                   
                     
                       
                         ( 
                         
                           
                             4 
                             
                               N 
                               i 
                             
                           
                           - 
                           1 
                         
                         ) 
                       
                       ⁢ 
                       
                         V 
                         i 
                       
                     
                     + 
                     
                       
                         
                           
                             N 
                             i 
                           
                           - 
                           4 
                         
                         
                           N 
                           i 
                         
                       
                       ⁢ 
                       
                         V 
                         i 
                         l 
                       
                     
                   
                 
               
               
                 
                   ( 
                   11 
                   ) 
                 
               
             
             
               
                 
                   = 
                   
                     
                       
                         
                           N 
                           i 
                         
                         - 
                         4 
                       
                       
                         N 
                         i 
                       
                     
                     ⁢ 
                     
                       ( 
                       
                         
                           V 
                           i 
                           l 
                         
                         - 
                         
                           V 
                           i 
                         
                       
                       ) 
                     
                   
                 
               
               
                 
                   ( 
                   12 
                   ) 
                 
               
             
             
               
                 
                   
                     
                       V 
                       i 
                     
                     ∷ 
                   
                   = 
                   
                     
                       V 
                       i 
                     
                     + 
                     
                       γδ 
                       i 
                     
                   
                 
               
               
                 
                   ( 
                   13 
                   ) 
                 
               
             
             
               
                 
                   
                     Δ 
                     ⁡ 
                     
                       ( 
                       
                         V 
                         i 
                       
                       ) 
                     
                   
                   = 
                   
                     α 
                     ⁡ 
                     
                       ( 
                       
                         
                           V 
                           i 
                           l 
                         
                         - 
                         
                           V 
                           i 
                         
                       
                       ) 
                     
                   
                 
               
               
                 
                   ( 
                   14 
                   ) 
                 
               
             
             
               
                 
                   
                     Δ 
                     ⁡ 
                     
                       ( 
                       
                         E 
                         i 
                       
                       ) 
                     
                   
                   = 
                   
                     
                       1 
                       2 
                     
                     ⁢ 
                     
                       ( 
                       
                         
                           Δ 
                           ⁡ 
                           
                             ( 
                             
                               V 
                               0 
                             
                             ) 
                           
                         
                         + 
                         
                           Δ 
                           ⁡ 
                           
                             ( 
                             
                               V 
                               1 
                             
                             ) 
                           
                         
                       
                       ) 
                     
                   
                 
               
               
                 
                   ( 
                   15 
                   ) 
                 
               
             
             
               
                 
                   
                     Δ 
                     ⁡ 
                     
                       ( 
                       
                         F 
                         i 
                       
                       ) 
                     
                   
                   = 
                   
                     
                       1 
                       
                         
                           ɛ 
                           ⁡ 
                           
                             ( 
                             
                               F 
                               i 
                             
                             ) 
                           
                         
                         # 
                       
                     
                     ⁢ 
                     
                       
                         ∑ 
                         
                           
                             E 
                             k 
                           
                           ∈ 
                           
                             ɛ 
                             ⁡ 
                             
                               ( 
                               
                                 F 
                                 i 
                               
                               ) 
                             
                           
                         
                       
                       ⁢ 
                       
                         Δ 
                         ⁡ 
                         
                           ( 
                           
                             E 
                             k 
                           
                           ) 
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   16 
                   ) 
                 
               
             
             
               
                 
                   = 
                   
                     
                       1 
                       
                         
                           C 
                           ⁡ 
                           
                             ( 
                             
                               F 
                               i 
                             
                             ) 
                           
                         
                         # 
                       
                     
                     ⁢ 
                     
                       
                         ∑ 
                         
                           
                             V 
                             k 
                           
                           ∈ 
                           
                             C 
                             ⁡ 
                             
                               ( 
                               
                                 F 
                                 i 
                               
                               ) 
                             
                           
                         
                       
                       ⁢ 
                       
                         Δ 
                         ⁡ 
                         
                           ( 
                           
                             V 
                             k 
                           
                           ) 
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   17 
                   ) 
                 
               
             
             
               
                 
                   
                     l 
                     ⁡ 
                     
                       ( 
                       
                         E 
                         i 
                       
                       ) 
                     
                   
                   = 
                   
                     
                       β 
                       ⁢ 
                       
                         
                           
                              
                             
                                
                               
                                 Δ 
                                 ⁡ 
                                 
                                   ( 
                                   
                                     V 
                                     0 
                                   
                                   ) 
                                 
                               
                                
                             
                              
                           
                           + 
                           
                              
                             
                                
                               
                                 Δ 
                                 ⁡ 
                                 
                                   ( 
                                   
                                     V 
                                     1 
                                   
                                   ) 
                                 
                               
                                
                             
                              
                           
                         
                         
                           2 
                           ⁢ 
                           
                              
                             
                                
                               
                                 Δ 
                                 ⁡ 
                                 
                                   ( 
                                   
                                     E 
                                     i 
                                   
                                   ) 
                                 
                               
                                
                             
                              
                           
                         
                       
                     
                     + 
                     1 
                     - 
                     β 
                   
                 
               
               
                 
                   ( 
                   18 
                   ) 
                 
               
             
             
               
                 
                   
                     l 
                     ⁡ 
                     
                       ( 
                       
                         F 
                         i 
                       
                       ) 
                     
                   
                   = 
                   
                     
                       β 
                       ⁢ 
                       
                         
                           
                             ∑ 
                             
                                 
                             
                             ⁢ 
                             
                               V 
                               k 
                             
                           
                           ∈ 
                           
                             
                               ɛ 
                               ⁡ 
                               
                                 ( 
                                 
                                   F 
                                   i 
                                 
                                 ) 
                               
                             
                             ⁢ 
                             
                                
                               
                                  
                                 
                                   Δ 
                                   ⁡ 
                                   
                                     ( 
                                     
                                       V 
                                       k 
                                     
                                     ) 
                                   
                                 
                                  
                               
                                
                             
                           
                         
                         
                           
                             
                               ɛ 
                               ⁡ 
                               
                                 ( 
                                 
                                   F 
                                   
                                     i 
                                     ⁢ 
                                     
                                         
                                     
                                   
                                 
                                 ) 
                               
                             
                             # 
                           
                           ⁢ 
                           
                              
                             
                                
                               
                                 Δ 
                                 ⁡ 
                                 
                                   ( 
                                   
                                     F 
                                     i 
                                   
                                   ) 
                                 
                               
                                
                             
                              
                           
                         
                       
                     
                     + 
                     1 
                     - 
                     β 
                   
                 
               
               
                 
                   ( 
                   19 
                   ) 
                 
               
             
             
               
                 
                   
                     
                       Δ 
                       ⁡ 
                       
                         ( 
                         
                           E 
                           i 
                         
                         ) 
                       
                     
                     ∷ 
                   
                   = 
                   
                     
                       l 
                       ⁡ 
                       
                         ( 
                         
                           E 
                           i 
                         
                         ) 
                       
                     
                     ⁢ 
                     
                       Δ 
                       ⁡ 
                       
                         ( 
                         
                           E 
                           i 
                         
                         ) 
                       
                     
                   
                 
               
               
                 
                   ( 
                   20 
                   ) 
                 
               
             
             
               
                 
                   
                     
                       Δ 
                       ⁡ 
                       
                         ( 
                         
                           F 
                           i 
                         
                         ) 
                       
                     
                     ∷ 
                   
                   = 
                   
                     
                       l 
                       ⁡ 
                       
                         ( 
                         
                           F 
                           i 
                         
                         ) 
                       
                     
                     ⁢ 
                     
                       Δ 
                       ⁡ 
                       
                         ( 
                         
                           F 
                           i 
                         
                         ) 
                       
                     
                   
                 
               
               
                 
                   ( 
                   21 
                   ) 
                 
               
             
             
               
                 
                   
                     
                       V 
                       i 
                     
                     ∷ 
                   
                   = 
                   
                     
                       1 
                       
                         
                           k 
                         
                         ⁢ 
                         
                           
                             ( 
                             
                               V 
                               i 
                             
                             ) 
                           
                           # 
                         
                       
                     
                     ⁢ 
                     
                       
                         ∑ 
                         
                           
                             V 
                             j 
                           
                           ∈ 
                           
                             
                               k 
                             
                             ⁢ 
                             
                               ( 
                               
                                 V 
                                 i 
                               
                               ) 
                             
                           
                         
                       
                       ⁢ 
                       
                         V 
                         j 
                       
                     
                   
                 
               
               
                 
                   ( 
                   22 
                   ) 
                 
               
             
             
               
                 
                   
                     
                       F 
                       i 
                     
                     ∷ 
                   
                   = 
                   
                     
                       1 
                       
                         
                           k 
                         
                         ⁢ 
                         
                           
                             ( 
                             
                               F 
                               i 
                             
                             ) 
                           
                           # 
                         
                       
                     
                     ⁢ 
                     
                       
                         ∑ 
                         
                           
                             
                                 
                             
                             j 
                           
                           ∈ 
                           
                             
                               k 
                             
                             ⁢ 
                             
                               ( 
                               
                                 F 
                                 i 
                               
                               ) 
                             
                           
                         
                       
                       ⁢ 
                       
                         V 
                         j 
                       
                     
                   
                 
               
               
                 
                   ( 
                   23 
                   ) 
                 
               
             
             
               
                 
                   
                     
                       V 
                       i 
                     
                     ∷ 
                   
                   = 
                   
                     
                       1 
                       
                         
                           k 
                         
                         ⁢ 
                         
                           
                             ( 
                             
                               V 
                               i 
                             
                             ) 
                           
                           # 
                         
                       
                     
                     ⁢ 
                     
                       
                         ∑ 
                         
                           
                             
                                 
                             
                             j 
                           
                           ∈ 
                           
                             
                               k 
                             
                             ⁢ 
                             
                               ( 
                               
                                 V 
                                 i 
                               
                               ) 
                             
                           
                         
                       
                       ⁢ 
                       
                         F 
                         j 
                       
                     
                   
                 
               
               
                 
                   ( 
                   24 
                   )