Apparatus and method for generating progressive polygon data, and apparatus and method for generating three-dimensional real-time graphics using the same

• US 6,307,554 B1
• Filed: 05/04/1998
• Issued: 10/23/2001
• Est. Priority Date: 12/19/1997
• Status: Active Grant

• Current Assignee: Hanger Solutions, LLC (IP Investments Group LLC)
• Original Assignee: Fujitsu Limited
• Inventors: Arai, Masatoshi, Murakami, Koichi, Miyata, Ryosuke
• Primary Examiner(s): Zimmerman, Mark
• Assistant Examiner(s): Padmanabhan, Mano
• Application Number:
  US09/071,830
• Time in Patent Office: 1,268 Days
• Field of Search: 345/423, 345/428, 345/441, 345/442
• US Class Current: 345/423
• CPC Class Codes: G06T 17/20 Finite element generation, e.g. wire-frame surface description, tesselation

Abstract

The present invention provides a 3D real-time graphics generator for generating progressive polygon data for rendering 3D graphics that can reduce the amount of data processing by a computer and a storage area for polygon data, facilitates editing of an object by using the progressive polygon data so as to reduce the amount of work of an animator. The progressive polygon data includes information about vertices of a basic polyhedron approximate to a shape of a 3D object and information about detailed vertices of a polyhedron in a level of approximation to the object that is higher than the basic polyhedron, which are determined progressively based on the level of approximation. In the generation of 3D real-time graphics, detailed vertices are sequentially merged into the vertices of the basic polyhedron so as to produce 3D polygon data.

Claims

1. A progressive polygon data generator, comprising:

a basic vertex determinator for determining vertices of a basic polyhedron approximate to a shape of a 3D object;

a detailed vertex determinator for determining vertices of a detailed polyhedron in a level of approximation to the 3D object that is higher than the approximation of the basic polyhedron progressively based on the level of approximation;

a detailed vertex coordinate calculator for progressively calculating relative position coordinates of the vertices of the detailed polyhedron determined by said detailed vertex determinator in a relative coordinate system based on a plurality of predetermined vertices in a level of approximation that is lower than the detailed polyhedron;

a basic polygon data generator for generating basic polygon data representing the basic polyhedron based on the vertices of the basic polyhedron determined by said basic vertex determinator;

a detailed polygon data generator for generating detailed polygon data for representing each progressive detailed polyhedron in a corresponding level of approximation to the 3D object based on the vertices of each detailed polyhedron determined by said detailed vertex determinator, which information is described in relative position coordinates in the relative coordinate system; and

a polygon progressing part for combining the basic polygon data and the detailed polygon data and progressively generating polygon data for rendering respective models in each progressive level in corresponding levels of approximation to the 3D object.

2. The progressive polygon data generator according to claim 1, wherein said basic vertex determinator determines vertices of the basic polyhedron by selection of an operator.

3. The progressive polygon data generator according to claim 1, wherein said detailed vertex determinator comprises:

an approximation level calculator for calculating a difference between an area of each face of the basic polyhedron and an area on a surface of the 3D object defined by line segments connecting vertices of each face of the basic polyhedron;

a comparator for comparing the difference calculated by the approximation level calculator with a predetermined value; and

a progressive vertex determinator for determining a new vertex closer to the surface of the 3D object than a corresponding face when the comparator determines that the difference is the predetermined value or more, and not determining a new vertex when the difference is determined to be smaller than the predetermined value,

wherein when a new vertex is determined by said progressive vertex determinator, the approximation level calculator calculates a difference in area with respect to a polyhedron defined by the corresponding face and the new vertex, and the progressive vertex determinator determines a vertex of a polygon in a higher level of approximation recursively, until the progressive vertex determinator no longer determines a new vertex.

4. The progressive polygon data generator according to claim 3, wherein the progressive vertex determinator determines, as the new vertex, a point at which a normal line from a centroid of the corresponding face of the detailed polyhedron intersects a face represented by original polygon data obtained by geometric modeling of the 3D object.

5. A 3D real-time graphics generator, comprising:

a rendering polygon number determinator for determining a number of polygons for rendering 3D polygon data;

a 3D polygon data producer for producing 3D polygon data based on progressive polygon data in accordance with the number of polygons determined by the rendering polygon number determinator;

a progressive polygon data generator generating the progressive polygon data, comprising;

a basic vertex determinator determining vertices of a basic polyhedron approximate to a shape of a 3D object;

a detailed vertex determinator determining vertices of a detailed polyhedron in a level of approximation to the 3D object that is higher than the approximation of the basic polyhedron progressively based on the level of approximation;

a detailed vertex coordinate calculator progressively calculating relative position coordinates of the vertices of the detailed polyhedron determined by said detailed vertex determinator in a relative coordinate system based on a plurality of predetermined vertices in a level of approximation that is lower than the detailed polyhedron;

a basic polygon data generator generating basic polygon data representing the basic polyhedron based on the vertices of the basic polyhedron determined by said basic vertex determinator;

a detailed polygon data generator generating detailed polygon data for representing each progressive detailed polyhedron in a corresponding level of approximation to the 3D object based on the vertices of each detailed polyhedron determined by said detailed vertex determinator, which information is described in relative position coordinates in the relative coordinate system;

a polygon progressing part combining the basic polygon data and the detailed polygon data and progressively generating polygon data for rendering respective models in each progressive level in corresponding levels of approximation to the 3D object;

an outputting unit outputting the generated progressive polygon data,

wherein said basic vertex determinator determines vertices of the basic polyhedron by selection of an operator,

