CN117915105A

CN117915105A - Grid coding method, grid decoding method and related equipment

Info

Publication number: CN117915105A
Application number: CN202211282835.1A
Authority: CN
Inventors: 邹文杰; 张伟; 杨付正; 吕卓逸
Original assignee: Vivo Mobile Communication Co Ltd
Current assignee: Vivo Mobile Communication Co Ltd
Priority date: 2022-10-19
Filing date: 2022-10-19
Publication date: 2024-04-19
Also published as: WO2024083039A1

Abstract

The application discloses a grid coding method, a grid decoding method and related equipment, belonging to the technical field of computers, wherein the grid coding method comprises the following steps: splitting a non-manifold structure in the grid to be coded to obtain non-manifold information and manifold grids; encoding the non-manifold information to obtain a first sub-code stream; encoding the manifold grid to obtain a second subcode stream; and obtaining a grid coding result according to the first sub-code stream and the second sub-code stream.

Description

Grid coding method, grid decoding method and related equipment

Technical Field

The application belongs to the technical field of computers, and particularly relates to a grid coding method, a grid decoding method and related equipment.

Background

With the rapid development of multimedia technology, three-dimensional models become a new generation of digital media following audio, images, and video. Three-dimensional grids and point clouds are two commonly used three-dimensional model representations. Compared with traditional multimedia such as images and videos, the three-dimensional grid model has the characteristics of stronger interactivity and reality, and has wider application range.

At present, when a three-dimensional grid is encoded at an encoding end, the grid with a non-manifold structure is converted into the grid with the manifold structure for encoding, and the grid with the manifold structure is obtained when a decoding end decodes the grid, so that the grid decoded by the decoding end and the grid encoded by the encoding end have larger difference, and the quality loss of grid information after encoding and decoding is larger.

Disclosure of Invention

The embodiment of the application provides a grid coding method, a grid decoding method and related equipment, which can solve the problem of larger quality loss of grid information after three-dimensional grid coding and decoding processing.

In a first aspect, there is provided a trellis encoding method, comprising:

splitting a non-manifold structure in the grid to be coded to obtain non-manifold information and manifold grids;

Encoding the non-manifold information to obtain a first sub-code stream;

encoding the manifold grid to obtain a second subcode stream;

And obtaining a grid coding result according to the first sub-code stream and the second sub-code stream.

In a second aspect, there is provided a trellis decoding method, comprising:

acquiring a first subcode stream and a second subcode stream according to a grid coding result of a grid to be decoded;

decoding the first subcode stream to obtain non-manifold information;

Decoding the second subcode stream to obtain a manifold grid;

And reconstructing the manifold grid based on the non-manifold information to obtain a decoding grid.

In a third aspect, there is provided a trellis encoding device comprising:

The processing module is used for splitting the non-manifold structure in the grid to be coded to obtain non-manifold information and manifold grids;

the first coding module is used for coding the non-manifold information to obtain a first subcode stream;

The second coding module is used for coding the manifold grids to obtain a second subcode stream;

and the acquisition module is used for acquiring a grid coding result according to the first subcode stream and the second subcode stream.

In a fourth aspect, there is provided a trellis decoding device, comprising:

the acquisition module is used for acquiring a first subcode stream and a second subcode stream according to the grid coding result of the grid to be decoded;

the first decoding module is used for decoding the first sub-code stream to obtain non-manifold information;

The second decoding module is used for decoding the second subcode stream to obtain a manifold grid;

and the processing module is used for reconstructing the manifold grid based on the non-manifold information to obtain a decoding grid.

In a fifth aspect, there is provided a terminal comprising a processor, a memory and a program or instruction stored on the memory and executable on the processor, the program or instruction when executed by the processor implementing the steps of the method according to the first aspect; or the program or instructions when executed by the processor implement the steps of the method as described in the second aspect.

In a sixth aspect, a terminal is provided, including a processor and a communication interface, where the processor is configured to:

Encoding the non-manifold information to obtain a first sub-code stream;

encoding the manifold grid to obtain a second subcode stream;

In a seventh aspect, a terminal is provided, including a processor and a communication interface, where the processor is configured to:

decoding the first subcode stream to obtain non-manifold information;

Decoding the second subcode stream to obtain a manifold grid;

In an eighth aspect, there is provided a readable storage medium having stored thereon a program or instructions which when executed by a processor, performs the steps of the trellis encoding method of the first aspect, or which when executed by a processor, performs the steps of the trellis decoding method of the second aspect.

In a ninth aspect, there is provided a chip comprising a processor and a communication interface, the communication interface and the processor being coupled, the processor being for running a program or instructions, implementing the steps of the method as described in the first aspect, or implementing the steps of the method as described in the second aspect.

In a tenth aspect, a computer program/program product is provided, stored in a non-volatile storage medium, the program/program product being executed by at least one processor to implement the steps of the method as described in the first aspect, or to implement the steps of the method as described in the second aspect.

In the embodiment of the application, the non-manifold structure in the grid to be coded is split to obtain non-manifold information and manifold grids; encoding the non-manifold information to obtain a first sub-code stream; encoding the manifold grid to obtain a second subcode stream; and obtaining a grid coding result according to the first sub-code stream and the second sub-code stream. Thus, the non-manifold information obtained by splitting the non-manifold structure is encoded, so that the non-manifold structure can be reconstructed through the non-manifold information during decoding, the quality loss of grid information after encoding and decoding can be reduced or even eliminated, and lossless encoding is realized.

Drawings

FIG. 1 is a schematic diagram of five modes of Edgebreaker in the related art;

FIG. 2 is a flowchart of a trellis encoding method provided by an embodiment of the present application;

FIG. 3 is a flowchart of another trellis encoding method provided by an embodiment of the present application;

FIG. 4 is one of the schematic diagrams of a grid provided by an embodiment of the present application;

FIG. 5 is a schematic view of an angle (Corner) relationship provided by an embodiment of the present application;

FIG. 6 is a diagram of a grid traversal provided by an embodiment of the application;

FIG. 7 is a second schematic diagram of a grid according to an embodiment of the present application;

FIG. 8 is a third schematic view of a grid provided in accordance with an embodiment of the present application;

Fig. 9 is a flowchart of a trellis decoding method according to an embodiment of the present application;

FIG. 10 is a flowchart of another trellis decoding method provided by an embodiment of the present application;

FIG. 11 is a schematic diagram of a trellis encoding device according to an embodiment of the present application;

fig. 12 is a schematic structural diagram of a trellis decoding device according to an embodiment of the present application;

Fig. 13 is a schematic structural diagram of a communication device according to an embodiment of the present application;

Fig. 14 is a schematic structural diagram of a terminal according to an embodiment of the present application.

Detailed Description

The technical solutions of the embodiments of the present application will be clearly described below with reference to the drawings in the embodiments of the present application, and it is apparent that the described embodiments are some embodiments of the present application, but not all embodiments. All other embodiments, which are derived by a person skilled in the art based on the embodiments of the application, fall within the scope of protection of the application.

The terms first, second and the like in the description and in the claims, are used for distinguishing between similar elements and not necessarily for describing a particular sequential or chronological order. It is to be understood that the terms so used are interchangeable under appropriate circumstances such that the embodiments of the application are capable of operation in sequences other than those illustrated or otherwise described herein, and that the "first" and "second" distinguishing between objects generally are not limited in number to the extent that the first object may, for example, be one or more. Furthermore, in the description and claims, "and/or" means at least one of the connected objects, and the character "/" generally means a relationship in which the associated object is an "or" before and after.

The codec end corresponding to the codec method in the embodiment of the present application may be a terminal, which may also be referred to as a terminal device or a User Equipment (UE), and the terminal may be a mobile phone, a tablet (Tablet Personal Computer), a laptop (laptop computer) or a terminal-side device called a notebook, a personal digital assistant (personal DIGITAL ASSISTANT, PDA), a palm computer, a netbook, an ultra-mobile personal computer, a UMPC, a mobile internet device (mobile INTERNET DEVICE, MID), an augmented reality (augmented reality, AR)/Virtual Reality (VR) device, a robot, a wearable device (Wearable Device) or a vehicle-mounted device (VUE), a pedestrian terminal (PUE), and the wearable device includes: smart watches, bracelets, headphones, eyeglasses, etc. It should be noted that, the embodiment of the present application is not limited to a specific type of terminal.

For ease of understanding, some of the following descriptions are directed to embodiments of the present application:

(1) Open source three-dimensional grid compression tool Draco

Draco respectively encoding and storing the connection information, the geometric information and the UV coordinates of the three-dimensional grid. The key module, namely the module for encoding the connection information, uses Edgebreaker algorithm. The geometric information and UV coordinates are encoded by conventional compression methods, namely quantization, predictive compression (parallelogram prediction) and entropy coding of the data. Since Draco adopts the coding method driven by the connection relation, the coding of the geometric information and the UV coordinates follows the coding sequence of the connection information. In this way, the vertex sequence of the connection relation code is implicit in the vertex sequence of the geometric information to avoid separately transmitting the vertex sequence of the connection relation code, thereby saving the bit overhead of the part.

