Search

EP-4740179-A1 - EDGEBREAKER MESH CODING WITH ALTERNATIVE VERTEX TRAVERSALS

EP4740179A1EP 4740179 A1EP4740179 A1EP 4740179A1EP-4740179-A1

Abstract

Example embodiments provide encoding and decoding methods and apparatus for coding of mesh data. In example embodiments of a mesh encoding method, input information is obtained defining at least one connected component of a mesh, the connected component having a plurality of vertices including a plurality of dummy vertices. During a first traversal of the connected component to encode a topology of the connected component, an index is assigned to each vertex representing an order in which the vertex is visited in the first traversal. At least one attribute of the connected component is encoded using a second traversal of the connected component, the second traversal using a different traversal order than the first traversal. A table is encoded identifying the dummy vertices, each dummy vertex being identified by its associated index. The table of dummy vertices may be sorted in an ascending order of indices.

Inventors

  • MARVIE, JEAN-EUDES
  • MOCQUARD, OLIVIER

Assignees

  • InterDigital CE Patent Holdings, SAS

Dates

Publication Date
20260513
Application Date
20240625

Claims (15)

  1. 1. A mesh encoding method comprising: obtaining input information defining at least one connected component of a mesh, the connected component having a plurality of vertices including a plurality of dummy vertices; during a first traversal of the connected component to encode a topology of the connected component, assigning an index to each vertex representing an order in which the vertex is visited in the first traversal; encoding at least one attribute of the connected component using a second traversal of the connected component, the second traversal using a different traversal order than the first traversal; and encoding a table identifying the dummy vertices, each dummy vertex being identified by its associated index.
  2. 2. A mesh encoding apparatus comprising one or more processors configured to perform at least: obtaining input information defining at least one connected component of a mesh, the connected component having a plurality of vertices including a plurality of dummy vertices; during a first traversal of the connected component to encode a topology of the connected component, assigning an index to each vertex representing an order in which the vertex is visited in the first traversal; encoding at least one attribute of the connected component using a second traversal of the connected component, the second traversal using a different traversal order than the first traversal; and encoding a table identifying the dummy vertices, each dummy vertex being identified by its associated index.
  3. 3. The method of claim 1 or the apparatus of claim 2, further comprising sorting the table in ascending order of indices.
  4. 4. The method of claim 1 or claim 3 as it depends from claim 1 , or the apparatus of claim 2 or claim 3 as it depends from claim 2, wherein obtaining input information defining at least one connected component comprises: obtaining information defining an input mesh, the input mesh having a plurality of holes; and for each of a plurality of the holes, adding a dummy vertex to fill the respective hole.
  5. 5. The method of claim 1 or claims 3-4 as they depend from claim 1 , or the apparatus of claim 2 or claims 3-4 as they depend from claim 2, wherein the input information defining the at least one connected component of a mesh comprises a corner table.
  6. 6. The method of claim 1 or claims 3-5 as they depend from claim 1 , or the apparatus of claim 2 or claims 3-5 as they depend from claim 2, wherein the encoding of the topology of the connected component is edgebreaker encoding.
  7. 7. The method of claim 1 or claims 3-6 as they depend from claim 1 , or the apparatus of claim 2 or claims 3-6 as they depend from claim 2, wherein the second traversal is performed according to a vertex-degree-based traversal method.
  8. 8. The method of claim 1 or claims 3-6 as they depend from claim 1 , or the apparatus of claim 2 or claims 3-6 as they depend from claim 2, wherein the second traversal is performed according to a depth-first traversal method.
  9. 9. The method of claim 1 or claims 3-8 as they depend from claim 1 , or the apparatus of claim 2 or claims 3-8 as they depend from claim 2, wherein the first attribute comprises at least one position coordinate of the respective vertex.
  10. 10. The method of claim 1 of claims 3-8 as they depend from claim 1 , or the apparatus of claim 2 or claims 3-8 as they depend from claim 2, wherein the first attribute comprises at least one UV coordinate of the respective vertex.
  11. 11 . A computer-readable medium storing a mesh encoded according to the method of claim 1 or claims 3-10 as they depend from claim 1 .
  12. 12. A mesh decoding method comprising: obtaining encoded information defining at least one connected component of a mesh, the connected component having a plurality of vertices including a plurality of dummy vertices; obtaining a table identifying an index of each of the dummy vertices; during a first traversal of the connected component to decode a topology of the connected component, identifying the dummy vertices based on the table; and decoding at least one attribute of the connected component using a second traversal of the connected component, the second traversal using a different traversal order than the first traversal, wherein the attribute is not decoded for the identified dummy vertices.
  13. 13. A mesh decoding apparatus comprising one or more processors configured to perform at least: obtaining encoded information defining at least one connected component of a mesh, the connected component having a plurality of vertices including a plurality of dummy vertices; obtaining a table identifying an index of each of the dummy vertices; during a first traversal of the connected component to decode a topology of the connected component, identifying the dummy vertices based on the table; and decoding at least one attribute of the connected component using a second traversal of the connected component, the second traversal using a different traversal order than the first traversal, wherein the attribute is not decoded for the identified dummy vertices.
  14. 14. The method of claim 12 or the apparatus of claim 13, wherein the table is sorted in ascending order of the indices.
  15. 15. The method of claim 12 or claim 14 as it depends from claim 12, or the apparatus of claim 13 or claim 14 as it depends from claim 13, wherein the decoding of the topology of the connected component is edgebreaker decoding.

