Shape model generation device for generating shape models with a reduced number of polygons while maintaining quality of the two-dimensional image of the generated shape models

• US 5,754,182 A
• Filed: 11/08/1995
• Issued: 05/19/1998
• Est. Priority Date: 11/09/1994
• Status: Expired due to Term

• Current Assignee: Matsushita Electric Industrial Company Limited (Panasonic Holdings Corporation)
• Original Assignee: Matsushita Electric Industrial Company Limited (Panasonic Holdings Corporation)
• Inventors: Kobayashi, Tadashi
• Primary Examiner(s): Jankus, Almis R.
• Application Number:
  US08/555,035
• Time in Patent Office: 923 Days
• Field of Search: 395/119, 395/1, 395/123, 395/125, 395/128, 395/129, 395/133, 395/141, 345/423
• US Class Current: 345/423
• CPC Class Codes: G06T 17/20 Finite element generation, e.g. wire-frame surface description, tesselation

Abstract

An image generation system having a shape model generation device for generating a set of polygons which approximates a given solid having a curved surface and output vertex coordinates of each polygon in a screen coordinate system. An image generation device is provided for generating images for each polygon on receiving the vertex coordinates, and an image display device displays the generated images. The shape model generation device divides the solid into a set of polygons in a virtual-space, where the number of polygons used for dividing the solid into polygons is minimized while maintaining a high-quality display image. The set of polygons are projected onto a screen based on a designated view point and direction in the virtual-space, and the vertex coordinates of each polygon is transformed into two-dimensional screen coordinates. An edge judgment unit is provided in the shape model generation device for judging whether any side of each screen-projected polygon constitutes a part of an outline of the set of screen-projected polygons. An edge change unit in the shape model generation device generates a new vertex in the virtual-space on any side which constitutes a part of the outline, and the coordinates of the new vertex are transformed into two-dimensional screen coordinates. A polygon division unit is provided for dividing a screen-projected polygon including any side which constitutes a part of the outline into smaller screen-projected polygons at the new vertex.

Claims

1. In an image generation system having

a shape model generation device for generating a set of polygons which approximates to a given solid and outputting vertex coordinates of each polygon in a screen coordinate system,

an image generation device for generating images applying shading and the like to each polygon on receiving the vertex coordinates from the shape model generation device, and

an image display device for displaying an image generated by the image generation device,

the shape model generation device comprising:

a shape transformation means for transforming the solid having a given curved surface to the set of polygons approximating to a shape of the solid in a virtual-space, with a number of polygons being smaller than a standard division number for dividing the solid into polygons in order to display high-quality image by the image display device;

a coordinate transformation means for projecting the set of polygons transformed by the shape transformation means on a screen based on a designated view point and direction in the virtual-space, and transforming vertex coordinates of each polygon of the set of polygons to two-dimensional screen coordinates;

an edge judgement means for judging whether each side of each screen-projected polygon constitutes a part of an outline of the set of screen-projected polygons;

an edge change means for generating a new vertex in the virtual-space on any side which the edge judgement means judged to constitute a part of the outline and transforming coordinates of the new vertex to two-dimensional screen coordinates; and

a polygon division means for dividing a screen-projected polygon including any side which the edge judgement means judged to constitute a part of the outline into smaller screen-projected polygons at the new vertex transformed by the edge change means.

2. The shape model generation device of claim 1, wherein the shape transformation means includes:

a first solid storage unit for storing functions which express the shape of the solid beforehand;

a polygon mesh generation unit for generating a polygon mesh in which each polygon is seemingly quadrangular; and

an intersection point coordinate calculation unit for calculating virtual-space coordinates of each intersection point of the polygon mesh from the functions stored in the first solid storage unit, the virtual-space coordinates being used as data for expressing the solid.

3. The shape model generation device of claim 2, wherein the edge judgement means includes an outline side detection unit for detecting any side which constitutes a part of the outline of the set of screen-projected polygons from relation of each side and their neighboring two sides in the same direction.