(2)Edgebreaker

The Edgebreaker method is a three-dimensional grid connection relation coding method and has the advantages of good compression performance, convenient implementation, capability of giving an upper limit of a compression ratio and the like. The Edgebreaker method only describes a compression method of the three-dimensional grid connection information, and the compression of the three-dimensional grid can be realized through geometric information compression, entropy coding and the like.

The Edgebreaker encoding technique can achieve 2 bits per triangle or less of compression efficiency on triangle meshes that are co-embryo with spheres. The encoding algorithm accesses each triangle of the mesh in depth-first order using five different modes (referred to as C, L, E, R and S). And marking each triangle according to the mode of the triangle, and generating CLERS character strings to obtain compact representation of the grid connection relation.

Five modes of the Edgebreaker method are shown in figure 1. The Edgebreaker method separates the mesh into a traversed portion and a non-traversed portion, the boundary of the two portions being referred to as the active boundary. In the encoding process of Edgebreaker, the triangle to be traversed is accessed through the active edge on the active boundary, and which mode is used is selected according to the relation between the active edge and the triangle in which it is located. The other vertex in the triangle where the active edge is located is referred to as the third vertex. If the third vertex is not on the active boundary, then the current triangle is marked as C-mode. If the third vertex is on the active boundary and, in a counter-clockwise order, is next to the currently active edge vertex, then the current triangle is marked as R-mode. If the third vertex is on the active boundary and, in a counter-clockwise order, is the last of the currently active edge vertices, then the current triangle is marked as L-mode. If the third vertex is on the active boundary and in a counter-clockwise order is both the last vertex of the currently active edge vertex and the next vertex of the currently active edge, then the current triangle is marked as E-mode. If the third vertex is on the active boundary, but in a counter-clockwise order, neither the last vertex of the currently active edge vertex nor the next vertex of the currently active edge, then the current triangle is marked as S-mode.

After each marking of a triangle, the active boundary is updated and the next active edge is selected according to certain rules. After traversing all triangles, entropy encoding is performed on the obtained CLERS character strings, so that higher compression efficiency can be obtained, and the final entropy encoded mode codeword is CCRRSLCRSERRELCRRRCRRRE according to the EB encoding rule.

Since the five modes of the Edgebreaker method cannot handle non-manifold grids, the grid must be converted to a manifold grid before the Edgebreaker method can be used.

The grid coding method, the grid decoding method and the related devices provided by the embodiment of the application are described in detail below through some embodiments and application scenarios thereof with reference to the accompanying drawings.

Referring to fig. 2, fig. 2 is a flowchart of a trellis encoding method provided by an embodiment of the present application, which may be applied to an encoding end device, as shown in fig. 2, the trellis encoding method includes the following steps:

and step 101, splitting the non-manifold structure in the grid to be coded to obtain non-manifold information and manifold grids.

The non-manifold structure may include a non-manifold edge and a non-manifold point, where the non-manifold point may also be described as a non-manifold vertex, and two vertices that form the non-manifold edge may also be described as non-manifold vertices.

Note that, manifold (manifield) is a space having a local euclidean space property. The general manifold may be formed by bending and bonding a plurality of flat sheets. The manifold satisfies the following conditions: locally having euclidean spatial properties, rather than a manifold may mean that the condition of the manifold is not met. For a three-dimensional grid, the manifold sides satisfy the following conditions: the grid edges are shared (EDGE IS INCIDENT to only one or two faces) for one or two grid triangular patches; the manifold point satisfies the following conditions: a ring of adjacent triangular plates of the grid vertices form a closed or open sector (THE FACES INCIDENT to a vertex form a closed or an open fan). Non-manifold sides may refer to grid sides that do not satisfy the conditions of manifold sides, and non-manifold points may refer to grid vertices that do not satisfy the conditions of manifold points.

In addition, the method for determining the non-manifold sides in the grid to be encoded may be that a data structure is established to store triangles where each side in the grid to be encoded is located, and the non-manifold sides are found out by querying the number of triangles corresponding to each side, where the number of triangles corresponding to the non-manifold sides is greater than or equal to 3; or, a correspondence between corners and edges in the grid is established by constructing CornerTable, and a non-manifold edge is found according to the correspondence, wherein the number of the corners corresponding to the non-manifold edge is greater than or equal to 3. Wherein CornerTable may be used to represent the relationship between corners and vertices in the mesh, as well as triangles.

In addition, the method for determining the non-manifold point in the grid to be encoded may be to construct CornerTable, establish a correspondence between each vertex in the grid to be encoded and the angle of the vertex, sequentially traverse all angles adjacent to the angle and forming a sector from one angle of the vertex, and mark the vertex and the traversed angle as traversed. If there are vertices for which there are no traversing angles after the process is performed, the vertex is indicated as a non-manifold point.

In addition, the splitting treatment of the non-manifold structure in the grid to be coded may be to establish repeated vertexes for the non-manifold vertexes in the grid to be coded, and adjust the connection relationship to convert the non-manifold structure into a manifold structure, where the non-manifold vertexes may include vertexes forming non-manifold edges and non-manifold points. Since a repeating vertex is created for the non-manifold vertex, the repeating vertex may be referred to as an added vertex, and the non-added vertex may be referred to as an original non-manifold vertex for convenience of description.

And 102, encoding the non-manifold information to obtain a first subcode stream.

The first subcode stream may also be described as a non-manifold information stream. The non-manifold information may include index information of original non-manifold vertices and index information of newly added vertices. When the first subcode stream is encoded, the corresponding relation between the newly added vertex and the original non-manifold vertex can be kept according to a certain rule. For example, the index information of the newly added vertex may be encoded in a staggered manner with the index information of the original non-manifold vertex; or the index information of the newly added vertex and the index information of the original non-manifold vertex can be respectively encoded into two paths of code streams according to the same sequence, and the corresponding relation between the newly added vertex and the original non-manifold vertex is kept through the encoding sequence. The specific encoding method for encoding non-manifold information is not limited in this embodiment.

And 103, encoding the manifold grids to obtain a second subcode stream.

The second subcode stream may include a geometric information code stream, an attribute information code stream, and a connection relationship information code stream. The geometric information of the manifold mesh can be encoded to obtain a geometric information code stream; the attribute information of the manifold grids can be encoded to obtain an attribute information code stream; and the connection relation information of the manifold grids can be encoded to obtain a connection relation information code stream.

Step 104, obtaining a grid coding result according to the first sub-code stream and the second sub-code stream.

Wherein the trellis encoding result may include the first sub-code stream and the second sub-code stream. The trellis encoding result may further include a texture map code stream obtained for encoding a texture map using a video encoder.

It should be noted that, the grid to be encoded may be a three-dimensional grid, as shown in fig. 3, and the procedure of the grid encoding method may be as follows: firstly, if a non-manifold structure exists in the three-dimensional grid, splitting the non-manifold structure to obtain a manifold grid, and simultaneously recording vertex information of newly added vertexes and vertex information of original non-manifold vertexes which are newly added due to splitting the non-manifold structure; then, encoding connection information by Edgebreaker method to obtain pattern character string and entropy encoding; the geometric information of the encoded grid after the connection relation encoding is completed, for example, a parallelogram prediction encoding method can be used, and the encoding method of the geometric information is not limited in this embodiment; if the grid has the attribute information such as UV coordinates, the grid can be encoded by using methods such as similar triangle predictive coding, and the encoding method of the attribute information is not limited in the embodiment; then, whether a non-manifold structure exists in the encoding grid is determined, if the non-manifold structure exists in the encoding grid, the index information of the newly added vertex and the index information of the original non-manifold vertex are encoded according to the encoding sequence of the geometric information and the attribute information, and the geometric index information and the attribute index information of the newly added vertex and the corresponding original non-manifold vertex can be directly entropy encoded. And finally, encoding the texture map by using a video encoder, and mixing all paths of sub-code streams to obtain the encoded code streams of the grid.

Note that Edgebreaker needs to have a manifold structure for the mesh to be encoded, and Draco needs to split the mesh with a non-manifold structure into manifold structures for the mesh to be encoded correctly. However, draco does not combine the split structure at the decoding end, so that the grid output by the decoding end can be more than the split point compared with the original grid input by the encoding end, and Draco cannot encode the grid with non-manifold structure in a lossless manner.

With the increasing demand of three-dimensional grid models in visual effect and the advent of many more sophisticated three-dimensional scanning techniques and three-dimensional modeling software, the data size and complexity of three-dimensional grid models obtained by three-dimensional scanning devices or three-dimensional modeling software have also increased dramatically. Therefore, how to efficiently compress three-dimensional mesh data is a key to achieve convenient transmission, storage, and processing of three-dimensional mesh data.

