CONNECTIVITY INFORMATION CODING METHOD AND APPARATUS FOR CODED MESH REPRESENTATION

Systems and methods of the present disclosure provide solutions that address technological challenges related to 3D content. These solutions include a computer-implemented method for encoding three-dimensional (3D) content comprising: processing the 3D content into segments, each segment comprising a set of faces and vertex indices representative of the 3D content; processing each segment to sort the respective set of faces and vertex indices in each segment; packing each segment of 3D content to generate connectivity information frames of blocks, each block comprising a subset of the sorted faces and vertex indices; and encoding the connectivity information frames.

BACKGROUND

Developments in three dimensional (3D) graphics technologies have led to the integration of 3D graphics in various applications. For example, 3D graphics are used in various entertainment applications such as interactive 3D environments or 3D videos. Interactive 3D environments offer immersive six degrees of freedom representation, which provides improved functionality for users. Additionally, 3D graphics are used in various engineering applications, such as 3D simulations and 3D analysis. Furthermore, 3D graphics are used in various manufacturing and architecture applications, such as 3D modeling. As developments in 3D graphics technologies have led to the integration of 3D graphics in various applications, so too have these developments led to increasing complexity associated with processing (e.g., coding, decoding, compressing, decompressing) 3D graphics. The Motion Pictures Experts Group (MPEG) of the International Organization for Standardization/International Electrotechnical Commission (ISO/IEC) has published standards with respect to coding/decoding and compression/decompression of 3D graphics. These standards include the Visual Volumetric Video-Based Coding (V3C) standard for Video-Based Point Cloud Compression (V-PCC).

SUMMARY

Various embodiments of the present disclosure provide a computer-implemented method comprising processing the 3D content into segments, each segment comprising a set of faces and vertex indices representative of the 3D content; processing each segment to sort the respective set of faces and vertex indices in each segment; packing each segment of 3D content to generate connectivity information frames of blocks, each block comprising a subset of the sorted faces and vertex indices; and encoding the connectivity information frames.

In some embodiments of the computer-implemented method, each face in the set of faces is associated with three sorted vertices indicated by the sorted vertex indices.

In some embodiments of the computer-implemented method, each block is mapped to a particular slice of a connectivity information frame.

In some embodiments of the computer-implemented method, the faces are sorted in a descending order and, for each face, the vertex indices are sorted in an ascending order.

In some embodiments of the computer-implemented method, each block includes connectivity coding samples that are encoded as pixels.

In some embodiments of the computer-implemented method, each block comprises connectivity coding samples that indicate differential values of the sorted vertex indices, wherein the faces are encoded based on the differential values.

In some embodiments of the computer-implemented method, the connectivity information frames are associated with one or more resolutions based on a number of faces in each connectivity information frame.

In some embodiments of the computer-implemented method, the encoding the connectivity information frames is based on a video codec, the video codec indicated in a sequence parameter set, a picture parameter set, or a supplemental enhancement information associated with the encoded connectivity information frames.

Various embodiments of the present disclosure provide an encoder comprising at least one processor; and a memory storing instructions that, when executed by the at least one processor, cause the encoder to perform processing the 3D content into segments, each segment comprising a set of faces and vertex indices representative of the 3D content; processing each segment to sort the respective set of faces and vertex indices in each segment; packing each segment of 3D content to generate connectivity information frames of blocks, each block comprising a subset of the sorted faces and vertex indices; determining differential values of the sorted vertex indices and a constant value based on a video coded bit depth for encoding the connectivity information frames, wherein the differential values are encoded as connectivity coding samples in the blocks; and encoding the connectivity information frames.

In some embodiments of the encoder, each face in the set of faces is associated with three sorted vertices indicated by the sorted vertex indices.

In some embodiments of the encoder, each block is mapped to a particular slice of a connectivity information frame.

In some embodiments of the encoder, the faces are sorted in a descending order and, for each face, the vertex indices are sorted in an ascending order.

In some embodiments of the encoder, each block includes connectivity coding samples that are encoded as pixels.

In some embodiments of the encoder, the connectivity information frames are associated with one or more resolutions based on a number of faces in each connectivity information frame.

Various embodiments of the present disclosure provide a non-transitory computer-readable storage medium including instructions that, when executed by at least one processor of an encoder, cause the decoder to perform processing 3D content into segments, each segment comprising a set of faces and vertex indices representative of the 3D content; processing each segment to sort the respective set of faces and vertex indices in each segment to generate respective face lists; packing each segment of 3D content to generate connectivity information frames of blocks, each block comprising a subset of the sorted faces and vertex indices; determining differential values of the sorted vertex indices and a constant value based on a video coded bit depth for encoding the connectivity information frames, wherein the differential values are encoded as connectivity coding samples in the blocks; and encoding the connectivity information frames.

In some embodiments of the non-transitory computer-readable storage medium, each face in the set of faces is associated with three sorted vertices indicated by the sorted vertex indices.

In some embodiments of the non-transitory computer-readable storage medium, each block is mapped to a particular slice of a connectivity information frame.

In some embodiments of the non-transitory computer-readable storage medium, the faces are sorted in a descending order and, for each face, the vertex indices are sorted in an ascending order.

In some embodiments of the non-transitory computer-readable storage medium, each block includes connectivity coding samples that are encoded as pixels.

In some embodiments of the non-transitory computer-readable storage medium, the encoding the connectivity information frames is based on a video codec, the video codec indicated in a sequence parameter set, a picture parameter set, or a supplemental enhancement information associated with the encoded connectivity information frames.

DETAILED DESCRIPTION

As described above, 3D graphics technologies are integrated in various applications, such as entertainment applications, engineering applications, manufacturing applications, and architecture applications. In these various applications, 3D graphics may be used to generate 3D models of incredible detail and complexity. Given the detail and complexity of the 3D models, the data sets associated with the 3D models can be extremely large. Furthermore, these extremely large data sets may be transferred, for example, through the Internet. Transfer of large data sets, such as those associated with detailed and complex 3D models, can therefore become a bottleneck in various applications. As illustrated by this example, developments in 3D graphics technologies provide improved utility to various applications but also present technological challenges. Improvements to 3D graphics technologies, therefore, represent improvements to the various technological applications to which 3D graphics technologies are applied. Thus, there is a need for technological improvements to address these and other technological problems related to 3D graphics technologies.

