# US 12,182,941 B2 · Systems and methods for storing triangulations of polygonal mesh faces > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 12,182,941 B2 - Document ID: US12182941B2 - Status: Granted - Kind: B2 - Application number: 17/977,259 - Filed: 2022-10-31 - Published: 2024-05-02 - Granted: 2024-12-31 - Earliest claimed: 2022-10-31 - Assignees: Electronic Arts Inc. - Applicants: Electronic Arts Inc. - Inventors: Ashton Mason - Web page: https://patentgrep.com/patent/US12182941B2 ## CPC - G06T 17/20: Finite element generation, e.g. wire-frame surface description, {tesselation} - G06T 17/205: {Re-meshing} - G06T 17/10: Constructive solid geometry [CSG] using solid primitives, e.g. cylinders, cubes - G06T: IMAGE DATA PROCESSING OR GENERATION, IN GENERAL ## Abstract A method, device, and computer-readable storage medium for retrieving a stored triangulation of a polygonal mesh. The method includes: 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. ## Claims ### Claim 1 A method for retrieving a stored triangulation of a polygonal mesh, the method comprising: receiving, by one or more processors, an input polygonal mesh that is a computer representation of a three-dimensional (3D) object; identifying, by the one or more processors, one or more faces of the input polygonal mesh that have more than three edges; retrieving, by the one or more processors, 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, by the one or more processors, 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, by the one or more processors, 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, by the one or more processors, 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, by the one or more processors, 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, by the one or more processors, the integer counts of the number of triangles that are incident to the first vertex, the second vertex, and the third vertex. ### Claim 2 (depends on 1) The method according to claim 1, wherein the face-vertex properties of the face are stored in a half-edge data structure. ### Claim 3 (depends on 1) The method according to claim 1, wherein the input polygonal mesh is one of multiple polygonal meshes each being a computer representation of the same 3D object, wherein each polygonal mesh of the multiple polygonal meshes is a geometrically distorted version having the same topology. ### Claim 4 (depends on 3) The method according to claim 3, wherein for corresponding faces among the multiple polygonal meshes, the integer counts of the number of triangles that are incident to each vertex of the face stored in the face-vertex properties of the face are the same, representing the same specific triangulation of the faces among the multiple polygonal meshes. ### Claim 5 (depends on 1) The method according to claim 1, further comprising: for each face of the one or more faces of the input polygonal mesh, storing, by the one or more processors, the integer counts of the number of triangles that are incident to each vertex of the face in the face-vertex properties of the face, comprising: selecting, by the one or more processors, the first face of the input polygonal mesh; triangulating, by the one or more processors, the first face using a triangulation algorithm; and storing, by the one or more processors, the integer counts of the number of triangles that are incident to each vertex of the first face in the face-vertex properties of the first face based on the triangulating. ### Claim 6 (depends on 5) The method according to claim 5, wherein the triangulation algorithm comprises a triangle fan algorithm or a Delaunay triangulation algorithm. ### Claim 7 (depends on 5) The method according to claim 5, wherein triangulating the first face using the triangulation algorithm comprises: determining, by the one or more processors, that vertices of the first face are not co-planar; determining, by the one or more processors, a vertex normal for each vertex of the first face; computing, by the one or more processors, an average vertex normal among the vertex normals for the vertices of the first face; projecting, by the one or more processors, the first face to a two-dimensional (2D) shape in a direction of the average vertex normal; and triangulating, by the one or more processors, the 2D shape using the triangulation algorithm. ### Claim 8 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. ### Claim 9 (depends on 8) The computer-readable storage medium according to claim 8, wherein the face-vertex properties of the face are stored in a half-edge data structure. ### Claim 10 (depends on 8) The computer-readable storage medium according to claim 8, wherein the input polygonal mesh is one of multiple polygonal meshes each being a computer representation of the same 3D object, wherein each polygonal mesh of the multiple polygonal meshes is a geometrically distorted version having the same topology. ### Claim 11 (depends on 10) The computer-readable storage medium according to claim 10, wherein for corresponding faces among the multiple polygonal meshes, the integer counts of the number of triangles that are incident to each vertex of the face stored in the face-vertex properties of the face are the same, representing the same specific triangulation of the faces among the multiple polygonal meshes. ### Claim 12 (depends on 8) The computer-readable storage medium according to claim 8, further comprising: for each face of the one or more faces of the input polygonal mesh, storing the integer counts of the number of triangles that are incident to each vertex of the face in the face-vertex properties of the face, comprising: selecting the first face of the input polygonal mesh; triangulating the first face using a triangulation algorithm; and storing the integer counts of the number of triangles that are incident to each vertex of the first face in the face-vertex properties of the first face based on the triangulating. ### Claim 13 (depends on 12) The computer-readable storage medium according to claim 12, wherein the triangulation algorithm comprises a triangle fan algorithm or a Delaunay triangulation algorithm. ### Claim 14 (depends on 12) The computer-readable storage medium according to claim 12, wherein triangulating the first face using the triangulation algorithm comprises: determining that vertices of the first face are not co-planar; determining a vertex normal for each vertex of the first face; computing an average vertex normal among the vertex normals for the vertices of the first face; projecting the first face to a two-dimensional (2D) shape in a direction of the average vertex normal; and triangulating the 2D shape using the triangulation algorithm. ### Claim 15 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. ### Claim 16 (depends on 15) The device according to claim 15, wherein the input polygonal mesh is one of multiple polygonal meshes each being a computer representation of the same 3D object, wherein each polygonal mesh of the multiple polygonal meshes is a geometrically distorted version having the same topology; and wherein for corresponding faces among the multiple polygonal meshes, the integer counts of the number of triangles that are incident to each vertex of the face stored in the face-vertex properties of the face are the same, representing the same specific triangulation of the faces among the multiple polygonal meshes. ### Claim 17 (depends on 15) The device according to claim 15, further comprising: for each face of the one or more faces of the input polygonal mesh, storing the integer counts of the number of triangles that are incident to each vertex of the face in the face-vertex properties of the face, comprising: selecting the first face of the input polygonal mesh; triangulating the first face using a triangulation algorithm, wherein the triangulation algorithm comprises a triangle fan algorithm or a Delaunay triangulation algorithm; and storing the integer counts of the number of triangles that are incident to each vertex of the first face in the face-vertex properties of the first face based on the triangulating.