Systems and methods for storing triangulations of polygonal mesh faces

A non-transitory computer-readable storage medium storing instructions that, when executed by one or more processors, causes a computing device to retrieve a stored triangulation of a polygonal mesh, by performing the steps of:

• receiving an input polygonal mesh that is a computer representation of a three-dimensional (3D) object;
• identifying one or more faces of the input polygonal mesh that have more than three edges;
• retrieving for each face of the one or more faces, integer counts of a number of triangles that are incident to each vertex of the face stored in face-vertex properties of the face, wherein a specific triangulation of the face is represented by the number of triangles that are incident to each vertex of the face;
• and
• generating a triangulated polygonal mesh corresponding to the input polygonal mesh by triangulating, for each face of the one or more faces, the face based on the integer counts of the number of triangles that are incident to each vertex of the face stored in the face-vertex properties;
• wherein for each face of the one or more faces of the input polygonal mesh, edges of the face form a polygonal boundary for the face;
• and
• wherein generating the triangulated polygonal mesh corresponding to the input polygonal mesh comprises:
• for a first face of the one or more faces:
• selecting a first vertex in the polygonal boundary of the first face having an integer count of the number of triangles that are incident to the first vertex equal to 1;
• forming a triangle by creating an edge between a second vertex and a third vertex of the first face, wherein the second vertex and the third vertex are adjacent vertices to the first vertex in the polygonal boundary of the first face;
• updating the polygonal boundary of the first face by removing edges incident on the first vertex from the polygonal boundary and adding the edge formed between the second vertex and the third vertex to the polygonal boundary;
• and
• decrementing by 1 the integer counts of the number of triangles that are incident to the first vertex, the second vertex, and the third vertex.

A device for retrieving a stored triangulation of a polygonal mesh, the device comprising:

• a memory storing instructions;
• and
• one or more processors configured to the execute the instructions to cause the device to:
• receive an input polygonal mesh that is a computer representation of a three-dimensional (3D) object;
• identify one or more faces of the input polygonal mesh that have more than three edges;
• retrieve for each face of the one or more faces, integer counts of a number of triangles that are incident to each vertex of the face stored in face-vertex properties of the face, wherein a specific triangulation of the face is represented by the number of triangles that are incident to each vertex of the face;
• and
• generate a triangulated polygonal mesh corresponding to the input polygonal mesh by triangulating, for each face of the one or more faces, the face based on the integer counts of the number of triangles that are incident to each vertex of the face stored in the face-vertex properties;
• wherein for each face of the one or more faces of the input polygonal mesh, edges of the face form a polygonal boundary for the face;
• and
• wherein generating the triangulated polygonal mesh corresponding to the input polygonal mesh comprises:
• for a first face of the one or more faces:
• selecting a first vertex in the polygonal boundary of the first face having an integer count of the number of triangles that are incident to the first vertex equal to 1;
• forming a triangle by creating an edge between a second vertex and a third vertex of the first face, wherein the second vertex and the third vertex are adjacent vertices to the first vertex in the polygonal boundary of the first face;
• updating the polygonal boundary of the first face by removing edges incident on the first vertex from the polygonal boundary and adding the edge formed between the second vertex and the third vertex to the polygonal boundary;
• and
• decrementing by 1 the integer counts of the number of triangles that are incident to the first vertex, the second vertex, and the third vertex.