# US 12,008,716 B2 · Systems and methods for generating a simplified polygonal mesh > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 12,008,716 B2 - Document ID: US12008716B2 - Status: Granted - Kind: B2 - Application number: 17/530,952 - Filed: 2021-11-19 - Published: 2023-05-25 - Granted: 2024-06-11 - Earliest claimed: 2021-11-19 - Assignees: Electronic Arts Inc. - Applicants: Electronic Arts Inc. - Inventors: Ashton Mason - Web page: https://patentgrep.com/patent/US12008716B2 ## CPC - G06T 17/205: {Re-meshing} - G06T 2210/36: Level of detail - G06T: IMAGE DATA PROCESSING OR GENERATION, IN GENERAL ## Abstract A method, device, and computer-readable storage medium for generating a simplified mesh. The method includes: receiving an input mesh that is a polygonal mesh; identifying one or more submeshes of the input mesh; fitting a set of shapes to the one or more submeshes to determine which shapes approximate which submeshes within a threshold value; for each submesh that is associated with at least one shape that approximates the submesh within the threshold value, generating a set of proxy levels-of-detail (LODs) for the submesh, wherein each proxy LOD is a polygonal mesh corresponding to the shape that approximates the submesh; generating for each submesh, a set of traditionally simplified levels-of-detail (LODs) based on simplifying the submesh; and generating the simplified mesh based on selecting one proxy LOD or one traditionally simplified LOD for each submesh of the one or more submeshes. ## Claims ### Claim 1 A method for generating a simplified mesh, the method comprising: receiving, by one or more processors, an input mesh, wherein the input mesh comprises a polygonal mesh that is a computer representation of a three-dimensional (3D) object; identifying, by the one or more processors, one or more submeshes of the input mesh, wherein each submesh of the one or more submeshes comprises a polygonal mesh; fitting, by the one or more processors, a set of shapes to the one or more submeshes to determine which shapes in the set of shapes approximate which submeshes of the one or more submeshes within a threshold value; for each submesh that is associated with at least one shape that approximates the submesh within the threshold value, generating, by the one or more processors, a set of proxy levels-of-detail (LODs) for the submesh, wherein each proxy LOD is a polygonal mesh corresponding to the at least one shape that approximates the submesh; generating, by the one or more processors, for each submesh of the one or more submeshes, a set of traditionally simplified levels-of-detail (LODs) for the submesh, wherein each traditionally simplified LOD is a polygonal mesh generated based on simplifying the submesh; and generating, by the one or more processors, the simplified mesh based on selecting one proxy LOD or one traditionally simplified LOD for each submesh of the one or more submeshes. ### Claim 2 (depends on 1) The method according to claim 1, wherein, for a given submesh, each traditionally simplified LOD of the given submesh is a polygonal mesh generated based on simplifying the submesh via edge collapse operations. ### Claim 3 (depends on 1) The method according to claim 1, further comprising: grouping the one or more submeshes into an initial set of one or more root groups; for a first root group of the one or more root groups, identifying a subset of submeshes of the first root group, wherein the subset of submeshes corresponds to a shape in the set of shapes that approximates the subset of submeshes within the threshold value; and generating a proxy LOD for the subset of submeshes of the first root group corresponding to the shape in the set of shapes that approximates the subset of submeshes. ### Claim 4 (depends on 3) The method according to claim 3, further comprising: generating a compound LOD for the subset of submeshes, wherein the compound LOD is formed by combining LODs of the submeshes in the subset of submeshes. ### Claim 5 (depends on 3) The method according to claim 3, wherein the one or more submeshes are grouped into the initial set of one or more root groups based on being associated with a same material or being associated with a same part of the 3D object represented by the input mesh. ### Claim 6 (depends on 1) The method according to claim 1, wherein each proxy LOD and each traditionally simplified LOD is associated with a cost metric and a benefit metric, wherein the cost metric corresponds to an estimated cost of rendering the proxy LOD or the traditionally simplified LOD, and the benefit metric is based on a fidelity metric and an importance metric of the proxy LOD or the traditionally simplified LOD. ### Claim 7 (depends on 6) The method according to claim 6, wherein the estimated cost of rendering the proxy LOD or the traditionally simplified LOD corresponds to a number of polygons of the proxy LOD or the traditionally simplified LOD. ### Claim 8 (depends on 6) The method according to claim 6, wherein the fidelity metric for a given proxy LOD or a given traditionally simplified LOD is based on comparing a first rendered image of the given proxy LOD or the given traditionally simplified LOD with a second rendered image of the submesh corresponding to the given proxy LOD or the given traditionally simplified LOD. ### Claim 9 (depends on 6) The method according to claim 6, wherein the importance metric for a given proxy LOD or a given traditionally simplified LOD is based on comparing a size of a silhouette of the given proxy LOD or the given traditionally simplified LOD with a size of a silhouette of the submesh corresponding to the given proxy LOD or the given traditionally simplified LOD. ### Claim 10 (depends on 6) The method according to claim 6, wherein generating the simplified mesh based on selecting one proxy LOD or one traditionally simplified LOD for each submesh of the one or more submeshes is based on applying an optimization algorithm based on the cost metrics and benefit metrics of the proxy LODs and the traditionally simplified LODs of the one or more submeshes. ### Claim 11 (depends on 1) The method according to claim 1, wherein the set of shapes includes: a box shape, a cylinder shape, a sphere shape, a capsule shape, a convex hull shape, a two-dimensional card shape, or a voxel proxy shape. ### Claim 12 A non-transitory computer-readable storage medium storing instructions that, when executed by one or more processors, causes a computing device to generate a simplified mesh, by performing the steps of: receiving an input mesh, wherein the input mesh comprises a polygonal mesh that is a computer representation of a three-dimensional (3D) object; identifying one or more submeshes of the input mesh, wherein each submesh of the one or more submeshes comprises a polygonal mesh; fitting a set of shapes to the one or more submeshes to determine which shapes in the set of shapes approximate which submeshes of the one or more submeshes within a threshold value; for each submesh that is associated with at least one shape that approximates the submesh within the threshold value, generating a set of proxy levels-of-detail (LODs) for the submesh, wherein each proxy LOD is a polygonal mesh corresponding to the at least one shape that approximates the submesh; generating for each submesh of the one or more submeshes, a set of traditionally simplified levels-of-detail (LODs) for the submesh, wherein each traditionally simplified LOD is a polygonal mesh generated based on the simplifying submesh; and generating the simplified mesh based on selecting one proxy LOD or one traditionally simplified LOD for each submesh of the one or more submeshes. ### Claim 13 (depends on 12) The computer-readable storage medium according to claim 12, the steps further comprising: grouping the one or more submeshes into an initial set of one or more root groups; for a first root group of the one or more root groups, identifying a subset of submeshes of the first root group, wherein the subset of submeshes corresponds to a shape in the set of shapes that approximates the subset of submeshes within the threshold value; and generating a proxy LOD for the subset of submeshes of the first root group corresponding to the shape in the set of shapes that approximates the subset of submeshes. ### Claim 14 (depends on 13) The computer-readable storage medium according to claim 13, the steps further comprising: generating a compound LOD for the subset of submeshes, wherein the compound LOD is formed by combining LODs of the submeshes in the subset of submeshes. ### Claim 15 (depends on 13) The computer-readable storage medium according to claim 13, wherein the one or more submeshes are grouped into the initial set of one or more root groups based on being associated with a same material or being associated with a same part of the 3D object represented by the input mesh. ### Claim 16 (depends on 12) The computer-readable storage medium according to claim 12, wherein each proxy LOD and each traditionally simplified LOD is associated with a cost metric and a benefit metric, wherein the cost metric corresponds an estimated cost of rendering the proxy LOD or the traditionally simplified LOD, and the benefit metric is based on a fidelity metric and an importance metric of the proxy LOD or the traditionally simplified LOD. ### Claim 17 (depends on 16) The computer-readable storage medium according to claim 16, wherein the estimated cost of rendering the proxy LOD or the traditionally simplified LOD corresponds to a number of polygons of the proxy LOD or the traditionally simplified LOD; wherein the fidelity metric for a given proxy LOD or a given traditionally simplified LOD is based on comparing a first rendered image of the given proxy LOD or the given traditionally simplified LOD with a second rendered image of the submesh corresponding to the given proxy LOD or the given traditionally simplified LOD; and wherein the importance metric for a given proxy LOD or a given traditionally simplified LOD is based on comparing a size of a silhouette of the given proxy LOD or the given traditionally simplified LOD with a size of a silhouette of the submesh corresponding to the given proxy LOD or the given traditionally simplified LOD. ### Claim 18 (depends on 16) The computer-readable storage medium according to claim 16, wherein generating the simplified mesh based on selecting one proxy LOD or one traditionally simplified LOD for each submesh of the one or more submeshes is based on applying an optimization algorithm based on the cost metrics and benefit metrics of the proxy LODs and the traditionally simplified LODs of the one or more submeshes. ### Claim 19 (depends on 12) The computer-readable storage medium according to claim 12, wherein the set of shapes includes: a box shape, a cylinder shape, a sphere shape, a capsule shape, a convex hull shape, a two-dimensional card shape, or a voxel proxy shape. ### Claim 20 A device for generating a simplified 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 mesh, wherein the input mesh comprises a polygonal mesh that is a computer representation of a three-dimensional (3D) object; identify one or more submeshes of the input mesh, wherein each submesh of the one or more submeshes comprises a polygonal mesh; fit a set of shapes to the one or more submeshes to determine which shapes in the set of shapes approximate which submeshes of the one or more submeshes within a threshold value; for each submesh that is associated with at least one shape that approximates the submesh within the threshold value, generate a set of proxy levels-of-detail (LODs) for the submesh, wherein each proxy LOD is a polygonal mesh corresponding to the at least one shape that approximates the submesh; generate for each submesh of the one or more submeshes, a set of traditionally simplified levels-of-detail (LODs) for the submesh, wherein each traditionally simplified LOD is a polygonal mesh generated based on simplifying the submesh; and generate the simplified mesh based on selecting one proxy LOD or one traditionally simplified LOD for each submesh of the one or more submeshes.