Manipulation of graphic structures using inverse kinematics

DETAILED DESCRIPTION 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)