17.2PreachingbyExample:TheArticulatedPlaceholderModel 293
applications already offer a feature to automatically assign weights. While artists
usually don’t use the feature due to the poor weight maps it produces, it remains
good enough for a placeholder. If you decide to generate your placeholders di-
rectly in the 3D CAD software, your best bet might be to directly use the soft-
ware’s automatic weight system (remember that the faster your placeholder
system is up, the better). Otherwise, we’ll draw inspiration from these systems
and devise a small and simple algorithm that remains fast and produces accepta-
ble results.
Most of the existing automatic weight assignment algorithms use a distance
calculation of some sort to determine which bones affect a certain vertex. If the
animation system supports n bones per vertex, then the algorithm finds the clos-
est n bones or fewer within a certain threshold and assigns a weight to each bone
based on the distance. The distance itself is what usually differentiates one algo-
rithm from another. Some algorithms use geodesic distance on the surface, and
others use a heat diffusion simulation [Rosen 2009] to generate a volumetric dis-
tance map by filling the volume defined by the mesh with 3D voxels. The most
advanced algorithms even use mesh segmentations or other mesh analysis meth-
ods to produce the weight maps [Baran and Popović 2007, Aguiar et al. 2008].
To keep things simple, we don’t delve into any of this and simply use a skeleton-
aware Euclidean distance computation to generate the map.
What we mean by “skeleton-aware” distance is that it considers the skele-
ton’s structure when calculating distances. A pure Euclidean distance that doesn’t
consider bone connectivity would most likely lead to strange artifacts. For exam-
ple, the two feet of a character are often close to each other in space, but far apart
in the skeleton’s structure. By using only a Euclidean distance, the left foot’s ver-
tices would be partly bound to the left foot bone and partly bound to the right
foot bone since they’re close to each other. This would undoubtedly create
strange artifacts when the feet are animated.
To prevent this problem, our weight assignment algorithm functions in two
parts and is performed on every vertex of the mesh. The first part finds the clos-
est bone to a particular vertex and keeps the distance from that vertex to the bone
in memory, reusing the vertex-to-segment distance computation given by Equa-
tion (17.5). During the second step, the nearest bone’s parent and children are
recursively explored. If their distances are lower than a certain threshold t, then
the distance and bone ID is saved in a distance-ordered list, and the parent and
children of that new bone that haven’t been visited yet are recursively submitted
to the same process. If the distance is higher than the threshold, then the explora-
tion of this branch of the skeleton stops there. Once all of the bones within the
threshold are found, the n closest bones are assigned to the vertex, and their