3D mesh coding/decoding method

• US 6,668,091 B1
• Filed: 06/24/1999
• Issued: 12/23/2003
• Est. Priority Date: 10/02/1998
• Status: Expired due to Term

• Current Assignee: Samsung Electronics Co. Ltd.
• Original Assignee: Samsung Electronics Co. Ltd.
• Inventors: Jung, Seok-yoon, Kim, Sung-jin, Han, Mahn-jin, Jang, Euee-seon, Seo, Yang-seock, Song, Mun-sup
• Primary Examiner(s): Do, Anh Hong
• Application Number:
  US09/339,161
• Time in Patent Office: 1,643 Days
• Field of Search: 382/243, 382/242, 382/241, 345/440, 716/5, 716/7
• US Class Current: 382/243
• CPC Class Codes: G06T 9/001 Model-based coding, e.g. wire frame
• CPC Class Codes: H04N 19/27 involving both synthetic and natural picture components, e.g. synthetic natural hybrid coding [SNHC]
• CPC Class Codes: H04N 19/30 using hierarchical techniques, e.g. scalability H04N19/63 takes precedence
• CPC Class Codes: H04N 19/89 involving methods or arrangements for detection of transmission errors at the decoder

Abstract

A progressive coding and decoding method of three-dimensional (3D) mesh data used in the fields of motion picture experts group-4 synthetic and natural hybrid coding (MPEG-4 SNHC), virtual reality modelling language (VRML) and the like. In transmitting 3D objects composed of 3D mesh data, it is very important to progressively restore transmitted data as well as to effectively code the 3D mesh data. In the progressive restoration, in the event that a transmission data error is generated, partial restoration of the transmitted data is allowed. Thus, it is possible to minimize the amount of mesh data to be transmitted again. The progressive restoration method which is resistant to such transmission errors can be effectively applied in wireless communications or low transmission rate communications. In the progressive coding and decoding method, connectivity, geometry and photometry necessary for progressively coding 3D mesh data are constructed and then coded/decoded, thereby providing data resilience against errors.

Claims

1. A progressive coding method of three dimensional (3D) mesh information comprising the steps of:

(a) dividing a 3D triangle mesh of a model into one or more connected components;

(b) generating a vertex graph and a triangle graph for each of the connected components;

(c) partitioning the vertex graph and triangle graph constituting the connected components into data partitions each capable of being independently decoded for the respective connected components and then coding the same;

(d) coding geometry containing positions of vertices of triangles constituting each partition, and photometry containing color, normal and texture coordinate information, for the respective data partitions.

2. The progressive coding method according to claim 1, wherein in the step (c), the vertex graph and triangle graph constituting the connected components are partitioned into independent data partitions for the respective connected components and then coded.

3. The progressive coding method according to claim 1, wherein in the step (c), all of the vertex graphs belonging to the model are collected and partitioned into data partitions having a predetermined size to then be coded, and all of the triangle graphs belonging to the model are collected and partitioned into data partitions having a predetermined size to then be coded.

4. The progressive coding method according to claim 1, wherein in the step (c), the vertex graphs constituting each connected component are coded into a data partition, and the triangle graphs are partitioned into data partitions having a predetermined size to then be coded.

5. The progressive coding method according to claim 1, wherein in the step (c), the vertex graphs and triangle graphs constituting the respective connected components are partitioned using one of prescribed partition types and coded, and then the partition type used for partitioning is coded.

6. The progressive coding method according to claim 5, wherein the partition types include a first partition type in which one or more vertex graphs and triangle graphs are sequentially contained, a second partition type in which only one vertex graph is contained, a third partition type in which the vertex graphs relating to the triangle graphs contained in other partition type and a part of the triangle graphs corresponding to the vertex graphs are contained, and a fourth partition type in which only triangle graphs are contained.

7. The progressive coding method according to claim 1, wherein in the step (c), of two branches connected to a branching triangle, the branch having fewer triangles is first coded and orientation information indicative of a traversing direction is then coded.

8. The progressive coding method according to claim 7, wherein the orientation information is given for each data partition containing the triangle graph.

9. The progressive coding method according to claim 7, wherein the orientation information is arranged in triangle trees constituting the triangle graphs.

10. The progressive coding method according to claim 7, wherein the orientation information is arranged in triangle data constituting the triangle graphs.

11. The progressive coding method according to claim 1, wherein if a branching triangle exists when the triangle graphs are partitioned and coded into data partitions in the step (c), data partitioning is performed at a position where all the triangle information of at least one of two branches connected to the branching triangle is contained.