A three-dimensional grid often contains three main information, namely topology information, geometric information and attribute information. Topology information, also called connectivity relationship information, is used to describe the connection relationship between elements such as vertices and patches in the mesh; the geometric information is the three-dimensional coordinates of all vertices in the mesh; the attribute information records other information attached to the grid, such as normal vectors, texture coordinates, colors, etc. The compression of three-dimensional grid data is often performed on the three kinds of information according to the data characteristics of the three kinds of information. In addition, for three-dimensional meshes with texture maps, the texture maps need to be compressed.

In the three-dimensional grid coding framework in the related art, the three-dimensional grid coding framework mainly comprises a grid preprocessing module, a basic grid coding module, a video-based displacement information coding module, a texture map coding module and the like. Wherein, the basic grid coding module adopts Draco to code. Draco is a library for compressing and decompressing 3D geometric meshes and point clouds, aiming at improving the storage and transmission of 3D graphics, and greatly accelerating the encoding, transmission and decoding of 3D data. Draco support compression of three-dimensional mesh geometry information, connection information, and attribute information. Draco support a lossy mode and a near lossless mode. Draco the Edgebreaker method used in encoding connection relationships is one of the most efficient methods for encoding three-dimensional mesh connection information.

Optionally, the mesh to be encoded includes a first manifold mesh and a first non-manifold mesh, the first manifold mesh and the first non-manifold mesh are connected through the non-manifold structure, the non-manifold structure includes a first vertex, and splitting the non-manifold structure in the mesh to be encoded includes:

Establishing a second vertex, wherein the second vertex and the first vertex are repeated points, and the index information of the second vertex and the index information of the first vertex are different;

splitting the non-manifold structure in the grid to be coded based on the second vertex to convert the first non-manifold grid into a second manifold grid;

Wherein the non-manifold information includes index information of the first vertex and index information of the second vertex, and the manifold mesh includes the first manifold mesh and the second manifold mesh.

The first vertex is a non-manifold vertex (may also be referred to as an original non-manifold vertex), and the first vertex may be a vertex constituting a non-manifold edge or may be a non-manifold point. The non-manifold structure may include a non-manifold edge, which may be shared by the first manifold mesh and the first non-manifold mesh; alternatively, the non-manifold structure may include non-manifold points that may be shared by the first manifold mesh and the first non-manifold mesh.

In addition, index information of a first vertex in the connection relation of the first non-manifold mesh can be updated to index information of the second vertex, so that the first non-manifold mesh does not comprise the first vertex any more, and the first non-manifold mesh can be converted into the second manifold mesh.

In this embodiment, a second vertex is established, where the second vertex and the first vertex are repetition points, and index information of the second vertex and index information of the first vertex are different; splitting the non-manifold structure in the grid to be coded based on the second vertex to convert the first non-manifold grid into a second manifold grid; wherein the non-manifold information includes index information of the first vertex and index information of the second vertex, and the manifold mesh includes the first manifold mesh and the second manifold mesh. Therefore, the non-manifold structure in the grid to be encoded can be split, the non-manifold structure in the grid to be encoded is converted into the manifold structure, and index information of newly added vertexes is recorded, so that the non-manifold structure can be conveniently reconstructed during decoding.

Optionally, the non-manifold information further includes a non-manifold identifier;

The first sub-code stream comprises a code stream corresponding to the non-manifold identifier, a code stream corresponding to the index information of the second vertex and a code stream corresponding to the index information of the first vertex;

And in the first sub-code stream, the code stream corresponding to the non-manifold mark, the code stream corresponding to the index information of the second vertex and the code stream corresponding to the index information of the first vertex have an association relation.

Wherein the non-manifold identification may be used to identify the non-manifold structure. And encoding the non-manifold mark to obtain a code stream corresponding to the non-manifold mark. For example, entropy encoding may be performed on the non-manifold identifier, so as to obtain a code stream corresponding to the non-manifold identifier. And encoding the index information of the second vertex to obtain a code stream corresponding to the index information of the second vertex. For example, the index information of the second vertex may be entropy encoded, to obtain a code stream corresponding to the index information of the second vertex. The index information of the first vertex can be encoded to obtain a code stream corresponding to the index information of the first vertex. For example, the index information of the first vertex may be entropy encoded, to obtain a code stream corresponding to the index information of the first vertex.

In addition, when the first subcode stream is encoded, the correspondence relationship among the non-manifold mark, the first vertex and the second vertex can be maintained according to a certain rule. Taking the example of maintaining the corresponding relationship between the first vertex and the second vertex, the index information of the second vertex and the index information of the first vertex may be encoded in a staggered manner, so that an association relationship exists between the code stream corresponding to the index information of the first vertex and the code stream corresponding to the index information of the second vertex. Or the index information of the second vertex and the index information of the first vertex can be respectively encoded into two paths of code streams according to the same sequence, and the code streams corresponding to the index information of the first vertex and the code streams corresponding to the index information of the second vertex have an association relation through the encoding sequence.

In this embodiment, the non-manifold information further includes a non-manifold identifier; the first sub-code stream comprises a code stream corresponding to the non-manifold identifier, a code stream corresponding to the index information of the second vertex and a code stream corresponding to the index information of the first vertex; in the first subcode stream, the association relationship exists among the code stream corresponding to the non-manifold identifier, the code stream corresponding to the index information of the second vertex and the code stream corresponding to the index information of the first vertex, so that the index information of the second vertex can be updated to the index information of the first vertex based on the association relationship during decoding, and the first vertex and the second vertex are combined to reconstruct the non-manifold structure.

Optionally, the index information of any one of the first vertex and the second vertex includes geometric index information and attribute index information, the geometric index information represents the position of the vertex in a geometric information coding sequence, and the attribute index information represents the position of the vertex in an attribute information coding sequence;

the first subcode stream comprises a code stream corresponding to the geometric index information and a code stream corresponding to the attribute index information.

The geometric index information may be encoded to obtain a code stream corresponding to the geometric index information. For example, entropy coding may be performed on the geometric index information to obtain a code stream corresponding to the geometric index information. And encoding the attribute index information to obtain a code stream corresponding to the attribute index information. For example, entropy coding may be performed on the attribute index information to obtain a code stream corresponding to the attribute index information.

In this embodiment, the index information of any one of the first vertex and the second vertex includes geometric index information and attribute index information, where the geometric index information indicates a position of the vertex in a geometric information coding order, and the attribute index information indicates a position of the vertex in an attribute information coding order; the first subcode stream comprises a code stream corresponding to the geometric index information and a code stream corresponding to the attribute index information. In this way, the index information of the newly added vertex and the original non-manifold vertex can be encoded in the geometric encoding dimension and the attribute encoding dimension respectively by the geometric index information and the attribute index information.

Optionally, the splitting processing of the non-manifold structure in the mesh to be encoded based on the second vertex includes:

Updating index information of a first vertex in first connection relation information to index information of the second vertex, wherein the first connection relation information is used for representing connection relation of the vertices of the first non-manifold mesh.

When the first vertex is a vertex forming a non-manifold edge, a second vertex can be respectively created for two vertices of the non-manifold edge, the second vertex is a repeated vertex of the first vertex, a triangle t where the non-manifold edge is located is selected, the selected triangle is a triangle corresponding to the first non-manifold grid, index information of the first vertex in the first connection relation information is updated to index information of the second vertex, a new triangle t 'is formed by a third vertex in the triangle and the newly added two vertices, and the original triangle t is replaced by t', so that the non-manifold edge is converted into the manifold edge. When the first vertex is a non-manifold point, a second vertex can be created, a triangle where the non-manifold point is located is selected, the selected triangle is a triangle corresponding to the first non-manifold mesh, index information of the first vertex in the first connection relation information is updated to index information of the second vertex, and the non-manifold point is split into two manifold vertices.

In this embodiment, the index information of the first vertex in the first connection relationship information is updated to the index information of the second vertex, where the first connection relationship information is used to characterize the connection relationship of the vertices of the first non-manifold mesh, so that the non-manifold structure can be split, and the non-manifold structure is converted into the manifold structure.

Optionally, the encoding the manifold mesh to obtain a second subcode stream includes:

Encoding the geometric information of the manifold grids to obtain a geometric information code stream;

encoding the attribute information of the manifold grids to obtain attribute information code streams;

Encoding the second connection relation information of the manifold grids to obtain a connection relation information code stream;

The second subcode stream comprises the geometric information code stream, the attribute information code stream and the connection relation information code stream, the second connection relation information is used for representing the connection relation of the vertexes of the manifold grids, and the second connection relation information comprises the updated first connection relation information.

The geometric information code stream may be obtained by encoding geometric information of the manifold mesh, and the encoded geometric information may be a difference predictive encoding algorithm, a parallelogram predictive encoding algorithm, a multi-parallelogram predictive encoding algorithm, or the like, which is not limited in this embodiment. The attribute information code stream may be obtained by encoding attribute information of the manifold mesh, and the encoding attribute information may be a difference predictive encoding algorithm, or a parallelogram predictive encoding algorithm, or a similar triangle predictive encoding algorithm, etc., which is not limited in this embodiment. The connection information code stream may be obtained by encoding the second connection information, for example, the second connection information of the manifold mesh may be encoded using Edgebreaker method, the connection of the mesh is represented by establishing CornerTable, and all triangles in the mesh are traversed by CornerTable to generate CLERS mode strings of Edgebreaker.

