Mesh skinning technique

A computer-implemented method for computing skinning weights. The method includes traversing one or more paths from a first voxel included in a voxelization associated with a three-dimensional model to a second voxel included in the voxelization. The first voxel intersects a first influence included in the three-dimensional model. The second voxel intersects a target vertex associated with the three-dimensional model. The voxelization includes a set of interior voxels. The first voxel and the second voxel are included in the set of interior voxels. The method also includes identifying a first path included in the one or more paths that is associated with a first distance value related to the second voxel that indicates that the first path represents the shortest distance between the first voxel and the second voxel. The method further includes assigning a skinning weight to the target vertex based on the first distance value.

BACKGROUND OF THE INVENTION

Field of the Invention

The present invention relates generally to computer aided design (CAD) applications and, in particular, to a mesh skinning technique.

Description of the Related Art

Three-dimensional animation generally involves creating a three-dimensional model or skin, creating a transformation hierarchy for that model, and binding the transformation hierarchy to the model. An animation is a sequence of translations for one or more influences in the transformation hierarchy. When the animation proceeds, the translations that are made to the influences in the transformation hierarchy cause the skin to deform.

Generally speaking, the degree to which any particular part of a skin deforms is related to a value known as a binding weight. Any particular portion of the skin may be affected by a particular influence to a greater or lesser degree based on the binding weight associated with that portion of skin and that particular influence.

Typically, binding weights are assigned manually. There are several drawbacks, however, with assigning binding weights manually. One drawback is that assigning weights is unintuitive, as the impact of assigning a particular weight for a particular pose of the model is not immediately clear to an animator. Another drawback is that assigning weights for a model is time consuming, as each vertex of a model must be assigned a weight.

As the foregoing illustrates, what is needed in the art are improved techniques for assigning skinning weights to a three-dimensional model.

SUMMARY OF THE INVENTION

One embodiment of the invention is a computer-implemented method for computing skinning weights. The method includes traversing one or more paths from a first voxel included in a voxelization associated with a three-dimensional model to a second voxel included in the voxelization, wherein the first voxel intersects a first influence included in the three-dimensional model, and the second voxel intersects a target vertex associated with the three-dimensional model, wherein the voxelization includes a set of interior voxels, and wherein the first voxel and the second voxel are included in the set of interior voxels. The method also includes identifying a first path included in the one or more paths that is associated with a first distance value related to the second voxel that indicates that the first path represents the shortest distance between the first voxel and the second voxel across the one or more paths. The method further includes assigning a skinning weight to the target vertex based on the first distance value.

One advantage of the disclosed techniques is that an application automatically generates skinning weights for skinning a three-dimensional model, which reduces the amount of time needed to animate models. Another advantage is that the techniques generate weights that produce improved deformations of model skins, which improves the quality of resulting animations.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS

System Overview

FIG. 1is a block diagram of a system100configured to implement one or more aspects of the present invention. System100may be a computer workstation, personal computer, or any other device suitable for practicing one or more embodiments of the present invention. As shown, system100includes one or more processing units, such as central processing unit (CPU)102, and a system memory104communicating via a bus path that may include a memory bridge105. CPU102includes one or more processing cores, and, in operation, CPU102is the master processor of system100, controlling and coordinating operations of other system components. System memory104stores software applications and data for use by CPU102. CPU102runs software applications and optionally an operating system. Memory bridge105, which may be, e.g., a Northbridge chip, is connected via a bus or other communication path (e.g., a HyperTransport link) to an I/O (input/output) bridge107. I/O bridge107, which may be, e.g., a Southbridge chip, receives user input from one or more user input devices such as keyboard108or mouse109and forwards the input to CPU102via memory bridge105. In alternative embodiments, I/O bridge107may also be connected to other input devices such as a joystick, digitizer tablets, touch pads, touch screens, still or video cameras, motion sensors, and/or microphones (not shown).

One or more display processors, such as display processor112, are coupled to memory bridge105via a bus or other communication path113(e.g., a PCI Express, Accelerated Graphics Port, or HyperTransport link); in one embodiment display processor112is a graphics subsystem that includes at least one graphics processing unit (GPU) and graphics memory. Graphics memory includes a display memory (e.g., a frame buffer) used for storing pixel data for each pixel of an output image. Graphics memory can be integrated in the same device as the GPU, connected as a separate device with the GPU, and/or implemented within system memory104. Display processor112periodically delivers pixels to a display device110that may be any conventional CRT or LED monitor. Display processor112can provide display device110with an analog or digital signal.