wherein said detailed vertex determinator comprises;

an approximation level calculator calculating a difference between an area of each face of the basic polyhedron and an area on a surface of the 3D object defined by line segments connecting vertices of each face of the basic polyhedron;

a comparator comparing the difference calculated by the approximation level calculator with a predetermined value; and

a progressive vertex determinator determining a new vertex closer to the surface of the 3D object than a corresponding face when the comparator determines that the difference is the predetermined value or more, and not determining a new vertex when the difference is determined to be smaller than the predetermined value,

wherein when a new vertex is determined by said progressive vertex determinator, the approximation level calculator calculates a difference in area with respect to a polyhedron defined by the corresponding face and the new vertex, and the progressive vertex determinator determines a vertex of a polygon in a higher level of approximation recursively, until the progressive vertex determinator no longer determines a new vertex.

6. The 3D real-time graphics generator according to claim 5, wherein the 3D polygon data producer produces 3D polygon data by determining vertices constituting 3D polygon data for rendering an object in accordance with the number of polygons determined by the rendering polygon number determinator.

7. The 3D real-time graphics generator according to claim 6, further comprising a basic vertex changer for changing positions of vertices of the basic polyhedron, wherein

when positions of vertices of the basic polyhedron are changed by the basic vertex changer, the 3D polygon data producer calculates absolute coordinates of detailed vertices whose positions are represented by coordinates in a coordinate system determined based on the vertices, based on changed positions of the vertices.

8. The 3D real-time graphics generator according to claim 5, further comprising:

an animation data storage for storing a plurality of progressive polygon data added with information about rendering timing; and

an animation rendering controller for rendering 3D polygon data produced by the 3D polygon data producer from the progressive polygon data stored in the animation data storage in accordance with the information about rendering timing.

9. The 3D real-time graphics generator according to claim 8,

wherein the rendering polygon number determinator comprises a moving speed calculator for calculating a moving speed of an object when 3D polygon data is rendered sequentially, based on the plurality of progressive polygon data and the information about rendering timing stored in the animation data storage, and

the rendering polygon number determinator determines the number of polygons based on the moving speed calculated by the moving speed calculator.

10. The 3D real-time graphics generator according to claim 8,

wherein the rendering polygon number determinator comprises a Z value obtainer for obtaining a Z value representing a distance from a viewpoint to a position of a rendered object from the progressive polygon data;

and the rendering polygon number determinator determines the number of polygons based on the distance obtained by the Z value obtainer.

11. The 3D real-time graphics generator according to claim 8, wherein the rendering polygon number determinator determines the number of polygons based on information about system resources on which the object is rendered.

12. A method for generating 3D real-time graphics, comprising:

a rendering polygon number determining operation determining the number of polygons for rendering 3D polygon data; and

a 3D polygon data producing operation producing 3D polygon data based on progressive polygon data, based on the number of polygons determined by the rendering polygon number determining operation;

using a progressive polygon data generator to generate the progressive polygon data by performing;

a basic vertex operation determining vertices of a basic polyhedron approximate to a shape of a 3D object;

a detailed vertex operation determining vertices of a detailed polyhedron in a level of approximation to the 3D object that is higher than the approximation of the basic polyhedron progressively based on the level of approximation;

a detailed vertex coordinate operation progressively calculating relative position coordinates of the vertices of the detailed polyhedron determined by said detailed vertex operation in a relative coordinate system based on a plurality of predetermined vertices in a level of approximation that is lower than the detailed polyhedron;

a basic polygon data operation generating basic polygon data representing the basic polyhedron based on the vertices of the basic polyhedron determined by said basic vertex operation;

a detailed polygon data operation generating detailed polygon data for representing each progressive detailed polyhedron in a corresponding level of approximation to the 3D object based on the vertices of each detailed polyhedron determined by said detailed vertex operation, which information is described in relative position coordinates in the relative coordinate system;

a polygon progressing operation combining the basic polygon data and the detailed polygon data and progressively generating polygon data for rendering respective models in each progressive level in corresponding levels of approximation to the 3D object;

an outputting operation outputting the progressively generated polygon data,

wherein said basic vertex operation determines vertices of the basic polyhedron by selection of an operator,

wherein said detailed vertex operation comprises;

an approximation level operation calculating a difference between an area of each face of the basic polyhedron and an area on a surface of the 3D object defined by line segments connecting vertices of each face of the basic polyhedron;

a comparator operation comparing the difference calculated by the approximation level operation with a predetermined value; and

a progressive vertex operation determining a new vertex closer to the surface of the 3D object than a corresponding face when the comparator operation determines that the difference is the predetermined value or more, and not determining a new vertex when the difference is determined to be smaller than the predetermined value,

wherein when a new vertex is determined by said progressive vertex operation, the approximation level operation calculates a difference in area with respect to a polyhedron defined by the corresponding face and the new vertex, and the progressive vertex operation determines a vertex of a polygon in a higher level of approximation recursively, until the progressive vertex operation no longer determines a new vertex.

13. A computer-readable recording medium storing a program executing a process comprising:

a rendering polygon number determining operation determining the number of polygons for rendering 3D polygon data;

a 3D polygon data producing operation producing 3D polygon data based on the progressive polygon data, based on the number of polygons determined in the rendering polygon number determining operation,

wherein in the 3D polygon data producing operation, the 3D polygon data is produced by determining vertices constituting the 3D polygon data for rendering an object, based on the number of polygons determined in the rendering polygon number determining operation,

using a progressive polygon data generator to generate the progressive polygon data, by performing;

