54 6. SIMULATION AS AN OPTIMIZATION PROBLEM
6.6 SOLVING TIME INTEGRATION USING
LOCAL-GLOBAL ALTERNATION
We have spent quite a bit of time deriving the formulation of Qg to make sure you understand
how it works. If you are only interested in coding up a working implementation, this is where
things get interesting.
e local-global optimization consists of two steps that are iteratively executed until con-
vergence or until you decide the solution is good enough. e nice thing is that the error decreases
monotonically so you’ll know for sure that the more iterations you spend, the more accurate the
solution will be. In the first step, we will find the minimizing values for the auxiliary variables
d assuming that x is fixed. is can be done in parallel since every spring can be optimized over
seperately. In the second, global step, we will assume d is fixed and optimize for x.
1. Local step. Assume x is fixed and optimize for d. is can be done in parallel because
every spring can be treated separately. is will reset the springs to their rest length. By
doing so they break the connection between the particle positions.
2. Global step. In the second global step, we assume d is fixed and we optimize over all
particle states x essentially reconnecting the springs into a state with lower energy.
6.6.1 LOCAL STEP
Assuming x is fixed, finding the values for d is actually very easy. e minimizing values for
d is just the rest length direction of the spring. We just need to project every spring onto the
rest length. is is visualized in Figure 6.3 for a triangle with three springs. Every spring i is
rescaled along p
i
1
p
i
2
to have length L
i
. e figure shows the projected springs in blue. We
see that this step disconnects the springs from the particles. We’re not changing the directions,
only the lengths. is separation will be resolved in the global step which will reconnect the
springs to the particles. e projection is performed separately for every spring so this is very
easy to parallelize in the implementation. Mathematically, for every spring i we compute d
i
as
d
i
D
p
i
1
p
i
2
jjp
i
1
p
i
2
jj
L
i
:
(6.19)
6.6.2 GLOBAL STEP
In the global step, we will keep d fixed and optimize over x. Whereas the local step disconnected
the springs from the particles, the global step will bring everything together again. In this step,
we’re left with solving the unconstrained quadratic function given in Equation (6.18) over x.
6.6. SOLVING TIME INTEGRATION USING LOCAL-GLOBAL ALTERNATION 55
z
x
y
x
0
x
2
x
1
Figure 6.3: Visualization of the local solve where the springs are projected onto their rest length
along the direction connecting the two particles. e original springs are shown in black and
the projected springs are shown in blue.
We know that the minimum of a quadratic function is simply solved as the critical point. So we
find the solution by setting the gradient equal to zero and solving for x
M C h
2
L
x D My C h
2
Jd C h
2
f
ext
,
M C h
2
L
x D b:
(6.20)
And this is just a linear system of the form Ax D b which we know how to solve. Okay!
Phew, we’re done, finally! We have now described an alternative way to integrate mass spring
systems over time. But wait. We said this was supposed to be a faster method than before, but
we still have to solve a linear system in every time step. And now we even have those auxiliary
variables to compute! Ahah, very good comment. But the thing that makes this method fast is
the fact that both M and L are fixed and don’t change over time. e right-hand side b will be
different in every time step but the matrix on the left-hand side won’t ever change!
For a symmetric positive definite matrix such as our Hessian, a sparse Cholesky factor-
ization is guaranteed to exist and can be precomputed to efficiently solve the linear system in
every iteration of the local-global optimization process. e Cholesky factorization of a matrix
A will give you
A D KK
T
;
(6.21)
where K is a lower triangular matrix meaning that everything above the diagonal will be zero.
e system Ax D b then becomes KK
T
x D b. Defining K
T
x D z, the overall solution can be
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.