42 5. IMPLICIT INTEGRATION
is formulation allows us to efficiently use a preconditioned conjugate gradient method.
is method is particularly well suited for positive definite symmetric systems. e left-hand
side matrix A of the system is stored in the BCRS format. e right-hand side b is a dense
vector. ey are defined as follows:
A D
M h
@f
@v
h
2
@f
@x
b D h
f
n
C h
@v
@x
v
n
:
(5.22)
e conjugate gradient algorithm used to iteratively solve this system Av D b is given in
Algorithm 5.2. It is an update method that starts with an initial guess that is iteratively updated
by adding scalar multiples of the search directions. e filtering algorithm to implement the
velocity constraints is given in Algorithm 5.3.
After converging, the solution will satisfy the following two conditions.
• For each particle, the component of the residual vector r in the unconstrained directions
will be zero.
• For each particle, the component of v in the constrained directions will equal the pre-
scribed constraint z.
5.7.1 PRECONDITIONING
Preconditioning is a technique that is commonly used to transform the system to a form that’s
more suitable for a numerical algorithm. is is the reason Krylov methods have such good
properties. In our case we would like the system matrix to be close to the unity matrix since
would make the system trivial to solve. Decreasing the condition number of the matrix will
increase the rate of convergence. e preconditioning matrix P that we use is a simple diagonal
matrix that is readily available and inexpensive to compute. e diagonal elements are computed
as P
i i
D
1
A
i i
, this is also known as diagonal scaling.
Alternative preconditioners are for example incomplete Cholesky factorization,
successive-symmetric over-relaxation or block diagonal preconditioners.
5.8 POSITION ALTERATIONS
So far, we’ve seen how constraints can be used to impose conditions on the particle positions. It
seems natural to also want to impose constraints on the particle positions. A common example
is when a cloth particle collides with a solid object and needs to be displaced to be back on the
5.8. POSITION ALTERATIONS 43
Algorithm 5.2 Modified Preconditioned Conjugate Gradients
1: v D z
2: ı
0
D filter.b/
T
P filter.b/
3: r D filter.b Av/
4: c D filter.P
1
r/
5: ı
new
D r
T
c
6: while ı
new
>
2
ı
0
do
7: q D filter.Ac/
8: ˛ D ı
new
=
c
T
q
9: v D v C ˛c
10: r D r ˛q
11: s D P
1
r
12: ı
old
D ı
new
13: ı
new
D r
T
s
14: c D filter.s C
ı
new
ı
old
c/
15: end while
Algorithm 5.3 Constraint Filter
1: for i D 1 to N do
2: Oa
i
D S
i
a
i
3: end for
4: return Oa
object boundary. You could just displace the particles during the simulation but this would lead
to instabilities since the neighboring particles aren’t informed until the next time step. Particles
are likely to end up in unfavorable positions, resulting in large forces. In order to make position
alterations, we will need to incorporate this update in the entire system update. We can do this
by modifying the position update, including the desired displacement y
n
at time t
n
as follows:
x D h
.
v
n
C v
/
C y
n
:
(5.23)
Repeating the derivations made earlier in this chapter, we find the following system:
M h
@f
@v
h
2
@f
@x
v D h
f
n
C h
@f
@x
v
n
C
@f
@x
y
n
: (5.24)
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.