Cost-driven framework for progressive compression of textured meshes

Patent metadata

Field	Value
Publication number	US-10977773-B2
Application number	US-201916279319-A
Country	US
Kind code	B2
Filing date	Feb 19, 2019
Priority date	Feb 19, 2019
Publication date	Apr 13, 2021
Grant date	Apr 13, 2021

Abstract

Techniques of compressing level of detail (LOD) data involve defining a cost metric that predicts how much computing resources are necessary to decode and render a mesh at a given LOD. The cost metric may be optimized by a selection of a LOD reduction process of a plurality of processes at each LOD reduction step. For each process of the plurality of processes, the LOD is reduced according to that process and the resulting reduced LOD is evaluated according to the cost metric. Each such process at that LOD reduction step produces a respective LOD, which includes a mesh, one or more texture atlases, and/or other attributes. The LOD produced by the process having the lowest value of the cost metric at a reduction step is the LOD that is input into the next LOD reduction step.

First claim

What is claimed is:

1. A method, comprising:
obtaining, by processing circuitry of a server computer configured to encode information related to a surface of a three-dimensional object, data representing a first level of detail (LOD), the first LOD including a first triangular mesh, the first level of detail (LOD) being lower than or equal to a reference LOD that includes a reference mesh;
performing, by the processing circuitry, a plurality of LOD reduction operations on the first LOD to produce a plurality of candidate LODs and a plurality of recovery bitstreams, each of the plurality of candidate LODs including a respective candidate triangular mesh of a plurality of candidate triangular meshes and being lower than the first LOD, each of the plurality of recovery bitstreams being associated with a respective candidate LOD of the plurality of candidate LODs;
performing, by the processing circuitry, a distortion measurement operation on each of the plurality of candidate LODs to produce a measure of distortion from the reference LOD of a plurality of measures of distortion from the reference LOD corresponding to that candidate LOD;
generating, by the processing circuitry, a respective value of a LOD cost metric associated with each of the plurality of candidate LODs, the LOD cost metric being based on (i) the measure of distortion of the plurality of measures of distortion corresponding to that candidate LOD and (ii) a size of the recovery bitstream associated with that candidate LOD; and
performing, by the processing circuitry, a candidate selection operation on the values of the LOD cost metric for each of the plurality of candidate LODs to produce a second LOD, the second LOD being lower than the first LOD, the candidate selection operation being configured to (i) select, as the second LOD, the candidate triangular mesh of the plurality of candidate LODs associated with the smallest of the values of the LOD cost metric and (ii) select the recovery bitstream of the plurality of recovery bitstreams associated with the second LOD, the recovery bitstream enabling a recovery of the first LOD from the second LOD.

2. The method as in claim 1 , wherein the value of the LOD cost metric associated with each of the plurality of candidate LODs includes a product of a difference between a measure of distortion of the first LOD and the measure of distortion corresponding to that candidate LOD and the size of the recovery bitstream associated with that candidate LOD.

3. The method as in claim 1 , wherein the reference LOD is the first LOD.

4. The method as in claim 1 , wherein performing the plurality of LOD reduction operations on the first LOD includes performing a mesh decimation operation on the first triangular mesh to produce a candidate LOD and obtaining the recovery bitstream associated with the candidate LOD.

5. The method as in claim 4 , wherein the first triangular mesh further includes a plurality of vertices and a plurality of edges, each of the plurality of edges including a respective pair of vertices of the plurality of vertices of the triangular mesh, and
wherein performing the mesh decimation operation on the first triangular mesh includes performing a batch vertex removal operations on the first triangular mesh.

6. The method as in claim 4 , wherein the first triangular mesh further includes a plurality of vertices and a plurality of edges, each of the plurality of edges including a respective pair of vertices of the plurality of vertices of the triangular mesh, and
wherein performing the mesh decimation operation on the first triangular mesh includes performing a batch of edge collapse operations on the first triangular mesh.

7. The method as in claim 6 , where the batch of edge collapse operations is a batch of half-edge collapses.

8. The method as in claim 6 , where the batch of edge collapse operations is a batch of full-edge collapses.

9. The method as in claim 6 , where the batch of edge collapse operations is a batch of mid-edge collapses.

10. The method as in claim 6 , wherein the vertices of an edge of the plurality of edges of the first triangular mesh are on a seam of a set of seam edges, and wherein performing the batch of edge-collapse operations includes performing an edge collapse operation on another edge of the plurality of edges of the first triangular mesh.

11. The method as in claim 10 , further comprising:
generating the set of seam edges from the set of edges of the mesh of the first LOD according to an abstraction of the reference LOD, the abstraction including a polygonal mesh, the polygonal mesh including a plurality of vertices, a plurality of edges, and a plurality of faces.

12. The method as in claim 11 , where the set of seam edges is selected such that it is a subdivision of edge chains, where the subdivision forms a one to one correspondence to the set of edges of the abstraction.

13. The method as in claim 11 , where the set of seam edges is selected such that it subdivides the first triangular mesh into a set of connected components that forms a one to one correspondence to the plurality of faces of the polygonal mesh of the abstraction.

14. The method as in claim 11 , further comprising:
generating the abstraction from the reference LOD, the abstraction having a measure of distortion from the reference LOD that is less than a specified measure of distortion.

15. The method as in claim 11 , wherein the first LOD further includes a first texture atlas, the first texture atlas including a set of seams defining boundaries of a set of patches, each of the set of patches including an image configured to be superimposed onto a set of mesh triangles of the first triangular mesh,
wherein the vertices of an edge of the plurality of edges of the first triangular mesh are on a seam of the set of seams of the abstraction, and
wherein performing the batch of edge-collapse operations includes performing an edge collapse operation on another edge of the plurality of edges of the first triangular mesh.

16. The method as in claim 11 , wherein the polygonal mesh of the abstraction and the reference mesh each include a respective plurality of triangular faces,
wherein the reference LOD includes a reference texture atlas, including an embedding of each triangular face of the plurality of triangular faces of the reference LOD into a coordinate space of a reference texture image, and
wherein the method further comprises:
performing a re-atlasing operation on the reference texture atlas, the re-atlasing operation providing a conversion of the reference atlas to a texture atlas of the abstraction, to produce, as a texture atlas of the abstraction, an abstracted atlas, the abstracted atlas including a set of patches, each of the set of patches of the abstracted atlas being mapped onto a triangular face of the plurality of triangular faces of the polygonal mesh of the abstraction.

17. The method as in claim 1 , wherein the first triangular mesh includes a plurality of vertices, and
wherein performing the plurality of LOD reduction operations on the first LOD includes performing a quantization operation on coordinates of the plurality of vertices of the first triangular mesh and generating a recovery bitstream for the coordinates.

18. The method as in claim 17 , wherein performing the quantization operation includes decrementing a number of bits used in representing the coordinates of the plurality of vertices.

19. The method as in claim 1 , wherein the first triangular mesh further includes a plurality of trian

Assignees

• Google Llc

Inventors

• Hemmer Michael
• Alliez Pierre
• Portaneri Cedric

Classifications

• G06T9/001 Primary

  Model-based coding, e.g. wire frame · CPC title

• G06T9/00

  Image coding (bandwidth or redundancy reduction for static pictures H04N1/41; coding or decoding of static colour picture signals H04N1/64; methods or arrangements for coding, decoding, compressing or decompressing digital video signals H04N19/00) · CPC title

• G06T3/4023 Primary

  based on decimating pixels or lines of pixels; based on inserting pixels or lines of pixels · CPC title

• G06T2210/36

  Level of detail · CPC title

• G06T17/205

  Re-meshing · CPC title