Accordingly, the present disclosure provides solutions that address the technological challenges described above through improved approaches to compression/decompression and coding/decoding of 3D graphics. In various embodiments, connectivity information in 3D mesh content can be efficiently coded through packing sorted mesh connectivity information into mesh connectivity frames. 3D content, such as 3D graphics, can be represented as a mesh (e.g., 3D mesh content). The mesh can include vertices, edges, and faces that describe the shape or topology of the 3D content. The mesh can be segmented into blocks (e.g., segments, tiles). For each block, the vertex information associated with each face can be arranged in order (e.g., descending order). With the vertex information associated with each face arranged in order, the faces are arranged in order (e.g., ascending order). The sorted faces in each block can be packed into two-dimensional (2D) frames. Sorting the vertex information can guarantee an increasing order of vertex indices, facilitating improved processing of the mesh. In various embodiments, connectivity information in 3D mesh content can be efficiently packed into connectivity information frames that are further divided into coding blocks. Components of the connectivity information in the 3D mesh content can be transformed from one-dimensional (1D) connectivity components (e.g., list, face list) to 2D connectivity images (e.g., connectivity coding sample array). With the connectivity information in the 3D mesh content transformed to 2D connectivity images, video encoding processes can be applied to the 2D connectivity images (e.g., as video connectivity frames). In this way, 3D mesh content can be efficiently compressed and decompressed by leveraging video encoding solutions. 3D mesh content encoded in accordance with these approaches can be efficiently decoded. Connectivity components can be extracted from a coded dynamic mesh bitstream and decoded as a frame (e.g., image). Connectivity coding samples, which correspond with pixels in the frame, are extracted. The 3D mesh content can be reconstructed from the connectivity information extracted. Thus, the present disclosure provides solutions that address technological challenges arising in 3D graphics technologies. Various features of the solutions are discussed in further detail herein and in co-pending International application Attorney Docket No. 75EP-356118-WO, incorporated by reference in their entirety.

Descriptions of the various embodiments provided herein may include one or more of the terms listed below. For illustrative purposes and not to limit the disclosure, exemplary descriptions of the terms are provided herein.

Mesh: a collection of vertices, edges, and faces that may define the shape/topology of a polyhedral object. The faces may include triangles (e.g., triangle mesh).

Dynamic mesh: a mesh with at least one of various possible components (e.g., connectivity, geometry, mapping, vertex attribute, and attribute map) varying in time.

Animated Mesh: a dynamic mesh with constant connectivity.

Connectivity: a set of vertex indices describing how to connect the mesh vertices to create a 3D surface (e.g., geometry and all the attributes may share the same unique connectivity information).

Geometry: a set of vertex 3D (e.g., x, y, z) coordinates describing positions associated with the mesh vertices. The coordinates (e.g., x, y, z) representing the positions may have finite precision and dynamic range.

Mapping: a description of how to map the mesh surface to 2D regions of the plane. Such mapping may be described by a set of UV parametric/texture (e.g., mapping) coordinates associated with the mesh vertices together with the connectivity information.

Vertex attribute: a scalar of vector attribute values associated with the mesh vertices.

Attribute Map: attributes associated with the mesh surface and stored as 2D images/videos. The mapping between the videos (e.g., parametric space) and the surface may be defined by the mapping information.

Vertex: a position (e.g., in 3D space) along with other information such as color, normal vector, and texture coordinates.

Edge: a connection between two vertices.

Face: a closed set of edges in which a triangle face has three edges defined by three vertices. Orientation of the face may be determined using a “right-hand” coordinate system.

Surface: a collection of faces that separates the three-dimensional object from the environment.

Connectivity Coding Unit (CCU): a square unit of size N×N connectivity coding samples that carry connectivity information.

Connectivity Coding Sample: a coding element of the connectivity information calculated as a difference of elements between a current face and a predictor face.

Block: a representation of the mesh segment as a collection of connectivity coding samples represented as three attribute channels. A block may consist of CCUs.

bits per point (bpp): an amount of information in terms of bits, which may be required to describe one point in the mesh.

Before describing various embodiments of the present disclosure in detail, it may be helpful to describe an exemplary approach to encoding connectivity information for a mesh.FIGS.1A-1Billustrate examples associated with coding and decoding connectivity information for a triangle mesh, according to various embodiments of the present disclosure. Various approaches to coding 3D content involves representing the 3D content using a triangle mesh. The triangle mesh provides the shape and topology of the 3D content being represented. In various approaches to coding and decoding the 3D content, the triangle mesh is traversed in a deterministic, spiral-like manner beginning with an initial face (e.g., triangle at an initial corner). The initial face can be located at the top of a stack or located at a random corner in the 3D content. By traversing the triangle mesh in a deterministic, spiral-like manner, each triangle can be marked in accordance with one of five possible cases (e.g., “C”, “L”, “E”, “R”, “S”). Coding of the triangle mesh can be performed based on the order in which traversal of the triangle mesh encounters these cases.

