Limb coordination system for interactive computer animation of articulated characters

• US 6,191,798 B1
• Filed: 03/31/1997
• Issued: 02/20/2001
• Est. Priority Date: 03/31/1997
• Status: Expired due to Fees

• Current Assignee: Sovoz, Inc.
• Original Assignee: Katrix, Inc.
• Inventors: Handelman, David A, Gullapalli, Vijaykumar, Lane, Stephen H
• Primary Examiner(s): Zimmerman, Mark K.
• Assistant Examiner(s): Nguyen, Kimbinh T.
• Application Number:
  US08/828,490
• Time in Patent Office: 1,422 Days
• Field of Search: 345/473, 345/474, 345/475
• US Class Current: 345/473
• CPC Class Codes: G06T 13/40 of characters, e.g. humans, animals or virtual beings

Abstract

A method and apparatus for interactively controlling and coordinating the limb movements of computer-generated articulated characters with an arbitrary number of joints. On-line computational methods are used for animating limb movements of articulated characters by solving associated forward and inverse kinematics problems in real time subject to multiple goals and constraints. The methods provide computer animated characters with fully interactive goal-directed behaviors, such as bipedal walking, through simultaneous satisfaction of position, alignment, posture, balance, obstacle avoidance, and joint limitation constraints. Goal-based motion primitives, called synergies, coordinate sets of joint movements which separately attempt to satisfy each of the above constraints. The present methods adapt character movements on-line to accommodate uneven terrain, body modifications, or changes in the environment by automatically transforming and producing joint rotations relative to the instantaneous point of contact of the body with the world. Libraries of pre-configured goal-directed behaviors, such as reaching, sitting, walking, jumping, etc., can be constructed and used to animate a wide variety of characters.

Claims

1. In a method for animating a character figure in a video image memory responsive to an input goal, said character figure being represented in said memory as having a first plurality of joints and a plurality of links coupled between respective pairs of said first plurality of joints, said plurality of links representing respective limbs of said character figure, a method for coordinating limb movements subject to at least one constraint of said character figure, said method comprising:

storing a representation of each of said first plurality of joints in said memory;

storing a representation of each of said plurality of links in said memory;

storing a representation of the respective positions of said first plurality of joints and said plurality of links in said memory;

computing, responsive to said input goal, a first set of motions subject to said constraint for each of said first plurality of joints respectively, each motion of said first set of motions being computed for each respective joint independently of the others of said first plurality of joints with said others of said first plurality of joints being held substantially motionless;

modifying said stored representations of the positions of said first plurality of joints and said plurality of links in said memory using said first set of motions; and

rendering said stored representation of said links as the limbs of said character figure in said video image memory.

2. A method in accordance with claim 1, wherein said step of computing said set of motions further comprises;

computing a first motion for a first joint of said first plurality of joints while holding said plurality of joints substantially motionless except for said first joint;

moving said first joint in phantom in said memory by storing a representation of said first motion; and

computing a second motion for a second joint of said first plurality of joints while holding said plurality of joints substantially motionless except for said second joint.

3. A method in accordance with claim 1, wherein one of said first plurality of joints of said character figure is designated as a contact joint, and said step of computing said first set of motions subject to said constraint for each of said first plurality of joints, includes computing said first set of motions substantially in the order from a distal joint to a proximal joint, relative to said contact joint.

4. A method in accordance with claim 1, wherein one of said first plurality of joints of said character figure is designated as a contact joint, and said step of computing said first set of motions subject to said constraint for each of said first plurality of joints, includes computing said first set of motions substantially in the order from a proximal joint to a distal joint, relative to said contact joint.

5. A method in accordance with claim 1, wherein one of said first plurality of joints of said character figure is designated as a contact joint, and said step of computing said first set of motions subject to said constraint for each of said first plurality of joints, includes computing said first set of motions in an arbitrary order relative to said contact joint.

6. A method in accordance with claim 1, wherein each motion of said first set of motions is an angular rotation of one of said first plurality of joints.

7. A method in accordance with claim 1, wherein one of said first plurality of joints is designated as the control joint to be positioned, and wherein said input goal is a point in space is defined as the goal point which is the desired location in space for said control joint, and wherein one of said first set of motions is the motion to position a proximal joint relative to said control joint, said step of computing said motion for said proximal joint comprises rotating said proximal joint while holding the others of said first set of joints substantially motionless to minimize the position error between said control joint and said goal point.

8. A method in accordance with claim 1, wherein one of said first plurality of joints is designated as the control joint to be positioned, and wherein said input goal is a point in space is defined as the goal point which is the desired location in space for said control joint, and wherein one of said first set of motions is the motion to position a proximal joint relative to said control joint, said step of computing said motion for said proximal joint comprises rotating said proximal joint while holding the others of said first set of joints substantially motionless, so that the distance between the next proximal joint relative to said proximal joint and the control joint is substantially the same as the distance between the next proximal joint and the desired goal point location.

