Progressive 3D mesh coding method and apparatus

• US 6,563,500 B1
• Filed: 08/24/1999
• Issued: 05/13/2003
• Est. Priority Date: 08/29/1998
• Status: Expired due to Term

• Current Assignee: Samsung Electronics Co. Ltd.
• Original Assignee: Samsung Electronics Co. Ltd.
• Inventors: Kim, Sung-jin, Han, Mahn-jin, Jang, Euee-seon, Seo, Yang-seock, Song, Mun-sup
• Primary Examiner(s): Jankus, Almis R.
• Assistant Examiner(s): Sealey, Lance W.
• Application Number:
  US09/379,595
• Time in Patent Office: 1,358 Days
• Field of Search: 345/423, 345/440, 345/473, 345/419, 345/420
• US Class Current: 345/423
• CPC Class Codes: G06T 17/20 Finite element generation, e.g. wire-frame surface description, tesselation
• CPC Class Codes: G06T 9/001 Model-based coding, e.g. wire frame

Abstract

A progressive coding method and apparatus of three-dimensional (3D) mesh data is provided. The method includes the steps of (a) constructing a 3D triangle mesh of one or more mesh object layers, (b) partitioning each mesh object layer into a plurality of mesh components, (c) forming bitstreams in units of mesh components and coding the same, and (d) combining the coded mesh components into compressed bitstreams and transmitting the same. Therefore, progressive 3D mesh restoration is allowed, and the entropy coding efficiency can be enhanced.

Claims

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

(a) constructing a 3D triangle mesh of one or more mesh object layers;

(b) partitioning each mesh object layer into a plurality of mesh components;

(c) forming bitstreams in units of mesh components and coding the same; and

(d) combining the coded mesh components into compressed bitstreams and transmitting the same.

2. The progressive coding method according to claim 1, wherein the bitstreams formed in units of mesh components include vertex binary tree information and triangle binary tree information as the mesh data in each mesh component, and the total number of mesh components is represented in addition to the vertex binary tree information to be first coded among the bitstreams of the mesh components.

3. A progressive 3D mesh coding method comprising the steps of:

(a) constructing a 3D triangle mesh of one or more mesh object layers;

(b) partitioning each mesh object layer into a plurality of mesh components;

(c) classifying the plurality of mesh components in accordance with size information of each mesh component, combining mesh components having a first predetermined size or smaller and reconstructing all mesh components to have a size greater than the first predetermined size;

(d) partitioning mesh data in each mesh component into units of bitstreams having a second predetermined size and coding the same; and

(e) combining the coded mesh data into compressed bitstreams and transmitting the same.

4. The progressive 3D mesh coding method according to claim 3, wherein in the step (c), if the total number of vertices in a vertex binary tree constituting a mesh component is less than or equal to the reference number of vertices, the mesh component is combined with the mesh component to be coded next to be reconstructed such that the mesh components to be coded have a vertex binary tree in which the total number of vertices is greater than a first predetermined reference number of vertices.

5. The progressive 3D mesh coding method according to claim 4, wherein in the step (d), the vertex binary tree information and triangle binary tree information constituting mesh data in each mesh component are partitioned into a second predetermined reference number of vertices and into a predetermined number of triangles.

6. The progressive 3D mesh coding method according to claim 3, wherein in the step (d), the vertex binary tree information and triangle binary tree information constituting mesh data in each mesh component are partitioned into a second predetermined reference number of vertices and into a predetermined number of triangles.

7. The progressive 3D mesh coding method according to claim 3, wherein the compressed bitstreams include the total number of mesh components reconstructed in the step (c), vertex tree headers and triangle tree headers constituting the respective reconstructed mesh components, and vertex tree bitstreams of a plurality of triangle binary trees and triangle tree bitstreams of a plurality of triangle binary trees, partitioned into units of bistreams having a second predetermined size and then reconstructed.

8. The progressive 3D mesh coding method according to claim 7, wherein the compressed bitstreams further include Y-vertex information which provides connectivity information in a constant direction at a branching point of a binary tree, the Y-vertex information including the total number of Y-vertices present in the respective reconstructed mesh components, and geometry information of Y-vertices represented by the total number of triangles present in a tree positioned to the right of a branching point of the triangle binary tree with respect to each Y-vertex, respectively, and the Y-vertex information represented in addition to each of bitstreams of the plurality of vertex binary trees and bitstreams of the plurality of triangle binary trees.

9. The progressive 3D mesh coding method according to claim 7, wherein the compressed bitstreams further include Y-vertex information which provides connectivity information in a constant direction at a branching point of a binary tree, the Y-vertex information including the total number of Y-vertices present in the respective reconstructed mesh components, the geometry information of Y-vertices represented as one bit in addition to symbols the branching point and end point of each vertex binary tree, and binary tree information of a Y-vertex representing information on the order of Y-vertices in the form of binary trees.

10. A progressive 3D mesh coding method comprising the steps of:

(a) constructing a 3D triangle mesh of one or more mesh object layers;

(b) partitioning each mesh object layer into a plurality of mesh components;

(c) inserting orientation information indicating the coding order of branches having branched from a branching triangle of a triangle binary tree into each mesh component, and coding the same; and