A system disk114is also connected to I/O bridge107and may be configured to store content and applications and data for use by CPU102and display processor112. System disk114provides non-volatile storage for applications and data and may include fixed or removable hard disk drives, flash memory devices, and CD-ROM, DVD-ROM, Blu-ray, HD-DVD, or other magnetic, optical, or solid state storage devices.

A switch116provides connections between I/O bridge107and other components such as a network adapter118and various add-in cards120and121. Network adapter118allows system100to communicate with other systems via an electronic communications network, and may include wired or wireless communication over local area networks and wide area networks such as the Internet.

Other components (not shown), including USB or other port connections, film recording devices, and the like, may also be connected to I/O bridge107. For example, an audio processor may be used to generate analog or digital audio output from instructions and/or data provided by CPU102, system memory104, or system disk114. Communication paths interconnecting the various components inFIG. 1may be implemented using any suitable protocols, such as PCI (Peripheral Component Interconnect), PCI Express (PCI-E), AGP (Accelerated Graphics Port), HyperTransport, or any other bus or point-to-point communication protocol(s), and connections between different devices may use different protocols, as is known in the art.

In one embodiment, display processor112incorporates circuitry optimized for graphics and video processing, including, for example, video output circuitry, and constitutes a graphics processing unit (GPU). In another embodiment, display processor112incorporates circuitry optimized for general purpose processing. In yet another embodiment, display processor112may be integrated with one or more other system elements, such as the memory bridge105, CPU102, and I/O bridge107to form a system on chip (SoC). In still further embodiments, display processor112is omitted and software executed by CPU102performs the functions of display processor112.

Pixel data can be provided to display processor112directly from CPU102. In some embodiments of the present invention, instructions and/or data representing a scene are provided to a render farm or a set of server computers, each similar to system100, via network adapter118or system disk114. The render farm generates one or more rendered images of the scene using the provided instructions and/or data. These rendered images may be stored on computer-readable media in a digital format and optionally returned to system100for display.

Alternatively, CPU102provides display processor112with data and/or instructions defining the desired output images, from which display processor112generates the pixel data of one or more output images, including characterizing and/or adjusting the offset between stereo image pairs. The data and/or instructions defining the desired output images can be stored in system memory104or a graphics memory within display processor112. In an embodiment, display processor112includes 3D rendering capabilities for generating pixel data for output images from instructions and data defining the geometry, lighting shading, texturing, motion, and/or camera parameters for a scene. Display processor112can further include one or more programmable execution units capable of executing shader programs, tone mapping programs, and the like.

In one embodiment, application150is stored in system memory104. Application150may be any application configured to display a graphical user interface (GUI) on display device110. Application150is configured to accept user input for generating and modifying a three-dimensional model, and to perform certain processing techniques on the three-dimensional model.

It will be appreciated that the system shown herein is illustrative and that variations and modifications are possible. The connection topology, including the number and arrangement of bridges, may be modified as desired. For instance, in some embodiments, system memory104may be connected to CPU102directly rather than through a bridge, and other devices may communicate with system memory104via memory bridge105and CPU102. In other alternative topologies display processor112may be connected to I/O bridge107or directly to CPU102, rather than to memory bridge105. In still other embodiments, I/O bridge107and memory bridge105may be integrated in a single chip. In addition, the particular components shown herein are optional. For instance, any number of add-in cards or peripheral devices might be supported. In some embodiments, switch116is eliminated, and network adapter118and add-in cards120,121connect directly to I/O bridge107.

Skinning Weights for Vertex Deformation During Model Animation

FIG. 2Ais an illustration of a geometry model200, according to one embodiment of the present invention. As shown, the geometry model200includes a skin202and a transformation hierarchy204that is bound to the skin. The skin202is a mesh that includes vertices210and edges212that together define the mesh. The transformation hierarchy204is a hierarchy of influences206that may each influence the motion of vertices210within skin202during animation of the geometry model200, as is generally known. In some embodiments, the transformation hierarchy204is a skeleton204that includes bones206and joints208. In other embodiments, the transformation hierarchy204includes other types of influences, such as points, spheres, capsules, and other types of influences, as is generally known. The skin202is bound to the transformation hierarchy204so that movement of influences206in the transformation hierarchy204causes deformation of the skin202. The skin occupies a bounding box238whose limits are defined by the maximum extent of the skin202in three orthogonal directions (x, y, and z). For purposes of illustration, the model200is a cylinder, which has simple geometry. However, those of skill in the art will understand that the techniques described herein can be applied to any geometry model. Further, in some embodiments, the geometry model200does not include the transformation hierarchy204of influences206.