a basic vertex operation determining vertices of a basic polyhedron approximate to a shape of a 3D object;

a detailed vertex operation determining vertices of a detailed polyhedron in a level of approximation to the 3D object that is higher than the approximation of the basic polyhedron progressively based on the level of approximation;

a detailed vertex coordinate operation progressively calculating relative position coordinates of the vertices of the detailed polyhedron determined by said detailed vertex operation in a relative coordinate system based on a plurality of predetermined vertices in a level of approximation that is lower than the detailed polyhedron;

a basic polygon data operation generating basic polygon data representing the basic polyhedron based on the vertices of the basic polyhedron determined by said basic vertex operation;

a detailed polygon data operation generating detailed polygon data for representing each progressive detailed polyhedron in a corresponding level of approximation to the 3D object based on the vertices of each detailed polyhedron determined by said detailed vertex operation, which information is described in relative position coordinates in the relative coordinate system;

a polygon progressing operation combining the basic polygon data and the detailed polygon data and progressively generating polygon data for rendering respective models in each progressive level in corresponding levels of approximation to the 3D object,

wherein, said basic vertex determinator determines vertices of the basic polyhedron by selection of an operator,

wherein said detailed vertex operation comprises;

an approximation level operation calculating a difference between an area of each face of the basic polyhedron and an area on a surface of the 3D object defined by line segments connecting vertices of each face of the basic polyhedron;

a comparator operation comparing the difference calculated by the approximation level operation with a predetermined value;

a progressive vertex operation determining a new vertex closer to the surface of the 3D object than a corresponding face when the comparator operation determines that the difference is the predetermined value or more, and not determining a new vertex when the difference is determined to be smaller than the predetermined value; and

an outputting operation outputting the generated progressive polygon data,

wherein when a new vertex is determined by said progressive vertex operation, the approximation level operation calculates a difference in area with respect to a polyhedron defined by the corresponding face and the new vertex, and the progressive vertex operation determines a vertex of a polygon in a higher level of approximation recursively, until the progressive vertex operation no longer determines a new vertex.

14. A 3D real-time graphics generator comprising:

a rendering polygon number determinator for determining the number of polygons for rendering 3D polygon data; and

a 3D polygon data producer for producing 3D polygon data based on progressive polygon data generated by the progressive polygon data generator in accordance with the number of polygons determined by the rendering polygon number determinator,

wherein the progressive polygon data is generated by a progressive polygon generator comprising;

a basic vertex determinator determining vertices of a basic polyhedron approximate to a shape of a 3D object;

a detailed vertex determinator determining vertices of a detailed polyhedron in a level of approximation to the 3D object that is higher than the approximation of the basic polyhedron progressively based on the level of approximation;

a detailed vertex coordinate calculator progressively calculating relative position coordinates of the vertices of the detailed polyhedron determined by said detailed vertex determinator in a relative coordinate system based on a plurality of predetermined vertices in a level of approximation that is lower than the detailed polyhedron;

a basic polygon data generator generating basic polygon data representing the basic polyhedron based on the vertices of the basic polyhedron determined by said basic vertex determinator;

a detailed polygon data generator generating detailed polygon data for representing each progressive detailed polyhedron in a corresponding level of approximation to the 3D object based on the vertices of each detailed polyhedron determined by said detailed vertex determinator, which information is described in relative position coordinates in the relative coordinate system;

a polygon progressing part combining the basic polygon data and the detailed polygon data and progressively generating polygon data for rendering respective models in each progressive level in corresponding levels of approximation to the 3D object; and

an outputting unit outputting the generated progressive polygon data.

15. The 3D real-time graphics generator according to claim 14, wherein the 3D polygon data producer produces 3D polygon data by determining vertices constituting 3D polygon data for rendering an object in accordance with the number of polygons determined by the rendering polygon number determinator.

16. The 3D real-time graphics generator according to claim 15, further comprising a basic vertex changer for changing positions of vertices of the basic polyhedron, wherein

when positions of vertices of the basic polyhedron are changed by the basic vertex changer, the 3D polygon data producer calculates absolute coordinates of detailed vertices whose positions are represented by coordinates in a coordinate system determined based on the vertices, based on changed positions of the vertices.

17. The 3D real-time graphics generator according to claim 14, further comprising:

an animation data storage for storing a plurality of progressive polygon data added with information about rendering timing; and

an animation rendering controller for rendering 3D polygon data produced by the 3D polygon data producer from the progressive polygon data stored in the animation data storage in accordance with the information about rendering timing.

18. The 3D real-time graphics generator according to claim 17,

wherein the rendering polygon number determinator comprises a moving speed calculator for calculating a moving speed of an object when 3D polygon data is rendered sequentially, based on the plurality of progressive polygon data and the information about rendering timing stored in the animation data storage;

and

the rendering polygon number determinator determines the number of polygons based on the moving speed calculated by the moving speed calculator.

19. The 3D real-time graphics generator according to claim 17,

wherein the rendering polygon number determinator comprises a Z value obtainer for obtaining a Z value representing a distance from a viewpoint to a position of a rendered object from the progressive polygon data;

and

the rendering polygon number determinator determines the number of polygons based on the distance obtained by the Z value obtainer.

20. The 3D real-time graphics generator according to claim 17, wherein the rendering polygon number determinator determines the number of polygons based on information about system resources on which the object is rendered.

21. A method for generating 3D real-time graphics comprising;

a rendering polygon number determining operation determining the number of polygons for rendering 3D polygon data; and