Description

EDGEBREAKER MESH CODING WITH ALTERNATIVE VERTEX TRAVERSALS CROSS REFERENCE [0001] The present application claims the priority of European Patent Application No. 23306154.8, filed 7 July 2023, entitled “Edgebreaker Mesh Coding with Alternative Vertex Traversals,” which is incorporated herein by reference in its entirety. BACKGROUND [0002] The present disclosure relates to systems and methods for encoding and decoding a mesh based on edgebreaker technology. Edgebreaker is a technology that is capable of efficiently coding the connectivity of a triangular mesh. In its most straightforward implementation, a mesh encoded using edgebreaker is represented by an ordered series made up of the symbols, C, L, E, R, and S, called the “CLERS” sequence. Generally speaking, starting with an initial triangle, these symbols describe different ways to attach a new triangle, providing information on whether or how different edges of the new triangle are connected to one or more of the existing triangles. Edgebreaker technology is described in greater detail, for example in the following sources: • J. Rossignac, "3D compression made simple: Edgebreaker with ZipandWrap on a cornertable," in Proceedings International Conference on Shape Modeling and Applications, Genova, Italy, 2001. Desribes decoding in a forward direction with the use of a corner table (CT) representation of the mesh, which leads to a very compact algorithm. • H. Lopes, G. Tavares, J. Rossignac, A. Szymczak and A. Safonova, "Edgebreaker: a simple compression for surfaces with handles.," in ACM Symposium on Solid Modeling and Applications,, Saarbrucken, 2002. • J. Rossignac, "Edgebreaker: Connectivity compression for triangle meshes," GVU center, Georgia Institute of Technology, 1999. Describes decoding in a forward direction using a half-edge representation. • J. Rossigniac, "Course on triangle meshes and corner table," 2006. • M. Isenburg and J. Snoeyink, "Spirale Reversi: Reverse decoding of the Edgebreaker encoding," Computational Geometry, vol. 20, pp. 39-52, 2001. Describes the “spiral reversi” technique, which uses a half edge representation, but performing the decoding in a reverse manner, which leads to faster decoding of O(n). [0003] Following the MPEG V-Mesh (now renamed V-DMC) call for proposals the solution proposed by Apple was selected to become the foundation of the MPEG V-Mesh Test Model (TM). The proposal is described in K. Mammou, J. Kim, A. Tourapis and D. Podborski, "m59281 - [V-CG] Apple's Dynamic Mesh Coding CfP Response," Apple Inc, 2022. Summary figures depicting intra coding from the proposal are provided in FIG. 1 and FIG. 2 of the present disclosure. [0004] The test model, for some frames, uses a static mesh coder for the encoding of a base mesh that is then subdivided to obtain an approximation of the original mesh. Early versions of the V-Mesh test model encode a base mesh using the Google Draco implementation of an edgebreaker-based mesh encoder. Specifically, the implementation uses the “spirale reversi” version of edgebreaker as described in M. Isenburg and J. Snoeyink, "Spirale Reversi: Reverse decoding of the edgebreaker encoding," Computational Geometry, vol. 20, pp. 39-52, 2001. [0005] Version 4.0 of the test model (TM) of VDMC performs static mesh coding using the MPEG EdgeBreaker (MEB) implementation presented in J.-E. Marvie and O. Mocquard, “m63344 -[V-DMC][EE4.4]-an-efficient-Edgebreaker-implementation,” MPEG meeting 142, Antalya (hereinafter “Marvie & Mocquard”). Such static mesh coding is performed at the blocks “Static Mesh Coder” and “Static Mesh decoder” of FIG. 1 and FIG. 2). [0006] While edgebreaker coding provides an efficient way to code the connectivity of a base mesh, it has certain limitations. For example, edgebreaker coding on its own is effective only for manifold surfaces whithout “holes” or “handles.” Additional processing is required to bring such non-manifold surfaces into a format that is capable of being coded using edgebreker technology. Moreover, edgebreaker coding on its own only codes for the connectivity of a mesh. The CLERS sequence itslef does not code additional properties of a mesh, such as the locations of the vertices and any other attributes of the vertices (such as color, normal direction, UV coordinates, and the like). SUMMARY [0007] A mesh encoding method according to some embodiments comprises: obtaining input information defining at least one connected component of a mesh, the connected component having a plurality of vertices including a plurality of dummy vertices; during a first traversal of the connected component to encode a topology of the connected component, assigning an index to each vertex representing an order in which the vertex is visited in the first traversal; encoding at least one attribute of the connected component using a second traversal of the connected component, the second traversal using a different traversal order than the first traversal; and encoding