During animation of the model200, application150applies a skin deformation algorithm to deform the skin202based on the movements of the influences206. Generally speaking, skin deformation algorithms determine a modified position for each vertex210in the skin202based on transformations of influences206in the transformation hierarchy204. In many techniques, the movements of one or more influences contribute to the modified position for any particular vertex. The amount that each influence contributes to the modified position of any particular vertex is based on a weight value that is associated with that particular influence-vertex combination. Thus, the modified position for any particular vertex210is based on the transformation amounts for one or more influences206, each modified by a weight value.

FIG. 2Bis an illustration of a geometry model200in a deformed state, according to one embodiment of the present invention. As shown, the deformed geometry model200includes the skin202and transformation hierarchy204. Because the transformation hierarchy204is bound to the skin202, moving the influences206of the transformation hierarchy204as shown, causes the skin202to deform in the manner shown. More specifically, as shown, vertices210of the skin202are moved based on the movements of the influences206.

One example of a skin deformation algorithm is linear blend skinning (LBS). LBS calculates a modified position (pi′) for each vertex210in the skin202. The input to LBS includes a user-specified rest-pose mesh M (e.g., the skin202) with the following vertex positions (pi):
p1,p2, . . . ,pnε3

The input to LBS also includes a corresponding transformation hierarchy (e.g., transformation hierarchy204) (Ti) specified as:
T1,T2, . . . ,Tmε3×4

LBS also accepts a weight function ωj(pi) that specifies the amount of influence a particular influence j has on vertex piof the skin202. Based on these inputs, LBS calculates modified position pi′ for each vertex210as follows:

As is apparent from the equations presented above, the vertex positions piare dependent on movement of the influences (Tj) as well as weight values (ωj). Described herein are techniques for automatically calculating weight values based on characteristics of the skin202and the transformation hierarchy204. Application150implements such a technique. The technique generally involves two phases: 1) determining geodesic distances between each vertex in the skin202and each influence206in the transformation hierarchy,204based on a solid voxelization of a geometry model that indicates voxels that are interior to the geometry model and voxels that are exterior to the geometry model; and 2) defining a weight function ωj(pi) for each vertex based on the geodesic distances between each vertex and each influence. These two phases are now described in greater detail.

Calculating Geodesic Distance

To calculate geodesic distances, application150begins with a voxelized representation of the geometric model, where such a voxelized representation includes voxels that are classified as internal (to the skin202) or external (to the skin202) voxels. Voxels may also be classified as voxels that intersect influencers206or voxels that intersect the skin202. In one embodiment, the voxelization is a uniform voxelization (FIG. 3A). In another embodiment, the voxelization is a sparse voxelization (FIG. 3B).

FIG. 3Ais an illustration of a uniform voxelization300of the geometry model200ofFIG. 2A, according to one embodiment of the present invention. As shown, the uniform voxelization includes internal voxels306, which include influencer voxels304, and boundary voxels302, as well as other internal voxels. For clarity, external voxels are not depicted inFIG. 3A.

Because the voxelization300is uniform, all voxels within the voxelization300are the same size. Boundary voxels302are voxels that intersect the skin202(FIG. 2A). Influencer voxels304are voxels that intersect influences206(FIG. 2A). Determining whether a particular voxel intersects a particular object (such as a vertex210or an influence206) may be done with techniques known to those of skill in the art. For example, to test whether a point such as a vertex is within a voxel, the coordinates of the point are compared to the coordinates of the boundaries of the voxel. If the coordinates of the point are within the boundaries of the voxel in each dimension, then the point is considered to intersect the voxel.

FIG. 3Bis an illustration of a non-uniform, sparse voxelization350of the geometry model200ofFIG. 2A, according to one embodiment of the present invention. As shown, the sparse voxelization350includes internal voxels352, boundary voxels354, and influencer voxels356.

Because the voxelization is non-uniform, the voxels in the voxelization are different sizes. As described above, boundary voxels354are voxels that intersect with the skin202(FIG. 2A). Influencer voxels356are voxels that intersect the influences206(FIG. 2A).

Once application150has a voxelized representation of a model with voxels classified as either internal or external, application150calculates geodesic distances between vertices210in the skin202and influences206in the transformation hierarchy204.FIG. 4Aand related discussion illustrate techniques for calculating geodesic distances for uniform voxelizations, andFIG. 4Band related discussion illustrate techniques for calculating geodesic distances for sparse voxelizations.