In the embodiment, the geometric information of the manifold grid is encoded to obtain a geometric information code stream; encoding the attribute information of the manifold grids to obtain attribute information code streams; encoding the second connection relation information of the manifold grids to obtain a connection relation information code stream; the second subcode stream comprises the geometric information code stream, the attribute information code stream and the connection relation information code stream, the second connection relation information is used for representing the connection relation of the vertexes of the manifold grids, and the second connection relation information comprises the updated first connection relation information. Therefore, the connection relation of the non-manifold structure does not exist in the connection relation information code stream obtained by encoding, and the Edgebreaker algorithm is convenient to encode the grid.

In one embodiment, a trellis encoding method may be applied to an encoding end, and the trellis encoding method may include the following processes:

1) Splitting non-manifold points and non-manifold edges which may exist in the grid, converting the grid into a plurality of manifold grids, and recording newly added vertices and original non-manifold vertices which are newly added due to the splitting of the non-manifold structure. Determining whether a non-manifold structure exists in the coding grid, and if the non-manifold structure exists in the coding grid, coding the corresponding relation between the newly added vertex and the original non-manifold vertex generated by splitting the non-manifold structure to obtain a non-manifold information code stream;

2) Coding the connection relation by using Edgebreaker method to obtain CLERS mode character string capable of simply representing the connection relation, and compressing the mode character string by using entropy coding to obtain connection relation information code stream;

3) Geometric information of the grid is encoded by using a method such as parallelogram prediction, and if attribute information such as UV coordinates exists in the grid, the UV coordinates of the grid are encoded by using a method such as similar triangle prediction, so that an attribute information code stream is obtained.

4) Encoding the texture map by using a video encoder to obtain a texture map code stream;

5) And merging the sub-code streams to obtain the code stream of the grid.

As a specific embodiment, the trellis encoding method may be applied to the encoding side. The coding end can be divided into five parts: the device comprises a split non-manifold structure module, a connection relation coding module, a geometric information coding module, an attribute information coding module and a non-manifold vertex information coding module, wherein the non-manifold vertex information coding module codes a non-manifold mark and codes non-manifold vertex index information. The following description will be made respectively:

(1) Split non-manifold structural module

Input: original grid

And (3) outputting: manifold mesh, original non-manifold vertex and newly added vertex

Wherein the split non-manifold structure module can be used to split non-manifold structures. The split non-manifold structure is mainly divided into two parts: splitting non-manifold sides and splitting non-manifold points.

The first step in splitting the non-manifold sides is to find the non-manifold sides. The non-manifold edge is judged if one edge exists in three or more triangles at the same time. The specific implementation method comprises the following steps: a data structure is established to store triangles where each edge is located, and non-manifold edges are found out by inquiring the number of the triangles corresponding to the edge; the correspondence between corners and edges in the mesh may also be established by constructing CornerTable to find non-manifold edges. Specifically, for a manifold grid, each edge is at most opposite two corners, the opposite two corners being referred to as diagonal. As shown in fig. 4, angle a is opposite to angle d from side bc, angle a being diagonal to angle d; while for non-manifold sides there may be three or more diagonals. Therefore, the non-manifold sides can be found out through the corresponding relation between the corners and the sides.

The second step in splitting the non-manifold edges is to add vertices and modify the connection relationships. After the non-manifold edge is found, repeated vertexes are respectively created for the two vertexes of the non-manifold edge, one triangle t where the non-manifold edge is located is selected, a new triangle t 'is formed by a third vertex in the triangle and the newly added two vertexes, the original triangle t is replaced by t', and the process is iterated until the non-manifold edge is converted into the manifold edge. The newly added vertex is the newly added vertex, and simultaneously, the index information of the newly added vertex and the index information of the original non-manifold vertex in the process are recorded.

Splitting non-manifold points first requires construction CornerTable, establishing a correspondence between each vertex and the corner of that vertex. A two-step operation is performed for each vertex. In the first step, all angles adjacent to a certain angle of the vertex and forming a sector are sequentially traversed, and the vertex and the traversed angle are marked as traversed. If there are vertices for which there are no traversing angles after the process is performed, the vertex is indicated as a non-manifold point. And secondly, for each non-manifold point, creating a repeated point, modifying the connection relation, connecting the angles which are not traversed in the first step to the newly added repeated points, and splitting the non-manifold point into two manifold vertexes. This process is repeated until all vertices are converted to manifold points. The created point is the newly added vertex, and simultaneously, the index information of the newly added vertex and the index information of the original non-manifold vertex in the process are recorded.

In addition, a non-manifold logo is provided for the grid where the non-manifold structure exists.

(2) Connection relation coding module

Input: connection relation of manifold grids

And (3) outputting: connection relation information code stream and vertex coding sequence

Wherein the vertex coding order may also be referred to as vertex traversal order. The present embodiment may encode the connection of the three-dimensional mesh using Edgebreaker method, represent the connection of the mesh by creating CornerTable, and traverse all triangles in the mesh with CornerTable to generate the CLERS pattern string of Edgebreaker.

CornerTable are used to represent the relationship between corners and vertices in the mesh and triangles. The triangles need to be numbered first diagonally before CornerTable is built, traversing the triangles in the order of the triangle patches in the mesh, and for each triangle, the angles are numbered in a counter-clockwise order, if the mesh has f triangle patches, then the mesh will have 3f angles. The advantage of such numbering is that the triangle number where the current angle is can be calculated by the number of the angle, and the calculation mode is as follows;

f_i＝c/3

Where c is the index of the current angle, f _i is the sequence number of the triangle in which the current angle c is located, "/" is the integer division, and the result is rounded down.

In addition, the sequence numbers of the previous angle c _p and the next angle c _n of the current angle c in the counterclockwise direction can be calculated, and the calculation mode of the previous angle is as follows:

c_p＝(f_i*3)+(c-1)％3

Wherein c is the index of the current angle, f _i is the sequence number of the triangle where the current angle c is located, "x" is multiplication, and "%" is modulo operation.

The latter angle is calculated as follows:

c_n＝(f_i*3)+(c+1)％3

CornerTable comprises four parts: the tables are V table, O table, U table and M table. Wherein, the V table stores the vertex index corresponding to each angle, the O table stores the diagonal index of each angle, the U table stores the mark whether each triangle is traversed in the traversing process, and the M table stores the mark whether each vertex is traversed in the traversing process.

Using CornerTable, a relationship as shown in fig. 5 can be constructed, where c represents the current angle, c.p represents the previous angle (in a counter-clockwise direction) of the current angle c, and c.n represents the next angle of the current angle c. c.o is the diagonal of the current angle c, which can be obtained by looking up an O table. And c.t is the sequence number of the triangle where c is located, and can be calculated by the formula 1. c.v denotes the vertex of the current angle, which can be found by looking up the V table. c.l denotes the angle to the left of the current angle c, obtained by looking up the diagonal angle of c.p in the O table; c.r denotes the angle to the right of the current angle c, obtained by looking up the diagonal angle of c.n in the O table.

After the relationships between the angles and the vertices and triangles are constructed using CornerTable, the mesh can be traversed in a spiral order to obtain a CLERS pattern string of Edgebreaker representing the mesh connection relationships. At this time, the judgment conditions and the traversal rules of the five modes are shown in fig. 6. The angle of current traversal is x, if the vertex x.v corresponding to x is not accessed, the current triangle is in C mode, and the triangle to be traversed next is the triangle where x.r is located; otherwise, if the triangle where x.1 is located is accessed, the current triangle is in L mode, and the triangle to be traversed next is the triangle where x.r is located; if the triangle where x.r is located is accessed, the current triangle is in R mode, and the next triangle to be traversed is the triangle where x.l is located; if the vertex x.v is accessed but neither the triangle where x.l nor the triangle where x.r is located is accessed, then the current triangle is in S mode, and the traversal path generates two branches at this time, and the depth-first traversal principle is adopted, the traversed triangle is the triangle where x.r is located first, and the triangle where x.l is located is stored in the stack, and after the traversal of the branch where x.r is located is waited, the triangle where x.l is located is traversed again; if the triangles where x.1 and x.r are located are all accessed, the current triangle mode is E, and the current traversal path branches to the end point.

An initial triangle is randomly selected in the grid, the triangle in the grid is traversed according to the rule, and CLERS-mode character strings are generated. When the traversal path is terminated, but the grid still exists as a traversed triangle, a non-traversed triangle is randomly selected and the next traversal is started until all the triangles in the grid are traversed.

And compressing CLERS mode character strings by using entropy coding to obtain a final connection information code stream.

(3) Geometric information coding module

Input: geometric information and connection relation coding sequence of manifold grids

And (3) outputting: geometric information code stream and geometric information coding sequence