9. A method in accordance with claim 1, wherein said constraint is position.

10. A method in accordance with claim 1, wherein said constraint is alignment.

11. A method in accordance with claim 1, wherein said constraint is obstacle avoidance.

12. A method in accordance with claim 1, wherein said constraint is balance.

13. A method in accordance with claim 1, wherein said constraint is posture.

14. A method in accordance with claim 1, wherein said constraint is position, and wherein one of said first plurality of joints is designated as the control joint to be positioned, and wherein said input goal is a point in space is defined as the goal point which is the desired location in space for said control joint, and wherein one of said first set of motions is the motion of a proximal joint relative to said control joint, said step of computing said motion for said proximal joint comprises

rotating said proximal joint while holding the others of said first set of joints substantially motionless to minimize the error between said control joint and said goal point;

and

rotating said proximal joint while holding the others of said first set of joints substantially motionless, so that the distance between the next proximal joint relative to said proximal joint and the control joint is substantially the same as the distance between the next proximal joint and the desired goal point location.

15. A method in accordance with claim 1, wherein said constraint is alignment, and wherein one of said first plurality of links is designated as the link to be aligned, and wherein said input goal is a line in space is defined as the goal link which is the desired direction in space for said control link, and wherein one of said first set of motions is the motion of a proximal joint relative to said control link, said step of computing said motion for said proximal joint comprises

rotating said proximal joint while holding the others of said first set of joints substantially motionless to minimize the error between said control joint and said goal point;

and

rotating said proximal joint while holding the others of said first set of joints substantially motionless, so that the distance between the next proximal joint relative to said proximal joint and the control joint is substantially the same as the distance between the next proximal joint and the desired goal point location.

16. A method in accordance with claim 1, wherein said constraint is obstacle avoidance, and wherein one of said first plurality of joints is designated as the control joint to be positioned, and wherein said input goal is a point in space is defined as the goal point which is the desired location in space for said control joint to avoid, and wherein one of said first set of motions is the motion of a proximal joint relative to said control joint, said step of computing said motion for said proximal joint comprises

rotating said proximal joint while holding the others of said first set of joints substantially motionless to maximize the error between said control joint and said goal point;

and

rotating said proximal joint while holding the others of said first set of joints substantially motionless, so that the distance between the next proximal joint relative to said proximal joint and the control joint is substantially the same as the distance between the next proximal joint and the desired goal point location.

17. A method in accordance with claim 1, wherein said constraint is balance, said links have a respective mass associated therewith and a designated center of mass for said plurality of links, and wherein the center of mass of at least two of said first plurality of links is designated as the control center of mass to be positioned, and wherein said input goal is a point in space is defined as the goal point which is the desired location in space for said designated center of mass for said plurality of links, and wherein one of said first set of motions is the motion of a proximal joint to position said control center of mass relative to said goal center of mass, said step of computing said motion for said proximal joint comprises

rotating said proximal joint while holding the others of said first set of joints substantially motionless to minimize the error between said control center of mass and said goal center of mass;

and

rotating said proximal joint while holding the others of said first set of joints substantially motionless, so that the distance between the next proximal joint relative to said proximal joint and the control center of mass is substantially the same as the distance between the next proximal joint and the desired goal center of mass location.

18. In a method for animating a character figure in a video image memory responsive to an input goal, said character figure being represented in said memory as having a first plurality of joints and a plurality of links coupled between respective pairs of said first plurality of joints, said plurality of links representing respective limbs of said character figure, a method for coordinating limb movements subject to respective first and second constraints of said character figure, said method comprising:

storing a representation of each of said first plurality of joints in said memory;

storing a representation of each of said plurality of links in said memory;

storing a representation of the respective positions of said first plurality of joints and said plurality of links in said memory;

computing, responsive to said input goal, a first set of motions subject to said first constraint for each of said first plurality of joints respectively;

computing, responsive to said input goal, a second set of motions subject to said second constraint for each of said first plurality of joints respectively;

combining said first set of motions with said second set of motions to form a combined set motions;

modifying said stored representation of the positions of said first plurality of joints and said plurality of links in said memory using said combined set of motions; and

rendering said stored representation of said links as the limbs of said character figure in said video image memory.

19. A method in accordance with claim 18, wherein said steps of computing said first set of motions and said second set of motions, respectively, further comprises;

computing, responsive to said input goal, a first set of motions subject to said first constraint for each of said first plurality of joints respectively, wherein each motion of said first set of motions is computed for each respective joint independently of the others of said first plurality of joints with said others of said first plurality of joints being held substantially motionless; and

