Skeleton model shape transformation method, image synthesizing apparatus, and information storage medium

[0002] 1. Field of the Invention

[0003] This invention relates to a method of transforming the shape of a skeleton model, an image synthesizing apparatus, and an information storage medium.

[0004] 2. Description of Related Art

[0005] A technique called inverse kinematics is known in the art. With this technique, a skeleton model 20 such as that shown in FIG. 22A is created beforehand within a computer. The user then uses an input device such as a mouse to transform that skeleton model 20 while viewing the skeleton model 20 on a display device, such as a CRT, to create any motion or pose that the user desires. It should be noted that each of the joint or end points of the skeleton model 20 is called a “node” in the description that follows, and a linking “bone” that connects two nodes is called an arc.

[0006] Several methods of using this inverse kinematics technique are known in the art, such as is described in “Modeling and Animation Techniques for a Computer Generated Actor” (by Fukui Kazuo, reference material for a seminar on Human Modelling and Display Techniques, held in September 1991 by the Information Processing Society). With this prior-art technique, arc-to-arc angles θ₁, θ₂, and θ₃are used as basic variables representing the shape of a skeleton model, as shown in FIG. 22B. One of the problems to be solved with this prior-art inverse kinematics method occurs when there is a straight-linked skeleton having a fixed node 40 and the location (x, y, z) of a node 42 at the other end thereof has been specified. The difficulty involves deriving the arc-to-arc angles θ₁, θ₂, and θ₃that implement this method. This problem is equivalent to obtaining an inverse function f⁻¹(x, y, z) of a function f(θ_1x, θ_1y, θ_1z, θ_2x. . . ). However, since the function f is non-linear, it is not easy to obtain this inverse function. In this case, infinitesimal differentials Δx, Δy, and Δz in x, y, and z are approximated by linear expression involving infinitesimal differentials Δθ_1x, Δθ_1y, Δθ_1z, Δθ_2x. . . of the arc-to-arc angles. The problem to be solved thereby can be reduced to the solving of the set of simultaneous equations shown in FIG. 22C. However, the matrix M in FIG. 22C is not square and the number of variables thereof is less than the number of equations, so there is an infinite number of solutions. In this case, by adding a condition that the sum of squares of variations in the arc-to-arc angles is a minimum, the set of simultaneous equations of FIG. 22C can be solved.

[0007] However, the above described prior-art technique applies to a straight-linked skeleton that has one end fixed wherein arc-to-arc angles are used as basic variables expressing the shape, so it involves the following problems:

[0008] 1. It is Difficult to Handle a Multiple-branching Structure

[0009] With this prior-art technique, in order to handle a skeleton model of a multiple-branching structure (a structure in which three or more arcs are connected to one node), such as that shown for example in FIG. 22C, it is necessary to divide it into a plurality of directly linked structures 23 to 27 and then set parent-child relationships as shown in FIGS. 23A and 23B. To move one of the hands of the skeleton model 20, for example, a node 30 is set as a root and a node 32 is moved as an effector, and to move the other hand, the node 30 is set as the root and a node 34 is moved as an effector. Similarly, to move one of the legs, a node 36 is set as a root in this case and a node 38 is moved as an effector. The user must therefore work while constantly being aware of which node acts as the root and which node acts as effector, which makes the work troublesome.

[0010] 2. It is Difficult to Handle Complicated Restrictive Conditions

[0011] If restrictive conditions are set for a plurality of nodes, for example, it is necessary to divide the skeleton into suitable directly linked structures before handling it, so that the processing becomes complicated. These restrictive conditions are generally expressed as equations defining the node coordinates. If, for example, the node 38 in FIG. 22A is restricted to a polygon, an equation is used that always limits the node 38 to locations on that polygon. However, the basic variables used in the prior-art technique are the arc-to-arc angles, so it is difficult to use the above equations and thus restrictive conditions are difficult to handle.

[0012] 3. It is Difficult to Move a Plurality of Nodes in Different Directions Simultaneously

[0013] In other words, if an attempt is made to move nodes 38 and 39 in different directions simultaneously, for example, with the prior-art technique, the processing is extremely complicated.

[0014] This invention was devised in order to solve the above-described technical problems and has as an objective thereof the provision of a method of transforming the shape of a skeleton model, an image synthesizing apparatus, and an information storage medium which can easily handle a skeleton model of a multiple-branching structure and which enable the simple setting of complicated restrictive conditions.

[0015] In order to solve the above technical problems, a first aspect of this invention relates to a method of transforming the shape of a skeleton model , comprising the steps of:

[0016] expressing the skeleton model by basic variables that comprise coordinates of at least one node of the skeleton model;

[0017] causing a change in at least one of a set of basic equations and an evaluation expression based on given information, the set of basic equations taking the basic variables as unknowns and comprising an equation that defines the length of a plurality of arcs of the skeleton model as given values, and the evaluation expression uniquely determining a solution for the basic variables of the set of basic equations;

[0018] obtaining the solution that substantially satisfies the set of basic equations and makes the value of the evaluation expression one of substantially a minimum, substantially a maximum, or substantially stationary; and

[0019] transforming the shape of the skeleton model, based on the thus obtained solution.

[0020] With this aspect of the invention, a skeleton model is expressed by basic variables comprising node coordinates. Furthermore, a solution that substantially satisfies the basic equations is uniquely specified by adding a condition such as one that makes the value of an evaluation expression substantially at minimum, to determine the shape of the skeleton model. Therefore, this aspect of the invention makes it possible to handle all nodes equally, making it easy to manipulate a skeleton model of a multiple-branching structure. Since it is often necessary to define a restrictive condition on the basis of node coordinates, this aspect of the invention enables the simple setting of complicated restrictive conditions.

[0021] The basic variables may comprise components of arc-normal vectors that are perpendicular to the arcs; and the set of basic equations may comprise an equation defining the length of the arc-normal vectors as given values and an equation specifying that the arc-normal vectors are perpendicular to the arcs.

[0022] The arc-normal vector is used as a basic variable, so that all arcs can be handled equally, making it easy to manipulate a skeleton model of a multiple-branching structure.

[0023] The basic variables may comprise components of arc-normal vectors that are perpendicular to the arcs; and a variation in the components of the arc-normal vectors may be expressed as a single given variable to obtain the solution for these basic variables.

[0024] Since a variation in the components of the arc-normal vectors can be expressed by a single given variable as mentioned above, the number of unknowns to be solved can be reduced, increasing the speed of processing. Note that it is particularly preferable to express the variation in the components of the arc-normal vectors as a linear expression involving a single given variable.

[0025] The basic variables may comprise components of arc-normal vectors that are perpendicular to the arcs; and the solution for the basic variables may be obtained such that the value of the evaluation expression is one of substantially a minimum, substantially a maximum, or substantially stationary, when the evaluation expression comprises at least one of a variation in an angle between two of the arcs, a distance between the node and a given point, a variation in the direction of one of the arcs which has a fixed node at one end, a variation in the coordinates of the node, and a variation in the velocity of the coordinates of the node.

[0026] This makes it possible to transform the skeleton model in a well-balanced manner by including variations in arc-to-arc angles within the evaluation expression. It also makes it possible to set conditions such as rubber-banding by including the distance between a node and a given point therein. Similarly, indefinite solutions and uncoordinated motion of the skeleton model can be prevented by including variations in the coordinates of nodes or variation in the velocity of the coordinates of nodes within the evaluation expression.

[0027] The solution for the basic variables may be obtained by iterative calculations; and at least one of the set of basic equations and the evaluation expression may be successively modified based on given information in synchronization with the start or end of an iterative loop.

[0028] If an iterative method such as a Newtonian method is used, the known values and form of the equations do not normally change until the calculations converge. In this case, the basic equations and evaluation expression change successively before the calculations converge, such as in each iterative loop or in every two or three iterative loops. This makes it possible to achieve a shape transformation that follows the user's input sufficiently well, if the given information is the coordinates of the position of a mouse cursor manipulated by the user, for example, which increases the usefulness of this invention to the user. Note that it is preferable to enable compensation by scaling, if errors become too large.

[0029] Coordinates of a fixed node or components of fixed arc-normal vectors may be used as known values.

[0030] This makes it possible to fix the coordinates of a node or the direction of an arc in a simple manner, further increasing the usefulness to the user. The number of unknowns can also be reduced, enabling an increase in processing speed.

[0031] The evaluation expression may comprise at least one of an expression that restricts an angle between two of the arcs to within a given range, an expression that restricts the node to within a given surface or a given line, and an expression that restricts the skeleton model or a first object that moves together with the skeleton model to a second object, when an interaction occurs between the skeleton model or the first object and the second object.

[0032] This makes it easy to set a restrictive condition, such as a limit on the movability range of arc-to-arc angles, an attachment of a node to a given surface or the like, or an interaction between the skeleton model and another object, by simply including one of the above different expressions in the evaluation expression.

[0033] A second aspect of this invention relates to a method of transforming the shape of a skeleton model, comprising the steps of:

[0034] expressing the skeleton model by basic variables that comprise coordinates of at least one node of the skeleton model and components of arc-normal vectors that are perpendicular to a plurality of arcs of the skeleton model; and

[0035] transforming the shape of the skeleton model in such a manner that the value of an expression is one of substantially a minimum, substantially a maximum, or substantially stationary, when the expression comprises at least one of a variation in an angle between two of the arcs, a distance between the node and a given point, a variation in the direction of one of the arcs which has a fixed node at one end, a variation in the coordinates of the node, and a variation in the velocity of the coordinates of the node.

[0036] Since node coordinates or the components of arc-normal vectors are used as basic variables in this aspect of the invention, all nodes and arcs can be handled equally, making it easy to manipulate a multiple-branching structure. It is also possible to transform the shape in a well-balanced manner, by minimizing an expression that comprises a variation in arc-to-arc angle.

[0037] A third aspect of this invention relates to a method of transforming the shape of a skeleton model, comprising the steps of:

[0038] expressing the skeleton model by basic variables that comprise coordinates of at least one node of the skeleton model; and

[0039] transforming the shape of the skeleton model in such a manner that, when the coordinates of at least one given point that controls a transformation in the shape of the skeleton model have changed, the distance between the node and the given point is minimized.

[0040] This aspect of the invention makes it possible to set a feature called “rubber-banding,” enabling a well-balanced shape transformation because the shape transformation can be executed with a suitable form as an initial state.

[0041] The shape of the skeleton model may be transformed in such a manner that distances between two or more of the nodes and two or more of the given points linked thereto are minimized.

[0042] This makes it possible to transform the shape of a skeleton model by using at least two given points as control points, enabling a further increase in usefulness to the user.

[0043] A fourth aspect of this invention relates to a method of transforming the shape of a skeleton model, comprising the steps of:

[0044] expressing the skeleton model by basic variables that comprise coordinates of at least one node of the skeleton model;

[0045] obtaining a solution for an equation including the basic variables by iterative calculations; and

[0046] successively modifying the equation based on given information in synchronization with the start or end of an iterative loop.

[0047] With this aspect of the invention, the equation changes successively before the calculations converge, such as in each iterative loop or in every two or three iterative loops, so that a rapid response is enabled without the appearance of excessive unnaturalness in the shape, even when rapid shape transformation of the skeleton model is required.

[0048] A fifth aspect of this invention concerns a method of transforming the shape of a skeleton model, comprising the steps of:

[0049] transforming the shape of the skeleton model under a restrictive condition such that, when the skeleton model or an object that moves together with the skeleton model has passed beyond a given boundary, the skeleton model or object is returned to the boundary;

[0050] executing calculations in such a manner that, when one iterative loop of iterative calculations for obtaining the shape of the skeleton model is executed in a state in which the restrictive condition is disabled and the skeleton model or object does not pass beyond the boundary, the restrictive condition remains disabled in the next iterative loop;