a 3D polygon data producing operation producing 3D polygon data based on progressive polygon data, based on the number of polygons determined by the rendering polygon number determining operation;

using a progressive polygon data generator to generate the progressive polygon data by performing;

a basic vertex operation determining vertices of a basic polyhedron approximate to a shape of a 3D object;

a detailed vertex operation determining vertices of a detailed polyhedron in a level of approximation to the 3D object that is higher than the approximation of the basic polyhedron progressively based on the level of approximation;

a detailed vertex coordinate operation progressively calculating relative position coordinates of the vertices of the detailed polyhedron determined by said detailed vertex operation in a relative coordinate system based on a plurality of predetermined vertices in a level of approximation that is lower than the detailed polyhedron;

a basic polygon data operation generating basic polygon data representing the basic polyhedron based on the vertices of the basic polyhedron determined by said basic vertex operation;

a detailed polygon data operation generating detailed polygon data for representing each progressive detailed polyhedron in a corresponding level of approximation to the 3D object based on the vertices of each detailed polyhedron determined by said detailed vertex operation, which information is described in relative position coordinates in the relative coordinate system;

a polygon progressing operation combining the basic polygon data and the detailed polygon data and progressively generating polygon data for rendering respective models in each progressive level in corresponding levels of approximation to the 3D object; and

an outputting operation outputting the generated progressive polygon data.

22. A computer-readable recording medium storing a program executing a process comprising:

a rendering polygon number determining operation determining the number of polygons for rendering 3D polygon data; and

a 3D polygon data producing operation producing 3D polygon data based on progressive polygon data, based on the number of polygons determined in the rendering polygon number determining operation,

wherein in the 3D polygon data producing operation, the 3D polygon data is produced by determining vertices constituting the 3D polygon data for rendering an object, based on the number of polygons determined in the rendering polygon number determining operation;

using a progressive polygon data generator to generate the progressive polygon data by performing;

a basic vertex operation determining vertices of a basic polyhedron approximate to a shape of a 3D object;

a detailed vertex operation determining vertices of a detailed polyhedron in a level of approximation to the 3D object that is higher than the approximation of the basic polyhedron progressively based on the level of approximation;

a detailed vertex coordinate operation progressively calculating relative position coordinates of the vertices of the detailed polyhedron determined by said detailed vertex operation in a relative coordinate system based on a plurality of predetermined vertices in a level of approximation that is lower than the detailed polyhedron;

a basic polygon data operation generating basic polygon data representing the basic polyhedron based on the vertices of the basic polyhedron determined by said basic vertex operation;

a detailed polygon data operation generating detailed polygon data for representing each progressive detailed polyhedron in a corresponding level of approximation to the 3D object based on the vertices of each detailed polyhedron determined by said detailed vertex operation, which information is described in relative position coordinates in the relative coordinate system;

a polygon progressing operation combining the basic polygon data and the detailed polygon data and progressively generating polygon data for rendering respective models in each progressive level in corresponding levels of approximation to the 3D object; and

an outputting operation outputting the generated progressive polygon data.

23. A progressive polygon data generator, comprising:

a basic vertex determinator for determining vertices of polygons approximate to an outer edge shape of cross-sections virtually segmenting a 3D object such that the determined vertices are vertices of a basic polyhedron approximate to a shape of the 3D object;

a detailed vertex determinator for progressively determining vertices of a detailed polyhedron in a level of approximation to the 3D object that is higher than the basic polyhedron based on the level of approximation;

a detailed vertex coordinate calculator for progressively calculating relative position coordinates of the detailed polyhedron vertices determined by said detailed vertex determinator in a relative coordinate system based on a plurality of predetermined vertices of a polyhedron in a level of approximation that is lower than the detailed polyhedron;

a basic polygon data generator for generating basic polygon data for representing the basic polyhedron based on information on the vertices of the basic polyhedron determined by the basic vertex determinator;

a detailed polygon data generator for generating detailed polygon data for representing each progressive detailed polyhedron in a corresponding level of approximation to the 3D object based on the information on vertices of the detailed polyhedron determined by the detailed vertex determinator, which information is described in relative position coordinates in a relative coordinate system; and

a polygon progressing part for combining the basic polygon data and the detailed polygon data and generating progressive polygon data for rendering respective models in each progressive level in a corresponding level of approximation to the 3D object.

24. The progressive polygon data generator according to claim 23, wherein

the 3D object is a 3D object represented by the original polygon data obtained by geometric modeling of the 3D object,

the polygon approximate to an outer edge shape of each cross-section determined by the basic vertex determinator is a quadrilateral which is defined by that points at which line segments represented by intersect a face virtually bisecting the 3D object are selected as control points so as to form a second polygonal shape by connecting the control points and the polygon approximate to each cross-section is a quadrilateral defined by four vertices that divide a total length of sides of the second polygonal shape into four equal lengths.

25. The progressive polygon data generator according to claim 24, wherein the detailed vertex determinator comprises:

an approximation level calculator for calculating a difference between a length of each side of the quadrilateral and a total length of sides of the second polygonal shape between both ends of each side of the quadrilateral;

a comparator for comparing the difference calculated by the approximation level calculator with a predetermined value;

a progressive vertex determinator for determining a point that divides into two equal lengths the total length of the sides of the second polygonal shape between both ends of the side of the quadrilateral as a vertex of a polygon in a higher level of approximation when the comparator determines that the difference is the predetermined value or more, and not determining a vertex of a polygon in a higher level of approximation when the difference is determined to be smaller than the predetermined value, and