computing, responsive to said input goal, a second set of motions subject to said second constraint for each of said first plurality of joints respectively, wherein each motion of said second set of motions is computed for each respective joint independently of the others of said first plurality of joints with said others of said first plurality of joints being held substantially motionless.

20. A method in accordance with claim 18, wherein said steps of computing said first set of motions and said steps of computing said second set of motions, respectively, each further comprises;

computing a first motion for a first joint of said first plurality of joints while holding said plurality of joints substantially motionless except for said first joint;

moving said first joint in phantom in said memory by storing a representation of said first motion; and

computing a second motion for a second joint of said first plurality of joints while holding said plurality of joints substantially motionless except for said second joint.

24. A method in accordance with claim 18, wherein one of said first plurality of joint s of said character figure is designated as a contact joint, and said step of computing said first set of motions subject to said first constraint for each of said first plurality of joints, includes computing said first set of motions substantially in the order from a distal joint to a proximal joint, relative to said contact joint.

25. A method in accordance with claim 18, wherein one of said first plurality of joints of said character figure is designated as a contact joint, and said step of computing said first set of motions subject to said first constraint for each of said first plurality of joints, includes computing said first set of motions substantially in the order from a proximal joint to a distal joint, relative to said contact joint.

26. A method in accordance with claim 18, wherein each motion of said first set of motions is an angular rotation of one of said first plurality of joints.

27. A method in accordance with claim 18, wherein one of said first plurality of joints is designated as the control joint to be positioned, and wherein said input goal is a point in space is defined as the goal point which is the desired location in space for said control joint, and wherein one of said first set of motions is the motion to position a proximal joint relative to said control joint, said step of computing said motion for said proximal joint comprises rotating said proximal joint while holding the others of said first set of joints substantially motionless to minimize the error between said control joint and said goal point.

28. A method in accordance with claim 18, wherein one of said first plurality of joints is designated as the control joint to be positioned, and wherein said input goal is a point in space is defined as the goal point which is the desired location in space for said control joint, and wherein one of said first set of motions is the motion to position a proximal joint relative to said control joint, said step of computing said motion for said proximal joint comprises rotating said proximal joint while holding the others of said first set of joints substantially motionless, so that the distance between the next proximal joint relative to said proximal joint and the control joint is substantially the same as the distance between the next proximal joint and the desired goal point location.

29. A method in accordance with claim 18, wherein said first constraint is chosen from the group consisting of alignment, posture, balance, obstacle avoidance and joint limitation, and said second constraint chosen from remaining group of alignment, posture, balance, obstacle avoidance and joint limitation, said remaining group not including said first constraint.

30. A method in accordance with claim 18, wherein said first constraint is position and said second constraint is alignment.

31. A method in accordance with claim 18, wherein said first constraint is position and said second constraint is obstacle avoidance.

32. A method in accordance with claim 18, wherein said first constraint is position and said second constraint is balance.

33. A method in accordance with claim 18, wherein said first constraint is position and said second constraint is posture.

34. A method in accordance with claim 18, wherein said first constraint is obstacle avoidance and said second constraint is balance.

35. A method in accordance with claim 18, wherein said first constraint is balance and said second constraint is posture.

21. A method in accordance with 18, wherein said step of combining said first set of motions with said second set of motions to form a combined set motions comprises the weighted sum of said first and second set of motions.

22. A method in accordance with 18, wherein said step of combining said first set of motions with said second set of motions to form a combined set motions comprises the priority based selection of said first and second set of motions.

23. A method in accordance with 18, wherein said step of combining said first set of motions with said second set of motions to form a combined set motions comprises the winner take all selection of said first and second set of motions.

36. In a method for animating a character figure in a video image memory responsive to an input goal, said video image memory depicting an environment in world coordinates, said character figure being represented in said memory as having a first plurality of joints and a plurality of links coupled between respective pairs of said first plurality of joints, said plurality of links representing respective limbs of said character figure, a method for coordinating limb movements subject to at least one constraint of said character figure, said method comprising:

storing a representation of each of said first plurality of joints in said memory;

storing a representation of each of said plurality of links in said memory;

storing a representation of the respective positions of said first plurality of joints and said plurality of links in said memory;

selecting an initial joint from said first plurality of joints as a first contact joint;

generating a contact chain from said initial joint selected as said first contact joint, wherein said contact chain indicates the order in which relative transformation matrices are multiplied to determine the location of each of said first plurality of joints in said world coordinates;

computing, responsive to said input goal, a first set of motions subject to said constraint for each of said first plurality of joints;

modifying said stored representations of the positions of said first plurality of joints and said plurality of links in said memory using said first set of motions; and