FIG. 4Ais an illustration of a portion of a voxelization400for calculating geodesic distances, according to one embodiment of the present invention. As shown, the voxelization400includes influencer voxels402that intersect an influence403, interior voxels404, boundary voxels406, and a skin408, which includes vertices410.

Geodesic distances are distances between two points through the interior of a model (as opposed to Euclidean distances, which are distances between two points without regard to whether the distances traverse the interior or exterior of a model). A geodesic distance is useful for assigning skinning weights because geodesic distances account for the structure of the model. For example, a model can include many branches, such as with a humanoid figure (e.g., the legs, arms, and head all branch off from a central entity—the trunk). By flowing through the interior of a particular three-dimensional model, the geodesic distances do not take “short cuts” through branches between space that is external to the model, and thereby roughly follow the skeleton of the model.

The geodesic distances calculated by application150are between vertices410and influences403(and more particularly between voxels that intersect vertices410and voxels that intersect influences403). More specifically, because skinning weights are generally applied to each vertex410in a three-dimensional model, and because the skinning weights indicate an amount of influence of any particular influence over the distortion of the vertex410, application150calculates geodesic distances between each voxel that overlaps a vertex410(also referred to herein as a “skin voxel”) and each voxel that intersects an influence403(also referred to herein as an “influencer voxel”402).

For any particular influencer voxel402-skin voxel pair, application150calculates the geodesic distance between the voxels in that pair as follows. Application150assigns a distance of zero to all influencer voxels402in the voxelization400and assigns a distance of infinity (or some other value indicating a “maximum” distance that is not likely to be exceeded during calculation of geodesic distances) to all other non-exterior voxels in the voxelization400. Application sets the influencer voxel402as the current voxel. For all voxels that are neighbors to the current voxel, application150calculates a proposed distance for the neighboring voxel as the Euclidean distance from the neighboring voxel to the current voxel plus the distance value of the current voxel. If the proposed distance is less than the distance value of the neighboring voxel, then application150sets the distance value for the neighboring voxel as the proposed distance. Otherwise, the application150does not modify the distance value of the neighboring voxel. Then, if the proposed distance is less than the distance value of the neighboring voxel, application150adds the neighboring voxel to a list of voxels to analyze. Application150repeats the above steps for all voxels in the list of voxels to analyze until application150determines that the list of voxels to analyze is empty. At that point, a distance value for the targeted skin voxel is known. The described technique is a form of Djikstra's algorithm, which is generally known to those of skill in the art.

The following table depicts a pseudo-code version of the above-described technique for calculating geodesic distance. This pseudo-code version calculates the geodesic distances for all voxels of a particular bone (influence) and also for all bones (influences) in a skeleton (transformation hierarchy).

In the pseudo-code provided above, lines 2-4 initialize the distance values for each non-exterior voxel to infinity. Lines 6-9 identify all voxels intersecting the influence, set the distance values for those intersecting voxels to zero, and push all of those voxels into a working queue. In lines 10-19, the following is performed. While the working queue is not empty, a voxel viis dequeued. Value dist is calculated as the distance value for voxel viplus the Euclidean distance between pvi(the center of voxel vi) and pvj(the center of voxel vj). For every neighboring voxel vjof voxel viwith a stored distance less than a value dist, the distance value for vjis updated as equal to value dist, and vjis added to the working queue. To calculate distance values from all influences to all vertices, the algorithm may be performed in parallel by multiple execution units. Once the distances between all voxels that overlap a particular influence and a particular vertex have been calculated, application150may determine a shortest distance between the vertex and the influence by simply selecting the lowest value of all influencer voxel-to-vertex distances associated with that influence and that vertex.

FIG. 4Bis an illustration of a portion of a non-uniform voxelization450for calculating geodesic distances, according to another embodiment of the present invention. As shown, the non-uniform voxelization includes influencer voxels402, interior voxels404, boundary voxels406, and a skin408, which includes vertices410. The influencer voxels402represent voxels that intersect influences206of the transformation hierarchy204in the three-dimensional model associated with the voxelization.

For the non-uniform voxelization depicted inFIG. 4B, the distance calculation would be the same as for the uniform voxelization. More specifically, application150would initialize each distance value for each voxel as with the uniform voxelization illustrated inFIG. 4A, and distances would be calculated also as described above.

