Manipulation of Graphic Structures Using Inverse Kinematics

This invention relates to manipulation of graphic structures.

FIG. 1 illustrates an example of a graphic structure 100. Kinematics is an approach to manipulating a graphic structure by construing the structure (or a portion of the structure) as having a recursive branching arrangement, beginning with a root joint 110 branching off to zero or more joints 120, 130, and 140, each of which may, in turn, branch off to zero or more joints 121 and 141 and so on until each branch eventually terminates in an end effector 122, 130, and 142.

Graphic structures are used in fields such as computer animation. For example, FIG. 2 illustrates how the graphic structure 100 of FIG. 1 may be used to represent the upper body of a human, with root joint 210 and joint 230 representing the torso, joints 220, 221, 240, and 241 representing the shoulders and elbows, and end effectors 222 and 242 representing the wrists.

Forward kinematics addresses the problem: "Assuming a stationary root joint and given specific joint angles at the structure's joints, find the position of the end effectors." With reference to the "arms" of FIG. 2, the problem would be to find the positions of the wrists 222 and 242, given the position of the root 210 and the angles at the shoulders 220 and 240, and elbows 221 and 231. Only one configuration of the structure satisfies these conditions, and is readily determined by starting at the root joint 210 and positioning the joints 220, 221, 240, and 241, based on the given joint angles until the positions of the end effectors 222 and 242 are determined.

Inverse kinematics addresses the reverse problem: "Assuming a stationary root joint and given specific goal positions for the structure's end effectors, find a configuration of the structure that positions the end effectors at the goal positions." Again using the arms of FIG. 2, the problem involves finding angles at the shoulders 220 and 240, and elbows 221 and 241, to place the wrists 222 and 242 at specified goal positions. Unlike forward kinematics, inverse kinematics addresses a problem that may have multiple solutions, as multiple sets of joint angles may satisfy the placement requirement of the end effectors.

In general, in one aspect, the invention features a computer-implemented method of manipulating a graphic structure having joint angles from an initial configuration towards a goal configuration by a succession of iterations, each of which derives an update configuration from a prior configuration.

A regular iteration determines at least one test configuration by modifying fewer than all of the joint angles of the prior configuration, determines, for each test configuration, an improvement value reflecting the improvement between the differences of the prior configuration and the test configuration with respect to the goal configuration, and selects a test configuration as the updated configuration based on the improvement values.

Certain implementations of the invention may include one or more of the following features.

Each test configuration modifies a single joint angle of the prior configuration.

The method further assigns the updated configuration as the goal configuration if the updated configuration satisfies termination criterion. For example, termination criterion may be met if the difference between the updated configuration and the goal configuration is less than a predetermined threshold.

The method further evaluates convergence of the graphic structure towards the goal configuration based on successive iterations, and if the convergence evaluation meets alternate method criteria, uses an alternate iteration method which determines test configurations by modifying up to all of the joint angles of the prior configuration. A possible alternate iteration method identifies a pattern of joint angles that have been updated in successive iterations and determines the updated configuration from the prior configuration by modifying each of the joint angles in the identified pattern. The alternate iteration method further identifies the pattern of joint angles by determining increments by which each of the pattern angles was updated in the successive iterations, and determines the updated configuration by modifying each of the joint angles by an increment based on the determined increments for the pattern angles.

The determined test configurations minimize a difference between the test configuration and the goal configuration.

The graphic structure further comprises at least one end effector, and the method determines for each test configuration, a test position for each end effector and determines the improvement value for each test configuration based on the test positions of each end effector. The method may determine each test configuration by calculating, for each test configuration, a partial derivative for each end effector with respect to the modified joint angles, and determining a test configuration that minimizes a difference between the test configuration and the goal configuration based on the partial derivatives.

In general, in another aspect, the invention enables use of the computer-implemented method through a memory device storing computer-readable instructions for aiding the computer to manipulate the graphic structure.

By using both a computationally simple method and a quickly converging method, the invention provides an iterative method for manipulating a graphic structure that efficiently converges to a goal configuration.

Other features and advantages of the invention will become apparent from the following description and from the claims.

FIGS. 1 and 2 illustrate graphic structures.

FIG. 3 is a flow diagram of a method of manipulating a graphic structure.

FIG. 4 illustrates a graphic structure.

FIGS. 5-7 illustrate derivation of a method of manipulating a graphic structure.