rendering said stored representation of said links as the limbs of said character figure in said video image memory in said world coordinates.

37. A method in accordance with claim 36, wherein said step of computing said first set of motions further comprises;

computing, responsive to said input goal, said first set of motions subject to said first constraint for each of said first plurality of joints respectively, wherein each motion of said first set of motions is computed for each respective joint independently of the others of said first plurality of joints with said others of said first plurality of joints being held substantially motionless.

38. A method in accordance with claim 36, wherein said step of computing said first set of motions, further comprises;

computing a first motion for a first joint of said first plurality of joints while holding said first plurality of joints substantially motionless except for said first joint;

moving said first joint in phantom in said memory by storing a representation of said first motion; and

computing a second motion for a second joint of said first plurality of joints while holding said first plurality of joints substantially motionless except for said second joint.

39. A method in accordance with claim 36, further comprising:

selecting a second joint from said first plurality of joints as a second contact joint;

generating a second contact chain from said second joint selected as said second contact joint, wherein said second contact chain indicates the order in which relative transformation matrices are multiplied to determine the location of each of said first plurality of joints in said world coordinates;

computing, responsive to said input goal, a second set of motions subject to said constraint for each of said first plurality of joints;

modifying said stored representations of the positions of said first plurality of joints and said plurality of links in said memory using said second set of motions; and

rendering said stored representation of said links as the limbs of said character figure in said video image memory in said world coordinates.

40. In a method for animating a character figure in a video image memory responsive to an input goal for coordinating limb movements and subject to the constraint of balance of said character figure, said character figure having a first plurality of joints and a plurality of links coupled between respective pairs of said first plurality of joints, said plurality of links representing respective limbs of said character figure, wherein said links have a respective mass associated therewith and a designated center of mass for said plurality of links, wherein the method comprises:

designating a point in space as a input goal point which is the desired location in space for said designated center of mass for said plurality of links;

storing said representation of each of said first plurality of joints in said memory;

storing said representation of each of said plurality of links in said memory;

storing a representation of the respective positions of said first plurality of joints and said plurality of links in said memory;

computing, responsive to said input goal point, a set of motions subject to said balance constraint for each of said first plurality of joints respectively, such that moving said character figure by said set of motions tends to position said designated center of mass at said goal point;

modifying said stored representations of the positions of said first plurality of joints and said plurality of links in said memory using said first set of motions; and

rendering said stored representation of said links as the limbs of said character figure in said video image memory.

41. A method in accordance with claim 40, wherein said steps of computing said set of motions comprises;

computing, responsive to said input goal, a set of motions subject to said balance constraint for each of said first plurality of joints respectively, wherein each motion of said set of motions is computed for each respective joint independently of the others of said first plurality of joints with said others of said first plurality of joints being held substantially motionless.

42. A method in accordance with claim 41, wherein said step of computing said set of motions further comprises;

computing a first motion for a first joint of said first plurality of joints while holding said plurality of joints substantially motionless except for said first joint;

moving said first joint in phantom in said memory by storing a representation of said first motion; and

computing a second motion for a second joint of said first plurality of joints while holding said plurality of joints substantially motionless except for said second joint.

43. A method in accordance with claim 40, wherein one of said first plurality of joints of said character figure is designated as a contact joint, and said step of computing said set of motions subject to said balance constraint for each of said first plurality of joints, includes computing said set of motions substantially in the order from a distal joint to a proximal joint, relative to said contact joint.

44. A method in accordance with claim 40, wherein one of said first plurality of joints of said character figure is designated as a contact joint, and said step of computing said set of motions subject to said balance constraint for each of said first plurality of joints, includes computing said set of motions substantially in the order from a proximal joint to a distal joint, relative to said contactjoint.

45. A method in accordance with claim 40, wherein one of said first plurality of joints of said character figure is designated as a contact joint, and said step of computing said set of motions subject to said constraint for each of said first plurality of joints, includes computing said set of motions in an arbitrary order relative to said contact joint.

46. A method in accordance with claim 40, wherein each motion of said set of motions is an angular rotation of one of said first plurality of joints.

47. A method in accordance with claim 40, wherein the center of mass of at least two of said first plurality of links is designated as the control center of mass to be positioned, and wherein said input goal is a point in space is defined as the goal point which is the desired location in space for said designated center of mass for said plurality of links, and wherein one of said first set of motions is the motion of a proximal joint to position said control center of mass relative to said goal center of mass, said step of computing said motion for said proximal joint comprises rotating said proximal joint while holding the others of said first set of joints substantially motionless to minimize the error between said control center of mass and said goal center of mass.

