Approximation method of shape data, information processing apparatus and medium

• US 6,690,827 B1
• Filed: 06/07/1999
• Issued: 02/10/2004
• Est. Priority Date: 06/12/1998
• Status: Expired due to Fees

• Current Assignee: Sony Corporation (Sony Group Corp.)
• Original Assignee: Sony Corporation (Sony Group Corp.)
• Inventors: Totsuka, Takashi, Horikawa, Junji
• Primary Examiner(s): Mariam, Daniel G.
• Application Number:
  US09/326,841
• Time in Patent Office: 1,709 Days
• Field of Search: 382/181, 382/195, 382/199, 382/203, 382/241, 382/266, 382/269, 382/275, 382/118, 382/190, 382/197, 382/242, 382/243, 382/215, 345/418, 345/419, 345/420, 345/428, 345/433, 345/441, 345/421, 345/424, 345/473, 345/581, 345/606
• US Class Current: 382/203
• CPC Class Codes: G06T 17/20 Finite element generation, e.g. wire-frame surface description, tesselation
• CPC Class Codes: G06T 17/205 Re-meshing

Abstract

An shape data approximation method for reducing the amount of data with an adjacency relationship between a plurality of components maintained. The shape data is read, an adjacent region of the shape data is designated, a virtual surface and a virtual edge are created in the designated adjacent region, and each edge in the shape data is evaluated to determine a evaluation score. The evaluation score is based on a change in the shape of the adjacent region on the assumption that the virtual edge is removed. The edges are subjected to data sorting, and an edge having a low evaluation score is removed with high priority, and resulting approximate shape data is thus output.

Claims

1. A method of approximating shape data at a desired level of detail to be approximate data, the approximation method comprising the steps of:

designating an adjacent region between at least first and second adjacent components in the shape data;

calculating an evaluation score in accordance with a degree of deformation of the adjacent region resulting from an approximation; and

approximating the shape data in accordance with the evaluation score to create the approximate data wherein a positional relationship between the at least first and second adjacent components is maintained.

2. The approximation method according to claim 1, further comprising the step of selecting an evaluation edge of interest for evaluation from the shape data,

wherein the evaluating step calculates the evaluation score in accordance with the degree of deformation of the adjacent region when the evaluation edge is removed from the shape data and,

wherein the approximating step approximates the shape data by determining, in accordance with the evaluation score, whether to remove the evaluation edge.

3. An approximation method according to claim 1, wherein the evaluating step places a virtual edge between apexes of adjacent components, and calculates the evaluation score in accordance with the degree of deformation of a virtual surface containing the virtual edge.

4. An approximation method according to claim 3, wherein the evaluating step calculates the evaluation score in accordance with a quantity of deformation by which the shape of the adjacent region deforms when the edge of the shape data or the virtual edge is removed.

5. An approximation method according to claim 3, wherein the evaluating step calculates the evaluation score in accordance with a change in height of the virtual surface including a new apex that is determined when the edge of the shape data or the virtual edge is removed.

6. An approximation method according the claim 5, wherein the evaluating step calculates the change in the height of the virtual surface including the new apex that is determined when the evaluation edge is removed, based on a rate of change between the height of the virtual surface before and after the removal of the evaluation edge.

7. An approximation method according to claim 5, wherein the evaluating step calculates the change in the height of the virtual surface including the new apex that is determined when the evaluation edge is removed, based on absolute values of the heights of the virtual surface before and after the evaluation edge is removed.

8. An approximation method according to claim 5, wherein the evaluating step calculates the evaluation score, based on the sum of changes in the heights of a plurality of virtual surfaces including the new apex that is determined when the evaluation edge is removed.

9. An approximation method according to claim 1, wherein the evaluating step calculates the evaluation score based on a quantity of change in the shape of the adjacent region when the edge of the shape data is removed.

10. An approximation method according to claim 9, wherein the evaluating step calculates the evaluation score, based on a change in spacing of the adjacent region when the edge of the shape data is removed.

11. A method for approximating shape data at a desired level of detail to be approximate data, the approximation method comprising the steps of:

placing a virtual edge between apexes of an adjacent region between a plurality of adjacent components within the shape data;

selecting an evaluation edge of interest for evaluation from edges constituting the shape data and the virtual edge;