FIG. 8 illustrates a programmable processing system.

The invention addresses manipulation of a graphic structure (or a portion of a graphic structure) having at least two dimensions, such as the structure 200 illustrated in FIG. 2.

Relative to a position of a root joint (e.g., joint 110 of FIG. 1), a configuration describing a specific position of a graphic structure may be described by a set of x joint angles, with each joint angle corresponding to a single degree of freedom. Thus, a joint having more than one degree of freedom will correspond to more than one joint angle. For a configuration .theta..sub.k of a structure, let:

.theta..sub.k : represent the x joint angles of the structure, {.theta..sub.k,1, .theta..sub.k,2, . . . , .theta..sub.k,x };

e.sub.k : represent the positions of the structure's n end effectors {e.sub.k,1, e.sub.k,2, . . . , e.sub.k,n }, typically represented in coordinate locations;

g: represent a set of n goal positions corresponding to the n end effectors {g.sub.1, g.sub.2, . . . , g.sub.n }, where each element of g is typically represented by coordinate locations; and

F(e.sub.k): represent an error function indicating how close end effectors e.sub.k are to goal positions g. The precise function may vary. As used below, F(e.sub.k) is the sum of the squared distances between each end effector e.sub.k,i and its corresponding goal position g.sub.i. Accordingly, F is always positive and decreases as the total distance between the end effectors and the goal positions decrease. F(e.sub.k)=0 indicates that e.sub.k =g.

The invention manipulates a graphic structure from an initial configuration .theta..sub.0 towards a goal configuration .theta..sub.g, which positions the end effectors at or near the desired goal positions. One embodiment determines the goal configuration .theta..sub.g using a numerical iteration technique that in a regular iteration method, updates an approximation .theta..sub.k-1 to a next approximation .theta..sub.k by adjusting a single joint angle to reduce the value of F(e.sub.k-1).

The flow diagram of FIG. 3 illustrates how one embodiment manipulates a graphic structure to a goal configuration. The variable k represents a counter for the number of single-angle update iterations and is initially set to 1 (310). Initial approximation .theta..sub.0 is predetermined, and .theta..sub.k represents a configuration determined in the kth iteration.

320, 330, and 340 describe a single angle update method that modifies only one joint angle between sequential iterations.

To determine which angle to modify in updating a configuration .theta..sub.(k-1) to a configuration .theta..sub.k, the embodiment determines a .DELTA.F for each of the x joint angles, the maximum decrease in F(e.sub.(k-1)) that can be effected by a change in joint angle .theta..sub.(k-1)i (320).

For example, for the graphic structure 400 of FIG. 4, .theta..sub.(k-1), 1 and .theta..sub.(k-1), 2 are separately evaluated to determine the minimum distance (reflected by a minimum value of F) between end effector 440 and goal position 450 that can be achieved by changing a single joint angle.

The position of a joint relative to a root position may be expressed using a notation method using transform matrices, which is discussed in references such as JAMES D. FOLEY ET AL., COMPUTER GRAPHICS: PRINCIPLES AND PRACTICE 213-226 (2d ed. 1990), incorporated by reference.

Transform matrix notation uses a coordinate frame for each joint, and each transform matrix describes a relation between joints. One embodiment uses a transform matrix T.sub.i to describe the rotation between joints in a single degree of freedom, corresponding to a joint angle .theta..sub.i of a graphic structure. To represent a rotation about the z axis, T.sub.i has the following format: ##EQU1##

Transform matrices for rotations about the x and y axes are similar, as discussed in the above reference. The axis of rotation for a specific joint angle is an attribute of the joint and is readily determined. Thus, while the following discussion uses the example of rotation about the z axis, the embodiment described handles rotation about the x and y axes as well.

Using matrix notation for graphic structure 400 having two joint angles .theta..sub.(k-1),1 and .theta..sub.(k-1),2, the position of end effector 440 relative to the root 410 is represented by formula:

where e.sub.r and e.sub.e are coordinates in three dimensional space, expressed in homogenous notation. e.sub.r is expressed in the coordinate frame of the root (›e.sub.rx, e.sub.ry, e.sub.rz, 1!), and e.sub.e is expressed in its own coordinate frame (›e.sub.ex, e.sub.ey, e.sub.ez, 1!). Transform matrices T.sub.i have the general format of EQ 1.