FIG.1Aillustrates an example 100 of vertex symbol coding for connectivity information of a triangle mesh, according to various embodiments of the present disclosure. The vertex symbol coding corresponds with cases that traversal of the triangle mesh may encounter. Case “C”102ais a case where a visited face (e.g., visited triangle) has a vertex common to the visited face, a left adjacent face, and a right adjacent face, and the vertex has not been previously visited in traversal of a triangle mesh. Because the vertex has not been previously visited, the left adjacent face and the right adjacent face have also not been previously visited. In other words, in case “C”102a, the vertex and faces adjacent to the visited face have not been previously visited. In case “L”102b, case “E”102c, case “R”102d, and case “S”102e, a vertex common to a visited face, a left adjacent face, and a right adjacent face has been previously visited. These cases, case “L”102b, case “E”102c, case “R”102d, and case “S”102e, describe different possible cases associated with a vertex that has been previously visited. In case “L”102b, a left adjacent face of a visited face has been previously visited, and a right adjacent face of the visited face has not been previously visited. In case “E”102c, a left adjacent face of a visited face and a right adjacent face of the visited face have been previously visited. In case “R”102d, a left adjacent face of a visited face has not been previously visited, and a right adjacent face of the visited face has been previously visited. In case “S”102e, a left adjacent face of a visited face and a right adjacent face of the visited face have not been visited. Case “S”102ediffers from case “C”102ain that, in case “S”102e, a vertex common to a visited face, a left adjacent face, and a right adjacent face has been previously visited. This may indicate that a face opposite the visited face may have been previously visited.

As described above, traversal of a triangle mesh encounters these five possible cases. Vertex symbol coding for connectivity information can be based on which case is encountered while traversing the triangle mesh. So, when traversal of a triangle mesh encounters a face corresponding with case “C”102a, then connectivity information for that face can be coded as “C”. Similarly, when traversal of the triangle mesh encounters a face corresponding with case “L”102b, case “E”102c, case “R”102d, or case “S”102e, then connectivity information for that face can be coded as “L”, “E”, “R”, or “S” accordingly.

FIG.1Billustrates an example 110 of connectivity data based on the vertex symbol coding illustrated inFIG.1A, according to various embodiments of the present disclosure. In the example illustrated inFIG.1B, traversal of a triangle mesh can begin with an initial face112. As the traversal of the triangle mesh has just begun, the initial face112corresponds with case “C”102aofFIG.1A. Traversal of the triangle mesh continues in accordance with the arrows illustrated inFIG.1B. The next face encountered in the traversal of the triangle mesh corresponds with case “C”102aofFIG.1A. Traversal continues, encountering a face corresponding with case “R”102dofFIG.1A, followed by another face corresponding with case “R”102dofFIG.1A, followed by another face corresponding with case “R”102dofFIG.1A, and followed by a face114corresponding with case “S”102eofFIG.1A. At the face114corresponding with case “S”102eofFIG.1A, traversal of the triangle mesh follows two paths along a left adjacent face and a right adjacent face, as illustrated inFIG.1B. In general, traversal of the triangle mesh follows the path along the right adjacent face before returning to follow the path along the left adjacent face. Accordingly, as illustrated inFIG.1B, traversal first follows the path along the right adjacent face, encountering faces corresponding with case “L”102b, case “C”102a, case “R”102d, and case “S”102eofFIG.1A, respectively. As another face corresponding with case “S”102eofFIG.1Ahas been encountered, traversal of the triangle mesh follows two paths along a left adjacent face and a right adjacent face. Again, traversal of the triangle mesh follows the path along the right adjacent face first, which terminates with a face corresponding with case “E”102cofFIG.1A. Traversal of the path along the left adjacent face encounters face corresponding with case “R”102dand case “R”102dofFIG.1A, respectively, and terminates with a face corresponding with case “E”102cofFIG.1A. Returning to face114, and following the path along the left adjacent face, traversal of the triangle mesh encounters faces corresponding with case “L”102b, case “C”102a, case “R”102d, case “R”102d, case “R”102d, case “C”102a, case “R”102d, case “R”102d, case “R”102d, and finally case “E”102cofFIG.1A, respectively. Traversal of the triangle mesh following the path along the left adjacent face terminates with the face corresponding with case “E”102cofFIG.1A. In this way, traversal of the triangle mesh illustrated inFIG.1Bis conducted in a deterministic, spiral-like manner. The resulting coding of connectivity data for the triangle mesh, in accordance with the order with which the triangle mesh was traversed, provides the coding “CCRRRSLCRSERRELCRRRCRRRE”. Further information regarding vertex symbol coding and traversal of triangle meshes is provided by Jarek Rossignac. 1999. Edgebreaker: Connectivity Compression for Triangle Meshes. IEEE Transactions on Visualization and Computer Graphics 5, 1 (January 1999), 47-61. https://doi.org/10.1109/2945.764870, incorporated by reference herein.

In the various approaches to coding 3D content illustrated inFIGS.1A-1B, traversal of a triangle mesh in a deterministic, spiral-like manner ensures that each face (besides the initial face) is next to an already encoded face. This allows efficient compression of vertex coordinates and other attributes associated with each face. Attributes, such as coordinates and normals of a vertex, can be predicted from adjacent faces using various predictive algorithms, such as parallelogram prediction. This allows for efficient compression using differences between predicted and original values. By encoding each vertex of a face using the “C”, “L”, “E”, “R”, and “S” configuration symbols, information to reconstruct a triangle mesh can be minimized by encoding the mesh connectivity of the triangle mesh as the sequence by which the faces of the triangle mesh are encoded. Still, while these various approaches to coding 3D content provide for efficient encoding of connectivity information, these various approaches can be further improved, as further described herein.

FIGS.1C-1Dillustrate example systems associated with coding and decoding connectivity information for a mesh, according to various embodiments of the present disclosure. In various approaches to coding 3D content, mesh information is encoded using a point cloud coding framework (e.g., V-PCC point cloud coding framework) with modifications to encode connectivity information and, optionally, an associated attribute map. In the point cloud coding framework, encoding the mesh information involves using a default patch generation and packing operations. Points are segmented into regular patches, and points not segmented into regular patches (e.g., not handled by the default patch generation process) are packed into raw patches. In some cases, this may result in the order of reconstructed vertices (e.g., from decoding the mesh information) to be different from that in the input mesh information (e.g., from encoding the mesh information). To address this potential issue, vertex indices may be updated to follow the order of the reconstructed vertices before encoding connectivity information.

