# US 2019/0318522 A1 · Collision Detection and Resolution in Virtual Environments

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

- Number: US 2019/0318522 A1
- Document ID: US20190318522A1
- Status: Published application
- Kind: A1
- Application number: 16/220,689
- Filed: 2018-12-14
- Published: 2019-10-17
- Earliest claimed: 2018-04-11
- Assignees: Electronic Arts Inc.
- Applicants: Electronic Arts Inc.
- Inventors: Christopher Charles Lewin
- Web page: https://patentgrep.com/patent/US20190318522A1

## CPC

- G06T 13/20: Three-dimensional [3D] animation
- G06T 19/00: Manipulating three-dimensional [3D] models or images for computer graphics
- A63F 13/42: by mapping the input signals into game commands, e.g. mapping the displacement of a stylus on a touch screen to the steering angle of a virtual vehicle
- A63F 13/577: using determination of contact between game characters or objects, e.g. to avoid collision between virtual racing cars
- A63F 2300/643: by determining the impact between objects, e.g. collision detection
- A63F 2300/6607: for animating game characters, e.g. skeleton kinematics
- G06F 30/20: Design optimisation, verification or simulation (optimisation, verification or simulation of circuit designs G06F30/30)
- G06F 2113/12: Cloth
- G06T 2210/16: Cloth
- G06T 2210/21: Collision detection, intersection
- G06T: IMAGE DATA PROCESSING OR GENERATION, IN GENERAL
- A63F: CARD, BOARD, OR ROULETTE GAMES; INDOOR GAMES USING SMALL MOVING PLAYING BODIES; VIDEO GAMES; GAMES NOT OTHERWISE PROVIDED FOR
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

A non-transitory computer readable storage medium storing computer program code that, when executed by a processing device, cause the processing device to perform operations comprising: determining a first representative point, wherein the first representative point represents a first geometric primitive; determining a second representative point, wherein the second representative point represents a second geometric primitive; determining an initial distance between the first representative point and the second representative point; calculating a first displacement based on a velocity of the first representative point; calculating a second displacement based on a velocity of the second representative point; determining a separating direction between the first representative point and the second representative point; projecting the first displacement along the separating direction; projecting the second displacement along the separating direction; calculating a predicted minimum distance between the first representative point and the second representative point based on the projection of the first displacement along the separating direction, the projection of the second displacement along the separating direction and the initial distance between the first representative point and the second representative point; and in response to the predicted minimum distance being less than a threshold distance, generating a collision constraint preventing penetration between the first geometric primitive and the second geometric primitive.

## Claims

### Claim 1

A non-transitory computer readable storage medium storing computer program code that, when executed by a processing device, cause the processing device to perform operations comprising:
determining a first representative point, wherein the first representative point represents a first geometric primitive;
determining a second representative point, wherein the second representative point represents a second geometric primitive;
determining an initial distance between the first representative point and the second representative point;
calculating a first displacement based on a velocity of the first representative point;
calculating a second displacement based on a velocity of the second representative point;
determining a separating direction between the first representative point and the second representative point;
projecting the first displacement along the separating direction;
projecting the second displacement along the separating direction;
calculating a predicted minimum distance between the first representative point and the second representative point based on the projection of the first displacement along the separating direction, the projection of the second displacement along the separating direction and the initial distance between the first representative point and the second representative point; and
in response to the predicted minimum distance being less than a threshold distance, generating a collision constraint preventing penetration between the first geometric primitive and the second geometric primitive.

### Claim 2 (depends on 1)

The non-transitory computer readable storage medium of claim 1, wherein the threshold distance is based on a static collision radius.

### Claim 3 (depends on 1)

The non-transitory computer readable storage medium of claim 1, wherein the threshold distance is based on a radius associated with at least one of the first geometric primitive and the second geometric primitive.

### Claim 4 (depends on 1)

The non-transitory computer readable storage medium of claim 1, wherein the computer program code, when executed by the processing device, causes the processing device to perform calculating the first displacement by multiplying the velocity of the first point by a time unit.

### Claim 5 (depends on 1)

The non-transitory computer readable storage medium of claim 1, wherein:
the first geometric primitive is a point; and
the second geometric primitive is a triangle.

### Claim 6 (depends on 6)

The non-transitory computer readable storage medium of claim 6, wherein the first representative point is the point.

### Claim 7 (depends on 6)

The non-transitory computer readable storage medium of claim 6, wherein the computer program code, when executed by the processing device, causes the processing device to perform determining the second representative point by determining a closest point on the triangle to the point.

### Claim 8 (depends on 8)

