FIELD OF THE INVENTION The present invention relates to the field of computer graphics and more particularly relates to a mechanism for skeletal joint optimization for linear blend skinning deformations utilizing skeletal pose sampling.

BACKGROUND OF THE INVENTION

Linear Blend Skinning (LBS) is a well-known standard technique for skeleton based animation and used extensively in video games, movies, simulations and virtual-reality systems. One fact that makes LBS popular is that artists are used to manipulating skeletons for deformation and animation. Another is that the LBS expression or formula can be evaluated directly without the use of any optimization process. This is important if performance is relevant (e.g., games). The input mesh is transformed by blending bone transformations using skinning weights, which define the influence bones have on mesh vertices. Skinning is the process of computing these weights.

Skinning is a well-known standard technique in computer graphics for skeleton based animation that requires little computational overhead and has been used extensively in video games, movies, simulations and virtual-reality systems. This process associates a skeleton, defined by a set of segments, each storing a rotation/translation pair {(R ,T/)} to a mesh. The skeleton can be manipulated, which modifies in turn the deformation pairs. These transformations can then be transferred to the mesh vertices. Specifically, the location of a vertex i under linear blend skinning (LBS) is determined by

∑ _Wij (Rj - Vi + Tj) ,

(1) where v _l is the original position of vertex i and wy the influence of bone j on i. The major challenge lies in determining the weights {wy} to ensure adequate transformations. Figure 1A illustrates an example standard skeleton topology 60 in Blender, which is a popular free and open source 3D creation software suite. The skeleton definitions 62, 68 (shown in Figure IB and 1C) consist of vertices 63, 64, 70 where joints 70, 64 connect two segments 72 and oriented segments 66 for parent relations, and extremities 63 are connected to one segment only as shown in Figures IB and 1C. For example, in Figure 1C, the skeleton topology 68 includes bone F that is the parent of bones Ci through C ₅ .

Considering typical meshes and their skeletons produced by artists, such as shown in Figure 1A, it becomes clear that automatic skinning is challenging. First, models can consist of disconnected parts, which might not even be manifold. Second, the skeletal topology might differ from the mesh topology, as it is conceived to facilitate animating, not to follow geometric constraints. In particular, bones might jut out of the shape's interior. Further, it is not even possible to always define an interior. Third, the skeleton can be complex in itself. Previously, many automatic approaches cannot handle such input and require complex (or unwanted) and potentially costly mesh and skeleton modifications.

Typically, skinning weights should have certain properties (e.g., affinity, positivity, sparsity and locality). Approaches based on (k-)harmonic or general partial differential equations ensure this on the surface or on a volumetric embedding, while enforcing additional smoothness constraints derived from the geometry of the mesh/skeleton. Nonetheless, while smooth weights are necessary, they are not sufficient to enable high-quality deformations.

In prior art techniques, as the goal of the skinning process is to enable adequate deformations, the quality of the weights is generally assessed via experiments, in which several poses under reasonable user-defined transformations are produced. These poses are then evaluated using certain quality metrics, such as the conformality factor, which often serves as a main quality indicator. The above weight constraints, however, while being important, do not directly address this goal. Thus, for practicality, there is a need for a skinning mechanism that overcomes the above- mentioned challenges and disadvantages of prior art techniques.

SUMMARY OF THE INVENTION

The present invention provides a novel and useful mechanism for the skinning of 3D meshes with reference to a skeleton utilizing statistical weight optimization techniques. The mechanism of the present invention comprises (1) an efficient high quality LBS skinning technique based on a set of skeleton deformations sampled from the manipulation space; (2) a joint placement algorithm to optimize the input skeleton; and (3) a set of tools for a user to interactively control the skinning process.

The approach of the mechanism of the present invention optimizes weights to achieve as- good-as-possible mesh deformations. These transformations are referred to as "as-rigid-as- possible" or ARAP transformations to benefit from their properties (angle, aspect ratio, edge length preservation, etc. ). A set of representative skeleton deformations referred to as exemplars are then constructed that are sampled from the space of all possible transformations (i.e. the manipulation space).

The skinning weights are then optimized to achieve an ARAP transformation of the mesh for the exemplars. One reason the weights generated by the invention are naturally smooth is because differential quantities (i.e. Jacobian of the transformations, hence, involving the gradient of the weights) are considered in the process. Taking samples from the manipulation space or using user-provided skeleton animations (e.g., games often use predefined animations), naturally integrates constraints, such as joint-angular and axis-motion constraints of popular modeling packages (e.g., Blender, Maya) currently available.

The approach of the present invention is general and robust. Although compatible with volumetric meshes, it does not rely on volumetric structures for the weight computation on surface meshes. Otherwise, the input would be limited to objects that can be represented as a 2-boundary of a volume. The mechanism of the present invention is capable of handling numerous challenges, including for example, self intersections, open boundaries, disconnected parts or wire-edges, and is compatible with complex (i.e. parameterized) bones (e.g., twistable, stretchable and bendable bones, and spines, a generalization described in more detail infra). The mechanism also supports the user in fitting the skeleton to the input for an optimal deformation quality, which can be a tedious step for prior art approaches.

The mechanism was developed to maximize efficiency and user-friendliness. In addition, a sparsification scheme is utilized that is applied prior to the weight optimization step. This results in a performance increase of several orders of magnitude. This enables interactive tools to be provided to a user to control the skinning process using brush metaphors. Also provided is fine-tuning of sparsity and locality of the resulting skinning weights, which are properties that are ill defined in prior art approaches.

The methods of the present invention is capable of optimizing the skinning weights so to achieve the desired properties of affinity, positivity, sparsity and locality, as well as an as-rigid-as- possible (ARAP) transformation behavior to preserve angles, aspect ratios, and edge lengths etc. . To this extent, the methods of the present invention use an optimization process involving a set of representative deformations, which are sampled from the space of possible skeleton transformations, referred to as manipulation space. The skinning weights are optimized for these deformations to optimize for ARAP transformations and they are naturally smooth because differential quantities (the Jacobian of the transformations, thus, involving the gradient of the weights on the surface) are considered.

The solution of the present invention can support a large variety of triangle and tetrahedral meshes. Only very few assumptions are imposed, which makes it possible to use most existing models directly. In particular, the present method has been demonstrated on meshes featuring non- manifold structures, self-intersections, open boundaries, disconnected components and wire edges.

The invention further introduces several interactive tools to resolve ambiguous situations, e.g., for relationships between disconnected components. The user interaction remains minimal and, in most cases, the approach is actually automatic. User input is relied on only for configurations where all existing approaches fail.

The invention also supports the user in creating a skeleton, if needed. In this case, it is enough to define it coarsely with respect to the mesh. The method adapts this control structure automatically to reach an optimal deformation quality.

The invention also incorporates motion constraints on the skeleton. These restrictions are often readily available and provided by the artist for a skeleton in order to facilitate the use of the skeleton (e.g., the models on Blendswap.com) and can be defined easily. The method exploits this information naturally during the sampling process, which leads to a further increased quality of the weights.

Similarly, if examples of key transformations are provided, the method can integrate these seamlessly in the optimization process as well (e.g., in games where a few character animations are predefined). Finally, the fast execution of the algorithms of the method makes for an almost instant verification and immediate use of the results possible.

Specifically, the methods of the present invention includes (1) an approach to sample exemplars in the manipulation space; (2) an exemplar based skinning weight optimization method that takes into account bones that can be stretched; (3) a joint-placement algorithm to optimize the input skeleton; (4) a selection of tools to control the skinning process; and (5) a set of accelerations to attain high performance.

There is thus provided in accordance with the invention, a method of optimizing joint positions of a skeleton, the method comprising receiving 3D mesh information, skeleton information and linear blend skinning (LBS) weights related to a 3D model, generating a plurality of representative structure preserving deformation exemplars of said skeleton sampled from a manipulation space of all possible skeleton deformations, generating a linear relationship between joint positions and bone translations by constraining the bones to be connected at their respective joints when the bones of each exemplar are rotated, for each bone of each exemplar, fixing a rotation entity while allowing a translation entity to change, calculating an energy entity representing a quality of deformation of the mesh as a function of the rotation and translation, and determining joint positions so as to minimize said energy entity over said plurality of exemplars.

There is also provided in accordance with the invention, a method of optimizing positions of the joints of a skeleton used for deforming a 3D polygonal mesh using linear blend skinning (LBS) transformations, the method comprising receiving 3D mesh information, skeleton information and linear blend skinning weights related to the model, generating a plurality of representative structure preserving deformation exemplars of said skeleton sampled from a manipulation space of all possible skeleton deformations, first expressing bone displacements in terms of joint displacements whereby the bones are constrained to be connected at their respective joints when the bones of each exemplar are rotated, for each vertex of an exemplar, second calculating an energy entity representing a quality of deformation of the mesh as a function of the rotation and displacement based on bone displacements and joint displacements, and iterating said second calculating over said plurality of exemplars so as to generate optimal joint positions that minimizes said energy entity.

There is further provided in accordance with the invention, a computer program product for optimizing joint positions of a skeleton used for deforming a 3D polygonal mesh using linear blend skinning (LBS) transformations, the computer program product comprising a non-transitory, tangible computer usable storage medium having computer usable code embodied therewith, the computer usable program code comprising computer usable code configured for receiving 3D mesh information, skeleton information and linear blend skinning weights related to the model, computer usable code configured for generating a plurality of representative structure preserving deformation exemplars of said skeleton sampled from a manipulation space of all possible skeleton deformations, computer usable code configured for generating a linear relationship between joint positions and bone translations by constraining the bones to be connected at their respective joints when the bones of each exemplar are rotated, computer usable code configured for fixing a rotation entity, for each bone of each exemplar, while allowing a translation entity to change, computer usable code configured for calculating an energy entity representing a quality of deformation of the mesh as a function of the rotation and translation, and computer usable code configured for determining joint positions so as to minimize said energy entity over said plurality of exemplars.

