Abstract:
A system that predistorts a computer generated paint stamp for paint being applied to a 3D computer model of an object. The predistortion is based on a difference in shape and orientation of a texture space polygon, to which the stamp is initially applied, and the corresponding world space target polygon of the model. Because the paint stamps often overlap several polygons of different shapes and orientations, the distortion compensation becomes a weighted average of the distortion compensation for the polygon under the stamp and its nearest neighbors.

Description:
CROSS REFERENCE TO RELATED APPLICATION 
     This application is related to U.S. application entitled Computer Generated Paint Stamp Seaming Compensation, having Silicon Graphics Inc. Ser. No. 09/024,127 by Reiter et al, filed concurrently herewith and incorporated by reference herein. 
     BACKGROUND OF THE INVENTION 
     1. Field of the Invention 
     The present invention is directed to the compensation of the electronic paint that an artist can apply to a computer based model and, more particularly, to the compensation of a paint stamp for the warping that occurs when the stamp, applied to a texture triangle, is warped, along with the triangle, to fit a model surface triangle. 
     2. Description of the Related Art 
     Computer generated three dimensional (3D) objects are typically comprised of polygons, typically triangles, of sufficiently small size that the surface of the model appears smooth. Surface detail (color, surface topology, reflectance, etc.) is applied to these smooth computer generated three-dimensional images by applying 2D images, known as textures, to the 3D models in a process called texture mapping. Much of the realism of the models is affected by these textures, and great care is therefore taken to produce the desired effects when painting the textures. 
     Digital paint is typically applied in brush strokes, with each stroke using a particular paint brush specified by the user. Various attributes of the brush must be specified before the brush can be used to produce a stroke. These attributes include, for example, the color of paint; the radius, aspect ratio, and rotational angle of the brush; and a detailed map specifying the amount of paint to be applied at each point in the brush. The collection of these attributes is called a brush stamp. Once the attributes are set, a digital image of the stamp is created: this is called the stamp image, or a stamp source image. Stamps can then be placed on a target image, such as a texture, by a copying the stamp image to various locations on the target. Paint brush strokes are typically applied by placing a sequence of consecutive stamps along the trajectory of a path as indicated by the user with a stylus or mouse pointer. The spacing between the stamps on the path determines the appearance of the stroke. Stamp spacing is typically another attribute specified by the user. 
     Paint may be applied to 3D models by either painting directly onto the flat texture, or by painting on the model. Although both are useful, only the latter method provides direct visual feedback as to the final appearance of the painted model. 
     Two methods are conventionally provided for painting in 3D: projective paint and surface paint. In projective painting, the paint is applied to a flat surface which is shaded and masked by the model in such a way that the paint appears to be applied directly to the surface. A separate projection step is then necessary to move the paint from this paint plane onto the various textures of the object. 
     The second 3D painting method is known as painting on the surface. In this approach, paint is applied directly onto the texture assigned to each surface. In particular, brush stamps are applied to the texture in a manner which is consistent with the conventional triangulated surface tessellation of computer based models. Stamps are centered at the world space position designated by the mouse or stylus pointer. That is, given a world space point in the interior of a surface triangle, the corresponding texture space point is found in the interior of the texture triangle assigned to it. The point in texture space is then used as the center of the stamp that it is to be placed. This gives rise to the problem illustrated in FIG.  1 . As there is no inherent correlation between the size and orientation of the texture space and world space triangles, neighboring triangles may receive stamps that are identical in texture-space but whose appearances in world-space is greatly distorted. The circular stamp  2  of the desired shape in FIG. 1A when applied to the texture space triangle  4  in FIG. 1B is undistorted but when the texture space triangle  4  is mapped to the corresponding world space triangle  6 , the stamp is distorted as depicted in FIG.  1 C. These figures primarily depict shape and size distortion that occurs when the texture and world space triangles are of different shapes. 
     What is needed is a system that compensates for the shape and size distortion occurring when the paint stamp is transferred from texture space to world space. 
     Texture triangles in texture space, as noted above, often have an orientation that is not correlated with the orientation of the world space triangles. This lack of correlation causes rotational distortion This would not be a problem if all paint brushes and their stamps were circular but it is often the case that an electronic paint brush can have a non-circular shape associated with it. 
     What is needed is a system that preserves rotational coherence between polygons. 
     Distortion compensation as described herein is computed for each individual stamp before it is applied. However, the compensation compensates for a stamp which lies completely inside a single triangle. Unfortunately, this is seldom the case as stamps will generally overlap several triangles whose individual distortions differ, thus giving the stroke a very jagged appearance. 
     What is needed is a method of compensating for the differences in distortion caused by different triangles. 
     SUMMARY OF THE INVENTION 
     It is an object of the present invention to apply paint to world space objects in a manner such that the individual stamps are not distorted. 
     It is another object of the present invention to compensate a paint stamp before it is applied to a texture surface so that when it is transferred from texture space to world space the stamp shape appears as the artist would expect. 
     It is also an object of the present invention to provide a consistent coordinate frame that prevents rotational distortion, so that when the stamp is transferred from texture space to world space, the orientation of the stamp remains consistent. 
     It is a further object of the present invention to compensate for the distortions that can be caused by the paint stamp covering more than one polygon. 
     It is a further object of the present invention to provide a consistent set of distortion compensations, so that the individual stamps comprising a brush stroke will vary smoothly along the trajectory of the stroke, and embody it with a smooth appearance irrespective of the polygons affected by it. 
     The above objects can be attained by a system that predistorts a paint stamp using the difference in shape between the texture polygon and the world space target polygon before it is applied to a texture space surface. To preserve rotational invariance, a consistent coordinate frame is chosen for each surface within which the mapping between texture space and world space polygons occurs. The distortion compensation for a particular stamp inside a particular texture space polygon becomes a weighted average of the distortions of the target polygon and those of its three nearest neighbors. 
     These together with other objects 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 
     FIGS. 1A-1C depict distortion of a paint stamp when it is transferred from texture space to world space. 
     FIGS. 2A-2C illustrate predistortion that results in a correctly appearing stamp in world space. 
     FIG. 3 shows a system according to the present invention. 
     FIGS. 4 and 6 depict the operations of the present invention. 
     FIG. 5 depicts an incorrect mapping. 
     FIG. 7 illustrates a distortion corrected mapping. 
     FIG. 8 depicts how rotational invariance is preserved. 
     FIG. 9 shows triangles used in a numerical example. 
     FIGS. 10A-10F show the results of mapping with shape correction and with shape plus rotation correction. 
     FIG. 11 illustrates triangles used in weighted stamp compensation. 
    
    
     DESCRIPTION OF THE PREFERRED EMBODIMENTS 
     Computer generated paint stamps are distorted when texture triangles are warped to fit the corresponding world space triangles on a model surface. By judiciously stretching and rotating each stamp before it is applied to the texture space triangle, the overall effect of this warping can be nullified, thus producing identical looking stamps in world-space. This process is called stamp compensation. The present invention predistorts the stamp before it is applied to the texture space by essentially creating a distorted texture surface by stretching, warping, compressing, etc. the target texture space triangle, as if it were made of rubber, into the shape of the corresponding world space triangle, applying the stamp to that distorted texture surface and allowing the surface including the stamp to snap back to the shape of the original texture space triangle. As illustrated in FIGS. 2A-2C a desired paint stamp  8  (FIG. 2A) is predistorted and applied to a texture space triangle  10  (FIG. 2B) and then mapped to the desired world space surface triangle  12  (FIG.  2 C). 
     The present invention is preferably implemented in a computer system  20 , as depicted in FIG.  3 . An input device  22 , such as a stylus and tablet available from WACOM, capable of providing inputs for a paint program is coupled to a computer  24  and display  26 , such as an O2 available from Silicon Graphics, Inc. Of course other input devices, such as a mouse, and other computers, such as a personal computer, could be used. As the input device  22  is moved, paint is applied to a model displayed on display  26  by computer  24 . The individual brush stamps comprising this paint are compensated for the changes in shape, size and orientation of the texture space triangles and world space triangles used by the system to apply the paint to the model. 
     The process of applying a paint stamp to a model, as illustrated in FIG. 4, starts with obtaining  32  the cursor location as specified by the input device or paint brush. A stamp is typically placed on the model each time an input event occurs indicating that the brush has moved to a new location. The world space 3D triangle (polygon) under of the location of the cursor is identified  34  and the location of the cursor within the triangle is also determined  36 . Each world space triangle has a corresponding two dimensional (2D) texture space triangle (polygon) mapped to it and the corresponding texture space triangle is found  38  and the cursor location within the texture space triangle is determined  40 . Next, a source image is created  41  for the paint stamp. This step  41  involves the predistortion of the stamp before it is copied from the source to the texture triangle, which will be discussed in more detail with respect to FIG.  6 . Once the stamp image has been created, it is copied to the texture triangle at the location of the cursor  42 . After the paint stamp has been applied to the appropriate texture space triangles, the texture of the texture triangles is mapped  44  to the corresponding world space triangles, completing the painting process. 
     As previously mentioned the paint applied to a model is distorted when texture triangles are warped to fit the corresponding world space triangles. By predistorting the image of each stamp before it is copied to the texture triangle, the warping is removed or nullified producing identical looking stamps in world-space. 
     When generating each stamp image  52  (see FIG.  5 ), each stamp is considered as a planar linear transformation L, mapping the unit circle, C, to some ellipse S. Nominally, all a stamp generator must do is apply L to the unit circle to produce S: if a point p is inside C then Lp is in the ellipse S, and the pixel corresponding to Lp is drawn in the stamp image  52 . The stamp image is then copied to the texture space triangle  54 , as depicted in FIG.  5 . However this produces the incorrect shape in the world space triangle  56 . 
     Distortion compensation is achieved by producing or determining  75  (see FIG. 6) the appropriate linear warp factor M (see FIG.  7 ), which post-multiplies L to produce LM. The unit circle is thus transformed by L into the desired shape, S, which would produce the image  62  and is then warped by M into a new shape, S′, which produces the distorted stamp image  64 . This image is copied to the texture triangle  66 . When the texture triangle is mapped onto the world space surface triangle  68  by the texturing facilities of the system, the shape S′ is transformed back into the desired shape S (see FIG.  7 ). In this way, each stamp is placed on the object in such a way as if the paintbrush were always normal to the surface. 
     The appropriate linear transformation M (see FIG. 8) is the one that sends the three vertices of the world space triangle, A, to those of the corresponding texture-space triangle, B. It is produced in the following fashion. Assuming M is affine, it is uniquely determined by a non-degenerate triangle and its image. Thus, if t 1 ,t 2  are the directed edges of B, and w 1 ,w 2  are the corresponding ones in A, then M is found by solving: 
     
       
         Mw i =t i ,i=1,2  (1) 
       
     
     as depicted in FIG.  8 . More concisely, put T=(t 1 ,t 2 ), meaning the matrix with columns t 1  and t 2 , and put W=(w 1 ,w 2 ). Then equation 1 states that MW=T and therefore: 
     
       
         M=TW −1   (2) 
       
     
     In order to solve equation 2, w 1  and w 2  must be represented as planar vectors in the plane defined by A, as opposed to being represented as 3D vectors. One way to do this is to construct a planar orthonormal frame P={p 1 ,p 2 } out of the w i &#39;s:                p   1     =       w   1            w   1                    (   3   )                   p   2     =         (       w   1          w   2       )          w   1                (       w   1          w   2       )          w   1                ,           (   4   )                                
     where the wedge “{circumflex over ( )}” denotes the vector cross product. In this frame, the world space vectors are: 
     
       
         W′ 1 =(w 1 ·p 1 ,w 1 ·p 2 )=(∥w 1 ∥,0)  (5) 
       
     
      w′ 2 =(w 2 ·p 1 ,w 2 ·p 2 ).  (6) 
     Putting W′=(w′ 1 ,w′ 2 ) and substituting it for W in equation 2 will produce the required M. 
     Unfortunately, the embedded frame P depends completely on the orientation of A, and therefore varies from triangle to triangle. To preserve rotational coherence between adjacent polygons, a consistent coordinate frame must be chosen. To do this, the world space triangle is essentially rotated in space into planar coincidence with the texture space triangle while keeping the origin fixed. The following method produces  74  (see FIG. 6) a 2D frame coplanar with A in such a way that the orientation of A matches that of B. Assuming B (and A) are non-degenerate, the vectors t 1 ,t 2  span the plane embodying B, which means that every point in that plane can be specified as a barycentric combination of these vectors. Specifically, the standard basis vectors {e 1 ,e 2 } can be specified in terms of t 1 ,t 2 . Let s 1 =(s 11 ,s 12 ) be the barycentric coordinates of e 1  with respect to the t i &#39;s (i.e., e 1 =s 11 t 1 +s 12 t 2 ), and let s 2 =(s 21 ,s 22 ) be those of e 2 . Now let the vectors f 1 ,f 2  be those with barycentric coordinates s 1 ,s 2  with respect to the edges of A: f i =s i1 w 1 +s i2 w 2 , (i=1,2). Using the method described in equations 3 and 4, produce an orthonormal frame Q={q 1 ,q 2 } from {f 1 ,f 2 }:                q   1     =       f   1            f   1                    (   7   )                 q   2     =         (       f   1          f   2       )          f   1                (       f   1          f   2       )          f   1                      (   8   )                                
     Finally, put f′ 1 ,f′ 2  as the vectors corresponding to f i &#39;s in the {q 1 ,q 2 } basis, as in equations 5 and 6: 
     
       
         f′ 1 =(f 1 ·q 1 ,f 1 ·q 2 )=(∥f 1 ∥,0)  (9) 
       
     
     
       
         f′ 2 =(f 2 ·q 1 ,f 2 ·q 2 )  (10) 
       
     
     By definition M is linear and is therefore uniquely determined by mapping w i  to t i . Since barycentric combinations preserve linearity it is therefore true that Mf′ 1 =e 1 =(1,0) and Mf′ 2 =e 2 =(0,1). Putting F′=(f′ 1 ,f′ 2 ), we have that:                  MF   ′     =       (         1       0           0       1         )     =   I       ,           (   11   )                                
     and therefore, 
     
       
         M=F′ −1   (12) 
       
     
     as depicted in FIG.  8 . 
     The actual computation of {f 1 ,f 2 } is straight forward. Put                  T   ′     =       T   t     =       (       t   1       t   2       )     =     (           t   11           t   12               t   21           t   22           )           ,           (   13   )                                
     the change of basis matrix between the standard 2D basis {e 1 ,e 2 } and the basis {t 1 ,t 2 }. Each row of T′ represents a new basis vector as a linear combination of the old ones. The matrix S=T′ −1  is the change of basis matrix from {t 1 ,t 2 } to the standard basis. Its rows, therefore, represent the standard basis as linear, or barycentric combinations of t 1  and t 2 . Thus 
     
       
         e 1 =s 11 t 1 +s 12 t 2 , and  (14) 
       
     
     
       
         e 2 =s 21 t 1 +s 22 t 2 ,  (15) 
       
     
     Applying M to both sides in equations 14 and 15 produces: 
     
       
         f 1 =s 11 w 1 +s 12 w 2 , and  (16) 
       
     
     
       
         f 2 =s 21 w 1 +s 22 w 2 .  (17) 
       
     
     Once the coordinate frame is known, the warp factor is computed  75  and applied  76  (see FIG. 6) to the stamp to create the stamp source image before it is copied to the texture surface. 
     To provide an example of computing the warp factor, numerical examples are provided below for two sets of triangles as depicted in FIG.  9 . The examples will discuss the development of the warp factor matrix when only shape compensation is performed and when both shape and rotation compensation are performed. In FIG. 9, 2D texture triangle B 1 (x,y,w) maps to 3D world space triangle A 1 (a,b,d) and texture triangle B 2 (w,y,z) maps to world space triangle A 2 (d,b,c). For simplification, the texture triangles are identical to the world space triangles, but the process is the same for non-identical triangles where the coordinates of the vertices change. 
     For triangles B 1 , A 1  we have the following: 
     
       
         t1=y−x=(1,0)−(0,0)=(1,0)  (18) 
       
     
     
       
         t2=w−x=(0,1)−(0,0)=(0,1)  (19) 
       
     
     
       
         w1=b−a=(1,0,0)−(0,0,0)=(1,0,0)  (20) 
       
     
     
       
         w2=d−a=(0,1,0)−(0,0,0)=(0,1,0)  (21) 
       
     
     When there is no rotational compensation for mapping triangle B 1  to triangle A 1 , the warp factor matrix M is computed as follows:              T   =     (         1       0           0       1         )             (   22   )                                
     The coordinate frame P is:                p   1     =         w   1            w   1            =         (     1   ,   0   ,   0     )     1     =     (     1   ,   0   ,   0     )                 (   23   )                               (w 1 {circumflex over ( )}w 2 ){circumflex over ( )}w 1 =(0,0,1){circumflex over ( )}W 1 =(0,1,0)  (24) 
     
       
         
           
             
               
                 
                   
                     p 
                     2 
                   
                   = 
                   
                     
                       
                         ( 
                         
                           0 
                           , 
                           1 
                           , 
                           0 
                         
                         ) 
                       
                       1 
                     
                     = 
                     
                       ( 
                       
                         0 
                         , 
                         1 
                         , 
                         0 
                       
                       ) 
                     
                   
                 
               
               
                 
                   ( 
                   25 
                   ) 
                 
               
             
           
         
                 
         
             
         
      
     
     W′ is computed as 
     
       
         w′ 1 =(w 1 ·p 1 ,w 1 ·p 2 )=(1,0) 
       
     
     
       
         w′ 2 =(w 2 ·p 1 ,w 2 ·p 2 )=(0,1)  (26) 
       
     
     
       
         
           
             
               
                 
                   
                     ∴ 
                     
                       W 
                       ′ 
                     
                   
                   = 
                   
                     ( 
                     
                       
                         
                           1 
                         
                         
                           0 
                         
                       
                       
                         
                           0 
                         
                         
                           1 
                         
                       
                     
                     ) 
                   
                 
               
               
                 
                   ( 
                   27 
                   ) 
                 
               
             
           
         
                 
         
             
         
      
     
     Therefore            W     ′   -   1       =     (         1       0           0       1         )       ,                          
     and the warp factor M is              M   =       T                   W     ′   -   1         =       (         1       0           0       1         )     =   identity               (   28   )                                
     When there is rotation compensation along with shape compensation for mapping triangle B 1  to triangle A 1 , the warp factor matrix M is computed as follows:                T   ′     =         (         1       0           0       1         )                   so                   T     ′   -   1         =         (         1       0           0       1         )                   and                 S     =       T     ′   -   1       =       (         1       0           0       1         )     .                   (   29   )                                
     Therefore, 
     
       
         f 1 =1·w 1 +0·w 2 =(1,0,0)  (30) 
       
     
     
       
         f 2 =0·w 1 +1·w 2 =(0,1,0)  (31) 
       
     
                     q   1     =         f   1            f   1            =         (     1   ,   0   ,   0     )     1     =     (     1   ,   0   ,   0     )                 (   32   )                               (f 1 {circumflex over ( )}f 2 ){circumflex over ( )}f 1 =(0,0,1){circumflex over ( )}f 1 =(0,1,0)  (33) 
     
       
         
           
             
               
                 
                   
                     q 
                     2 
                   
                   = 
                   
                     
                       
                         ( 
                         
                           0 
                           , 
                           1 
                           , 
                           0 
                         
                         ) 
                       
                       1 
                     
                     = 
                     
                       ( 
                       
                         0 
                         , 
                         1 
                         , 
                         0 
                       
                       ) 
                     
                   
                 
               
               
                 
                   ( 
                   34 
                   ) 
                 
               
             
           
         
                 
         
             
         
      
     
     F′ is computed as: 
     
       
         
           
             
               
                 
                   
                     
                       
                         
                           
                             
                               f 
                               1 
                               ′ 
                             
                             = 
                             
                               
                                 ( 
                                 
                                   
                                     
                                       f 
                                       1 
                                     
                                     · 
                                     
                                       q 
                                       1 
                                     
                                   
                                   , 
                                   
                                     
                                       f 
                                       1 
                                     
                                     · 
                                     
                                       q 
                                       2 
                                     
                                   
                                 
                                 ) 
                               
                               = 
                               
                                 ( 
                                 
                                   1 
                                   , 
                                   0 
                                 
                                 ) 
                               
                             
                           
                         
                       
                       
                         
                           
                             
                               f 
                               1 
                               2 
                             
                             = 
                             
                               
                                 ( 
                                 
                                   
                                     
                                       f 
                                       2 
                                     
                                     · 
                                     
                                       q 
                                       1 
                                     
                                   
                                   , 
                                   
                                     
                                       f 
                                       2 
                                     
                                     · 
                                     
                                       q 
                                       2 
                                     
                                   
                                 
                                 ) 
                               
                               = 
                               
                                 ( 
                                 
                                   0 
                                   , 
                                   1 
                                 
                                 ) 
                               
                             
                           
                         
                       
                     
                      
                     
                         
                     
                      
                     so 
                      
                     
                         
                     
                      
                     
                       F 
                       ′ 
                     
                   
                   = 
                   
                     ( 
                     
                       
                         
                           1 
                         
                         
                           0 
                         
                       
                       
                         
                           0 
                         
                         
                           1 
                         
                       
                     
                     ) 
                   
                 
               
               
                 
                   ( 
                   35 
                   ) 
                 
               
             
           
         
                 
         
             
         
      
     
     The warp factor M is therefore                ∴   M     =       F     ′   -   1       =       (         1       0           0       1         )     =   identity               (   36   )                                
     In order to draw stamp  90  such as illustrated in FIG. 10A on world space triangle A 1  (see FIG.  9 ), a stamp image  92  in FIG. 10B is created. Since the identical warp factor is used when compensating for shape and rotation as is used when compensating for shape only, the pre-warped stamp image created for both will be the one  92  in FIG.  10 B. This image is then copied to triangle  94  in FIG. 10C and 106 in FIG.  10 E. When texture triangles  94  and  106  are mapped to world space triangles  98  and  102  respectively, the stamps appear correctly. 
     For triangle B 2 ,A 2  we have the following: 
     
       
         t1=y−w=(1,0)−(0,1)=(1,−1)  (37) 
       
     
     
       
         t2=z−w=(1,1)−(0,1)=(1,0)  (38) 
       
     
     
       
         w1=b−d=(1,0,0)−(0,1,0)=(1,−1,0)  (39) 
       
     
     
       
         w2=c−d=(1,1,0)−(0,1,0)=(1,0,0)  (40) 
       
     
     When there is no rotational compensation for mapping triangle B 2  to triangle A 2 , the warp factor M is computed as follows:              T   =     (         1       1             -   1         0         )             (   41   )                                
     The coordinate frame P is:                p   1     =         w   1            w   1            =         (     1   ,     -   1     ,   0     )       2       =     (       1     2       ,       -   1       2       ,   0     )                 (   42   )                               (w 1 {circumflex over ( )}w 2 ){circumflex over ( )}w 1 =(0,0,1){circumflex over ( )}w 1 =(1,1,0)  (43) 
     
       
         
           
             
               
                 
                   
                     p 
                     2 
                   
                   = 
                   
                     
                       
                         ( 
                         
                           1 
                           , 
                           1 
                           , 
                           0 
                         
                         ) 
                       
                       
                         2 
                       
                     
                     = 
                     
                       ( 
                       
                         
                           1 
                           
                             2 
                           
                         
                         , 
                         
                           1 
                           
                             2 
                           
                         
                         , 
                         0 
                       
                       ) 
                     
                   
                 
               
               
                 
                   ( 
                   44 
                   ) 
                 
               
             
           
         
                 
         
             
         
      
     
     W′ is computed as:                  w   1   ′     =       (         w   1     ·     p   1       ,       w   1     ·     p   2         )     =     (       2     2       ,   0     )              
            w   2   ′     =       (         w   2     ·     p   1       ,       w   2     ·     p   2         )     =     (       1     2       ,     1     2         )              
            so                   W   ′       =     (           2     2             1     2               0         1     2             )               (   45   )                                
     Therefore                w     ′   -   1       =     (           2     2               -   1       2               0         2     2             )             (   46   )                                
     and the warp factor M is:              M   =         TW     ′   -   1            (         1       1             -   1         0         )            (           1     2             -                1     2                 0         2     2             )               (   48   )                            =     (           1     2             1     2                 -                1     2               1     2             )               (   49   )                                              =     Rotation                 by                 45      °       ,     then                 uniform                 scale                 by                   1     2                 (   50   )                                 
     When there is rotation compensation along with shape compensation for the triangle B 2  to triangle A 2  the warp factor M is computed as follows:                  T   ′     =         (         1         -   1             1       0         )                   and                 S     =       T     ′   -   1       =     (         0       1             -   1         1         )                              (   51   )                                
     Therefore, 
     
       
         f 1 =0·w 1 +1·w 2 =(1,0,0)  (52) 
       
     
     
       
         f 2 =−1·w 1 +1·w 2 =(0,1,0)  (53) 
       
     
     The coordinate frame Q is:                q   1     =         f   1            f   1            =         (     1   ,   0   ,   0     )     1     =     (     1   ,   0   ,   0     )                 (   54   )                               (f 1 {circumflex over ( )}f 2 ){circumflex over ( )}f 1 =(0,0,1){circumflex over ( )}f 1 =(0,1,0)  (55) 
     
       
         
           
             
               
                 
                   
                     q 
                     2 
                   
                   = 
                   
                     
                       
                         ( 
                         
                           0 
                           , 
                           1 
                           , 
                           0 
                         
                         ) 
                       
                       1 
                     
                     = 
                     
                       ( 
                       
                         0 
                         , 
                         1 
                         , 
                         0 
                       
                       ) 
                     
                   
                 
               
               
                 
                   ( 
                   56 
                   ) 
                 
               
             
           
         
                 
         
             
         
      
     
     F′ is computed as: 
     
       
         f′ 1 =(f 1 ·q 1 ,f 1 ·q 2 )=(1,0) 
       
     
     
       
         f′ 2 =(f 2 ·q 1 ,f 2 ·q 2 )=(0,1)  (57) 
       
     
     
       
         
           
             
               
                 
                   
                     
                       so 
                        
                       
                           
                       
                        
                       
                         F 
                         ′ 
                       
                     
                     = 
                     
                       ( 
                       
                         
                           
                             1 
                           
                           
                             0 
                           
                         
                         
                           
                             0 
                           
                           
                             1 
                           
                         
                       
                       ) 
                     
                   
                    
                   
                       
                   
                 
               
               
                 
                   ( 
                   58 
                   ) 
                 
               
             
           
         
                 
         
             
         
      
     
     The warp factor M is therefore              M   =       F     ′   -   1       =       (         1       0           0       1         )     =   identity               (   59   )                                
     In order to draw stamp  90  such as illustrated in FIG. 10A on world space triangle A 2 , a stamp image must be created. Stamp image  93  as shown in FIG. 10B is created when shape compensation but no rotational compensation is taken into account. However, when rotational compensation and shape compensation are both taken into account, stamp image  92  as shown in FIG. 10B is created. These images are then copied to texture triangles  96  (image  93 ) and  108  (image  92 ) in FIG. 10C and 10E, respectively. When texture triangle  96  in FIG. 10C is mapped onto world space triangle  100  in FIG. 10D, the stamp shows up incorrectly. However, when texture triangle  108  in FIG. 10E is mapped onto world-space triangle  104  in FIG. 10F, the appearance of the stamp is correct. 
     As previously mentioned, a brush stroke consists of a sequence of consecutive stamps applied to the surface. Distortion compensation must be computed for each individual stamp before it is applied. The warp factor matrix M, however, compensates for a stamp which lies completely inside a single triangle. Unfortunately, this is seldom the case as stamps will generally overlap several triangles whose individual distortions differ, thus giving the stroke a very jagged appearance. The problem may be overcome by using weighted stamp compensation. 
     For each stamp, the distortion matrix used is the weighted “butterfly” or cross average of the matrices of the target polygon and that of its neighbors. As the stroke moves across a polygon, the next polygon along the path is given ever increasing influence on the current distortion. The stamp shape is thus gradually distorted from one polygon to the next, smoothing out the appearance of the stroke. 
     Weighted compensation is computed as follows. At each vertex, the estimated distortion is given as the arithmetic mean of that of the triangle under the center of the stamp (the current triangle) and that of the two triangles adjacent to it who share the vertex. Double weight is assigned to the current triangle when computing the mean. For example, in FIG. 11, the triangles affecting vertex c are W (the current triangle  112 ), U (the triangle on the right  114 ,) and V (the triangle on the left  116 ) The distortion matrix M c  at vertex c is therefore:                M   c     =         2        M   W       +     M   U     +     M   V       4             (   60   )                                
     For a stamp centered at point p in triangle W  112 , having barycentric coordinates (u,v,w) with respect to the vertices a,b,c of triangle  112  (i.e., p=ua+vb+wc), the distortion matrix, M p  at p is computed as the barycentric combination of the estimated vertex distortion:                M   p     =       uM   a     +     vM   b     +     wM   c               (   61   )                            =         2        M   W       +       (     1   -   u     )          M   U       +       (     1   -   v     )          M   V       +       (     1   -   w     )          M   X         4               (   62   )                                
     It is sometimes the case that a triangle has no adjacent neighbor across one of its edges. In this case, the distortion of the current triangle is substituted for that of the missing neighbor. That is, if triangle X (the bottom triangle  118 ) was missing from FIG. 11, the distortion at the vertex a would be computed as: 
     
       
         M a =(3M w +M v )/4  (63) 
       
     
     The process described above requires finding the unique polygon that lies under the mouse pointer to compute its distortion compensation. This follows the assumption that all polygons along the path of the cursor will be hit. Unfortunately, this may not always be the case as sliver triangles and those with sub-pixel extent may be overlooked by the algorithm and ignored. Fortunately this is not a grave problem, as the process of painting is incremental in nature. The workflow typically consists of painting several strokes, then rotating the object, and painting several more. Textures are often touched up and painted directly regardless of the paint mode. In this way, all the required triangles will eventually get painted. 
     The present invention has been described with respect to the texture space and world space tessellations being triangles, however, it is possible for the tessellations to be any shape polygon. When the tessellated polygons are quadrilateral, the shape distortion compensation may be computed using a projective surface parameterization. Conformal maps may be used to compute the compensation factor for polygons of any degree. 
     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 which 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 scope of the invention.