In addition to the rotational relationship described by joint angle .theta..sub.i and transform matrix T.sub.i, the spatial relationship between linked joints can also include, for example, translation and twist factors. However, the embodiment expresses each of these factors independently from the rotation reflected by joint angle .theta..sub.i in a separate matrix S.sub.i.

The embodiment finds the single joint angle corresponding to the greatest potential decrease in F (.DELTA.F), indicating that adjustment of that joint angle results in an updated configuration with the greatest improvement over the prior configuration with respect to distance from the goal configuration. The embodiment finds this angle using partial derivatives of F with respect to individual joint angles, derived using the partial derivatives of the end effector positions of the graphic structure with respect to the individual joint angles.

For example, for the graphic structure 400 of FIG. 4, two partial derivatives of the position of end effector 440 are calculated: one with respect to .theta..sub.(k-1),1 and one with respect to .theta..sub.(k-1),2.

In general, for an end effector e.sub.j having y joint angles between itself and the root, the partial derivative e' of e.sub.j with respect to a single joint angle .theta..sub.i may be expressed as: ##EQU2##

Each matrix S is independent of .theta..sub.i, and as each joint angle .theta..sub.i corresponds to a transform matrix T.sub.i, each of the transform matrices other than T.sub.i is also independent of .theta..sub.i. Accordingly, EQ 3 reduces to: ##EQU3##

EQ 4 illustrates that the partial derivative of an end effector position with respect to a single joint angle .theta..sub.i is calculated by replacing the corresponding transform matrix T.sub.i with its partial derivative with respect to .theta..sub.i.

The partial derivative of a rotation matrix T.sub.i about the z axis, as shown in EQ 1, is: ##EQU4##

Comparing EQ 1 to EQ 5 illustrates that the partial derivative T.sub.i ' is: ##EQU5##

Thus, letting ##EQU6## we see that in general, for a matrix having the form ›c.sub.1 c.sub.2 c.sub.3 c.sub.4 !, where each c.sub.i is a column of one or more entries:

EQS 7 and 8 illustrate that T.sub.i ', the partial derivative of a transform matrix T.sub.i, is determined without any calculation by switching and/or negating columns. More specifically, the first column of T.sub.i ' is the second column of T.sub.i ; the second column of T.sub.i ' is the negated first column of T.sub.i ; and the third and fourth columns of T.sub.i ' are zeroes. Thus, T.sub.i ' is readily determined, and calculation of EQ 4 is straight forward.

The embodiment calculates EQ 4 for each .theta..sub.i of each end effector of a graphic structure. Methods of determining the set of partial derivatives may vary. One embodiment calculates a partial derivative of an end effector position e.sub.r with respect to joint angle .theta..sub.i by letting:

(1) p.sub.i represent e.sub.e T.sub.1 S.sub.1 . . . T.sub.i, a first partial calculation of EQ 4;

(2) q.sub.i represent e.sub.e T.sub.1 S.sub.1 . . . T.sub.i ', a modification of p.sub.i ; and

(3) R.sub.i represent S.sub.1 T.sub.(i+1) S.sub.(i+1) . . . T.sub.y S.sub.y, a remaining portion of the matrix string of EQ 4.

Letting PD.sub.i represent a partial derivative of an end effector with respect to a joint angle .theta..sub.i, the embodiment calculates PD.sub.i for each of the joint angles by the following steps:

1. Initially, i=1, p.sub.0 =q.sub.0 =e.sub.e, R.sub.y =S.sub.y.

2. Calculate p.sub.i =p.sub.i-1 *T.sub.i.

3. Calculate q.sub.i =p.sub.i-1 *T.sub.i '=p.sub.i *X'. This step may be calculated without computation by switching and negating columns, as discussed above.

4. If i=y go to step 5. Otherwise, increment i and return to step 2.

5. Calculate PD.sub.i =q.sub.i *R.sub.i.

6. If i=1, go to step 8. Otherwise, decrement i.

7. Calculate R.sub.i =S.sub.i *T.sub.i+1 *R.sub.i+1, and return to step 5.

8. End.

Thus, for the example of graphic structure 400 of FIG. 4, partial derivatives are calculated as follows:

p.sub.0 =q.sub.0 =e.sub.e ; R.sub.2 =S.sub.2

p.sub.i =p.sub.0 *T.sub.1

