# US 7,610,184 B1 · Sector meshing and neighbor searching for object interaction simulation > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 7,610,184 B1 - Document ID: US7610184B1 - Status: Granted - Kind: B1 - Application number: 11/336,885 - Filed: 2006-01-23 - Published: 2009-10-08 - Granted: 2009-10-27 - Earliest claimed: 2006-01-23 - Assignees: ITT Manufacturing Enterprises, Inc. - Inventors: Steven T. Tillman; Andrew J. Witzig - Web page: https://patentgrep.com/patent/US7610184B1 ## CPC - G06F 30/25: using particle-based methods - G06F 30/20: Design optimisation, verification or simulation (optimisation, verification or simulation of circuit designs G06F30/30) - G06F 2111/10: Numerical modelling - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract Methods for computer-implemented simulation for the interaction of two or more objects are provided. Data describing particles that represent each of the objects is generated from geometric data for objects. The data for each particle describes a mass density, velocity and energy at a position of the corresponding object. The particles are grouped into sectors to define a computational mesh comprising a plurality of sectors, wherein each sector is a volume region at a position in space in which particles associated with the objects may reside. For each of a plurality of select particles, so called neighboring particles are determined that are within a region of influence with respect to a select particle. Computations are performed based on laws of conservation of mass, energy and momentum to produce updated values for mass, velocity, energy, pressure, stress and position for the particles at each of a plurality of time steps. According to one aspect, when determining neighboring particles for a given select particle, a search is made through a limited or bounded volume region with respect to the select particle that consists of the region of influence for the select particle at the previous time step and within those sectors in contact with or bordering the region of influence at the previous time step. According to another aspect, the plurality of select particles are identified as those particles that reside in an active sector, wherein an active sector is a sector that contains, or is adjacent to a sector that contains, particles that is actively involved in the engagement between the two objects. For example, an active sector is a sector that contains, or is adjacent to a sector that contains, at least one particle that has a velocity, pressure or stress greater than a corresponding predetermined amount. ## Claims ### Claim 1 A computer-implemented method for simulating interaction of at least first and second objects, comprising: a. generating data describing particles that represent each of the first and second objects from geometric data for the first and second objects, wherein the data for each particle describes a mass, density, velocity, pressure, stress and energy at a position of the corresponding object, to produce a first collection of particles representing the first object and a second collection of particles representing the second object; b. grouping particles into sectors to define a computational mesh comprising a plurality of sectors, wherein each sector is a volume region at a position in space; c. for each of a plurality of select particles, determining neighboring particles that are within a region of influence with respect to each select particle; d. performing computations pertaining to the interaction of particles in said computational mesh based on the neighboring particles determined for each of the plurality of select particles to produce for a time step updated data for mass, velocity, energy and position for the particles; and e. repeating (b) through (d) for each of a plurality of time steps; wherein (c) determining at a current time step comprises searching through particles that are within a bounding volume region comprised of sectors that are within the region of influence at a previous time step and within those sectors in contact with or bordering the region of influence from the previous time step. ### Claim 2 (depends on 1) The method of claim 1, wherein (c) determining neighboring particles comprises identifying a predetermined number of a plurality of particles that are closest to the select particle within said bounding volume region. ### Claim 3 (depends on 1) The method of claim 1, wherein (c) determining further comprises identifying said plurality of select particles as particles that reside in an active sector, wherein an active sector is a sector that comprises at least one particle that is actively involved in the engagement between the first and second objects. ### Claim 4 (depends on 3) The method of claim 3, wherein identifying comprises identifying said plurality of select particles as particles that are within a sector that contains, or is adjacent to a sector that contains, at least one particle that has a velocity, pressure or stress greater than a corresponding predetermined amount. ### Claim 5 (depends on 1) The method of claim 1, wherein (c) determining comprises adjusting a size of the region of influence such that there are a constant number of neighboring particles for each of said plurality of select particles. ### Claim 6 (depends on 1) The method of claim 1, wherein (c) determining comprises determining neighboring particles that are within a region of influence that has a spherical shape. ### Claim 7 (depends on 6) The method of claim 6, wherein (c) determining comprises adjusting a radius of said region of influence such that there are a constant number of neighboring particles for each of said plurality of select particles. ### Claim 8 (depends on 1) The method of claim 1, wherein (d) performing comprises performing computations based on laws of conservation of mass, energy and momentum. ### Claim 9 (depends on 1) The method of claim 1, wherein (b) grouping comprises binning particles into sectors, and wherein each sector is a rectangular volume region, and wherein said bounding volume region is rectangular. ### Claim 10 (depends on 1) The method of claim 1, wherein (b) grouping comprises determining geometric extents for said first and second collections of particles prior to grouping into said plurality of sectors. ### Claim 11 (depends on 10) The method of claim 10, wherein (b) grouping comprises binning particles into sectors, and wherein each sector is a rectangular volume region having dimensions that are based on the geometric extents for said first and second collections of particles. ### Claim 12 (depends on 1) The method of claim 1, wherein (d) determining neighboring particles comprises identifying a predetermined number of a plurality of particles that are closest to the select particle within said bounding volume region. ### Claim 13 (depends on 1) The method of claim 1, wherein (d) determining comprises adjusting a size of the region of influence such that there are a constant number of neighboring particles for each of said plurality of select particles. ### Claim 14 (depends on 1) The method of claim 1, wherein (d) determining comprises determining neighboring particles that are within a region of influence that has a spherical shape. ### Claim 15 (depends on 14) The method of claim 14, wherein (d) determining comprises adjusting a radius of said region of influence such that there are a constant number of neighboring particles for each of said plurality of select particles. ### Claim 16 (depends on 1) The method of claim 1, wherein (e) performing comprises performing computations based on laws of conservation of mass, energy and momentum. ### Claim 17 (depends on 1) The method of claim 1, wherein (b) grouping comprises binning particles into sectors, and wherein each sector is a rectangular volume region, and wherein said bounding volume region is rectangular. ### Claim 18 (depends on 1) The method of claim 1, wherein (b) grouping comprises determining geometric extents for said particles prior to grouping into said plurality of sectors. ### Claim 19 (depends on 18) The method of claim 18, wherein (b) grouping comprises binning particles into sectors, and wherein each sector is a rectangular volume region having dimensions that are based on the geometric extents for said particles. ### Claim 20 A computer-implemented method for simulating interaction of at least first and second objects, comprising: a. generating data describing particles that represent each of the first and second objects from geometric data for the first and second objects, wherein the data for each particle describes a mass density, velocity, pressure, stress and energy at a position of the corresponding object, to produce a first collection of particles representing the first object and a second collection of particles representing the second object; b. grouping particles into sectors to define a computational mesh comprising a plurality of sectors, wherein each sector is a volume region at a position in space; c. identifying a plurality of select particles as those particles that reside in an active sector, wherein an active sector is a sector that contains at least one particle that is actively involved in the engagement between the first and second objects; d. for each of said plurality of select particles, determining neighboring particles that are within a region of influence with respect to each select particle; e. performing computations pertaining to the interaction of particles in said computational mesh based on the neighboring particles determined for each of the plurality of select particles to produce for a time step updated data for mass, velocity, energy and position for the particles; and f. repeating (b) through (e) for each of a plurality of time steps. ### Claim 21 (depends on 20) The method of claim 20, wherein (c) identifying comprises identifying the plurality of select particles as particles within is a sector that is, or is adjacent to a sector that contains, at least one particle that has a velocity pressure or stress greater than a corresponding predetermined amount. ### Claim 22 (depends on 20) The method of claim 20, wherein (d) determining comprises searching through particles that are within a bounding volume region comprised of sectors that are within the region of influence from a previous time step and within those sectors in contact with or bordering the region of influence from the previous time step. ### Claim 23 A computer-readable medium storing instructions that, when executed by a computer, cause the computer to: a. generate data describing particles that represent each of the first and second objects from geometric data for the first and second objects, wherein the data for each particle describes a mass density, velocity, pressure stress and energy at a position of the corresponding object, to produce a first collection of particles representing the first object and a second collection of particles representing the second object; b. group particles into sectors to define a computational mesh comprising a plurality of sectors, wherein each sector is a volume region at a position in space; c. for each of a plurality of select particles, determine neighboring particles that are within a region of influence with respect to each select particle; d. perform computations pertaining to the interaction of particles in said computational mesh based on the neighboring particles determined for each of the plurality of select particles to produce for a time step updated data for mass, velocity, energy and position for the particles; and e. repeat (b) through (d) for each of a plurality of time steps; wherein the instructions that cause the computer to (c) determine at a current time step comprise instructions that cause the computer to search through particles that are within a bounding volume region comprised of sectors that are within the region of influence from a previous time step and within those sectors in contact with or bordering the region of influence from the previous time step. ### Claim 24 A computer-readable medium storing instructions that, when executed by a computer, cause the computer to: a. generate data describing particles that represent each of the first and second objects from geometric data for the first and second objects, wherein the data for each particle describes a mass density, velocity, pressure, stress and energy at a position of the corresponding object, to produce a first collection of particles representing the first object and a second collection of particles representing the second object; b. group particles into sectors to define a computational mesh comprising a plurality of sectors, wherein each sector is a volume region at a position in space; c. identify a plurality of select particles as those particles that reside in an active sector, wherein an active sector is a sector that contains at least one particle that is actively involved in the engagement between the first and objects; d. for each of said plurality of select particles, determine neighboring particles that are within a region of influence with respect to each select particle; e. perform computations pertaining to the interaction of particles in said computational mesh based on the neighboring particles determined for each of the plurality of select particles to produce for a time step updated data for mass, velocity, energy and position for the particles; and f. repeat (b) through (e) for each of a plurality of time steps. ### Claim 25 (depends on 24) The computer-readable medium of claim 24, wherein the instructions that cause the computer to (c) determine comprises instructions that cause the computer to identify a predetermined number of a plurality of particles that are closest to the select particle within said bounding volume region. ### Claim 26 (depends on 24) The computer-readable medium of claim 24, wherein the instructions that cause the computer to (c) determine comprises instructions that cause the computer to identify said plurality of select particles as those particles that reside in an active sector, wherein an active sector is a sector that comprises at least one particle that is actively involved in the engagement between the first and second objects. ### Claim 27 (depends on 26) The computer-readable medium of claim 26, wherein the instructions that cause the computer to identify comprises instructions that cause the computer to identify said plurality of select particles as particles that are within a sector that contains, or is adjacent to a sector that contains, at least one particle that has a velocity, pressure or stress greater than a corresponding predetermined amount. ### Claim 28 (depends on 24) The computer-readable medium of claim 24, wherein the instructions that cause the computer to (c) determine comprise instructions that cause the computer to adjust a size of the region of influence such that there are a constant number of neighboring particles for each of said plurality of select particles. ### Claim 29 (depends on 24) The computer-readable medium of claim 24, wherein the instructions that cause the computer to group comprise instructions that cause the computer to bin particles into sectors, wherein each sector is a rectangular volume region, and wherein said bounding volume region is rectangular. ### Claim 30 (depends on 24) The computer-readable medium of claim 24, wherein the instructions that cause the computer to group comprise instructions that cause the computer to determine geometric extents for said first and second collection of particles prior to grouping into said plurality of sectors. ### Claim 31 (depends on 30) The computer-readable medium of claim 30, wherein the instructions that cause the computer to group comprise instructions that cause the computer to bin particles into sectors, wherein each sector is a rectangular volume region having dimensions that are based on the geometric extents for said first and second collection of particles.