[0051] executing calculations in such a manner that, when the one iterative loop is executed in a state in which the restrictive condition is disabled and the skeleton model or object passes beyond the boundary, the restrictive condition is enabled in the next iterative loop;

[0052] executing calculations in such a manner that, when the one iterative loop is executed in a state in which the restrictive condition is enabled and the skeleton model or object passes beyond the boundary, the restrictive condition remains enabled in the next iterative loop; and

[0053] executing calculations in such a manner that, when the one iterative loop is executed in a state in which the restrictive condition is enabled and the skeleton model or object does not pass beyond the boundary, the restrictive condition is disabled in the next iterative loop.

[0054] With this aspect of the invention, the skeleton model or object can be restricted in a spring-like manner to a boundary, making it possible to determine easily whether the user is moving the skeleton model towards that boundary or in a direction away from that boundary. Since this aspect also makes it unnecessary to perform repeated calculations to determine such a restrictive condition, the processing speed can be increased dramatically.

[0055] The shape of the skeleton model may be transformed under a restrictive condition that ensures that the value of an expression comprising the distance between the skeleton model or object and the boundary is one of substantially a minimum, substantially a maximum, or substantially stationary.

[0056] This simplifies the implementation of an interaction function between a skeleton model and an object.

[0057] A virtual boundary may be provided at a location separated from the boundary by a given spacing; and, when the skeleton model or object passes beyond that boundary, the skeleton model or object may be returned to the virtual boundary and also a decision may be made as to whether to enable or disable a restrictive condition by using the virtual boundary instead of the boundary.

[0058] This makes it possible to remove the problems that occur when there are multiple collisions between nodes or other structural components and objects.

[0059] A sixth aspect of this invention relates to a method of transforming the shape of a skeleton model, wherein:

[0060] when a domain of at least one first variable for expressing the shape of the skeleton model is defined by an inequality comprising the first variable, the shape of the skeleton model is transformed under a discontinuous restrictive condition by substituting an equality for the inequality and defining the domain of the first variable by the equality, the equality being made by moving all terms of the inequality to either the left of right side of the inequality and inserting a function of a second variable into the other side of the inequality, the value of the function being constantly positive or constantly negative or constantly non-negative or constantly non-positive.

[0061] In general way, the domain of the first variable such as an arc-to-arc angle, node coordinates, or the components of an arc-normal vector can be defined by using an inequality. With this aspect of the invention, this inequality can be substituted into an equality having the same effect as this inequality with respect to domain defining. The domain of the first variable is defined in terms of this equality, so that a discontinuous restrictive condition can be given for the shape transformation of the skeleton model. This substitution of an inequality into an equality in this manner means that classifying the cases that is necessary when using an inequality can be omitted, enabling faster processing. Since an equality can be easily added to an expression which provides a restrictive condition for a skeleton model, the processing can be simplified.

[0062] The shape of the skeleton model may be transformed in such a manner that the value of an expression comprising a variation in the second variable is one of substantially a minimum, substantially a maximum, or substantially stationary.

[0063] This makes it possible to prevent large changes in the value of the second variable. It also makes it possible to prevent a situation in which uncoordinated variations are generated in the second variable, so that the first variable cannot be restricted to within its domain.

[0064] When the second variable has achieved a value close to a given convergent value, another given value may be added to the second variable.

[0065] If a long time is requires for the second variable to converge on the given convergent value, or escape from that convergent state, the speed of response of the skeleton model with respect to the user's input will deteriorate. In this case, a value of a given infinitesimal quantity may be added to the second variable before the second variable converges. This makes it possible to prevent the second variable from converging, and thus remove the above problem of a deterioration in response speed. Note that it is preferable to use a random number as the given value to be added to the second variable.

[0066] A seventh aspect of this invention relates to a method of transforming the shape of a skeleton model, wherein:

[0067] in one iterative loop of iterative calculations for obtaining the shape of the skeleton model, a first calculation step is executed in a state in which a restrictive condition that restricts the skeleton model or an object that moves together with the skeleton model to a given boundary is disabled; and

[0068] when the skeleton model or object is in a given positional relationship with respect to the boundary after the first calculation step in the one iterative loop, a second calculation step is executed to attract the skeleton model or object towards the boundary.

[0069] With this aspect of the invention, a first calculation step is executed first with a restrictive condition in a disabled state, then a second calculation step is executed to attract the skeleton model or object to a boundary. This makes it possible to restrict the skeleton model to a boundary, with only two calculation steps being executed within one iterative loop. This enables a dramatic improvement in processing speed during iterative calculations, in comparison with the prior-art method in which one iterative loop comprises another iterative loop. Note that the second calculation step of attracting the skeleton model to the boundary could be omitted if the positional relationship between the skeleton model and the boundary is in a certain state.

[0070] Calculations may be executed in the first calculation step in such a manner that the value of an expression comprising an amount of movement of the skeleton model or object in the direction of the boundary is one of substantially a minimum, substantially a maximum, or substantially stationary; and calculations may be executed in the second calculation step in such a manner that the value of an expression comprising the distance between the skeleton model or object and the boundary is one of substantially a minimum, substantially a maximum, or substantially stationary.

[0071] This makes it possible to prevent a situation in which a skeleton model that ought to be restricted to a boundary moves so far away from the boundary that it cannot be returned thereto, by ensuring that an expression comprising an amount of movement in a boundary direction is at substantially a minimum, substantially a maximum, or substantially stationary. This enables a simple implementation of a function that returns the skeleton model to the boundary, by setting the expression comprising a distance to the boundary to be substantially a minimum, substantially a maximum, or substantially stationary.

[0072] The boundary may be a limited surface or limited line.

[0073] This makes it possible to increase the usefulness to the user, by enabling a restriction of the skeleton model to a limited surface or limited line (such as a polygon of a limited size or a polygon edge of a limited length). Note that this method can also be applied if a restriction is to a limitless surface or limitless line, by making the size of a polygon or the length of an edge sufficiently large.

[0074] An eighth aspect of this invention relates to a method of transforming the shape of a skeleton model, comprising the steps of:

[0075] expressing the skeleton model by basic variables that comprise coordinates of at least one node of the skeleton model;

[0076] determining whether or not a first set of simultaneous equations that takes a variation of the basic variables as an unknown is degenerate or in a state approximating thereto; and

[0077] transforming the shape of the skeleton model by reducing the number of equations of the first set of simultaneous equations to reconfigure the first set of simultaneous equations as an independent second set of simultaneous equations, and obtaining a solution to the thus reconfigured second set of simultaneous equations, when it is determined that the first set of simultaneous equations is degenerate or in a state approximating thereto.

[0078] If, for example, a first set of simultaneous equations comprises dependent equations and are thus in a degenerate state, a situation can occur in which the solution to this first set of simultaneous equations is indefinite. In such a case, this aspect of the invention reduces the number of equations and reconfigures the equations into an independent second set of simultaneous equations. It is therefore possible to determine a unique solution, even if the above situation occurs in which the solution is indefinite, and thus it is possible to suitably transform the shape of a skeleton model that comprises node coordinates as basic variables.

[0079] The first set of simultaneous equations may comprise an equation that defines the length of arcs of the skeleton model as given values.

[0080] Consider an example in which there is a first equation that defines the length of a first arc which connected at one end to a fixed node and a second equation that defines the length of a second arc which is connected at one end to a fixed node and at the other end to the other end of the first arc. In this case, the first and second equations both define the coordinates of a first node that is the connection point of the first and second arcs. However, it could happen that the definition by the first equation has the same meaning as the definition by the second equation, so that the first and second equations end up in a mutually dependent relationship. If the first and second equations are in a dependent relationship, a first set of simultaneous equations for obtaining a solution to these first and second equations will be degenerate. This aspect of the invention makes it possible to obtain an appropriate solution in such as case, by reconfiguring the equations as an independent second set of simultaneous equations.

[0081] An image synthesizing apparatus according to a ninth aspect of this invention comprises means for outputting the shape of a skeleton model that has been transformed by any of the above-described shape transformation methods, and manipulation means for enabling an operator to specify a transformation of the skeleton model.

[0082] This makes it possible to implement a shape data creation tool that uses the shape transformation method of this invention.

[0083] An image synthesizing apparatus according to a tenth aspect of this invention comprises means for outputting an image of an object that moves together with a skeleton model that has been transformed by any of the above-described shape transformation methods.

[0084] This makes it possible to implement a games machine or the like that uses shape data obtained by the shape transformation method of this invention.

[0085] FIGS. 1A to 1D illustrate the principles of this invention;

[0086] FIG. 2A illustrates a description of a method of expressing a variation in an arc-normal vector as one variable, and FIG. 2B illustrates various different examples of evaluation expressions;

[0087] FIG. 3A illustrates a description of a Newtonian method, and FIG. 3B illustrates a description of a method of varying basic equations or the like in each iteration of an iterative loop;

[0088] FIG. 4 shows an example of the picking of a node and the resultant shape transformations of a skeleton model;

[0089] FIGS. 5A to 5E illustrate a description of rubber-banding;

[0090] FIG. 6 shows an example of the picking of two nodes and the resultant shape transformations of a skeleton model;

[0091] FIG. 7 shows an example of the shape transformation of a skeleton model having a complicated multiple-branching structure;

[0092] FIGS. 8A and 8B illustrate a description of the setting of a movability range for an arc-to-arc angle;

[0093] FIGS. 9A and 9B illustrate a description of a function for attaching a node to a polygon or edge;

[0094] FIG. 10 illustrates a description of an example of the use of the attachment function to make a skeleton model climb a wall;

[0095] FIG. 11 further illustrates the description of this example of the use of the attachment function to make a skeleton model climb a wall;

[0096] FIG. 12 illustrates a description of a function that causes a skeleton model and an object to interact;

[0097] FIGS. 13A and 13B illustrate a description of a method of handling a restrictive condition;

[0098] FIG. 14 illustrates the relationships between an arc, nodes, and arc-normal vectors;

[0099] FIG. 15 illustrates a description of an arc coordinate system;

[0100] FIG. 16A to FIG. 16D illustrate a description of the effectiveness of rubber-banding;

[0101] FIG. 17A illustrates the rotation of an arc about a fixed node, and FIGS. 17B and 17C illustrate the generation of a singular state;

[0102] FIGS. 18A, 18B, and 18C illustrate a description of the setting of a movability range for arc-to-arc angles;

[0103] FIG. 19 illustrate a description of overshooting of an arc-to-arc angle, and the setting of a permissible limit therefor;

[0104] FIG. 20A, FIG. 20B, FIG. 20C illustrate a description of a function that enables interaction between a skeleton model and an object;

[0105] FIGS. 21A, 21B, and 21C show various different embodiments of an image synthesizing apparatus and an information storage medium;

[0106] FIGS. 22A, 22B, and 22C illustrate a description of a prior-art method of transforming the shape of a skeleton model; and

[0107] FIGS. 23A and 23B illustrate the setting of parent-child relationships.

[0108] An embodiment of this invention will be described below, with reference to the accompanying drawings.

[0109] <1> Basic Principles

[0110] In this embodiment, the (x, y, z) coordinates of nodes 2, 3, and 4 and the (u, v, w) components of arc-normal vectors 10, 11, and 12 (which are perpendicular to arcs 6, 7, and 8, respectively) are used as basic variables representing a skeleton model 18, as shown in FIG. 1A. Taking as an example the prior-art model of FIGS. 22A, 22B, and 22C, which uses arc-to-arc angle as basic variables, it is necessary to set parent-child relationships. With that prior-art technique, nodes and arcs cannot be handled uniformly, but this embodiment, which uses node coordinates and arc-normal vectors as basic variables, makes it possible to handle all nodes and arcs in a uniform manner. Note that other variables could equally well be used instead of arc-normal vectors, for example.