The non-transitory computer readable storage medium of claim 8, wherein the computer program code, when executed by the processing device, causes the processing device to perform determining the closest point on the triangle by performing barycentric interpolation.

### Claim 9 (depends on 6)

The non-transitory computer readable storage medium of claim 6, wherein the computer program code, when executed by the processing device, causes the processing device to perform generating the collision constraint by:
determining a first vector between a first vertex of the triangle and a second vertex of the triangle;
determining a second vector between the first vertex of the triangle and a third vertex of the triangle;
determining a third vector between the point and the first vertex of the triangle;
determining a perpendicular direction, where the perpendicular direction is substantially perpendicular to the first vector and the second vector; and
generating a constraint based on a scalar product of the perpendicular direction and the third vector.

### Claim 10 (depends on 6)

The non-transitory computer readable storage medium of claim 6, wherein the computer program code, when executed by the processing device, causes the processing device to further perform:
receiving an indication that the point should be on a given side of the triangle;
in response to the point being on a side of the face of the triangle other than the given side, relocating the point to be on the given side of the face of the triangle.

### Claim 11 (depends on 6)

The non-transitory computer readable storage medium of claim 6, wherein the computer program code, when executed by the processing device, causes the processing device to further perform:
generating a further collision constraint based on a stored indication of a predicted collision.

### Claim 12 (depends on 1)

The non-transitory computer readable storage medium of claim 1, wherein the first geometric primitive is a first edge and the second geometric primitive is a second edge.

### Claim 13 (depends on 11)

The non-transitory computer readable storage medium of claim 11, wherein the computer program code, when executed by a processing device, causes the processing device to perform:
determining the first representative point by determining the closest point on the first edge to the second edge; and
determining the second representative point by determining the closest point on the second edge to the first edge.

### Claim 14 (depends on 13)

The non-transitory computer readable storage medium of claim 13, wherein the computer program code, when executed by the processing device, causes the processing device to perform:
determining the closest point on the first edge to the second edge by performing linear interpolation; and
determining the closest point on the second edge to the first edge by performing linear interpolation.

### Claim 15 (depends on 14)

The non-transitory computer readable storage medium of claim 14, wherein the computer program code, when executed by the processing device, causes the processing device to perform generating the collision constraint by:
determining a vector between the first representative point and the second representative point;
determining a direction, wherein the second direction is substantially opposite to the direction of the vector; and
generating a constraint based on the scalar product of the vector and the direction.

### Claim 16 (depends on 1)

The non-transitory computer readable storage medium of claim 1, wherein the non-transitory computer readable storage medium is a Blu-ray disc.

### Claim 17 (depends on 1)

The non-transitory computer readable storage medium of claim 1, wherein the non-transitory computer readable storage medium is a persistent storage medium of a game distribution system.

### Claim 18

A computer-implemented method for collision prediction comprising:
determining a first representative point, wherein the first representative point represents a first geometric primitive;
determining a second representative point, wherein the second representative point represents a second geometric primitive;
determining an initial distance between the first representative point and the second representative point;
calculating a first displacement based on a velocity of the first representative point;
calculating a second displacement based on a velocity of the second representative point;
determining a separating direction between the first representative point and the second representative point;
projecting the first displacement along the separating direction;
projecting the second displacement along the separating direction;
calculating a predicted minimum distance between the first representative point and the second representative point based on the projection of the first displacement along the separating direction, the projection of the second displacement along the separating direction and the initial distance between the first representative point and the second representative point; and
in response to the predicted minimum distance being less than a threshold distance, generating a collision constraint preventing penetration between the first geometric primitive and the second geometric primitive.

### Claim 19

An apparatus comprising:
at least one processor; and
at least one memory including computer program code which, when executed by the at least one processor, cause the apparatus to:
determine a first representative point, wherein the first representative point represents a first geometric primitive;
determine a second representative point, wherein the second representative point represents a second geometric primitive;
determine an initial distance between the first representative point and the second representative point;
calculate a first displacement based on a velocity of the first representative point;
calculate a second displacement based on a velocity of the second representative point;
determine a separating direction between the first representative point and the second representative point;
project the first displacement along the separating direction;
project the second displacement along the separating direction;
calculate a predicted minimum distance between the first representative point and the second representative point based on the projection of the first displacement along the separating direction, the projection of the second displacement along the separating direction and the initial distance between the first representative point and the second representative point; and
in response to the predicted minimum distance being less than a threshold distance, generate a collision constraint preventing penetration between the first geometric primitive and the second geometric primitive.

### Claim 20 (depends on 19)

The apparatus of claim 19, wherein the apparatus is a video game console.