The geometric information encoding module may encode geometric information by using various methods, such as a difference predictive encoding algorithm, a parallelogram predictive encoding algorithm, a multi-parallelogram predictive encoding algorithm, etc., where specific encoding methods are not emphasized. Taking the parallelogram predictive coding algorithm as an example: there are a, b, c, d vertices that make up two adjacent triangles in the mesh as shown in fig. 7.

Wherein, the geometric information of the points a, b and c is encoded, the geometric information of the point d is to be encoded, and the formula for calculating the predicted value d' of the geometric coordinates of the point d is as follows:

d′(x，y，z)＝b(x，y，z)+c(x，y，z)-a(x，y，z)

After d 'is obtained, calculating the difference between the three-dimensional coordinates of d' and d points:

Δd(x，y，z)＝d(x，y，z)-d′(x，y，z)

And performing entropy coding on the delta d to obtain a code stream of the geometric information.

For triangles that cannot be predicted using parallelograms, such as triangles at the mesh boundaries, the difference coding method is used to encode the geometric information. I.e. using the coordinate values of neighboring coded vertices as predictors of the current vertex coordinates, a residual is calculated and predicted.

(4) Attribute information coding module

Input: attribute information and connection relation coding sequence of manifold mesh

And (3) outputting: attribute information code stream and attribute information coding sequence

The attribute information of the three-dimensional grid generally includes UV coordinates, normal vectors, and the like, and the UV coordinates are taken as an example. There are a number of coding methods that may be employed for UV coordinates, including differential predictive coding, parallelogram predictive coding, and similar triangle predictive coding, and the like, and specific coding methods are not emphasized here. The similar triangle prediction algorithm is described below.

Firstly, selecting a triangle in a three-dimensional grid as an initial triangle, directly encoding UV coordinates without predicting three vertexes of the initial triangle, and storing edges of the initial triangle into an edge set, wherein the set can be a data structure meeting a certain access criterion. The edges τ in one set are then fetched, predicting the pair-vertex UV coordinates of τ in the next new triangle. And placing two sides of the new triangle other than τ into the collection. The point to be predicted is marked as a point C, two end points of the side tau are respectively N and P, the vertex of a triangle pair adjacent to the new triangle through tau is marked as 0, and the projection point of C on tau is marked as X. As shown in fig. 8, since the UV coordinates of the three points N, P,0 are encoded before the C point, the UV coordinates of the C point can be predicted using the three points. The specific calculation flow is as follows:

let C _uv,X_uv,N_uv,P_uv,O_uv be the UV coordinates of each point and C _G,X_G,N_G,P_G,O_G be the geometric coordinates of each point. First, the UV coordinates of point X are calculated:

Calculating vectors Rotated () represents a 90 degree flip of the vector:

Finally, calculating a C point predicted UV coordinate Pred _c:

and after obtaining the predicted value of the UV coordinates, subtracting the predicted value from the original UV coordinates to obtain a residual value.

The encoding UV coordinates steps are as follows:

(41) And selecting an initial triangle from the connectivity relation, and directly encoding UV coordinates of three vertexes of the initial triangle without prediction. The initial triangle edge is stored in an edge set.

(42) And selecting the side tau from the set according to the access criterion, and encoding the UV coordinates of the new triangle formed by tau on the vertex. And calculating the predicted value of the point to be coded according to the UV coordinate predicted value calculation process by utilizing the three-dimensional to two-dimensional projection relation of the triangle. Subtracting the predicted value from the original value of the UV coordinates to obtain a residual error.

(43) Adding two sides of the new triangle into the side set, and removing the side tau at the top of the set. And (3) taking out the next edge from the set, continuing to encode the UV coordinates of the pair of vertexes of the adjacent triangle of the edge, and returning to the step (3) until the UV coordinates of all vertexes are encoded.

(44) Entropy coding UV coordinate residual errors and outputting UV coordinate code streams.

(5) Non-manifold vertex index coding module

Input: index information of newly added vertex, index information of original non-manifold vertex, coding sequence of geometric information and coding sequence of attribute information

And (3) outputting: non-manifold information code stream

The non-manifold vertex index information comprises newly added vertex index information and original non-manifold vertex index information.

Firstly, determining whether a non-manifold structure exists in the coding grid, for example, if the non-manifold structure does not exist in the coding grid, namely, the number of newly added vertexes is 0, setting the non-manifold mark to 0, and no newly added vertex information is needed to be coded; if the non-manifold structure exists in the coding grid, namely the number of newly added vertexes is larger than 0, the non-manifold mark is set to be 1, and then the index information of the newly added vertexes and the index information of the corresponding original non-manifold vertexes are coded. During encoding, the corresponding relation between the newly added vertex and the original non-manifold vertex is required to be maintained according to a certain rule. For example, the index information of the newly added vertex may be encoded in a staggered manner with the index information of the original non-manifold vertex; the index information of the newly added vertex and the index information of the original non-manifold vertex can be respectively encoded into two paths of code streams according to the same sequence, and the corresponding relation between the newly added vertex and the original non-manifold vertex is kept through the encoding sequence. The embodiment is not limited to a specific implementation of maintaining the correspondence between the newly added vertex and the original non-manifold vertex.

In addition, the non-manifold vertex index information comprises geometric vertex index information and attribute vertex index information. Optionally, encoding non-manifold vertex index information is mainly divided into two steps: the first step is to record the position of the geometric vertex in the geometric information coding sequence and the position of the attribute vertex in the attribute information coding sequence; and the second step is to perform entropy coding on the geometric information position of the geometric vertex and the attribute information position of the attribute vertex to obtain a non-manifold information code stream. Here, in addition to directly entropy encoding index information of non-manifold vertices, when the newly added vertex corresponds to the original non-manifold vertex one by one, an identifier for indicating whether the vertex is the newly added vertex and an identifier for indicating whether the vertex is the original non-manifold vertex may be encoded to represent a correspondence between the newly added vertex index information and the non-manifold vertex index information. The present embodiment is not limited to a specific encoding scheme.

The non-manifold information code stream comprises a non-manifold mark and non-manifold vertex index information.

In addition, the non-manifold information code stream can have a plurality of storage modes in the total code stream: one is to take the non-manifold information code stream as a single sub-code stream; the other is to store the code stream of the index information of the non-manifold geometric vertex into the geometric information code stream, and store the code stream of the index information of the non-manifold attribute vertex into the attribute information code stream; or the code stream of the index information of the non-manifold geometric vertex and the code stream of the index information of the non-manifold attribute vertex can be respectively stored in the total code stream as two paths of sub-code streams. The storage mode of the non-manifold information code stream in the total code stream is not limited in this embodiment.

And finally, mixing all the sub-code streams to form a grid coding code stream.

Referring to fig. 9, fig. 9 is a flowchart of a trellis decoding method according to an embodiment of the present application, which may be applied to a decoding side device, and as shown in fig. 9, the trellis decoding method includes the following steps:

step 201, obtaining a first sub-code stream and a second sub-code stream according to a grid coding result of a grid to be decoded;

Step 202, decoding the first subcode stream to obtain non-manifold information;

step 203, decoding the second subcode stream to obtain a manifold grid;

and 204, reconstructing the manifold grid based on the non-manifold information to obtain a decoding grid.

In the embodiment of the application, a first subcode stream and a second subcode stream are obtained according to a grid coding result of a grid to be decoded; decoding the first subcode stream to obtain non-manifold information; decoding the second subcode stream to obtain a manifold grid; and reconstructing the manifold grid based on the non-manifold information to obtain a decoding grid. Therefore, the manifold grid is reconstructed based on the non-manifold information, and the non-manifold structure can be reconstructed through the non-manifold information, so that the quality loss of grid information after encoding and decoding processing can be reduced or even eliminated, and lossless encoding is realized.

Optionally, the non-manifold information includes index information of a first vertex and index information of a second vertex, the second vertex being different from the index information of the first vertex;

the reconstructing the manifold grid based on the non-manifold information to obtain a decoding grid comprises the following steps:

Reconstructing the manifold mesh based on the index information of the first vertex and the index information of the second vertex to obtain a decoding mesh;

The manifold grids comprise a first manifold grid and a second manifold grid, the grids to be decoded comprise the first manifold grid and a first non-manifold grid, the first manifold grid and the first non-manifold grid comprise non-manifold structures, the non-manifold structures comprise the first vertexes, and the first non-manifold grid is obtained by converting the second manifold grid.

In this embodiment, the manifold mesh is reconstructed based on the index information of the first vertex and the index information of the second vertex, so as to obtain a decoding mesh; the manifold grids comprise a first manifold grid and a second manifold grid, the grids to be decoded comprise the first manifold grid and a first non-manifold grid, the first manifold grid and the first non-manifold grid comprise non-manifold structures, the non-manifold structures comprise the first vertexes, and the first non-manifold grid is obtained by converting the second manifold grid, so that the non-manifold structures can be rebuilt during decoding.

Optionally, the first sub-code stream includes a code stream corresponding to the non-manifold identifier, a code stream corresponding to the index information of the second vertex, and a code stream corresponding to the index information of the first vertex;