12. The progressive coding method according to claim 1, wherein if a branching triangle exists when the triangle graphs are partitioned and coded into data partitions in the step (c), coding is performed with the Y-vertices of the branching triangle being contained in a header of the triangle graph.

13. The progressive coding method according to claim 12, wherein the Y-vertices are bounding loop indices therefor.

14. The progressive coding method according to claim 1, wherein when the 3D triangle mesh is reconstructed from a polygonal mesh into triangles so that it contains polygonal edges, in the step (c), partitioning is performed only at actual edges of the polygonal mesh, and the polygonal edges of the first triangle contained in the data partition of the triangle graph are not coded.

15. The progressive coding method according to claim 1, wherein when the 3D triangle mesh is reconstructed from a polygonal mesh into triangles so that it contains polygonal edges, in the step (c), partitioning is performed at both actual edges and virtual edges of the polygonal mesh, and the polygonal edges of the first triangle contained in the first data partition of the triangle graph are not coded.

16. The progressive coding method according to claim 1, wherein when the triangle graphs are partitioned and coded into data partitions in the step (c), coding is performed with pairs of bounding loop indices for starting points of the left and right boundaries in a triangle strip being contained in the header of the triangle graph.

17. The progressive coding method according to claim 16, wherein the indices for use in the pairs of bounding loop indices are one of a series of independent numbers for the respective connected components belonging to the model.

18. The progressive coding method according to claim 16, wherein the indices for use in the pairs of bounding loop indices are one of a series of numbers throughout the model.

19. The progressive coding method according to claim 1, wherein in the step (d), the geometry in the boundary between data partitions is coded only in the precedent data partition.

20. The progressive coding method according to claim 1, wherein in the step (d), the geometry in the boundary between data partitions is coded both in the precedent data partition and the subsequent data partition.

21. The progressive coding method according to claim 1, wherein in the step (d), the geometry in the boundary between data partitions is coded at the precedent data partition, and the geometry of the subsequent data partition and connected to more than a predetermined number is coded in the subsequent data partition.

22. The progressive coding method according to claim 1, wherein in the step (d), one half of the geometry sampled from the geometry in the boundary between data partitions is coded in the precedent data partition, and the other half is coded in the subsequent data partition.

23. The progressive coding method according to claim 1, wherein in the step (d), coding is selectively performed by a first geometry coding method in which the geometry in the boundary between data partitions is coded only at the precedent data partition, or a second geometry coding method in which the geometry in the boundary between data partitions is coded both in the precedent data partition and the subsequent data partition, and the selection information is then coded.

24. The progressive coding method according to claim 1, wherein in the step (d), the geometry and photometry are coded for the respective marching bits belonging to a data partition.

25. The progressive coding method according to claim 1, wherein in the step (d), the triangle graph, geometry and photometry belonging to a data partition are separately collected to form a partition and then coded.

26. The progressive coding method according to claim 1, wherein in the step (d), the triangle graph, geometry and photometry belonging to a data partition are separately collected to form each separate partition and then coded.

27. The progressive coding method according to claim 1, wherein the data partitions each contain an identifier and information on a number of triangles contained therein.

28. The progressive coding method according to claim 27, wherein the identifier corresponds to pairs of bounding loop indices for starting points on the left and right boundaries in a triangle strip when the triangle graphs are partitioned and coded into data partitions.

29. A progressive decoding method for receiving bitstreams coded by a progressive coding method comprising the steps of:

(a) dividing input bitstreams into units of data partitions;

(b) identifying the partition type of each of the data partitions;

(c) if the data partitions contain vertex graphs, decoding the vertex graphs to generate bounding loops;

(d) if the data partitions contain triangle graphs, decoding the triangle graphs to generate a 3D mesh; and

(e) repeating the steps (a) through (d) to progressively generate 3D meshes.

30. The progressive decoding method according to claim 29, wherein the partition types include a first partition type in which one or more vertex graphs and triangle graphs are sequentially contained, a second partition type in which only one vertex graph is contained, a third partition type in which the vertex graphs relating to the triangle graphs contained in other partition type and a part of the triangle graphs corresponding to the vertex graphs are contained, and a fourth partition type in which only triangle graphs are contained.

31. The progressive decoding method according to claim 29, wherein orientation information is given to triangle trees constituting the triangle graphs and a decoding direction is determined by the orientation information.

32. The progressive decoding method according to claim 29, wherein orientation information is given to triangle data constituting the triangle graphs and a decoding direction is determined by the orientation information.

33. The progressive decoding method according to claim 29, wherein Y-vertices of a branching triangle are given to the header of the triangle graphs and decoding is performed by the Y-vertices in the case of decoding the branching triangle.