6.5. LOCAL-GLOBAL ALTERNATION PROBLEM FORMULATION 51
erefore, we are looking for the value of x that minimizes g.x/. We do not really care
about the actual value of the function. We only care about the minimizer since this solves our
original problem of time integrating the mass-spring system.
We are now faced with minimizing a nonlinear function. e straightforward way to go
about this is to use Newton’s method. If you recall, that is exactly the approach we took in
Chapter 5 where we solved implicit integration by using one iteration of Newton’s method.
is time, however, we will be taking a different approach, one that will lead to a more
efficient implementation when you really care about getting a result on screen fast and aren’t too
concerned about accuracy.
6.5 LOCAL-GLOBAL ALTERNATION PROBLEM
FORMULATION
e method that we will use to optimize this problem formulation is named local-global alter-
nation. is method is sometimes also referred to as block coordinate descent. e trick to make
this strategy work is to introduce some additional auxiliary variables. In our case, these auxiliary
variables will be the spring directions. Let’s look at Hooke’s law again to make this more con-
crete. For a spring connecting two particles with positions p
1
and p
2
and with rest length L and
spring stiffness k, we have the energy definition
E.p
1
; p
2
/ D
k
2
.
jjp
1
p
2
jj L
/
2
:
(6.11)
Making use of the following lemma (see the original paper by Liu et al. [2013] for a proof
of this lemma):
Lemma: 8 p
1
; p
2
2 R
3
and 8L 0 W
min
jjdjjDL;d2R
3
jj
.
p
1
p
2
/
djj
2
D
.
jjp
1
p
2
jj L
/
2
:
(6.12)
e left-hand side is a small minimization problem over the auxiliary variable d, where the
positions p
1
and p
2
are kept fixed. e auxiliary variable d is the vector that represents the spring
direction and is constraint to be of length equal to the rest length L. is is easily visualized in
Figure 6.2. So, why do we need to be dealing with this additional mathematical construct? It
will helps us to rewrite E.x/ in Equation (6.9). is way the minimization problem g.x/ can be
written as a new problem Qg
.
x; d
/
and additional constraints on the auxiliary variables.
So let’s now look at the whole mass-spring system containing S springs. For a spring
i 2
Œ
0; : : : ; S 1
, we have endpoints p
i
1
and p
i
2
with particle indices i
1
and i
2
, respectively.
52 6. SIMULATION AS AN OPTIMIZATION PROBLEM
p
1
||d|| = L
d
p
2
Figure 6.2: e auxiliary variable d 2 R
3
for the spring connecting p
1
and p
2
is shown as the red
vector. is variable is equal to the spring direction with length equal to the spring rest length.
Finally, we have a stiffness constant
k
i
. Using the lemma we can rewrite the energy potential for
all springs as
1
2
S1
X
iD0
k
i
jjp
i
1
p
i
2
d
i
jj
2
;
(6.13)
where d
i
is still restricted to have a length equal to the rest length jjd
i
jj D L
i
.
We can get rid of the sum notation by using a little bit of mathematical trickery. e
equation can be rewritten in matrix form
1
2
S1
X
iD0
k
i
jjp
i
1
p
i
2
d
i
jj
2
D
1
2
x
T
Lx x
T
Jd;
(6.14)
where x 2 R
3N
is the vector that stacks all N particle positions p
i
2 R
3
in a single long vector.
Similarly, d 2 R
3S
stacks all the individual d
i
2 R
3
vectors. We see that L 2 R
3N 3N
and J 2
R
3N 3S
and they are given by the following expressions:
L D
S1
X
i
D
0
k
i
A
i
A
T
i
!
˝ I
J D
S1
X
iD0
k
i
A
i
S
T
i
!
˝ I;
(6.15)
where I 2 R
33
is the identity matrix. e vectors A
i
2 R
N
and S
i
2 R
S
are indicator functions
that are mostly zero. For a spring i, A
i
will have element i
1
equal to 1 and element i
2
equal to
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.