the non-manifold information further comprises a non-manifold identifier, and in the non-manifold information, an association relationship exists among the non-manifold identifier, the index information of the second vertex and the index information of the first vertex.

In this embodiment, the first subcode stream includes a code stream corresponding to the non-manifold identifier, a code stream corresponding to index information of the second vertex, and a code stream corresponding to index information of the first vertex; the non-manifold information further comprises a non-manifold identifier, and in the non-manifold information, an association relationship exists among the non-manifold identifier, the index information of the second vertex and the index information of the first vertex. In this way, the index information of the second vertex can be updated to the index information of the first vertex based on the association relationship, so that the first vertex and the second vertex can be combined, and the non-manifold structure can be reconstructed.

Optionally, the first subcode stream includes a code stream corresponding to the geometric index information and a code stream corresponding to the attribute index information;

The index information of any one of the first vertex and the second vertex comprises geometric index information and attribute index information, wherein the geometric index information represents the position of the vertex in a geometric information coding sequence, and the attribute index information represents the position of the vertex in an attribute information coding sequence.

In this embodiment, the first subcode stream includes a code stream corresponding to geometric index information and a code stream corresponding to attribute index information; the index information of any one of the first vertex and the second vertex comprises geometric index information and attribute index information, wherein the geometric index information represents the position of the vertex in a geometric information coding sequence, and the attribute index information represents the position of the vertex in an attribute information coding sequence. In this way, the code streams corresponding to the index information of the newly added vertex and the original non-manifold vertex can be decoded in the geometric decoding dimension and the attribute decoding dimension respectively by the geometric index information and the attribute index information.

Optionally, the second subcode stream includes a geometric information code stream, an attribute information code stream and a connection relationship information code stream, where the geometric information code stream is a code stream corresponding to geometric information of the manifold mesh, the attribute information code stream is a code stream corresponding to attribute information of the manifold mesh, and the connection relationship information code stream is a code stream corresponding to second connection relationship information of the manifold mesh, and the second connection relationship information is used to characterize a connection relationship of vertices of the manifold mesh;

The manifold grid is obtained by constructing a grid based on geometric information of the manifold grid, attribute information of the manifold grid and the second connection relation information.

In this embodiment, the second subcode stream includes a geometric information code stream, an attribute information code stream and a connection relationship information code stream, where the geometric information code stream is a code stream corresponding to geometric information of the manifold mesh, the attribute information code stream is a code stream corresponding to attribute information of the manifold mesh, and the connection relationship information code stream is a code stream corresponding to second connection relationship information of the manifold mesh, where the second connection relationship information is used to characterize a connection relationship of vertices of the manifold mesh; the manifold grid is obtained by constructing a grid based on geometric information of the manifold grid, attribute information of the manifold grid and the second connection relation information. Therefore, the connection relation of the non-manifold structure does not exist in the connection relation information code stream, and the Edgebreaker algorithm is convenient to encode the grid.

Optionally, the reconstructing the manifold mesh based on the index information of the first vertex and the index information of the second vertex to obtain a decoding mesh includes:

Updating the index information of the second vertex in the second connection relation information to the index information of the first vertex, and carrying out reconstruction processing on the manifold mesh to obtain a decoding mesh.

In this embodiment, the index information of the second vertex in the second connection relationship information is updated to the index information of the first vertex, and the manifold mesh is reconstructed to obtain a decoding mesh, so that the non-manifold structure in the mesh can be recovered, and the reconstruction of the non-manifold mesh can be realized.

It should be noted that, as an implementation manner of the decoding side corresponding to the embodiment shown in fig. 3, a specific implementation manner of the embodiment may refer to a related description of the embodiment shown in fig. 3, so that in order to avoid repeated description, the embodiment is not described again, and the same beneficial effects may be achieved.

At the decoding end, the code stream to be decoded can be decomposed to obtain each sub-code stream. The trellis decoding method may include the following processes:

1) Entropy decoding the connection relation information code stream to obtain CLERS mode character strings, and reconstructing the connection relation by using the mode character strings.

2) Decoding the geometric information code stream, and decoding the geometric information of the grid by using methods such as parallelogram inverse prediction and the like;

3) And decoding the attribute information code stream, and decoding UV coordinates of the grid by using methods such as similar triangle reverse prediction and the like.

4) The non-manifold information code stream is decoded, and whether the grid has a non-manifold identification is determined. If the non-manifold structure exists in the grid, if the non-manifold mark exists in the grid, further decoding to obtain index information of the newly added vertex and index information of the original non-manifold vertex corresponding to the newly added vertex, combining the newly added vertex and the original non-manifold vertex, adjusting the connection relation, recovering the non-manifold structure in the grid, and completing lossless encoding and decoding of the grid containing the non-manifold structure.

5) And decoding the texture map code stream to obtain a final three-dimensional grid.

When encoding a mesh having a non-manifold structure, the encoding end can perform mesh splitting and the decoding end can perform mesh merging to perform lossless encoding on the non-manifold mesh using Edgebreaker.

It should be noted that, as shown in fig. 10, the code stream to be decoded may be decomposed into a geometric information code stream, a connection relationship information code stream, an attribute information code stream, a non-manifold information code stream, and a texture map code stream. These code streams may be decoded separately. Firstly, entropy decoding a connection relation information code stream to obtain a mode character string and reconstructing a connection relation; then, decoding the geometric information code stream by using a decoding method corresponding to the encoding end; then, decoding UV coordinates of the grid using a decoding method corresponding to the encoding end; then, decoding the non-manifold information code stream, determining whether a grid has a non-manifold identifier, if the grid has the non-manifold identifier, further decoding to obtain index information of newly added vertexes and index information of original non-manifold vertexes corresponding to the newly added vertexes, merging the newly added vertexes with the original non-manifold vertexes, adjusting a connection relation, recovering a non-manifold structure in the grid, and finishing lossless encoding and decoding of the grid with the non-manifold structure; and finally, decoding the texture map code stream, and reconstructing a three-dimensional grid by using each path of decoding information.

As a specific embodiment, the trellis decoding method may be applied to the decoding side. The decoding end can be divided into six parts: the device comprises a connection relation decoding module, a geometric information decoding module, an attribute information decoding module, a non-manifold vertex information decoding module, a manifold mesh reconstruction module and a non-manifold structure recovery module. The following description will be made respectively:

(1) Connection relation decoding module

Input: connection relation information code stream

And (3) outputting: connection relation of manifold grids and decoded vertex traversing sequence

The connection relation decoding module decodes the connection relation information code stream to obtain a mode character string. Traversing the pattern character strings according to a certain vertex traversing sequence (positive sequence or reverse sequence), and reconstructing connection relations according to corresponding patterns in the pattern character strings. In addition, the vertex traversal order is output to the geometry information decoding module and the attribute information decoding module.

(2) Geometric information decoding module

Input: decoding sequence of geometric information code stream and connection relation

And (3) outputting: geometric information of manifold mesh.

The decoding process of the grid geometry is the inverse of the encoding process: entropy decoding is carried out to obtain a coordinate prediction residual. And predicting the predicted coordinates of the point to be decoded according to the parallelogram rule according to the decoded triangle. And adding the residual error value obtained by entropy decoding to the predicted coordinate to obtain the position of the geometric coordinate to be decoded. The vertex traversal order in the decoding process is the same as the vertex traversal order of the encoded geometry information. Note that the geometric coordinates of the initial triangles are not encoded using prediction, but rather their geometric coordinates are directly encoded. And after the decoding end decodes the geometric coordinates of the triangle, the geometric coordinates of vertexes of other triangles are traversed and decoded as the initial triangle. In addition, other decoding methods may be used herein, and specific decoding methods are not emphasized as long as they correspond to the encoding end.

(3) Attribute information decoding module

Input: decoding sequence of attribute information code stream and connection relation

And (3) outputting: attribute information of the manifold mesh.

Taking UV coordinates as an example, the decoding method adopts a decoding method corresponding to the encoding end, and specific decoding methods are not emphasized here. The decoding process of decoding using the similar triangle prediction algorithm is described below.

The decoding UV coordinates process is as follows:

(31) Entropy decoding the UV coordinate code stream.

(32) The UV coordinates of the three vertices of the initial triangle are decoded in vertex traversal order, where no predictors are calculated, the initial triangle is directly encoded with its UV coordinates rather than with the residuals. The initial triangle edge is stored in an edge set.

(33) And selecting the side tau from the set according to the access criterion, and decoding the UV coordinates of the new triangle formed by the side tau on the vertex. Firstly, calculating the UV coordinate predicted value of the point to be decoded by using a three-dimensional to two-dimensional mapping relation of the triangle and a calculation mode consistent with the coding end. And adding the predicted value and the residual error decoded by the entropy to obtain the reconstructed UV coordinate.

(34) Adding two sides of the new triangle into the side set, and removing the side tau at the top of the set. The next edge is taken out of the set, the UV coordinates of the vertices of the adjacent triangle of the edge continue to be decoded, and the step (33) is returned until the UV coordinates of all the vertices are decoded.

