Graphics Reference
In-Depth Information
Reference
Figure 25.29: We start with a source and a target mesh, shown at left, a triangle-by-triangle
correspondence between them (in this case, the correspondence is the fairly obvious one),
and a deformation of the source mesh, shown at the top right. The deformation transfer
algorithm provides a transformation of the target mesh that's analogous to the deformation
of the source mesh. (Courtesy of Robert Sumner and Jovan Popovic.)
and similarly for
M
, although we'll choose the origin
O
M
independently. (It's a
good idea to use something like the center of mass of
M
as the origin for
M
, and
similarly for
M
, to avoid roundoff errors in later numerical computations.)
We'll similarly use
w
i
and
w
i
for the (vector) position of the
i
th target vertex
before and after deformation. We'll assume that we're given
v
i
,
v
i
, and
w
i
for all
i
, and we wish to find
w
i
for all
i
.
To make the connection between the deformations of the source mesh
M
and
the target mesh
M
, we need a
correspondence,
C
, between them. This is pro-
vided, in the Sumner-Popovic formulation, by a collection of pairs
C
=
{
(
s
i
,
t
i
)
∈
Z
between triangles. A pair
(
s
i
,
t
i
)
indicates that the target
triangle with index
t
i
should deform similarly to the source triangle with index
s
i
.
The set
C
is a
relation
on triangle indices: It may specify that triangle 7 in
M
is to deform similarly to both triangles 2 and 96 in
M
(in which case the pairs
(
2, 7
)
and
(
96, 7
)
would both be in
C
), or that triangles 11 and 12 in
M
should
both deform like triangle 4 in
M
, in which case
C
would contain both
(
4, 11
)
and
(
4, 12
)
. It's not required that every triangle index of
M
appear as the first element
of some pair in
C
, nor that every index of
M
appear as the second element of a
pair. Nonetheless, it may be easiest to imagine
C
as being nearly a one-to-one cor-
respondence, in which a triangle on the horse's head corresponds to a triangle on
the camel's head and a triangle on the horse's left front foot corresponds to a trian-
gle on the camel's left front foot, etc. The problem of
building
or describing such
a correspondence in the first place is a separate one; it's possible to try to algo-
rithmically guess correspondences between parts, etc., but it's probably easiest to
have a user indicate correspondences between a few dozen key points, and then
use some kind of breadth-first-search-followed-by-relaxation approach to “grow”
the correspondence outward from these key points.
We'll now set about describing deformation transfer as an optimization prob-
lem. Before we write the optimization, however, we need one more enhancement
of the meshes.
Suppose we have a triangle with vertices
v
1
,
v
2
, and
v
3
, which are to be sent
to another triangle with vertices
v
1
,
v
2
, and
v
3
. It's natural to think of the transfor-
mation from one to the other in terms of the affine transformations we use all the
×
Z
:
i
=
1, 2,
...
,
c
}