[0111] These basic variables are then used as unknowns in basic equations, as shown in FIG. 1B, which provide an equation defining the length of an arc as a given value, an equation defining the length of an arc-normal vector as a given value, and an equation defining that an arc-normal vector is perpendicular to an arc. Note that g=0 and h=0 in these equations could be replaced by other equations.

[0112] In this case, the basic equations shown in FIG. 1B are non-linear. A solution is obtained by iterative calculations in this embodiment, such as those of a Newtonian method. The use of this Newtonian method, or the like, makes it possible to express the basic equations as linear expressions comprising to variations in the basic variables. The resultant set of simultaneous equations to be solved are as shown in FIG. 1C.

[0113] However, the number of variables in the equations of FIG. 1C is greater than the number of equations. That is why this embodiment provides an evaluation expression for uniquely specifying a solution to the basic equations. A condition is added to the effect that the value of this evaluation expression is at any one of substantially a minimum, substantially a maximum, or substantially stationary, and a Lagrangian multiplier method can be applied to obtain a solution for the basic variables. The use of this Lagrangian multiplier method makes it possible to determine an unique solution, because the number of variables in the equations to be solved is the same as the number of equations, as shown in FIG. 1D.

[0114] Note that in this embodiment the skeleton model is transformed in accordance with data such as the coordinates of a cursor that moves on the screen as the user moves a mouse. During this time, the basic equations and the evaluation expression vary based on given information such as these coordinates of the cursor position. More specifically, the known values comprised within the basic equations and the evaluation expression, as well as the form of the equations and the expression themselves, vary based on the coordinates of the cursor position and the like, and these variations transform the shape of the skeleton model. Note that the above described given information is not limited to the coordinates of the cursor position, various other factors such as previously prepared data can equally well be used.

[0115] <2> First-degree Approximations of Variations in Arc-Normal Vectors

[0116] With this embodiment, variations in each arc-normal vector n(u, v, w) shown in FIG. 2A are expressed by ρ, which is a single given variable, to obtain a solution for the basic variables (this will be described later in more detail, with reference to Algorithm 2). More specifically, variations in the arc-normal vector n are approximated by a linear expression involving the variable ρ. The arc-normal vector n is expressed by the three variables u, v, and w, but since n is perpendicular to an arc 50 and the magnitude thereof is constant, as shown in FIG. 2A, n has one degree of freedom in practice. Therefore, variations in n can also be expressed in terms of that one variable ρ, which makes it possible to reduce the number of basic variables to be solved and thus aim for an increase in processing speed.

[0117] <3> Evaluation Expression

[0118] In order to achieve a desired transformation of the skeleton model, the evaluation expression of this embodiment comprises factors such as variations in arc-to-arc angles, the distances between nodes and a given point, a variation in the direction of an arc having one end fixed, and a variation in the node coordinates or variation in the velocity of the node coordinates. More specifically, various conditions can be added to the evaluation expression, as shown in FIG. 2B. For example, it is possible to have all arc-to-arc angles vary uniformly by including variations in arc-to-arc angles into the evaluation expression and minimizing the sum-of-squares of these variations in arc-to-arc angles. It is also possible to set an appropriate shape as an initial state for the start of a transformation, and thus implement a well-balanced transformation of the shape of the skeleton model, by including distances between nodes and a given point into the evaluation expression and setting rubber-banding (which will be described later). Similarly, it is possible to prevent indefinite solutions by including a variation in the direction of an arc having one end fixed and variations in node coordinates into the evaluation expression, and setting rotational dampers for arcs rotating about fixed nodes and node dampers. It is furthermore possible to prevent uncoordinated motion of arcs, caused by instability in the calculations, by including variations in node coordinates and variation in the velocity of node coordinates into the evaluation expression, and setting node dampers and node inertias.

[0119] <4> Updating of Basic Equations and Evaluation Expression in Each Iterative Loop

[0120] Two usage methods are considered for this embodiment: real-time and non-real-time. For non-real-time usage, the calculations are sufficiently converged so that the shape of the skeleton model can be updated. For real-time usage, however, it is necessary to have sufficient followability with respect to the user's input.

[0121] With this embodiment, a solution for the basic variables is obtained by iterative calculations using a Newtonian method or the like, as shown in FIG. 3A, and also at least one of the set of basic equations and the evaluation expression is varied successively in accordance with the given information, in synchronization with the end or start of each iterative loop.

[0122] During the calculation processing, the process from obtaining the coordinates of the mouse cursor, transforming the skeleton model accordingly, and up until that result is displayed, for example, is called one event cycle. Since the user is causing the position of a picked node to move by dragging the mouse in real-time, the volume of calculations during one event cycle required for the consequent transformation of the skeleton model must be as small as possible. In this embodiment, only a single iterative loop in iterative calculations is executed within one event cycle while the user is dragging the mouse. More specifically, when the coordinates of the mouse cursor position are obtained, known values in the basic equations and evaluation expression, as well as the form of the equations and the expression themselves, can be varied in accordance with those position coordinates, and only a single iterative loop is executed, as shown in FIG. 3B.

[0123] In this method, a problem that the length of an arc is extended beyond its original length and the like occurs, since the calculations cannot converge while the mouse is being dragged and the basic equations cannot be satisfied. However, the magnitude of this length extension is not high enough to cause problems in practice. When the shape of the skeleton model is being subtly adjusted, the movement of the mouse could be slowed so that the skeleton model is transformed into a shape which is close to a correct shape that is obtained when the calculations converge. If the movement of the mouse stops, the calculations converge and a correct shape can be obtained for the skeleton model.

[0124] Note that this embodiment performs scaling compensation if the variation of a variable is too great within one loop of the iterative calculations. This makes it possible to prevent the skeleton model achieving an unnatural shape, even if the above described method is used to vary the basic equations and evaluation expression in each iterative loop. Although the above description stated that the basic equations and the like are modified in each iterative loop, it should be noted that this invention is not limited thereto and thus the basic equations and the like could be modified every two iterative loops or every three iterative loops, for example. In other words, the basic equations and the like could be modified successively at least at the start or end of each iterative loop.

[0125] <5> Fixed Node and Fixed Arc-Normal Vector

[0126] In this embodiment, coordinates of a fixed node or components of a fixed arc-normal vector are handled as known values. An example of the transformation of the shape of a skeleton model 52 in accordance with this embodiment is shown in FIG. 4. In this model, nodes 54 and 56 are fixed nodes. A node 58 is a node that the user has picked, and the user transforms the shape of the skeleton model by dragging the mouse to cause the node 58 to move. The coordinates of the nodes 54 and 56 are known values in the basic equations, and the coordinates of the other nodes or the components of the arc-normal vector are unknowns to be obtained. Therefore, if the node 58 is moved, not only the node 58 of the skeleton model 52 but also the entire skeleton model 52 will be transformed smoothly.

[0127] Note that FIG. 4 shows an example in which nodes are fixed, but the directions in which arcs are orientated could also be fixed, in other words, the directions of their arc-normal vectors could also be fixed. In such a case, the components of fixed arc-normal vectors act as known values.

[0128] In the prior-art example shown in FIGS. 22A, 22B, and 22C, a fixed node is limited to being a root and a movable node is limited to being an effector. In this embodiment, however, the user can fix or move any desired node or arc freely, without having to be aware of parent-child relationships. This is because node coordinates or arc-normal vectors are used as basic variables in this embodiment, and all of the nodes and arcs can be handled uniformly.

[0129] <6> Rubber-Banding

[0130] A concept called rubber-banding is introduced into this embodiment for transforming the shape of a skeleton model. In other words, if the coordinates of a given point that controls the shape transformation of a skeleton model have changed, the shape of the skeleton model is transformed in such a manner that a rubber-band minimizes the distance between each node and that given point. Consider what happens when the node 58 in FIG. 5A is fixed and a node 60 is moved. In this case, think of a rubber-band having a root and a tip; the root moves with the movement of the mouse, and the tip is fixed at the picked node. In a state in which the user has clicked the mouse button but the mouse cursor still hasn't moved away from a point 62, the root and tip of the rubber-band are positioned at the node 60. When the user then drags the mouse to move the mouse cursor from the point 62 to another point 64, the root of a rubber-band 66 moves from the location of the node 60 to a point 68, as shown in FIG. 58. During this time, the tip of the rubber-band 66 remains fixed at the location of the node 60. This rubber-band 66 has a tendency to contract. In other words, it tends to minimize the distance between the node 60 and the given point 68. This moves the node 60 towards the point 68, to transform the shape of the skeleton model.

[0131] Note that if rubber-banding is used for the movement of the node 58 in FIG. 4, the coordinates of the node 58 will become unknowns. On the other hand, the coordinates of the node 58 become known values if the user moves the node 58 directly without rubber-banding or if the coordinates of the node 58 are changed in accordance with previously prepared data.

[0132] In this embodiment, two or more nodes such as nodes 58 and 59 can be made to move simultaneously, as shown in FIG. 6. In such a case, two rubber-bands 66 and 67 are created, as shown in FIGS. 5D and 5E, and the rubber-bands 66 and 67 are transformed in such a manner that the distances between nodes 60 and 61 and given points 68 and 69 are minimized.

[0133] An example of the shape transformation of a skeleton model 70 having a more complicated multiple-branching structure is shown in FIG. 7. In this case, nodes 72 and 74 and an arc 73 are fixed, and a node 76 is moved with rubber-banding. The above implementation of this embodiment differs from the prior-art example in that the shape of a skeleton model can be transformed smoothly, without any complications due to the multiple-branching structure.

[0134] <7> Restrictive Conditions

[0135] <7>-1 Types of Restrictive Conditions

[0136] Various different restrictive conditions can be set by this embodiment to affect transformations of the shape of a skeleton model.

[0137] First of all, a restrictive condition that fixes the position of a node or the direction of an arc could be set by this embodiment, making is possible to handle the coordinates of the fixed node or the arc-normal vector of the fixed arc as known values, as described above.

[0138] Secondly, a restrictive condition that specifies the movability range of an angle between two arcs of the skeleton model could be set by this embodiment. For example, a discontinuous restrictive condition can be set in such a manner that the angle θ between two arcs 78 and 80 of a skeleton model 77 shown in FIGS. 8A and 8B does not exceed 180 degrees. In other words, it would seem unnatural for an elbow joint of a skeleton model to bend backwards during a shape transformation, and thus the usefulness to the user can be increased by setting such a restrictive condition. Note that this restrictive condition could be implemented by including into the evaluation expression an expression that restricts an angle between two arcs to within a given range.

[0139] Thirdly, a condition could be set by this embodiment to restrict a node of the skeleton model to within a given surface or line, such as to within a polygon or the edges thereof. In the description below, an operation that restricts a specific node to a specified polygon or edge is called an attachment. Assume for example that the user has specified that a node 82 of a skeleton model 81 is attached to a polygon 84, as shown in FIG. 9A, or to an edge 86, as shown in FIG. 9B. A characteristic of this embodiment is the way in which the node 82 can be restricted to the polygon 84 or edge 86 in a discontinuous manner. In other words, the node 82 can move only within the surface of the polygon 84 in FIG. 9A; it cannot move beyond the edge of the polygon 84. Similarly, the node 82 can move only within the edge 86 in FIG. 9B; it cannot move beyond the vertexes thereof. This enables an increase in usefulness to the user, by making it possible to restrict a node discontinuously onto a polygon or edge.