48. A method in accordance with claim 40, wherein the center of mass of at least two of said first plurality of links is designated as the control center of mass to be positioned, and wherein said input goal is a point in space is defined as the goal point which is the desired location in space for said designated center of mass for said plurality of links, and wherein one of said set of motions is the motion of a proximal joint to position said control center of mass relative to said goal center of mass, said step of computing said motion for said proximal joint comprises rotating said proximal joint while holding the others of said first set of joints substantially motionless, so that the distance between the next proximal joint relative to said proximal joint and the control center of mass is substantially the same as the distance between the next proximal joint and the desired goal center of mass location.

49. In an apparatus for animating a character figure in a video image memory responsive to an input goal, said character figure being represented in said memory as having a first plurality of joints and a plurality of links coupled between respective pairs of said first plurality of joints, said plurality of links representing respective limbs of said character figure, an apparatus for coordinating limb movements subject to at least one constraint of said character figure, said apparatus comprising:

means for storing a representation of each of said first plurality of joints in said memory;

means for storing a representation of each of said plurality of links in said memory;

means for storing a representation of the respective positions of said first plurality of joints and said plurality of links in said memory;

means for computing, responsive to said input goal, a first set of motions subject to said constraint for each of said first plurality of joints respectively, each motion of said first set of motions being computed for each respective joint independently of the others of said first plurality of joints with said others of said first plurality of joints being held substantially motionless;

means for modifying said stored representations of the positions of said first plurality of joints and said plurality of links in said memory using said first set of motions; and

means for rendering said stored representation of said links as the limbs of said character figure in said video image memory.

50. An apparatus in accordance with claim 49, wherein said means for computing said set of motions further comprises;

means for computing a first motion for a first joint of said first plurality of joints while holding said plurality of joints substantially motionless except for said first joint;

means for moving said first joint in phantom in said memory by storing a representation of said first motion; and

means for computing a second motion for a second joint of said first plurality of joints while holding said plurality of joints substantially motionless except for said second joint.

51. An apparatus in accordance with claim 49, wherein one of said first plurality of joints of said character figure is designated as a contact joint, and said means for computing said first set of motions subject to said constraint for each of said first plurality of joints, includes computing said first set of motions substantially in the order from a distal joint to a proximal joint, relative to said contact joint.

52. An apparatus in accordance with claim 49, wherein one of said first plurality of joints of said character figure is designated as a contact joint, and said means for computing said first set of motions subject to said constraint for each of said first plurality of joints, includes computing said first set of motions substantially in the order from a proximal joint to a distal joint, relative to said contact joint.

53. An apparatus in accordance with claim 49, wherein one of said first plurality of joints of said character figure is designated as a contact joint, and said means for computing said first set of motions subject to said constraint for each of said first plurality of joints, includes computing said first set of motions in an arbitrary order relative to said contact joint.

54. An apparatus in accordance with claim 49, wherein each motion of said first set of motions is an angular rotation of one of said first plurality of joints.

55. An apparatus in accordance with claim 49, wherein one of said first plurality of joints is designated as the control joint to be positioned, and wherein said input goal is a point in space is defined as the goal point which is the desired location in space for said control joint, and wherein one of said first set of motions is the motion to position a proximal joint relative to said control joint, said means for computing said motion for said proximal joint comprises rotating said proximal joint while holding the others of said first set of joints substantially motionless to minimize the position error between said control joint and said goal point.

56. An apparatus in accordance with claim 49, wherein one of said first plurality of joints is designated as the control joint to be positioned, and wherein said input goal is a point in space is defined as the goal point which is the desired location in space for said control joint, and wherein one of said first set of motions is the motion to position a proximal joint relative to said control joint, said means for computing said motion for said proximal joint comprises rotating said proximal joint while holding the others of said first set of joints substantially motionless, so that the distance between the next proximal joint relative to said proximal joint and the control joint is substantially the same as the distance between the next proximal joint and the desired goal point location.

57. An apparatus in accordance with claim 49, wherein said constraint is position.

58. An apparatus in accordance with claim 49, wherein said constraint is alignment.

59. An apparatus in accordance with claim 49, wherein said constraint is obstacle avoidance.

60. An apparatus in accordance with claim 49, wherein said constraint is balance.

61. An apparatus in accordance with claim 49, wherein said constraint is posture.

62. An apparatus in accordance with claim 49, wherein said constraint is position, and wherein one of said first plurality of joints is designated as the control joint to be positioned, and wherein said input goal is a point in space is defmed as the goal point which is the desired location in space for said control joint, and wherein one of said first set of motions is the motion of a proximal joint relative to said control joint, said means for computing said motion for said proximal joint comprises

means for rotating said proximal joint while holding the others of said first set of joints substantially motionless to minimize the error between said control joint and said goal point;

and

