Abstract:
A polygon data generating apparatus, comprising: an initial connection data generator configured to generate connection data relating to connection information of vertices, sides and faces, based on vertex data of the inputted polygon; a new connection data generator configured to generate new connection data based on said connection data; a new vertex data generator configured to generate new vertex data based on said vertex data and said connection data; a data combining part configured to combine said new connection data relating to the same vertex; a connection data storing part configured to store the connection data generated by said initial connection data generator and said new connection data generator, and the connection data combined by said data combining part; and a vertex data storing part configured to store the inputted vertex data and the vertex data generated by said new vertex data generator, wherein said new connection data generator repeatedly generates said new connection data based on the connection data stored in said connection data storing part; and said new vertex data storing part repeatedly generates said new vertex data based on the connection data stored in said connection data storing part and the vertex data stored in said vertex data storing part.

Description:
CROSS REFERENCE TO RELATED APPLICATIONS  
         [0001]    This application is based upon and claims the benefit of priority from the prior Japanese Patent Applications No. 2001-101674, filed on Mar. 30, 2001, the entire contents of which are incorporated herein by reference.  
         BACKGROUND OF THE INVENTION  
         [0002]    1. Field of the Invention  
           [0003]    The present invention relates to a polygon data generating apparatus and a drawing system for generating polygon data for drawing 3D-objects as a collection of polygons.  
           [0004]    2. Related Background Art  
           [0005]    A CPU and a graphic control chip perform processings collectively in order to realize 3D-graphics. The 3D-objects are generally drawn as a collection of the polygons. The objects have to be divided into a lot of polygons to display the objects of which curved surface is smooth.  
           [0006]    However, when the objects are divided into a lot of polygons, the amount of data transferred between the CPU and the GPU increases. Because of this, the smoothness of the curved surface is limited by a bus band width between the CPU and the GPU.  
           [0007]    On the other hand, a subdivision surface processing has been proposed. In the subdivision surface processing, the polygons are repeatedly divided into small pieces in order to smooth the curved surface.  
           [0008]    When the subdivision surface processing is implemented by software, the CPU has to execute a complicated and a large amount of list processing. Because of this, there is a problem in which the load of the CPU is large and a processing performance of the CPU is not improved.  
         SUMMARY OF THE INVENTION  
         [0009]    A polygon data generating apparatus according to an embodiment of the present invention, comprising:  
           [0010]    an initial connection data generator configured to generate connection data relating to connection information of vertices, sides and faces, based on vertex data of the inputted polygon;  
           [0011]    a new connection data generator configured to generate new connection data based on said connection data;  
           [0012]    a new vertex data generator configured to generate new vertex data based on said vertex data and said connection data;  
           [0013]    a data combining part configured to combine said new connection data relating to the same vertex;  
           [0014]    a connection data storing part configured to store the connection data generated by said initial connection data generator and said new connection data generator, and the connection data combined by said data combining part; and  
           [0015]    a vertex data storing part configured to store the inputted vertex data and the vertex data generated by said new vertex data generator,  
           [0016]    wherein said new connection data generator repeatedly generates said new connection data based on the connection data stored in said connection data storing part; and  
           [0017]    said new vertex data generator repeatedly generates said new vertex data based on the connection data stored in said connection data storing part and the vertex data stored in said vertex data storing part. 
       
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0018]    [0018]FIG. 1 is a diagram of an embodiment of a polygon data generating system according to the present invention.  
         [0019]    [0019]FIG. 2 is a flowchart showing the entire processing operation of the polygon data generating apparatus according to the present embodiment.  
         [0020]    [0020]FIG. 3 is a diagram showing an example of the polygon.  
         [0021]    [0021]FIG. 4A- 4 C is a diagram showing an example of connection data.  
         [0022]    [0022]FIG. 5 is a flowchart showing a processing operation of the initial connection data generator.  
         [0023]    [0023]FIG. 6 is a diagram showing an example of the polygon.  
         [0024]    [0024]FIG. 7 is a diagram showing connection information of v 1  in FIG. 6.  
         [0025]    [0025]FIG. 8 is a diagram showing connection information of v 0  in FIG. 6.  
         [0026]    [0026]FIG. 9 is a diagram showing connection information of v 2  in FIG. 6.  
         [0027]    [0027]FIG. 10A- 10 B are diagrams in which new vertex is added to the polygon of FIG. 6.  
         [0028]    [0028]FIG. 11 is a diagram showing connection information of v 1  in FIG. 10A.  
         [0029]    [0029]FIG. 12A- 12 B are diagrams showing connection information of v 2  in FIG. 10A- 10 B.  
         [0030]    [0030]FIG. 13 is a diagram showing connection information of v 3  in FIG. 10A.  
         [0031]    [0031]FIG. 14 is a diagram showing an example of the polygon.  
         [0032]    [0032]FIG. 15 is a diagram showing connection information of v 3  in FIG. 14.  
         [0033]    [0033]FIG. 16A- 16 B are diagrams showing connection information of v 5  and v 7  in FIG. 14.  
         [0034]    [0034]FIG. 17 is a diagram showing an example of the polygon.  
         [0035]    [0035]FIG. 18 is a diagram showing connection information of v 3  in FIG. 17.  
         [0036]    [0036]FIG. 19A- 19 B are diagrams showing connection information of v 5  and v 7  in FIG. 17.  
         [0037]    [0037]FIG. 20 is a diagram showing an example of the polygon.  
         [0038]    [0038]FIG. 21A- 21 B are diagrams showing connection information of v 3  in FIG. 20.  
         [0039]    [0039]FIG. 22 is a flowchart showing a processing procedure of catmull-clark method.  
         [0040]    [0040]FIG. 23 is a diagram showing an example of the polygon.  
         [0041]    [0041]FIG. 24 is a diagram showing a table configuration of the second vertex data storing part.  
         [0042]    [0042]FIG. 25A- 25 B are diagrams for explaining the side point.  
         [0043]    [0043]FIG. 26A- 26 D are diagrams for explaining the face point.  
         [0044]    [0044]FIG. 27 is a diagram showing an embodiment of a drawing system having the polygon data generating system according to the present embodiment.  
         [0045]    [0045]FIG. 28 is a layout diagram of an LSI for integrating the GPU  12  of FIG. 27 as one chip.  
         [0046]    [0046]FIG. 29A- 29 B are diagrams showing an example of the polygon.  
         [0047]    [0047]FIG. 3OA- 30 B are diagrams showing an example of the polygon. 
     
    
     DESCRIPTION OF THE PREFERRED EMBODIMENTS  
       [0048]    Hereinafter, an embodiment of a polygon data generating apparatus and a drawing system according to the present invention will be more specifically described with reference to drawings.  
         [0049]    [0049]FIG. 1 is a block diagram of an embodiment of a polygon data generating system according to the present invention. In the polygon data generating apparatus of FIG. 1, vertex data is inputted clockwise or counterclockwise in sequence. Hereinafter, although an example in which the vertex data is inputted counterclockwise will be described, the same processings are performed even in the case where the vertex data is inputted clockwise.  
         [0050]    The polygon data generating apparatus of FIG. 1 has an initial connection data generator  1  for generating after-mentioned connection data based on the vertex data of the inputted polygon, a first connection data storing part  2  for storing the generated connection data, a first vertex data storing part  3  for storing the inputted vertex data, a new connection data generator  4  for generating new connection data by performing after-mentioned subdivision surface processing, a new vertex data generator  5  for generating new vertex data based on the original connection data, a second connection data storing part  6  for storing the generated new connection data, a second vertex data storing part  7  for storing the generated new vertex data, and a data combining part  8  for combining a plurality of connection data relating to the same vertex.  
         [0051]    [0051]FIG. 2 is a flowchart showing the entire processing operation of the polygon data generating apparatus according to the present embodiment.  
         [0052]    First of all, the initial connection data generator  1  generates the connection data based on the vertex data of the inputted rough initial polygon (step S 1 ). The generated connection data is stored in the first connection data storing part  2 , and the inputted vertex data is stored in the first vertex data storing part  3  (step S 2 ).  
         [0053]    Subsequently, the new vertex data generator  4  and the new vertex data generator  5  generate new connection data and new vertex data, respectively, by performing after-mentioned subdivision surface processing based on the connection data stored in the first connection data storing part  2  and the vertex data stored in the first vertex data storing part  3  (step S 3 ). The newly generated connection data is stored in the second connection data storing part  6 , and the newly generated vertex data is stored in the second vertex data storing part  7  (step S 4 ).  
         [0054]    Subsequently, the data combining part  8  combines all the connection data relating to the same vertex (step S 5 ). The combined connection data is stored in the first connection data storing part  2 , and the vertex data stored in the second vertex data storing part  7  is stored in the first vertex data storing part  3  (step S 6 ).  
         [0055]    The above-mentioned processings of step S 3 -S 6  are repeatedly performed until when the curved surfaces of the polygon are divided into sufficiently small pieces (step S 7 ).  
         [0056]    As a more specified example, the subdivision surface processing for the polygon of FIG. 3 will be described hereinafter. Although FIG. 3 shows an example in which each surface of the polygon is a quadrangle, the shape of the surface may be triangular shape.  
         [0057]    In the polygon data generating apparatus of FIG. 1, the vertex data of FIG. 3 is inputted counterclockwise in sequence. The initial connection data generator  1  generates the connection data by allocating to the vertices, the sides and the faces of the polygon, inherent and continuous numerals as shown in FIG. 3. In FIG. 3, the numerals of the vertices are expressed as v 1 -v 8 , the numerals of the sides as e 0 -e 3 , and the numerals of the faces as f 0 -f 3 .  
         [0058]    The vertex data inputted in the initial connection data generator  1  is composed of a vertex coordinate, a normal line vector of the vertex, a texel coordinate of the vertex and so on. Here, the normal line vector of the vertex shows a normal line vector of a minute plane including the vertex among curved surfaces formed of the vertex and the neighborhood vertex. The texel coordinate of the vertex shows a coordinate location in the case of performing texture mapping.  
         [0059]    The connection data generated by the initial connection data generator  1  is composed of the number of the sides including the vertices, the number of the faces including the vertices, an inherent number of the sides including the vertices and an inherent number of the other end of the side, an inherent number of the faces including the vertices and an inherent number of the vertex on a diagonal line the face or an inherent number of the vertex neighbor by sandwiching the other vertex and so on.  
         [0060]    In this specification, the vertex is expresses as “v”, the side as “e”, and the face as “f”. For example, when the vertex data relating to the vertex v 0  of the polygon of FIG. 3 is inputted in the initial connection data generator  1 , the connection data such as shown in FIG. 4A is generated. The number of the sides including the vertices is “4”, the number of the faces including the vertices is “4”, inherent number of the sides including the vertices and inherent numbers of the other ends of the sides are (e 1 , v 3 )(e 2 , v 5 )(e 3 , v 7 )(e 0 , v 1 ), inherent numbers of the faces including the vertices and inherent numbers of the vertices on the diagonal line of the face or inherent numbers of the vertex neighbor by sandwiching the other vertex are (f 1 , v 4 ) (f 2 , v 6 ) (f 3 , v 8 )(f 0 , v 2 ).  
         [0061]    Hereinafter, as a simplified model, the connection data is expressed by (the number of sides including vertices, the number of faces including vertices, an identifier showing whether or not the other connection data exists), (an inherent number of the side, an inherent number of the other end of the side), and (an inherent number of the face, the vertex on diagonal of the face or an inherent number of the second vertex from the objective).  
         [0062]    As the identifier showing whether or not the other connection data exists, there are “false” showing that the other connection data does not exist and “true” showing that the other connection data exists.  
         [0063]    For example, if FIG. 4A is expressed by a form of FIG. 4B, FIG. 4C is obtained.  
         [0064]    [0064]FIG. 5 is a flowchart showing a processing operation of the initial connection data generator  1 , and shows the processing operation in the case where the vertex data of the triangle is inputted. First of all, whether or not the same vertex data as the inputted vertex data was inputted before is determined (step S 11 ). Here, the first connecting data generator  1  searches for the first vertex data storing part  3 , and checks whether or not the same vertex data exists.  
         [0065]    As a result, if the same vertex data is not stored in the first vertex data storing part  3 , a new numeral is attached to the vertex and the vertex is added to an entry of the initial connection data generator  1 . Here, the addition of the entry means a registration of a new connection data.  
         [0066]    On the other hand, if the same vertex data is already stored in the first vertex data storing part  3 , the corresponding connection data is read out from the first connection data storing part  2 .  
         [0067]    Subsequently, connection information of the triangle composed of two vertices of the newly inputted vertex and the previously inputted vertex are added to the connection data of each vertex (step S 13 ).  
         [0068]    For example, as shown in FIG. 6, it is assumed that the vertices v 0  and v 1  were already inputted and the vertex data of the vertex v 2  is newly inputted. In FIG. 6, the inherent numbers of the vertices are v 0 , v 1  and v 2 , the inherent numbers of the sides are e 0 , e 1  and e 2 , and the inherent number of the face is f 0 .  
         [0069]    In this case, the connection information for the vertex v 2  is added to the connection data of the vertices v 0  and v 1 . At this time, if assumed that the vertex v 2  is data inputted at odd turn, connection information (e 2 , v 2 )(−f 0 , don&#39;t care) is added just before the side information (e 0 ,v 0 ) registered just before in the connection data of the vertex inputted one before, i.e., the vertex v 1  inputted at even number turn. Furthermore, the connection information (e 1 , v 2 ) for the vertex v 2  is added to the connection data of the vertex inputted two before, that is, the vertex v 0  inputted at odd number turn. In this case, the connection information (e 1 , v 2 ) is added just after the side information (e 0 , v 1 )(−f 0 , don&#39;t care) registered just before, as shown in FIG. 8. on the other hand, the connection data of the newly added vertex v 2  is shown in FIG. 9.  
         [0070]    In FIGS.  7 - 9 , symbols before the face numerals show whether the faces are the triangle or the quadrangle. For example, the triangle is expressed as minus symbol, and the quadrangle is expressed as plus symbol. The “don&#39;t care” means that there is no vertex on the opposite corner.  
         [0071]    Afterward, as shown in FIG. 10A, if assumed that the vertex data of the vertex v 3  is inputted newly, the connection information to the vertex v 3  is added to a head of the connection data of the vertex v 1 , as shown in FIG. 11. The connection information for the vertex v 3  is added to the end of the connection data of the vertex v 2 , as shown in FIG. 12A, and the connection data of the vertex v 3  is shown in FIG. 13.  
         [0072]    For example, as shown in FIG. 10B, if assumed that the vertex v 4  exists besides the vertex v 3 , the connection data of the vertex v 2  in this case is shown in FIG. 12B. In this case, because the vertex v 3  exists on the diagonal line, the connection data becomes (f 1 , v 3 ) instead of “don&#39;t care”.  
         [0073]    The processing operation of the initial connection data generator  1  will be described again based on FIG. 5. In the above-mentioned step S 1  of FIG. 5, if determined that the vertex data relating to the same vertex is inputted, whether or not the vertex data is input counterclockwise is determined( step S 14 ). If the vertex data is not inputted counterclockwise, it is determined whether or not the vertex data is odd number turn (step S 15 ). If the vertex data is inputted counterclockwise, it is determined whether or not the vertex data is odd number turn (step S 16 ).  
         [0074]    If determined not to be odd number turn in step S 15 , or if determined to be odd number turn in step S 16 , it is determined whether or not the side corresponding to the head line in the connection data of the vertex inputted two before is equal to the side to be added (step S 17 ).  
         [0075]    If determined that both sides are equal to each other, the side information and the face information are added to the connection data (step S 18 ). If determined that both sides are equal to each other, only the face information is added to the connection data, and it is determined that the surrounding of the objective vertex is enclosed by the series of polygons (step S 19 ).  
         [0076]    When the processings of step S 18  and S 19  is finished, it is determined whether or not the side of the last line in the connection data of the vertex inputted one before is equal to the side to be added (step S 20 ).  
         [0077]    When determined that both sides are not equal to each other, the side information and the face information are added to the connection data (step S 21 ). When determined to be equal, only the face information is added to the connection data, and it is determined that the surrounding of the objective vertex is enclosed (step S 22 ). In this case, because any more new information is not added to the connection data, the connection data corresponding to the vertex is deleted from the entries of the initial connection data generator  1 .  
         [0078]    On the other hand, if it is determined to be odd number turn in step S 15 , or it is determined not to be odd number turn in step S 16 , it is determined whether or not the side of the last line in the connection data of the vertices inputted two before is equal to the side to be added (step S 23 ).  
         [0079]    If determined not to be equal, the side information and the face information are added to the connection data (step S 24 ). If determined to be equal, only the face information is added to the connection data, and it is determined that the surrounding of the objective vertex is enclosed by series of polygons (step S 25 ).  
         [0080]    The processings of step S 24  and S 25  are finished, it is determined whether or not the side of the head line in the connection data of the vertex inputted one before is equal to the side to be added (step S 26 ).  
         [0081]    If determined not to be equal, the side information and the face information are added to the connection data (step S 27 ). If determined to be equal, only the face information is added to the connection data, and the surrounding of the objective vertex is enclosed by series of polygons (step S 28 ).  
         [0082]    Next, an example in which the initial connection data generator  1  generates the connection data of the polygon of FIG. 14 will be described hereinafter.  
         [0083]    For example, as shown in FIG. 14, it is assumed that the vertex data of the vertices v 1 -v 7  are already inputted, the connection data of the vertex v 3  is expressed by FIG. 15 at this time, and the connection data of the vertices v 5  and v 7  are expressed by FIG. 16A and FIG. 16B, respectively.  
         [0084]    Furthermore, among the already inputted vertex data, the vertex data of the vertex v 3  is inputted two before, the vertex data of the vertex v 7  is inputted one before, and then the vertex data of the vertex v 5  is inputted.  
         [0085]    In this case, as shown in FIG. 17, information relating to the side e 13  and the face f 6  are added to the connection data of the vertices v 3  and v 7 , respectively. More specifically, because the side e 7  consisted of the vertices v 3  and v 5  already exists, only the information of the face f 6  is added to the connection data of the vertex v 3 , as shown in FIG. 18, and the information of the side e 13  and the face f 6  are added to the respective connection data of the vertices v 5  and v 7 , as shown in FIG. 19A and FIG. 19B.  
         [0086]    Furthermore, depending on the shape of the polygon, there is a case where the connection data is divided into a plurality of pieces, as shown in FIG. 20. In FIG. 20, with regard to the vertex v 3 , the connection data shown in FIG. 21A consisted of the vertices v 0 , v 1 , v 2 , v 4  and v 5 , and the connection data shown in FIG. 21B consisted of the vertices v 6 , v 7 , v 8  and v 9  are generated. When the other multiple connection data exists with regard to the same vertex, the “true” identifier is registered to the connection data as shown in FIG. 21A.  
         [0087]    When all the connection data is generated by the initial connection data generator  1  based on the above-mentioned procedure, the new connection data generator  4 , the new vertex data generator  5  and the data combining part  8  performs the subdivision surface processing based on the connection data stored in the first connection data storing part  2  and the vertex data stored in the first vertex data storing part  3 .  
         [0088]    [0088]FIG. 22 is a flowchart showing a processing procedure of catmull-clark method, which is one method of the subdivision surface processing. The flowchart describes the processing procedure of step S 3 -S 6  of FIG. 2 in detail.  
         [0089]    First of all, the new connection data generator  4  calculates the inherent number of the newly generated face and the inherent number of the side based on the objective vertex v, the point Fi on the diagonal line of the face in which the vertex v exists, and the inherent number of the side, in order to generate the new connection data (step S 31 ).  
         [0090]    Subsequently, the new vertex data generator  5  calculates a gravity point of the face by an expression ( 1 ) (step S 32 ). Hereinafter, the gravity point is called as a face point.  
                 f   →     i     =         v   →     +       F   →     i     +       e   →     i     +       e   →       i   +   1         4             (   1   )                               
 
         [0091]    The new vertex data generator  5  repeats the processings of step S 32  until when all the face points in the surrounding of the vertex v are calculated (step S 33 ).  
         [0092]    After the calculation of the face points is finished, the new vertex data generator  5  calculates a side point by an expression ( 2 ) based on the objective vertex v, gravity points fi- 1  and fi the faces at both sides of the side, and the end point ei of the side (step S 34 ).  
               e          p   →     i       =           f   →       i   -   1       +       f   →     i     +     v   →     +       e   →     i       4             (   2   )                               
 
         [0093]    Here, the side point expresses a vertex for dividing the side. For example, the side point ep 1  of FIG. 23 corresponds to the gravity point of the face enclosed by both ends points v of the side to be divided, the end point e 2 , the gravity point of the face f 1  and the gravity point of the face f 2 . The generated face point forms a new face with the original vertex and the gravity point of the peripheral face.  
         [0094]    The new vertex data generator  5  repeatedly performs the processing of step S 34  until when all the side points corresponding to the vertex v are calculated (step S 35 ).  
         [0095]    Subsequently, the new vertex data generator  5  moves the coordinate of the original vertex by an expression ( 3 ) (step S 36 ).  
                 v   →     ′     =               ∑     i   =   1     n            f   →     i       +       ∑     i   =   1     m          (         e   →     i     +     v   →       )         m     +       (     m   -   3     )          v   →         m             (   3   )                               
 
         [0096]    The new vertex data generator  5  performs the processings of the above-mentioned steps S 31 -S 36  with regard to all of the original vertices, and calculates the above-mentioned face points and side points by each vertex (step S 37 ).  
         [0097]    Subsequently, the data combining part  8  combines the new connection data corresponding to the face points and the side points generated by step S 31 -S 37  (step S 38 ). That is, the data combining part  8  performs the processings for combining the connection data corresponding to the same face points and side points.  
         [0098]    The new connection data after the combination is stored in the first connection data storing part  2 , and the new vertex data is stored in the first vertex data storing part  3  (step S 39 ).  
         [0099]    The above-mentioned processings are repeatedly performed by each of the newly generated face points and side points (step S 40 ). Therefore, it is possible to divide the initial polygon into sufficiently small pieces.  
         [0100]    [0100]FIG. 24 is a diagram showing a table configuration of the second vertex data storing part  7  for storing the face points and the side points generated by the new vertex data storing part  5 . As shown in FIG. 24, the second vertex data storing part  7  stores coordinate data 0−vn−1 after changing the coordinate of the vertex of the initial polygon by the calculation of the expression ( 3 ), coordinate data vn−vn+en−1 of the side points, and coordinate data vn+en−vn+enfn−1 in sequence. The coordinate data 0−(vn−1) is corresponded to the vertices 0−vn−1 of the original polygons, the coordinate data vn−vn+en−1 is corresponded to the sides 0−(en−1) of the original polygon, and the coordinate data vn+en−vn+en+fn−1 is corresponded to the faces 0−(fn−1) of the original polygon.  
         [0101]    When the subdivision surface processing showing in FIG. 22 are performed, the vertices, the sides and the faces are generated newly. In order to specify these newly generated vertices, sides and faces, the present embodiment allocates inherent numbers to the respective vertices, sides and faces.  
         [0102]    With regard to the vertices, a serial number is allocated to each vertex, as shown in FIG. 24.  
         [0103]    With regard to the sides, the original side number and numbers obtained by adding the total numbers of the original sides to the respective original side numbers are allocated to the sides shown in FIG. 25B generated by dividing the original side shown in FIG. 25A into two. For example, if it is assumed that the original side number is e 0 , and the total number of the original sides is en, the side numbers generated by dividing this side into two are e 0  and (e 0 +en).  
         [0104]    When the face is quadrangle as shown in FIG. 26A, 4-fold, 4-fold+1, 4-fold+2 and 4-fold+3 numbers of the original face numbers are allocated counterclockwise to the faces generated in the surrounding of the face points showing the vertices generated in the face, as shown in FIG. 26B. When the face is triangle as shown in FIG. 26C, 3-fold, 3-fold+1 and 3-fold+2 numbers of the original face numbers are allocated counterclockwise as shown in FIG. 26D. These numbers are also used for numbers of the respective sides.  
         [0105]    As mentioned above, according to the present embodiment, the processing for generating independent connection data by each vertex based on the inputted small number of vertex data is performed, and then the subdivision surface processing are repeatedly performed to generate new vertex data and connection data. Because of this, it is possible to draw the polygon having smooth curved surface with the inputted small number of vertex data, thereby drawing at higher speed than the conventional apparatus.  
         [0106]    [0106]FIG. 27 is a diagram showing an embodiment of a drawing system having the polygon data generating system according to the present embodiment. The drawing system of FIG. 27 has a CPU  11  and a GPU  12 . The GPU  12  has a polygon data generating apparatus  13  for performing the same processing operation as that of FIG. 1 and a drawing controller  14 .  
         [0107]    The polygon data generating apparatus  13  has the initial connection data generator  1 , a subdivision surface processor  16 , a vertex data memory  17  and a connection data memory  18 .  
         [0108]    The subdivision surface processor  16  performs the same processing operation as that of the new connection data generator  4  and the new vertex data generator  5  of FIG. 1. The vertex data memory  17  corresponds to the first vertex data storing part  3  and the second vertex data storing part  7  of FIG. 1. The connection data memory  18  corresponds to the first connection data storing part  2  and the second connection data storing part  6  of FIG. 1.  
         [0109]    The initial connection data generator  1 , the subdivision surface processor  16 , the vertex data memory  17 , the connection data memory  18  and the drawing controller  14  are connected to internal bus  19 . The CPU  11  and the GPU  12  are connected to a common bus  20 .  
         [0110]    The polygon data generating apparatus  13  of FIG. 27 generates new vertex data and new connection data based on the vertex data of the initial polygon sent from the CPU  11 . The drawing system  14  performs the drawing processing based on the vertex data and the connection data generated by the polygon data generating apparatus  13 .  
         [0111]    [0111]FIG. 28 is a layout diagram of an LSI for integrating the GPU  12  of FIG. 27 as one chip. The LSI of FIG. 28 has a content-addressable memory (CAM)  21 , an information converter  22 , a polygon data storing part  23  and a subdivision surface processor  16 . The lower n bits of the already inputted vertex coordinates are stored in the CAM  21 . The CAM  21  compares these n bits data with the lower n bits of the vertex coordinate inputted outside, and determines whether or not the same vertex data exists.  
         [0112]    The information converter  22  generates the connection data based on the inputted vertex data, and stores the generated connection data and the inputted vertex data into the polygon data storing part  23 , similarly to the initial connection data generator  1  of FIG. 1. The polygon data storing part  23  combines the functions of the vertex data memory  17  and the connection data memory  18  of FIG. 27.  
         [0113]    The subdivision surface processor  16  performs the subdivision surface processing to generate the new vertex data and new connection data, similarly to the new connection data generator  4  and the new vertex data generator  5  of FIG. 1, and stores the generated data into the polygon data storing part  23 .  
         [0114]    The LSI of FIG. 28 searches for the entries of the CAM  21  when the vertex data is inputted from outside. If the same vertex data already exists, the vertex number and the connection data are read out from the polygon data storing part  23 . If the same vertex data does not exist, new number is attached to the vertex, and added to the entry of the CAM  21 .  
         [0115]    Furthermore, the LSI of FIG. 28 stores the vertex data and the connection data of the vertex into the polygon data storing part  23 , based on the vertex data inputted from outside. At this time, a new number is always allocated to the face, the previously allocated number is used for the already inputted vertex, and new number is allocated to the newly inputted vertex.  
         [0116]    Such a processing is repeatedly performed. If determined that the surrounding of the objective vertex is enclosed by series of polygons, the connection data corresponding to the vertex is deleted from the entry of the CAM  21 .  
         [0117]    For example, an example in which the vertices of the polygon series shown in FIG. 29A is inputted to the LSI of FIG. 28, and then the vertex data of the polygon series shown in FIG. 29B is inputted will be described hereinafter. The vertices v 2 , v 4 , v 6  and v 8  of FIG. 29A are the same as the vertices v 10 , v 12 , v 14  and v 16  of FIG. 29B.  
         [0118]    First of all, the information converter  22  of FIG. 28 allocates the inherent numbers to the sides and the faces generated from the polygon series of FIG. 29A, respectively, and the vertex data and the connection data are generated with regard to the vertices v 1 -v 8 . Because these vertices are the vertices inputted firstly, the coordinates of all the vertices are registered in the CAM  21 .  
         [0119]    Next, when the vertex data of series of polygons shown in FIG. 29B is inputted, because all the vertex data corresponding to the vertices v 1 , v 12 , v 14  and v 16  has already been inputted, the corresponding connection data is read out from the polygon data storing part  23  in order to add the connection information. Because the other vertices are initial vertices, the coordinates of the vertices are registered to the CAM  21 .  
         [0120]    On the other hand, for example, an example in which the vertex data of a polygon fan shown in FIG. 30A is inputted to the LSI of FIG. 28, and then the vertex data of a polygon fan shown in FIG. 30B is inputted will be described hereinafter. The vertices v 3  and v 4  of FIG. 30A are the same as the vertices v 14  and v 13  of FIG. 30B.  
         [0121]    The information converter  22  of FIG. 28 allocates the inherent numbers to the sides and the faces generated from the polygon fan of FIG. 30A, respectively, in order to generate the vertex data and the connection data relating to the vertices v 1 -v 7 . Because these vertices are inputted firstly, the coordinates of all the vertices are registered to the CAM  21 .  
         [0122]    Subsequently, when the vertex data of the series of polygon of FIG. 30B is inputted, the connection data corresponding to the vertices v 13  and v 14  is read out from the polygon data storing part  23  in order to add the connection information. Because the other vertices are inputted firstly, the coordinates of the vertices are registered to the CAM  21 .  
         [0123]    In FIG. 1, an example in which the connection data is stored by separating into the first connection data storing part  2  and the second connection data storing part  6  has been described. However, these storing parts  2  and  6  are combined into one piece. Similarly, The first vertex data storing part  3  and the second vertex data storing part  7  may be combined into one piece.  
         [0124]    The polygon data generating apparatus described in the above-mentioned embodiment, may be realized by hardware or software. If realized by the software, a program for realizing a function of the polygon data generating apparatus is stored in a recording medium such as a floppy disk or a CD-ROM and read out by a computer to execute the program. The recording medium is not limited to a portable medium such as a magnetic disk or an optical disk, and may be a fixed medium such as a hard disk drive or a semiconductor memory.  
         [0125]    Furthermore, a program for realizing the function of the polygon data generating apparatus may be distributed through a communication line such as an internet or a radio communication line. Moreover, the program may be distributed through the wired or wireless line such as the internet, or by storing in the recording medium, while encoding, modulating or compressing the program.