q.sub.1 =p.sub.1 *X'

p.sub.2 =p.sub.1 *T.sub.2

q.sub.2 =p.sub.2 *X'

PD.sub.2 =q.sub.2 *R.sub.2

R.sub.1 =S.sub.1 *T.sub.2 *R.sub.2

PD.sub.1 =q.sub.1 *R.sub.1

The second order derivatives are calculated in the same manner, except that matrix T.sub.i ' is replaced by matrix T.sub.i ": ##EQU7##

Comparing EQS 1, 5, and 9 illustrates that the partial derivative T.sub.i " is: ##EQU8##

Thus, letting: ##EQU9## we see that in general, for a matrix having the form ›c.sub.1 c.sub.2 c.sub.3 c.sub.4 !, where each c.sub.i is a column of one or more entries:

EQS 11 and 12 show that T.sub.i ", like T.sub.i ', is determined without any calculation. The second partial derivative has a first column that is the negated first column of T.sub.i and the second column that is the negated second column of T.sub.i. The third and fourth columns of T.sub.i " are zeroes.

This process thus produces first and second order derivatives of an end effector position with respect to a change in a single joint angle. Using three dimensional coordinate components (x, y, z), a first order partial derivative of an end effector with respect to a joint angle .theta..sub.i in a configuration .theta..sub.k has coordinates (e.sub.x ' e.sub.y ' e.sub.z ') and a second order partial derivative with respect to joint angle .theta..sub.i has coordinates (e.sub.x ", e.sub.y ", e.sub.z ").

One embodiment uses the sum of the squares of the distances between the end effectors and their corresponding goal positions for error function F. Using goal positions g, and the first and second order derivatives calculated for each joint angle .theta..sub.i, the values of F, F', and F" are calculated as follows: ##EQU10##

The partial derivatives F' and F" are used in minimizing error function F. Different minimization techniques may be used, and general background about iterative minimization may be found in references such as WILLIAM H. PRESS, NUMERICAL RECIPES IN C: THE ART OF SCIENTIFIC COMPUTING Ch. 10(1995), incorporated by reference.

One embodiment minimizes error function F by recognizing that if F is the sum of the squares of the distances between end effectors and goal positions and is a function of a single joint angle .theta..sub.i, F can always be written in the following form:

where A is an amplitude, .theta..sub.i is a joint angles, .omega. represents the effect of other joint angles, and k represents an offset. The derivation of EQ 14 is shown in FIG. 5.

Thus, because F has no higher order sine terms, it can be expressed as a sine function in the form of EQ 14.

The value for .theta..sub.i resulting in the smallest value of F, derived from EQ 14:

from which the resulting difference in F is derived:

Derivation of EQ 15 and EQ 16 are further shown in FIGS. 6 and 7, respectively.

After each of the joint angles .theta..sub.(k-1),i and its corresponding .DELTA.F.sub..theta.i value are evaluated, the joint angle .theta..sub.(k-1)i having the greatest .DELTA.F.sub..theta.i value is selected (330) and configuration .theta..sub.(k-1) is updated to configuration .theta..sub.k by replacing .theta..sub.(k-1)i with .theta..sub.min i (340).

Updated configuration .theta..sub.k is evaluated to determine whether it meets a termination condition (350), in which case the iterative process ends (355). For example, a possible termination condition is if end effectors .theta..sub.k come within a threshold distance from goal positions g--one embodiment recognizes such a condition by a value for F(e.sub.k) falling below a predetermined threshold. Should this occur, .theta..sub.k is assigned as the goal configuration .theta..sub.g, completing the iterative process (355).

Termination (355) may also occur if the iterative process has exceeded a predetermined limit without finding goal configuration .theta..sub.g (e.g., the process has exceeded a predetermined number of iterations or a predetermined processing time limit).

Even if termination conditions are not met, the regular iterative method described by 320, 330, and 340 may be interrupted in some situations. The practical success of an iterative technique depends in part on reducing the number of iterations required to find .theta..sub.g, which in turn depends on the update method: the faster the update method converges towards the goal configuration, the fewer iterations will be required. Thus, if termination conditions are not met, a possibility is to switch to an alternate update method (360, 365).

Generally, the embodiment switches to an alternate update method when prior iterations are determined to converge towards the goal configuration too slowly. Specific criteria may vary. For example, a cyclic pattern of the specific joint angles updated may indicate slow convergence; accordingly, one embodiment switches to an alternate update method (365) when a pattern is recognized. Another embodiment switches to an alternate update method (365) when the number of iterations exceeds a predetermined threshold. Another embodiment keeps a record of updates in sequential iterations, and if a pattern of minimal progress is detected (indicated, for example by a series of low values for .DELTA.F), an alternate method (365) is used.

A variety of alternate update methods (365) may be used. For example, the update method represented by 320, 330, and 340 modifies a single joint angle in an iteration. In some cases, convergence towards goal configuration .theta..sub.g is faster if more than one joint angle is modified in an iteration.

One embodiment uses an update method based on a variation of Powell's conjugate direction set method to update configuration .theta..sub.(k-1) by altering multiple joint angles in one iteration. Powell's method is explained in references such as WILLIAM H. PRESS, NUMERICAL RECIPES IN C: THE ART OF SCIENTIFIC COMPUTING, at 412-420.

One embodiment performs the following steps for updating a graphic structure .theta.:

1. Perform the normal single angle update method until a pattern in update angles is recognized. For example, if the pattern angles in consecutive iterations are . . . .theta..sub.1, .theta..sub.3, .theta..sub.4, .theta..sub.1, .theta..sub.3, .theta..sub.4, . . . a pattern of .theta..sub.1, .theta..sub.3, .theta..sub.4, may be recognized.

A cyclic pattern of updated angles tends to update a pattern angle in similar increments in sequential cycles, and generally indicates that F can be minimized by updating the graphic structure by moving, in a single update, each of the pattern angles.

2. Determine the set of p independent joint angles of graphic structure .theta. to be moved, based on the joint angles of the pattern identified in step 1. (This step differs from the traditional Powell's method, which would evaluate and modify every joint angle to minimize F.)

3. Move the graphic structure from a configuration .theta..sub.k-1 to an updated configuration .theta..sub.k by modifying each of the p pattern angles. In general, the increments by which each angle is modified will generally be based on the pattern increments recognized for that angle.

For example, one embodiment uses the increments recognized in the last cycle. Using the above pattern, and using .DELTA..theta..sub.1, .DELTA..theta..sub.3, .DELTA..theta..sub.4, to indicate the increments recognized in the last cycle, the modifications .DELTA..sub.a .theta..sub.1, .DELTA..sub.a .theta..sub.3, .DELTA..sub.a .theta..sub.4 for the alternate update are:

.DELTA..sub.a .theta..sub.1 =.theta..sub.1 +t .DELTA..theta..sub.1 ;

.DELTA..sub.a .theta..sub.3 =.theta..sub.3 +t .DELTA..theta..sub.3 ; and

.DELTA..sub.a .theta..sub.4 =.theta..sub.4 +t .DELTA..theta..sub.4.

The alternate update method finds a value for t that minimizes F. In this implementation, t is found using the golden ratio search with parabolic interpolation, explained in references such as previously referenced WILLIAM H. PRESS, NUMERICAL RECIPES IN C: THE ART OF SCIENTIFIC COMPUTING, at 394-408. Other methods for finding t also exist.

Just as the conditions under which an alternate update method is used may vary, the conditions under which the iterative single angle update method of 320, 330, and 340 is resumed may also vary. One embodiment switches back to the single angle modification method after one iteration of the alternate update method.

If the process has not terminated (350, 355) and an alternate update method is not used (360, 365), iteration counter k is incremented (370), and the process repeats.

While the invention is described in terms of a software implementation, the invention may be implemented in hardware or software, or a combination of both. Preferably, the invention is implemented in a software program executing on a programmable processing system comprising a processor, a data storage system, an input device, and an output device.

FIG. 8 illustrates one such programmable processing system 800, including a CPU 810, a RAM 820, and an I/O controller 830 coupled by a CPU bus 840. The I/O controller 830 is also coupled by an I/O bus 850 to input devices such as a keyboard 860, and output devices such as a display 870.

Other embodiments are within the scope of the following claims.

For example, while an embodiment was described with reference to structure 400 of FIG. 4, which has only a single end effector, the invention extends to graphic structures having multiple end effectors.

Other variations are possible. For example, as previously indicated, a variety of criteria may be used to determine when to stop the iterative process. Similarly, other alternate update methods may be used, and the conditions for returning to the single angle update method may vary.