Method and apparatus for reducing three-dimensional shape data

• US 20020003539A1
• Filed: 12/27/2000
• Published: 01/10/2002
• Est. Priority Date: 12/27/1999
• Status: Active Grant

• Current Assignee: Minolta Co., Ltd. (Konica Minolta Inc.)
• Original Assignee: Minolta Co., Ltd. (Konica Minolta Inc.)
• Inventors: Abe, Yoshihisa
• Granted Patent: US 6,958,753 B2
• Time in Patent Office: Days
• US Class Current: 345/428
• CPC Class Codes: G06T 17/205 Re-meshing

Abstract

A method and apparatus for reducing three-dimensional shape data, includes calculating estimation values for portions to be deformed by converging two or more vertices of a polygon model, and reducing the number of data for the polygon model by converging two or more vertices of the polygon model when the estimation values are equal to or below the predetermined permissible value. Estimation values for surfaces to be deformed by shrinking edges or surfaces are calculated based on distances between the respective surfaces and all the original vertices involved in the surface deformation. Before each data reduction, the portion having been involved in all the previous data reductions is defined as a reduction prohibition area, and a succeeding data reduction is applied to a portion other than the reduction prohibition area.

Claims

1. A method for reducing three-dimensional shape data, comprising the steps of:

calculating estimation values for surfaces to be deformed by shrinking edges or surfaces of a polygon model by converging two or more vertices of the polygon model based on distances between the respective surfaces and all the original vertices involved in the surface deformation;

comparing calculated estimation values with a predetermined permissible value; and

reducing the number of data for the polygon model by shrinking edges or surfaces of the polygon model when the estimation values are equal to or below the predetermined permissible value.

2. A method according to claim 1, wherein the estimation value is an error ε

defined by Equation (A);

3. A method according to claim 1, wherein the polygon model includes a number of triangular polygons.

4. A method f or reducing three-dimensional shape data, comprising the steps of:

calculating respective estimation values for a plurality of portions of a polygon model that are to be deformed by converging two or more vertices of the polygon model; and

reducing the number of data for the polygon model by converging two or more vertices of one portion of the polygon model based on the calculated estimation values after another portion, repeatedly,

wherein before each data reduction, the portion that has been involved in all the previous data reductions is defined as a reduction prohibition area, and a succeeding data reduction is applied to a portion other than the reduction prohibition area.

5. A method according to claim 4, wherein the reduction prohibition area is released if a predetermined condition is satisfied.

6. A method according to claim 5, where the predetermined condition is a state that there is no portion to be deformed by converging two or more vertices.

7. A method according to claim 5, wherein the predetermined condition is a state that a predetermined number of data reductions are completed.

8. An apparatus for reducing three-dimensional data, comprising:

an estimation value calculator which calculates estimation values for surfaces to be deformed by shrinking edges or surfaces of a polygon model by converging two or more vertices of the polygon model based on distances between the respective surfaces and all the original vertices involved in the surface deformation;

a comparator which compares calculated estimation values with a predetermined permissible value; and

a data reducing device which reduces the number of data for the polygon model by shrinking edges or surfaces of the polygon model when the estimation values are equal to or below the predetermined permissible value.

9. An apparatus according to claim 8, wherein the estimation value is an error ε

defined by Equation (A);

10. An apparatus according to claim 9, wherein the estimation value calculator calculates an error matrix Kv for each of all the vertices v constituting an original polygon model;

and when two or more vertices v_p (p=1, 2, . . . ) are converged into one vertex v_q, the estimation value calculator calculates an error ε

in accordance with the above-defined equation (A) by using a sum of error matrix Kv_p for each converged vertex v_p as an error matrix Kv_q for the vertex v_q.

11. An apparatus according to claim 10, wherein the estimation value calculator includes a memory which stores only diagonal elements and elements above them for the error matrix calculated for the original vertex v_i, and the estimation value calculator restores the error matrix using the diagonal elements and elements above them stored in the memory, and calculates an error ε

in accordance with the above-defined equation (A) by using the restored error matrix.

12. An apparatus according to claim 9, wherein the estimation value calculator calculates

13. An apparatus according to claim 9, wherein the estimation value calculator calculates an error ε

in accordance with the above-defined equation (A) by using a weighted error matrix w_j·

Kν

_j for the vertex V_j in place of Kv_j.

14. An apparatus according to claim 8, wherein the polygon model includes a number of triangular polygons.

15. An apparatus for reducing three-dimension shape data, comprising:

an estimation value calculator which calculates respective estimation values for a plurality of portions of a polygon model that are to be deformed by converging two or more vertices of the polygon model;

a judging device which judges based on a calculated estimated value whether a portion of the polygon model is permissible for the deformation;

a data reducing device which reduces the number of data of the polygon model by converging two or more vertices of one allowed portion based on calculated estimation values after another allowed portion; and

a prohibition area defining device which defines a portion having been involved in all the previous data reductions executed by the data reducing device as a prohibition area to keep a succeeding data reduction from being applied.

16. An apparatus according to claim 15, wherein the prohibition area defining device changes the estimation value for an involved portion to a predetermined value to render the involved portion impermissible by the judging device.

17. An apparatus according to claim 15, further comprising a prohibition releasing device which releases the prohibition area according to a predetermined condition.

18. An apparatus according to claim 17, where the predetermined condition is a state that there is no portion to be deformed by converging two or more vertices.

19. An apparatus according to claim 17, wherein the predetermined condition is a state that a predetermined number of data reductions are completed.

20. An apparatus according to claim 15, wherein the judging device includes:

a minimum estimation value calculator which calculates a minimum estimation value;

a comparator which compares the minimum estimation value with a permissible value; and

a determiner which determines a portion having the minimum estimation value as a portion to be converged when the minimum estimation value is equal or below the permissible value.

21. An apparatus according to claim 15, wherein the portion to be converged is an edge of a triangular polygon.

22. An apparatus according to claim 15, wherein the portion to be converged is a surface of a triangular polygon.