The updated vertex indices are encoded in accordance with the traversal approach described above. In various approaches to coding 3D content, connectivity information is encoded losslessly in the traversal order of the updated vertex indices. As the updated vertex indices are of a different order than that of the input mesh information, the traversal order of the updated vertex indices is encoded along with the connectivity information. The traversal order of the updated vertex indices can be referred to as a reordering information or a vertex map. The reordering information, or the vertex map, can be encoded in accordance with various encoding approaches, such as differential coding or entropy coding. The encoded reordering information, or encoded vertex map, can be added to an encoded bitstream with the encoded connectivity information derived from the updated vertex indices. The resulting encoded bitstream can be decoded, and the encoded connectivity information and the encoded vertex map can be extracted therefrom. The vertex map is applied to the connectivity information to align the connectivity information with the reconstructed vertices.

FIG.1Cillustrates an example system120for decoding connectivity information for a mesh, according to various embodiments of the present disclosure. The example system120can decode an encoded bitstream including encoded connectivity information and an encoded vertex map as described above. As illustrated inFIG.1C, a compressed bitstream (e.g., encoded bitstream) is received by a demultiplexer. The demultiplexer can separate the compressed bitstream into various substreams, including an attribute substream, a geometry substream, an occupancy map substream, a patch substream, a connectivity substream, and a vertex map substream. With respect to the connectivity substream (e.g., containing encoded connectivity information) and the vertex map substream (e.g., containing an encoded vertex map), the connectivity substream is processed by a connectivity decoder120and the vertex map substream is processed by a vertex map decoder122. The connectivity decoder120can decode the encoded connectivity information in the connectivity substream to derive connectivity information for a mesh. The vertex map decoder122can decode the encoded vertex map in the vertex map substream. As noted above, the connectivity information for the mesh derived by the connectivity decoder120is based on reordered vertex indices. Therefore, the connectivity information from the connectivity decoder120and the vertex map from the vertex map decoder122are used to update vertex indices124in the connectivity information. The connectivity information, with the updated vertex indices, can be used to reconstruct the mesh from the compressed bitstream. Similarly, the vertex map can also be applied to reconstructed geometry and color attributes to align them with the connectivity information.

In some approaches to coding 3D content, a vertex map is not separately encoded. In such approaches (e.g., color-per-vertex), connectivity information is represented in mesh coding in absolute values with associated vertex indices. The connectivity information is coded sequentially using, for example, entropy coding.FIG.1Dillustrates an example system130for decoding connectivity information for a mesh where a vertex map is not separately encoded, according to various embodiments of the present disclosure. As illustrated inFIG.1D, a compressed bitstream (e.g., encoded bitstream) is received by a demultiplexer. The demultiplexer can separate the compressed bitstream into various substreams, including an attribute substream, a geometry substream, an occupancy map substream, a patch substream, and a connectivity substream. As there is no encoded vertex map in the compressed bitstream, the demultiplexer does not produce a vertex map substream. The connectivity substream (e.g., containing connectivity information with associated vertex indices) is processed by a connectivity decoder132. The connectivity decoder132decodes the encoded connectivity information to derive the connectivity information and associated vertex indices for a mesh. As the connectivity information is already associated with its respective vertex indices, the example system130does not update the vertex indices of the connectivity information. Therefore, the connectivity information from the connectivity decoder132is used to reconstruct the mesh from the compressed bitstream.

As illustrated inFIGS.1C-1D, associating connectivity information with its respective vertex indices in some approaches to coding 3D content (e.g., color-per-vertex) offer a simplified process over other approaches to coding 3D content that use a vertex map. However, this simplified process comes with a tradeoff of with respect to limited flexibility and efficiency for information coding. Because the connectivity information and vertex indices are mixed, there is a significant entropy increase when coded. Furthermore, connectivity information uses a unique vertex index combination method for representing topography of a mesh, which increases the data size. For example, data size for connectivity information can be from approximately 16 to 20 bits per index, meaning a face is represented by approximately 48 to 60 bits. A typical data rate for information in mesh content using a color-per-vertex approach can be 170 bpp, with 60 bpp allocated for the connectivity information. Thus, while these various approaches to coding 3D content offer tradeoffs between simplicity and data size, these various approaches can be further improved with respect to both simplicity and data size, as further described herein.

FIGS.1E-11illustrate examples associated with coding and decoding connectivity information for a mesh, according to various embodiments of the present disclosure. In various approaches to coding 3D content, connectivity information is encoded in mesh frames. For example, as described above, in color-per-vertex approaches, connectivity information are stored in mesh frames with associated vertex indices.FIG.1Eillustrates example mesh frames140associated with color-per-vertex approaches, according to various embodiments of the present disclosure. As illustrated inFIG.1E, geometry and attribute information142can be stored in mesh frames as an ordered list of vertex coordinate information. Each vertex coordinate is stored with corresponding geometry and attribute information. Connectivity information144can be stored in mesh frames as an ordered list of face information, with each face including corresponding vertex indices and texture indices.

FIG.1Fillustrates an example 150 of mesh frames152a,152bassociated with color-per-vertex approaches and a corresponding 3D content154, according to various embodiments of the present disclosure. As illustrated in mesh frame152a, geometry and attribute information as well as connectivity information are stored in a mesh frame, with geometry and attribute information stored as an ordered list of vertex coordinate information and connectivity information stored as an ordered list of face information with corresponding vertex indices and texture indices. The geometry and attribute information illustrated in mesh frame152aincludes four vertices. The positions of the vertices are indicated by X, Y, Z coordinates and color attributes are indicated by R, G, B values. The connectivity information illustrated in mesh frame152aincludes three faces. Each face includes three vertex indices listed in the geometry and attribute information to form a triangle face. As illustrated in mesh frame152b, which is the same as mesh frame152a, by using the vertex indices for each corresponding face to point to the geometry and attribute information stored for each vertex coordinate, the 3D content154(e.g., 3D triangle) can be decoded based on the mesh frames152a,152b.

