METHOD FOR ANIMATING CHARACTERS, WITH COLLISION AVOIDANCE BASED ON TRACING INFORMATION

• US 20130235047A1
• Filed: 11/28/2011
• Published: 09/12/2013
• Est. Priority Date: 11/26/2010
• Status: Active Grant

• Current Assignee: InterDigital CE Patent Holdings SAS (InterDigital, Inc.)
• Original Assignee: Thomson Licensing (Vantiva SA)
• Inventors: Xia, Zhijin, Teng, Jun, Cai, Kangying, Chen, Zhibo
• Granted Patent: US 9,460,540 B2
• Time in Patent Office: Days
• US Class Current: 345/474
• 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 manoeuvre is necessary then updating the tracing information in the current terrain cell.

Claims

1. A method for determining for a character in a group at least one of a moving direction and a moving velocity, the method comprising steps of

reading tracing information from a current cell in a terrain map on which the character is located;

determining if collision avoidance is needed;

if not, advancing the character according to its previous direction and previous velocity;

if so, searching, for at least one of a matching direction and velocity;

if a matching direction and/or velocity is found, computing a time-to-collision, and comparing the computed time-to-collision with a predetermined range;

if the time-to-collision is within the predetermined range, then advancing the character according to the found matching direction and/or velocity; and

if no matching direction and/or velocity is found, or if the time-to-collision is outside the predetermined range, then performing a manoeuvre for collision avoiding, and updating the tracing information in the current cell in the terrain map.

2. 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. Method according to claim 1, wherein multiple characters are employed and the given preference speed of characters is identical for all characters.

4. Method according to claim 2, wherein the read tracing information of a cell influences the individual behaviour of at least the next character entering the cell, not the group behaviour in general.

5. Method according to claim 2, wherein the step of determining if collision avoidance is needed comprises that a character, when entering a new cell, searches for the tracing information which matches at least a range of angles including the character'"'"'s entry angle.

6. Method according to claim 2, wherein tracing information of a cell in a terrain map comprises entry angle, the new velocity and the time to collide for at least one previous character that entered the cell.

7. Method according to claim 2, wherein the tracing information of a cell includes at least four sets of data, each of which relates to a range of entry direction Ve of the character, and each data set comprises at least the new velocity V_new and the time-to-collide (TTC) based on this new velocity.

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

9. Method for simulating a crowd comprising steps of

determining a group heading direction;

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

combining the velocity for the group and the local adjustment to generate the new velocity for each character, wherein the local adjustment for each character is generated using a method according to claim 1.

10. Device for determining for a character in a group at least one of a moving direction and a moving velocity, comprising

memory for storing cells of a terrain map;

first data read means for reading tracing information from a current cell in a terrain map on which the character is located;

first collision detector for determining, based on the tracing information from the first data read means, whether or not collision avoidance is needed, and for notifying the determining result;

first position calculator for advancing the character according to its previous direction and previous velocity if the first calculator notifies that collision avoidance is not needed;

first processor for searching, if the first calculator notifies that collision avoidance is needed, for at least one of a matching direction and velocity;

second processor for computing a time-to-collision based on the found matching direction and/or velocity;

comparator for comparing the computed time-to-collision with a predetermined range; and

second position calculator for advancing the character according to the found matching direction and/or velocity, and for performing a collision avoiding manoeuvre and updating the tracing information in the current terrain cell if no matching direction and/or velocity is found, or if the time-to-collision is outside the predetermined range.

11. Device according to claim 10, wherein tracing information of a cell in a terrain map comprises entry angle, a new velocity and a time to collide for at least one previous character that entered the cell.

12. Device according to claim 10, wherein the tracing information of a cell includes at least four sets of data, each of which relates to a range of entry direction Ve of the character, and each data set comprises at least the new velocity V_new and the time-to-collide based on this new velocity.

13. Device according to claim 11, wherein the first collision detector, when determining if collision avoidance is needed for a character entering a new cell, searches for tracing information which matches at least a range of angles including the character'"'"'s entry angle.

14. Device according to claim 11, 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. Device for simulating a crowd, comprising a processor for

determining a group heading direction;

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

combining the velocity for the group and the local adjustment to generate the new velocity for each character, wherein the local adjustment for each character is generated using a device according to claim 11.