means for rotating said proximal joint while holding the others of said first set of joints substantially motionless, so that the distance between the next proximal joint relative to said proximal joint and the control joint is substantially the same as the distance between the next proximal joint and the desired goal point location.

63. An apparatus in accordance with claim 49, wherein said constraint is alignment, and wherein one of said first plurality of links is designated as the link to be aligned, and wherein said input goal is a line in space is defined as the goal link which is the desired direction in space for said control link, and wherein one of said first set of motions is the motion of a proximal joint relative to said control link, said means for computing said motion for said proximal joint comprises

means for rotating said proximal joint while holding the others of said first set of joints substantially motionless to minimize the error between said control joint and said goal point;

and

means for rotating said proximal joint while holding the others of said first set of joints substantially motionless, so that the distance between the next proximal joint relative to said proximal joint and the control joint is substantially the same as the distance between the next proximal joint and the desired goal point location.

64. An apparatus in accordance with claim 49, wherein said constraint is obstacle avoidance, and wherein one of said first plurality of joints is designated as the control joint to be positioned, and wherein said input goal is a point in space is defined as the goal point which is the desired location in space for said control joint to avoid, and wherein one of said first set of motions is the motion of a proximal joint relative to said control joint, said means for computing said motion for said proximal joint comprises

means for rotating said proximal joint while holding the others of said first set of joints substantially motionless to maximize the error between said control joint and said goal point;

and

means for rotating said proximal joint while holding the others of said first set of joints substantially motionless, so that the distance between the next proximal joint relative to said proximal joint and the control joint is substantially the same as the distance between the next proximal joint and the desired goal point location.

65. An apparatus in accordance with claim 49, wherein said constraint is balance, said links have a respective mass associated therewith and a designated center of mass for said plurality of links, and wherein the center of mass of at least two of said first plurality of links is designated as the control center of mass to be positioned, and wherein said input goal is a point in space is defined as the goal point which is the desired location in space for said designated center of mass for said plurality of links, and wherein one of said first set of motions is the motion of a proximal joint to position said control center of mass relative to said goal center of mass, said means for computing said motion for said proximal joint comprises

means for rotating said proximal joint while holding the others of said first set of joints substantially motionless to minimize the error between said control center of mass and said goal center of mass;

and

means for rotating said proximal joint while holding the others of said first set of joints substantially motionless, so that the distance between the next proximal joint relative to said proximal joint and the control center of mass is substantially the same as the distance between the next proximal joint and the desired goal center of mass location.

66. In an apparatus for animating a character figure in a video image memory responsive to an input goal, said character figure being represented in said memory as having a first plurality of joints and a plurality of links coupled between respective pairs of said first plurality of joints, said plurality of links representing respective limbs of said character figure, an apparatus for coordinating limb movements subject to respective first and second constraints of said character figure, said apparatus comprising:

means for storing a representation of each of said first plurality of joints in said memory;

means for storing a representation of each of said plurality of links in said memory;

means for storing a representation of the respective positions of said first plurality of joints and said plurality of links in said memory;

means for computing, responsive to said input goal, a first set of motions subject to said first constraint for each of said first plurality of joints respectively;

means for computing, responsive to said input goal, a second set of motions subject to said second constraint for each of said first plurality of joints respectively;

means for combining said first set of motions with said second set of motions to form a combined set motions;

means for modifying said stored representation of the positions of said first plurality of joints and said plurality of links in said memory using said combined set of motions; and

means for rendering said stored representation of said links as the limbs of said character figure in said video image memory.

67. An apparatus in accordance with claim 66, wherein said steps of computing said first set of motions and said second set of motions, respectively, further comprises;

means for computing, responsive to said input goal, a first set of motions subject to said first constraint for each of said first plurality of joints respectively, wherein each motion of said first set of motions is computed for each respective joint independently of the others of said first plurality of joints with said others of said first plurality of joints being held substantially motionless; and

means for computing, responsive to said input goal, a second set of motions subject to said second constraint for each of said first plurality of joints respectively, wherein each motion of said second set of motions is computed for each respective joint independently of the others of said first plurality of joints with said others of said first plurality of joints being held substantially motionless.

68. An apparatus in accordance with claim 66, wherein said steps of computing said first set of motions and said steps of computing said second set of motions, respectively, each further comprises;

means for computing a first motion for a first joint of said first plurality of joints while holding said plurality of joints substantially motionless except for said first joint;

means for moving said first joint in phantom in said memory by storing a representation of said first motion; and

means for computing a second motion for a second joint of said first plurality of joints while holding said plurality of joints substantially motionless except for said second joint.