[0140] An example of how the above described attachment function is used when making a skeleton model climb a wall is shown in FIG. 10. A skeleton model 88 has nodes 90, 91, 92, and 93 (corresponding to the ends of the arms and legs thereof) that are attached to a first wall object 96. Other nodes 94 and 95 (corresponding to the back of the skeleton model 88) are attached to a second wall object 98 that is positioned at a given spacing from the first wall object 96. The provision of the second wall object 98 in this manner makes it possible to transform the skeleton model 88 in a state in which the trunk thereof is held at a suitable distance from the first wall object 96. Note that FIG. 11 is also provided, to clarify the positional relationships between the skeleton model 88 and the first and second wall objects 96 and 98. In FIG. 10, the node 91 is attached to the first wall object 96 and also the coordinates thereof are fixed. The coordinates of a node 89 are also fixed. If the user then picks nodes 87 and 90 and moves them, the skeleton model 88 climbs the wall while undergoing a shape transformation that follows that movement. During this time, the nodes 92, 93, 94, and 95 are still attached to the corresponding first or second wall object 96 or 98, so the skeleton model moves while being restricted to within the surfaces of these wall objects.

[0141] Fourthly, a restrictive condition could be set by this embodiment to ensure that a skeleton model does not penetrate into or pass through an object when interaction occurs between the skeleton model and the object. If, for example, a skeleton model 100 representing a whip interacts with a circular cylindrical object 102, as shown in FIG. 12, the shape of the skeleton model 100 is transformed in such a manner that it wraps around the circular cylindrical object 102 without penetrating it. Such a restrictive condition can be implemented by comprising within the evaluation expression an expression that restricts the skeleton model to an object, when the skeleton model and the object interact with each other.

[0142] <7>-2 Improvements to Discontinuous Restrictive Condition

[0143] There are some problems involved with the handling of a discontinuous restrictive condition, as described below. In the methods generally used up until now, a calculation is first done when the restrictive condition is in a disabled state (free) and if, for example, it is determined thereby that a node of the skeleton model and an object have hit each other, the calculation is re-done with the restrictive condition in a enabled state (the node is absolutely restricted to the object), as shown in FIG. 13A. If as a result of this calculation it is detected that another node has hit the object, the recalculation is done again. With this method, the node is absolutely restricted to the object when the restrictive condition is enabled. Therefore, the calculations must be performed initially with the restrictive condition disabled, to identify whether the user has moved the skeleton model in the direction of the object or in a direction away from the object. Conversely, if the calculations are done with the restrictive condition initially in an enabled state, the node is absolutely restricted to the object and thus it is impossible to identify in which direction the user is moving the object.

[0144] Use of the above described method makes it necessary to execute calculations with the restrictive condition disabled and iterative calculations for determining the restrictive condition, within one iterative loop. In other words, this iterative loop contains another iterative loop, making it a two-step iterative loop, which greatly reduces the processing speed.

[0145] That is why this embodiment handles a discontinuous restrictive condition by a method that is shown in FIG. 13B. First of all, the transformation of a skeleton model (or an object that moves together therewith) is done under a restrictive condition that, if the skeleton model has passed a given boundary, the skeleton model is returned to within the boundary. In other words, this is a condition called a spring restriction in which the nodes and other components of the skeleton model are not absolutely restricted to the boundary when the restrictive condition is in an enabled state. This spring restriction makes it possible to determine whether the user is causing the skeleton model to move in a direction towards the boundary of an object or the like, or in a direction away from that boundary.

[0146] If the iterative loop that obtains the shape of the skeleton model is executed with the restrictive condition disabled, and a node 106 or an arc of the skeleton model does not pass a boundary 104, the calculation in the next iterative loop will be done with the restrictive condition still disabled.

[0147] On the other hand, if the iterative loop is executed with the restrictive condition disabled, and the node 106 or arc of the skeleton model does pass the boundary 104, it is possible to determine that the user is moving the skeleton model in the direction of the boundary 104 and thus the calculation in the next iterative loop is executed with the restrictive condition enabled. In this case, the calculation results are scaled to return the node 106 to a position 107.

[0148] If the iterative loop is executed with the restrictive condition enabled and the node 106 or arc passes the boundary 104, the restrictive condition remains enabled for the next iterative loop. Note that, since a powerful spring restriction is applied when the restrictive condition is enabled, the passing through the boundary 104 is so small, the user would be unaware of it.

[0149] If the iterative loop is executed with the restrictive condition enabled and the node 106 or arc does not pass the boundary 104, it can be determined that the user is moving the skeleton model in a direction away from the boundary 104, and thus the same calculation is done again with the restrictive condition disabled. Then, the calculation in the next iterative loop is executed with the restrictive condition disabled. Note, however, that since suitable calculation results can be obtained in this next iterative loop when the skeleton model is moving in a direction away from the boundary 104, recalculation thereof can be omitted.

[0150] Use of the above method to handle a discontinuous restrictive condition makes it possible to dramatically reduce the amount of processing required for calculations in the iterative loop, in comparison with the case shown in FIG. 13A, increasing the speed of processing.

[0151] <7>-3 Substitution of Inequality Defining a Discontinuous Restrictive Condition into Equalities

[0152] In this embodiment, an inequality (50) that defines a discontinuous restrictive condition is substituted by a first equality of (48) that have the same effect, as will be described later in details in Section <5> of the description of Algorithm 1 (setting of arc-to-arc angle range), with reference to FIGS. 18A to 18C. The domain of a first variable, such as an arc-to-arc angle, can be defined by the inequality (50), but the necessity of classifying the cases for solution makes the processing complicated when the inequality is used as the basic equations or evaluation expression. In such a case, this embodiment substitutes the first equality of (48) for the inequality (50). More specifically, this embodiment moves the terms of the inequality (50) to the left side (or right side) thereof and also inserts into the right side (or left side) thereof a function (such as t_x²) which is a function of a new second variable (such as t_x) and which is constantly positive or constantly negative or constantly non-negative or constantly non-positive. The domain of the first variable is then defined by thus obtained first equality of (48), and the shape of the skeleton model is transformed accordingly. An equality can be more easily combined with the basic equations and evaluation expression than an inequality, making the processing of this embodiment easier.

[0153] Note that an expression comprising a variation in the second variable is preferably inserted, as will be described with reference to Expression (58) in Section <5>-2 of the description of Algorithm 1, to prevent the second variable from varying so large that the restrictive condition no longer functions. It is also preferable that a given value is added to the second variable before it converges to reduce the speed of response of the transformation of the skeleton model. This method of substituting an inequality with equalities can be applied to other discontinuous restrictive conditions, not just to a discontinuous restrictive condition that sets a movability range for arc-to-arc angle, such as one that sets an attachment of a node to a polygon or an edge, or one that sets an interaction between a skeleton model and another object.

[0154] <7>-4 Drag-Back Method

[0155] With this embodiment, as will be described later in section <7> of the description of Algorithm 1, a method called a “drag-back method” is used in the handling of discontinuous restrictive conditions. With this method, a first calculation step is executed within one iterative loop, in which a restrictive condition that restricts a node or arc of the skeleton model to a boundary at a polygon or edge is disabled. Next, a second calculation step is executed after this first calculation step, and within the same one iterative loop, to attract the node or arc to the boundary. This arrangement makes it possible to divide the calculations necessary within one iterative loop into only two parts, enabling a dramatic increase in processing speed over the prior-art method (shown in FIG. 13A) in which one iterative loop comprises another, separate, iterative loop.

[0156] Note that this first calculation step preferably operates a surface-perpendicular damper or line-perpendicular damper, as will be described later with reference to Expressions (62) and (65) in Sections <7>-1 and <7>-2 on Algorithm 1. In other words, an expression comprising an amount of movement in a boundary direction of a node or arc of a skeleton model is subjected to a process such as minimization. This makes it possible to prevent a situation in which a node or arc moves so far away from the boundary, it cannot be returned thereto. Note also that this second calculation step preferably operates a face magnet, line magnet, or point magnet, as will be described later in Sections <7>-3, <7>-4, and <7>-5 of the description of Algorithm 1. In other words, an expression comprising a distance between a node or arc and the boundary is subjected to a process such as minimization. This arrangement makes it possible to implement a return of the node or arc to the boundary in a simple manner. The drag-back method can also be applied to discontinuous restrictive conditions, not only to the discontinuous restrictive condition for attaching a node to a polygon or edge, but also to one for setting the movability range of arc-to-arc angles or one for setting an interaction between a skeleton model and another object.

[0157] <8> Singular Value Decomposition (Reconfiguration of Set of Simultaneous Equations)

[0158] With this embodiment, if a set of simultaneous equations is degenerate or in a state approximating thereto, a method can be used to reconfigure them into an independent new set of simultaneous equations, to obtain a solution, as will be described later in Section <4> of Algorithm 1, with reference to FIGS. 17B and 17C. If a set of simultaneous equations is in a degenerate state in which it comprises dependent equations, the solution thereof is indefinite and it is not possible to obtain a suitable shape transformation. As described with reference to F_ijof Equations (4) in the section on Algorithm 1, it is particularly likely that such an indefinite solution will occur for an equation that defines the length of an arc, and this embodiment makes it possible to prevent such a situation from happening.

[0159] Two specific examples of the algorithm of this embodiment will now be described. Note that the meanings of the Σ-notations used in the description are given below. In these descriptions, “arc-to-arc angle” is referred to simply as “angle” and the two arcs that form that angle and the three nodes that are the end points of the two arcs are referred to as the “structural elements” of the angle. $\sum _{\mathrm{node}i}{X}_i\text{:}\mathrm{Sum}\mathrm{Total}\mathrm{of}X\mathrm{for}\mathrm{all}\mathrm{nodes}$ $\sum _{\mathrm{node}i}^{N_i|C}{X}_i\text{:}\mathrm{Sum}\mathrm{Total}\mathrm{of}X\mathrm{for}\mathrm{nodes}\mathrm{that}\mathrm{satisfy}\mathrm{condition}C$ $\sum _{\mathrm{arc}\mathrm{ij}}{X}_{\mathrm{ij}}\text{:}\mathrm{Sum}\mathrm{Total}\mathrm{of}X\mathrm{for}\mathrm{all}\mathrm{arcs}$ $\sum _{\mathrm{arc}\mathrm{ij}}^{A_{\mathrm{ij}}|C}{X}_{\mathrm{ij}}\text{:}\mathrm{Sum}\mathrm{Total}\mathrm{of}X\mathrm{for}\mathrm{arcs}\mathrm{that}\mathrm{satisfy}\mathrm{condition}C$ $\sum _{\mathrm{ang}}X\text{:}\mathrm{Sum}\mathrm{Total}\mathrm{of}X\mathrm{for}\mathrm{all}\mathrm{weighted}\mathrm{angles}$ $\sum _{\mathrm{arc}\mathrm{ij}}^{\mathrm{node}i}{X}_{\mathrm{ij}}\text{:}\mathrm{Sum}\mathrm{Total}\mathrm{of}X\mathrm{for}\mathrm{arcs}\mathrm{around}\mathrm{node}{N}_1$ $\begin{array}{c}\sum _{\mathrm{ang}}^{N_i\in \mathrm{ang}}X\text{:}\mathrm{Sum}\mathrm{Total}\mathrm{of}X\mathrm{for}\mathrm{all}\mathrm{angles}\mathrm{that}\mathrm{have}\mathrm{node}{N}_1\\ \mathrm{as}a\mathrm{structural}\mathrm{element}\end{array}$ $\begin{array}{c}\sum _{\mathrm{ang}}^{A_{\mathrm{ij}}\in \mathrm{ang}}X\text{:}\mathrm{Sum}\mathrm{Total}\mathrm{of}X\mathrm{for}\mathrm{all}\mathrm{angles}\mathrm{that}\mathrm{have}\mathrm{arc}{A}_{\mathrm{ij}}\\ \mathrm{as}a\mathrm{structural}\mathrm{element}\end{array}$ $\begin{array}{c}\sum _{\mathrm{node}i}^{N_i\in \mathrm{ang}}{X}_i\text{:}\mathrm{Sum}\mathrm{Total}\mathrm{of}X\mathrm{for}\mathrm{nodes}\left(\mathrm{three}\mathrm{of}\mathrm{them}\right)\mathrm{that}\mathrm{are}\\ \mathrm{structural}\mathrm{elements}\mathrm{of}\mathrm{angle}\end{array}$ $\begin{array}{c}\sum _{\mathrm{arc}\mathrm{ij}}^{A_{\mathrm{ij}}\in \mathrm{ang}}{X}_{\mathrm{ij}}\text{: }\mathrm{Sum}\mathrm{Total}\mathrm{of}X\mathrm{for}\mathrm{arcs}\left(\mathrm{two}\mathrm{of}\mathrm{them}\right)\mathrm{that}\mathrm{are}\\ \mathrm{structural}\mathrm{elements}\mathrm{of}\mathrm{an}\mathrm{angle}\end{array}$