There is also provided in accordance with the invention, a computer program product for optimizing joint positions of a skeleton used for deforming a 3D polygonal mesh using linear blend skinning (LBS) transformations, the computer program product comprising a non-transitory, tangible computer usable storage medium having computer usable code embodied therewith, the computer usable program code comprising computer usable code configured for receiving 3D mesh information, skeleton information and linear blend skinning weights related to the model, computer usable code configured for generating a plurality of representative structure preserving deformation exemplars of said skeleton sampled from a manipulation space of all possible skeleton deformations, computer usable code configured for first expressing bone displacements in terms of joint displacements whereby the bones are constrained to be connected at their respective joints when the bones of each exemplar are rotated, computer usable code configured for second expressing, for each vertex of an exemplar, an energy entity representing a quality of deformation of the mesh as a function of the rotation and displacement based on bone displacements and joint displacements, and computer usable code configured for iterating said second calculating over said plurality of exemplars so as to generate optimal joint positions that minimizes said energy entity.

BRIEF DESCRIPTION OF THE DRAWINGS

The invention is herein described, by way of example only, with reference to the accompanying drawings, wherein:

Fig. 1 A is a diagram illustrating an example prior art skeleton topology;

Fig. IB is a diagram illustrating an example mesh and skeleton used to illustrate the principles of the present invention;

Fig. 1C is a diagram illustrating the detailed topology of the skeleton in Figure IB;

Fig. 2A is a diagram illustrating the process of constructing a spine as a bone subdivided into N small bones;

Fig. 2B is a diagram illustrating the limit behavior obtained when considering additional bones for the approximate representation of the spine;

Fig. 2C is a diagram illustrating several examples of possible spine transformations including stretching, bending and twisting;

Figs. 3 A and 3B are diagrams illustrating an example of spine conversion into two bones;

Fig. 4 is a general block diagram illustrating the linear blend skinning processing of the present invention;

Fig. 5 is a flow diagram illustrating an example linear blend skinning method of the present invention;

Fig. 6A is a diagram depicting an example input mesh and skeleton used to illustrate the method of generating linear blend skinning weights;

Fig. 6B is a diagram illustrating example input constraints;

Fig. 6C is a diagram illustrating an example weight initialization;

Fig. 6D is a diagram illustrating example weight maps sparsification and optional editing; Fig. 6E is a diagram illustrating the creation of exemplars;

Fig. 6F is a diagram illustrating weight optimization and optional joint optimization in accordance with the present invention; Fig. 6G is a diagram illustrating an example deformation created using the resulting weights;

Fig. 7 is a diagram illustrating successive bone rotations for the creation of an example exemplar;

Figs. 8A and 8B are diagrams illustrating example bone Voronoi cells;

Figs. 8C and 8D are diagrams illustrating mesh transformations respectively before and after the first iteration of the weight optimization;

Fig. 9A is a diagram illustrating an example of skeleton constraints, such as fixed rotation axis or bounded range of rotation, editing in Blender;

Figs. 9B and 9C are diagrams illustrating an example of skeleton deformation exemplars created respectively without and with such constraints using the present invention

Fig. 10 is a diagram illustrating several examples of deformations using stretchable bones and spines;

Fig. 11 is a flow diagram illustrating an example as-rigid-as-possible (ARAP) linear blend skinning (LBS) weight optimization method of the present invention;

Fig. 12 is a flow diagram illustrating an example linear blend skinning (LBS) weight one- step optimization method of the present invention;

Fig. 13 is a flow diagram illustrating an example joint optimization method of the present invention;

Fig. 14 is a diagram illustrating algebraic construction of the exemplars;

Fig. 15A is a diagram illustrating example weights created with the present invention (without non-negativity constraints in this example) for eight exemplars;

Fig. 15B is a diagram illustrating example weights created with the present invention (without non-negativity constraints in this example) for 32 exemplars;

Figs. 16A, 16B, 16C are diagrams illustrating clusterings of various sizes which are uniform despite anisotropic vertex distribution; Fig. 17 is a diagram illustrating example links added via wire-edges to the teeth of a dog's mouth;

Figs. 18 A, 18B, 18C, 18D, 18E are diagrams illustrating transformations for an example dog skeleton and mesh using the weights created using the present invention and an existing state- of-the-art weight computation technique, respectively;

Figs. 19A, 19B, 19C, 19D, 19E are diagrams illustrating transformations for an example lemur skeleton and mesh using the weights created using the present invention and an existing state-of-the-art weight computation technique, respectively;

Figs. 20A, 20B, 20C, 20D, 20E, 20F, 20G, 20H are diagrams illustrating transformations for an example body skeleton and mesh using the weights created using the present invention and an existing state-of-the-art weight computation technique, respectively;

Figs. 21A, 21B, 21C, 21D, 21E, 21F are diagrams illustrating a comparison with bounded biharmonic weights;

Figs. 22A, 22B, 22C are diagrams illustrating an example disconnected skeleton and resultant optimized weights and deformations;

Figs. 23 A, 23B, 23C are diagrams illustrating the results of joint optimization of the present invention;

Figs. 24A, 24B, 24C, 24D, 24E are diagrams illustrating transformations for an example body skeleton and mesh using 16 small bones and a spine deformer subdivided into 16 bones after the weight optimization performed using the present invention, respectively; and

Fig. 25 is a block diagram illustrating an example computer processing system adapted to implement the linear blend skinning (LBS) methods of the present invention. DETAILED DESCRIPTION OF THE INVENTION

1 Technical Basis

1.1 Skeleton Topology and Constraints

A skeleton as shown in Figures 1A, IB and 1C is composed of skeletal vertices 63, 64, 70 and segments 66, 72, which are directed wire edges creating parent-child dependencies. Each segment consists of two vertices (for example segment 72 has vertices 64 and 63); an origin and a target along the segment's direction. Segments can be bones 72, whose transformations will have an influence on the mesh, or virtual segments, which are used to define parent-child relations between otherwise not directly connected bones. Virtual segments, e.g., 66, follow the deformations of the skeleton, but do not influence the mesh. Bones can have restrictions like maximal angles or imposed rotation axes.

1.2 Linear Blend Skinning (LBS) With Parameterized Bones

As explained supra, skinning is a standard technique in computer graphics for skeleton based animation that induces little computational overhead and has been used extensively in video games, movies, simulations, and virtual-reality systems. This process associates a skeleton, defined by a set of segments, each storing a rotation/translation pair {(R _j , 7})} to a mesh. The skeleton can be manipulated, which modifies in turn the deformation pairs. These transformations can then be transferred to the mesh vertices. Specifically, the location of a vertex i under linear blend skinning (LBS) is determined by the expression give in Equation 1 supra.

The location of a vertex i under LBS, using parameterized bones, is given by

jeB(i)

(2) where

v, is the input vertex;

R _j (v,) is the rotation applied to vertex i by bone j; T _j (yi) the translation applied to vertex i by bone j. Note that for rigid bones, these transformations are constant, but vary over the mesh for parameterized bones;

B(J) is the set of bones influencing z;

wy the weight of vertex i with respect to bone j;

The quantity {B(J)} is referred to as the bone influence maps and is refereed to as the weight maps.

The quantity being summed represents the rigid transformation applied to vertex i by bone j. Each bone (indexed by j) transforms the input vertex using a rigid transformation (i.e. a rotation and a translation). The final transformation of the vertex is obtained by averaging the transformations by all bones, using the weights w, which define the respective influence of the bones over the vertex.

Typically, skinning weights need to fulfill certain constraints:

1. Affinity:∑ w _i = 1; ensures that the model is not distorted under rigid transformations.

2. Positivity: w _tj ≥ Of or every bone j; prevents unnatural behavior (e.g., translating a bone in one direction could induce translations in the opposite direction).

3. Sparsity: only "few" w _tj > 0; leads to simpler controls and a faster rendering process (ill-defined).

4. Locality: bones should have "small" influence zones; improves control over editing operations (ill- defined).

1.3 Spines

An example of parameterized bones is twistable and stretchable bones. The methods of the present invention are compatible with this kind of bones and a generalization referred to as "spines" which are introduced herein. A spine is defined as a skeletal segment which is subdivided into infinitely small bones, which undergo the same transformation as shown in Figures 2A, 2B and 2C. The term reflects its suitability to represent spines in models. Fixing e ₀ , the spine transformation combines a stretch σ (84), affecting its length, and a rotation around an axis a, such that the accumulated rotation from e ₀ to e _} amounts to Θ. Similar to other bones, a spine also has a rigid transformation applied to e ₀ , the spine's base transformation (R _s , t _s ). In consequence, a spine has five parameters: (R _s , t _s , σ, Θ, a). It generalizes twistable (e.g., 2π twist 82) and stretchable bones (84) because a twistable bone is a spine with a twist-only rotation. A π rotation example is shown in 86. Formulas of the induced transformation for spines are presented infra.

A point p with parameter u(p) e [0, 1] (u describes "to which infinitely small bone" p is attached) is transformed by a spine as p→ R _s Ri _0C (u(p)) -p + R _s -ti _oc (u(p)) + _s ,

rotation translation

(3) with

Given a spine s with vertices e ₀ , e _} , one needs to define the above parameterization u _s : V→

[0, 1] on the mesh vertices V to define the influence of the bone. It is possible to use complex (or artistically driven definitions. By default, we use a linear parameterization: u _s (Vi) = max(0, min(l, (vi - e ₀ ) ^T■ e ₀ ei / | |e ₀ ei | | ² ))

If an artist would like to manipulate a set of bones instead of a smooth spine, or a system that only supports rigid bones, a spine s can be converted into a set of bones, s is cut into n bones with vertices v ₀ ^■■ -v„ and for each v _l its corresponding w-parameter w, is determined. We define the w-parameterization for a bone v, as a piecewise linear function{7T : [0, 1]→[0, 1]}, where TI^C^) =