(4) Non-manifold vertex information decoding module

Input: non-manifold information code stream, geometric information decoding sequence and attribute information decoding sequence

And (3) outputting: non-manifold identification, newly added vertex index information and original non-manifold vertex index information

Firstly, decoding a non-manifold information code stream to obtain a non-manifold mark and non-manifold vertex index information. The non-manifold mark is used for marking whether a non-manifold structure exists in the grid, if the non-manifold mark is 0, non-manifold vertex index information does not need to be decoded, and the non-manifold structure does not need to be restored; if the non-manifold label is 1, the non-manifold vertex index information is decoded.

The non-manifold vertex index information is decoded by adopting a method corresponding to the encoding end, firstly, the non-manifold vertex index information is entropy decoded, the positions of the non-manifold vertices in the geometric decoding order and the attribute decoding order are obtained based on the entropy decoding result, the geometric information decoding order and the attribute information decoding order, and then the index information of the non-manifold vertices at the decoding end is recorded, so that newly added vertex index information and original non-manifold vertex index information are obtained. And inputting the newly added vertex index information and the original non-manifold vertex index information into a non-manifold restoration structure module.

(5) Reconstruction manifold grid module

Input: connection relation of manifold grids, geometric information of manifold grids, and attribute information of manifold grids

And (3) outputting: manifold grid

The manifold grids can be directly reconstructed by utilizing the connection relation, the geometric information and the attribute information of the manifold grids, and the reconstructed manifold grids are input into a non-manifold structure module.

(6) Restoring non-manifold structural module

Input: manifold mesh, newly added vertex index information and original non-manifold vertex index information

And (3) outputting: reconstructed non-manifold mesh

Wherein the non-manifold edge and the recovery process of the non-manifold point are the same. First, traversing the newly added vertex index information and the corresponding original non-manifold vertex index information, and updating the index information of the newly added vertex in the connection relation to the index information of the original non-manifold vertex. Then, the newly added vertices are deleted from the vertices of the manifold mesh, resulting in a reconstructed non-manifold mesh (i.e., a decoding mesh).

It should be noted that, in the trellis encoding method provided in the embodiment of the present application, the execution subject may be a trellis encoding device, or a control module of the trellis encoding device for executing the trellis encoding method. In the embodiment of the present application, a method for executing the trellis encoding by the trellis encoding device is taken as an example, and the trellis encoding device provided by the embodiment of the present application is described.

Referring to fig. 11, fig. 11 is a block diagram of a trellis encoding device according to an embodiment of the present application, and as shown in fig. 11, a trellis encoding device 300 includes:

the processing module 301 is configured to split the non-manifold structure in the mesh to be encoded to obtain non-manifold information and a manifold mesh;

a first encoding module 302, configured to encode the non-manifold information to obtain a first subcode stream;

A second encoding module 303, configured to encode the manifold mesh to obtain a second subcode stream;

And the obtaining module 304 is configured to obtain a trellis encoding result according to the first subcode stream and the second subcode stream.

Optionally, the grid to be encoded includes a first manifold grid and a first non-manifold grid, the first manifold grid and the first non-manifold grid are connected by the non-manifold structure, the non-manifold structure includes a first vertex, and the processing module includes:

the establishing unit is used for establishing a second vertex, wherein the second vertex and the first vertex are repeated points, and the index information of the second vertex and the index information of the first vertex are different;

The processing unit is used for splitting the non-manifold structure in the grid to be coded based on the second vertex so as to convert the first non-manifold grid into a second manifold grid;

Optionally, the processing unit is specifically configured to:

Optionally, the second encoding module is specifically configured to:

The grid coding device 300 in the embodiment of the application can reduce the quality loss of grid information after encoding and decoding processing.

The trellis encoding device in the embodiments of the present application may be a device, a device with an operating system or an electronic device, or may be a component, an integrated circuit, or a chip in a terminal. The apparatus or electronic device may be a mobile terminal or a non-mobile terminal. By way of example, mobile terminals may include, but are not limited to, the types of terminals listed above, and non-mobile terminals may be servers, network attached storage (Network Attached Storage, NAS), personal computers (personal computer, pcs), televisions (tvs), teller machines, self-service machines, etc., and embodiments of the present application are not limited in particular.

The trellis encoding device provided by the embodiment of the present application can implement each process implemented by the method embodiment of fig. 2, and achieve the same technical effects, and for avoiding repetition, the description thereof will not be repeated here.

It should be noted that, in the trellis decoding method provided in the embodiment of the present application, the execution subject may be a trellis decoding device, or a control module of the trellis decoding device for executing the trellis decoding method. In the embodiment of the present application, a method for executing trellis decoding by a trellis decoding device is taken as an example, and the trellis decoding device provided by the embodiment of the present application is described.

Referring to fig. 12, fig. 12 is a block diagram of a trellis decoding device according to an embodiment of the present application, and as shown in fig. 12, a trellis decoding device 400 includes:

an obtaining module 401, configured to obtain a first subcode stream and a second subcode stream according to a trellis encoding result of a trellis to be decoded;

a first decoding module 402, configured to decode the first subcode stream to obtain non-manifold information;

A second decoding module 403, configured to decode the second subcode stream to obtain a manifold mesh;

And a processing module 404, configured to reconstruct the manifold mesh based on the non-manifold information, so as to obtain a decoding mesh.

the processing module is specifically configured to:

Optionally, the processing module is specifically configured to:

The grid decoding device 400 in the embodiment of the application can reduce or even eliminate the quality loss of the grid information after the encoding and decoding processing.

The trellis decoding device in the embodiments of the present application may be a device, a device with an operating system or an electronic device, or may be a component, an integrated circuit, or a chip in a terminal. The apparatus or electronic device may be a mobile terminal or a non-mobile terminal. By way of example, mobile terminals may include, but are not limited to, the types of terminals listed above, and non-mobile terminals may be servers, network attached storage (Network Attached Storage, NAS), personal computers (personal computer, pcs), televisions (tvs), teller machines, self-service machines, etc., and embodiments of the present application are not limited in particular.

The trellis decoding device provided by the embodiment of the present application can implement each process implemented by the method embodiment of fig. 9, and achieve the same technical effects, and for avoiding repetition, the description thereof will not be repeated here.

Optionally, as shown in fig. 13, the embodiment of the present application further provides a communication device 500, including a processor 501 and a memory 502, where the memory 502 stores a program or instructions that can be executed on the processor 501, for example, when the communication device 500 is an encoding end device, the program or instructions implement the steps of the foregoing embodiment of the trellis encoding method when executed by the processor 501, and achieve the same technical effect. When the communication device 500 is a decoding end device, the program or the instruction, when executed by the processor 501, implements the steps of the foregoing embodiment of the trellis decoding method, and the same technical effects can be achieved, so that repetition is avoided and detailed description is omitted.

The embodiment of the application also provides a terminal, which comprises a processor and a communication interface, wherein the processor is used for: splitting a non-manifold structure in the grid to be coded to obtain non-manifold information and manifold grids; encoding the non-manifold information to obtain a first sub-code stream; encoding the manifold grid to obtain a second subcode stream; and obtaining a grid coding result according to the first sub-code stream and the second sub-code stream. Or the processor is configured to: acquiring a first subcode stream and a second subcode stream according to a grid coding result of a grid to be decoded; decoding the first subcode stream to obtain non-manifold information; decoding the second subcode stream to obtain a manifold grid; and reconstructing the manifold grid based on the non-manifold information to obtain a decoding grid. The terminal embodiment corresponds to the above-mentioned embodiment of the trellis encoding method or the trellis decoding method, and each implementation process and implementation manner of the above-mentioned embodiment of the trellis encoding method or the trellis decoding method are applicable to the terminal embodiment, and the same technical effects can be achieved. Specifically, fig. 14 is a schematic diagram of a hardware structure of a terminal for implementing an embodiment of the present application.

The terminal 600 includes, but is not limited to: at least some of the components of the radio frequency unit 601, the network module 602, the audio output unit 603, the input unit 604, the sensor 605, the display unit 606, the user input unit 607, the interface unit 608, the memory 609, and the processor 610, etc.

Those skilled in the art will appreciate that the terminal 600 may further include a power source (e.g., a battery) for powering the various components, and the power source may be logically coupled to the processor 610 by a power management system so as to perform functions such as managing charging, discharging, and power consumption by the power management system. The terminal structure shown in fig. 14 does not constitute a limitation of the terminal, and the terminal may include more or less components than shown, or may combine certain components, or may be arranged in different components, which will not be described in detail herein.

It should be appreciated that in embodiments of the present application, the input unit 604 may include a graphics processing unit (Graphics Processing Unit, GPU) 6041 and a microphone 6042, with the graphics processor 6041 processing image data of still pictures or video obtained by an image capturing apparatus (e.g., a camera) in a video capturing mode or an image capturing mode. The display unit 606 may include a display panel 6061, and the display panel 6061 may be configured in the form of a liquid crystal display, an organic light emitting diode, or the like. The user input unit 607 includes at least one of a touch panel 6071 and other input devices 6072. The touch panel 6071 is also called a touch screen. The touch panel 6071 may include two parts of a touch detection device and a touch controller. Other input devices 6072 may include, but are not limited to, a physical keyboard, function keys (e.g., volume control keys, switch keys, etc.), a trackball, a mouse, a joystick, and so forth, which are not described in detail herein.