calculating an evaluation score in accordance with a degree of importance of an evaluation edge in response to a removal of the evaluation edge; and

approximating the shape data in accordance with the evaluation score such that a positional relationship between said plurality of components in said shape data is maintained in said approximate data.

12. An approximation method according to claim 11, wherein the selecting step selects the evaluation edge from both the edges constituting the shape data and the virtual edge.

13. An approximation method according to claim 11, wherein the selecting step selects no virtual edge as an evaluation edge.

14. An approximation method according to claim 11, wherein the evaluating step calculates the evaluation score, based on a change in volume of a shape model when the evaluation edge is removed.

15. An approximation method according to claim 11, wherein the evaluating step calculates the evaluation score, based on a change in area of a shape model when the evaluation edge is removed.

16. An approximation method according to claim 11, wherein the evaluating step calculates the evaluation score, based on a change in the area of a contour constituted by an edge adjacent to the evaluation edge when the evaluation edge is removed.

17. An approximation method according the claim 11, wherein the forming step forms a virtual surface between the apexes of the adjacent region using the virtual edge formed between the apexes of the adjacent region, and

wherein the evaluating step calculates the evaluation score based on a change in height of a virtual surface when the edge constituting the virtual surface or the edge adjacent to the virtual surface is removed.

18. An approximation method according to claim 11, where the evaluating step calculates the evaluation score by summing at least two changes out of a change in the volume of a shape model, a change in the area of the shape model, a change in the area of a contour, and a change in the height of a virtual surface, when the evaluation edge is removed.

19. An information processing apparatus for approximating shape data at a desired level of detail to be approximate data, the apparatus comprising:

designating means for designating an adjacent region between at least first and second adjacent components in the shape data;

evaluating means for calculating an evaluation score in accordance with a degree of deformation of the adjacent region resulting from an approximation; and

approximating means for approximating the shape data in accordance with the evaluation score provided by the evaluating means to create the approximate data wherein a positional relationship between the at least first and second adjacent components is maintained.

20. An information processing apparatus according to claim 19, further comprising selecting means for selecting an evaluation edge of interest for evaluation from the shape data,

wherein the evaluating means calculates the evaluation score in accordance with the degree of deformation of the adjacent region when the evaluation edge is removed from the shape data and,

wherein the approximating means approximates the shape data by determining, in accordance with the evaluation score, whether to remove the evaluation edge.

21. An information processing apparatus according to claim 19, wherein the evaluating means places a virtual edge between apexes of adjacent components, and calculates the evaluation score in accordance with the degree of deformation of a virtual surface containing the virtual edge.

22. An information processing apparatus according to claim 21, wherein the evaluating means calculates the evaluation score in accordance with a quantity of deformation by which the shape of the adjacent region deforms when the edge of the shape data or the virtual edge is removed.

23. An information processing apparatus according to claim 21, wherein the evaluating means calculates the evaluation score in accordance with a change in the height of the virtual surface including a new apex that is determined when the edge of the shape data or the virtual edge is removed.

24. An information processing apparatus according to claim 23, wherein the evaluating means calculates the change in the height of the virtual surface including the new apex that is determined when the evaluation edge is removed, based on a rate of change between a height of the virtual surface before and after the removal of the evaluation edge.

25. An information processing apparatus according to claim 23, wherein the evaluating means calculates the change in the height of the virtual surface including the new apex that is determined when the evaluation edge is removed, based on absolute values of heights of the virtual surface before and after the removal of the evaluation edge.

26. An information processing apparatus according to claim 23, wherein the evaluating means calculates the evaluation score, based on the sum of changes in the heights of a plurality of virtual surfaces including the new apex that is determined when the evaluation edge is removed.

27. An information processing apparatus according to claim 19, wherein the evaluating means calculates the evaluation score, based on a quantity of change in the shape of the adjacent region when the edge of the shape data is removed.

28. An information processing apparatus according to claim 27, wherein the evaluating means calculates the evaluation score, based on a change in spacing of the adjacent region when the edge of the shape data is removed.

29. An information processing apparatus for approximating shape data at a desired level of detail to be approximate data, the apparatus comprising:

forming means for placing a virtual edge between apexes of an adjacent region where between a plurality of components are adjacent to each other in the shape data;