[0160] The relationships between the sequence of indexes and the symbols are as follows: $L_{\mathrm{ij}}=L_{\mathrm{ji}},l_{\mathrm{ij}}=l_{\mathrm{ji}}$ $n_{\mathrm{ij}}=n_{\mathrm{ji}},u_{\mathrm{ij}}=u_{\mathrm{ji}},v_{\mathrm{ij}}=v_{\mathrm{ji}},w_{\mathrm{ij}}=w_{\mathrm{ji}}$ $a_{\mathrm{ij}}=-a_{\mathrm{ji}},x_{\mathrm{ij}}=-x_{\mathrm{ji}},y_{\mathrm{ij}}=-y_{\mathrm{ji}},z_{\mathrm{ij}}=-z_{\mathrm{ji}},b_{\mathrm{ij}}=-b_{\mathrm{ji}}$ $s_{\mathrm{ij}}=-s_{\mathrm{ji}},s_{\mathrm{xij}}=-s_{\mathrm{xji}},s_{\mathrm{yij}}=-s_{\mathrm{yji}},s_{\mathrm{zij}}=-s_{\mathrm{zji}}$ ${\rho }_{\mathrm{ij}}=-{\rho }_{\mathrm{ji}}$ $p_{\mathrm{ij}}=p_{\mathrm{ji}},q_{\mathrm{ij}}=q_{\mathrm{ji}},r_{\mathrm{ij}}=r_{\mathrm{ji}}$ $f_{\mathrm{ij}}=f_{\mathrm{ji}},g_{\mathrm{ij}}=g_{\mathrm{ji}},h_{\mathrm{ij}}=-h_{\mathrm{ji}}$ $F_{\mathrm{ij}}=F_{\mathrm{ji}},G_{\mathrm{ij}}=G_{\mathrm{ji}},H_{\mathrm{ij}}=-H_{\mathrm{ji}}$ ${\alpha }_{\mathrm{ij}}={\alpha }_{\mathrm{ji}},{\beta }_{\mathrm{ij}}={\beta }_{\mathrm{ji}},{\gamma }_{\mathrm{ij}}=-{\gamma }_{\mathrm{ji}}$

[0161] <1> Basic Equations

[0162] Assume that the coordinates of a node N_iin FIG. 14 are (x_i, y_i, z_i). In order to express the rotation of an arc therefrom within a three-dimensional space, an arc-normal vector is provided. Assume that the normal vector of an arc A_ij(the arc that links node N_ito node N_j) is n_ij(u_ij, v_ij, w_ij). In this embodiment, these basic variables are used to represent the shape of a skeleton model. The following basic equations hold for each arc: $\begin{array}{cc}\begin{array}{c}{f}_{\mathrm{ij}}\equiv \left[{\left(x_j-x_i\right)}^2+{\left(y_j-y_i\right)}^2+{\left(z_j-z_i\right)}^2-L_{\mathrm{ij}}^2\right]/{\lambda }^2=0\\ g_{\mathrm{ij}}\equiv u_{\mathrm{ij}}^2+v_{\mathrm{ij}}^2+w_{\mathrm{ij}}^2-1=0\\ h_{\mathrm{ij}}\equiv \left[\left(x_j-x_i\right)u_{\mathrm{ij}}+\left(y_j-y_i\right)v_{\mathrm{ij}}+\left(z_j-z_i\right)w_{\mathrm{ij}}\right]/\lambda =0\end{array}& \left(1\right)\end{array}$

[0163] The first equation means that the length of the arc A_ijis L_ij. The second equation means that the magnitude of the normal vector is 1. The third equation means that the arc-normal vector and the arc are mutually perpendicular. A scaling factor λ is used to ensure that equations for a first skeleton model can be the same with equations for a second skeleton model that has a similar figure of the first skeleton model. In other words, if the shape of a first skeleton model has been transformed, a similar form is obtained for a second skeleton model of twice the size, when the shape thereof is transformed by twice the above amount. The average of the lengths of the arcs in each skeleton model is used as λ.

[0164] <2> Method of Solving Basic Equations

[0165] When a user has picked a node for movement, it is necessary to derive the coordinates of the other nodes and the values of the normal vectors of arcs that are associated therewith, during the process of causing a skeleton to move by inverse kinematics. These values are obtained as solutions of Equations (1). However, Equations (1) consist of non-linear expressions, and the number of equations therein is less than the number of variables. This is where a combination of the Newtonian method and the Lagrangian multiplier method is used for a solution.

[0166] Note that the indexes of variables are omitted from the discussion below, unless it is particularly necessary to specify them.

[0167] <2>-1 Application of Newtonian Method

[0168] The variation of each variable in each loop is defined as follows:

[0169] ξ_i≡Δx_i, η_i≡Δy_i, ζ_i≡Δz_i

[0170] p_ij≡Δu_ij, q_ij≡Δv_ij, r_ij≡Δw_ij  (2)

[0171] If the Newtonian method is applied to the above basic Equations (1), the following equations are obtained: $\begin{array}{cc}\sum _{\mathrm{node}k}\left(\frac{\partial f_{\mathrm{ij}}}{\partial x_k}{\xi }_k+\frac{\partial f_{\mathrm{ij}}}{\partial y_k}{\eta }_k+\frac{\partial f_{\mathrm{ij}}}{\partial z_k}{\zeta }_k\right)+\sum _{\mathrm{arc}\mathrm{kl}}\left(\frac{\partial f_{\mathrm{ij}}}{\partial u_{\mathrm{kl}}}{p}_{\mathrm{kl}}+\frac{\partial f_{\mathrm{ij}}}{\partial v_{\mathrm{kl}}}{q}_{\mathrm{kl}}+\frac{\partial f_{\mathrm{ij}}}{\partial w_{\mathrm{kl}}}{r}_{\mathrm{kl}}\right)=-f_{\mathrm{ij}}& \left(3\right)\\ \sum _{\mathrm{node}k}\left(\frac{\partial g_{\mathrm{ij}}}{\partial x_k}{\xi }_k+\frac{\partial g_{\mathrm{ij}}}{\partial y_k}{\eta }_k+\frac{\partial g_{\mathrm{ij}}}{\partial z_k}{\zeta }_k\right)+\sum _{\mathrm{arc}\mathrm{kl}}\left(\frac{\partial g_{\mathrm{ij}}}{\partial u_{\mathrm{kl}}}{p}_{\mathrm{kl}}+\frac{\partial g_{\mathrm{ij}}}{\partial v_{\mathrm{kl}}}{q}_{\mathrm{kl}}+\frac{\partial g_{\mathrm{ij}}}{\partial w_{\mathrm{kl}}}{r}_{\mathrm{kl}}\right)=-g_{\mathrm{ij}}& \\ \sum _{\mathrm{node}k}\left(\frac{\partial h_{\mathrm{ij}}}{\partial x_k}{\xi }_k+\frac{\partial h_{\mathrm{ij}}}{\partial y_k}{\eta }_k+\frac{\partial h_{\mathrm{ij}}}{\partial z_k}{\zeta }_k\right)+\sum _{\mathrm{arc}\mathrm{kl}}\left(\frac{\partial h_{\mathrm{ij}}}{\partial u_{\mathrm{kl}}}{p}_{\mathrm{kl}}+\frac{\partial h_{\mathrm{ij}}}{\partial v_{\mathrm{kl}}}{q}_{\mathrm{kl}}+\frac{\partial h_{\mathrm{ij}}}{\partial w_{\mathrm{kl}}}{r}_{\mathrm{kl}}\right)=-h_{\mathrm{ij}}& \end{array}$

[0172] These equations can be re-arranged as follows: $\begin{array}{cc}\begin{array}{c}{F}_{\mathrm{ij}}\equiv [\left(x_j-x_i\right){\xi }_i-\left(x_j-x_i\right){\xi }_j+\left(y_j-y_i\right){\eta }_i-\left(y_j-y_i\right){\eta }_j+\\ \left(z_j-z_i\right){\zeta }_i-\left(z_j-z_i\right){\zeta }_j]/{\lambda }^2-f_{\mathrm{ij}}/2=0\\ G_{\mathrm{ij}}\equiv u_{\mathrm{ij}}{p}_{\mathrm{ij}}+v_{\mathrm{ij}}{q}_{\mathrm{ij}}+w_{\mathrm{ij}}{r}_{\mathrm{ij}}+g_{\mathrm{ij}}/2=0\\ H_{\mathrm{ij}}\equiv [-u_{\mathrm{ij}}{\xi }_i+u_{\mathrm{ij}}{\xi }_j-v_{\mathrm{ij}}{\eta }_i+v_{\mathrm{ij}}{\eta }_j-w_{\mathrm{ij}}{\zeta }_i+w_{\mathrm{ij}}{\zeta }_j+\\ \left(x_j-x_i\right)p_{\mathrm{ij}}+\left(y_j-y_i\right)q_{\mathrm{ij}}+\left(z_j-z_i\right)r_{\mathrm{ij}}]/\lambda +h_{\mathrm{ij}}=0\end{array}& \left(4\right)\end{array}$

[0173] Since the number of equations in (4) is less than the number of variables, it is not possible to determine a unique solution from them alone. A solution is obtained by adding a minimization condition and applying the Lagrangian multiplier method, as described below.

[0174] Note that in this embodiment the basic equations are varied in each iterative loop by the cursor position set by a mouse, as previously described with reference to FIG. 3B.

[0175] <2>-2 Application of Lagrangian Multiplier Method

[0176] An evaluation expression involving U₁, U₂, U₃, . . . is prepared, a condition that minimizes this sum total is added to Equations (4), and the Lagrangian multiplier method is used to obtain ξ, η, ζ, p, q, and r. The terms U_kwill be defined later. Indeterminate multipliers α_ij, β_ij, and γ_ijare inserted so that U is defined as follows: $\begin{array}{cc}U\equiv \sum _{\mathrm{arc}\mathrm{ij}}\left({\alpha }_{\mathrm{ij}}{F}_{\mathrm{ij}}+{\beta }_{\mathrm{ij}}{G}_{\mathrm{ij}}+{\gamma }_{\mathrm{ij}}{H}_{\mathrm{ij}}\right)+\sum U_k& \left(5\right)\end{array}$

[0177] Equations (4) and Equations (6) below are linked to obtain solutions for ξ, η, ζ, p, q, and r. $\begin{array}{cc}\frac{\partial U}{\partial {\xi }_i}=0,\frac{\partial U}{\partial {\eta }_i}=0,\frac{\partial U}{\partial {\zeta }_i}=0& \left(6\right)\\ \frac{\partial U}{\partial p_{\mathrm{ij}}}=0,\frac{\partial U}{\partial q_{\mathrm{ij}}}=0,\frac{\partial U}{\partial r_{\mathrm{ij}}}=0& \end{array}$