when a vertex of a polygon in a higher level of approximation is determined by the progressive vertex determinator, the approximation level calculator calculates the difference with respect to a newly produced side of the polygon whose vertex is determined, and the progressive vertex determinator determines a vertex of a polygon in a higher level of approximation recursively, until the progressive vertex determinator no longer determines a vertex of a polygon in a higher level of approximation.

26. The progressive polygon data generator according to claim 23, wherein the detailed vertex determinator progressively determines vertices of a polygon the number of which is increased so that the level of approximation to the outer edge shape of each cross-section is higher than the polygon approximate to the outer edge shape of each cross-section as detailed vertices, based on the increased number of vertices.

27. A 3D real-time graphics generator comprising:

a rendering polygon number determinator determining the number of polygons for rendering 3D polygon data;

a 3D polygon data producer for producing 3D polygon data based on progressive polygon data in accordance with the number of polygons determined by the rendering polygon number determinator,

wherein the progressive polygon data is generated by a progressive polygon data generator, comprising;

a basic vertex determinator determining vertices of a basic polyhedron approximate to a shape of a 3D object;

a detailed vertex determinator determining vertices of a detailed polyhedron in a level of approximation to the 3D object that is higher than the approximation of the basic polyhedron progressively based on the level of approximation;

a detailed vertex coordinate calculator progressively calculating relative position coordinates of the vertices of the detailed polyhedron determined by said detailed vertex determinator in a relative coordinate system based on a plurality of predetermined vertices in a level of approximation that is lower than the detailed polyhedron;

a basic polygon data generator generating basic polygon data representing the basic polyhedron based on the vertices of the basic polyhedron determined by said basic vertex determinator;

a detailed polygon data generator generating detailed polygon data for representing each progressive detailed polyhedron in a corresponding level of approximation to the 3D object based on the vertices of each detailed polyhedron determined by said detailed vertex determinator, which information is described in relative position coordinates in the relative coordinate system;

a polygon progressing part combining the basic polygon data and the detailed polygon data and progressively generating polygon data for rendering respective models in each progressive level in corresponding levels of approximation to the 3D object;

an outputting unit outputting the generated progressive polygon data,

wherein the 3D object is a 3D object represented by the original polygon data obtained by geometric modeling of the 3D object,

the polygon approximate to an outer edge shape of each cross-section determined by the basic vertex determinator is a quadrilateral which is defined by control points at which line segments intersect a face virtually bisecting the 3D object so as to form a second polygonal shape by connecting the control points and the polygon approximate to each cross-section which is a quadrilateral defined by four vertices that divide a total length of sides of the second polygonal shape into four equal lengths,

wherein the detailed vertex determinator comprises;

an approximation level calculator calculating a difference between a length of each side of the quadrilateral and a total length of sides of the second polygonal shape between both ends of each side of the quadrilateral;

a comparator comparing the difference calculated by the approximation level calculator with a predetermined value; and

a progressive vertex determinator determining a point that divides into two equal lengths the total length of the sides of the second polygonal shape between both ends of the side of the quadrilateral as a vertex of a polygon in a higher level of approximation when the comparator determines that the difference is the predetermined value or more, and not determining a vertex of a polygon in a higher level of approximation when the difference is determined to be smaller than the predetermined value,

when a vertex of a polygon in a higher level of approximation is determined by the progressive vertex determinator, the approximation level calculator calculates the difference with respect to a newly produced side of the polygon whose vertex is determined, and the progressive vertex determinator determines a vertex of a polygon in a higher level of approximation recursively, until the progressive vertex determinator no longer determines a vertex of a polygon in a higher level of approximation.

28. The 3D real-time graphics generator according to claim 27, wherein the 3D polygon data producer produces 3D polygon data by determining vertices constituting 3D polygon data for rendering an object in accordance with the number of polygons determined by the rendering polygon number determinator.

29. The 3D real-time graphics generator according to claim 28, further comprising a basic vertex changer for changing positions of vertices of the 30 basic polyhedron, wherein

when positions of vertices of the basic polyhedron are changed by the basic vertex changer, the 3D polygon data producer calculates absolute coordinates of detailed vertices whose positions are represented by coordinates in a coordinate system determined based on the vertices, based on changed positions of the vertices.

30. The 3D real-time graphics generator according to claim 27, further comprising:

an animation data storage for storing a plurality of progressive polygon data added with information about rendering timing; and

an animation rendering controller for rendering 3D polygon data produced by the 3D polygon data producer from the progressive polygon data stored in the animation data storage in accordance with the information about rendering timing.

31. The 3D real-time graphics generator according to claim 30,

wherein the rendering polygon number determinator comprises a moving speed calculator for calculating a moving speed of an object when 3D polygon data is rendered sequentially, based on the plurality of progressive polygon data and the information about rendering timing stored in the animation data storage;

and

the rendering polygon number determinator determines the number of polygons based on the moving speed calculated by the moving speed calculator.

32. The 3D real-time graphics generator according to claim 30,

wherein the rendering polygon number determinator comprises a Z value obtainer for obtaining a Z value representing a distance from a viewpoint to a position of a rendered object from the progressive polygon data;

and

the rendering polygon number determinator determines the number of polygons based on the distance obtained by the Z value obtainer.

33. The 3D real-time graphics generator according to claim 30, wherein the rendering polygon number determinator determines the number of polygons based on information about the system resources on which the object is rendered.

34. A method for generating 3D real-time graphics using progressive polygon data, comprising:

a rendering polygon number determining operation determining a number of polygons for rendering 3D polygon data;

