# US 8,279,227 B2 · Method for detecting collisions among large numbers of particles

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 8,279,227 B2
- Document ID: US8279227B2
- Status: Granted
- Kind: B2
- Application number: 12/111,075
- Filed: 2008-04-28
- Published: 2009-10-08
- Granted: 2012-10-02
- Earliest claimed: 2008-04-04
- Assignees: Sony Corporation; Sony Pictures Entertainment Inc.
- Inventors: Jonathan Cohen
- Web page: https://patentgrep.com/patent/US8279227B2

## CPC

- G06T 13/20: Three-dimensional [3D] animation
- G06T 2210/21: Collision detection, intersection
- G06T: IMAGE DATA PROCESSING OR GENERATION, IN GENERAL

## Abstract

A method for detecting object collisions in a simulation, which includes identifying a plurality of objects moving along a path within a simulation area, and defining a grid comprising defined regions which individually define a region within which any of the plurality of objects could potentially occupy. For each of the objects, the method further includes identifying which of the defined regions that each of the plurality of object occupies for at least a portion of a time step, and for each of the objects, determining an associated potential collision set by identifying objects of the plurality of objects which occupy common regions of the defined regions during any portion of the time step. In addition, for each of the objects, the method further includes determining an actual collision set comprising objects with which a given object will collide during the time step based upon location parameters of objects included in the potential collision set.

## Claims

### Claim 1

A method for detecting object collisions in a simulation, the method comprising:
identifying a plurality of objects within a defined area;
defining a plurality of grids, each comprising a plurality of defined regions, some of which individually include at least one of the plurality of objects within an associated one of the defined regions;
building a data tree in which each leaf node is implemented with one of the plurality of grids; and
identifying collisions between objects of the plurality of objects by searching the data tree and by considering only those objects of the plurality of objects which occupy at least one common region of the plurality of defined regions during any portion of a time step.

### Claim 2 (depends on 1)

The method according to claim 1, wherein multiple defined regions of the plurality of grids include a plurality of objects which occupy at least one common region of the plurality of defined regions during any portion of the time step.

### Claim 3 (depends on 1)

The method according to claim 1, wherein the defined regions individually comprise boxes and wherein the at least one common region comprises at least one box shared by the defined regions of two or more objects during the time step.

### Claim 4 (depends on 3)

The method according to claim 3, wherein identifying collisions comprises examining objects which are located in or pass through a box to determine whether a given object is present or passes through the same box during the same time step.

### Claim 5 (depends on 1)

The method according to claim 1, wherein defining a plurality of grids comprises including only grids meeting a threshold density of objects and excluding outlier objects not within grids meeting the threshold density.

### Claim 6 (depends on 5)

The method according to claim 5 further comprising storing each of outlier objects in a list and searching the list to identify collisions.

### Claim 7

A method for detecting object collisions in a simulation, the method comprising:
identifying a plurality of objects moving along a path within a simulation area;
defining a grid comprising a plurality of defined regions which individually define a region within which any of the plurality of objects could potentially occupy;
for each of the objects, identifying which of the plurality of defined regions that each of the plurality of objects occupies for at least a portion of a time step;
for each of the objects, determining an associated potential collision set by identifying objects of the plurality of objects which occupy at least one common region of the defined regions during any portion of the time step; and
for each of the objects, determining an actual collision set comprising objects with which a given object will collide during the time step based upon location parameters of objects included in the potential collision set.

### Claim 8 (depends on 7)

The method according to claim 7, wherein the defined regions individually comprise boxes and wherein the at least one common region comprises at least one box shared by the defined regions of two or more objects during the time step.

### Claim 9 (depends on 7)

The method according to claim 7, wherein the potential collision set comprises fewer objects than the number of the plurality of objects.

### Claim 10 (depends on 9)

The method according to claim 9, wherein the actual collision set comprises fewer objects than the potential collision set.

### Claim 11 (depends on 7)

The method according the claim 7, wherein the location parameters comprise a path along which an associated object travels during the time step.

### Claim 12 (depends on 7)

The method according the claim 7, wherein the location parameters comprise position and velocity.

### Claim 13 (depends on 7)

The method according to claim 7, wherein defining a plurality of grids comprises including only grids meeting a threshold density of objects and excluding outlier objects not within grids meeting the threshold density.

### Claim 14 (depends on 13)

The method according to claim 13 further comprising storing each of the outlier objects in a list and searching the list to determine the associated potential collision set.

### Claim 15

A computer-readable medium for detecting object collisions in a simulation, the computer-readable medium comprising instructions which, when executed by a processor, cause the processor to perform:
identifying a plurality of objects moving along a path within a simulation area;
defining a grid comprising a plurality of defined regions which individually define a region within which any of the plurality of objects could potentially occupy;
for each of the objects, identifying which of the plurality of defined regions that each of the plurality of object occupies for at least a portion of a time step;
for each of the objects, determining an associated potential collision set by identifying objects of the plurality of objects which occupy at least one common region of the defined regions during any portion of the time step; and
for each of the objects, determining an actual collision set comprising objects with which a given object will collide during the time step based upon location parameters of objects included in the potential collision set.

### Claim 16 (depends on 15)

The computer-readable medium according to claim 15, wherein the defined regions individually comprise boxes and wherein the at least one common region comprises at least one box shared by the defined regions of two or more objects during the time step.

### Claim 17 (depends on 16)

The computer-readable medium according to claim 16, wherein the actual collision set comprises fewer objects than the potential collision set.

### Claim 18 (depends on 15)

The computer-readable medium according to claim 15, wherein the potential collision set comprises fewer objects than the number of the plurality of objects.

### Claim 19 (depends on 15)

The computer-readable medium according to claim 15, wherein the location parameters comprise a path along which an associated object travels during the time step.

### Claim 20 (depends on 15)

The computer-readable medium according to claim 15, wherein the location parameters comprise position and velocity.