[0178] Based on the thus obtained solutions, new values of x, y, z, u, v, and w are obtained from Expression (7) below, ending the calculations for one iterative loop of the Newtonian method.

[0179] x+ξ→x, y+η→y, z+ζ→z

[0180] u+p→u, v+q→v, w+r→w  (7)

[0181] <3> Creation of Evaluation Expression

[0182] As described previously, when applying the Lagrangian multiplier method it is necessary to prepare an evaluation expression that is to be minimized. In this case, an evaluation expression is created to ensure that the skeleton model undergoes a pleasing transformation.

[0183] <3>-1 Sum-of-Squares of Arc-to-Arc Angle Variations

[0184] Assume that the sum-of-squares of variations in the arc-to-arc angles (joint angles) is U₁. Minimizing U₁assures that all of the joints curve in a well-balanced manner. Differences in the ease of curvature of each joint can be applied by assigning different weightings to each component of the arc-to-arc angles.

[0185] <3>-1-1 Arc-to-Arc Angles and Rotational Matrix

[0186] A rotational matrix M_ijfor converting from a world coordinate system to a coordinate system for the arc A_ijis expressed as shown below. Note that the coordinate system for the arc A_ijis a right-handed system in which the direction of the arc-normal vector is taken as the x-axis and the direction from node N_ito node N_jis taken as the y-axis, as shown in FIG. 15. Note also that the arrangement of matrix elements is in accordance with a method in which the matrix is multiplied from the left with respect to column vectors. $\begin{array}{cc}{M}_{\mathrm{ij}}=\left(\begin{array}{ccc}{u}_{\mathrm{ij}}& x_{\mathrm{ij}}& s_{\mathrm{xij}}\\ v_{\mathrm{ij}}& y_{\mathrm{ij}}& s_{\mathrm{yij}}\\ w_{\mathrm{ij}}& z_{\mathrm{ij}}& s_{\mathrm{zij}}\end{array}\right)& \left(8\right)\\ x_{\mathrm{ij}}\equiv \left(x_j-x_i\right)/l_{\mathrm{ij}},y_{\mathrm{ij}}\equiv \left(y_j-y_i\right)/l_{\mathrm{ij}},z_{\mathrm{ij}}\equiv \left(z_j-z_i\right)/l_{\mathrm{ij}}& \left(9\right)\\ l_{\mathrm{ij}}\equiv \sqrt{{\left(x_j-x_i\right)}^2+{\left(y_j-y_i\right)}^2+{\left(z_j-z_i\right)}^2}& \\ \begin{array}{c}{s}_{\mathrm{xij}}\equiv v_{\mathrm{ij}}{z}_{\mathrm{ij}}-w_{\mathrm{ij}}{y}_{\mathrm{ij}}\\ s_{\mathrm{yij}}\equiv w_{\mathrm{ij}}{x}_{\mathrm{ij}}-u_{\mathrm{ij}}{z}_{\mathrm{ij}}\\ s_{\mathrm{zij}}\equiv u_{\mathrm{ij}}{y}_{\mathrm{ij}}-v_{\mathrm{ij}}{x}_{\mathrm{ij}}\end{array}& \left(10\right)\end{array}$

[0187] A rotational matrix for converting from the coordinate system for the arc A_ijto the coordinate system for the arc A_jkis M_ijk, as follows: $\begin{array}{cc}{M}_{\mathrm{ijk}}\equiv \left(\begin{array}{ccc}{a}_{\mathrm{ijk00}}& a_{\mathrm{ijk01}}& a_{\mathrm{ijk02}}\\ a_{\mathrm{ijk10}}& a_{\mathrm{ijk11}}& a_{\mathrm{ijk12}}\\ a_{\mathrm{ijk20}}& a_{\mathrm{ijk21}}& a_{\mathrm{ijk22}}\end{array}\right)\equiv \left(\begin{array}{ccc}{a}_{00}& a_{01}& a_{02}\\ a_{10}& a_{11}& a_{12}\\ a_{20}& a_{21}& a_{22}\end{array}\right)& \left(11\right)\end{array}$

[0188] Note that the indexes “_ijk” are omitted unless it is particularly necessary to specify them.

[0189] M_ijkis expressed as follows: $\begin{array}{cc}{M}_{\mathrm{ijk}}=M_{\mathrm{ij}}^{-1}{M}_{\mathrm{jk}}=\left(\begin{array}{ccc}{u}_{\mathrm{ij}}& v_{\mathrm{ij}}& w_{\mathrm{ij}}\\ x_{\mathrm{ij}}& y_{\mathrm{ij}}& z_{\mathrm{ij}}\\ s_{\mathrm{xij}}& s_{\mathrm{yij}}& s_{\mathrm{zij}}\end{array}\right)\left(\begin{array}{ccc}{u}_{\mathrm{jk}}& x_{\mathrm{jk}}& s_{\mathrm{xjk}}\\ v_{\mathrm{jk}}& y_{\mathrm{jk}}& s_{\mathrm{yjk}}\\ w_{\mathrm{jk}}& z_{\mathrm{jk}}& s_{\mathrm{zjk}}\end{array}\right)& \left(12\right)\end{array}$

[0190] If the angles of rotation from the coordinate system for the arc A_ijto the coordinate system for the arc A_jkare taken to be θ_x, θ_y, and θ_zand the rotational sequence thereof is the y-axis, the x-axis, then the z-axis, the matrix M_ijkcan be expressed as follows: $\begin{array}{cc}{M}_x=\left(\begin{array}{ccc}1& 0& 0\\ 0& \cos {\theta }_x& -\sin {\theta }_x\\ 0& \sin {\theta }_x& \cos {\theta }_x\end{array}\right)& \left(13\right)\\ M_y=\left(\begin{array}{ccc}\cos {\theta }_y& 0& \sin {\theta }_y\\ 0& 1& 0\\ -\sin {\theta }_y& 0& \cos {\theta }_y\end{array}\right)& \\ M_z=\left(\begin{array}{ccc}\cos {\theta }_z& -\sin {\theta }_z& 0\\ \sin {\theta }_z& \cos {\theta }_z& 0\\ 0& 0& 1\end{array}\right)& \\ M_{\mathrm{ijk}}=M_y{M}_x{M}_z=\left(\begin{array}{ccc}\cdots & \cdots & \cos {\theta }_x\sin {\theta }_y\\ \cos {\theta }_x\sin {\theta }_z& \cos {\theta }_x\cos {\theta }_z& -\sin {\theta }_x\\ \cdots & \cdots & \cos {\theta }_x\cos {\theta }_y\end{array}\right)& \left(14\right)\end{array}$

[0191] Therefore, Expressions (11), (12), and (14) lead to the following: $\begin{array}{cc}{a}_{01}=u_{\mathrm{ij}}{x}_{\mathrm{jk}}+v_{\mathrm{ij}}{y}_{\mathrm{jk}}+w_{\mathrm{ij}}{z}_{\mathrm{jk}}& \left(15\right)\\ a_{02}=u_{\mathrm{ij}}{s}_{\mathrm{xjk}}+v_{\mathrm{ij}}{s}_{\mathrm{yjk}}+w_{\mathrm{ij}}{s}_{\mathrm{zjk}}=\cos {\theta }_x\sin {\theta }_y& \\ a_{10}=x_{\mathrm{ij}}{u}_{\mathrm{jk}}+y_{\mathrm{ij}}{v}_{\mathrm{jk}}+z_{\mathrm{ij}}{w}_{\mathrm{jk}}=\cos {\theta }_x\sin {\theta }_z& \\ a_{11}=x_{\mathrm{ij}}{x}_{\mathrm{jk}}+y_{\mathrm{ij}}{y}_{\mathrm{jk}}+z_{\mathrm{ij}}{z}_{\mathrm{jk}}=\cos {\theta }_x\cos {\theta }_z& \\ a_{12}=x_{\mathrm{ij}}{s}_{\mathrm{xjk}}+y_{\mathrm{ij}}{s}_{\mathrm{yjk}}+z_{\mathrm{ij}}{s}_{\mathrm{zjk}}=-\sin {\theta }_x& \\ a_{21}=s_{\mathrm{xij}}{x}_{\mathrm{jk}}+s_{\mathrm{yij}}{y}_{\mathrm{jk}}+s_{\mathrm{zij}}{z}_{\mathrm{jk}}& \\ a_{22}=s_{\mathrm{xij}}{s}_{\mathrm{xjk}}+s_{\mathrm{yij}}{s}_{\mathrm{yjk}}+s_{\mathrm{zij}}{s}_{\mathrm{zjk}}=\cos {\theta }_x\cos {\theta }_y& \end{array}$

[0192] <3>-1-2 Linear Expressions Relating to Angle Variations Variations in θ_x, θ_y, and θ_zdefine each of φ_x, φ_y, and φ_zas follows:

[0193] φ_x≡Δθ_x, φ_y≡Δθ_y, φ_z≡Δθ_z  (16)

[0194] In this case, an attempt is made to express the relationships between φ_x, φ_y, and φ_zand ξ_i, η_i, ζ_i, p_ij, q_ij, and r_ijby first-degree approximations. Note that variations in a_mndefine b_mnas follows:

[0195] b_mn≡Δα_mn(m=0,1,2 n=0,1,2)  (17)

[0196] The value of φ_xis obtained by rearranging and differentiating Expressions (15): $\begin{array}{cc}\sin {\theta }_x=-a_{12}& \left(18\right)\\ \therefore \cos {\theta }_x{\phi }_x=-b_{12}& \\ \therefore {\phi }_x=\frac{-1}{\sqrt{1-a_{12}^2}}{b}_{12}& \end{array}$

[0197] Similarly, φ_yand φ_zare obtained as follows: $\begin{array}{cc}\tan {\theta }_y=\frac{a_{02}}{a_{22}}& \left(19\right)\\ \therefore {\sec }^2{\theta }_y{\phi }_y=\frac{1}{a_{22}^2}\left(a_{22}{b}_{02}-a_{02}{b}_{22}\right)& \\ \therefore {\phi }_y=\frac{1}{1-a_{12}^2}\left(a_{22}{b}_{02}-a_{02}{b}_{22}\right)& \\ \tan {\theta }_z=\frac{a_{10}}{a_{11}}& \left(20\right)\\ \therefore {\sec }^2{\theta }_z{\phi }_z=\frac{1}{a_{11}^2}\left(a_{11}{b}_{10}-a_{10}{b}_{11}\right)& \\ \therefore {\phi }_z=\frac{-1}{\sqrt{1-a_{12}^2}}\left(a_{11}{b}_{10}-a_{10}{b}_{11}\right)& \end{array}$

