# US 10,872,469 B2 · System and method for subdividing large polygon mesh datasets into hierarchical subsets for level-of-detail use > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 10,872,469 B2 - Document ID: US10872469B2 - Status: Granted - Kind: B2 - Application number: 16/824,064 - Filed: 2020-03-19 - Published: 2020-09-24 - Granted: 2020-12-22 - Earliest claimed: 2019-03-22 - Assignees: Cesium GS, Inc. - Applicants: Cesium GS, Inc. - Inventors: Kangning Li; Sean Lilley; Daniel Bagnell - Web page: https://patentgrep.com/patent/US10872469B2 ## CPC - G06T 17/205: {Re-meshing} - G06T 2210/36: Level of detail - G06T: IMAGE DATA PROCESSING OR GENERATION, IN GENERAL ## Abstract Systems, methods, devices, and non-transitory media of various embodiments enable subdividing large polygon meshes with diverse materials into a hierarchy of separate components, such as tiles. In various embodiments, the components may in aggregate represent the entire mesh. In the hierarchies of separate components as provided by the various embodiments, the components may be loaded as-needed based on importance, culled due to lack of importance to a given view, and/or replaced with higher or lower detail variants depending on importance to a given view. The ability to load components, such as tiles, on-demand provided by the various embodiments may provide improved rendering performance of a large polygon mesh with diverse materials, especially when the rendering leverages data transmission over a network. ## Claims ### Claim 1 A method for subdividing large polygon mesh datasets into hierarchical subsets for level-of-detail use, comprising: grouping triangles in a triangle mesh dataset by material use to create at least two different material groups; determining and storing a hierarchy of tiles within each material group; generating and storing a hierarchical level-of-detail (HLOD) structure indicating the tiles and all the material groups, wherein: each of the at least two different material groups comprises the triangles in the triangle mesh dataset associated with any functionally identical materials unique to that respective group; and each of the at least two different material groups preserves any triangle groups associated with the functionally identical materials unique to that respective group indicated in the triangle mesh dataset; and in parallel, and on a separate processor for each of the at least two different material groups: generating placeholder tiles for any tiles exceeding a combined processing budget comprising a vertex count per tile of below 216 and a material expense below a threshold, wherein each placeholder tile has a lower level of detail than the respective tile exceeding the combined processing budget for which that placeholder tile was generated; and generating children tiles for at least one placeholder tile based on the respective tile exceeding the combined processing budget for which that placeholder tile was generated, wherein the children tiles have a same resolution as the respective tile exceeding the processing budget for which that placeholder tile was generated. ### Claim 2 (depends on 1) The method of claim 1, wherein determining and storing the hierarchy of tiles within each material group comprises: identifying triangles that should be perceived together when rendered as a perception group of triangles; and adding the perception group of triangles to a same tile. ### Claim 3 (depends on 1) The method of claim 1, wherein determining and storing the hierarchy of tiles within each material group comprises assembling perception groups of triangles together in the same tile until a vertex count per tile budget is met for the same tile. ### Claim 4 (depends on 1) The method of claim 1, wherein determining and storing the hierarchy of tiles within each material group comprises prioritizing tiles based on a visual importance of the perception group within the tile. ### Claim 5 (depends on 4) The method of claim 4, wherein visual importance is based at least in part on surface area. ### Claim 6 (depends on 1) The method of claim 1, wherein grouping triangles in a triangle mesh dataset by material use to create at least two different material groups comprises grouping all triangles in the triangle mesh dataset by material use to create at least two different material groups. ### Claim 7 (depends on 1) The method of claim 1, further comprising: determining a priority for rendering of each tile in the HLOD structure; and indicating the priority for rendering of each tile in the HLOD structure. ### Claim 8 (depends on 7) The method of claim 7, wherein the priority for rendering for each tile is that tile's geometric error. ### Claim 9 A computing device, comprising: a graphic display; and a processor connected to the graphic display, wherein the processor is configured with processor executable instructions to perform operations comprising: grouping triangles in a triangle mesh dataset by material use to create at least two different material groups; determining and storing a hierarchy of tiles within each material group; generating and storing a hierarchical level-of-detail (HLOD) structure indicating the tiles and all the material groups, wherein: each of the at least two different material groups comprises the triangles in the triangle mesh dataset associated with any functionally identical materials unique to that respective group; and each of the at least two different material groups preserves any triangle groups associated with the functionally identical materials unique to that respective group indicated in the triangle mesh dataset; and controlling a separate processor for each of the at least two different material groups to, in parallel, perform operations to: generate placeholder tiles for any tiles exceeding a combined processing budget comprising a vertex count per tile of below 216 and a material expense below a threshold, wherein each placeholder tile has a lower level of detail than the respective tile exceeding the combined processing budget for which that placeholder tile was generated; and generate children tiles for at least one placeholder tile based on the respective tile exceeding the combined processing budget for which that placeholder tile was generated, wherein the children tiles have a same resolution as the respective tile exceeding the processing budget for which that placeholder tile was generated. ### Claim 10 (depends on 9) The computing device of claim 9, wherein the processor is configured with processor executable instruction to perform operations such that determining and storing the hierarchy of tiles within each material group comprises: identifying triangles that should be perceived together when rendered as a perception group of triangles; and adding the perception group of triangles to a same tile. ### Claim 11 (depends on 9) The computing device of claim 9, wherein the processor is configured with processor executable instruction to perform operations such that determining and storing the hierarchy of tiles within each material group comprises assembling perception groups of triangles together in the same tile until a vertex count per tile budget is met for the same tile. ### Claim 12 (depends on 9) The computing device of claim 9, wherein the processor is configured with processor executable instruction to perform operations such that determining and storing the hierarchy of tiles within each material group comprises prioritizing tiles based on a visual importance of the perception group within the tile. ### Claim 13 (depends on 12) The computing device of claim 12, wherein visual importance is based at least in part on surface area. ### Claim 14 (depends on 9) The computing device of claim 9, wherein the processor is configured with processor executable instruction to perform operations such that grouping triangles in a triangle mesh dataset by material use to create at least two different material groups comprises grouping all triangles in the triangle mesh dataset by material use to create at least two different material groups. ### Claim 15 (depends on 9) The computing device of claim 9, wherein the processor is configured with processor executable instruction to perform operations further comprising: determining a priority for rendering of each tile in the HLOD structure; and indicating the priority for rendering of each tile in the HLOD structure. ### Claim 16 (depends on 15) The computing device of claim 15, wherein the priority for rendering for each tile is that tile's geometric error. ### Claim 17 A non-transitory processor readable medium having stored thereon processor-readable instructions configured to cause a processor of a computing device to perform operations comprising: grouping triangles in a triangle mesh dataset by material use to create at least two different material groups; determining and storing a hierarchy of tiles within each material group; generating and storing a hierarchical level-of-detail (HLOD) structure indicating the tiles and all the material groups, wherein: each of the at least two different material groups comprises the triangles in the triangle mesh dataset associated with any functionally identical materials unique to that respective group; and each of the at least two different material groups preserves any triangle groups associated with the functionally identical materials unique to that respective group indicated in the triangle mesh dataset; and controlling a separate processor for each of the at least two different material groups to, in parallel, perform operations to: generate placeholder tiles for any tiles exceeding a combined processing budget comprising a vertex count per tile of below 216 and a material expense below a threshold, wherein each placeholder tile has a lower level of detail than the respective tile exceeding the combined processing budget for which that placeholder tile was generated; and generate children tiles for at least one placeholder tile based on the respective tile exceeding the combined processing budget for which that placeholder tile was generated, wherein the children tiles have a same resolution as the respective tile exceeding the processing budget for which that placeholder tile was generated. ### Claim 18 (depends on 17) The non-transitory processor readable medium of claim 17, wherein the processor-readable instructions are configured to cause a processor of a computing device to perform operations such that determining and storing the hierarchy of tiles within each material group comprises: identifying triangles that should be perceived together when rendered as a perception group of triangles; and adding the perception group of triangles to a same tile. ### Claim 19 (depends on 17) The non-transitory processor readable medium of claim 17, wherein the processor-readable instructions are configured to cause a processor of a computing device to perform operations further comprising: determining a priority for rendering of each tile in the HLOD structure; and indicating the priority for rendering of each tile in the HLOD structure.