Selective mesh refinement

• US 6,931,155 B1
• Filed: 08/03/1999
• Issued: 08/16/2005
• Est. Priority Date: 08/03/1998
• Status: Expired due to Fees

• Current Assignee: Orange S.A., Telediffusion De France SA
• Original Assignee: Telediffusion De France SA
• Inventors: Gioia, Patrick
• Primary Examiner(s): Do, Anh Hong
• Application Number:
  US09/743,972
• Time in Patent Office: 2,205 Days
• Field of Search: 382/232, 382/240, 382/248, 345/419, 345/582, 345/418, 345/420, 345/428, 348/564, 708/203
• US Class Current: 382/232
• 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

The invention concerns a method for coding an original mesh representing a three-dimensional object, which consist in determining a simple meshing having a reduced number of defined faces each defined by vertices and edges, then coefficients in a wavelet base of a function whereof said source mesh is the image defined on said simple mesh, so as to supply successive refined meshes. The method is characterized in that each of the faces of said meshes is subdivided into a limited number of facets to form the higher level mesh, the subdivisions of said surface corresponding only to those required for observing an affinity condition of said function of said face. The invention also concerns the corresponding method for reconstructing the mesh.

Claims

1. Method for the encoding of a source mesh (M) representing a 3D object in which is determined a simple mesh (M₀) with a limited number of faces, each defined by vertices, ridges, and coefficients in a base of wavelets of a function (f) of which said source mesh is the image defined on said simple mesh (M₀), so as to give a subdivision of said source mesh (M) into successive refined meshes (or sub-meshes) (M_j), according to a predetermined criterion, which comprises:

each of the faces of said meshes (M_j) is subdivided into a limited number of facets to form the higher-level mesh (M_j+1), and

the subdivisions of said face corresponding solely to those needed to comply with a condition of affinity of said function (f) on said face.

2. Encoding method according to claim 1, characterized in that said source mesh (M) is subdivided up into a set of trees, each of said trees representing a face of said simple mesh (M₀) and comprising nodes each representing a face of a mesh (M_j), said function (f) being refined on each of said faces and each of said trees being the smallest such that, when a given face is subdivided into four facets, the corresponding node comprises four offspring representing said four facets.

3. Encoding method according to claim 1, characterized in that it enables access to several levels of encoding quality, corresponding to each of said successive meshes.

4. Encoding method according to claim 1, characterized in that said successive meshes are obtained by the implementation of a recursive algorithm.

5. Encoding method according to claim 1, characterized in that said recursive algorithm comprises the following steps:

(a) the reception (31) of a wavelet coefficient indexed by a vertex (s) of barycentric coordinates (α

,β

,γ

) on a face F₀;

(b) for each neighboring face F_j of F₀ containing said vertices (s);

F=F_i is supposed;

from the barycentric coordinates (α

,β

,γ

), the coordinates of said vertex (s) in the refined base (42) formed by the vertices of the face F, also referenced (α

,β

,γ

) are deduced;

if the coordinates α

, β

, or γ

are positive or zero and if two of them are strictly positive (43);

the face F (45) is subdived;

the processing of the step (b) is resumed for the four offspring of the face F successively.

6. Method of reconstruction of a source mesh (M) representing a 3D object encoded according to the encoding method of claim 1, characterized in that said object is reconstructed progressively, using the simple mesh (M₀), and then by means of successive meshes (M_i).

7. Method of reconstruction according to claim 6, characterized in that it enables access to several levels of quality of encoding, corresponding to each of said successive meshes.

8. Application of the encoding method according to claim 1 to at least one of the following fields:

the display of meshed objects in a 3D screen;

the progressive display of meshed objects in three dimensions on a screen, said wavelet coefficients being taken into account as and when they arrive;

the display of meshed objects in three dimensions on a screen with at least two levels of detail, one level of detail corresponding to one of said successive meshes (M_i);

the display of different parts of a meshed object with at least two different levels of detail;

the compression of a mesh of a meshed object.