FIG.1Gillustrates example mesh frames160associated with 3D coding approaches using vertex maps, according to various embodiments of the present disclosure. As illustrated inFIG.1G, geometry information162can be stored in mesh frames as an ordered list of vertex coordinate information. Each vertex coordinate is stored with corresponding geometry information. Attribute information164can be stored in mesh frames, separate from the geometry information162, as an ordered list of projected vertex attribute coordinate information. The projected vertex attribute coordinate information is stored as 2D coordinate information with corresponding attribute information. Connectivity information166can be stored in mesh frames as an ordered list of face information, with each face including corresponding vertex indices and texture indices.

FIG.1Hillustrates an example 170 of a mesh frame172, a corresponding 3D content174, and a corresponding vertex map176associated with 3D coding approaches using vertex maps, according to various embodiments of the present disclosure. As illustrated inFIG.1H, geometry information, mapping information (e.g., attribute information), and connectivity information are stored in the mesh frame172. The geometry information illustrated in the mesh frame172includes four vertices. The positions of the vertices are indicated by X, Y, Z coordinates. The mapping information illustrated in the mesh frame172includes five texture vertices. The positions of the texture vertices are indicated by U, V coordinates. The connectivity information in the mesh frame172includes three faces. Each face includes three pairs of vertex indices and texture vertex coordinates. As illustrated inFIG.1H, by using the pairs of vertex indices and texture vertex coordinates for each face, the 3D content174(e.g., 3D triangle) and the vertex map176can be decoded based on the mesh frame172. Attribute information associated with the vertex map176can be applied to the 3D content174to apply the attribute information to the 3D content174.

FIG.11illustrates an example 180 associated with determining face orientation in various 3D coding approaches, according to various embodiments of the present disclosure. As illustrated inFIG.11, face orientation can be determined using a right-hand coordinate system. Each face illustrated in the example 180 includes three vertices, forming three edges. Each face is described by the three vertices. In a manifold mesh182, each edge belongs to at most two different faces. In a non-manifold mesh184, an edge can belong to two or more different faces. In both cases of the manifold mesh182and the non-manifold mesh184, the right-hand coordinate system can be applied to determine the face orientation of a face.

A coded bitstream for dynamic mesh is represented as a collection of components, which is composed of mesh bitstream header and data payload. The mesh bitstream header is comprised of the sequence parameter set, picture parameter set, adaptation parameters, tile information parameters, and supplemental enhancement information, etc. The mesh bitstream payload is comprised of the coded atlas information component, coded attribute information component, coded geometry (position) information component, coded mapping information component, and coded connectivity information component.

FIG.2Aillustrates an example encoder system200for mesh coding, according to various embodiments of the present disclosure. As illustrated inFIG.2A, an uncompressed mesh frame sequence202can be input to the encoder system200, and the example encoder system200can generate a coded mesh frame sequence224based on the uncompressed mesh frame sequence202. In general, a mesh frame sequence is composed of mesh frames. A mesh frame is a data format that describes 3D content (e.g., 3D objects) in a digital representation as a collection of geometry, connectivity, attribute, and attribute mapping information. Each mesh frame is characterized by a presentation time and duration. A mesh frame sequence (e.g., sequence of mesh frames) forms a dynamic mesh video.

As illustrated inFIG.2A, the encoder system200can generate coded mesh sequence information206based on the uncompressed mesh frame sequence202. The coded mesh sequence information206can include picture header information such as sequence parameter set (SPS), picture parameter set (PPS), and supplemental enhancement information (SEI). A mesh bitstream header can include the coded mesh sequence information206. The uncompressed mesh frame sequence202can be input to mesh segmentation204. The mesh segmentation204segments the uncompressed mesh frame sequence202into block data and segmented mesh data. A mesh bitstream payload can include the block data and the segmented mesh data. The mesh bitstream header and the mesh bitstream payload can be multiplexed together by the multiplexer222to generate the coded mesh frame sequence224. The encoder system200can generate block segmentation information208(e.g., atlas information) based on the block data. Based on the segmented mesh data, the encoder system200can generate attribute image composition210, geometry image composition,212, connectivity image composition,214, and mapping image composition216. As illustrated inFIG.2A, the connectivity image composition and the mapping image composition216can also be based on the block segmentation information208. As an example of the information generated, the block segmentation information208can include binary atlas information. The attribute image composition210can include RGB and YUV component information (e.g., RGB 4:4:4, YUV 4:2:0). The geometry image composition212can include XYZ vertex information (e.g., XYZ 4:4:4, XYZ 4:2:0). The connectivity image composition214can include vertex indices and texture vertex information (e.g., dv0, dv1, dv2 4:4:4). This can be represented as the difference between sorted vertices, as further described below. The mapping image composition216can include texture vertex information (e.g., UV 4:4:X). The block segmentation information208can be provided to a binary entropy coder218to generate atlas composition. The binary entropy coder218may be a lossless coder. The attribute image composition210can be provided to a video coder220ato generate attribute composition. The video coder220amay be a lossy coder. The geometry image composition212can be provided to a video coder220bto generate geometry composition. The video coder220bmay be lossy. The connectivity image composition can be provided to video coder220cto generate connectivity composition. The video coder220cmay be lossless. The mapping image composition216can be provided to video coder220dto generate mapping composition. The video coder220dmay be lossless. A mesh bitstream payload can include the atlas composition, the attribute composition, the geometry composition, the connectivity composition, and the mapping composition. The mesh bitstream payload and the mesh bitstream header are multiplexed together by the multiplexer222to generate the coded mesh frame sequence224.

In general, a coded bitstream for a dynamic mesh (e.g., mesh frame sequence) is represented as a collection of components, which is composed of mesh bitstream header and data payload (e.g., mesh bitstream payload). The mesh bitstream header is comprised of a sequence parameter set, picture parameter set, adaptation parameters, tile information parameters, and supplemental enhancement information, etc. The mesh bitstream payload can include coded atlas information component, coded attribute information component, coded geometry (position) information component, coded mapping information component, and coded connectivity information component.