72. An apparatus in accordance with claim 66, wherein one of said first plurality of joints of said character figure is designated as a contact joint, and said means for computing said first set of motions subject to said first constraint for each of said first plurality of joints, includes computing said first set of motions substantially in the order from a distal joint to a proximal joint, relative to said contact joint.

73. An apparatus in accordance with claim 66, wherein one of said first plurality of joints of said character figure is designated as a contact joint, and said means for computing said first set of motions subject to said first constraint for each of said first plurality of joints, includes computing said first set of motions substantially in the order from a proximal joint to a distal joint, relative to said contact joint.

74. An apparatus in accordance with claim 66, wherein each motion of said first set of motions is an angular rotation of one of said first plurality of joints.

75. An apparatus in accordance with claim 66, wherein one of said first plurality of joints is designated as the control joint to be positioned, and wherein said input goal is a point in space is defined as the goal point which is the desired location in space for said control joint, and wherein one of said first set of motions is the motion to position a proximal joint relative to said control joint, said means for computing said motion for said proximal joint comprises rotating said proximal joint while holding the others of said first set of joints substantially motionless to minimize the error between said control joint and said goal point.

76. An apparatus in accordance with claim 66, wherein one of said first plurality of joints is designated as the control joint to be positioned, and wherein said input goal is a point in space is defined as the goal point which is the desired location in space for said control joint, and wherein one of said first set of motions is the motion to position a proximal joint relative to said control joint, said means for computing said motion for said proximal joint comprises rotating said proximal joint while holding the others of said first set of joints substantially motionless, so that the distance between the next proximal joint relative to said proximal joint and the control joint is substantially the same as the distance between the next proximal joint and the desired goal point location.

77. An apparatus in accordance with claim 66, wherein said first constraint is chosen from the group consisting of alignment, posture, balance, obstacle avoidance and joint limitation, and said second constraint chosen from remaining group of alignment, posture, balance, obstacle avoidance and joint limitation, said remaining group not including said first constraint.

78. An apparatus in accordance with claim 66, wherein said first constraint is position and said second constraint is alignment.

79. An apparatus in accordance with claim 66, wherein said first constraint is position and said second constraint is obstacle avoidance.

80. An apparatus in accordance with claim 66, wherein said first constraint is position and said second constraint is balance.

81. An apparatus in accordance with claim 66, wherein said first constraint is position and said second constraint is posture.

82. An apparatus in accordance with claim 66, wherein said first constraint is obstacle avoidance and said second constraint is balance.

83. An apparatus in accordance with claim 66, wherein said first constraint is balance and said second constraint is posture.

69. An apparatus in accordance with 66, wherein said means for combining said first set of motions with said second set of motions to form a combined set motions comprises the weighted sum of said first and second set of motions.

70. An apparatus in accordance with 66, wherein said means for combining said first set of motions with said second set of motions to form a combined set motions comprises the priority based selection of said first and second set of motions.

71. An apparatus in accordance with 66, wherein said means for combining said first set of motions with said second set of motions to form a combined set motions comprises the winner take all selection of said first and second set of motions.

84. In an apparatus for animating a character figure in a video image memory responsive to an input goal, said video image memory depicting an environment in world coordinates, said character figure being represented in said memory as having a first plurality of joints and a plurality of links coupled between respective pairs of said first plurality of joints, said plurality of links representing respective limbs of said character figure, an apparatus for coordinating limb movements subject to at least one constraint of said character figure, said apparatus comprising:

means for storing a representation of each of said first plurality of joints in said memory;

means for storing a representation of each of said plurality of links in said memory;

means for storing a representation of the respective positions of said first plurality of joints and said plurality of links in said memory;

means for selecting an initial joint from said first plurality of joints as a first contact joint;

means for generating a contact chain from said initial joint selected as said first contact joint, wherein said contact chain indicates the order in which relative transformation matrices are multiplied to determine the location of each of said first plurality of joints in said world coordinates;

.

means for computing, responsive to said input goal, a first set of motions subject to said constraint for each of said first plurality of joints;

means for modifying said stored representations of the positions of said first plurality of joints and said plurality of links in said memory using said first set of motions; and

means for rendering said stored representation of said links as the limbs of said character figure in said video image memory in said world coordinates.

85. An apparatus in accordance with claim 84, wherein said means for computing said first set of motions further comprises;

means for computing, responsive to said input goal, said first set of motions subject to said first constraint for each of said first plurality of joints respectively, wherein each motion of said first set of motions is computed for each respective joint independently of the others of said first plurality of joints with said others of said first plurality of joints being held substantially motionless.

86. An apparatus in accordance with claim 84, wherein said means for computing said first set of motions, further comprises;

means for computing a first motion for a first joint of said first plurality of joints while

holding said first plurality of joints substantially motionless except for said first joint;

