# US 8,751,207 B1 · Simulating granular material > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 8,751,207 B1 - Document ID: US8751207B1 - Status: Granted - Kind: B1 - Application number: 13/831,060 - Filed: 2013-03-14 - Granted: 2014-06-10 - Earliest claimed: 2009-12-01 - Assignees: Lucasfilm Entertainment Company Ltd. - Applicants: Lucasfilm Entertainment Company Ltd. - Inventors: Nicholas Grant Rasmussen; Frederick E. Hankins - Web page: https://patentgrep.com/patent/US8751207B1 ## CPC - G06F 30/23: using finite element methods [FEM] or finite difference methods [FDM] - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract A computer-implemented method for simulating a granular material includes removing, from a layer of granular material in a virtual domain defined by a data structure stored in a computer readable storage medium, a portion of the granular material in a closed region where the portion and a part of an object impacting the granular material are defined as occupying a same space. The method includes determining a value for a size aspect of the portion based on applying a numerical solver along an entirety of a boundary of the closed region. The method includes placing additional granular material along the boundary to create a shape resulting from the impact of the object. The method includes generating an image using the data structure, the image reflecting the impact of the object on the granular material in the virtual domain. ## Claims ### Claim 1 A method comprising: creating a virtual domain including a grid, the grid comprising multiple grid cells; defining a height level field in the virtual domain, the height level field including height values assigned to respective grid cells and wherein the height values represent a height of a granular material at each corresponding grid cell; defining a rigid object having a position in the virtual domain, the object being positioned in the virtual domain with an interference between at least part of the object and the granular material, the interference being that part of the object occupying a same space as some of the granular material; identifying interference grid cells from among the grid cells of the virtual domain, wherein an interference grid cell is a grid cell where the object interferes with the granular material, the identified interference grid cells forming a closed region in the granular material; identifying boundary grid cells associated with the closed region from among the grid cells of the virtual domain, wherein a boundary grid cell is a grid cell that abuts at least one of the interference grid cells and is not also an interference grid cell; removing a portion of the granular material from the closed region including determining a size of the closed region by integrating a gradient of a potential field for the virtual domain over the boundary grid cells; modifying the height level field of at least one boundary grid cell by placing additional granular material in the at least one boundary grid cell; and generating an image of the virtual domain, the image reflecting an impact of the object on the granular material. ### Claim 2 (depends on 1) The method of claim 1, wherein the integration is performed using a numerical solver along the boundary grid cells of the closed region. ### Claim 3 (depends on 1) The method of claim 1, wherein the additional granular material is placed to create a shape resulting from an impact of the object on the granular material. ### Claim 4 (depends on 1) The method of claim 1, wherein integrating the gradient of the potential field for the virtual domain comprises: defining a first field as a source field ρ for the virtual domain that has a source value assigned to each of the grid cells, the source values corresponding to a height of the granular material removed per unit area, wherein each source value inside the closed region is a nonzero value based on a corresponding interference height value, and each source value outside the closed region is zero; and determining a second field as the potential field φ for the virtual domain, wherein φ has a potential value assigned to each of the grid cells, and wherein the potential field is related to the source field by: ∇2φ=ρ, wherein ∇2 is the Laplace operator. ### Claim 5 (depends on 4) The method of claim 4, wherein integrating the potential field's gradient ∇φ over the boundary grid cells yields a distribution height value by which to modify the height level field for each of the boundary grid cells. ### Claim 6 (depends on 5) The method of claim 5, further comprising: adding each distribution height value to the height value of the corresponding boundary grid cells, the addition corresponding to distributing the additional granular material among all of the boundary grid cells, the additional granular material being equal in volume to the amount of the removed portion of the granular material. ### Claim 7 (depends on 1) The method of claim 1, wherein the granular material is defined to represent one or more of sand, gravel, dirt, snow, hail, slush, earth, dust, debris, ashes, powder, flour, pebbles, saw dust, beads, salt, spice, packing peanuts, marbles, food, tablets, or confetti. ### Claim 8 (depends on 1) The method of claim 1, further comprising determining, after placing the additional granular material and before generating the image, whether the additional granular material causes additional interference with the object in the virtual domain, and if so changing a distribution of the additional granular material. ### Claim 9 (depends on 8) The method of claim 8, wherein an iterative process is performed until the additional interference no longer occurs. ### Claim 10 A system comprising: one or more computers configured to perform operations comprising: creating a virtual domain including a grid, the grid comprising multiple grid cells; defining a height level field in the virtual domain, the height level field including height values assigned to respective grid cells and wherein the height values represent a height of a granular material at the corresponding grid cell; defining a rigid object having a position in the virtual domain, the object being positioned in the virtual domain with an interference between at least part of the object and the granular material, the interference being that part of the object occupying a same space as some of the granular material; identifying interference grid cells from among the grid cells of the virtual domain, wherein an interference grid cell is a grid cell where the object interferes with the granular material, the identified interference grid cells forming a closed region in the granular material; identifying boundary grid cells associated with the closed region from among the grid cells of the virtual domain, wherein a boundary grid cell is a grid cell that abuts at least one of the interference grid cells and is not also an interference grid cell; removing a portion of the granular material from the closed region including determining a size of the closed region by integrating a gradient of a potential field for the virtual domain over the boundary grid cells; modifying the height level field of at least one boundary grid cell by placing additional granular material in the at least one boundary grid cell; and generating an image of the virtual domain, the image reflecting an impact of the object on the granular material. ### Claim 11 (depends on 10) The system of claim 10, wherein the integration is performed using a numerical solver along the boundary grid cells of the closed region. ### Claim 12 (depends on 10) The system of claim 10, wherein the additional granular material is placed to create a shape resulting from an impact of the object on the granular material. ### Claim 13 (depends on 10) The system of claim 10, wherein integrating the gradient of the potential field for the virtual domain comprises: defining a first field as a source field ρ for the virtual domain that has a source value assigned to each of the grid cells, the source values corresponding to a height of the granular material removed per unit area, wherein each source value inside the closed region is a nonzero value based on a corresponding interference height value, and each source value outside the closed region is zero; and determining a second field as the potential field φ for the virtual domain, wherein φ has a potential value assigned to each of the grid cells, and wherein the potential field is related to the source field by: ∇2φ=ρ, where ∇2 is the Laplace operator. ### Claim 14 (depends on 13) The system of claim 13, wherein integrating the potential field's gradient ∇φ over the boundary grid cells yields a distribution height value by which to modify the height level field for each of the boundary grid cells. ### Claim 15 (depends on 14) The system of claim 14, further comprising: adding each distribution height value to the height value of the corresponding boundary grid cells, the addition corresponding to distributing the additional granular material among all of the boundary grid cells, the additional granular material being equal in volume to the amount of the removed portion of the granular material. ### Claim 16 (depends on 10) The system of claim 10, wherein the granular material is defined to represent one or more of sand, gravel, dirt, snow, hail, slush, earth, dust, debris, ashes, powder, flour, pebbles, saw dust, beads, salt, spice, packing peanuts, marbles, food, tablets, or confetti. ### Claim 17 (depends on 10) The system of claim 10, further comprising determining, after placing the additional granular material and before generating the image, whether the additional granular material causes additional interference with the object in the virtual domain, and if so changing a distribution of the additional granular material. ### Claim 18 (depends on 17) The system of claim 17, wherein an iterative process is performed until the additional interference no longer occurs. ### Claim 19 A non-transitory computer storage medium encoded with a computer program, the program comprising instructions that when executed by one or more computers cause the one or more computers to perform operations comprising: creating a virtual domain including a grid, the grid comprising multiple grid cells; defining a height level field in the virtual domain, the height level field including height values assigned to respective grid cells and wherein the height values represent a height of granular material at the corresponding grid cell; defining a rigid object having a position in the virtual domain, the object being positioned in the virtual domain with an interference between at least part of the object and the granular material, the interference being that part of the object occupying a same space as some of the granular material; identifying interference grid cells from among the grid cells of the virtual domain, wherein an interference grid cell is a grid cell where the object interferes with the granular material, the identified interference grid cells forming a closed region in the granular material; identifying boundary grid cells associated with the closed region from among the grid cells of the virtual domain, wherein a boundary grid cell is a grid cell that abuts at least one of the interference grid cells and is not also an interference grid cell; removing a portion of the granular material from the closed region including determining a size of the closed region by integrating a gradient of a potential field for the virtual domain over the boundary grid cells; modifying the height level field of at least one boundary grid cell by placing additional granular material in the at least one boundary grid cell; and generating an image of the virtual domain, the image reflecting an impact of the object on the granular material. ### Claim 20 (depends on 19) The non-transitory computer storage medium encoded with a computer program of claim 19, wherein integrating the gradient of the potential field for the virtual domain comprises: defining a first field as a source field ρ for the virtual domain that has a source value assigned to each of the grid cells, the source values corresponding to a height of the granular material removed per unit area, wherein each source value inside the closed region is a nonzero value based on a corresponding interference height value, and each source value outside the closed region is zero; and determining a second field as the potential field φ for the virtual domain, wherein φ has a potential value assigned to each of the grid cells, and wherein the potential field is related to the source field by: ∇2φ=ρ, wherein ∇2 is the Laplace operator.