6 _k ^J with Cj = (iij + Uj ₊ i)/2. Additionally, we impose π ₀ (0) = π _η -ι(1) = 1. The weight of a mesh vertex / w.r.t. bone k is defined as w _ls tiu _s {v ). An example of a spine conversion into two bones is shown in Figure 3. 1.4 As-Rigid- As-Possible (ARAP) Transformations.

ARAP deformations include vertex positions that are optimized to reproduce almost rigid behavior in areas not specified by the user. Instead of vertices, the methods of the present invention focus on bone influences. An ARAP transformation / minimizes the energy:

= : <£i (f, 7¾.(¾) ), the rigidity of vertex i assuming rotation 7Z(i)

s

<£(/, n) = \ \ ² ,

(6) where V _\ {i) is the one ring neighborhood of vertex i, R(J) is a rotation matrix associated with vertex / ^' , A _; is an input vertex weight and λ¾ an input weight for the directed edge from vertex i to k to account for the local discretization of the mesh.

Regarding ARAP transformations, the optimum manner of defining LBS weights (i.e. skeleton weights) is really not known. It is known, however, what are 'good' transformations of a surface (i.e. the input mesh): ARAP transformations. This is because ARAP transformations preserve edge length, angles, surface and texture aspect. Therefore, the methods of the present invention define the LBS weights as those that deform the surface in a ARAP fashion when the skeleton is manipulated by the user.

The ARAP energy expressed above in Equation 6, the ARAP energy defines how much the transformations of the neighborhood of every vertex differ from rotations. This energy, which we want to minimize, depends on the transformation function which depends on the LBS weights in this case. Given a transformation of the skeleton (i.e. the rotation and translation of the various bones), the LBS weights are optimized so as to obtain a deformation which minimizes this ARAP energy.

Since it is not practical to do this for every possible skeleton transformation, a large number of skeleton transformations are created and it is assumed that these are representative enough of the transformations that will be used by an artist later on. 2 General Overview

A general block diagram of the skinning methods of the present invention is shown in Figure 4. The processing block 10 comprises initialization block 12, weight optimization block 14, joint optimization block 16 (optional) and iteration block 26. The input to the methods of the present invention is a polygonal mesh 18 and a skeleton 20 having possible deformation restrictions (i.e. user specified constraints 22). The output is the skinning weights 24, which employed with LBS (i.e. Equation 2) minimize the ARAP energy (i.e. Equation 6) over a set of skeleton deformations.

A flow diagram illustrating the LBS skinning weights method of the present invention is shown in Figure 5. An example of the overall process of the invention is shown in Figures 6A, 6B, 6C, 6D, 6E, 6F and 6G. Figure 6A shows the 3D mesh 32 and skeleton 34 input for an example animated character 30 of an ogre. Optional user specified constraints are shown in Figure 6B.

During weight initialization as shown in Figure 6C, a rough weight estimate based on the rest pose (e.g., 36) is generated (step 120). The weights are then sparsified, shown in Figure 6D, by reducing the bone influence B(i) of each vertex i concurrently to localize the influence and improve performance (step 122) (see characters 38, 40, 42, 44 and 46). A user can also refine these bone- influence maps to fine-tune the process (48). Finally, a set of skeleton deformations 50 referred to as exemplars are generated, as shown in Figure 6E, by sampling the manipulation space respecting skeleton constraints (58) or by using provided skeleton animations (56) (step 124). Note that the segments of the skeleton may include constraints 58. The resultant weight optimized and optional joint optimized character 52 is shown in Figure 6F. An deformation example 54 is shown in Figure 6G.

Note that the manipulation space is defined as the space of all possible transformations of the skeleton, which an artist can do. The rotation and translation of the bones cannot be arbitrary as they should at least preserve the connectivity of the bones at the joint. These transformations are generally constrained meaning that not every bone can be moved freely; some have maximum angle constraints. These constraints are taken into account when sampling from the manipulation space. In one embodiment, the methods of the present invention are operative to take as input existing skeleton animations. Note that it has been found that approximately 80 poses of the skeleton are sufficient to yield quality results.

An example generation of an exemplar is shown in Figure 7. Starting from the rest pose 390, an exemplar is constructed as a set of rigid transformations per bone, where each bone defines a local rotation, which are accumulated along parent-child relations. The concatenated rotations are kept and the translations ensure that the skeleton segments stay connected. Successive bone rotations are shown in 392, 394, 396, 398 and 400 resulting in the final exemplar 402.

With reference to Figure 5, the weight optimization stage defines the skinning weights, which result in as-rigid-as-possible (ARAP) transformations for the exemplars, by solving, in one embodiment, a least-squares inversion of a linear system (step 126). The solution is found iteratively by optimizing rotation matrices and weights alternatingly (step 128). The method iterates over steps 126, 128, 130 until desired convergence is achieved (step 132). During each iteration, constraints are added to avoid trivial solutions and to ensure weight positivity. Upon convergence, the optimal weights have been determined.

Optional joint optimization is performed in step 130. If performed, it is used to refine the input skeleton's joint positions. Being pivot points, they greatly impact the quality of the resulting transformations. Designing a precise skeleton requires strong artist skills, whereas quadratic-energy optimization of the invention is automatic, a big advantage. Note that when alternating between weight and joint optimizations, each linear system needs to re-factorized. As changing joints implies changing the exemplars, optimizing joints requires from the system a full re-factorization of the linear system involved for the weight optimization. Similarly, optimizing weights requires from the system to re-factorize the linear system involved for the joint optimization.

Example results of the weight and optional joint optimization is shown in Figure 6F. A deformation example is shown in Figure 6G. 3 System Initialization

3.1 Weight Initialization

For triangular meshes, weights are initialized using any suitable technique know in the art. For the example illustrated in this document, the technique described in I. Baran and J. Popovic, "Automatic rigging and animation of 3d characters," ACM Transactions on Graphics, vol. 26, ACM 72, 2007, incorporated herein by reference in its entirety. This technique finds the weight vector w.j := (w ₀ ,...,Wjv-i/) ^T for bone j by solving:

where Δ denotes the square Laplacian matrix, and %. _j the indicative function of the Voronoi cell of bone 3 fa ^{G Vor '} ) Χϋ = !). H is a diagonal matrix, where ^{Hii = 1} / \ ^{Vi ~} if the segment between v _l and its closest point on the skeleton p(J) does not intersect the input mesh (the test is accelerated with a Kd-tree), otherwise H _n = 0. Consequently, the closest bone has a strong influence (due to H), but the weights are smoothly diffused over the mesh (due to Δ). Two modifications to this algorithm are presented.

First, support for virtual segments is added. Figure 8A shows a partitioning using only skeleton bones. The zone of influence of the parent bone is very limited although the child bone' s origin is located at the end of the virtual segment. A natural transition near the child's pivot is obtained by making the virtual segments part of the parent bone, thus extending their Voronoi cells as shown in Figure 8B. Figure 8C shows that diffusing cell indicators can result in poor initial weights. The results of the algorithm of the present invention that immediately resolves these ambiguities are shown in Figure 8D.

Second, having disconnected components in the mesh, the linear system (i.e. Equation 7) might become non-invertible (e.g., if a component is invisible from the skeleton). A simple remedy is to set H ^%% — l

ignoring the intersection test. These weights are not of high quality (as shown in Figures 8C and 8D) but serve as a sufficient starting point for the algorithm of the present invention. Note that they do not constitute a local minimum and are improved immediately after the first iteration of the algorithm.

3.2 Bone Infiuence Reduction

Before optimizing the weights, the set is first rendered sparse to improve locality (useful for editing operations) and computational efficiency. Initially, the bone infiuence map B(i) for a vertex i is set to all bone indices; any bone potentially influences any vertex. To sparsify the set of weights per vertex / ^' , a bone index j should be removed from B(i) if weight w _tj is small.

Most prior art approaches enforce sparsity by adding an energy term using the / ₀ (or , or l _p with p < 1) norm involving the variables of the optimization process. Instead, the method of the present invention functions to sparsify the bone infiuence maps prior to the optimization, which has several advantages:

1. The linear system becomes smaller and sparse, making almost interactive rates possible.

It allows adding constraints at any time and providing immediate feedback, which is of utmost importance for user interaction.

2. The topology of the weight maps is easier to control.

3. An artist can use this information to control sparsity and locality. A drawback is that poor initial weights can lead to suboptimal results.

Two important topological properties are maintained during sparsification: (1) Bone topology: From the perspective of bone j, the resulting weight map {w ₇ } should preserve the topology on the mesh (i.e. no extremum is artificially introduced) to make edits consistent; and (2) Vertex topology: From the perspective of vertex / ^' , the set of bones in B(i) should stay fully connected, which is meaningful for the subsequent ARAP minimization described in more detail infra.

In practice, all index pairs (/ ^' , j) are processed in increasing order of the associated weights wy. We remove j from B(J) if: (1) at least M bones still have an infiuence on i (M = 2 in all examples); (2)∑ _έ w _tj stays larger than a threshold t (t := 0.9 in all examples); and (3) no local minimum is introduced (i.e. for all adjacent vertices k for which j is in B(k), w _j is larger than M¾).

After this pruning, the vertex topology is established in a post process procedure. The skeleton is first converted to a graph SG by collapsing all virtual segments. Then, for each vertex / ^' , the minimal spanning tree in each component of SG is found covering the bones in B(i).

As emphasized in the introduction supra, locality and sparsity are ultimately ill defined, and should be driven by the user, which is why the ability to refine these influence maps {B(J)} is provided for, as described in more detail in Section 6.

3.3 Manipulation-Space Sampling

Figure 9A shows an example constraint dialog from the open source Blender application (blender.org). Figure 9B is an example of constraint free sampling and Figure 9C is an example of constraint sampling. To define an exemplar, we start with a random rotation matrix η for each bone j by determining a roll axis and a roll and twist value. Typically, this axis is a random axis orthogonal to the bone and the roll value is chosen between -60 and +60 degrees. The twist is a rotation around the bone axis and is restricted between -10 degrees and +10 degrees. Default constraints are used to avoid extreme deformations, which can lead to the candy wrapper effect, for which it is unreasonable to optimize for ARAP deformations. If the skeleton contains definitions for a roll axis, or restrictions on the angles, these are respected in the construction of η, as shown in Figure 9C. Regarding spines, their base transformation (R _s ) is set similarly sampling bones, while the rotation axis (a) is chosen randomly and the spine rotation angle (Θ) is taken randomly between -60 and +60 degrees as well. For a virtual segment j, we set η to Id.

Next, the global transformation pairs (R _j , 7}) are derived for each segment j to maintain the skeleton' s connectivity. To this extent, all skeleton segments are traversed in a breadth first manner, their global transformation is updated by defining each global translation such that the joint with its parent is preserved after it was affected by the concatenation of all previously encountered bone transformations. Working with local quantities instead of sampling directly is more likely to result in a bias free sampling. Further, skeleton {R,-} constraints are often expressed in local frames, which makes their integration relatively easy.

If the skeleton consists of several unconnected components, each component can be treated in any order. This latter case is rare in industrial applications, as a skeleton is usually defined from a root bone with successive children (leading to a fully connected tree). Nonetheless, the method of the present invention is general enough to handle such special cases. The set of all bones and their transformations finally constitutes an exemplar.

4 Weight and Joint Optimization

In order to optimize the weights, the methods of the present invention express the ARAP energy in terms of weights, by inserting Equation 2 into Equation 6. This leads to a quadratic energy, whose minimization results in weights that lead to mesh deformations that best approximate an as-rigid-as-possible (ARAP) behavior. This energy, however, also depends on various matrices {R(i)}, which represent the linear part of the expected transformation for the exemplar at the vertices. Optimizing for these variables at the same time as the weights cannot be easily done. The method alternates between the matrix optimization {R(J)} (referred to as the local step, since each matrix can be optimized independently, see Section 4.1 infra) and the optimization of the weights (referred to as the global step, since they have to be jointly optimized, see Section 4.2 infra). Additional weight constraints (i.e. Section 4.3 infra) are also introduced, which are efficiently injected into the optimization process, to steer the weight derivation. Finally, it is shown that skeleton joint positions can be injected into the ARAP energy as well (see Section 4.4 infra), allowing the optimization of their location via a similar strategy.

4.1 R(i) Refinement (ARAP Local Step)

To derive R(J) for each vertex and each exemplar, Equation 6 is optimized for 1Ζ{Ϊ) = argmin (£¾ (/, R)

R S T ^ADM ₍₈₎ where Τ ^άία is a set of admissible transformations. In the traditional ARAP case, ^dm := SO(3) (the space of 3 x3 rotation matrices), for which the solution is obtained by projecting

f ^cf≡yi W onto Τ ^άία (e.g., using well-known singular value decomposition techniques).

4.1.1 ARAP for Parameterized Bones

When the bones' length is preserved, the produced deformations should be ARAP. Some of the bone transformations, however, contain stretch. Using the sparsification strategy is sufficient to leverage ambiguities, but optimizing for rotations on stretched transformations can lead to artifacts. A strategy to counter this is to constrain the singular value σ _¾ (with associated singular vector v¾ i.e. Cov, = U∑V ^T and v is the k ^th column of V), based on an analysis of the stretch induced by the bones in the exemplar.

Intuitively, if the bones influencing v _l are stretched, its neighborhood should be stretched as a result, by an amount contained within the range of the stretch values of the bones. Given a bone

j

j <≡£(/ ^' ) with Jacobian J at point v _h ^a k · ^~ I ^Vk \ is computed, the stretch induced by bone in this direction (if the bone is rigid, then its Jacobian is a rotation and the induced stretch is 1). We

j

then take J ^' G -B W ^%3 ^ thus blending the stretch values induced by the various bones by the weights {wy} . Finally, R(i) = £/diag(oi, σ ₂ , C3)V ^T .

This construction falls back onto the traditional solution if all bones are rigid (i.e. it implies Ok = 1). Note that no ARAP energy was defined (or adapted) in the literature for anisotropic stretch. Unlike in the traditional rigid case, it is difficult to estimate what values of stretch on the mesh are appropriate, given stretchable controls as input, and no error measure exists for such deformations. The strategy of the present invention was designed to be not only intuitive, but also more efficient than optimizing for rotations, for similarities, for arbitrary matrices (i.e. remaining oblivious to the expected stretch based on the bones), or simply bounding the singular values by the stretch of the bones. It is noted that strategies other than the method of the present invention result in disturbing artifacts and suboptimal optimizations. The results of optimizing with highly stretched-bone exemplars (σ<≡[0.5, 4.0]) are shown in Figure 10, namely characters 160, 162, 164, 166, 168, 170, and 180, 182.

4.1.2 A Note on Jacobians

For a parameterized bone with transformation given by Equation 3, its Jacobian at point p with parameter u(p) is given by

J _p =

Hence, one needs to compute the gradient V ^¾ In this document, a linear parameterization is sued, which is defined as a field in . This parameterization, however, is only weakly differentiable at 0 and 1. Additionally, parameterizations are generally defined as a function on the mesh only (e.g., hand-painted, or resulting from a diffusion equation on the mesh), and their

→

gradient does not have a close form expression. For these reasons, the gradient V ^M¾ i _s estimated at vertex i as

V«i = argmin ∑ e _ik - (u(v _k ) - u(vi)) | | ² ,

sent ³ feevi (i) (10)

The derivatives of Ri _oc (w) and _oc {u) are given by:

-¾oc ( ^¾ ) =θ cos(¾#)a _{[X ]} + # sin(¾#) (a - a ^T — Id)

11)

jjr D _= ¾ x D £ IR,^

noting a[x] the 3x3 matrix such that ί ^χ -Ι '

4.2 Weight Optimization (ARAP Global Step)

How to produce an initial set of weights and how to compute an optimal set of transformation matrices {R(J)} from the weights have been described supra. Next, the global step; optimizing the weights while keeping the transformations constant will be described. Let bone influence for vertex / ^' , which is thus influenced by N, bones. Let w be the vector of length l ^w >, concatenating the weights w _tj , which we want to solve for, ordered by increasing indices / and j, but ignoring the first weight of each vertex:

W = _b l , · · · , ¾0-l , %l , - , ^Λ χ -l , · · · ) ₍₁₃₎

First consider a single exemplar (for readability we avoid indexing the various quantities). Defining the transformation of vertex i by the j influencing bone,

Equation 2 can be rewritten as:

N _t -1 N _t -1 N _t -1 iV,-l

i ^{=1 1} (14) 3 I w I

Note that matrix £ ' is sparse and only contains entries organized in a block for vertex / ^' . Based on this expression for a single vertex, an expression of a transformed edge can be deduced e _ik - _ΐ¾ · w + i _fc , _{where ί¾} := Φ¾-Φ. _αι ι ■= {Φ ^~ Φ _ί ) _,

This expression can be inserted into the equation for ARAP energy (Equation 6) to obtain an expression in the weights. Given an exemplar ex, the following is obtained: (£(w, TV) = w ^T · Q ^A (ex) · w - 2Q ^B (ex) ^T · w + const, with

(3 ^Α (βχ) := ^ Λ, λ^ ^ - ^

iev fceVi (i)

Q ^B (ex) :=

A flow chart illustrating the weight optimization method is shown in Figure 1 1. First, the

ARAP energy function ^( ^w> ^) i _s defined in weight space (as described above) (step 140). The method then adds Neumann and attach constraints (see section 4.3) to the energy (step 142). The method then performs a one-step optimization of w (i.e. the LBS weights) (step 144). The method then performs a one-step optimization of {R(i)} (step 146). The method repeats with step 144 until the desired convergence is achieved (step 148).

A flow chart detailing the one-step optimization of the weights is shown in Figure 12. First, the weight positivity constraints are created (see Positivity constraints in section 4.3) and Q ^A is updated (step 150). Then, Q ^B and w are updated to minimize ^( ^w ' ^) (step 152).

A flow chart illustrating an overview of an example LBS weight optimization method is shown in Figure 1 1. First, the weight constraints are created and Q ^A is updated (step 140). The, QB and w are updated to minimize ^ ( ^w ' (step 142). The per-vertex transformation matrices are then optimized (step 144). The weight optimization is the iterated until the desired level of convergence is achieved (step 146).

A flow chart illustrating an example ARAP optimization method is shown in Figure 12.

First, the ARAP energy function ^ ( ^w ' is defined (as described above) (step 150). The method then optimizes / for w (i.e. the LBS weights) (step 152). Note that in one embodiment, this step requires the minimization of a quadratic energy with the weights as variables (i.e. invert a linear system to the least-squares sense). Once the weights are optimized, the method optimizes for R(J) (step 154). Note that this step can be performed for each vertex separately. The method repeats with step 152 until the desired convergence is achieved (step 156). 4.2.1 Multiple Exemplars

For a reasonable deformation behavior, several exemplars are involved (preferably a few tens or hundreds) to well cover the manipulation space. Fortunately, adding exemplars does not induce substantial memory costs since all matrices (Q ^A (ex)} have the same pattern; the ARAP energy for all exemplars in weight space can be expressed as

(£(w, TV) := w ^T · Q ^{A ■} w— 2Q ^{B T ■} w + const with Q ^{A : =} ∑ex Q ^A ( ^ex ) ^and Q ^{B '■} = ∑ _ex Q ^S (ex) _{The optmia} i weights under the linearity constraint are thus given by w* = argmin (S(w, TV)— Q ^A ^ ^■ Q ^B

(17)

4.3 Weight Constraints

In principle, the optimization process is complete, but by introducing additional constraints, it is possible to steer the optimization to improve quality. These weight constraints are defined in form of a supplementary error term added to ^( ^w > ^):

<£(w, n) <r- <£(w, n) + ∑ ^c ^ Wij I

(i,j,ii>j _j ) SConstraints (18) where 3 is a value, which is softly enforced on weight w _i} and c _l is a scaling factor to control its impact. In all examples presented herein, c _l := 100.BDD ² .A(i).#{ex}, where BDD is the bounding box diagonal (to ensure that value ranges are compatible), the vertex weight A(i) (to take the vertex density into account), and the number of exemplars #{ex}(to keep the constraints independent of the manipulation-space sampling).

Attach constraints are used to maintain a strong attachment for vertices whose initial weight estimate for a bone is maximal. Especially extremities of a skeleton that would otherwise be ignored; attaching vertices only to a parent bone would have a similar rigidity advantage as attaching all vertices to a single bone. The initial weight estimates (before the first iteration) can be used to identify such important skeleton connections; we set ^l 3 if (1) w _lj is a strict local maximum at i with respect to the neighboring vertices (because a single attachment is sufficient); (2) Wjj > 0.5 (because only strong influences should be considered); and (3) j is visible from i. Note that, for a volumetric weight optimization, it means setting these constraints on the bones.

Neumann constraints are used to ensure that weights of a bone j fade out smoothly where the influence of j disappears. Consequently, we set ^ if a neighboring vertex of i is not influenced by bone j. Note that we call it a Neumann constraint because it enforces a null gradient on the boundary.

Positivity constraints are used to ensure that the resulting weights satisfy the positivity constraint. In practice, we achieve this goal by adding after each iteration a constraint with

^^ Q

t ^J , if a weight w _tj becomes negative and is a local minimum. In this way, negative weights are drastically reduced and hard constraints are avoided, while introducing only a sparse set of constraints. In all results resented herein, the resulting performance overhead is barely noticeable when updating the factorization.

Mixed-weight constraints are optional and, if requested by the user, are used to bound areas

Wij

of the mesh to following other strategies than ARAP by setting ^J to the desired weight value.

Note that adding and removing weight constraints can be realized efficiently because a re- factorization of matrix is unnecessary. Using low-rank Cholesky factorization updates the computation is significantly accelerated by several orders of magnitude.

4.4 Joint Optimization

Artists tend to produce skeletons reflecting the desired degrees of freedom to best serve their animation needs, but fine-tuning operations should not be required. Consider a skeletal chain inside a cylinder (e.g., the arm of a character), here, the bones should lie close to the medial axis to minimize stretch. Similarly, joints (i.e. vertices connected to at least two segments) would be best placed at the centers of the intended articulations, which can also be cumbersome to do. This section presents an automatic optimization of the skeletal joints, which in turn leads to better skinning results as well.

The motivation for joint optimization is that it is fairly simple enough to place the joints for fingers, elbows, etc. but it is much more challenging to correctly place the joints for shoulders, hips, etc. The position of the joint defines a pivot point and has influence over the rotation and translation applied by the bones to the mesh vertices. It therefore has influence over the final transformation of the mesh. The present invention provides a mechanism to optimize the placement of the joints, such as the corresponding skeleton transformations (for given LBS weights), that results in ARAP transformations of the mesh (i.e. that minimize the ARAP energy function). Thus, joint optimization depends on (1) LBS weights, and (2) given skeleton transformations for which the mesh reconstruction is optimized.

If the rotation of the bones is maintained, a linear relationship can be defined between the joint positions and the translation of the bones. This is achieved by the constraint that the bones are connected at the joints when they are rotated. The rotation R _j of bone j is fixed and the translation 7} is allowed to vary. The joint positions can be inserted in the place of 7} in the energy expression, e.g., the ARAP energy function described supra, which defines the quality of the deformation of a mesh. Note that any expression for the energy function can be used as the joint optimization is not limited to using only the ARAP energy expression described herein. The joint positions are optimized in such a way that improvement of the quality of the mesh transformation is now possible. The inputs to the algorithm are the LBS weights (fixed) and the skeleton transformations from the manipulation space (rotations are fixed, translations are optimized).

When changing joints, the essence of the exemplars are retained; defined by rotations of the bones and additional quantities (σ, 6>, a) for spines. In Section 3.3 discussed supra, the bones' translations were derived by marching on the skeleton while ensuring that the bones stayed connected at the joints. This construction can be expressed in terms of a linear dependency linking the joint positions and the bone translations, allowing the joint positions to be plugged into the ARAP energy and thus derive joint displacements {½} minimizing the ARAP energy.

A flow chart illustrating an example joint optimization method of the present invention is shown in Figure 13. First, a linear relationship is defined between joint positions and the translations of bones (step 200). The method then fixes Rj while allowing 7} to vary (step 202). The method then replaces 7} with joint positions in an energy function (e.g., energy entity, ARAP energy function, etc.) (step 204). Then the joint positions are optimized such that the quality of the mesh transformations is improved (i.e. the energy decreases) (step 206). The details of this method are described in more detail infra.

4.4.1 Algebraic Exemplar Construction

In one embodiment, the goal is to express bone translations in terms of joint displacements. Thus the joints are adapted and the other parameters (e.g., rotations) of the exemplar are maintained. First a pair of rigid bones (/ ^' , j) connected by a joint k and a displacement dJ are investigated, before addressing different components of the skeleton. As the joint is located between two skeletal segments, applying either one of their transformations on the joint should yield the same result. Mathematically, this condition implies the following:

RriJk+dJ _k ) + (Tr+dTD = R iJk+dJ _k ) + {T + ^dT D ₍₁₉₎

r nex fTiexi r pex

Observing that the skeleton transformations \ ^Λί ' ^J * J and i ^ ' i _{in e} x were constructed similarly, to maintain connectivity (see

Section 3.3 supra), the following is obtained:

We note this joint constraint JointConst(i, j, k) ^ex .

Note, that if spines are used, this construction is more complicated. For a spine s with extremities (e ₀ , e _\ ) and deformation parameters (R _s , t _s , σ, 6>, a) in the exemplar, the deformation of extremity e _o will be <¾ = Hs · en + t _s (similar to before) but the deformation of extremity e _\ will _be ei = R _s Rot(a, Θ) ^■ ei + R _S A{1) ^■ e ₀ + R _S B{1) - ei + t ( _{by rewr} i _t i _{ng ¾c} ( _M ) =· A(u) e ₀ +

P i

B(u) e , see Equation 5). In short, the fact that ¹ depends both on e ₀ and on e ₁ changes the right side of JointConst(i, j, k† ^x in case bone i (or j) is a spine and joint k is its positive extremity (i.e. e\). JointConst(i, j, k† ^x then contains not only products of matrices by ½, but also products of matrices by dJr, joint k' being the negative extremity of the spine (i.e. e ₀ ). Otherwise, the construction remains the same and valid. i<9T ^ex i

If the skeleton is not fully connected, joint constraints are insufficient to express ^{L J J} in terms of {½}; assume that a constant displacement is added to every skeletal segment of a connected component, then the joint constraints would still be preserved. Consequently, auxiliary

^ex

variables are introduced, one for each connected component c, which reflects an average component displacement. The resulting component constraints, which are denoted ComponentConst(c) ^ex , are given by:

ϋ omponent c

Using joint and component constraints, a linear relationship is defined to express the change of the skeletal segment translations ^ for a set of joint displacements {½} and average component displacements χ ₀ this extent, each connected component c of the skeleton was processed successively. Each joint k in c is then processed successively as well. Let {s ₀ ,...,s _n } be &'s adjacent skeletal segments. A constraint JointConst(s ₀ , s k) ^ex for all > 0 is then added. Note that having each constraint rely on s ₀ is irrelevant because the expression of _{m terms 0} f

{dJ _k } and *- ^c . is already unique with the linear system. Once all joint constraints of c are collected, the component constraint ComponentConst{c† ^x is added and processing proceeds with the next connected component.

The resulting set of equations can be written in matrix form as follows:

ex

where dJ := (5J ₀ , . .. ,5J„) ^T and are the concatenations of the displacement variables for the n joints and m connected components of the skeleton. The entries of

a simple structure, which becomes apparent when reordering the joint indices. If it is assumed that they are sorted such that joints are grouped by connected components in the skeleton, both matrices become diagonal block matrices, as shown in blocks 190, 192, 194 of Figure 14. This property makes it easy to invert M. In the following, this joint ordering is assumed.

Given the above observations, a linear relation between (dJ, dC) and 3T ^ex can be produced as follows:

where dT ^ex is a matrix of skeletal-segment translations for an exemplar, M is a matrix describing the topology of the skeleton, Mf ^x is a joint constraint matrix, M _Q ^X is a component constraint matrix, dJ is a concatenation of displacement variables for joints of the skeleton and dC is a concatenation of displacement variables for connected components of the skeleton.

One should not assume that the above equation is a one-to-one relationship between joints

1VT ^— ^ T T ^e:x " T T ^e:x " ^

and bones. In general, ^{' J} ' ^c ' is not invertible. Nonetheless, Equation 23 allows us to correctly adapt the translations of the provided exemplar to maintain its original rotations despite the additional joint displacement.

4.4.1.1 Multiple Exemplars

For each exemplar, following the case of a single exemplar, one auxiliary variable is added for each connected component, while the joint displacements are shared and globally defined. In consequence, each exemplar enlarges ^M c ^x to reflect all bone translations and all average component displacements over all exemplars. Block 194 of Figure 14 illustrates the extended form of i ^± v ^VJ r- ^e c ^x and the corresponding displacement vector, which is similarly extended to hold the average component displacements over all exemplars.

4.4.2 Skeletal Joint Optimization (ARAP Global Step) Expressing the bone displacement via the joint displacement, allows us to link it to the mesh. Injecting into the ARAP energy term, makes it possible to measure the impact of joint

Q—ex

displacements on the ARAP energy. We first observe that 5T ^ex leads to an offset ^OVi for the LBS of a vertex i (Equation 2):

R _j (y,) does not appear in the previous expression because modifying the position of the joints or changing the translation part of the bones (either the standard bones or the translation of the base of the spines) does not change it.

For standard bones, the change of the translation applied to vertex i by bone

^■ > ' ^■ > ., and one can use Equation 23 to express ³ ' in terms or (dJ, dC) . For a spine s with extremities (e ₀ , e ) and deformation parameters (R _s , t _s , σ, Θ, a) in the exemplar ex, more care is needed. Since the transformation induced by the spine is ^ ^ R _s Rioc(u(p) ) ^■ p + R _s -ti _oc (u(p) ) + i _{S j t} he change of the translation applied to vertex _/ by

Ί (dT ^e (v ) )

bone ^{J s} ^ ^% ' ^} is not simply dt _s , because t _\oc (u) depends on e ₀ and e _\ as well. As before, we rewrite _oc (u) =: A(u) e ₀ + B(u) e leading to ^< 9T _s ^ex ( ⁱ ) = _{Using Equation 2} 3 to express dt _s in terms of dJ,dC) , i ^% > can be expressed in terms of (dJ, dC) for spines (and therefore for twistable and stretchable bones) as well. ex

Consequently, we can also compute the effect on an edge and obtain again an offset de , which is given by the following:

9¾

where ^(l,fc) is a horizontal vector of block matrices.

Combining this result with the ARAP energy (Equation 16) yields the following:

where E is the energy entity, dj is a concatenation of displacement variables for joints of the skeleton and dC is a concatenation of displacement variables for connected components of the skeleton, ex represents an exemplar, R(i) ^ex is a matrix constraining the transformation of the 3D edges incident to vertex i in exemplar ex, V are mesh vertices, is the set of vertices connected to vertex / ^' , A _t is an input vertex weight and X _ik is an input weight for directed edge e¾.

This last equation finally expresses the ARAP energy in terms of (dJ,dC) ^T . Using a minimization of the corresponding quadric, we can thus solve for an optimal skeletal joint placement. It is noted that for some complex configurations, this energy is not always positive definite, so we regularize and minimize: diagonal matrix where the z ^th block penalizes large offsets for the z ^th variable. The quadric to minimize for the joint positions is: dJ dj dj

dc Q ^A j dc 2Q? \dc + const

(27) with

In the implementation described herein, joint tangential displacement is penalized more severely than joint non-tangential displacement and connected component displacements. In another embodiment, an attachment term is added to the quadric to restrict the initial joint positions. Further, the user can tune relative joint displacements, by providing a joint-material scalar function, influencing the norm of the z ^th block of . Note, that after each solver iteration, each exemplar ex needs to be updated (the translations of the bones) using Equation 23.

QB

Nonetheless, the user is free to refine the various matrices {R(z) ^ex }, the linear part ^ J, or refine the joints without changing the factorization of o ^A . As already mentioned, however, changing the joint positions results in an un update of the skeleton deformation exemplars. It is thus required to update the matrix Q ^A and to re-factorize it before further optimizing the weights again.

5 Algorithmic Details

5.1 Vertex and Edge Weights

While A _; and λ¾ are often defined via Voronoi-cell areas and cotangent weights, such weights lead to severe artifacts because negative values can occur for triangles exhibiting obtuse angles and the ARAP minimization would maximize the rigidity error of the concerned edges. Instead, the initialization of the method of the present invention uses barycentric cell-area weights, which guarantee initial positive values. Further, their sum results in the total mesh area, which can be seen as a discretization of a continuous formulation and increases robustness.

5.2 Local Maxima and Positivity

Other than weight constraints for negative local minima (i.e. penalized during optimization; see Section 4.3), we do not strictly ensure positivity in the system because negative weights are mostly avoided. They would produce distorted transformations, which contradict the goal of the final weights to opt for ARAP transformations. Therefore, performance is improved drastically. Figures 15A and 15B show this observation. Negative weights (depicted in oval 211) might occur for a small number of exemplars (e.g., 8, character 210) but are drastically diminished when a larger number of exemplars (e.g., 32, character 212) is used. Note that, for illustration purposes, the examples use no weight constraints.

Similarly, local maxima in the weights can lead to serious artifacts and prior art techniques propose to detect and suppress non-global extrema (i.e. constrain the value to 0 or 1). In the method of the present invention, although small local extrema are observed that arise when optimizing for ARAP transformations, a one-step Laplacian filtering (including a re-normalization) after each optimization iteration is sufficient to avoid artifacts. This result illustrates that the ARAP -transformation optimization of the present invention provides previously artificially- enforced properties.

5.3 Vertex-Clustering Acceleration

Following Section 4.1, for each exemplar and iteration, updating R(J) requires a large number of costly 3 x3 matrix singular value decompositions to be performed per vertex. Nonetheless, the transformations should ultimately be smooth, which implies that the matrices will vary smoothly as well. Consequently, this step can be accelerated using vertex clustering.

In order to avoid clustering effects in the output, a set of clusterings is computed and each exemplar is associated with a random clustering (e.g., 10 clusterings on the positions, with a number of clusters taken randomly between 1000 and 5000). To obtain uniform clusterings despite anisotropy in the input mesh, a variant of k-means++ is used, and vertex v _l is selected as seed s„ with relative probability ^area ( ^v i ) * ^ i ^s J }j <n ) Characters 220, 222, 224 in Figures 16A, 16B and 16C show clusterings of various sizes that are uniform, despite the anisotropic vertex distribution.

For a given exemplar and clustering, the transformation matrices for cluster cl is estimated as follows: TZ(cl)— argmin _J Ai \ \ eik — R ^■ eik

ReT ^adm

(29)

Specifically, the cluster covariance is computed as and the stretch o _k in direction v _k is set as

^(J k = ∑ ∑ AiWij \ Jij - v _k \l ∑ ∑ iW-

(J _tj being the Jacobian of bone j at point v, in the exemplar). Finally, the cluster' s matrix is set to R(c/)=i7diag(o ₁ , σ ₂ , o ₃ )V ^T , and each vertex i in the cluster cl is associated with this matrix, i.e. R(i) = R(cl)Vi≡el.

6 Skinning Tools

The method of the present invention is operative to respect linearity and positivity constraints. The desired locality, however, is often subjective. Preferably, it is based on user preferences, for which in one embodiment several tools are provided in the form of brushes, which allow the user to easily indicate additional constraints interactively. Note that in the examples presented herein, these interactions were only applied where stated, most results shown were automatically produced without use of any tools. The examples where an interaction was applied typically represent cases for which other methods completely fail.

One tool comprises a bone-influence brush that is used to modify the {B(i) after sparsification. The user selects a bone j and then increases/decreases its influence by adding/removing j to/from the B sets. This enables the locality of the bone influence to be easily adjusted.

Another tool comprises weight-constraint brush that is used to add weight constraints (see Section 4.3). The weight-constraint values can be taken from different skinning techniques or set to zero/one to reduce/increase certain bone influences.

A third tool comprises a wire-edge brush that functions to link disconnected components, which are common in many artist-designed 3D models. These elements, even when modeled independently are usually intended to stay in close proximity, but without a spatial link, the LBS deformations might separate them. An example of a dog is shown in Figures 17, 18 A, 18B, 18C, 18D, and 18E. In Figure 17, the dog 230 has teeth 232 and wire edges 234 added in order to create a connection between the teeth and the muzzle. In Figure 18 A, the skeleton of the dog 240 is shown as well as the weights created using the present invention. Note that each bone is associated with a different tone or shading, and the shades on the mesh indicate the blending of the various bones' influence using the weights. Figure 18B shows results of the dog 242 using the method of the present invention. The area 246 of the head is shown enlarged in Figure 18D where the dog 250 has all its teeth intact. Figure 18C shows results of the dog 244 using prior art techniques. Note that the dog's teeth 247 are not in its mouth where they should be. Area 248 of the head is shown enlarged in Figure 18E which shows teeth missing from the mouth of the dog 252 as well as the non-rigidly deformed muzzle.

This brush allows the user to add these links via wire-edges using mouse clicks. Wire edges i→j connecting vertices i and j in the ARAP energy are added (234, Figure 17) with the following weights:

The goal is to establish a soft connection between the chosen two vertices, i.e. a portion of the weights adjacent to i is attributed to the new edges, while ensuring that their sum does not exceed half the sum of the original weights, thereby prioritizing the original connectivity.

7 Example Results

7.1 Models

Drawings of a lemur illustrating the results using the methods of the present invention are shown in Figures 19A, 19B, 19C, 19D and 19E. The skeleton and mesh of the model 260 is shown in Figure 19A while the transformation of the body using the methods of the present invention is shown in Figure 19B. A portion 264 of the resultant transformation 262 is shown enlarged (270) in Figure 19D. Transformations using prior art methods are shown in Figure 19C. A portion 268 of the resultant transformation 266 is shown enlarged (272) in Figure 19E.

Drawings of an ogre illustrating the results using the methods of the present invention are shown in Figures 20A, 20B, 20C, 20D, 20E, 20F, 20G and 20H. The skeleton and mesh of the full body model 280 is shown in Figure 20A along with the LBS weights once again depicted by blending shades associated with the bones. The transformation of the body using the methods of the present invention is shown in Figure 20B. The head portion 286 of the resultant transformation 284 is shown enlarged (294) in Figure 20E. The lower torso portion 285 of the resultant transformation 284 is shown enlarged (298) in Figure 20G. A portion of the skeleton and mesh of the head region 292 is shown in Figure 20D. Transformations of the body using prior art methods are shown in Figure 20C. The head portion 290 of the resultant transformation 288 is shown enlarged (296) in Figure 20F. The lower torso portion 289 of the resultant transformation 288 is shown enlarged (300) in Figure 20H.

Note that to illustrate practicality, most models used were challenging, produced by artists, and provided via Blendswap (blendswap.com). They exhibit disconnected components (e.g., dog, dinosaur), tiny features, non-manifold vertices (the dinosaur), boundaries and very elongated triangles, self-intersections (e.g., the dog) and complex topology. The skeletons used are relatively complex, partially disconnected, with various bones types, and scales (i.e. from main limbs to fingers) and may include deformation constraints.

Except for the dog example, all weights were computed fully automatically. For the dog, wire-edges were added (described supra) to connect the teeth to the jaw and the bone-influence brush was used in order to correct the influence maps which were incorrect around the muzzle, as the input heat-diffusion weights were of poor quality (see Figure 8C). The mixed-weight brush was used on the tip of the nose, to enforce a strong influence of the bone there. It results in an apparent local stretch, which was used to illustrate that artistic choices remain possible. The user interaction took less than one minute.

7.2 Timing

An example implementation of the present invention was sufficiently fast enough for almost-interactive work sessions. For all models, preprocessing took 5 to 20 seconds, while each optimization iteration took 0.5 to 3 seconds. Joint optimization was slightly more costly, depending on the topology of the skeleton. For all examples, it took 5 to 10 seconds for system factorization and 1 to 4 seconds per iteration. Approximately 20 iterations were performed.

7.3 Volumetric Structures

Relying on volumetric structures poses a significant challenge in practice. For example, not all scenes could be used with bounded biharmonic weights (BBW). The necessary tetrahedrization (using TetGen for an exact input-face reproduction and CGAL for an approximate one) failed on several examples.

To illustrate the fundamental issue, consider the dog example above. The teeth were modeled independently of the mouth, a common choice of artists. Their intersection with the mouth and tongue would make an animation impossible, as a watertight tetrahedrization would sew the mouth shut. It is conceptually impossible to represent the mesh as the 2-boundary of a volume and not because of non-manifold structure. No prior art mesh-repairing technique can solve this problem. The wire-edge brush of the present invention, however, connects these entities and ensures a correctly deformed output (Figures 17, 18 A, 18B, 18C, 18D and 18E). The method of the present invention is general enough to deal with these complicated cases and delivers high quality skinning. 7.4 Comparison With Bounded Biharmonic Weights (BBW)

For most meshes, a tetrahedrization can be obtained only after manually tuning the surface and the resulting tetrahedrization, which could take several minutes per model. These changes, however, necessarily modified the input mesh structure (causing issues for textures) or the skeleton's geometry (which should only be driven by the artist's intentions, not by avoidance of issues). Still, even if a tetrahedrization could be produced, several numerical issues arise due to fine structures, leading to problems in the BBW solver.

The methods of the present invention operates on meshes and volumes. Figures 21A, 21B, 21C, 21D, 21E and 21F show example results of how the methods described herein can improve upon BBW weights, which were used here to initialize the weights. The BBW robustness issues are reflected by the lost influence of the index fingertip (314/312 compared to 324/316) of the hand 310 versus the hand 320. Section 318 of the BBW example is shown enlarged as 326 in Figure 21C. Section 322 of the optimized results using the present invention is shown enlarged as 330 in Figure 2 IE. The tiny features led to small tetrahedra causing numerical issues, even after enforcing the skeleton to be part of the tetrahedrization and ensuring its containment within the mesh. These points illustrate the practical difficulties, which arise even for standard models. Using weight constraints (see Section 6), it is possible to recover the missing influence (324) after a few iterations of the algorithm of the present invention. This example additionally illustrates the usefulness of virtual segments, which make the bone influences change precisely at the joints of the palm, which better reflects the user intention, e.g., see the rotation of the thumb in Figures 2 ID (328) and 2 IF (332). It is noted applying the method to the surface mesh automatically leads to high-quality skinning even without any user intervention.

7.5 Disconnected Skeletons

The methods of the present invention support highly disconnected skeletons such as shown in Figures 22A, 22B and 22C. Here, the constraints of the skeleton 340, 342 (e.g., fixed bone length, etc.) are not enough to create skeleton deformation exemplars that are pertinent to steer the weight optimization. For example, taking one arm and moving it by 100 meters will still preserve all skeletal constraints, while introducing a high amount of stretch. By alternating between weight and connected-component optimizations, the lost constraints are progressively recovered and the incorrect exemplars are mapped to a set of useful exemplars to train ARAP weights. For illustration purposes, joints were not optimized, but only the average displacement of the connected components. Example optimized weights and deformations 344, 346 are shown in Figure 22B while example output weights 348 are shown in Figure 22C.

7.6 Joint Optimization

The joint optimization method of the present invention supports users by placing joints at adequate locations, which naturally resemble articulations, even on cases where the topologies of the mesh and the skeleton do not match. Figures 23 A, 23B and 23C show how well the correction performs. The skeleton 362 does not have to be placed perfectly in the interior of the mesh. The joint optimization does not rely on a special type of weights. It can be used in conjunction with any type of weight definitions (not only those described supra) and will optimize the skeleton accordingly. For all comparison examples shown, optimized skeletons for the competitors were used which improved their deformation. The result 364 of five iterations is shown in Figure 23B while before and after results 366 are shown in Figure 23 C.

7.7 Parameterized Bones

It is noted that the methods of the present invention are compatible with parameterized bones (see Section 1) and can generate weights, which typically cannot be obtained without knowledge of the user's intent. For example, defining a spine with standard bones, an artist would typically use many bones and weights that lead to a banding pattern. While small rotations might mimic the human anatomy, large rotations result in a high stretch and implausible transformations regardless of the weight definition. As a result, the created weights are sub-optimal, and the influence of many bones is lost (see Figure 24C). Using a spine deformer (see Figure 24D), the method of the present invention generates high-quality weights (see weight maps in Figure 24D). The spine can be converted into many bones in a post process (see Section 1 and Figure 24E), leading to the expected banding pattern. Note, that the upper-bone weights of the torso blend naturally with the those of the arms and neck.

Thus, the systems and methods of the present invention provide a practical, robust, fast and high-quality skinning solution, having wide applicability and capability of handling numerous complicated cases that are too difficult or impossible for prior art solutions to handle. The system and methods operate to sample the space of possible deformations of a skeleton resulting in meaningful weights, i.e. that minimize the ARAP energy. Furthermore, motion constraints, which are often available or easy to define, are naturally integrated. While the example results shown herein illustrate that the techniques of the present invention achieve good automatic solutions for various cases, skinning tools to resolve ambiguous situations are also provided. The resulting constraints are used for the optimization process, which makes it possible to apply these user annotations coarsely with quick interactive feedback.

8 Computer Embodiment

As will be appreciated by one skilled in the art, the present invention may be embodied as a system, method, computer program product or any combination thereof. Accordingly, the present invention may take the form of an entirely hardware embodiment, an entirely software embodiment (including firmware, resident software, micro-code, etc.) or an embodiment combining software and hardware aspects that may all generally be referred to herein as a "circuit," "module" or "system." Furthermore, the present invention may take the form of a computer program product embodied in any tangible medium of expression having computer usable program code embodied in the medium. The invention may be described in the general context of computer-executable instructions, such as program modules, being executed by a computer. Generally, program modules include routines, programs, objects, components, data structures, etc. that perform particular tasks or implement particular abstract data types. The invention may also be practiced in distributed computing environments where tasks are performed by remote processing devices that are linked through a communications network. In a distributed computing environment, program modules may be located in both local and remote computer storage media including memory storage devices.

Any combination of one or more computer usable or computer readable medium(s) may be utilized. The computer-usable or computer-readable medium may be, for example but not limited to, an electronic, magnetic, optical, electromagnetic, infrared, or semiconductor system, apparatus, device, or propagation medium. More specific examples (a non-exhaustive list) of the computer- readable medium would include the following: an electrical connection having one or more wires, a portable computer diskette, a hard disk, a random access memory (RAM), a read-only memory (ROM), an erasable programmable read-only memory (EPROM or flash memory), an optical fiber, a portable compact disc read-only memory (CDROM), an optical storage device, a transmission media such as those supporting the Internet or an intranet, or a magnetic storage device. Note that the computer-usable or computer-readable medium could even be paper or another suitable medium upon which the program is printed, as the program can be electronically captured, via, for instance, optical scanning of the paper or other medium, then compiled, interpreted, or otherwise processed in a suitable manner, if necessary, and then stored in a computer memory. In the context of this document, a computer-usable or computer-readable medium may be any medium that can contain or store the program for use by or in connection with the instruction execution system, apparatus, or device.

Computer program code for carrying out operations of the present invention may be written in any combination of one or more programming languages, including an object oriented programming language such as Java, Smalltalk, C++, C# or the like and conventional procedural programming languages, such as the "C" programming language or similar programming languages. The program code may execute entirely on the user' s computer, partly on the user' s computer, as a stand-alone software package, partly on the user' s computer and partly on a remote computer or entirely on the remote computer or server. In the latter scenario, the remote computer may be connected to the user' s computer through any type of network, including a local area network (LAN) or a wide area network (WAN), or the connection may be made to an external computer (for example, through the Internet using an Internet Service Provider).

The present invention is described below with reference to flowchart illustrations and/or block diagrams of methods, apparatus (systems) and computer program products according to embodiments of the invention. It will be understood that each block of the flowchart illustrations and/or block diagrams, and combinations of blocks in the flowchart illustrations and/or block diagrams, can be implemented or supported by computer program instructions. These computer program instructions may be provided to a processor of a general purpose computer, special purpose computer, or other programmable data processing apparatus to produce a machine, such that the instructions, which execute via the processor of the computer or other programmable data processing apparatus, create means for implementing the functions/acts specified in the flowchart and/or block diagram block or blocks.

These computer program instructions may also be stored in a computer-readable medium that can direct a computer or other programmable data processing apparatus to function in a particular manner, such that the instructions stored in the computer-readable medium produce an article of manufacture including instruction means which implement the function/act specified in the flowchart and/or block diagram block or blocks.

The computer program instructions may also be loaded onto a computer or other programmable data processing apparatus to cause a series of operational steps to be performed on the computer or other programmable apparatus to produce a computer implemented process such that the instructions which execute on the computer or other programmable apparatus provide processes for implementing the functions/acts specified in the flowchart and/or block diagram block or blocks.

The invention is operational with numerous general purpose or special purpose computing system environments or configurations. Examples of well-known computing systems, environments, and/or configurations that may be suitable for use with the invention include, but are not limited to, personal computers, server computers, cloud computing, hand-held or laptop devices, multiprocessor systems, microprocessor, microcontroller or microcomputer based systems, set top boxes, programmable consumer electronics, ASIC or FPGA core, DSP core, network PCs, minicomputers, mainframe computers, distributed computing environments that include any of the above systems or devices, and the like.

A block diagram illustrating an example computer processing system adapted to implement the electronic catalog system of the present invention is shown in Figure 25. The exemplary computer processing system, generally referenced 410, for implementing the invention comprises a general purpose computing device 411. Computing device 411 comprises central processing unit (CPU) 412, host/PIC/cache bridge 420 and main memory 424.

The CPU 412 comprises one or more general purpose CPU cores 414 and optionally one or more special purpose cores 416 (e.g., DSP core, floating point, etc.). The one or more general purpose cores execute general purpose opcodes while the special purpose cores executes functions specific to their purpose. The CPU 412 is coupled through the CPU local bus 418 to a host/PCI/cache bridge or chipset 420. A second level (i.e. L2) cache memory (not shown) may be coupled to a cache controller in the chipset. For some processors, the external cache may comprise an LI or first level cache. The bridge or chipset 420 couples to main memory 424 via memory bus 420. The main memory comprises dynamic random access memory (DRAM) or extended data out (EDO) memory, or other types of memory such as ROM, static RAM, flash, and non-volatile static random access memory (NVSRAM), bubble memory, etc. The computing device 411 also comprises various system components coupled to the CPU via system bus 426 (e.g., PCI). The host/PCI/cache bridge or chipset 420 interfaces to the system bus 426, such as peripheral component interconnect (PCI) bus. The system bus 426 may comprise any of several types of well-known bus structures using any of a variety of bus architectures. Example architectures include Industry Standard Architecture (ISA) bus, Micro Channel Architecture (MCA) bus, Enhanced ISA (EISA) bus, Video Electronics Standards Associate (VESA) local bus and Peripheral Component Interconnect (PCI) also known as Mezzanine bus.

Various components connected to the system bus include, but are not limited to, nonvolatile memory (e.g., disk based data storage) 428, video/graphics adapter 430 connected to display 432, user input interface (I/F) controller 431 connected to one or more input devices such mouse 434, tablet 435, microphone 436, keyboard 438 and modem 440, network interface controller 442, peripheral interface controller 452 connected to one or more external peripherals such as printer 454 and speakers 456. The network interface controller 442 is coupled to one or more devices, such as data storage 446, remote computer 448 running one or more remote applications 450, via a network 444 which may comprise the Internet cloud, a local area network (LAN), wide area network (WAN), storage area network (SAN), etc. A small computer systems interface (SCSI) adapter (not shown) may also be coupled to the system bus. The SCSI adapter can couple to various SCSI devices such as a CD-ROM drive, tape drive, etc.

The non-volatile memory 428 may include various removable/non-removable, volatile/nonvolatile computer storage media, such as hard disk drives that reads from or writes to non-removable, nonvolatile magnetic media, a magnetic disk drive that reads from or writes to a removable, nonvolatile magnetic disk, an optical disk drive that reads from or writes to a removable, nonvolatile optical disk such as a CD ROM or other optical media. Other removable/non-removable, volatile/nonvolatile computer storage media that can be used in the exemplary operating environment include, but are not limited to, magnetic tape cassettes, flash memory cards, digital versatile disks, digital video tape, solid state RAM, solid state ROM, and the like.

A user may enter commands and information into the computer through input devices connected to the user input interface 431. Examples of input devices include a keyboard and pointing device, mouse, trackball or touch pad. Other input devices may include a microphone, joystick, game pad, satellite dish, scanner, etc.

The computer 411 may operate in a networked environment via connections to one or more remote computers, such as a remote computer 448. The remote computer may comprise a personal computer (PC), server, router, network PC, peer device or other common network node, and typically includes many or all of the elements described supra. Such networking environments are commonplace in offices, enterprise-wide computer networks, intranets and the Internet.

When used in a LAN networking environment, the computer 411 is connected to the LAN 444 via network interface 442. When used in a WAN networking environment, the computer 411 includes a modem 440 or other means for establishing communications over the WAN, such as the Internet. The modem 440, which may be internal or external, is connected to the system bus 426 via user input interface 431, or other appropriate mechanism.

The computing system environment, generally referenced 410, is an example of a suitable computing environment and is not intended to suggest any limitation as to the scope of use or functionality of the invention. Neither should the computing environment be interpreted as having any dependency or requirement relating to any one or combination of components illustrated in the exemplary operating environment.

In one embodiment, the software adapted to implement the system and methods of the present invention can also reside in the cloud. Cloud computing provides computation, software, data access and storage services that do not require end-user knowledge of the physical location and configuration of the system that delivers the services. Cloud computing encompasses any subscription-based or pay-per-use service and typically involves provisioning of dynamically scalable and often virtualized resources. Cloud computing providers deliver applications via the internet, which can be accessed from a web browser, while the business software and data are stored on servers at a remote location.

In another embodiment, software adapted to implement the system and methods of the present invention is adapted to reside on a computer readable medium. Computer readable media can be any available media that can be accessed by the computer and capable of storing for later reading by a computer a computer program implementing the method of this invention. Computer readable media includes both volatile and nonvolatile media, removable and non-removable media. By way of example, and not limitation, computer readable media may comprise computer storage media and communication media. Computer storage media includes volatile and nonvolatile, removable and non-removable media implemented in any method or technology for storage of information such as computer readable instructions, data structures, program modules or other data. Computer storage media includes, but is not limited to, RAM, ROM, EEPROM, flash memory or other memory technology, CD-ROM, digital versatile disks (DVD) or other optical disk storage, magnetic cassettes, magnetic tape, magnetic disk storage or other magnetic storage devices, or any other medium which can be used to store the desired information and which can be accessed by a computer. Communication media typically embodies computer readable instructions, data structures, program modules or other data such as a magnetic disk within a disk drive unit. The software adapted to implement the system and methods of the present invention may also reside, in whole or in part, in the static or dynamic main memories or in firmware within the processor of the computer system (i.e. within microcontroller, microprocessor or microcomputer internal memory).

Other digital computer system configurations can also be employed to implement the system and methods of the present invention, and to the extent that a particular system configuration is capable of implementing the system and methods of this invention, it is equivalent to the representative digital computer system of Figure 25 and within the spirit and scope of this invention. Once they are programmed to perform particular functions pursuant to instructions from program software that implements the system and methods of this invention, such digital computer systems in effect become special purpose computers particular to the method of this invention. The techniques necessary for this are well known to those skilled in the art of computer systems.

It is noted that computer programs implementing the system and methods of this invention will commonly be distributed to users on a distribution medium such as floppy disk, CDROM, DVD, flash memory, portable hard disk drive, etc. From there, they will often be copied to a hard disk or a similar intermediate storage medium. When the programs are to be run, they will be loaded either from their distribution medium or their intermediate storage medium into the execution memory of the computer, configuring the computer to act in accordance with the method of this invention. All these operations are well known to those skilled in the art of computer systems.

The flowchart and block diagrams in the Figures illustrate the architecture, functionality, and operation of possible implementations of systems, methods and computer program products according to various embodiments of the present invention. In this regard, each block in the flowchart or block diagrams may represent a module, segment, or portion of code, which comprises one or more executable instructions for implementing the specified logical function(s). It should also be noted that, in some alternative implementations, the functions noted in the block may occur out of the order noted in the Figures. For example, two blocks shown in succession may, in fact, be executed substantially concurrently, or the blocks may sometimes be executed in the reverse order, depending upon the functionality involved. It will also be noted that each block of the block diagrams and/or flowchart illustration, and combinations of blocks in the block diagrams and/or flowchart illustration, can be implemented by special purpose hardware-based systems that perform the specified functions or acts, or by combinations of special purpose hardware and computer instructions. The terminology used herein is for the purpose of describing particular embodiments only and is not intended to be limiting of the invention. As used herein, the singular forms "a", "an" and "the" are intended to include the plural forms as well, unless the context clearly indicates otherwise. It will be further understood that the terms "comprises" and/or "comprising," when used in this specification, specify the presence of stated features, integers, steps, operations, elements and/or components, but do not preclude the presence or addition of one or more other features, integers, steps, operations, elements, components and/or groups thereof.

The corresponding structures, materials, acts and equivalents of all means or step plus function elements in the claims below are intended to include any structure, material, or act for performing the function in combination with other claimed elements as specifically claimed. The description of the present invention has been presented for purposes of illustration and description, but is not intended to be exhaustive or limited to the invention in the form disclosed. As numerous modifications and changes will readily occur to those skilled in the art, it is intended that the invention not be limited to the limited number of embodiments described herein. Accordingly, it will be appreciated that all suitable variations, modifications and equivalents may be resorted to, falling within the spirit and scope of the present invention. The embodiments were chosen and described in order to best explain the principles of the invention and the practical application and to enable others of ordinary skill in the art to understand the invention for various embodiments with various modifications as are suited to the particular use contemplated.