4. The shape model generation device of claim 3, wherein the edge judgement means further includes a vertex number calculation unit for dividing a screen plane on which the set of polygons is projected into two by an extended line of any side of the screen-projected polygon, counting how many vertices exist in each region resulting from the division by the extended line, and recognizing that the side constitutes a part of the outline if the number of the vertices in each region is not equal.

5. The shape model generation device of claim 4, wherein the edge change means includes a middle point generation unit for generating a middle point on any side which the edge judgement means judged to constitute a part of the outline as a new vertex in the virtual-space and transforming coordinates of the middle point to two-dimensional screen coordinates.

6. The shape model generation device of claim 5 further includes an edge change prohibition means for prohibiting generation of a new vertex by the edge change means when a length of any side which the edge judgement means judged to constitute a part of the outline is equal to or shorter than a predetermined first threshold value, the first threshold value corresponding to a value of longest length of a side of a screen-projected polygon for expressing accurate outline.

7. The shape model generation device of claim 6, wherein the edge change means further includes a middle point generation cancellation unit for calculating distance between the side which constitutes a part of the outline and the new vertex generated by the middle point generation unit, and cancelling the new vertex when the distance is equal to or shorter than a predetermined second threshold value.

8. The shape model generation device of claim 7, wherein a smallest of the second threshold value corresponds to size of a pixel in the image display device.

9. The shape model generation device of claim 8, wherein the polygon division means includes:

a dividing-into-two unit for dividing a screen-projected polygon into two, the polygon including one side which the edge judgement means judged to constitute a part of the outline; and

a dividing-into-four unit for dividing a screen-projected polygon into four, the polygon including two or more sides which the edge judgement means judged to constitute a part of the outline.

10. The shape model generation device of claim 9 further includes:

a re-edge-change means for generating a new vertex in the virtual-space on a side of the screen-projected polygon divided by the polygon division means, and transforming coordinates of the new vertex to two-dimensional screen coordinates;

a re-edge-change prohibition means for prohibiting generation of a new vertex by the re-edge change means when length of the side treated by the re-edge change means is equal to or shorter than a predetermined first threshold value;

a re-edge-change cancellation means for calculating distance between the side and new vertex treated by the re-edge change means and cancelling the new vertex when the distance is equal to or shorter than a predetermined second threshold value; and

a re-polygon-division means for re-dividing a screen-projected polygon which was divided at the new vertex generated by the re-edge-change means.

11. The shape model generation device of claim 2 further includes an edge change prohibition means for prohibiting generation of a new vertex by the edge change means when a length of any side which the edge judgement means judged to constitute a part of the outline is equal to or shorter than a predetermined first threshold value, the first threshold value corresponding to a value of longest length of a side of a screen-projected polygon for expressing accurate outline.

12. The shape model generation device of claim 11, wherein the edge judgement means includes an outline side detection unit for detecting any side which constitutes a part of the outline of the set of screen-projected polygons from relation of each side and their neighboring two sides in the same direction.

13. The shape model generation device of claim 12, wherein the edge judgement means further includes a vertex number calculation unit for dividing a screen plane on which the set of polygons is projected into two by an extended line of any side of the screen-projected polygon, counting how many vertices exist in each region resulting from the division by the extended line, and recognizing that the side constitutes a part of the outline if the number of the vertices in each region is not equal.

14. The shape model generation device of claim 13, wherein the edge change means includes a middle point generation unit for generating a middle point on any side which the edge judgement means judged to constitute a part of the outline as a new vertex in the virtual-space and transforming coordinates of the middle point to two-dimensional screen coordinates.

15. The shape model generation device of claim 2 further includes:

a re-edge-change means for generating a new vertex in the virtual-space on a side of the screen-projected polygon divided by the polygon division means, and transforming coordinates of the new vertex to two-dimensional screen coordinates;

a re-edge-change prohibition means for prohibiting generation of a new vertex by the re-edge change means when length of the side treated by the re-edge change means is equal to or shorter than a predetermined first threshold value;

