17.2PreachingbyExample:TheArticulatedPlaceholderModel 289
try (triangle count) that constructs the mesh, to emulate animation and rendering
costs. Finally, it must be able to generate the mesh rapidly and automatically. The
technique we suggest to satisfy all of these requirements is to use implicit surfac-
es, also known as level sets, to generate the mesh geometry.
A level set, generally speaking, is a set of points
1
,,
n
x
x
for which a real-
valued function f of n variables satisfies the constraint
1
,...,
n
f
xxc , where c is
a constant. The entire set is then
11
,..., ,...,
nn
x
xfxx c
. (17.3)
When 3n , the set of points defined by the constraint creates what is called a
level surface, also commonly known as an isosurface or an implicitly defined sur-
face. A classic example of a 3D implicit surface is the sphere, which can be de-
fined as a set of points
,,
x
yz through the general equation
2222
,, ,,
x
yz f xyz x y z r
. (17.4)
In this case, our constant c would be
2
r
and our implicit surface would be defined
as all the 3D points
,,
x
yz located at a distance r from the origin, effectively
creating a sphere.
Another way to picture an implicit surface is to imagine that the function
1
,...,
n
f
xx defines a density field in the space where it is located and that all the
points having a certain density value c within the field are part of the set (which
is a surface in the 3D case). Finding the density value at a certain point is done
simply by evaluating f with the coordinates of that point.
In the case of our placeholder system, we define a mesh by generating an
implicit surface from the skeleton itself. The idea is to define a density field
based on an inverse squared distance function defined from the bones of the skel-
eton. As we saw earlier, a bone only consists of a transformation matrix and a
reference to its parent. However, to create a distance function for a given bone,
the bone must be mathematically represented as a line segment rather than a sin-
gle transformation. To obtain a line segment from the bone, we use the bone-
space transform. The translation of the bone
trans
j
B
is used to create one end of the
line segment, while the parent’s translation
trans
p
arent j
B
is used as the other end of the
segment, where
p
arent j maps the index j to the index of the parent bone. (Note
that we’re using B and not
1
B
here.) With this formulation, the squared distance
function can be defined as
290 17.PlaceholdersbeyondStaticArtReplacement
2
trans trans trans trans
parent parent parent
2
trans trans trans trans
parent
2
,if 0;
dist , , if 0;
,otherwise,
j
jjj
jjjj
j
d
pB pB B B
ppB pBBB
(17.5)
where
,,
x
yz
p
and
trans trans trans
parent
trans trans
parent
jj
j
j
j
d
BBBp
BB
. (17.6)
Once the distance can be calculated for a single bone, evaluating the density
field at a certain point amounts to summing the distance function for all bones
and determining whether that point is on the surface by setting a certain distance
threshold d. The implicit surface generated from our skeleton can therefore be
formulated using the distance function and the set
dist ,
j
f
jd
pp p . (17.7)
One way to define the whole 3D surface from the field generated by the skel-
eton would be to sample every point in our 3D space and build a polygonal sur-
face from those that happen to fall directly on the threshold d. This, however,
would be extremely inefficient and would most likely produce an irregular sur-
face unless the sampling is very precise. A smarter way to generate an implicit
surface from a density field is to use the marching cubes algorithm
1
[Lorensen
and Cline 1987] or its triangular equivalent, marching tetrahedrons [Doi and
Koide 1991, Müller and Wehle 1997], which we favor here for its simplicity and
robustness.
The marching tetrahedrons algorithm, depicted in Figure 17.3, starts by sam-
pling the density field at regular intervals, creating a 3D grid. Every discrete
point is then evaluated using the density function and flagged as inside or outside
depending on the computed value of the density field in regard to the threshold
(inside if the value is higher than the threshold and outside if the value is lower).
The whole 3D grid can be seen as an array of cells defined from groups of eight
points (
22
2
points) forming a cube. Each of these cells can be further divided
in six tetrahedrons that are the base primitives defining our polygonal implicit
1
The marching cubes algorithm is explained in detail in the chapter “Volumetric Repre-
sentation of Virtual Environments” in Game Engine Gems 1 [Williams 2010].
17.2Preachingb
y
Fi
gu
22
of th
surf
a
poi
n
pos
s
dro
n
figu
r
tran
s
old
a
rati
o
Fi
gu
tetra
h
ing
o
Example:Th
u
re 17.3. Rep
r
2
p
oints is s
p
e eight cases
d
a
ce. Every t
e
n
ts can have
t
s
ible differen
t
n
. (These 16
c
r
ations.) At
s
ition occurs
a
nd other poi
n
o
n. When all
u
re 17.4. Fro
m
h
edrons algori
t
o
n the skeletal
d
eArticulated
r
esentation o
f
p
lit into six te
t
d
epicted on the
e
trahedron is
t
wo different
t
configurati
o
c
onfiguration
s
this point,
a
when some
p
n
ts are lower
)
of the tetra
h
m
the skeleton
’
t
hm. For the
a
d
istance from
t
Placeholder
f
the marchin
g
t
rahedrons. Ea
c
right, and the
built with f
o
states (insid
e
o
ns of inside
s
can
b
e red
u
a
ll of the te
t
p
oints of the
t
)
create one
o
h
edrons have
’
s bone, the g
e
a
bove example
t
he root bone,
3
Model
g
t
etrahedron
s
c
h of these tet
r
geometry is g
e
o
u
r
different
p
e
or outside).
e
and outside
u
ced to two
m
t
rahedrons c
o
t
etrahedron
a
o
r two
t
riangl
e
been evalua
t
eometry is ge
n
e
, the bone’s d
e
giving the lim
b
0
1
2
s
algorithm.
E
r
ahedrons is
m
e
nerated accor
d
p
oints, and
e
Therefore, t
h
values for
e
m
irrored sets
o
o
ntaining a
t
a
re higher tha
n
e
s based on t
h
t
ed, have be
e
n
erated using
ensity was re
d
b
extremities
a
E
very cell of
m
atched to one
d
ingly.
e
ach of these
h
ere exist 16
e
ach tetrahe-
o
f eight con-
t
ransition (a
n
the thresh-
h
eir configu-
e
n classified,
the marching
d
uced depend-
a
smaller size.
291
292 17.PlaceholdersbeyondStaticArtReplacement
and have generated their triangles, the resulting geometry is a fully defined im-
plicit surface based on the density field. In our case, with a density field generat-
ed from the squared distance to our skeleton, the implicit surface should look like
a party balloon having roughly the shape of our skeleton, as shown in Fig-
ure 17.4.
One of the advantages of using this technique is that the amount of generated
geometry can be easily adjusted by increasing or decreasing the sampling preci-
sion. A larger sampling grid generates shapes with less geometry, whereas a finer
sampling grid increases the polygon count. This comes in handy and generates a
placeholder mesh that provides similar performance to the final desired asset. It
also becomes particularly useful when working under polygon constraints for
game objects, as the generated mesh provides a good performance estimate.
AutomaticVertexWeightAssignment
At this point, we have an animated skeleton and a mesh generated from the skele-
ton’s bind pose. This is a good start, but nothing actually binds the mesh to the
skeleton. This means that even if the skeleton is animated, the mesh will not fol-
low with the movements. The process of binding the mesh to the skeleton is
called vertex weight assignment or simply vertex assignment and consists of de-
fining which vertices are affected by a bone or multiple bones and what influ-
ence, or weight, each of these bones has in affecting the vertices’ positions. The
weight is usually normalized between zero and one, and it represents the percent-
age of that particular bone’s transformation that is used for the animation.
For example, imagine that you have a mesh that needs to be bound to a skele-
ton having only one bone j. In this particular case, all the vertices of the mesh
would be assigned to the bone j with a weight equal to one. In a more complex
case, say for an arm, all the vertices that are directly in the middle of the elbow
joint would be equally affected by the forearm bone and the upper arm bone. The
weight would therefore be 0.5 for the forearm and 0.5 for the upper arm. When
animated, these vertices would blend half of the forearm’s and half of the upper
arm’s transforms to obtain their final positions. (More to come on this topic in
the next section.)
In 3D modeling and animation, this whole weight assignment process is usu-
ally done by selecting a bone in the animation skeleton and painting the im-
portance of that bone directly on the vertices of the mesh. This practice is often
referred to as weight painting, and it remains relatively time consuming. In this
regard, this approach is hardly practicable for our placeholder system since we
need something fast and completely automated. Luckily for us, many 3D CAD
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
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.