a 3D polygon data producing operation producing 3D polygon data based on progressive polygon data, based on the number of polygons determined by the rendering polygon number determining operation,

using a progressive polygon data generator to generate the progressive polygon data by performing;

a basic vertex operation determining vertices of polygons approximate to an outer edge shape of cross-sections virtually segmenting a 3D object such that the determined vertices are vertices of a basic polyhedron approximate to a shape of the 3D object;

a detailed vertex operation progressively determining vertices of a detailed polyhedron in a level of approximation to the 3D object that is higher than the basic polyhedron based on the level of approximation;

a detailed vertex coordinate operation progressively calculating relative position coordinates of the detailed polyhedron vertices determined by said detailed vertex operation in a relative coordinate system based on a plurality of predetermined vertices of a polyhedron in a level of approximation that is lower than the detailed polyhedron;

a basic polygon data generator operation generating basic polygon data for representing the basic polyhedron based on information on the vertices of the basic polyhedron determined by the basic vertex operation;

a detailed polygon data generator operation generating detailed polygon data for representing each progressive detailed polyhedron in a corresponding level of approximation to the 3D object based on the information on vertices of the detailed polyhedron determined by the detailed vertex operation, which information is described in relative position coordinates in a relative coordinate system;

a polygon progressing operation combining the basic polygon data and the detailed polygon data and generating progressive polygon data for rendering respective models in each progressive level in a corresponding level of approximation to the 3D object;

an outputting operation outputting the generated progressive polygon data,

wherein the 3D object is a 3D object represented by the original polygon data obtained by geometric modeling of the 3D object,

the polygon approximate to an outer edge shape of each cross-section determined by the basic vertex determinator is a quadrilateral which is defined by control points at which line segments intersect a face virtually bisecting the 3D object so as to form a second polygonal shape by connecting the control points and the polygon approximate to each cross-section which is a quadrilateral defined by four vertices that divide a total length of sides of the second polygonal shape into four equal lengths,

wherein the detailed vertex operation comprises;

an approximation level operation calculating a difference between a length of each side of the quadrilateral and a total length of sides of the second polygonal shape between both ends of each side of the quadrilateral;

a comparator operation comparing the difference calculated by the approximation level calculator with a predetermined value; and

a progressive vertex operation determining a point that divides into two equal lengths the total length of the sides of the second polygonal shape between both ends of the side of the quadrilateral as a vertex of a polygon in a higher level of approximation when the comparator operation determines that the difference is the predetermined value or more, and not determining a vertex of a polygon in a higher level of approximation when the difference is determined to be smaller than the predetermined value,

when a vertex of a polygon in a higher level of approximation is determined by the progressive vertex operation, the approximation level calculator calculates the difference with respect to a newly produced side of the polygon whose vertex is determined, and the progressive vertex operation determines a vertex of a polygon in a higher level of approximation recursively, until the progressive vertex operation no longer determines a vertex of a polygon in a higher level of approximation.

35. A computer-readable recording medium storing a program executing a process comprising:

a rendering polygon number determining operation determining a number of polygons for rendering 3D polygon data;

a 3D polygon data producing operation producing 3D polygon data based on the progressive polygon data, based on the number of polygons determined in the rendering polygon number determining operation,

wherein in the 3D polygon data producing operation, the 3D polygon data is produced by determining vertices constituting the 3D polygon data for rendering an object, based on the number of polygons determined in the rendering polygon number determining operation;

using a progressive polygon data generator to generator the progressive polygon data by performing;

a basic vertex operation determining vertices of polygons approximate to an outer edge shape of cross-sections virtually segmenting a 3D object such that the determined vertices are vertices of a basic polyhedron approximate to a shape of the 3D object;

a detailed vertex operation progressively determining vertices of a detailed polyhedron in a level of approximation to the 3D object that is higher than the basic polyhedron based on the level of approximation;

a detailed vertex coordinate operation progressively calculating relative position coordinates of the detailed polyhedron vertices determined by said detailed vertex operation in a relative coordinate system based on a plurality of predetermined vertices of a polyhedron in a level of approximation that is lower than the detailed polyhedron;

a basic polygon data generator operation generating basic polygon data for representing the basic polyhedron based on information on the vertices of the basic polyhedron determined by the basic vertex operation;

a detailed polygon data generator operation generating detailed polygon data for representing each progressive detailed polyhedron in a corresponding level of approximation to the 3D object based on the information on vertices of the detailed polyhedron determined by the detailed vertex operation, which information is described in relative position coordinates in a relative coordinate system;

a polygon progressing operation combining the basic polygon data and the detailed polygon data and generating progressive polygon data for rendering respective models in each progressive level in a corresponding level of approximation to the 3D object;

an outputting operation outputting the generated progressive polygon data,

wherein the 3D object is a 3D object represented by the original polygon data obtained by geometric modeling of the 3D object,

the polygon approximate to an outer edge shape of each cross-section determined by the basic vertex determinator is a quadrilateral which is defined by control points at which line segments intersect a face virtually bisecting the 3D object so as to form a second polygonal shape by connecting the control points and the polygon approximate to each cross-section which is a quadrilateral defined by four vertices that divide a total length of sides of the second polygonal shape into four equal lengths,

wherein the detailed vertex operation comprises;

an approximation level operation calculating a difference between a length of each side of the quadrilateral and a total length of sides of the second polygonal shape between both ends of each side of the quadrilateral;

a comparator operation comparing the difference calculated by the approximation level calculator with a predetermined value; and