a re-edge-change cancellation means for calculating distance between the side and new vertex treated by the re-edge change means and cancelling the new vertex when the distance is equal to or shorter than a predetermined second threshold value; and

a re-polygon-division means for re-dividing a screen-projected polygon which was divided at the new vertex generated by the re-edge-change means.

16. The shape model generation device of claim 1, wherein the shape transformation means includes:

a second solid storage unit for storing the shape of the solid as virtual-space coordinates of vertices of the set of quadrangular polygons; and

a vertex read-out unit for reading out coordinates stored in the second solid storage unit at intervals, the coordinates being used as data for expressing a solid.

17. The shape model generation device of claim 16, wherein the edge judgement means includes an outline side detection unit for detecting any side which constitutes a part of the outline of the set of screen-projected polygons from relation of each side and their neighboring two sides in the same direction.

18. The shape model generation device of claim 17, wherein the edge judgement means further includes a vertex number calculation unit for dividing a screen plane on which the set of polygons is projected into two by an extended line of any side of the screen-projected polygon, counting how many vertices exist in each region resulting from the division by the extended line, and recognizing that the side constitutes a part of the outline if the number of the vertices in each region is not equal.

19. The shape model generation device of claim 18, wherein the edge change means includes a middle point read-out transformation unit for reading out a middle point on any side which the edge judgement means judged to constitute a part of the outline as a new vertex from the second solid storage unit and transforming coordinates of the new vertex to two-dimensional screen coordinates.

20. The shape model generation device of claim 19 further includes an edge change prohibition means for prohibiting generation of a new vertex by the edge change means when a length of any side which the edge judgement means judged to constitute a part of the outline is equal to or shorter than a predetermined first threshold value, the first threshold value corresponding to a value of longest length of a side of a screen-projected polygon for expressing accurate outline.

21. The shape model generation device of claim 20, wherein the edge change means further includes:

a middle point read-out transformation cancellation unit for calculating distance between the side which constitutes a part of the outline and the vertex read out by the middle point read-out transformation unit, and cancelling the vertex when the distance is equal to or shorter than the predetermined second threshold value.

22. The shape model generation device of claim 21, wherein a smallest of the second threshold value corresponds to size of a pixel in the image display device.

23. The shape model generation device of claim 22, wherein the polygon division means includes:

a dividing-into-two unit for dividing a screen-projected polygon into two, the polygon including one side which the edge judgement means judged to constitute a part of the outline; and

a dividing-into-four unit for dividing a screen-projected polygon into four, the polygon including two or more sides which the edge judgement means judged to constitute a part of the outline.

24. The shape model generation device of claim 23 further includes:

a re-edge-change means for reading out a middle point on a side of the screen-projected polygon divided by the polygon division means as a new vertex from the second solid storage unit, and transforming coordinates of the new vertex to two-dimensional screen coordinates; and

a re-edge-change prohibition means for prohibiting generation of a new vertex by the re-edge-change means when length of the side treated by the edge judgement means is equal to or shorter than the predetermined first threshold value;

a re-edge-change cancellation means for calculating distance between a side and the new vertex treated by the re-edge-change means, and cancelling the new vertex when the distance is equal to or shorter than the predetermined second threshold value; and

a re-polygon division means for re-dividing the screen-projected polygon divided at the new vertex read out by the re-edge-change means.

25. The shape model generation device of claim 16 further includes:

a re-edge-change means for reading out a middle point on a side of the screen-projected polygon divided by the polygon division means as a new vertex from the second solid storage unit, and transforming coordinates of the new vertex to two-dimensional screen coordinates; and

a re-edge-change prohibition means for prohibiting generation of a new vertex by the re-edge-change means when length of the side treated by the edge judgement means is equal to or shorter than the predetermined first threshold value;

a re-edge-change cancellation means for calculating distance between a side and the new vertex treated by the re-edge-change means, and cancelling the new vertex when the distance is equal to or shorter than the predetermined second threshold value; and

a re-polygon division means for re-dividing the screen-projected polygon divided at the new vertex read out by the re-edge-change means.