FIG.2Billustrates an example pipeline250for generated a coded mesh with color per vertex encoding, according to various embodiments of the present disclosure. As illustrated by the pipeline250, a mesh frame252can be provided to a mesh segmentation process254. The mesh frame252can include geometry, connectivity, and attribute information. This can be an ordered list of vertex coordinates with corresponding attribute and connectivity information. For example, the mesh frame252can include:

where v_idx_0, v_idx_1, v_idx_2, and v_idx_3 are vertex indices, x, y, and z are vertex coordinates, a_1, a_2, and a_3 are attribute information, and f_idx_0 and f_idx_1 are faces. A mesh is represented by vertices in the form of an array. The index of the vertices (e.g., vertex indices) is an index of elements within the array. The mesh segmentation process254may be non-normative. Following the mesh segmentation process254is mesh block packing256. Here, a block can be a collection of vertices that belong to a particular segment in the mesh. Each block can be characterized by block offset, relative to the mesh origin, block width, and block height. The 3D geometry coordinates of the vertices in the block can be represented in a local coordinate system, which may be a differential coordinate system with respect to the mesh origin. Following the mesh block packing256, connectivity information258is provided to connectivity information coding264. Position information260is provided to position information coding266. Attribute information262is provided to attribute information coding268. The connectivity information258can include an ordered list of face information with corresponding vertex index and texture index per block. For example, the connectivity information258can include:

where Block_1 and Block_2 are mesh blocks, f_idx_0, f_idx_1, and f_idx_n are faces, and v_idx_1, v_idx_2, and v_idx_3 are vertex indices. The position information260can include an ordered list of vertex position information with corresponding vertex index coordinates per block. For example, the position information260can include:

where Block_1 and Block_2 are mesh blocks, v_idx_0, v_idx_1, and v_idx_i are vertex indices, and x_I, y_I, and z_I are vertex position information. The attribute information262can include an ordered list of vertex attribute information with corresponding vertex index attributes per block. For example, the attribute information262can include:

where Block_1 and Block_2 are mesh blocks, v_idx_0, v_idx_1, and v_idx_i are vertex indices, R, G, B are red green blue color components, and Y, U, V are luminance and chrominance components. Following the providing of the connectivity information258to the connectivity information coding264, the position information260to the position information coding266, and the attribute information262to the attribute information coding268, the coded information is multiplexed to generated a multiplexed mesh coded bitstream270.

To process a mesh frame, the segmentation process is applied for the global mesh frame, and all the information is coded in the form of three-dimensional blocks, whereas each block has a local coordinate system. The information required to convert the local coordinate system of the block to the global coordinate system of the mesh frame is carried in a block auxiliary information component (atlas component) of the coded mesh bitstream.

Before delving further into the details of the various embodiments of the present disclosure, it may be helpful to describe an overview of an example method for efficiently coding connectivity information in mesh content, according to various embodiments of the present disclosure. The example method can include four stages. For purpose of illustration, the examples provided herein include vertexes grouped in blocks with index j and connectivity coding units (CCUs) with index k.

In a first stage of the example method, mesh segmentation can create segments or blocks of mesh content that represent individual objects or individual regions of interest, volumetric tiles, semantic blocks, etc.

In a second stage of the example method, face sorting and normalization can provide a process of data manipulation within a mesh, or a segment where each face is first processed in a manner such that for a face with index i the associated vertices are arranged in a descending order.

In a third stage of the example method, composition of a video frame for connectivity information coding can provide a process of transformation of a one-dimensional connectivity component of a mesh frame (e.g., face list) to a two-dimensional connectivity image (e.g., connectivity coding sample array).

In a fourth stage of the example method, coding can provide a process where a packed connectivity information frame or sequence is coded by a video codec, which is indicated in SPS/PPS or an external method such as SEI information.

FIG.3Aillustrates an example vertex reordering process300for mesh connectivity information, according to various embodiments of the present disclosure. In various embodiments, the example vertex reordering process300can be associated with the second stage of the example method described above. As illustrated inFIG.3A, the example vertex reordering process300begins at step302with mesh frame connectivity information. At step304, select face i, a face with index i is selected. For example, the selected face can be described as:

where f[i] is a face i and v_idx[i, 0], v_idx[i, 1], and v_idx[i, 2] are vertex indices associated with the face i. At step306, a determination is made with respect to whether the vertex indices are sorted. For example, step306can be determined by:

where v_idx[i, 0] and v_idx[i, 1] are vertex indices associated with face i. If the determination at step306is yes, then at step308, a determination is made with respect to whether the subsequent vertex indices are sorted. For example, step308can be determined by:

where v_idx[i, 1] and v_idx[i, 2] are vertex indices associated with face i. If the determination at step306is no, then at step310, a determination is made with respect to whether the next vertex index is sorted with respect to those evaluated at step306. For example, step310can be determined by:

where v_idx[i, 0] and v_idx[i, 2] are vertex indices associated with face i. Based on the determinations made at steps308and310, the face vertex indices can be reordered accordingly. If the determination at step308is no, then at step312, the face vertex indices are reordered accordingly. For example, step312can be performed by:

where f[i] is a face i and v_idx[i, 0], v_idx[i, 1], and v_idx[i, 2] are vertex indices associated with the face i. If the determination at step308or at step310is yes, then at step312, the face vertex indices are reordered accordingly. For example, step314can be performed by:

where f[i] is a face i and v_idx[i, 0], v_idx[i, 1], and v_idx[i, 2] are vertex indices associated with the face i. If the determination at step310is no, then at step316, the face vertex indices are not reordered. For example, step316can be performed by maintaining:

where f[i] is a face i and v_idx[i, 0], v_idx[i, 1], and v_idx[i, 2] are vertex indices associated with the face i. At step318, after all faces from the mesh frame connectivity information302have been sorted, frames can be split into blocks and connectivity coding units (CCUs). At step320, coding of the processed connectivity information is performed.

In various embodiments, face sorting and normalization can involve vertex rotation. As described above, in face sorting and normalization, vertices for a face can be arranged in a descending order:

where v_idx[i, 0], v_idx[i, 1], and v_idx[i, 2] are vertex indices associated with a face i. A vertex can be represented by a 2D array of vertex indices:

where v_idx[i, w] is a vertex index associated with face i and an index w within the face. Vertex rotation can achieve vertex index arrangement while preserving the normal of a face to be oriented in the same direction as the original face. As described above, the normal of a face can be determined by a right-hand rule, or right-hand coordinate system. For example, valid rotations can include:

where f[i](0, 1, 2), f[i](1, 2, 0), and f[i](2, 0, 1) are faces with vertex indexes 0, 1, and 2. The faces can be sorted in ascending order such that the first vertex index of the first face is guaranteed to be less than or equal to the first index of the second face:

where v_idx[i, 0] is a vertex index associated with face i and v_idx[i-1, 0] is a vertex index associated with a face preceding face i. The faces are then sorted such that:

where v_idx[i, 1] is a vertex index associated with face i and v_idx[i-1, 1] is a vertex index associated with a face preceding face i. The faces can then be sorted such that:

where v_idx[i, 2] is a vertex index associated with face i and v_idx[i-1, 2] is a vertex index associated with a face preceding face i. In this way, the vertex indices of all faces can be sorted in descending order, and all faces can be sorted in ascending order without compromising the information stored within.

FIG.3Billustrates an example 330 of a connectivity video frame, according to various embodiments of the present disclosure. In various embodiments, the example 330 can be associated with the third stage of the example method described above. In the composition of a video frame for connectivity information coding, a one-dimensional (1D) connectivity component of a mesh frame (e.g., face list) is transformed to a two-dimensional (2D) connectivity image (e.g., connectivity coding sample array). In the 2D connectivity image, each vertex index in the original vertex list (e.g., v_idx[i, w]) can be represented by a sorted vertex index in a sorted vertex index list (e.g., v_idx_s[j, i, w]). In the 2D connectivity image, each face of a block j (e.g., f[j, i]) can be defined by three sorted vertices (e.g., v_idx_s[j, i, 0], v_idx_s[j, i, 1], v_idx_s [j, I, 2]).

The 1D connectivity components of the mesh frame (e.g., face list, mesh connectivity component frame) can be converted to a 2D connectivity image (e.g., video connectivity frame) based on a transformation process that can be referred to as packing. By packing the 1D connectivity components into a 2D connectivity image, video codecs can be leveraged for connectivity information coding. The resolution of the video connectivity frame, such as width and height, can be defined by a total number of faces in the mesh frame. Each face information can be represented by a 3 vertex index that can be transformed to a connectivity coding unit (CCU) and mapped to a pixel of a video frame. The connectivity video resolution can be selected by a mesh encoder to compose an appropriate video frame. For example, a connectivity information packing strategy can generate a video frame (e.g., 2D image) with an aspect ratio close to 1:1 with a constraint to keep a resolution of the video frame a multiple of 32, 64, 128, or 256 samples. This connectivity information packing strategy would generate an appropriate video frame that can leverage various video coding solutions for coding.