(d) combining the coded mesh data into compressed bitstreams and transmitting the same.

11. The progressive 3D mesh coding method according to claim 10, wherein the step (c) comprises the sub-steps of:

(c1) classifying the plurality of mesh components in accordance with size information of each mesh component and combining mesh components having a size less than or equal to a first predetermined size, so that all mesh components are reconstructed such that they have a constant size;

(c2) partitioning mesh data in each mesh component among the reconstructed mesh components into units of bitstreams having a second predetermined size; and

(c3) inserting orientation information into the bitstreams and coding the same.

12. The progressive 3D mesh coding method according to claim 11, wherein the compressed bitstreams include the total number of mesh components reconstructed in the step (c1), vertex tree headers and triangle tree headers constituting the respective reconstructed mesh components, and vertex tree bitstreams of a plurality of triangle binary trees and triangle tree bitstreams of a plurality of triangle binary trees, partitioned into units of bistreams having a second predetermined size and then reconstructed in the sub-step (c2).

13. The progressive 3D mesh coding method according to claim 12, wherein the orientation information is represented such that in consideration of the sizes of two branches in branching triangles contained in a triangle binary tree for the mesh components reconstructed in the sub-step (c1) and a predetermined reference number of triangles, if the number of branching triangles is larger than the predetermined reference number of triangles, a relatively smaller branch is first coded.

14. The progressive 3D mesh coding method according to claim 11, wherein the orientation information is represented such that in consideration of the sizes of two branches in branching triangles contained in a triangle binary tree for the mesh components reconstructed in the sub-step (c1) and a predetermined reference number of triangles, if the number of branching triangles is larger than the predetermined reference number of triangles, a relatively smaller branch is first coded.

15. The progressive 3D mesh coding method according to claim 10, wherein in the step (c), when constructing triangle binary tree information for each mesh component, N trun units and M tleaf units, in which N is the number of triangles constituting the triangle binary tree and M is greater than or equal to zero and less than or equal to N, are constructed separately from triangle marching information and polygonal edge information, to increase the entropy coding efficiency and rendering efficiency.

16. A progressive three dimensional (3D) mesh coding apparatus for progressive restoration of 3D mesh information comprising:

a 3D mesh data analyzing portion for constructing a 3D triangle mesh of one or more mesh object layers and partitioning each mesh object layer into a plurality of mesh components;

a plurality of mesh component encoders for forming bitstreams in units of mesh components and coding the same; and

a multiplexer for combining the coded mesh components into compressed bitstreams and transmitting the same.

17. A progressive 3D mesh coding apparatus comprising:

a 3D mesh data partitioning portion for constructing a 3D triangle mesh of one or more mesh object layers and partitioning each mesh object layer into a plurality of mesh components;

a 3D mesh data classifying and combining portion for classifying the plurality of mesh components in accordance with size information of each mesh component, combining mesh components having a size less than or equal to a first predetermined size and reconstructing all mesh components to have a first predetermined size;

a plurality of mesh component encoders for partitioning mesh data in each mesh component into units of bitstreams having a second predetermined size and coding the same; and

a multiplexer for combining the coded mesh data into compressed bitstreams and transmitting the same.

18. The progressive 3D mesh coding method according to claim 17, wherein if the total number of vertices in a vertex binary tree constituting a mesh component is less than a first reference number of vertices, the 3D mesh data classifying and combining portion combines the mesh component with a mesh component to be coded next such that all mesh components to be coded are reconstructed to have a vertex binary tree in which the total number of vertices is larger than the first reference number of vertices.

19. The progressive 3D mesh coding method according to claim 18, wherein the plurality of mesh component encoders code the vertex binary tree information and triangle binary tree information constituting mesh data in each mesh component by partitioning the same into a second reference number of vertices and into a predetermined number of triangles, respectively.

20. The progressive 3D mesh coding method according to claim 17, wherein the plurality of mesh component encoders code the vertex binary tree information and triangle binary tree information constituting mesh data in each mesh component by partitioning the same into a second reference number of vertices and into a predetermined number of triangles, respectively.

21. A progressive three dimensional (3D) mesh coding apparatus for progressive restoration of 3D mesh information comprising:

a 3D mesh data analyzing portion for constructing a 3D triangle mesh of one or more mesh object layers and partitioning each mesh object layer into a plurality of mesh components;

a 3D mesh data classifying and combining portion for classifying the plurality of mesh components in accordance with size information of each mesh component, combining mesh components having a size less that or equal to a first predetermined size and reconstructing all mesh components to have a first predetermined size;

an orientation determining portion for inserting into the mesh data in each mesh component among the reconstructed mesh components, orientation information representing the coding order in a triangle branching in two directions in triangle binary tree information;

a plurality of mesh component encoders for forming bitstreams in units of mesh components and coding the same; and

a multiplexer for combining the coded mesh components into compressed bitstreams and transmitting the same.

22. The progressive 3D mesh coding method according to claim 21, wherein the orientation determining portion determines orientation information such that in consideration of sizes of two branches in branching triangles contained in a triangle binary tree for the reconstructed mesh components, the smaller branch is first coded.