In the embodiment of the present application, after receiving downlink data from the network side device, the radio frequency unit 601 may transmit the downlink data to the processor 610 for processing; in addition, the radio frequency unit 601 may send uplink data to the network side device. Typically, the radio frequency unit 601 includes, but is not limited to, an antenna, an amplifier, a transceiver, a coupler, a low noise amplifier, a duplexer, and the like.

The memory 609 may be used to store software programs or instructions and various data. The memory 609 may mainly include a first storage area storing programs or instructions and a second storage area storing data, wherein the first storage area may store an operating system, application programs or instructions (such as a sound playing function, an image playing function, etc.) required for at least one function, and the like. Further, the memory 609 may include volatile memory or nonvolatile memory, or the memory 609 may include both volatile and nonvolatile memory. The nonvolatile Memory may be a Read-Only Memory (ROM), a Programmable ROM (PROM), an Erasable PROM (EPROM), an Electrically Erasable EPROM (EEPROM), or a flash Memory. The volatile memory may be random access memory (Random Access Memory, RAM), static random access memory (STATIC RAM, SRAM), dynamic random access memory (DYNAMIC RAM, DRAM), synchronous Dynamic Random Access Memory (SDRAM), double data rate synchronous dynamic random access memory (double DATA RATE SDRAM, DDRSDRAM), enhanced synchronous dynamic random access memory (ENHANCED SDRAM, ESDRAM), synchronous link dynamic random access memory (SYNCH LINK DRAM, SLDRAM), and direct random access memory (DRRAM). Memory 609 in embodiments of the present application includes, but is not limited to, these and any other suitable types of memory.

The processor 610 may include one or more processing units; optionally, the processor 610 integrates an application processor that primarily processes operations involving an operating system, user interface, application programs, etc., and a modem processor that primarily processes wireless communication signals, such as a baseband processor. It will be appreciated that the modem processor described above may not be integrated into the processor 610.

Wherein, in the case that the terminal is a coding end device:

the processor 610 is configured to:

Encoding the non-manifold information to obtain a first sub-code stream;

encoding the manifold grid to obtain a second subcode stream;

Optionally, the mesh to be encoded includes a first manifold mesh and a first non-manifold mesh, the first manifold mesh and the first non-manifold mesh being connected by the non-manifold structure, the non-manifold structure including a first vertex, the processor 610 is further configured to:

Optionally, the processor 610 is further configured to:

Wherein, in the case that the terminal is a decoding end device:

the processor 610 is configured to:

decoding the first subcode stream to obtain non-manifold information;

Decoding the second subcode stream to obtain a manifold grid;

The processor 610 is further configured to:

Optionally, the processor 610 is further configured to:

The terminal in the embodiment of the application can reduce or even eliminate the quality loss of the grid information after the encoding and decoding processing.

Specifically, the terminal of the embodiment of the application further comprises: instructions or programs stored in the memory 609 and executable on the processor 610, the processor 610 invokes the instructions or programs in the memory 609 to perform the method performed by the modules shown in fig. 11, and achieve the same technical effects, so that repetition is avoided and thus are not described herein.

The embodiment of the present application further provides a readable storage medium, where a program or an instruction is stored on the readable storage medium, where the program or the instruction implements each process of the foregoing trellis encoding method embodiment when executed by a processor, or where the program or the instruction implements each process of the foregoing trellis decoding method embodiment when executed by a processor, and the program or the instruction can achieve the same technical effect, and for avoiding repetition, a detailed description is omitted herein.

Wherein the processor is a processor in the terminal described in the above embodiment. The readable storage medium includes a computer readable storage medium such as a read-only memory (ROM), a random access memory (Random Access Memory, RAM), a magnetic disk or an optical disk, and the like.

The embodiment of the application further provides a chip, which comprises a processor and a communication interface, wherein the communication interface is coupled with the processor, and the processor is used for running programs or instructions to realize the processes of the embodiment of the grid coding method or to realize the processes of the embodiment of the grid decoding method, and can achieve the same technical effects, so that repetition is avoided, and no redundant description is provided here.

It should be understood that the chips referred to in the embodiments of the present application may also be referred to as system-on-chip chips, or the like.

It should be noted that, in this document, the terms "comprises," "comprising," or any other variation thereof, are intended to cover a non-exclusive inclusion, such that a process, method, article, or apparatus that comprises a list of elements does not include only those elements but may include other elements not expressly listed or inherent to such process, method, article, or apparatus. Without further limitation, an element defined by the phrase "comprising one … …" does not exclude the presence of other like elements in a process, method, article, or apparatus that comprises the element. Furthermore, it should be noted that the scope of the methods and apparatus in the embodiments of the present application is not limited to performing the functions in the order shown or discussed, but may also include performing the functions in a substantially simultaneous manner or in an opposite order depending on the functions involved, e.g., the described methods may be performed in an order different from that described, and various steps may be added, omitted, or combined. Additionally, features described with reference to certain examples may be combined in other examples.

From the above description of the embodiments, it will be clear to those skilled in the art that the above-described embodiment method may be implemented by means of software plus a necessary general hardware platform, but of course may also be implemented by means of hardware, but in many cases the former is a preferred embodiment. Based on such understanding, the technical solution of the present application may be embodied essentially or in a part contributing to the prior art in the form of a computer software product stored in a storage medium (e.g. ROM/RAM, magnetic disk, optical disk) comprising instructions for causing a terminal (which may be a mobile phone, a computer, a server, an air conditioner, or a network device, etc.) to perform the method according to the embodiments of the present application.

The embodiments of the present application have been described above with reference to the accompanying drawings, but the present application is not limited to the above-described embodiments, which are merely illustrative and not restrictive, and many forms may be made by those having ordinary skill in the art without departing from the spirit of the present application and the scope of the claims, which are to be protected by the present application.

Claims

1. A method of trellis encoding, comprising:

Encoding the non-manifold information to obtain a first sub-code stream;

encoding the manifold grid to obtain a second subcode stream;

2. The method of claim 1, wherein the mesh to be encoded comprises a first manifold mesh and a first non-manifold mesh, the first manifold mesh and the first non-manifold mesh being connected by the non-manifold structure, the non-manifold structure comprising a first vertex, the splitting the non-manifold structure in the mesh to be encoded comprising:

3. The method of claim 2, wherein the non-manifold information further comprises a non-manifold identification;

4. The method of claim 2, wherein the index information of any one of the first vertex and the second vertex includes geometric index information and attribute index information, the geometric index information characterizing a position of the vertex in a geometric information encoding order, the attribute index information characterizing a position of the vertex in an attribute information encoding order;

5. The method according to claim 2, wherein the splitting the non-manifold structure in the mesh to be encoded based on the second vertex comprises:

6. The method of claim 5, wherein encoding the manifold trellis to obtain a second sub-stream comprises:

7. A trellis decoding method comprising:

decoding the first subcode stream to obtain non-manifold information;

Decoding the second subcode stream to obtain a manifold grid;

8. The method of claim 7, wherein the non-manifold information includes index information of a first vertex and index information of a second vertex, the second vertex being different from the index information of the first vertex;

9. The method of claim 8, wherein the first subcode stream comprises a code stream corresponding to a non-manifold identifier, a code stream corresponding to index information of the second vertex, and a code stream corresponding to index information of the first vertex;

10. The method of claim 8, wherein the first subcode stream comprises a stream corresponding to geometric index information and a stream corresponding to attribute index information;

11. The method of claim 8, wherein the second subcode stream comprises a geometric information code stream, an attribute information code stream and a connection relationship information code stream, the geometric information code stream is a code stream corresponding to geometric information of the manifold mesh, the attribute information code stream is a code stream corresponding to attribute information of the manifold mesh, the connection relationship information code stream is a code stream corresponding to second connection relationship information of the manifold mesh, and the second connection relationship information is used for representing a connection relationship of vertices of the manifold mesh;

12. The method of claim 11, wherein reconstructing the manifold mesh based on the index information of the first vertex and the index information of the second vertex to obtain a decoded mesh comprises:

13. A trellis encoding device, comprising:

14. A trellis decoding device, comprising:

15. A terminal comprising a processor, a memory and a program or instruction stored on the memory and executable on the processor, which when executed by the processor implements the steps of the trellis encoding method of any of claims 1 to 6; or the program or instructions when executed by the processor implement the steps of the trellis decoding method of any of claims 7 to 12.

16. A readable storage medium, characterized in that the readable storage medium stores thereon a program or instructions which, when executed by a processor, implements the steps of the trellis encoding method of any one of claims 1 to 6, or which, when executed by a processor, implements the steps of the trellis decoding method of any one of claims 7 to 12.