In some embodiments, application150disfavors including boundary voxels406in the middle of the path between influencer voxels402and boundary voxels406by applying a multiplicative weight to the distance value for boundary voxels406. The following pseudo-code illustrates techniques for disfavoring boundary voxels406.

The pseudo-code provided in Table 2 is similar to the pseudo-code of Table 1, except that the dist value is calculated as the sum of the distance value for the current voxel (dvi) added to β multiplied by the Euclidean distance between the center of the current voxel (pvi) and the center of the neighboring voxel (pvj). Beta is a value that is either 1 or εpenalty, depending on whether the neighboring voxel is a boundary voxel. εpenaltyis a value that can be adjusted by, for example, a programmer, and determines the degree by which boundary voxels are disfavored. Techniques for disfavoring boundary voxels may be applied in association with either uniform voxelizations or sparse voxelizations.

Calculating Skinning Weights

Once application150has calculated geodesic distances, application calculates skinning weights based on the geodesic distances. Generally, the value of a skinning weight is greater when a geodesic distance is lower and lower when a geodesic distance is higher (closer influences contribute a greater degree to the deformation of vertices210than farther influences do). In some embodiments, application150calculates weights with a falloff function having the property that the weight value drops dramatically (e.g., exponentially) with distance between influencer voxel402and boundary voxel406. Additionally, in some embodiments, application150adds the Euclidean distance from the center of the boundary voxel406to the vertex410at issue to the distance between the boundary voxel406and the influencer voxel402in order to obtain a more accurate measure of influence-to-vertex distance. Such a distance is referred to herein as a “influence-to-vertex-position distance.”

In one embodiment, application150applies the following equations to calculate skinning weights, where d is a influence-to-vertex-position distance for a particular vertex-influence pair, α, λmin, and λmax are programmer-selectable parameters for controlling bind smoothness, and ω is the skinning weight, described above:
λ=(1−α)λmin+αλmax
ω=(d)−λ

In another embodiment, application150applies the following equations to calculate skinning weights:
ω=((1−α)(d)+α(d)2)−2

In some embodiments, application150calculates weights for some or all influence-vertex pairs as described above. These weights can then be applied to the associated three-dimensional model to allow associated vertex deformation during animation of the model.

FIG. 5is a flow diagram of method steps for calculating geodesic distances based on a voxelized representation of a model, according to one embodiment of the present invention. Although the steps are described in conjunction withFIGS. 1-4B, persons skilled in the art will understand that any system configured to perform the method steps, in any order, falls within the scope of the present invention.

As shown, a method500begins at step502, in which application150chooses a voxel that intersects an influence and a voxel that intersects the skin of a model for analysis. In step504, application150initializes all voxels to have a distance value of infinity and sets the distance value of voxels that intersect the influence to zero. In step506, application150sets the current voxel as the chosen voxel that intersects the influence. In step508, application150determines whether the distance to a neighboring voxel is less than the current distance value of the neighboring voxel. If the distance is less than the current distance value, then the method proceeds to step510. If the distance is not less than the current distance value, then the method proceeds to step512.

In step510, application150updates the distance value of the neighboring voxel. In step512, application150determines whether there are more neighboring voxels. If there are more neighboring voxels, then the method returns to step508. If there are no more neighboring voxels, then the method proceeds to step514. In step514, application determines whether there are more voxels to analyze. If there are more voxels to analyze, then the method proceeds to step518. If there are no more voxels to analyze, then the method proceeds to step516, in which in which application150ends the analysis. In step518, the method chooses a new current voxel. After step518, the method returns to step508.

In sum, application150automatically calculates skinning weights by using a voxelized representation of a three-dimensional model. The application calculates geodesic distances based on the voxelization and assigns weights based on the geodesic distances. Application150begins with a particular influencer voxel and examines neighboring voxels to determine whether the distance between the influencer voxel and the neighboring voxel is less than a stored distance value for that neighboring voxel. If the distance is less than the stored value, then application150replaces the stored value with the distance. Application150repeats these steps and until arriving at the target skin voxel.

Once geodesic distances are generated, application150determines skinning weights based on the geodesic distances. More specifically, application150applies a function that generates a lower weight for further distances.

One advantage of the disclosed techniques is that application automatically generates skinning weights for skinning a three-dimensional model, which reduces the amount of time needed to animate models. Another advantage is that the techniques generate weights that produce improved deformations of model skins, which improves the quality of resulting animations.

Although the application150is described herein as performing both the animating procedures for deforming of the skin202in response to movement of the influences206, and the other calculations provided herein, those of skill in the art would understand that different applications could perform various functionality described herein.