a progressive vertex operation determining a point that divides into two equal lengths the total length of the sides of the second polygonal shape between both ends of the side of the quadrilateral as a vertex of a polygon in a higher level of approximation when the comparator operation determines that the difference is the predetermined value or more, and not determining a vertex of a polygon in a higher level of approximation when the difference is determined to be smaller than the predetermined value,

when a vertex of a polygon in a higher level of approximation is determined by the progressive vertex operation, the approximation level calculator calculates the difference with respect to a newly produced side of the polygon whose vertex is determined, and the progressive vertex operation determines a vertex of a polygon in a higher level of approximation recursively, until the progressive vertex operation no longer determines a vertex of a polygon in a higher level of approximation.

36. A 3D real-time graphics generator comprising:

a rendering polygon number determinator determining the number of polygons for rendering 3D polygon data;

a 3D polygon data producer producing 3D polygon data based on the progressive polygon data in accordance with the number of polygons determined by the rendering polygon number determinator,

wherein the progressive polygon data is generated by a progressive polygon data generator comprising;

a basic vertex determinator determining vertices of a basic polyhedron approximate to a shape of a 3D object;

a detailed vertex determinator determining vertices of a detailed polyhedron in a level of approximation to the 3D object that is higher than the approximation of the basic polyhedron progressively based on the level of approximation;

a detailed vertex coordinate calculator progressively calculating relative position coordinates of the vertices of the detailed polyhedron determined by said detailed vertex determinator in a relative coordinate system based on a plurality of predetermined vertices in a level of approximation that is lower than the detailed polyhedron;

a basic polygon data generator generating basic polygon data representing the basic polyhedron based on the vertices of the basic polyhedron determined by said basic vertex determinator;

a detailed polygon data generator generating detailed polygon data for representing each progressive detailed polyhedron in a corresponding level of approximation to the 3D object based on the vertices of each detailed polyhedron determined by said detailed vertex determinator, which information is described in relative position coordinates in the relative coordinate system; and

a polygon progressing part combining the basic polygon data and the detailed polygon data and progressively generating polygon data for rendering respective models in each progressive level in corresponding levels of approximation to the 3D object; and

an outputting unit outputting the generated progressive polygon data.

37. The 3D real-time graphics generator according to claim 36, wherein the 3D polygon data producer produces 3D polygon data by determining vertices constituting 3D polygon data for rendering an object in accordance with the number of polygons determined by the rendering polygon number determinator.

38. The 3D real-time graphics generator according to claim 37, further comprising a basic vertex changer for changing positions of vertices of the basic polyhedron, wherein

when positions of vertices of the basic polyhedron are changed by the basic vertex changer, the 3D polygon data producer calculates absolute coordinates of detailed vertices whose positions are represented by coordinates in a coordinate system determined based on the vertices, based on changed positions of the vertices.

39. The 3D real-time graphics generator according to claim 36, further comprising:

an animation data storage for storing a plurality of progressive polygon data added with information about rendering timing; and

an animation rendering controller for rendering 3D polygon data produced by the 3D polygon data producer from the progressive polygon data stored in the animation data storage in accordance with the information about rendering timing.

40. The 3D real-time graphics generator according to claim 39,

wherein the rendering polygon number determinator comprises a moving speed calculator for calculating a moving speed of an object when 3D polygon data is rendered sequentially, based on the plurality of progressive polygon data and the information about rendering timing stored in the animation data storage;

and

the rendering polygon number determinator determines the number of polygons based on the moving speed calculated by the moving speed calculator.

41. The 3D real-time graphics generator according to claim 39,

wherein the rendering polygon number determinator comprises a Z value obtainer for obtaining a Z value representing a distance from a viewpoint to a position of a rendered object from the progressive polygon data;

and

the rendering polygon number determinator determines the number of polygons based on the distance obtained by the Z value obtainer.

42. The 3D real-time graphics generator according to claim 39, wherein the rendering polygon number determinator determines the number of polygons based on information about system resources on which the object is rendered.

43. A method for generating 3D real-time graphics comprising:

a rendering polygon number determining operation determining a number of polygons for rendering 3D polygon data;

a 3D polygon data producing operation producing 3D polygon data based on progressive polygon data, based on the number of polygons determined a by the rendering polygon number determining operation;

using a progressive polygon data generator to generate the progressive polygon data by performing;

a basic vertex operation determining vertices of polygons approximate to an outer edge shape of cross-sections virtually segmenting a 3D object such that the determined vertices are vertices of a basic polyhedron approximate to a shape of the 3D object;

a detailed vertex operation progressively determining vertices of a detailed polyhedron in a level of approximation to the 3D object that is higher than the basic polyhedron based on the level of approximation;

a detailed vertex coordinate operation for progressively calculating relative position coordinates of the detailed polyhedron vertices determined by said detailed vertex operation in a relative coordinate system based on a plurality of predetermined vertices of a polyhedron in a level of approximation that is lower than the detailed polyhedron;

a basic polygon data operation generating basic polygon data for representing the basic polyhedron based on information on the vertices of the basic polyhedron determined by the basic vertex operation;

a detailed polygon data operation generating detailed polygon data for representing each progressive detailed polyhedron in a corresponding level of approximation to the 3D object based on the information on vertices of the detailed polyhedron determined by the detailed vertex operation, which information is described in relative position coordinates in a relative coordinate system;

a polygon progressing operation combining the basic polygon data and the detailed polygon data and generating progressive polygon data for rendering respective models in each progressive level in a corresponding level of approximation to the 3D object; and

an outputting operation outputting the generated progressive polygon data.