means for moving said first joint in phantom in said memory by storing a representation of said first motion; and

means for computing a second motion for a second joint of said first plurality of joints while holding said first plurality of joints substantially motionless except for said second joint.

87. An apparatus in accordance with claim 84, further comprising:

means for selecting a second joint from said first plurality of joints as a second contact joint;

means for generating a second contact chain from said second joint selected as said second contact joint, wherein said second contact chain indicates the order in which relative transformation matrices are multiplied to determine the location of each of said first plurality of joints in said world coordinates;

means for computing, responsive to said input goal, a second set of motions subject to said constraint for each of said first plurality of joints;

means for modifying said stored representations of the positions of said first plurality of joints and said plurality of links in said memory using said second set of motions; and

means for rendering said stored representation of said links as the limbs of said character figure in said video image memory in said world coordinates.

88. In an apparatus for animating a character figure in a video image memory responsive to an input goal for coordinating limb movements and subject to the constraint of balance of said character figure, said character figure having a first plurality of joints and a plurality of links coupled between respective pairs of said first plurality of joints, said plurality of links representing respective limbs of said character figure, wherein said links have a respective mass associated therewith and a designated center of mass for said plurality of links, wherein the apparatus comprises:

means for designating a point in space as a input goal point which is the desired location in space for said designated center of mass for said plurality of links;

means for storing said representation of each of said first plurality of joints in said memory;

means for storing said representation of each of said plurality of links in said memory;

means for storing a representation of the respective positions of said first plurality of joints and said plurality of links in said memory;

means for computing, responsive to said input goal point, a set of motions subject to said balance constraint for each of said first plurality of joints respectively, such that moving said character figure by said set of motions tends to position said designated center of mass at said goal point;

means for modifying said stored representations of the positions of said first plurality of joints and said plurality of links in said memory using said first set of motions; and

means for rendering said stored representation of said links as the limbs of said character figure in said video image memory.

89. An apparatus in accordance with claim 88, wherein said steps of computing said set of motions comprises;

means for computing, responsive to said input goal, a set of motions subject to said balance constraint for each of said first plurality of joints respectively, wherein each motion of said set of motions is computed for each respective joint independently of the others of said first plurality of joints with said others of said first plurality of joints being held substantially motionless.

90. An apparatus in accordance with claim 89, wherein said means for computing said set of motions further comprises;

means for computing a first motion for a first joint of said first plurality of joints while holding said plurality of joints substantially motionless except for said first joint;

means for moving said first joint in phantom in said memory by storing a representation of said first motion; and

means for computing a second motion for a second joint of said first plurality of joints while holding said plurality of joints substantially motionless except for said second joint.

91. An apparatus in accordance with claim 88, wherein one of said first plurality of joints of said character figure is designated as a contact joint, and said means for computing said set of motions subject to said balance constraint for each of said first plurality of joints, includes computing said set of motions substantially in the order from a distal joint to a proximal joint, relative to said contact joint.

92. An apparatus in accordance with claim 88, wherein one of said first plurality of joints of said character figure is designated as a contact joint, and said means for computing said set of motions subject to said balance constraint for each of said first plurality of joints, includes computing said set of motions substantially in the order from a proximal joint to a distal joint, relative to said contact joint.

93. An apparatus in accordance with claim 88, wherein one of said first plurality of joints of said character figure is designated as a contact joint, and said means for computing said set of motions subject to said constraint for each of said first plurality of joints, includes computing said set of motions in an arbitrary order relative to said contact joint.

94. An apparatus in accordance with claim 88, wherein each motion of said set of motions is an angular rotation of one of said first plurality of joints.

95. An apparatus in accordance with claim 88, wherein the center of mass of at least two of said first plurality of links is designated as the control center of mass to be positioned, and wherein said input goal is a point in space is defined as the goal point which is the desired location in space for said designated center of mass for said plurality of links, and wherein one of said first set of motions is the motion of a proximal joint to position said control center of mass relative to said goal center of mass, said means for computing said motion for said proximal joint comprises rotating said proximal joint while holding the others of said first set of joints substantially motionless to minimize the error between said control center of mass and said goal center of mass.

96. An apparatus in accordance with claim 88, wherein the center of mass of at least two of said first plurality of links is designated as the control center of mass to be positioned, and wherein said input goal is a point in space is defined as the goal point which is the desired location in space for said designated center of mass for said plurality of links, and wherein one of said set of motions is the motion of a proximal joint to position said control center of mass relative to said goal center of mass, said means for computing said motion for said proximal joint comprises rotating said proximal joint while holding the others of said first set of joints substantially motionless, so that the distance between the next proximal joint relative to said proximal joint and the control center of mass is substantially the same as the distance between the next proximal joint and the desired goal center.