selecting means for selecting an evaluation edge of interest for evaluation from edges constituting the shape data and the virtual edge;

evaluating means for calculating an evaluation score in accordance with a degree of importance of the evaluation edge in response to a removal of the evaluation edge; and

approximating means for approximating the shape data in accordance with the evaluation score wherein a positional relationship between the plurality of components in the shape data is maintained in the approximate data.

30. An information processing apparatus according to claim 29, wherein the selecting means selects the evaluation edge from both the edge constituting the shape data and the virtual edge.

31. An information processing apparatus according to claim 29, wherein the selecting means selects no virtual edge as an evaluation edge.

32. An information processing apparatus according to claim 29, wherein the evaluating means calculates the evaluation score, based on a change in volume of a shape model when the evaluation edge is removed.

33. An information processing apparatus according to claim 29, wherein the evaluating means calculates the evaluation score, based on a change in area of a shape model when the evaluation edge is removed.

34. An information processing apparatus according to claim 29, wherein the evaluating means calculates the evaluation score, based on a change in areas of a contour constituted by edges adjacent to the evaluation edge when the evaluation edge is removed.

35. An information processing apparatus according to claim 29, wherein the forming means forms a virtual surface between the apexes of the adjacent region using the virtual edge formed between the apexes of the adjacent region, and

wherein the evaluating means calculates the evaluation score, based on a change in height of the virtual surface when the edge constituting the virtual surface or the edge adjacent to the virtual surface is removed.

36. An information processing apparatus according to claim 29, where the evaluating means calculates the evaluation score by summing at least two changes out of a change in the volume of a shape model, a change in the area of the shape model, a change in the area of a contour, and a change in the height of a virtual surface, when the evaluation edge is removed.

37. An information processing apparatus for approximating shape data at a desired level of detail to be approximate data, the apparatus comprising:

a storage unit for storing a program including process steps; and

a control circuit for executing the program in accordance with the process steps,

wherein the program comprises the steps of;

designating an adjacent region between at least first and second adjacent components in the shape data;

calculating an evaluation score in accordance with a degree of deformation of the adjacent region resulting from an approximation; and

approximating the shape data in accordance with the evaluation score provided by the calculating means to create the approximate data wherein a positional relationship between the at least first and second components in the shape data is maintained in said approximate data.

38. An information processing apparatus for approximating shape data at a desired level of detail to be approximate data, the apparatus comprising:

a storage unit for storing a program including process steps; and

a control circuit for executing the program in accordance with the process steps,

wherein the program comprises the steps of;

placing a virtual edge between apexes of an adjacent region between a plurality of adjacent components within the shape data;

selecting an evaluation edge of interest for evaluation from an edge constituting the shape data and the virtual edge;

calculating an evaluation score in accordance with a degree of importance of the evaluation edge in response to a removal of the evaluation edge; and

approximating the shape data in accordance with the evaluation score such that a positional relationship between said plurality of components in said shape data is maintained in said approximate data.

39. A storage medium having a computer program stored thereon, the computer program adapted to be read from the storage medium and executed by an information processing apparatus, the program comprising the steps of:

designating an adjacent region where a plurality of components are adjacent to each other in the shape data;

calculating an evaluation score in accordance with a degree of deformation of the adjacent region resulting from an approximation; and

approximating the shape data in accordance with the evaluation score to create the approximate data such that a positional relationship between said plurality of components in said shape data is maintained in said approximate data.

40. A storage medium having a computer program stored thereon, the computer program adapted to be read from the storage medium and executed by an information processing apparatus, the program comprising the steps of:

placing a virtual edge between apexes of an adjacent region between a plurality of adjacent components within the shape data;

selecting an evaluation edge of interest for evaluation from an edge constituting the shape data and the virtual edge;

calculating an evaluation score in accordance with a degree of importance of the evaluation edge in response to a removal of the evaluation edge; and

approximating the shape data in accordance with the evaluation score such that a positional relationship between said plurality of components in said shape data is maintained in said approximate data.

41. A computer readable storage medium having approximate data stored thereon, where the approximate data represents shape data that has been approximated to a desired level of detail, wherein the approximate data is processed in accordance with “

the” and

replace it with “

a”

process that comprises the steps of;

designating an adjacent region where a plurality of components are adjacent to each other in the shape data;