44. A computer-readable recording medium storing a program executing a process comprising:

a rendering polygon number determining operation determining a number of polygons for rendering 3D polygon data;

a 3D polygon data producing operation producing 3D polygon data based on progressive polygon data, based on the number of polygons determined in the rendering polygon number determining operation,

wherein in the 3D polygon data producing operation, the 3D polygon data is produced by determining vertices constituting the 3D polygon data for rendering an object, based on the number of polygons determined in the rendering polygon number determining operation;

using a progressive polygon data generator to generate the progressive polygon data by performing;

a basic vertex operation determining vertices of polygons approximate to an outer edge shape of cross-sections virtually segmenting a 3D object such that the determined vertices are vertices of a basic polyhedron approximate to a shape of the 3D object;

a detailed vertex operation progressively determining vertices of a detailed polyhedron in a level of approximation to the 3D object that is higher than the basic polyhedron based on the level of approximation;

a detailed vertex coordinate operation for progressively calculating relative position coordinates of the detailed polyhedron vertices determined by said detailed vertex operation in a relative coordinate system based on a plurality of predetermined vertices of a polyhedron in a level of approximation that is lower than the detailed polyhedron;

a basic polygon data operation generating basic polygon data for representing the basic polyhedron based on information on the vertices of the basic polyhedron determined by the basic vertex operation;

a detailed polygon data operation generating detailed polygon data for representing each progressive detailed polyhedron in a corresponding level of approximation to the 3D object based on the information on vertices of the detailed polyhedron determined by the detailed vertex operation, which information is described in relative position coordinates in a relative coordinate system;

a polygon progressing operation combining the basic polygon data and the detailed polygon data and generating progressive polygon data for rendering respective models in each progressive level in a corresponding level of approximation to the 3D object; and

an outputting operation outputting the generated progressive polygon data.

45. A method for generating progressive polygon data comprising:

a basic vertex determining operation of determining vertices of a basic polyhedron approximate to a shape of a 3D object;

a detailed vertex determining operation of determining vertices of a polyhedron in a level of approximation to the 3D object that is higher than the basic polyhedron progressively based on the level of approximation;

a detailed vertex coordinate calculating operation of calculating relative position coordinates of vertices of a progressively determined polyhedron in a relative coordinate system based on a plurality of predetermined vertices of a polyhedron in a level of approximation that is lower than the polyhedron,

a basic polygon data generating operation of generating basic polygon data for representing basic polyhedron based on the information on vertices of a basic polyhedron determined by the basic vertex determining operation;

a detailed polygon data generating operation of generating detailed polygon data for representing each progressive detailed polyhedron in a corresponding level of approximation to the 3D object based on the information on vertices of detailed polyhedron determined by the detailed vertex determining operation, which information is described in relative position coordinates in a relative coordinate system; and

a polygon progressing operation of combining the basic polygon data and the detailed polygon data and generating progressive polygon data for rendering model in each progressive level in a corresponding level of approximation to the 3D object; and

an outputting operation outputting the generated progressive polygon data,

wherein the detailed vertex determining operation and the detailed vertex coordinate calculating operation are performed until the level of approximation reaches a predetermined level of approximation.

46. The method for generating progressive polygon data according to claim 45, wherein the level of approximation is determined by comparing a difference between an area of a face of a polyhedron defined by a vertex determined by the detailed vertex determining step and a plurality of predetermined vertices used for determining a coordinate system in the detailed vertex calculating step and an area of a potion corresponding to the face of the polyhedron represented by original polygon data obtained by geometric modeling of the object with a predetermined value.

47. A computer-readable recording medium storing a program, the program comprising:

a basic vertex determining operation of determining vertices of a basic polyhedron approximate to a shape of a 3D object;

a detailed vertex determining operation of determining vertices of a polyhedron in a level of approximation to the 3D object that is higher than the basic polyhedron progressively based on the level of approximation;

a detailed vertex coordinate calculating operation of calculating relative position coordinates of vertices of a progressively determined polyhedron in a relative coordinate system based on a plurality of predetermined vertices of a polyhedron in a level of approximation that is lower than the polyhedron,

a basic polygon data generating operation of generating basic polygon data for representing basic polyhedron based on the information on vertices of a basic polyhedron determined by the basic vertex determining operation;

a detailed polygon data generating operation of generating detailed polygon data for representing each progressive detailed polyhedron in a corresponding level of approximation to the 3D object based on the information on vertices of detailed polyhedron determined by the detailed vertex determining operation, which information is described in relative position coordinates in a relative coordinate system;

a polygon progressing operation of combining the basic polygon data and the detailed polygon data and generating progressive polygon data for rendering model in each progressive level in a corresponding level of approximation to the 3D object; and

an outputting operation outputting the generated progressive polygon data,

wherein the detailed vertex determining operation and the detailed vertex coordinate calculating operation are performed until the level of approximation reaches a predetermined level of approximation.

48. A computer-readable recording medium storing progressive polygon data,

wherein 3D polygon data representing an 3D object is produced based on the progressive polygon in accordance with a determined number of polygons;

the progressive polygon data comprises information about vertices of a basic polyhedron approximate to a shape of the 3D object and information about a plurality of detailed vertices obtained by sequentially computing vertices from the vertices of the basic polyhedron in accordance with the determined number of polygons so that a polyhedron in a higher level of approximation to the 3D object is generated;

the information of the detailed vertices is represented in the form of relative position coordinates in a relative coordinate system determined based on a plurality of predetermined vertices of a polyhedron not including the detailed vertices; and

the progressive polygon data is outputted.