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

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.