Valence based implicit traversal for improved compression of triangular meshes

Patent metadata

Field	Value
Publication number	US-10553035-B2
Application number	US-201715612689-A
Country	US
Kind code	B2
Filing date	Jun 2, 2017
Priority date	Jun 2, 2017
Publication date	Feb 4, 2020
Grant date	Feb 4, 2020

Abstract

In one general aspect, a method can include receiving, by processing circuitry of a computer configured to represent information related to a three-dimensional object, a plurality of vertices of a triangular mesh representing the three-dimensional object, the triangular mesh including a plurality of faces, each if the plurality of faces including three vertices of the plurality of vertices; generating a traversal order for the vertices of the triangular mesh based on valences of the plurality of vertices; producing an array of errors between predicted vertices and vertices of the plurality of vertices, the array of errors being arranged in a sequence based on the traversal order; and performing a compression operation on the array of differences to produce a compressed error array, the compressed error array producing the plurality of vertices of the triangular mesh in response to a decompression operation.

First claim

What is claimed is:

1. A method, comprising:
receiving, by processing circuitry of a computer configured to process information related to a three-dimensional object, a plurality of vertices of a triangular mesh representing the three-dimensional object, the triangular mesh including a plurality of faces, each of the plurality of faces defined by three vertices of the plurality of vertices;
generating, by the processing circuitry, a traversal order for the vertices of the triangular mesh based on valences of the plurality of vertices, including generating a value of a penalty function for a set of neighboring vertices of the plurality of vertices not on a current face of the plurality of faces;
producing, by the processing circuitry, an array of errors between predicted vertices and vertices of the plurality of vertices, the errors in the array of errors being arranged in a sequence based on the traversal order; and
performing, by the processing circuitry, a compression operation on the array of errors to produce a compressed error array, the compressed error array being used to produce the plurality of vertices of the triangular mesh in response to a decompression operation.

2. The method as in claim 1 , wherein
the value of the penalty function is based on the valence of each vertex included in the current face and a valence of the set of neighboring vertices; and
wherein generating the traversal order includes selecting, as the neighboring vertex from which the error of the array of errors is produced, the neighboring vertex of the set of neighboring vertices for when the value of the penalty function satisfies a condition.

3. The method as in claim 2 , wherein generating the value of the penalty function for each of the set of neighboring vertices includes:
producing a first difference between the valence of a first vertex of the current face and the valence of a second vertex of the current face;
producing a second difference between the valence of a third vertex of the current face and the valence of the neighboring vertex; and
producing, as the value of the penalty function, a sum of the first difference and the second difference.

4. The method as in claim 2 , wherein the generating the value of the penalty function for each of the set of neighboring vertices includes:
producing a first difference between the valence of a first vertex of the current face and the valence of a second vertex of the current face;
producing a second difference between the valence of a third vertex of the current face and the valence of the neighboring vertex;
generating a first weight and a second weight based on a predefined criterion; and
summing a product of the first weight and the first difference and a product of the second weight and the second difference.

5. The method as in claim 2 , wherein the generating the value of the penalty function for each of a set of neighboring vertices includes:
producing a first difference between the valence of a first vertex of the current face and the valence of a second vertex of the current face;
producing a second difference between the valence of a third vertex of the current face and the valence of the neighboring vertex;
generating a first weight and a second weight based whether the neighboring vertex is a corner vertex of the triangular mesh; and
summing a product of the first weight and the first difference and a product of the second weight and the second difference.

6. The method as in claim 2 , further comprising:
generating a priority queue into which each of the set of neighboring vertices is placed according to the value of the penalty function;
performing an assessment as to whether any vertices of the plurality of vertices would be excluded from the production of the array of differences based on the traversal order generated based on the selection of the neighboring vertex; and
in response to the selection of the neighboring vertex excluding another vertex of the plurality of vertices, selecting, as the neighboring vertex from which the error of the array of errors is produced, the neighboring vertex of the set of neighboring vertices that is next in the priority queue.

7. A computer program product comprising a non-transitory storage medium, the computer program product including code that, when executed by processing circuitry of a user device configured to process information related to a three-dimensional object, causes the processing circuitry to perform a method, the method comprising:
receiving a plurality of vertices of a triangular mesh representing the three-dimensional object, the triangular mesh including a plurality of faces, each of the plurality of faces including three vertices of the plurality of vertices;
generating a traversal order for the vertices of the triangular mesh based on valences of the plurality of vertices, including generating a value of a penalty function for a set of neighboring vertices of the plurality of vertices not on a current face of the plurality of faces;
producing an array of errors between predicted vertices and vertices of the plurality of vertices, the array of errors being arranged in a sequence based on the traversal order; and
performing a compression operation on the array of errors to produce a compressed error array, the compressed error array being used to produce the plurality of vertices of the triangular mesh in response to a decompression operation.

8. The computer program product as in claim 7 , wherein
the value of the penalty function is based on the valence of each vertex included in the current face and a valence of the set of neighboring vertices; and
wherein generating the traversal order includes selecting, as the neighboring vertex from which the error of the array of errors is produced, the neighboring vertex of the set of neighboring vertices for which the value of the penalty function satisfies a condition.

9. The computer program product as in claim 8 , wherein generating the value of the penalty function for each of the set of neighboring vertices includes:
producing a first difference between the valence of a first vertex of the current face and the valence of a second vertex of the current face;
producing a second difference between the valence of a third vertex of the current face and the valence of the neighboring vertex; and
producing, as the value of the penalty function, a sum of the first difference and the second difference.

10. The computer program product as in claim 8 , wherein generating the value of the penalty function for each of the set of neighboring vertices includes:
producing a first difference between the valence of a first vertex of the current face and the valence of a second vertex of the current face;
producing a second difference between the valence of a third vertex of the current face and the valence of the neighboring vertex;
generating a first weight and a second weight based on a predefined criterion; and
summing a product of the first weight and the first difference and a product of the second weight and the second difference.

11. The computer program product as in claim 8 , wherein generating the respective value of the penalty function for a neighboring vertex includes:
producing a first difference between the valence of a first vertex of the current face and the valence of a second vertex of the current face;
producing a second difference between the valence of a third vertex of the current face and the valence of the neighboring vertex;
generating a first weight and a second weight based whether the neighboring vertex is a corner vertex of the triangular mesh; and
summing a product of the first we

Assignees

• Google Inc
• Google Llc

Inventors

• Hemmer Michael
• Stava Ondrej

Classifications

• G06T15/80

  Shading · CPC title

• H04N19/61

  in combination with predictive coding · CPC title

• H04N19/30

  using hierarchical techniques, e.g. scalability (H04N19/63 takes precedence) · CPC title

• H04N19/27

  involving both synthetic and natural picture components, e.g. synthetic natural hybrid coding [SNHC] · CPC title

• G06T19/20 Primary

  Editing of three-dimensional [3D] images, e.g. changing shapes or colours, aligning objects or positioning parts · CPC title