calculating an evaluation in accordance with a degree of deformation of the adjacent region resulting from an approximation; and

approximating the shape data in accordance with the evaluation score provided through the calculating step to create the approximate data such that a positional relationship between said plurality of components in said shape data is maintained in said approximate data.

42. A computer readable storage medium having approximate data stored thereon, where the approximate data represents shape data that has been approximated to a desired level of detail, wherein the approximate data is processed in accordance with a process that comprises the steps of:

placing a virtual edge between apexes of an adjacent region between a plurality of adjacent components within the shape data;

selecting an evaluation edge of interest for evaluation from an edge constituting the shape data and the virtual edge;

calculating an evaluation score in accordance with a degree of importance of the evaluation edge in response to a removal of the evaluation edge; and

approximating the shape data in accordance with the evaluation score such that a positional relationship between said plurality of components in said shape data is maintained in said approximate data.

43. A storage medium having a computer program stored thereon, the computer program adapted to be executed by an information processing apparatus in order to create approximate data by approximating shape data at a desired level of detail, the program comprising the steps of:

designating an adjacent region where a plurality of components are adjacent to each other in the shape data;

calculating an evaluation score in accordance with a degree of deformation of the adjacent region resulting from an approximation; and

approximating the shape data in accordance with the evaluation score to create the approximate data such that a positional relationship between said plurality of components in said shape data is maintained in said approximate data.

44. A storage medium having a computer program stored thereon, the computer program adapted to be executed by an information processing apparatus in order to create approximate data by approximating shape data at a desired level of detail, the program comprising the steps of:

placing a virtual edge between apexes of an adjacent region between a plurality of adjacent components within the shape data;

selecting an evaluation edge of interest for evaluation from an edge constituting the shape data and the virtual edge;

calculating an evaluation score in accordance with a degree of importance of the evaluation edge in response to a removal of the evaluation edge; and

approximating the shape data in accordance with the evaluation score such that a positional relationship between said plurality of components in said shape data is maintained in said approximate data.

45. An image processing method for reducing image data to approximate image data, the method comprising the steps of:

designating a region between a plurality of image components within the image data;

creating a virtual surface including a virtual edge within said designated region by connecting vertices of said components to each other across said region;

reducing said image data to approximate image data in a manner such that the shape of at least one of the virtual surface and the virtual edge is maintained so that the positional relationship between the image components is maintained in the approximate data.

46. The image processing method according to claim 45, further comprising the step of selecting an evaluation edge of interest for evaluation from the image data,

wherein the reducing step calculates an evaluation score in accordance with a degree of deformation of the adjacent region when the evaluation edge is removed from the image data and,

wherein the reducing step approximates the image data by determining, in accordance with the evaluation score, whether to remove the evaluation edge.

47. An image processing method according to claim 45, wherein the reducing step places a virtual edge between apexes of adjacent components, and calculates an evaluation score in accordance with the degree of deformation of a virtual surface containing the virtual edge.

48. An image processing method according to claim 47, wherein the reducing step calculates an evaluation score in accordance with a quantity of deformation by which the shape of the adjacent region deforms when the edge of the shape data or the virtual edge is removed.

49. An image processing method according to claim 47, wherein the reducing step calculates an evaluation score in accordance with a change in height of the virtual surface including a new apex that is determined when the edge of the shape data or the virtual edge is removed.

50. An image processing method according to claim 49, wherein the reducing step calculates the change in the height of the virtual surface including the new apex that is determined when the evaluation edge is removed, based on a rate of change between the heights of the virtual surface before and after the removal of the evaluation edge.

51. An image processing method according to claim 49, wherein the reducing step calculates the change in the height of the virtual surface including the new apex that is determined when the evaluation edge is removed, based on absolute values of the heights of the virtual surface before and after the evaluation edge is removed.

52. An image processing method according to claim 49, wherein the reducing step calculates the evaluation score, based on the sum of changes in the heights of a plurality of virtual surfaces including the new apex that is determined when the evaluation edge is removed.

53. An image processing method according to claim 45, wherein the reducing step calculates the evaluation score based on a quantity of change in the shape of the adjacent region when the edge of the shape data is removed.

54. An image processing method according to claim 53, wherein the reducing step calculates the evaluation score, based on a change in spacing of the adjacent region when the edge of the shape data is removed.