As part of the packing process, the faces that belong to the same blocks are grouped first. A block may be mapped to a particular slice of a video connectivity frame. Doing so can facilitate spatial random access and partial reconstruction of a mesh frame. Each block in a video connectivity frame can be denoted by an index (e.g., j). A pixel in a connectivity video frame can be referred to as a connectivity coding sample (e.g., f_c[j, i]). The connectivity coding sample can be made up of elements representing differential values between one face vertex index (e.g., v{idx[j, i]) and another face vertex index (e.g., v_idx[j, i-1]). For example,

where f_c[j, i] is a connectivity coding sample and f[j, i] and f[j, i-1] are values of vertex indices. A connectivity coding sample can include three components (e.g., differential values). For example,

where f_c[j, i] is a connectivity coding sample, dv_idx[j, i, 0], dv_idx[j, i, 1], and dv_idx[j, i, 0] are differential values of vertex indices of two vertices, and C is a constant value based on video codec bit depth. In general, dv_idx[j, i, w] can represent the differential value of the vertex indexes of two vertices. v_idx_s[j, i, w] can represent a three-dimensional (3D) array representing vertex v_idx[i, w] of a connectivity component in block j of a mesh frame. The constant value C, which can depend on a video codec bit depth, can be defined as:

where bitDepth is a video codec bit depth. From these, the differential values of vertex indices of that make up a connectivity coding sample can be:

where dv_idx[j, i, 0], dv_idx[j, i, 1], and dv_idx[j, i, 2] are differential values of vertex indices, v_idx_s[j, i, 0], v_idx_s[j, i, 1], v_idx_s[j, i, 2], v_idx_s[j, i-1, 0], v_idx_s[j, i-1, 1], and v_idx_s[j, i-1, 2] are 3D arrays representing vertices, and C is a constant corresponding with a video codec bit depth. In various embodiments, information on the number of vertices in a block can be signaled in a data set for block information. The packing performed can be in a raster-scan order.

As illustrated inFIG.3B, a connectivity video frame332acan have a can have a connectivity video frame origin [0, 0]322b. The connectivity video frame332acan have a connectivity video frame width332cand a connectivity video height332d. As described above, connectivity components can be packed into blocks within the connectivity video frame322a. In the connectivity video frame322a, a block BLK[j]334includes several connectivity coding samples338aand338b. The block BLK[j]334origin (e.g., origin sample index) in the connectivity video frame332acan be derived as:

where BLK[j] Y and BLK[j] X are vertical and horizontal coordinates, respectively, of the BLK[j]334origin. N[j] is a number of connectivity coding samples in BLK[j]334, and ccf_width and ccf_height are the width and height, respectively of the connectivity video frame332a. As illustrated in block BLK[j+1]336, the connectivity coding samples are packed in accordance with a connectivity coding sample packing order340(e.g., raster-scan order).

FIG.3Cillustrates an example workflow350associated with connectivity information encoding, according to various embodiments of the present disclosure. For illustrative purposes, the example workflow350can demonstrate an example of a complete workflow for encoding 3D content. As illustrated inFIG.3C, at step352, the workflow350begins with connectivity information coding. At step354, mesh frame i is received. The mesh frame can be received, for example, from a receiver or other input device. At step356, the vertices in a connectivity frame are pre-processed. The pre-processing can be performed, for example, by:

where v_idx[i, 0], v_idx[i-1, 0], v_idx[i, 1], and v_idx[i, 2] are vertex indices and face f(0, 1, 2) is a face. At step358, the mesh frame i is segmented into blocks. For example, the mesh frame i can be segmented into blocks [0 . . . J-1]. At step360, connectivity information is segmented into blocks. Step360can involve converting a 2D vertex list to a 3D vertex list. For example, step360can be performed by:

FIG.4illustrates a computing component400that includes one or more hardware processors402and machine-readable storage media404storing a set of machine-readable/machine-executable instructions that, when executed, cause the one or more hardware processors402to perform an illustrative method for coding and decoding connectivity information, according to various embodiments of the present disclosure. For example, the computing component400can perform functions described with respect toFIGS.1A-11,2A-2B, and3A-3C. The computing component400may be, for example, the computing system500ofFIG.5. The hardware processors402may include, for example, the processor(s)504ofFIG.5or any other processing unit described herein. The machine-readable storage media404may include the main memory506, the read-only memory (ROM)508, the storage510ofFIG.5, and/or any other suitable machine-readable storage media described herein.

At block406, the hardware processor(s)402may execute the machine-readable/machine-executable instructions stored in the machine-readable storage media404to process 3D content into segments, each segment comprising a set of faces and vertex indices representative of the 3D content.

At block408, the hardware processor(s)402may execute the machine-readable/machine-executable instructions stored in the machine-readable storage media404to process each segment to sort the respective set of faces and vertex indices in each segment.

At block410, the hardware processor(s)402may execute the machine-readable/machine-executable instructions stored in the machine-readable storage media404to pack each segment of 3D content to generate connectivity information frames of blocks, each block comprising a subset of the sorted faces and vertex indices.

At block412, the hardware processor(s)402may execute the machine-readable/machine-executable instructions stored in the machine-readable storage media404to encode the connectivity information frames.

FIG.5illustrates a block diagram of an example computer system500in which various embodiments of the present disclosure may be implemented. The computer system500can include a bus502or other communication mechanism for communicating information, one or more hardware processors504coupled with the bus502for processing information. The hardware processor(s)504may be, for example, one or more general purpose microprocessors. The computer system500may be an embodiment of a video encoding module, video decoding module, video encoder, video decoder, or similar device.

The computer system500can also include a main memory506, such as a random access memory (RAM), cache and/or other dynamic storage devices, coupled to the bus502for storing information and instructions to be executed by the hardware processor(s)504. The main memory506may also be used for storing temporary variables or other intermediate information during execution of instructions by the hardware processor(s)504. Such instructions, when stored in a storage media accessible to the hardware processor(s)504, render the computer system500into a special-purpose machine that can be customized to perform the operations specified in the instructions.

The computer system500can further include a read only memory (ROM)508or other static storage device coupled to the bus502for storing static information and instructions for the hardware processor(s)504. A storage device510, such as a magnetic disk, optical disk, or USB thumb drive (Flash drive), etc., can be provided and coupled to the bus502for storing information and instructions.

Computer system500can further include at least one network interface512, such as a network interface controller module (NIC), network adapter, or the like, or a combination thereof, coupled to the bus502for connecting the computer system700to at least one network.

The computer system500may implement the techniques or technology described herein using customized hard-wired logic, one or more ASICs or FPGAs, firmware and/or program logic which in combination with the computer system700that causes or programs the computer system500to be a special-purpose machine. According to one or more embodiments, the techniques described herein are performed by the computer system700in response to the hardware processor(s)504executing one or more sequences of one or more instructions contained in the main memory506. Such instructions may be read into the main memory506from another storage medium, such as the storage device510. Execution of the sequences of instructions contained in the main memory506can cause the hardware processor(s)504to perform process steps described herein. In alternative embodiments, hard-wired circuitry may be used in place of or in combination with software instructions.

The term “non-transitory media,” and similar terms, as used herein refers to any media that store data and/or instructions that cause a machine to operate in a specific fashion. Such non-transitory media may comprise non-volatile media and/or volatile media. The non-volatile media can include, for example, optical or magnetic disks, such as the storage device510. The volatile media can include dynamic memory, such as the main memory506. Common forms of the non-transitory media include, for example, a floppy disk, a flexible disk, hard disk, solid state drive, magnetic tape, or any other magnetic data storage medium, a CD-ROM, any other optical data storage medium, any physical medium with patterns of holes, a RAM, a PROM, an EPROM, a FLASH-EPROM, an NVRAM, any other memory chip or cartridge, and networked versions of the same.

Non-transitory media is distinct from but may be used in conjunction with transmission media. The transmission media can participate in transferring information between the non-transitory media. For example, the transmission media can include coaxial cables, copper wire and fiber optics, including the wires that comprise the bus502. The transmission media can also take a form of acoustic or light waves, such as those generated during radio-wave and infra-red data communications.

The computer system500also includes a network interface518coupled to bus502. Network interface518provides a two-way data communication coupling to one or more network links that are connected to one or more local networks. For example, network interface518may be an integrated services digital network (ISDN) card, cable modem, satellite modem, or a modem to provide a data communication connection to a corresponding type of telephone line. As another example, network interface518may be a local area network (LAN) card to provide a data communication connection to a compatible LAN (or WAN component to communicated with a WAN). Wireless links may also be implemented. In any such implementation, network interface518sends and receives electrical, electromagnetic or optical signals that carry digital data streams representing various types of information.

The computer system500can send messages and receive data, including program code, through the network(s), network link and network interface518. In the Internet example, a server might transmit a requested code for an application program through the Internet, the ISP, the local network and the network interface518.