[0198] The terms b₀₂, b₁₀, b₁₁, b₁₂, and b₂₂are obtained from differentiation of Expressions (15), as follows: $\begin{array}{cc}\begin{array}{c}{b}_{02}=-a_{01}{s}_{\mathrm{xjk}}\left({\xi }_k-{\xi }_j\right)/l_{\mathrm{jk}}-a_{01}{s}_{\mathrm{yjk}}\left({\eta }_k-{\eta }_j\right)/l_{\mathrm{jk}}-\\ a_{01}{s}_{\mathrm{zjk}}\left({\xi }_k-{\zeta }_j\right)/l_{\mathrm{jk}}+s_{\mathrm{xjk}}{p}_{\mathrm{ij}}+s_{\mathrm{yjk}}{q}_{\mathrm{ij}}+s_{\mathrm{zjk}}{r}_{\mathrm{ij}}-\\ \left(v_{\mathrm{ij}}{z}_{\mathrm{jk}}-w_{\mathrm{ij}}{y}_{\mathrm{jk}}\right)p_{\mathrm{jk}}-\left(w_{\mathrm{ij}}{x}_{\mathrm{jk}}-u_{\mathrm{ij}}{z}_{\mathrm{jk}}\right)q_{\mathrm{jk}}-\\ \left(u_{\mathrm{ij}}{y}_{\mathrm{jk}}-v_{\mathrm{ij}}{x}_{\mathrm{jk}}\right)r_{\mathrm{jk}}\end{array}& \left(21\right)\\ \begin{array}{c}{b}_{10}=\left(u_{\mathrm{jk}}-a_{10}{x}_{\mathrm{ij}}\right)\left({\xi }_j-{\xi }_i\right)/l_{\mathrm{ij}}+\left(v_{\mathrm{jk}}-a_{10}{y}_{\mathrm{ij}}\right)\left({\eta }_j-{\eta }_i\right)/l_{\mathrm{ij}}+\\ \left(w_{\mathrm{jk}}-a_{10}{z}_{\mathrm{ij}}\right)\left({\zeta }_j-{\zeta }_i\right)/l_{\mathrm{ij}}+x_{\mathrm{ij}}{p}_{\mathrm{jk}}+y_{\mathrm{ij}}{q}_{\mathrm{jk}}+z_{\mathrm{ij}}{r}_{\mathrm{jk}}\end{array}& \left(22\right)\\ \begin{array}{c}{b}_{11}=\left(x_{\mathrm{jk}}-a_{11}{x}_{\mathrm{ij}}\right)\left({\xi }_j-{\xi }_i\right)/l_{\mathrm{ij}}+\left(x_{\mathrm{ij}}-a_{11}{x}_{\mathrm{jk}}\right)\left({\xi }_k-{\xi }_j\right)/l_{\mathrm{jk}}+\\ \left(y_{\mathrm{jk}}-a_{11}{y}_{\mathrm{ij}}\right)\left({\eta }_j-{\eta }_i\right)/l_{\mathrm{ij}}+\left(y_{\mathrm{ij}}-a_{11}{y}_{\mathrm{jk}}\right)\left({\eta }_k-{\eta }_j\right)/l_{\mathrm{jk}}+\\ \left(z_{\mathrm{jk}}-a_{11}{z}_{\mathrm{ij}}\right)\left({\zeta }_j-{\zeta }_i\right)/l_{\mathrm{ij}}+\left(z_{\mathrm{ij}}-a_{11}{z}_{\mathrm{jk}}\right)\left({\zeta }_k-{\zeta }_j\right)/l_{\mathrm{jk}}\end{array}& \left(23\right)\\ \begin{array}{c}{b}_{12}=\left(s_{\mathrm{xjk}}-a_{12}{x}_{\mathrm{ij}}\right)\left({\xi }_j-{\xi }_i\right)/l_{\mathrm{ij}}-a_{11}{s}_{\mathrm{xjk}}\left({\xi }_k-{\xi }_j\right)l_{\mathrm{jk}}+\\ \left(s_{\mathrm{yjk}}-a_{12}{y}_{\mathrm{ij}}\right)\left({\eta }_j-{\eta }_i\right)/l_{\mathrm{ij}}-a_{11}{s}_{\mathrm{yjk}}\left({\eta }_k-{\eta }_j\right)/l_{\mathrm{jk}}+\\ \left(s_{\mathrm{zjk}}-a_{12}{z}_{\mathrm{ij}}\right)\left({\zeta }_j-{\zeta }_i\right)/l_{\mathrm{ij}}-a_{11}{s}_{\mathrm{zjk}}\left({\zeta }_k-{\zeta }_j\right)/l_{\mathrm{jk}}-\\ \left(y_{\mathrm{ij}}{z}_{\mathrm{jk}}-z_{\mathrm{ij}}{y}_{\mathrm{jk}}\right)p_{\mathrm{jk}}-\left(z_{\mathrm{ij}}{x}_{\mathrm{jk}}-x_{\mathrm{ij}}{z}_{\mathrm{jk}}\right)q_{\mathrm{jk}}-\\ \left(x_{\mathrm{ij}}{y}_{\mathrm{jk}}-y_{\mathrm{ij}}{x}_{\mathrm{jk}}\right)r_{\mathrm{jk}}\end{array}& \left(24\right)\\ \begin{array}{c}{b}_{22}=-a_{12}{s}_{\mathrm{xij}}\left({\xi }_j-{\xi }_i\right)/l_{\mathrm{ij}}-a_{21}{s}_{\mathrm{xjk}}\left({\xi }_k-{\xi }_j\right)/l_{\mathrm{jk}}-\\ a_{12}{s}_{\mathrm{yij}}\left({\eta }_j-{\eta }_i\right)/l_{\mathrm{ij}}-a_{21}{s}_{\mathrm{yjk}}\left({\eta }_k-{\eta }_j\right)/l_{\mathrm{jk}}-\\ a_{12}{s}_{\mathrm{zij}}\left({\zeta }_j-{\zeta }_i\right)/l_{\mathrm{ij}}-a_{21}{s}_{\mathrm{zjk}}\left({\zeta }_k-{\zeta }_j\right)/l_{\mathrm{jk}}+\\ \left(y_{\mathrm{ij}}{s}_{\mathrm{zjk}}-z_{\mathrm{ij}}{s}_{\mathrm{yjk}}\right)p_{\mathrm{ij}}-\left(s_{\mathrm{yij}}{z}_{\mathrm{jk}}-s_{\mathrm{zij}}{y}_{\mathrm{jk}}\right)p_{\mathrm{jk}}+\\ \left(z_{\mathrm{ij}}{s}_{\mathrm{xjk}}-x_{\mathrm{ij}}{s}_{\mathrm{zjk}}\right)q_{\mathrm{ij}}-\left(s_{\mathrm{zij}}{x}_{\mathrm{jk}}-s_{\mathrm{xij}}{z}_{\mathrm{jk}}\right)q_{\mathrm{jk}}+\\ \left(x_{\mathrm{ij}}{s}_{\mathrm{yjk}}-y_{\mathrm{ij}}{s}_{\mathrm{xjk}}\right)r_{\mathrm{ij}}-\left(s_{\mathrm{xij}}{y}_{\mathrm{jk}}-s_{\mathrm{yij}}{x}_{\mathrm{jk}}\right)r_{\mathrm{jk}}\end{array}& \left(25\right)\end{array}$

[0199] Thus, the angle variations φ_x, φ_y, and φ_zcan be expressed as linear expressions involving ξ, η, ζ, p, q, and r.

[0200] <3>-1-3 Partial Differentiation of Sum-of-Squares of Angle Variations

[0201] The term U₁is expressed as the sum-of-squares of arc-to-arc angle variations, as shown below. Note that W_x, W_y, and W_zare weighting coefficients for adjusting the ease of curvature of the joint, where each term corresponds to rotations about the x-axis, y-axis, and z-axis, respectively. $\begin{array}{cc}{U}_1=\sum _{\mathrm{ang}}\left(W_x{\phi }_x^2+W_y{\phi }_y^2+W_z{\phi }_z^2\right)& \left(26\right)\end{array}$

[0202] Partial differentials of φ_x², φ_y², and φ_z²are obtained as shown below, because they are necessary during the calculations of Equations (6). These are linear expressions involving ξ, η, ζ, p, q, and r. Note, however, that ω is expressed in terms of the variables ξ, η, ζ, p, q, and r. $\begin{array}{cc}\frac{\partial }{\partial \omega }{\phi }_x^2=\frac{2}{1-a_{12}^2}\frac{\partial b_{12}}{\partial \omega }{b}_{12}& \left(27\right)\\ \frac{\partial }{\partial \omega }{\phi }_y^2=\frac{2}{{\left(1-a_{12}^2\right)}^2}\left(a_{22}\frac{\partial b_{02}}{\partial \omega }-a_{02}\frac{\partial b_{22}}{\partial \omega }\right)\left(a_{22}{b}_{02}-a_{02}{b}_{22}\right)& \\ \frac{\partial }{\partial \omega }{\phi }_z^2=\frac{2}{{\left(1-a_{12}^2\right)}^2}\left(a_{11}\frac{\partial b_{10}}{\partial \omega }-a_{10}\frac{\partial b_{11}}{\partial \omega }\right)\left(a_{11}{b}_{10}-a_{10}{b}_{11}\right)& \end{array}$

[0203] <3>-2-1 Necessity of Rubber-Banding

[0204] If a picked node N_iis moved directly, the shape of the skeleton model will be transformed from the initial state shown in FIG. 16A to the ungainly shapes shown in FIG. 16B. In such a case, the node N_iis made to move with rubber-banding, as described with reference to FIGS. 5A to 5E. A rubber-band is a virtual arc which tends to contract. One end of the rubber-band is connected to the node N_i(x_i, y_i, z_i) and the other end (x_ci, y_ci, z_ci) is moved together with the movement of the mouse cursor. This makes it possible to transform the shape of the skeleton model from the initial state shown in FIG. 16C to obtain the preferable shape shown in FIG. 16D. With the motion shown in FIGS. 16A and 16B, iterative calculations are started with the picked node having an initial state at a point 110. In contrast, the iterative calculations for the motion shown in FIGS. 16C and 16D are started with the initial state at a point 112.

[0205] <3>-2-2 Setting of Rubber-Banding

[0206] The contractibility of a rubber-band can be expressed by adding the term U₂, defined below, to the evaluation expression U. W_ris a weighting coefficient for expressing the strength of this contractibility and N_pickis the number of picked nodes. $\begin{array}{cc}{U}_2=\frac{1}{N_{\mathrm{pick}}}\sum _{\mathrm{nodc}i}^{N_i|\mathrm{pick}}{U}_{2i}& \left(28\right)\end{array}$

[0207] By adding U₂to the evaluation expression, the skeleton model can be transformed in such a way that the sum-of-squares of the distances between the picked nodes and other end (x_ci, y_ci, z_ci) of the rubber-band is minimized. Furthermore, as previously described with reference to FIGS. 5D, 5E, and 6, or with reference to Expression (28), a plurality of nodes can be made to move with rubber-banding by this embodiment.

[0208] The partial differentials of U_2iare as follows: $\begin{array}{cc}\frac{\partial U_{2i}}{\partial {\xi }_i}=\frac{2W_r}{{\lambda }^2}\left({\xi }_i+x_i-x_{\mathrm{ci}}\right)& \left(30\right)\\ \frac{\partial U_{2i}}{\partial {\eta }_i}=\frac{2W_r}{{\lambda }^2}\left({\eta }_i+y_i-y_{\mathrm{ci}}\right)& \\ \frac{\partial U_{2i}}{\partial {\zeta }_i}=\frac{2W_r}{{\lambda }^2}\left({\zeta }_i+z_i-z_{\mathrm{ci}}\right)& \end{array}$

[0209] <3>-2-3 Setting of Rubber-Banding Limits

[0210] If the mouse is dragged so far that a rubber-band is stretched too much, the Newtonian method calculations could fail to converge and the motion of the skeleton model could become uncoordinated. If the length l_rubof the rubber-band exceeds a given value l*_rubin such a case, W_ris multiplied by l*_rub/l_rubto compensate for the tension of the rubber-band. Furthermore, if a plurality of nodes are picked, the total rubber-band tension could become too large and so there is a division by N_pickin Expression (28) to compensate therefor.

[0211] <3>-3 Rotation of Arc about Fixed Node

