Graphics Reference
In-Depth Information
the intrinsic deformation and translation of each triangle. Because we've ignored
the source translations, our solution will not be unique: We can add any constant
translation to all the
d
s
vectors and get an equally good solution. By explicitly
setting the displacement
d
s
for one triangle
s
in the target, we remove this
ambiguity.
There is a further problem: If the vertex
w
i
is shared by two triangles
s
1
and
s
2
, it's possible that
T
s
1
w
i
+
d
s
1
=
T
s
2
w
i
+
d
s
2
.
(25.33)
In that case, the vertex will be sent to two different places by the two different
transformations, and thus will not define a transformation on the mesh,
M
,but
rather on the set of triangles in the mesh. Letting
N
(
w
i
)
denote the set of all trian-
gles that contain the vertex
w
i
, we therefore seek transformations satisfying
T
s
1
w
i
+
d
s
1
=
T
s
2
w
i
+
d
s
2
for all
s
1
,
s
2
∈
N
(
w
i
)
.
(25.34)
We express this goal numerically as the problem of minimizing
2
,
C
S
s
−
T
t
(25.35)
(
s
,
t
)
∈
subject to
T
s
1
w
i
+
d
s
1
=
T
s
2
w
i
+
d
s
2
for all
s
1
,
s
2
∈
N
(
w
i
)
,
(25.36)
where
2
denotes the sum of the squares of the entries in the matrix
A
.(The
square root of this quantity is called the
Frobenius norm
of the matrix
A
.) This
is a quadratic optimization problem, which can be solved by standard numeri-
cal techniques. (As an aside, we caution you against writing your own quadratic
optimizer, unless you are an expert in numerical analysis. Instead, find one you
like, and get to be an expert in using it.) One problem with this formulation is the
number of constraints: There's a constraint for every pair of triangles that meet at
a vertex. Even if every vertex had degree three, this would still be a number of
constraints that's equal to the number of vertices, which is very large in general.
The problem begs for reformulation.
Sumner and Popovic perform a natural transformation: Instead of treating the
transformations
T
i
as unknowns, with constraints on where they send the mesh
vertices, they treat the eventual vertex locations
w
i
as unknowns, and write the
transformations
T
i
in terms of these.
Recall that each source deformation transformation
S
was given by an expres-
sion of the form
S
=
VV
−
1
. If we knew the final positions
w
i
of the target vertices,
then the target deformations would similarly be given by expressions of the form
T
=
WW
−
1
. The entries of the matrix
T
are evidently
linear
functions of the
unknown positions
w
i
. The minimization problem becomes
A
|
M
|
j
=
1
S
s
j
−
T
t
j
2
,
min
w
1
,
(25.37)
...
,
w
n
where the
S
s
j
are all known, and in the expression for
T
,
T
=
WW
−
1
,
(25.38)
