Method for animating characters, with collision avoidance based on tracing information

• US 9,460,540 B2
• Filed: 11/28/2011
• Issued: 10/04/2016
• Est. Priority Date: 11/26/2010
• Status: Active Grant

• Current Assignee: InterDigital Patent Holdings, Inc. (InterDigital, Inc.)
• Original Assignee: Thomson Licensing (Vantiva SA)
• Inventors: Xia, Zhijin, Teng, Jun, Cai, Kangying, Chen, Zhibo
• Primary Examiner(s): Crawford, Jacinta M
• Assistant Examiner(s): Cofino, Jonathan M
• Application Number:
  US13/988,338
• Publication Number:
  US 20130235047A1
• Time in Patent Office: 1,772 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06T 13/40 of characters, e.g. humans, animals or virtual beings
• CPC Class Codes: G06T 13/80 2D [Two Dimensional] animation, e.g. using sprites
• CPC Class Codes: G06T 2210/21 Collision detection, intersection

Abstract

A method for determining a moving direction or moving velocity for a character in a group comprises reading tracing information from a cell in a terrain map on which the character is located, determining if collision avoidance is needed, and if a collision avoiding maneuver is necessary then updating the tracing information in the current terrain cell.

Claims

1. A method to avoid collision, the method comprising:

reading tracing information stored in a current cell of a terrain map in which a character is located, the tracing information comprising an entry angle of the character in the current cell;

advancing the character in accordance with a previous entry angle and a previous velocity of the character, when collision avoidance is not needed;

searching the current cell for at least one other character whose entry angle and velocity indicates a potential collision between the character and the at least one other character;

if the potential collision is indicated, computing a time-to-collision;

if the time-to-collision is outside a predetermined range, calculate a new velocity for the character using a reciprocal velocity obstacle operation; and

if the time-to-collision is within the predetermined range, calculate the new velocity for the character using an operation of a type different from the reciprocal velocity obstacle operation.

2. The method according to claim 1, wherein a cell of the terrain map has a diameter d according to d<

Δ

t*V^pref, wherein Δ

t is a simulation time step and V^pref is a given preference speed of characters.

3. The method according to claim 1, further comprising setting a preference speed for each character in the terrain map.

4. The method according to claim 1, influencing an individual behavior of at least a next character entering the cell based on the tracing information.

5. The method according to claim 1, further comprising searching the tracing information for a range of entry angles including the entry angle of the character, in order to determine whether collision avoidance is needed.

6. The method according to claim 1, wherein tracing information of a cell in the terrain map comprises an entry angle, a new velocity and a time-to-collision of at least one previous character that entered the cell.

7. The method according to claim 1, wherein the tracing information of a cell comprises at least four sets of data, each of which relates to a range of entry angles V_e of the character, and each data set comprises at least a new velocity V_new and a time-to-collision based on this new velocity.

8. The method according to claim 1, wherein the information stored in the terrain map is an intermediate result that is used as a guideline for deciding at least one of speed and velocity for at least a next character based on current circumstances.

9. The method according to claim 1, further comprising:

determining a direction for a group of characters;

adjusting a speed for each character inside the group when the direction changes; and

combining the velocity for the group and a local adjustment to generate a new velocity for each character so as to simulate a crowd.

10. A device to avoid collision, the device comprising:

a memory for storing cells of a terrain map; and

at least one processor configured to;

read tracing information from a current cell of the terrain map in which a character is located the tracing information comprising an entry angle of the character in the current cell;

advance the character according to a previous entry angle and a previous velocity of the character, when it is determined that collision avoidance is not needed;

search the current cell for at least one other character whose entry angle and velocity indicates a potential collision between the character and the at least one other character;

if the potential collision is indicated, compute a time-to-collision;

if the time-to-collision is outside a predetermined range, calculate a new velocity for the character using a reciprocal velocity obstacle operation; and

if the time-to-collision is within the predetermined range, calculate the new velocity for the character using an operation of a type different from the reciprocal velocity obstacle operation.

11. The device according to claim 10, wherein the tracing information comprises an entry angle, a new velocity and a time-to-collision for at least one previous character that entered the current cell.

12. The device according to claim 10, wherein the tracing information comprises at least four sets of data, each of which relates to a range of entry directions V_e of the character, and each data set comprises at least a new velocity V_new and a time-to-collision based on this new velocity.

13. The device according to claim 10, wherein the at least one processor is further configured to search the tracing information for a range of entry angles including the entry angle of the character, in order to determine whether collision avoidance is needed.

14. The device according to claim 10, wherein a cell of the terrain map has a diameter d according to d<

Δ

t*V^pref, wherein Δ

t is a simulation time step and V^pref is a given preference speed of characters.

15. The device according to claim 10, wherein the at least one processor is further configured to:

determine a direction for a group pf characters;

adjust a speed for each character inside the group when the direction changes; and

combine the velocity for the group and a local adjustment to generate a new velocity for each character so as to simulate a crowd.

16. The device according to claim 10, further comprising setting a preference speed for each character in the terrain map.

17. The device according to claim 10, wherein the tracing information influences an individual behavior of at least a next character entering the current cell.

18. The device according to claim 10, wherein the information stored in the terrain map is an intermediate result that is used as a guideline for deciding at least one of speed and velocity for at least a next character based on current circumstances.