[0212] There is an infinite number of solutions for the rotational component of an arc, such as that shown in FIG. 17A. In such a case, a rotational resistance is applied to an arc A_ijthat has the fixed node N_ias an end point. This resistance can be expressed by adding the term U₃, defined below, to the evaluation expression U. A weighting coefficient for swinging rotation is assumed to be W_sand a weighting coefficient for twisting rotation is assumed to be W_t. $\begin{array}{cc}{U}_3=\sum _{\mathrm{arc}\mathrm{ij}}^{A_{\mathrm{ij}}|N_i{f}_{\mathrm{ix}}}{U}_{3\mathrm{ij}}& \left(31\right)\\ \begin{array}{c}{U}_{3\mathrm{ij}}=W_s[{\left(y_{\mathrm{ij}}{\zeta }_j-z_{\mathrm{ij}}{\eta }_j\right)}^2+{\left(z_{\mathrm{ij}}{\xi }_j-x_{\mathrm{ij}}{\zeta }_j\right)}^2+\\ {\left(x_{\mathrm{ij}}{\eta }_j-y_{\mathrm{ij}}{\xi }_j\right)}^2]/l_{\mathrm{ij}}^2+W_t[{\left(v_{\mathrm{ij}}{r}_{\mathrm{ij}}-w_{\mathrm{ij}}{q}_{\mathrm{ij}}\right)}^2+\\ {\left(w_{\mathrm{ij}}{p}_{\mathrm{ij}}-u_{\mathrm{ij}}{r}_{\mathrm{ij}}\right)}^2+{\left(u_{\mathrm{ij}}{q}_{\mathrm{ij}}-v_{\mathrm{ij}}{p}_{\mathrm{ij}}\right)}^2]\end{array}& \left(32\right)\end{array}$

[0213] The skeleton model can be transformed in such a way that the sum-of-squares of a variation in the direction of an arc having one end fixed is minimized, by adding U₃to the evaluation expression.

[0214] The partial differentials of U_3ijare as follows: $\begin{array}{cc}\frac{\partial U_{3\mathrm{ij}}}{\partial {\xi }_j}=\frac{2W_s}{l_{\mathrm{ij}}^2}\left[\left(1-x_{\mathrm{ij}}^2\right){\xi }_j-x_{\mathrm{ij}}{y}_{\mathrm{ij}}{\eta }_j-z_{\mathrm{ij}}{x}_{\mathrm{ij}}{\zeta }_j\right]& \left(33\right)\\ \frac{\partial U_{3\mathrm{ij}}}{\partial {\eta }_j}=\frac{2W_s}{l_{\mathrm{ij}}^2}\left[-x_{\mathrm{ij}}{y}_{\mathrm{ij}}{\xi }_j+\left(1-y_{\mathrm{ij}}^2\right){\eta }_j-y_{\mathrm{ij}}{z}_{\mathrm{ij}}{\zeta }_j\right]& \\ \frac{\partial U_{3\mathrm{ij}}}{\partial {\zeta }_j}=\frac{2W_s}{l_{\mathrm{ij}}^2}\left[-z_{\mathrm{ij}}{x}_{\mathrm{ij}}{\xi }_j-y_{\mathrm{ij}}{z}_{\mathrm{ij}}{\eta }_j+\left(1-z_{\mathrm{ij}}^2\right){\zeta }_j\right]& \\ \frac{\partial U_{3\mathrm{ij}}}{\partial p_{\mathrm{ij}}}=2W_t\left[{\left(1-u_{\mathrm{ij}}\right)}^2{p}_{\mathrm{ij}}-u_{\mathrm{ij}}{v}_{\mathrm{ij}}{q}_{\mathrm{ij}}-w_{\mathrm{ij}}{u}_{\mathrm{ij}}{r}_{\mathrm{ij}}\right]& \left(34\right)\\ \frac{\partial U_{3\mathrm{ij}}}{\partial q_{\mathrm{ij}}}=2W_t\left[-u_{\mathrm{ij}}{v}_{\mathrm{ij}}{p}_{\mathrm{ij}}+{\left(1-v_{\mathrm{ij}}\right)}^2{q}_{\mathrm{ij}}-v_{\mathrm{ij}}{w}_{\mathrm{ij}}{r}_{\mathrm{ij}}\right]& \\ \frac{\partial U_{3\mathrm{ij}}}{\partial r_{\mathrm{ij}}}=2W_t\left[-w_{\mathrm{ij}}{u}_{\mathrm{ij}}{p}_{\mathrm{ij}}-v_{\mathrm{ij}}{w}_{\mathrm{ij}}{q}_{\mathrm{ij}}+{\left(1-w_{\mathrm{ij}}\right)}^2{r}_{\mathrm{ij}}\right]& \end{array}$

[0215] <3>-4 Setting of Node Inertia

[0216] The shape of the skeleton model can cause uncoordinated motion to occur. This uncoordinated motion can be reduced by affixing inertia and dampers (which will be described later) to the node. Node inertia can be expressed by adding the following term U₄to the evaluation expression U: $\begin{array}{cc}{U}_4=\sum _{\mathrm{node}i}{U}_{4i}& \left(35\right)\end{array}$  U_4i=W_I[(ξ_i−ξ_i″)²+(η_i−η_i″)²+(ζ_i−ζ_i″)²]/λ²  (36)

[0217] The term U_4icorresponds to the inertia of node N_i. (ξ″, η″, ζ″ is a movement vector for the node N_i, from the previous event cycle. W_Iis a weighting coefficient representing the strength of the inertia. The skeleton model can be transformed in such a way that the sum-of-squares of the variation in the velocity of the node coordinates is minimized, by adding U₄to the evaluation expression.

[0218] The partial differentials of U_4iare as follows: $\begin{array}{cc}\frac{\partial U_{4i}}{\partial {\xi }_i}=\frac{2W_I}{{\lambda }^2}\left({\xi }_i-{\xi }_i^{\mathrm{\prime \prime }}\right)& \left(37\right)\\ \frac{\partial U_{4i}}{\partial {\eta }_i}=\frac{2W_I}{{\lambda }^2}\left({\eta }_i-{\eta }_i^{\mathrm{\prime \prime }}\right)& \\ \frac{\partial U_{4i}}{\partial {\zeta }_i}=\frac{2W_I}{{\lambda }^2}\left({\zeta }_i-{\zeta }_i^{\mathrm{\prime \prime }}\right)& \end{array}$

[0219] <3>-5 Setting of Node Damper

[0220] A node damper can be expressed by adding the following term U₅to the evaluation expression U: $\begin{array}{cc}{U}_5=\sum _{\mathrm{node}i}{U}_{5i}& \left(38\right)\end{array}$  U_5i=W_d(ξ_i²+η_i²+ζ_i²)/λ²  (39)

[0221] The term U_5icorresponds to the damper of node N_i. W_dis a weighting coefficient representing the strength of the damper. The skeleton model can be transformed in such a way that the sum-of-squares of the variation in the node coordinates is minimized, by adding U₅to the evaluation expression.

[0222] The partial differentials of U_5iare as follows: $\begin{array}{cc}\frac{\partial U_{5i}}{\partial {\xi }_i}=\frac{2W_d}{{\lambda }^2}{\xi }_i& \left(40\right)\\ \frac{\partial U_{5i}}{\partial {\eta }_i}=\frac{2W_d}{{\lambda }^2}{\eta }_i& \\ \frac{\partial U_{5i}}{\partial {\zeta }_i}=\frac{2W_d}{{\lambda }^2}{\zeta }_i& \end{array}$

[0223] <4> Singular State and Countermeasure

[0224] <4>-1 Creation of Singular State

[0225] The shape of the skeleton model may be such that Equations (4) includes dependent equations. In the examples shown in FIGS. 17B and 17C, the equation F_ijare dependent. The equations G_ijand H_ijare not dependent.

[0226] Taking FIG. 17B by way of example, the Equations (4) include the equation F_ijfor arcs 120 and 121 (hereinafter called equations F₁and F₂, respectively). In this case, the equation F₁defines that the length of the arc 120 is constant in the form of a first-degree approximation. In other words, a node 124 is regulated to lie within a surface 126 that is perpendicular to the arc. Similarly, the equation F₂defines that the length of the arc 122 is constant in the form of a first-degree approximation. In other words, the node 124 is regulated to lie within the surface 126. That is to say, the equations F₁and F₂have the same meaning, and F₁and F₂are mutually dependent equations. If Equations (4) include dependent equations, it is not possible to determine a unique solution even if the Lagrangian multiplier method is used and the number of equations is the same as the number of variables. The example of FIG. 17C is similar in that the location of a node 136 is determined uniquely by the equation F_ijrelating to arcs 128, 130, or 132, which means that the equation F_ijrelating to an arc 134 is a dependent equation.

[0227] When Equations (4) include dependent equations in this manner, a unique solution cannot be determined if the Lagrangian multiplier method is used without modification. In such a case, the singular value decomposition method described below is used to reconfigure the set of simultaneous equations into an independent set of simultaneous equations.

[0228] <4>-2 Singular Value Decomposition

[0229] Singular value decomposition is a method which decomposes an m×n matrix A into the following equation:

[0230] A=UWV^t  (41)

[0231] Note that U is an m×n matrix, V is an n×n matrix, W is a diagonal n×n matrix, and U and V satisfy the following equations:

[0232] U^tU=E, V^tV=VV^t=E  (42)

[0233] Use of singular value decomposition makes it possible to reduce the number of equations of a dependent set of simultaneous equations and reconfigure the equations as an independent set of simultaneous equations, as described below. An example of the original equations are expressed as follows:

[0234] Ax=b  (43)

[0235] If m≧n, the following equation can be obtained by decomposing and transforming the matrix A into the form of Equation (41):

[0236] WV^tx=U^tb  (44)

[0237] On the other hand, if m<n, the matrix A^tcan be subjected to singular value decomposition to obtain Equation (45) below. In this case, U is an n×m matrix, V is an m×m matrix, W is an m×m diagonal matrix, and U and V satisfy Equation (42).

[0238] A^t=UWV^t  (45)

[0239] This causes Equation (43) to transform as follows:

[0240] WU^tx=V^tb  (46)

[0241] An independent set of simultaneous equations can be obtained from the Equations (44) and (46) by setting the diagonal elements of W to zero and remove a row.

[0242] Note that whether or not the set of simultaneous equations includes dependent equations, in other words, whether or not the set of simultaneous equations has become degenerate or in a state approximating thereto, can be determined by whether or not the diagonal elements of the diagonal matrix W are zero or close to zero.

[0243] <5> Setting of Movability Range of Arc-to-Arc Angles

[0244] <5>-1 Addition of Basic Equation

[0245] As described with reference to FIGS. 8A and 8B, limits to the movability ranges of arc-to-arc angle are provided. The upper and lower limits of the arc-to-arc angles θ_x, θ_y, and θ_zare set as follows:

[0246] θ_x0≦θ_x≦θ_x1(0≦θ_x1−θ_x0≦2π)

[0247] θ_y0≦θ_y≦θ_y1(0≦θ_y1−θ_y0≦2π)  (47)

[0248] θ_z0≦θ_z≦θ_z1(0≦θ_z1−θ_z0≦2π)

[0249] The movability ranges of θ_x, θ_y, and θ_zcan be limited by introducing new variables t_x, t_y, and t_zand adding the following equalities (equations) e_x, e_y, and e_zto the basic Equations (1): $\begin{array}{cc}{e}_x\equiv k_{\mathrm{x1}}\cos {\theta }_x+k_{\mathrm{x2}}\sin {\theta }_x+k_{\mathrm{x3}}-t_x^2=0& \left(48\right)\\ e_y\equiv k_{\mathrm{yl}}\cos {\theta }_y+k_{\mathrm{y2}}\sin {\theta }_y+k_{\mathrm{y3}}-t_y^2=0& \\ e_z\equiv k_{\mathrm{zl}}\cos {\theta }_z+k_{\mathrm{z2}}\sin {\theta }_z+k_{\mathrm{z3}}-t_z^2=0& \end{array}$